<|start_filename|>usr/ps.c<|end_filename|>
#include <stdlib.h>
#include <xv6/procdump.h>

int main()
{
  procdump();
  exit(0);
}


<|start_filename|>lib/curses.c<|end_filename|>
#include <termios.h>
#include <curses.h>

// termios
struct termios termios;

// screen buffer
typedef charcell ScreenType[LINES][COLS];
ScreenType screen;

// cursol location
int cursolX, cursolY;

// initializes
void initscr(){
  clear();
  cursolX = 0;
  cursolY = 0;
  tcgetattr(0, &termios);
}

void noecho(){
  struct termios noecho;
  tcgetattr(0, &noecho);
  noecho.c_lflag &= ~ECHO;
  tcsetattr(0, TCSANOW, &noecho);
}

void curs_set(int a){
  switch(a){
  case 0: //
    printf("\033[?25l");
    break;
  case 1: // default
    printf("\033[?25h");
    break;
  }
  fflush(stdout);
}

void endwin(){
  curs_set(1);
  printf("\n");
  fflush(stdout);
  tcsetattr(0, TCSANOW, &termios);
}

// outputs
int clear(){
  if(erase() == ERR)
    return ERR;
  if(refresh() == ERR)
    return ERR;
  return OK;
}

int erase(){
  int i,j;
  printf("\033[2J"); // clear screen
  fflush(stdout);
  for(i=0; i<LINES; ++i){
    for(j=0; j<COLS; ++j){
      screen[i][j].letter = ' ';
      screen[i][j].color = 0;
    }
  }
  return OK;
}

int move(int y, int x){
  if(y < 0 || LINES <= y)
    return ERR;
  if(x < 0 || COLS <= x)
    return ERR;

  cursolY = y;
  cursolX = x;
  return OK;
}

int addch(char c){
  screen[cursolY][cursolX].letter = c;
  cursolX++;
  if(cursolX >= COLS){
    cursolX -= COLS;
    cursolY++;
  }
  return OK;
}

int addstr(char*str){
  int i;
  for(i=0; str[i]!='\0'; i++){
    if(cursolY >= LINES)
      return ERR;

    screen[cursolY][cursolX].letter = str[i];

    cursolX++;
    if(cursolX >= COLS){
      cursolX -= COLS;
      cursolY++;
    }

  }
  return OK;
}

int mvaddch(int y, int x, char c){
  if(move(y,x) == ERR)
    return ERR;
  if(addch(c) == ERR)
    return ERR;
  return OK;
}

int mvaddstr(int y, int x, char*str){
  if(move(y,x) == ERR)
    return ERR;
  if(addstr(str) == ERR)
    return ERR;
  return OK;
}

int refresh(){
  int i,j;
  char buf[LINES*(COLS+1)];
  printf("\033[H"); // move cursol to top left
  fflush(stdout);
  for(i=0; i<LINES; ++i){
    for(j=0; j<COLS; ++j){
      buf[i*(COLS+1) + j] = screen[i][j].letter;
    }
    if(i!=LINES-1)
      buf[(i+1)*(COLS+1) -1] = '\n';
  }
  buf[LINES * (COLS+1) -1] = '\0';
  printf("%s", buf);
  fflush(stdout);
  return OK;
}


<|start_filename|>include/string.h<|end_filename|>
#ifndef _UCC_STRING_H
#define _UCC_STRING_H

#include <stddef.h>

size_t strlen(const char *);
int strcmp(const char *, const char *);
int strncmp(const char *, const char *, size_t);
char *strchr(const char *, int);
char *strcpy(char *, const char *);
char *strncpy(char *, const char *, size_t);
void *memset(void *, int, size_t);
void *memcpy(void *, const void *, size_t);
void *memmove(void*, const void*, size_t);

#endif  /* string.h */


<|start_filename|>mp.c<|end_filename|>
// GAIA does not support Multiprocessor.
// Only a few initalizations are done here.

#include <sys/types.h>
#include "defs.h"
#include <xv6/param.h>
#include "memlayout.h"
#include "gaia.h"
#include "mmu.h"
#include "proc.h"

struct cpu cpus[NCPU];
struct cpu *cpu;
int ismp;
int ncpu;

void
mpinit(void)
{
  // No MP.
  ncpu = 1;
  cpus[0].id = 0;
  ismp = 0;
; cpu = &cpus[0];
}


<|start_filename|>include/ctype.h<|end_filename|>
#ifndef _UCC_CTYPE_H
#define _UCC_CTYPE_H

int isalnum(int);
int isalpha(int);
int isdigit(int);
int islower(int);
int isspace(int);
int isupper(int);
int tolower(int);
int toupper(int);

#endif  /* ctype.h */


<|start_filename|>usr/as/parse.h<|end_filename|>
#ifndef PARSE_H
#define PARSE_H
struct buf {
  int  cur;
  char str[256];
};
typedef struct buf buffer;

void skip_space_and_comma(buffer *);
int  get_token(char *, buffer *);
int  get_line (char *, buffer *);
int  regnum(char *);
unsigned read_num(char *);
void rm_comment(char *);
void rstrip(char *);
#endif


<|start_filename|>traps.h<|end_filename|>
// x86 trap and interrupt constants.

#define T_TIMER        1
#define T_COM1         2
#define T_SYSCALL      3



<|start_filename|>memlayout.h<|end_filename|>
// Memory layout

#define EXTMEM   0x2000             // Start of extended memory
#define PHYSTOP  (4*1024*1024)      // Top physical memory
#define DEVSPACE 0xFE000000         // Other devices are at high addresses

// Key addresses for address space layout (see kmap in vm.c for layout)
#define KERNBASE 0x80000000         // First kernel virtual address
#define KERNLINK (KERNBASE+EXTMEM)  // Address where kernel is linked

// [0x80000000, 0x80001FFF] is special memory mapped area.
// Kernel MUST guarantee that this memory area is directly mapped to the physical same area.
#define VAENABLE   0x80001200
#define PDADDR     0x80001204
#define INTHANDLER 0x80001100
#define INTENABLE  0x80001104
#define EPC        0x80001108
#define CAUSE      0x8000110C
#define SERIAL     0x80001000
#define SERIALWE   0x80001004

#ifndef __ASSEMBLER__
#ifndef V2P_P2V
#define V2P_P2V

static inline uint v2p(void *a) { return ((uint) (a))  - KERNBASE; }
static inline void *p2v(uint a) { return (void *) ((a) + KERNBASE); }

#endif
#endif

#define V2P(a) (((uint) (a)) - KERNBASE)
#define P2V(a) ((void*)((uint)(a) + KERNBASE))

#define V2P_WO(x) ((x) - KERNBASE)    // same as V2P, but without casts
#define P2V_WO(x) ((x) + KERNBASE)    // same as V2P, but without casts


<|start_filename|>usr/as/as.c<|end_filename|>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <fcntl.h>
#include <assert.h>
#include <unistd.h>
#include "ops.h"
#include "vector.h"
#include "parse.h"

#define ERR(...)                                \
  do {                                          \
  fprintf(stderr, __VA_ARGS__);                 \
  exit(1);                                      \
  } while(0)

#define DEBUG 0

#define D(...)                                  \
  do {                                          \
  if (DEBUG)                                    \
    fprintf(stderr, __VA_ARGS__);               \
  } while(0)


#define START_ADDR 0

int g_ln = START_ADDR;

typedef struct {
  int   pc;
  buffer buf;
  int   pseudo;
} inst;

typedef struct {
  char *lbl;
  int addr;
} label;

Vector *g_lines;
Vector *g_labels;

void
init_globals()
{
  g_lines  = vec_create(100);
  g_labels = vec_create(20);
}

void
push_label(char *str, int addr)
{
  label *l = malloc(sizeof(label));
  D("label %s\n", str);
  l->lbl = malloc(strlen(str));
  strcpy(l->lbl, str);
  l->addr = addr;
  vec_push(g_labels, l);
}


int
assoc_label(char *str)
{
  int sz = vec_lengh(g_labels);
  int i;
  for (i = 0; i < sz; ++i) {
    label *l = vec_get(g_labels, i);
    if (strcmp(l->lbl, str) == 0) {
      return l->addr;
    }
  }
  ERR("label %s not found\n", str);
}


void set_inst(inst *ins, int pc, buffer *buf, int pseudo)
{
  ins->pc  = pc;
  ins->buf = *buf;
  ins->pseudo = pseudo;
}

void
push_inst(inst *ins)
{
  inst *dst = malloc(sizeof(inst));

  memcpy(dst, ins, sizeof(inst));
  vec_push(g_lines, dst);
}



bool
check_int_range(int i, int b)
{
  int x = 1 << (b - 1);
  return -x <= i && i < x;
}

unsigned
code_i(int op, char *rx, char *ra, char *rb, int imm, int tag)
{
  unsigned x = regnum(rx);
  unsigned a = regnum(ra);
  unsigned b = regnum(rb);
  unsigned c0, c1, c2, c3;
  if (! check_int_range(imm, 8)) {
    ERR("imm is too large %d\n", imm);
  }
  c0 = ((imm & 7) << 5) + tag;
  c1 = ((b & 7) << 5) + ((imm >> 3) & 31);
  c2 = ((x & 1) << 7) + (a << 2) + (b >> 3);
  c3 = (op << 4) + (x >> 1);
  return (c3 << 24) | (c2 << 16) | (c1 << 8) | c0;
}

unsigned
code_m(int op, char *rx, char *ra, int prd, int d, int disp_mode)
{
  unsigned x = regnum(rx);
  unsigned a = regnum(ra);
  unsigned c0, c1, c2, c3;
  if (disp_mode == 0) {
    if (!(-0x8000 <= d && d <= 0xffff))
      ERR("imm too large %d\n", d);
  } else if (disp_mode == 1){
    if (!(check_int_range(d, 16)))
      ERR("disp too large %d\n", d);
  } else {
    if ((d & 3) != 0)
      ERR("disp must be a mult of 4\n");
    if (!(check_int_range(d, 18)))
      ERR("disp too large %d\n", d);
    d >>= 2;
  }
  c0 = d & 255;
  c1 = (d >> 8) & 255;
  c2 = ((x & 1) << 7) + (a << 2) + prd;
  c3 = (op << 4) + (x >> 1);

  return (c3 << 24) | (c2 << 16) | (c1 << 8) | c0;

}



unsigned
on_alu4(inst *ins, int tag)
{
  char operands[4][8];
  get_token(operands[0], &ins->buf);
  get_token(operands[1], &ins->buf);
  get_token(operands[2], &ins->buf);
  get_token(operands[3], &ins->buf);
  return code_i(0, operands[0], operands[1], operands[2],
         atoi(operands[3]), tag);
}



unsigned
calc_disp(int pc, int op, char *oprnd)
{

  int addr;

  if (oprnd[0] == '0') {
    addr = read_num(oprnd);
  } else {
    addr = assoc_label(oprnd);
  }

  if (op == 1) {
    return addr - pc - 4;
  } else {
    return addr;
  }

}

unsigned
on_misc0(inst *ins, int op, int prd, int dmode)
{
  return code_m(op, "r0", "r0", prd, 0, dmode);
}


unsigned
on_misc1(inst *ins, int op, int prd, int dmode)
{
  char operand[20];
  get_token(operand, &ins->buf);
  return code_m(op, operand, "r0", prd, 0, dmode);
}

unsigned
on_misc2(inst *ins, int op, int prd, int dmode, int dop)
{
  char operands[2][20];
  int disp;
  get_token(operands[0], &ins->buf);
  get_token(operands[1], &ins->buf);
  disp = calc_disp(ins->pc, dop, operands[1]);
  return code_m(op, operands[0], "r0", prd, disp, dmode);
}

unsigned
on_misc3(inst *ins, int op, int prd, int dmode, int dop)
{
  char operands[3][20];
  int disp;
  get_token(operands[0], &ins->buf);
  get_token(operands[1], &ins->buf);
  get_token(operands[2], &ins->buf);
  disp = calc_disp(ins->pc, dop, operands[2]);
  return code_m(op, operands[0], operands[1], prd, disp, dmode);
}

unsigned
on_jr(inst *ins)
{
  char operands[2][20];
  get_token(operands[0], &ins->buf);
  get_token(operands[1], &ins->buf);
  return code_m(5, operands[0], operands[1], 3, 0, 0);
}

int
disp_mode(char *token)
{
  if (strcmp(token, "ldl") == 0 ||
      strcmp(token, "ldh") == 0) {
    return 0;
  } else if (strcmp(token, "ldb") == 0 ||
             strcmp(token, "stb") == 0) {
    return 1;
  }
  return 2;
}

int
pred(char *token)
{
  return 0;
}

int
disp_op(char *op)
{
  if(strcmp(op, "jl") == 0  ||
     strcmp(op, "bne") == 0 ||
     strcmp(op, "beq") == 0 )
    return 1;
  else
    return 0;
}


unsigned
code(inst *ins)
{
  char token[20];
  int opcode;
  int dmode, prd, dop;
  get_token(token, &ins->buf);
  dmode = disp_mode(token);
  prd    = pred(token);
  dop = disp_op(token);
  if (strcmp(token, "halt") == 0) {
    // only allow halt macro
    return 0xffffffff;
  } else if ((opcode = find_alu4(token)) >= 0) {
    return on_alu4(ins, opcode);
  } else if ((opcode = find_misc0(token)) >= 0) {
    return on_misc0(ins, opcode, prd, dmode);
  } else if ((opcode = find_misc2(token)) >= 0) {
    return on_misc2(ins, opcode, prd, dmode, dop);
  } else if ((opcode = find_misc3(token)) >= 0) {
    return on_misc3(ins, opcode, prd, dmode, dop);
  } else if (strcmp(token, "jr") == 0) {
    return on_jr(ins);
  } else {
    D("TODO : %s\n", token);
    return -1;
  }

}



void
read_buffer(buffer *buf)
{
  int len = strlen(buf->str);
  buffer tbuf = *buf;
  char op[20];
  get_token(op, &tbuf);

  if (len <= 1) {
    // blank line
  } else if (buf->str[0] == '.') {

    if (strcmp(op, ".global") == 0) {
      // ignore
    } else if (strcmp(op, ".string") == 0) {
      inst ins;
      int len = strlen(buf->str) - 9;
      set_inst(&ins, g_ln, &tbuf, 1);
      push_inst(&ins);
      g_ln += len;
    } else if (strcmp(op, ".align") == 0) {
      char str[5];
      char num[5];
      int n;
      get_token(str, buf);  // align
      get_token(num, buf);  // get number
      n = atoi(num);
      D("n=%d\n", n);
      D("[%s]\n", buf->str + buf->cur);
      D("%s\n", buf->str + buf->cur);
      g_ln = ((g_ln + (n-1)) / n) * n;
    } else {
      D("unknown directive: %s\n", op);
    }

  } else if (buf->str[len - 1] == ':') {
    // Label
    buf->str[len - 1] = '\0';
    push_label(buf->str, g_ln);
  } else if (strcmp(op, "write") == 0) { // write macro
    inst ins;
    buffer mybf;
    char regstr[10];
    int reg;
    get_token(regstr, &tbuf);
    reg = regnum(regstr);
    mybf.cur = 0;
    strcpy(mybf.str, "ldh r29, r0, 0x8000");
    set_inst(&ins, g_ln, &mybf, 0);
    push_inst(&ins);
    g_ln += 4;
    strcpy(mybf.str, "st rN, r29, 0x1000");
    mybf.str[4] = '0' + reg;
    set_inst(&ins, g_ln, &mybf, 0);
    push_inst(&ins);
    g_ln += 4;
  } else if (strcmp(op, "br") == 0) { // br macro
    inst ins;
    buffer mybf;
    char str[30] = "jl r29, ";
    char lbl[10];
    int len;
    get_token(lbl, &tbuf);
    len = strlen(lbl);
    memcpy(str + strlen(str), lbl, len);
    D("%s\n", str);
    mybf.cur = 0;
    strcpy(mybf.str, str);
    set_inst(&ins, g_ln, &mybf, 0);
    push_inst(&ins);
    g_ln += 4;
  } else {
    inst ins;
    set_inst(&ins, g_ln, buf, 0);
    push_inst(&ins);
    g_ln += 4;
  }
}

int
on_string(inst *ins, int fd)
{
  char str[30];
  int len;
  get_line(str, &ins->buf);
  len = strlen(str);
  str[len-1]='\0';
  write(fd, str+1, len-1);
  return len - 1;
}

void
emit_insts(int fd)
{
  int i;
  int len = vec_lengh(g_lines);
  int pc = START_ADDR;
  int fs = g_ln - pc;
  D("sz = %d\n", fs);
  write(fd, &fs, sizeof(unsigned));

  for(i = 0; i < len; ++i) {
    inst *ins = vec_get(g_lines, i);
    if (pc < ins->pc) {
      int j, n = ins->pc - pc;
      char z = 0;
      for(j = 0; j < n; ++j) {
        write(fd, &z, sizeof(char));
      }
      pc += n;
      D("align: %d\n", n);
    }
    if (ins->pseudo == 1) { // .string
      D("0x%06x string\n", pc);
      pc += on_string(ins, fd);
    } else {
      unsigned b = code(ins);
      D("0x%06x [%08x]\n", pc, b);
      write(fd, &b, sizeof(unsigned));
      pc += 4;
    }
  }

}

void
br_main()
{
  buffer buf;

  buf.cur = 0;
  strcpy(buf.str, "ldl r29, main");
  read_buffer(&buf);

  buf.cur = 0;
  strcpy(buf.str, "jr r29, r29");
  read_buffer(&buf);
}

int
read_line(char *buf, int max_sz, int fd) {
  int err;
  int idx = 0;
  while(idx < max_sz && (err = read(fd, buf + idx, 1)) > 0) {
    if (buf[idx] == '\n')
      break;
    ++idx;
  }
  buf[idx] = 0;
  D("[%s]\n", buf);
  return err;
}

int
main(int argc, char *argv[])
{
  int fd;
  buffer buf;

  if (argc != 2) {
    ERR("Usage: ./as [filename]\n");
    return 0;
  }

  if ((fd = open(argv[1], O_RDONLY)) < 0) {
    ERR("file open error!\n");
    exit(1);
  }

  init_globals();

  br_main();

  while(read_line(buf.str, 256, fd) != 0) {
    buf.cur = 0;
    rm_comment(buf.str);
    rstrip(buf.str);
    read_buffer(&buf);
  }

  close(fd);

  fd = open("a.out", O_CREATE | O_RDWR);
  emit_insts(fd);
  close(fd);
  exit(0);
}


<|start_filename|>include/stdbool.h<|end_filename|>
#ifndef _UCC_STDBOOL_H
#define _UCC_STDBOOL_H

#define bool int
#define true 1
#define false 0
#define __bool_true_false_are_defined 1

#endif  /* stdbool.h */


<|start_filename|>devicefile.c<|end_filename|>
// Console input and output.
// Input is from the keyboard or serial port.
// Output is written to the screen and serial port.

#include <sys/types.h>
#include <sys/file.h>
#include <sys/ioctl.h>
#include <xv6/param.h>
#include <xv6/fs.h>
#include <termios.h>
#include "defs.h"
#include "traps.h"
#include "spinlock.h"
#include "memlayout.h"
#include "mmu.h"
#include "proc.h"
#include "gaia.h"

extern char _binary__min_rt_start[];
extern char _binary__min_rt_size[];

int
minrtread(struct inode *ip, char *dst, int n)
{

  static unsigned offset = 0;
  unsigned sz = *(int*)(_binary__min_rt_start);
  int i;

  for(i=0; i<n; ++i) {
    dst[i] = _binary__min_rt_start[offset];
    offset = (offset + 1) % ((unsigned)_binary__min_rt_size);
  }

  return n;
}


void
minrtinit(void)
{

  devsw[MINRT].write = 0;
  devsw[MINRT].read  = minrtread;
  devsw[MINRT].ioctl = 0;

}

void
deviceinit(void)
{
  minrtinit();
}


<|start_filename|>include/sys/types.h<|end_filename|>
typedef unsigned int uint;
typedef unsigned short ushort;
typedef unsigned char uchar;
typedef uint pde_t;
typedef uint pte_t;


<|start_filename|>include/xv6/procdump.h<|end_filename|>
#ifndef _XV6_PROCDUMP_H
#define _XV6_PROCDUMP_H

int procdump(void);

#endif


<|start_filename|>usr/2048.c<|end_filename|>
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <termios.h>

struct termios termios, original_termios;

#define UP    0
#define DOWN  1
#define RIGHT 2
#define LEFT  3
int dx[4] = {  0, 0, 1, -1};
int dy[4] = { -1, 1, 0,  0};

int board[4][4];
int score;

int myrand(int n) {
  static int lcg = 0;
  int x;
  lcg = 1664525 * lcg + 1013904223;
  x = lcg % n;
  return x < 0 ? x + n : x;
}

void print_int(int d)
{
  printf("%4d", d);
}

void changeColor(int b){
  if(b==0){
    printf("\033[0m");
  } else {
    switch((b-1)%6){
    case 0:
      printf("\033[1;43m");
      break;
    case 1:
      printf("\033[1;42m");
      break;
    case 2:
      printf("\033[1;46m");
      break;
    case 3:
      printf("\033[1;44m");
      break;
    case 4:
      printf("\033[1;45m");
      break;
    case 5:
      printf("\033[1;41m");
      break;
    }
  }
}

void resetColor(){
  changeColor(0);
}

void showBoard(){
  int i,j,b;
  printf("\033[H");
  // draw
  for(i=0; i<4; i++){
    printf("+------+------+------+------+\n");
    for(j=0; j<4; j++){
      printf("|");
      changeColor(board[i][j]);
      printf("      ");
      resetColor();
    } printf("|\n");
    for(j=0; j<4; j++){
      printf("|");
      b = board[i][j];
      changeColor(b);
      if(b != 0)
        printf(" %4d ", 1 << b);
      else
        printf("      ");
      resetColor();
    } printf("|\n");
    for(j=0; j<4; j++){
      printf("|");
      changeColor(board[i][j]);
      printf("      ");
      resetColor();
    } printf("|\n");
  }

  printf("+------+------+------+------+\n");
}


bool isValid(int x, int y){
  if(x < 0 || 4 <= x)
    return false;
  if(y < 0 || 4 <= y)
    return false;
  return true;
}

bool movable(int dir){
  int i,j;
  int ay,ax;
  for(i=0; i<4; i++){
    for(j=0; j<4; j++){
      ay = i+dy[dir]; ax = j+dx[dir];
      if(isValid(ax, ay) && board[i][j]!=0){
        if(board[ay][ax]==0 || board[ay][ax]==board[i][j]){
          return true;
        }
      }
    }
  }
  return false;
}

bool gameover(){
  int i,j;
  for(i=0; i<4; i++){
    for(j=0; j<4; j++){
      if(board[i][j] == 11)
        return true;
    }
  }
  for(i=0; i<4; i++){
    if(movable(i))
      return false;
  }
  return true;
}

void putNum(){
  int n, b;
  if(myrand(10)==0)
    n=2;
  else
    n=1;

  do{
    b = myrand(16);
  } while(board[b%4][b/4] != 0);
  board[b%4][b/4] = n;
}

void init_term(){
  tcgetattr(0, &termios);
  original_termios = termios;
  cfmakeraw(&termios);
  tcsetattr(0, TCSANOW, &termios);
  printf("\033[?25l");
  fflush(stdout);
}

void restore_term(){
  tcsetattr(0, TCSANOW, &original_termios);
  printf("\033[?25h");
  fflush(stdout);
}

void init(){
  int i,j,b;
  init_term();
  for(i=0; i<4; i++)
    for(j=0; j<4; j++)
      board[i][j] = 0;

  score = 0;

  b = myrand(16);
  board[b%4][b/4] = 1;

  putNum();

  printf("\033[2J");
}

void end(){
  restore_term();
  exit(0);
}

int c2dir(char c){
  switch(c){
  case 'w': case 'k': case 'A':
    return 0;
  case 's': case 'j': case 'B':
    return 1;
  case 'd': case 'l': case 'C':
    return 2;
  case 'a': case 'h': case 'D':
    return 3;
  default:
    return -1;
  }
}

void push(int d){
  bool f;
  int i,j,ay,ax;
  do{
    f=false;
    for(i=0; i<4; i++){
      for(j=0; j<4; j++){
        ay=i+dy[d]; ax=j+dx[d];
        if(isValid(ax,ay) && board[ay][ax]==0 && board[i][j]!=0){
          board[ay][ax] = board[i][j];
          board[i][j] = 0;
          f=true;
        }
      }
    }
  } while(f);
}

void merge(int d){
  int i,j;
  switch(d){
  case UP:
    for(j=0;j<4;j++){
      for(i=0;i<3;){
        if(board[i][j]==board[i+1][j] && board[i][j]!=0){
          board[i][j]++;
          score += 1 << board[i][j];
          board[i+1][j]=0;
          i+=2;
        } else {
          i++;
        }
      }
    }
    break;
  case DOWN:
    for(j=0;j<4;j++){
      for(i=3;i>0;){
        if(board[i][j]==board[i-1][j] && board[i][j]!=0){
          board[i][j]++;
          score += 1 << board[i][j];
          board[i-1][j]=0;
          i-=2;
        } else {
          i--;
        }
      }
    }
    break;
  case RIGHT:
    for(i=0;i<4;i++){
      for(j=3;j>0;){
        if(board[i][j]==board[i][j-1] && board[i][j]!=0){
          board[i][j]++;
          score += 1 << board[i][j];
          board[i][j-1]=0;
          j-=2;
        } else {
          j--;
        }
      }
    }
    break;
  case LEFT:
    for(i=0;i<4;i++){
      for(j=0;j<3;){
        if(board[i][j]==board[i][j+1] && board[i][j]!=0){
          board[i][j]++;
          score += 1 << board[i][j];
          board[i][j+1]=0;
          j+=2;
        } else {
          j++;
        }
      }
    }
    break;
  }
}

void Move(int d){
  push(d);
  merge(d);
  push(d);
}

int main(){
  int d;
  init_term();
  init();

  do{
    showBoard();
    printf("score: %d\n", score);
    printf("(enter \'q\' to exit...)\n");
    do{
      char c;
      read(0, &c, 1);
      if (c == 'q')
        end();
      d = c2dir(c);
    } while(d==-1 || !movable(d));
    Move(d);
    putNum();
  } while(!gameover());

  showBoard();
  printf("gameover...\n");
  printf("your score is: %d\n\n", score);

  end();
}


<|start_filename|>include/setjmp.h<|end_filename|>
#ifndef _UCC_SETJMP_H
#define _UCC_SETJMP_H

typedef int jmp_buf[4];
int setjmp(jmp_buf);
void longjmp(jmp_buf, int);

#endif  /* setjmp.h */


<|start_filename|>include/assert.h<|end_filename|>
#ifndef _UCC_ASSERT_H
#define _UCC_ASSERT_H

#ifdef NDEBUG

#define assert(expr) ((void) 0)

#else

void __assert_fail(const char *, const char *, int);
#define assert(expr) \
  ((expr) ? (void) 0 : __assert_fail(#expr, __FILE__, __LINE__))

#endif

#endif  /* assert.h */


<|start_filename|>lib/libc.c<|end_filename|>
#include <assert.h>
#include <ctype.h>
#include <limits.h>
#include <setjmp.h>
#include <stdarg.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <fcntl.h>
#include <unistd.h>
#include <termios.h>
#include <sys/ioctl.h>

#define max(m, n)   ((m) > (n) ? (m) : (n))
#define min(m, n)   ((m) < (n) ? (m) : (n))



/* assert.h */

void __assert_fail(const char *expr, const char *file, int line)
{
  printf("%s:%d: Assertion `%s' failed.\n", file, line, expr);
  abort();
}



/* ctype.h */

int isalnum(int c) { return isalpha(c) || isdigit(c); }
int isalpha(int c) { return islower(c) || isupper(c); }
int isdigit(int c) { return '0' <= c && c <= '9'; }
int islower(int c) { return 'a' <= c && c <= 'z'; }
int isspace(int c) { return c == ' ' || ('\t' <= c && c <= '\r'); }
int isupper(int c) { return 'A' <= c && c <= 'Z'; }
int tolower(int c) { return isupper(c) ? c - 'A' + 'a' : c; }
int toupper(int c) { return islower(c) ? c - 'a' + 'A' : c; }



/* setjmp.h */

int setjmp(jmp_buf buf)
{
  __asm("\
  mov r1, [rbp + 4]     # r1 <- buf                    \n\
  mov r2, [rbp]         # r2 <- caller rbp             \n\
  mov [r1], r2          # save caller rbp              \n\
  mov [r1 + 4], r28     # save r28 (return address)    \n\
  mov [r1 + 8], rbp     # save current rbp             \n\
  jl  r2, 0             # get PC                       \n\
  add r2, r2, 12        # r2 <- address of 'ret'       \n\
  mov [r1 + 12], r2     # save r2                      \n\
  mov r1, 0             # return 0                     \n\
  ret                                                  \n\
");
}

void longjmp(jmp_buf buf, int val)
{
  __asm("\
  mov r1, [rbp + 8]     # r1 <- val                   \n\
  cmpeq r2, r1, 0       # if (val == 0)               \n\
  add r1, r1, r2        #   r1 <- 1                   \n\
  mov r2, [rbp + 4]     # r2 <- buf                   \n\
  mov r3, [r2]          # r3 <- caller rbp            \n\
  mov r28, [r2 + 4]     # restore r28                 \n\
  mov rbp, [r2 + 8]     # restore setjmp rbp          \n\
  mov [rbp], r3         # restore setjmp's caller rbp \n\
  mov r2, [r2 + 12]     # r2 <- address of 'ret'      \n\
  jr  r2                # jump                        \n\
");
}



/* stdio.h */


FILE _iob[OPEN_MAX] = {     /* stdin, stdout, stderr */
  { 0, (char *) 0, (char *) 0, _READ, 0 },
  { 0, (char *) 0, (char *) 0, _WRITE | _LNBUF, 1 },
  { 0, (char *) 0, (char *) 0, _WRITE | _UNBUF, 2 }
};


FILE *fopen(const char *name, const char *mode)
{
  int fd;
  FILE *fp;

  if (*mode != 'r' && *mode != 'w' && *mode != 'a')
    return NULL;


  for (fp = _iob; fp < _iob + OPEN_MAX; fp++)
    if ( (fp->flag & (_READ | _WRITE)) == 0)
      break;  /* found free slot */

  if (fp >= _iob + OPEN_MAX)  /* no free slots */
    return NULL;

  if (*mode == 'w')
    fd = open(name, O_CREATE | O_WRONLY);
  else if (*mode == 'a') {
    if ((fd = open(name, O_WRONLY)) == -1)
      fd = open(name, O_WRONLY);
  } else
    fd = open(name, O_RDONLY);

  if (fd == -1)   /* couldn't access name */
    return NULL;

  fp->fd = fd;
  fp->cnt = 0;
  fp->base = NULL;
  fp->flag = (*mode == 'r')? _READ : _WRITE;
  return fp;

}

int fclose(FILE *fp) {

  fflush(fp);
  fp->flag = 0;
  free(fp->base);
  return close(fp->fd);
}


int _fillbuf(FILE *fp) {
  int bufsize;

  if ((fp->flag & (_READ | _EOF | _ERR)) != _READ)
    return EOF;

  bufsize = (fp->flag & _UNBUF) ? 1: BUFSIZ;

  if  (fp->base == NULL)  /* no buffer yet */
    if ((fp->base = (char *) malloc(bufsize)) == NULL)
      return EOF;         /* can't get buffer */

  fp->ptr = fp->base;
  fp->cnt = read(fp->fd, fp->ptr, bufsize);

  if (--fp->cnt < 0) {
    if (fp->cnt == -1)
      fp->flag |= _EOF;
    else
      fp->flag |= _ERR;
    fp->cnt = 0;
    return EOF;
  }

  return (unsigned char) *fp->ptr++;
}

int _flushbuf(int x, FILE *fp) {

  int num_written=0, bufsize=0;
  unsigned char uc = x;

  if ((fp->flag & (_WRITE|_EOF|_ERR)) != _WRITE)
    return EOF;
  if (fp->base == NULL && ((fp->flag & _UNBUF) == 0)) {
    /* no buffer yet */
    if ((fp->base = malloc(BUFSIZ)) == NULL) {
      /* couldn't allocate a buffer, so try unbuffered */
      fp->flag |= _UNBUF;
    } else {
      fp->ptr = fp->base;
      fp->cnt = BUFSIZ - 1;
    }
  }
  if (fp->flag & _UNBUF) {
    /* unbuffered write */
    fp->ptr = fp->base = NULL;
    fp->cnt = 0;
    if (x == EOF)
      return EOF;
    num_written = write(fp->fd, &uc, 1);
    bufsize = 1;
  } else {
    /* buffered write */
    assert(fp->ptr);
    if (x != EOF) {
      *fp->ptr++ = uc;
    }
    bufsize = (int)(fp->ptr - fp->base);
    while(bufsize - num_written > 0) {
      int t;
      t = write(fp->fd, fp->base + num_written, bufsize - num_written);
      num_written += t;
    }

    fp->ptr = fp->base;
    fp->cnt = BUFSIZ - 1;
  }

  if (num_written == bufsize) {
    return x;
  } else {
    fp->flag |= _ERR;
    return EOF;
  }
}

/* fflush */
int fflush(FILE *f)
{
  int retval;
  int i;

  retval = 0;
  if (f == NULL) {
    /* flush all output streams */
    for (i = 0; i < OPEN_MAX; i++) {
      if ((_iob[i].flag & _WRITE) && (fflush(&_iob[i]) == -1))
        retval = -1;
    }
  } else {
    if ((f->flag & _WRITE) == 0)
      return -1;
    _flushbuf(EOF, f);
    if (f->flag & _ERR)
      retval = -1;
  }
  return retval;
}


int fputc(int x, FILE *fp)
{
  int flush = (fp->flag & _LNBUF) && x == '\n';

  if (--fp->cnt >= 0 && !flush) {
    return *(fp)->ptr++ = x;
  } else {
    return _flushbuf(x, fp);
  }
}


int fgetc(FILE *fp)
{
  if (--fp->cnt >= 0) {
    return (unsigned char) *(fp)->ptr++;
  } else {
    return _fillbuf(fp);
  }

}

int fputs(char *s, FILE *stream)
{

  while(*s != '\0') {

    if (fputc(*s, stream) == EOF)
      return EOF;

    ++s;

  }

  return 1;

}


int puts(char *s)
{
  int i = 0;

  while(*s != '\0') {

    if (putchar(*s) == EOF)
      return EOF;

    ++i; ++s;

  }

  putchar('\n');

  return i + 1;
}



char *fgets(char *s, int size, FILE *stream)
{
  int c;
  char *buf;
  fflush(NULL);
  buf = s;

  if (size == 0)
    return NULL;

  while (--size > 0 && (c = fgetc(stream)) != EOF) {

    if ((*buf++ = c) == '\n')
      break;

  }

  *buf = '\0';

  return (c == EOF && buf == s) ? NULL : s;

}

char *gets(char *s)
{
  int c;
  char *buf;
  fflush(NULL);
  buf = s;

  while ((c = getc(stdin)) != EOF && c != '\n') {

    *buf++ = c;

  }

  *buf = '\0';

  return (c == EOF && buf == s) ? NULL : s;

}





#define LEFT      (1 << 0)
#define ZEROPAD   (1 << 1)
#define SIGN      (1 << 2)
#define PLUS      (1 << 3)
#define SPACE     (1 << 4)
#define OCTPRE    (1 << 5)
#define HEXPRE    (1 << 6)
#define CAP       (1 << 7)
#define DOT       (1 << 8)
#define TRUNC     (1 << 9)

static int prints(FILE *fp, const char *str, int w, int prec, int flag)
{
  int i, len;

  if (! str)
    str = "(null)";

  len = strlen(str);;
  if (prec >= 0 && len > prec)
    len = prec;

  if (! (flag & LEFT))
    for (i = 0; i < w - len; ++i)
      putc(' ', fp);

  for (i = 0; i < len; ++i)
    putc(str[i], fp);

  if (flag & LEFT)
    for (i = 0; i < w - len; ++i)
      putc(' ', fp);

  return max(len, w);
}

static int printi(FILE *fp, int x, int base, int w, int prec, int flag)
{
  char buf[12], pbuf[2];
  int i, n, len = 0, plen = 0;
  unsigned u = x;

  if (prec >= 0)
    flag &= ~ZEROPAD;

  if (flag & SIGN) {
    if (x < 0) {
      u = -x;
      pbuf[plen++] = '-';
    } else if (flag & (PLUS | SPACE)) {
      pbuf[plen++] = flag & PLUS ? '+' : ' ';
    }
  }
  if (x && flag & HEXPRE) {
    pbuf[plen++] = '0';
    pbuf[plen++] = flag & CAP ? 'X' : 'x';
  }

  while (u > 0) {
    int t = u % base;
    buf[len++] = (t < 10) ? (t + '0') : (t - 10 + (flag & CAP ? 'A' : 'a'));
    u /= base;
  }
  if (x == 0 || flag & OCTPRE)
    buf[len++] = '0';

  n = max(len, prec) + plen;

  if (! (flag & (LEFT | ZEROPAD)))
    for (i = 0; i < w - n; ++i)
      putc(' ', fp);

  for (i = 0; i < plen; ++i)
    putc(pbuf[i], fp);

  if (flag & ZEROPAD)
    for (i = 0; i < w - n; ++i)
      putc('0', fp);

  for (i = 0; i < prec - len; ++i)
    putc('0', fp);

  for (i = len - 1; i >= 0; --i)
    putc(buf[i], fp);

  if (flag & LEFT)
    for (i = 0; i < w - n; ++i)
      putc(' ', fp);

  return max(w, n);
}

/*
static float normalize(float f, int *e)
{
  static float table_p[] = { 1e1, 1e2, 1e4, 1e8, 1e16, 1e32 };
  static float table_m[] = { 1e-1, 1e-2, 1e-4, 1e-8, 1e-16, 1e-32 };
  static float table_m1[] = { 1e0, 1e-1, 1e-3, 1e-7, 1e-15, 1e-31 };

  int i;

  *e = 0;
  for (i = 5; i >= 0; --i) {
    if (f >= table_p[i]) {
      *e += 1 << i;
      f *= table_m[i];
    }
    if (f < table_m1[i]) {
      *e -= 1 << i;
      f *= table_p[i];
    }
  }

  return f;
}

static int printef(FILE *fp, float f, int w, int prec, int flag)
{
  char buf[10], pbuf[1];
  int i, n, expo = 0, len = 0, plen = 0, sp = 0;
  union { float f; unsigned i; } u;

  u.f = f;

  if (prec < 0)
    prec = 6;

  if (u.i >> 31) {
    f = -f;
    pbuf[plen++] = '-';
  } else if (flag & (PLUS | SPACE)) {
    pbuf[plen++] = flag & PLUS ? '+' : ' ';
  }

  if ((u.i >> 23 & 255) == 255) {
    int ofs = flag & CAP ? 'A' - 'a' : 0;
    sp = 1;
    flag &= ~ZEROPAD;
    if ((u.i & 0x7fffff) == 0) {
      buf[len++] = 'i' + ofs;
      buf[len++] = 'n' + ofs;
      buf[len++] = 'f' + ofs;
    } else {
      buf[len++] = 'n' + ofs;
      buf[len++] = 'a' + ofs;
      buf[len++] = 'n' + ofs;
    }
  } else if (f == 0.0) {
    buf[len++] = '0';
    buf[len++] = '.';
    // prec >= 9 is treated as prec = 8
    for (i = 0; i < min(prec, 8); ++i)
      buf[len++] = '0';
  } else {
    int x = 0;
    f = normalize(f, &expo);

    len = min(prec, 8) + 2;
    for (i = 0; i < len - 1; ++i) {
      int d = f;
      x = x * 10 + d;
      f = (f - d) * 10.0;
    }
    if (f >= 5.0) ++x;

    buf[1] = '.';
    for (i = len - 1; i >= 2; --i) {
      buf[i] = x % 10 + '0';
      x /= 10;
    }
    if (x == 10) {
      ++expo;
      buf[0] = '1';
    } else {
      buf[0] = x + '0';
    }
  }

  if (flag & TRUNC)
    while (buf[len - 1] == '0')
      --len;
  if (buf[len - 1] == '.' && ~flag & DOT)
    --len;

  n = len + plen + (sp || flag & TRUNC ? 0 : max(prec - 8, 0)) + (sp ? 0 : 4);

  if (! (flag & (LEFT | ZEROPAD)))
    for (i = 0; i < w - n; ++i)
      putc(' ', fp);

  for (i = 0; i < plen; ++i)
    putc(pbuf[i], fp);

  if (flag & ZEROPAD)
    for (i = 0; i < w - n; ++i)
      putc('0', fp);

  for (i = 0; i < len; ++i)
    putc(buf[i], fp);

  if (! (sp || flag & TRUNC))
    for (i = 0; i < prec - 8; ++i)
      putc('0', fp);

  if (! sp) {
    putc(flag & CAP ? 'E' : 'e', fp);
    putc(expo < 0 ? '-' : '+', fp);
    if (expo < 0) expo = -expo;
    putc(expo / 10 + '0', fp);
    putc(expo % 10 + '0', fp);
  }

  if (flag & LEFT)
    for (i = 0; i < w - n; ++i)
      putc(' ', fp);

  return max(w, n);
}

static int printff(FILE *fp, float f, int w, int prec, int flag)
{
  static float round_table[] = {
    5e-1, 5e-2, 5e-3, 5e-4, 5e-5, 5e-6, 5e-7, 5e-8, 5e-9, 5e-10
  };

  char buf[49], pbuf[1];
  int i, n, len = 0, plen = 0, sp = 0;
  union { float f; unsigned i; } u;
  __asm("break 2\n");

  u.f = f;

  if (prec < 0)
    prec = 6;

  if (u.i >> 31) {
    f = -f;
    pbuf[plen++] = '-';
  } else if (flag & (PLUS | SPACE)) {
    pbuf[plen++] = flag & PLUS ? '+' : ' ';
  }
  __asm("break 3\n");

  if ((u.i >> 23 & 255) == 255) {
    int ofs = flag & CAP ? 'A' - 'a' : 0;
    sp = 1;
    flag &= ~ZEROPAD;
    if ((u.i & 0x7fffff) == 0) {
      buf[len++] = 'i' + ofs;
      buf[len++] = 'n' + ofs;
      buf[len++] = 'f' + ofs;
    } else {
      buf[len++] = 'n' + ofs;
      buf[len++] = 'a' + ofs;
      buf[len++] = 'n' + ofs;
    }
  } else {
    int expo;
    float g;

    // prec >= 10 is treated as prec = 9
    f += round_table[min(prec, 9)];

    g = normalize(f, &expo);
    if (expo < 0)
      expo = 0;
    else
      f = g;

    for (; expo >= 0; --expo) {
      int d = f;
      buf[len++] = d + '0';
      f = (f - d) * 10.0;
    }

    buf[len++] = '.';
    for (i = 0; i < min(prec, 9); ++i) {
      int d = f;
      buf[len++] = d + '0';
      f = (f - d) * 10.0;
    }
  }

  if (flag & TRUNC)
    while (buf[len - 1] == '0')
      --len;
  if (buf[len - 1] == '.' && ~flag & DOT)
    --len;

  n = len + plen + (sp || flag & TRUNC ? 0 : max(prec - 9, 0));

  if (! (flag & (LEFT | ZEROPAD)))
    for (i = 0; i < w - n; ++i)
      putc(' ', fp);

  for (i = 0; i < plen; ++i)
    putc(pbuf[i], fp);

  if (flag & ZEROPAD)
    for (i = 0; i < w - n; ++i)
      putc('0', fp);

  for (i = 0; i < len; ++i)
    putc(buf[i], fp);

  if (! (sp || flag & TRUNC))
    for (i = 0; i < prec - 9; ++i)
      putc('0', fp);

  if (flag & LEFT)
    for (i = 0; i < w - n; ++i)
      putc(' ', fp);

  return max(w, n);
}

static int printgf(FILE *fp, float f, int w, int prec, int flag)
{
  int expo;

  if (prec < 0)
    prec = 6;
  if (prec == 0)
    prec = 1;

  normalize(f, &expo);

  if (-4 <= expo && expo < prec) {
    return printff(fp, f, w, prec - expo - 1, flag);
  } else {
    return printef(fp, f, w, prec - 1, flag);
  }
}
*/

static char *write_string_dst;
static int write_string(int c)
{
  *write_string_dst = c;
  ++write_string_dst;
  return c;
}

int printf(const char *fmt, ...)
{
  va_list ap;
  va_start(ap, fmt);
  return vfprintf(stdout, fmt, ap);
}

int fprintf(FILE *fp, const char *fmt, ...)
{
  va_list ap;
  va_start(ap, fmt);
  return vfprintf(fp, fmt, ap);
}


int vprintf(const char *fmt, va_list ap)
{
  return vfprintf(stdout, fmt, ap);
}

int vfprintf(FILE *fp, const char *fmt, va_list ap)
{
  int ret = 0;

  if (! (fp->flag & _WRITE))
    return -1;

  for (; *fmt; ++fmt) {
    if (*fmt == '%') {
      int flag = 0;
      int alt = 0;
      int w = 0;
      int prec = -1;
      const char *bak = fmt++;
      if (*fmt == '%') {
        ++ret;
        putc('%', fp);
        continue;
      }
      while (strchr("-+ #0", *fmt)) {
        switch (*(fmt++)) {
          case '-': flag |= LEFT; break;
          case '+': flag |= PLUS; break;
          case ' ': flag |= SPACE; break;
          case '#': alt = -1; break;
          case '0': flag |= ZEROPAD; break;
        }
      }
      if (flag & LEFT)
        flag &= ~ZEROPAD;
      if (flag & PLUS)
        flag &= ~SPACE;
      if (*fmt == '*') {
        ++fmt;
        w = va_arg(ap, int);
      } else while (isdigit(*fmt)) {
        w = w * 10 + *(fmt++) - '0';
      }
      if (*fmt == '.') {
        ++fmt;
        prec = 0;
        if (*fmt == '*') {
          ++fmt;
          prec = va_arg(ap, int);
        } else while (isdigit(*fmt)) {
          prec = prec * 10 + *(fmt++) - '0';
        }
      }
      while (strchr("hlL", *fmt))
        ++fmt;
      switch (*fmt) {
        case 'c':
          ++ret;
          putc(va_arg(ap, int), fp);
          break;
        case 's':
          ret += prints(fp, va_arg(ap, char*), w, prec, flag);
          break;
        case 'd':
        case 'i':
          ret += printi(fp, va_arg(ap, int), 10, w, prec, flag | SIGN);
          break;
        case 'o':
          ret += printi(fp, va_arg(ap, int),  8, w, prec, flag | (alt & OCTPRE));
          break;
        case 'x':
          ret += printi(fp, va_arg(ap, int), 16, w, prec, flag | (alt & HEXPRE));
          break;
        case 'X':
          ret += printi(fp, va_arg(ap, int), 16, w, prec, flag | (alt & HEXPRE) | CAP);
          break;
        case 'u':
          ret += printi(fp, va_arg(ap, int), 10, w, prec, flag);
          break;
        case 'p':
          ret += printi(fp, va_arg(ap, int), 16, w, prec, flag | HEXPRE);
          break;
        // case 'e':
        //   ret += printef(fp, va_arg(ap, double), w, prec, flag | (alt & DOT));
        //   break;
        // case 'E':
        //   ret += printef(fp, va_arg(ap, double), w, prec, flag | (alt & DOT) | CAP);
        //   break;
        // case 'f':
        //   ret += printff(fp, va_arg(ap, double), w, prec, flag | (alt & DOT));
        //   break;
        // case 'F':
        //   ret += printff(fp, va_arg(ap, double), w, prec, flag | (alt & DOT) | CAP);
        //   break;
        // case 'g':
        //   ret += printgf(fp, va_arg(ap, double), w, prec, flag | (~alt & TRUNC));
        //   break;
        // case 'G':
        //   ret += printgf(fp, va_arg(ap, double), w, prec, flag | (~alt & TRUNC) | CAP);
        //   break;
        case 'n':
          *va_arg(ap, int*) = ret;
          break;
        default:
          ret += fmt - bak;
          for (; bak < fmt; ++bak){
            putc(*bak, fp);
          }
          --fmt;
          break;
      }
    } else {
      ++ret;
      putc(*fmt, fp);
    }
  }

  return ret;
}



/* stdlib.h */

void exit(int status)
{
  fflush(NULL);
  _exit();
}


void abort(void)
{
  fprintf(stderr, "abort!\n");
  exit(1);
}

int abs(int n)
{
  __asm("\
  mov r1, [rbp + 4] \n\
  sar r2, r1, 31    \n\
  xor r1, r1, r2    \n\
  sub r1, r1, r2    \n\
  ret               \n\
");
}


long strtol(const char *str, char **end, int base)
{
  long l = 0;

  if (base > 36) {
    if (end)
      *end = (char *)str;
    return 0;
  }

  if (base == 0) {
    if (*str == '0') {
      ++str;
      if (*str == 'x' || *str == 'X') {
        ++str;
        base = 16;
      } else {
        base = 8;
      }
    } else {
      base = 10;
    }
  }

  while (1) {
    char c = *str;
    long n = base;

    if (isdigit(c)) n = c - '0';
    if (islower(c)) n = c - 'a' + 10;
    if (isupper(c)) n = c - 'A' + 10;

    if (base <= n)
      break;

    ++str;
    l = l * base + n;
  }

  if (end)
    *end = (char *)str;
  return l;
}


static unsigned rbuf[32], ridx = -1;

int rand(void)
{
  if (ridx >= 32) srand(1);
  if (ridx == 31) {
    ridx = 0;
    return (rbuf[31] = rbuf[0] + rbuf[28]) >> 1;
  } else {
    int tmp = rbuf[ridx + 1] + rbuf[ridx + (ridx < 3 ? 29 : -3)];
    return (rbuf[ridx++] = tmp) >> 1;
  }
}

void srand(unsigned seed)
{
  int i;
  unsigned tmp, lo, hi;
  const unsigned mod = 0x7fffffff;
  ridx = 2;
  rbuf[0] = seed ? seed : 1;
  for (i = 1; i < 31; ++i) {
    /* rbuf[i] = (16807ll * (int)rbuf[i - 1] % mod + mod) % mod; */
    tmp = rbuf[i - 1];
    if ((int)tmp < 0) tmp = -tmp;
    lo = 16807 * (tmp & 0xffff);
    hi = 16807 * (tmp >> 16);
    tmp = (lo + ((hi & 0x7fff) << 16) + (hi >> 15));
    if (tmp >= mod) tmp -= mod;
    rbuf[i] = (int)rbuf[i - 1] < 0 && tmp ? mod - tmp : tmp;
  }
  rbuf[31] = rbuf[0]; rbuf[0] = rbuf[1]; rbuf[1] = rbuf[2];
  for (i = 34; i < 344; ++i) rand();
}


#define NALLOC 1024

struct header {
  struct header *next;
  size_t size;
};

typedef struct header Header;

static Header base;
static Header *freep;

void free(void *ap)
{
  Header *bp, *p;

  if (! ap)
    return;

  bp = (Header *)ap - 1;
  for (p = freep; !(p < bp && bp < p->next); p = p->next)
    if (p->next <= p && (p < bp || bp < p->next))
      break;

  if (bp + bp->size == p->next) {
    bp->size += p->next->size;
    bp->next = p->next->next;
  } else {
    bp->next = p->next;
  }

  if (p + p->size == bp) {
    p->size += bp->size;
    p->next = bp->next;
  } else {
    p->next = bp;
  }

  freep = p;
}

static Header *morecore(size_t nunits)
{
  Header *p;

  nunits = (nunits + NALLOC - 1) / NALLOC * NALLOC;
  p = (Header *)sbrk(nunits * sizeof(Header));
  if (p == (Header *)-1)
    return NULL;
  p->size = nunits;
  free(p + 1);
  return freep;
}

void *malloc(size_t nbytes)
{
  Header *p, *prevp;
  size_t nunits;

  nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;
  if (! (prevp = freep)) {  /* no free list yet */
    base.next = freep = prevp = &base;
    base.size = 0;
  }

  for (p = prevp->next; ; prevp = p, p = p->next) {
    if (p->size >= nunits) {  /* big enough */
      if (p->size == nunits) {  /* exactly */
        prevp->next = p->next;
      } else {  /* allocate tail end */
        p->size -= nunits;
        p += p->size;
        p->size = nunits;
      }
      freep = prevp;
      return (void *)(p + 1);
    }
    if (p == freep)
      if (! (p = morecore(nunits)))
        return NULL;
  }

}

static size_t malloc_size(void *ap)
{
  Header *p;

  p = (Header *)ap - 1;
  return (p->size - 1) * sizeof(Header);
}

void *realloc(void *ptr, size_t size)
{
  void *new;

  if (! ptr)
    return malloc(size);

  if (size <= malloc_size(ptr))
    return ptr;

  new = malloc(size);
  if (! new)
    return NULL;

  memcpy(new, ptr, malloc_size(ptr));
  free(ptr);

  return new;
}

void *calloc(size_t n, size_t size)
{
  char *ptr = malloc(n * size);

  if (! ptr)
    return NULL;

  memset(ptr, 0, n * size);
  return (void *) ptr;
}


int
atoi(const char *s)
{
  int n;

  n = 0;
  while('0' <= *s && *s <= '9')
    n = n*10 + *s++ - '0';
  return n;
}


/* string.h */

size_t strlen(const char *str)
{
  size_t len = 0;

  while (*str++) {
    ++len;
  }
  return len;
}

int strcmp(const char *l, const char *r)
{
  while (*l) {
    if (*l++ != *r++) {
      return l[-1] < r[-1] ? -1 : 1;
    }
  }
  return *r ? -1 : 0;
}

int strncmp(const char *l, const char *r, size_t n)
{
  while (*l && 0 < n) {
    if (*l++ != *r++) {
      return l[-1] < r[-1] ? -1 : 1;
    }
    --n;
  }
  return 0;
}

char *strchr(const char *str, int c)
{
  do {
    if (*str == c) {
      return (char *)str;
    }
  } while (*str++);
  return NULL;
}

char *strcpy(char *dst, const char *src)
{
  char *d = dst;

  while (*d++ = *src++);
  return dst;
}

char *strncpy(char *dst, const char *src, size_t n)
{
  char *d = dst;

  while (n-- > 0 && (*d++ = *src++));
  return dst;
}

void *memset(void *dst, int c, size_t n)
{
  char *d = dst;

  while (n-- > 0) {
    *d++ = c;
  }
  return dst;
}

void *memcpy(void *dst, const void *src, size_t n)
{
  const char *s = src;
  char *d = dst;

  while (n-- > 0) {
    *d++ = *s++;
  }
  return dst;
}

void*
memmove(void *dst, const void *src, size_t n)
{
  const char *s;
  char *d;

  s = src;
  d = dst;
  if(s < d && s + n > d){
    s += n;
    d += n;
    while(n-- > 0)
      *--d = *--s;
  } else
    while(n-- > 0)
      *d++ = *s++;

  return dst;
}


/* termios.h */

int tcgetattr(int fd, struct termios *termios_p)
{
  return ioctl(fd, TCGETA, termios_p);
}

int tcsetattr(int fd, int optional_actions, const struct termios *termios_p)
{
  return ioctl(fd, TCSETA, termios_p);
}

void cfmakeraw(struct termios *termios_p)
{
  // Ignore optional_actions
  termios_p->c_lflag = 0;
}


<|start_filename|>include/limits.h<|end_filename|>
#ifndef _UCC_LIMITS_H
#define _UCC_LIMITS_H

#define CHAR_BIT  8
#define SCHAR_MAX 127
#define SCHAR_MIN (-128)
#define UCHAR_MAX 255
#define CHAR_MAX  127
#define CHAR_MIN  (-128)
#define SHRT_MAX  32767
#define SHRT_MIN  (-32768)
#define USHRT_MAX 65535
#define INT_MAX   2147483647
#define INT_MIN   (-2147483648)
#define UINT_MAX  4294967295
#define LONG_MAX  INT_MAX
#define LONG_MIN  INT_MIN
#define ULONG_MAX UINT_MAX

#endif  /* limits.h */


<|start_filename|>usr/sed.c<|end_filename|>
// Simple sed.
// Only supports s and d command.
// Not checked regexp
// (example)
//  * sed 1,5d
//   -> delete line 1 to 5
//  * sed 2s/abc/pqr/g
//   -> substitute pqr for abc in line 2
//  * sed 3iabc
//   -> insert abc before line 3
//  * sed 3apqr
//   -> insert pqr after line 3

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <fcntl.h>
#include <unistd.h>

char buf[1024];
char *extractline(char *option, int *start, int *end);

void sed_delete(int fd, int start, int end);
void sed_substitute(int fd, int start, int end, char *option);
void sed_insert(int fd, int start, int end, char *txt);
void sed_append(int fd, int start, int end, char *txt);

void sed(char *option, int fd){
  int start, end;

  option = extractline(option, &start, &end);

  switch(*option){
  case 'd':
    sed_delete(fd, start, end);
    return;
  case 's':
    option++;
    sed_substitute(fd, start, end, option);
    return;
  case 'a':
    option++;
    sed_append(fd, start, end, option);
    return;
  case 'i':
    option++;
    sed_insert(fd, start, end, option);
    return;
  default:
    printf("sed: wrong command\n");
    return;
  }
}

int main(int argc, char *argv[]){
  int fd, i;
  char *option;

  if(argc <= 1){
    fprintf(stderr, "usage: sed [OPTION] [input]\n");
    fprintf(stderr, "OPTION: [line][command]\n");
    fprintf(stderr, "command: d(delete), s(substitute), a(append), i(insert)\n");
    exit(1);
  }
  option = argv[1];

  if(argc <= 2){
    sed(option, 0);
    exit(0);
  }

  for(i = 2; i < argc; i++){
    if((fd = open(argv[i], 0)) < 0){
      fprintf(stderr, "sed: cannot open %s\n", argv[i]);
      exit(1);
    }
    sed(option, fd);
    close(fd);
  }

  exit(0);
}

// extract line option
char *extractline(char *option, int *start, int *end){
  *start = 0;
  *end   = -1;

  // line optioned
  while(*option >= '0' && *option <= '9'){
    *start += (*start)*10 + ((*option) - '0');
    option++;
  }
  if(*option != ','){
    if(*start == 0){
      *start = 1;
      return option;
    }
    *end = *start;
    return option;
  }
  option++;
  *end = 0;
  while(*option >= '0' && *option <= '9'){
    *end += (*end)*10 + ((*option) - '0');
    option++;
  }
  return option;
}

// line is in range
int isrange(int start, int end, int line){
  return start <= line && (line <= end || end == -1);
}


// delete line
void sed_delete(int fd, int start, int end){
  int n, m, l;
  char *p, *q;

  m = 0;
  l = 0;
  while((n = read(fd, buf+m, sizeof(buf)-m-1)) >0 ){
    buf[m+n]=0;
    m += n;
    p = buf;
    while((q = strchr(p, '\n')) != 0){
      l++;
      *q = 0;

      if(!isrange(start, end, l)){
        *q = '\n';
        write(1, p, q+1-p);
      }
      p = q+1;
    }
    if(p == buf)
      m=0;
    if(m > 0){
      m -= p - buf;
      memmove(buf, p, m);
      memset(buf+m, '\0', sizeof(buf)-m);
    }
  }
}

int parse_regexp_sub(char *re, char *from, char *to, int *g){
  char *p, *q;

  if(*re != '/') return -1;
  re++;

  p = re;
  if((q = strchr(p, '/')) == 0)
    return -1;

  strcpy(from, p);
  from[q-p] = '\0';

  p = q+1;
  if((q = strchr(p, '/')) == 0)
    return -1;

  strcpy(to, p);
  to[q-p] = '\0';

  if(*q != '/')
    return -1;

  if(*(q+1) == 'g')
    *g = 1;
  else
    *g = 0;

  return 0;
}

void outputreplace(char *text, char *s, char *e, char *to){
  int i, j;
  for(i=0; *(to+i) != '\0'; ++i)
    ;
  for(j=0; *(e+j) != '\n'; ++j)
    ;
  write(1, text, s-text);
  write(1, to, i);
  write(1, e, j+1);
}

char *replacebegin(char *re, char *text);
char *replacestar(int c, char *re, char *text);

int replace(char *from, char *to, char *text){
  char *bak,*s,*e;
  bak = text;
  if(from[0] == '^'){
    s = text;
    e = replacebegin(from+1, text);
    outputreplace(bak, s, e, to);
    return 1;
  }
  do{  // must look at empty string
    s = text;
    if((e = replacebegin(from, text)) != 0){
      outputreplace(bak, s, e, to);
      return 1;
    }
  }while(*text++ != '\0');
  return 0;
}

// replacebegin: search for re at beginning of text
char *replacebegin(char *re, char *text){
  if(re[0] == '\0'){
    return text;
  }
  if(re[1] == '*'){
    return replacestar(re[0], re+2, text);
  }
  if(re[0] == '$' && re[1] == '\0'){
    if(*text == '\0')
      return text;
    else
      return 0;
  }
  if(*text!='\0' && (re[0]=='.' || re[0]==*text)){
    return replacebegin(re+1, text+1);
  }
  return 0;
}

// replacestar: search for c*re at beginning of text
char *replacestar(int c, char *re, char *text){
  char *tmp;
  do{  // a * replacees zero or more instances
    if(tmp = replacebegin(re, text))
      return tmp;
  }while(*text!='\0' && (*text++==c || c=='.'));
  return 0;
}

// substitute line
void sed_substitute(int fd, int start, int end, char *re){
  int n, m, l, g;
  char *p, *q;
  char from[128], to[128];

  if(parse_regexp_sub(re, from, to, &g) < 0){
    fprintf(stderr, "sed: unknown regexp\n");
    exit(1);
  }

  m = 0;
  l = 0;
  while((n = read(fd, buf+m, sizeof(buf)-m-1)) >0 ){
    buf[m+n]=0;
    m += n;
    p = buf;
    while((q = strchr(p, '\n')) != 0){
      l++;
      *q = 0;

      if(!isrange(start, end, l)){
        *q = '\n';
        write(1, p, q+1-p);
      }else{
        *q = '\n';
        if(replace(from, to, p)){
          // write in replace
        }else{
          write(1, p, q+1-p);
        }
      }
      p = q+1;
    }
    if(p == buf)
      m=0;
    if(m > 0){
      m -= p - buf;
      memmove(buf, p, m);
      memset(buf+m, '\0', sizeof(buf)-m);
    }
  }
}

// append, insert
void sed_insert_append(int flg, int fd, int start, int end, char *txt);
void sed_insert(int fd, int start, int end, char *txt){
  sed_insert_append(0, fd, start, end, txt);
}
void sed_append(int fd, int start, int end, char *txt){
  sed_insert_append(1, fd, start, end, txt);
}
// flg
//  0 -> insert
//  1 -> append
void sed_insert_append(int flg, int fd, int start, int end, char *txt){
  int i, n, m, l, g;
  char *p, *q;

  for(i=0; *(txt+i) != '\0'; ++i)
    ;
  *(txt+i) = '\n';
  i++;

  m = 0;
  l = 0;
  while((n = read(fd, buf+m, sizeof(buf)-m-1)) >0 ){
    buf[m+n]=0;
    m += n;
    p = buf;
    while((q = strchr(p, '\n')) != 0){
      l++;
      *q = 0;

      if(!isrange(start, end, l)){
        *q = '\n';
        write(1, p, q+1-p);
      }else{
        *q = '\n';
        if(flg == 0)
          write(1, txt, i);
        write(1, p, q+1-p);
        if(flg == 1)
          write(1, txt, i);
      }
      p = q+1;
    }
    if(p == buf)
      m=0;
    if(m > 0){
      m -= p - buf;
      memmove(buf, p, m);
      memset(buf+m, '\0', sizeof(buf)-m);
    }
  }
}


<|start_filename|>usr/vi.c<|end_filename|>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <fcntl.h>
#include <unistd.h>
#include <termios.h>

// screen
//  statusbar is append after SCREEN_HEIGHT screen
//  actual screen height is SCREEN_HEIGHT+1
#define SCREEN_WIDTH  30
#define SCREEN_HEIGHT 20

// line buffer length
#define LINE_BUFFER_LENGTH 128

// mode
#define MODE_NORMAL 1
#define MODE_INSERT 2

// statusbar
#define STATUSBAR_VISIBLE 1
#define STATUSBAR_HIDE    2
#define STATUSBAR_MESSAGE_LENGTH 64
#define STATUSBAR_MESSAGE_START  11

// keycode
#define KEYCODE_ESC  0x1b
#define KEYCODE_LF   0x0A
#define KEYCODE_CR   0x0D
#define KEYCODE_DEL  0x7f
#define KEYCODE_AT   0x40

// esc sequence
#define term_cursor_location(x,y) fprintf(stdout, "\033[%d;%dH" ,y,x)

// globals
int mode;
int command;
int quit_flg;

struct linebuffer{
  char *buf;
  int  size;
  struct linebuffer *prev;
  struct linebuffer *next;
} linebuffer_head, linebuffer_tail;

struct cursor{
  int x;
  int y;
  struct linebuffer *linebuffer;
} cursor;

struct statusbar{
  int  visibility;
  char mode[16];
  char msg[STATUSBAR_MESSAGE_LENGTH];
  int  msglength;
} statusbar;

struct screen{
  int line;
  struct linebuffer *upperline;
}screen;

struct termios termios;

char inputfilename[64];
char outputfilename[64];

// protos
void save();
void load();
void quit();

// screen
void screen_init(){
  screen.upperline = linebuffer_head.next;
  screen.line = 1;
}
void screen_up(){
  if(screen.upperline->prev == &linebuffer_head)
    return;
  screen.upperline = screen.upperline->prev;
  screen.line--;
}
void screen_down(){
  if(screen.upperline->next == &linebuffer_tail)
    return;
  screen.upperline = screen.upperline->next;
  screen.line++;
}
int is_screen_up(){
  return screen.upperline->prev == cursor.linebuffer;
}
int is_screen_down(){
  int i;
  struct linebuffer *lbp;

  lbp = screen.upperline;
  for(i=1; i<SCREEN_HEIGHT; i++){
    lbp = lbp->next;
  }
  return lbp->next == cursor.linebuffer;
}
struct linebuffer *screen_top(){
  int i;
  struct linebuffer *top;

  top = &linebuffer_head;
  for(i=0; i<screen.line; i++){
    top = top->next;
  }
  return top;
}

//cursor
void cursor_init(struct linebuffer *lbp){
  cursor.x          = 0;
  cursor.y          = 1;
  cursor.linebuffer = lbp;
}
void terminal_cursor_update(){
  if(command){
    term_cursor_location(STATUSBAR_MESSAGE_START+statusbar.msglength, SCREEN_HEIGHT+1);
    fflush(stdout);
  }else{
    term_cursor_location(cursor.x+1, cursor.y-screen.line+1);
    fflush(stdout);
  }
}
void cursor_up(){
  if(cursor.linebuffer->prev == &linebuffer_head)
    return;
  cursor.linebuffer = cursor.linebuffer->prev;
  cursor.y--;
  if(cursor.x >= cursor.linebuffer->size)
    cursor.x = cursor.linebuffer->size;

  if(is_screen_up())
    screen_up();
}
void cursor_down(){
  if(cursor.linebuffer->next == &linebuffer_tail)
    return;
  cursor.linebuffer = cursor.linebuffer->next;
  cursor.y++;
  if(cursor.x >= cursor.linebuffer->size)
    cursor.x = cursor.linebuffer->size;

  if(is_screen_down())
    screen_down();
}
void cursor_left(){
  if(cursor.x > 0)
    cursor.x--;
}
void cursor_right(){
  if(cursor.x < cursor.linebuffer->size)
    cursor.x++;
}

// debug, dump

/*
void dump(){
  struct linebuffer *lbp;

  fprintf(stdout, "\n=== dump ===\n");

  lbp = &linebuffer_head;
  fprintf(stdout, "---buffer---\n");
  while(lbp != &linebuffer_tail){
    fprintf(stdout, "%s", lbp->buf);
    lbp = lbp->next;
  }
  fprintf(stdout, ":::buffer:::\n");
  fprintf(stdout, "---cursor---\n");
  fprintf(stdout, "x:%d, y:%d, line:%s\n", cursor.x, cursor.y, cursor.linebuffer->buf);
  fprintf(stdout, ":::cursor:::\n");
//  fprintf(stdout, "---command---\n");
//  fprintf(stdout, "%d\n", command);
//  fprintf(stdout, ":::command:::\n");
}
*/

// display
void display(struct linebuffer *head){
  int i, v;
  int last1istail = 0, last2istail = 0;
  struct linebuffer *lbp;

  v = statusbar.visibility == STATUSBAR_VISIBLE;
  i = v ? SCREEN_HEIGHT : SCREEN_HEIGHT-1;
  lbp = head;

  term_cursor_location(0,0);
  fprintf(stdout,"\033[2J");
  while(i-->0){
    fprintf(stdout, "%s", lbp->buf);
    lbp = lbp->next;
    if(i == 2 && lbp == &linebuffer_tail)
      last2istail = 1;
    if(i == 1 && lbp == &linebuffer_tail)
      last1istail = 1;
  }

  if(last1istail && last2istail)
    fprintf(stdout, "~\n");

  if(v)
    fprintf(stdout, "%s  %s", statusbar.mode, statusbar.msg);

  // for debug
  // dump();

  terminal_cursor_update();
}

// status bar
void set_statusbar_mode(char *m){
  strcpy(statusbar.mode, m);
}
void statusbar_init(){
  set_statusbar_mode("[normal]");
  statusbar.visibility = STATUSBAR_VISIBLE;
  statusbar.msglength  = 0;
}
void set_statusbar_message(char *m){
  int i=0;
  while(*(m+i) != '\0') i++;

  statusbar.msglength = i;
  strcpy(statusbar.msg, m);
}
void set_statusbar_visibility(int v){
  statusbar.visibility = v;
}
void insert_statusbar_message(char c){
  int i;
  for(i=0; i+1<STATUSBAR_MESSAGE_LENGTH; i++){
    if(statusbar.msg[i] == '\0'){
      statusbar.msglength++;
      statusbar.msg[i] = c;
      statusbar.msg[i+1] = '\0';
      return;
    }
  }
}
void clear_statusbar_message(){
  statusbar.msg[0] = '\0';
  statusbar.msglength = 0;
}

void statusbar_command_begin(){
  command = 1;
  set_statusbar_message(":");
}
void statusbar_command_end(){
  command = 0;
  clear_statusbar_message();
}
void statusbar_command_exec(){
  int i;
  char *arg1, *arg2;


  i=0;
  while((statusbar.msg[i] == ' ' || statusbar.msg[i] == ':') && statusbar.msg[i] != '\0') i++;
  arg1 = statusbar.msg+i;

  if(statusbar.msg[i] != '\0')
    i++;

  while(statusbar.msg[i] == ' ' && statusbar.msg[i] != '\0') i++;
  arg2 = statusbar.msg+i;

  switch(*arg1){
  case 'e':
    if(*arg2 != '\0'){
      strcpy(inputfilename, arg2);
      load();
    }
    break;
  case 'w':
    if(*arg2 != '\0')
      strcpy(outputfilename, arg2);
    else
      strcpy(outputfilename, "default.viout");
    save();
    break;
  case 'q':
    quit();
    break;
  default:
    break;
  }
  clear_statusbar_message();
}

void error(char *msg){
  set_statusbar_message(msg);
}

// buffer
void link_linebuffer(struct linebuffer *l, struct linebuffer *r){
  l->next = r;
  r->prev = l;
}
void alloc_linebuffer(struct linebuffer *lb){
  lb->buf  = malloc(LINE_BUFFER_LENGTH);
  lb->size = 0;
  lb->prev = 0;
  lb->next = 0;
}
struct linebuffer *create_linebuffer(){
  struct linebuffer *lbp;
  lbp = malloc(sizeof(struct linebuffer));
  alloc_linebuffer(lbp);
  return lbp;
}

// mode
void mode_change(int m){
  mode = m;
  switch(m){
  case MODE_INSERT:
    set_statusbar_mode("[insert]");
    return;
  case MODE_NORMAL:
    set_statusbar_mode("[normal]");
    return;
  }
}

void delete_normal(){
  if(*(cursor.linebuffer->buf+cursor.x) == '\n' || cursor.x == cursor.linebuffer->size)
    return;
  memmove(cursor.linebuffer->buf+cursor.x, cursor.linebuffer->buf+cursor.x+1, cursor.linebuffer->size-cursor.x);

  cursor.linebuffer->buf[cursor.linebuffer->size] = '\0';
  if(cursor.linebuffer->size > 0)
    cursor.linebuffer->size--;

  if(cursor.x >= cursor.linebuffer->size)
    cursor_left();
}
void deleteline_normal(){
  struct linebuffer *p, *n;

  p = cursor.linebuffer->prev;
  n = cursor.linebuffer->next;

  if(p == &linebuffer_head && n == &linebuffer_tail){
    memset(cursor.linebuffer->buf, '\0', sizeof(cursor.linebuffer->buf));
    cursor.linebuffer->size = 0;
    return;
  }

  link_linebuffer(p,n);

  free(cursor.linebuffer->buf);
  free(cursor.linebuffer);

  if(n != &linebuffer_tail){
    cursor.linebuffer = n;
  }else{
    cursor_up();
    cursor.linebuffer = p;
  }
}

void save(){
  FILE *ofile;
  struct linebuffer *lbp;

  ofile = fopen(outputfilename, "w+");

  lbp = linebuffer_head.next;
  while(lbp != &linebuffer_tail){
    fprintf(ofile, "%s", lbp->buf);
    lbp = lbp->next;
  }
  fclose(ofile);
}

void load(){
  FILE *ifile;
  char buf[LINE_BUFFER_LENGTH];
  int len;
  struct linebuffer *lbp,*lbpnext;

  ifile = fopen(inputfilename, "r");
  if(ifile == 0) return;

  lbp  = &linebuffer_head;
  while(fgets(buf, sizeof(buf), ifile) != 0){
    lbpnext = create_linebuffer();
    strcpy(lbpnext->buf, buf);
    lbpnext->size = strlen(buf)-1;
    link_linebuffer(lbp, lbpnext);
    lbp  = lbpnext;
    memset(buf, '\0', sizeof(buf));
  }
  link_linebuffer(lbp, &linebuffer_tail);
  
  cursor.linebuffer = linebuffer_head.next;
  cursor.x = 0;
  cursor.y = 1;
  screen.upperline = linebuffer_head.next;

  fclose(ifile);
}

void quit(){
  quit_flg = 1;
}

int ischaracter(char c){
  return 0x20 <= c && c <= 0x7e;
}

void input_command(char c){
  switch(c){
  case KEYCODE_ESC:
    statusbar_command_end();
    return;
  case KEYCODE_CR:
  case KEYCODE_LF:
    statusbar_command_exec();
    statusbar_command_begin();
    return;
  default:
    if(!ischaracter(c))
      return;
    insert_statusbar_message(c);
    return;
  }
}

void input_mode_normal(char c){
  if(command){
    input_command(c);
    return;
  }

  switch(c){
  case 'a':
    cursor_right();
    mode_change(MODE_INSERT);
    return;
  case 'i':
    mode_change(MODE_INSERT);
    return;
  case 'h':
    cursor_left();
    return;
  case 'j':
    cursor_down();
    return;
  case 'k':
    cursor_up();
    return;
  case 'l':
    cursor_right();
    return;
  case 'x':
    delete_normal();
    return;
  case 'd':
    deleteline_normal();
    return;
  case ':':
    statusbar_command_begin();
    return;
  }
}

void enter_insert(){
  struct linebuffer *lbp, *lbpnext;
  lbp = create_linebuffer();

  strcpy(lbp->buf, cursor.linebuffer->buf+cursor.x);
  lbp->size = cursor.linebuffer->size - cursor.x;
  cursor.linebuffer->size = cursor.x;
  cursor.linebuffer->buf[cursor.x] = '\n';
  memset(cursor.linebuffer->buf+cursor.x+1, '\0', LINE_BUFFER_LENGTH-cursor.x-1);

  lbpnext = cursor.linebuffer->next;
  link_linebuffer(cursor.linebuffer, lbp);
  link_linebuffer(lbp, lbpnext);

  cursor_down();
  cursor.x = 0;
}

void character_insert(char c){
  memmove(cursor.linebuffer->buf+(cursor.x+1), cursor.linebuffer->buf+cursor.x, cursor.linebuffer->size-cursor.x+1);
  cursor.linebuffer->buf[cursor.x] = c;

  cursor.linebuffer->size++;
  cursor_right();
}

void input_mode_insert(char c){
  switch(c){
  case KEYCODE_ESC:
    mode_change(MODE_NORMAL);
    return;
  case KEYCODE_CR:
  case KEYCODE_LF:
    enter_insert();
    return;
  default:
    if(!ischaracter(c))
      return;
    character_insert(c);
    return;
  }
}

void input_hook(){
  char c;
  read(0, &c, 1);

  switch(mode){
  case MODE_NORMAL:
    set_statusbar_mode("[normal]");
    input_mode_normal(c);
    return;
  case MODE_INSERT:
    set_statusbar_mode("[insert]");
    input_mode_insert(c);
    return;
  default:
    error("undefined mode");
    return;
  }
}

// term
void init_term(){
  tcgetattr(0, &termios);
  termios.c_lflag &= ~ICANON;
  tcsetattr(0, TCSANOW, &termios);
}
void restore_term(){
  termios.c_lflag |= ICANON;
  tcsetattr(0, TCSANOW, &termios);
}

// init
void init(){
  struct linebuffer *lbp;
  lbp = create_linebuffer();

  mode     = MODE_NORMAL;
  quit_flg = 0;
  cursor_init(lbp);
  statusbar_init();

  alloc_linebuffer(&linebuffer_head);
  alloc_linebuffer(&linebuffer_tail);
  link_linebuffer(&linebuffer_tail, &linebuffer_tail);
  link_linebuffer(&linebuffer_head, lbp);
  link_linebuffer(lbp, &linebuffer_tail);
  strcpy(linebuffer_tail.buf,"~\n");

  // screen_init: after buffer initialization
  screen_init();
}

void cleanup(){
  struct linebuffer *lbp, *lbptmp;
  lbp = (&linebuffer_tail)->prev;
  while(lbp != &linebuffer_head){
    lbptmp = lbp;
    lbp    = lbp->prev;
    free(lbptmp->buf);
    free(lbptmp);
  }
  free(linebuffer_head.buf);
  free(linebuffer_tail.buf);
}

// main
int main(int argc, char *argv[]){
  struct linebuffer *top;

  init();
  init_term();

  if(argc == 2){
    strcpy(inputfilename, argv[1]);
    load();
  }

  while(1){
    top = screen_top();
    display(top);
    input_hook();

    if(quit_flg) break;
  }
  printf("\n");
  term_cursor_location(0,0);
  fprintf(stdout,"\033[2J");

  restore_term();
  cleanup();

  exit(0);
}


<|start_filename|>include/unistd.h<|end_filename|>
#ifndef _XV6_UNISTD_H
#define _XV6_UNISTD_H

#include <stddef.h>

struct stat;
struct rtcdate;

ssize_t write(int, const void *, size_t);
ssize_t read(int, void *, size_t);
int close(int);

int fork(void);
int _exit(void);
int wait(void);
int pipe(int*);
int kill(int);
int exec(char*, char**);
int mknod(char*, short, short);
int unlink(char*);
int fstat(int fd, struct stat*);
int link(char*, char*);
int mkdir(char*);
int chdir(char*);
int dup(int);
int getpid(void);
char* sbrk(int);
int sleep(int);
int uptime(void);
int halt(void);

#endif  /* unistd.h */


<|start_filename|>trap.c<|end_filename|>
#include <sys/types.h>
#include <xv6/param.h>
#include "defs.h"
#include "memlayout.h"
#include "mmu.h"
#include "proc.h"
#include "gaia.h"
#include "traps.h"
#include "spinlock.h"

struct spinlock tickslock;
uint ticks;

extern void alltraps();

void
trapinit(void)
{
  *(int*)INTHANDLER = (int)alltraps;
  initlock(&tickslock, "time");
}

void
trap(struct trapframe *tf)
{
  tf->trapno = readtrapno();
  tf->retaddr = readtreturn();

  if(tf->trapno == T_SYSCALL){
    if(proc->killed)
      exit();
    proc->tf = tf;
    syscall();
    if(proc->killed)
      exit();
    return;
  }

  switch(tf->trapno){
  case T_TIMER:
    if(cpu->id == 0){
      acquire(&tickslock);
      ticks++;
      wakeup(&ticks);
      release(&tickslock);
    }
    break;
  case T_COM1:
    uartintr();
    break;

  default:
    if(proc == 0 || cpu->privilege == PL_KERN){
      // In kernel, it must be our mistake.
      cprintf("unexpected trap %d from cpu %d pc 0x%x\n",
              tf->trapno, cpu->id, tf->retaddr);
      panic("trap");
    }
    // In user space, assume process misbehaved.
    cprintf("pid %d %s: trap %d pc 0x%x --kill proc\n",
        proc->pid, proc->name, tf->trapno, tf->retaddr);
    proc->killed = 1;
  }

  // Force process exit if it has been killed and is in user space.
  // (If it is still executing in the kernel, let it keep running
  // until it gets to the regular system call return.)
  if(proc && proc->killed)
    exit();

  // Force process to give up CPU on clock tick.
  // If interrupts were on while locks held, would need to check nlock.
  if(proc && proc->state == RUNNING && tf->trapno == T_TIMER)
    yield();

  // Check if the process has been killed since we yielded
  if(proc && proc->killed)
    exit();
}


<|start_filename|>include/curses.h<|end_filename|>
#ifndef _CURSES_H
#define _CURSES_H

#include <stdio.h>

#define OK  0
#define ERR 1

// console size
#define COLS  80
#define LINES 24

typedef struct charcell{
  char letter;
  char color;
} charcell;

// initializes
void initscr();
void noecho();
void curs_set(int);
void endwin();

// outputs
int clear();                   // clear & refresh screen
int erase();                   // clear screen
int move(int, int);            // move cursol
int addch(char);               // print char @cursol
int addstr(char*);             // print string @culsol
int mvaddch(int, int, char);   // move & addch
int mvaddstr(int, int, char*); // move & addstr
int refresh();                 // refresh screen

#endif /* curses.h */


<|start_filename|>usr/minesweeper.c<|end_filename|>
/*
 *
 * [TODO]
 *  : invalid command when reading "o 2"
 */

#include <stdio.h>
#include <stdlib.h>

#define MINESWEEPER_DEBUG 0

#define MAX_HEIGHT_SIZE 16
#define MAX_WIDTH_SIZE  30

// cell status
#define BOMB_MASK 15
#define OPENED 16
#define MARKED 32
#define BOMB   64

// command
#define INIT 0
#define IOPEN 1
#define OPEN 2
#define MARK 3
#define QUIT 4
#define HELP 5
#define NOP  6

// difficulty
#define EASY     1
#define MEDIUM   2
//#define ADVANCED 3

struct command{
  int com;
  int x, y;
} command;

char board[MAX_HEIGHT_SIZE][MAX_WIDTH_SIZE];
int height, width;
int bomb;
int initialized;

char buf[128];

char displayed[] = {
  // init, open, mark, bomb
     ' ',  '+',  'x',  'b'
};

int board2disp(int i, int j){
  if((board[i][j] & OPENED) && (board[i][j] & BOMB)) return 3;
  if(board[i][j] & OPENED) return 1;
  if(board[i][j] & MARKED) return 2;
  return 0;
}

void print_2d(int n){
  if(n < 10){
    printf(" %d", n);
  }else{
    printf("%d", n);
  }
}

void showboard(){
  int i,j;

  printf("\033[2J");
  printf("\033[1;1H");
  printf("   ||");
  for(i=0; i<width; i++){
    print_2d(i);
    printf(" |");
  }
  printf("\n---++");
  for(i=0; i<width; i++){
    printf("---+", i);
  }
  printf("\n");
  for(i=0; i<width; i++){
    print_2d(i);
    printf(" || ");
    for(j=0; j<height; j++){
      if(board2disp(i,j) == 1)
        printf("%d | ", board[i][j] & BOMB_MASK);
      else
        printf("%c | ", displayed[board2disp(i,j)]);
    }
    printf("\n");
  }
}

#if MINESWEEPER_DEBUG == 1
void dumpboard(){
  int i,j;
  for(i=0; i<width; i++){
    for(j=0; j<height; j++){
      print_2d(board[i][j]);
      printf(" ");
    }
    printf("\n");
  }
}
#endif

int myrand(int n) {
  static int lcg = 0;
  int x;
  lcg = 1664525 * lcg + 1013904223;
  x = lcg % n;
  return x < 0 ? x + n : x;
}

unsigned int xor128(void) {
  static unsigned int x = 123456789;
  static unsigned int y = 362436069;
  static unsigned int z = 521288629;
  static unsigned int w = 88675123;
  unsigned int t;

  t = x ^ (x << 11);
  x = y; y = z; z = w;
  return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}

int isvalid(int x, int y){
  return 0 <= x && x < width && 0 <= y && y < height;
}

// set board size by nums
void init00(int h, int w, int b){
   height = h;
   width  = w;
   bomb   = b;
}

// set board size by macro
void init0(int s){
  switch(s){
  case EASY:
    init00(9, 9,10);
    return;
  case MEDIUM:
    init00(16,16,40);
    return;
//  case ADVANCED:
//    init00(30,16,99);
//    return;
  }
}

// set number of bomb 0
void init1(){
  int i,j;
  for(i=0; i<width; i++){
    for(j=0; j<height; j++){
      board[i][j] = 0;
    }
  }
  initialized = 1;
}

// add number of bomb by bomb_number
void init2(int p, int q){
  int x, y;
  int i,j, bnum;
  int bomb_number;
  int drc[] = {-1, 0, 1};

  bomb_number = bomb;
  if(height*width < bomb_number-1) return;

  while(bomb_number > 0){
    x = xor128()%height;
    y = xor128()%width;

    if(p-1 <= x && x <= p+1 && q-1 <= y && y <= q+1) continue;
    if(board[x][y] & BOMB) continue;

    board[x][y] = BOMB;
    bomb_number--;

    for(i=0; i<3; i++){
      for(j=0; j<3; j++){
        if(i == 1 && j == 1) continue;

        if(isvalid(x+drc[i], y+drc[j])){
          bnum = board[x+drc[i]][y+drc[j]] & BOMB_MASK;
          bnum++;
          board[x+drc[i]][y+drc[j]] = (board[x+drc[i]][y+drc[j]] & ~BOMB_MASK) | bnum;
        }
      }
    }
  }
}

int isclear(){
  int i,j;

  for(i=0; i<width; i++){
    for(j=0; j<height; j++){
      if(!(board[i][j] & BOMB) && !(board[i][j] & OPENED)){
        return 0;
      }
    }
  }
  return 1;
}

int isgameover(){
  int i,j;

  for(i=0; i<width; i++){
    for(j=0; j<height; j++){
      if((board[i][j] & BOMB) && (board[i][j] & OPENED)){
        return 1;
      }
    }
  }
  return 0;
}

void getcom(struct command *com){
  char *c, *x, *y;
  int xint, yint;

  fgets(buf, sizeof(buf), stdin);

  c = buf;
  while(*c == ' ' && *c != '\0') c++;
  x = c + 1;
  while(*x == ' ' && *x != '\0') x++;
  y = x;
  while('0' <= *y && *y <= '9')  y++;
  while(*y == ' ' && *y != '\0') y++;

  xint = 0;
  yint = 0;
  while('0' <= *x && *x <= '9'){
    xint = xint*10 + (*x - '0');
    x++;
  }
  while('0' <= *y && *y <= '9'){
    yint = yint*10 + (*y - '0');
    y++;
  }

  switch(*c){
  case 'i':
    com->com = INIT;
    com->x   = xint;
    return;
  case 'o':
    com->com = initialized == 1 ? IOPEN : OPEN;
    com->x   = xint;
    com->y   = yint;
    initialized = 0;
    return;
  case 'm':
    com->com = MARK;
    com->x   = xint;
    com->y   = yint;
    return;
  case 'q':
    com->com = QUIT;
    return;
  case 'h':
    com->com = HELP;
    return;
  default:
    com->com = NOP;
    return;
  }
}

void mine_open(struct command *com){
  int x, y;
  int i, j;
  struct command com_tmp;
  int drc[] = {-1, 0, 1};

  x = com->x;
  y = com->y;

  if(!(board[x][y] & (OPENED | MARKED)))
    board[x][y] |= OPENED;
  else
    return;

  if((board[x][y] & BOMB_MASK) == 0){
    for(i=0; i<3; i++){
      for(j=0; j<3; j++){
        com_tmp.x = x+drc[i];
        com_tmp.y = y+drc[j];
        if(!(i==1 && j==1) && isvalid(com_tmp.x, com_tmp.y))
          mine_open(&com_tmp);
      }
    }
  }
}

void mine_mark(struct command *com){
  int x, y;
  x = com->x;
  y = com->y;

  if(!(board[x][y] & OPEN))
    board[x][y] ^= MARKED;
}

void mine_help(){
  printf("commands:\n");
  printf("  i, init x (x = 1,2)\n");
  printf("  o, open x y\n");
  printf("  m, mark x y\n");
  printf("  q, quit    \n");
}

int action(struct command *com){
  switch(com->com){
  case QUIT:
    return 1;
  case INIT:
    return 0;
  case IOPEN:
    init2(com->x, com->y);
    mine_open(com);
    return 0;
  case OPEN:
    mine_open(com);
    return 0;
  case MARK:
    mine_mark(com);
    return 0;
  default:
    printf("program mistake: unknown action\n");
    return 1;
  }
}

int main(){
  int exit_game;
  struct command com;

  init0(EASY);
  init1();

  while(1){
    showboard();
#if MINESWEEPER_DEBUG == 1
    dumpboard();
#endif

    printf("type 'help' to see available commands\n");
    com.com = NOP;
    while(com.com == NOP || com.com == HELP){
      if(com.com == HELP)
        mine_help();

      printf("command> ");
      getcom(&com);
    }

    if(com.com == INIT){
      printf("initinit!\n");
      if(EASY <= com.x && com.x <= MEDIUM)
        init0(com.x);
      else
        init0(EASY);

      init1();
      continue;
    }

    exit_game = action(&com);

    if(exit_game){
      showboard();
      printf("exit minesweeper\n");
      break;
    }
    if(isgameover()){
      showboard();
      printf("gameover...\n");
      break;
    }
    if(isclear()){
      showboard();
      printf("clear!\n");
      break;
    }
  }

  exit(0);
}


<|start_filename|>usr/as/parse.c<|end_filename|>
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "parse.h"

void
skip_space_and_comma(buffer *buf)
{
  char *s = buf->str;
  int  i = buf->cur;
  while (s[i] == ' ' || s[i] == ',') {
    ++i;
  }
  buf->cur = i;
}

int
get_token(char *token, buffer *buf)
{
  int i;
  char *s = buf->str;
  int n = strlen(buf->str);
  skip_space_and_comma(buf);
  i = buf->cur;

  if (i >= n) return -1;

  while (i < n &&
         s[i] != ',' &&
         s[i] != ' ' ) {
    ++i;
  }
  strncpy(token, &s[buf->cur], i - buf->cur);
  token[i - buf->cur]='\0';
  buf->cur = i;
  return 1;
}

int
get_line(char *token, buffer *buf)
{
  int i;
  char *s = buf->str;
  int n = strlen(buf->str);
  skip_space_and_comma(buf);
  i = buf->cur;

  if (i >= n) return -1;

  while (i < n &&
         s[i] != '\n') {
    ++i;
  }
  strncpy(token, &s[buf->cur], i - buf->cur);
  token[i - buf->cur]='\0';
  buf->cur = i;
  return 1;
}



int
regnum(char *r)
{
  if(r[0] != 'r') {
    fprintf(stderr, "%s is not register\n", r);
    return -1;
  }

  if (strcmp(r, "rsp") == 0) {
    return 30;
  }

  if (strcmp(r, "rbp") == 0) {
    return 31;
  }

  return atoi(r + 1);
}

unsigned
read_hex(char *hx)
{
  int i;
  unsigned r = 0;
  assert(hx[0] == '0' &&
         (hx[1] == 'x' || hx[1] == 'X'));
  i = 2;
  while(hx[i] != '\0') {
    unsigned t;
    if (isdigit(hx[i])) {
      t = hx[i] - '0';
    } else if (isalpha(hx[i])) {

      if (islower(hx[i])) {
        assert('a' <= hx[i] && hx[i] <= 'f');
        t = (hx[i] - 'a') + 10;
      } else {
        assert('A' <= hx[i] && hx[i] <= 'F');
        t = (hx[i] - 'A') + 10;
      }

    } else {
      fprintf(stderr, "Error: read_hex %s\n", hx);
      exit(1);
    }

    r = (r<<4) + t;
    ++i;
  }

  return r;

}


unsigned
read_num(char *num)
{
  if (num[0] == '0' && (num[1] == 'x' || num[1] == 'X'))
    return read_hex(num);
  return atoi(num);
}

void
rm_comment(char *str)
{
  int i;
  int l = strlen(str);

  for (i = 0; i < l; ++i) {
    if (str[i] == '#') {
      str[i] = '\0';
      break;
    }
  }

}

void
rstrip(char *str)
{
  int i = strlen(str) - 1;
  while(i >= 0) {
    if (str[i] != '\n' &&
        str[i] != '\r' &&
        str[i] != '\t' &&
        str[i] != ' ') {
      break;
    }
    --i;
  }
  str[i + 1] = '\0';
}


<|start_filename|>usr/sh.c<|end_filename|>
// Shell.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <fcntl.h>
#include <unistd.h>
#include <termios.h>

// Parsed command representation
#define EXEC  1
#define REDIR 2
#define PIPE  3
#define LIST  4
#define BACK  5

#define MAXARGS 10

struct cmd {
  int type;
};

struct execcmd {
  int type;
  char *argv[MAXARGS];
  char *eargv[MAXARGS];
};

struct redircmd {
  int type;
  struct cmd *cmd;
  char *file;
  char *efile;
  int mode;
  int fd;
};

struct pipecmd {
  int type;
  struct cmd *left;
  struct cmd *right;
};

struct listcmd {
  int type;
  struct cmd *left;
  struct cmd *right;
};

struct backcmd {
  int type;
  struct cmd *cmd;
};

int fork1(void);  // Fork but panics on failure.
void panic(char*);
struct cmd *parsecmd(char*);

// Execute cmd.  Never returns.
void
runcmd(struct cmd *cmd)
{
  int p[2];
  struct backcmd *bcmd;
  struct execcmd *ecmd;
  struct listcmd *lcmd;
  struct pipecmd *pcmd;
  struct redircmd *rcmd;

  if(cmd == 0)
    exit(0);

  switch(cmd->type){
  default:
    panic("runcmd");

  case EXEC:
    ecmd = (struct execcmd*)cmd;
    if(ecmd->argv[0] == 0)
      exit(0);
    exec(ecmd->argv[0], ecmd->argv);
    fprintf(stderr, "exec %s failed\n", ecmd->argv[0]);
    break;

  case REDIR:
    rcmd = (struct redircmd*)cmd;
    close(rcmd->fd);
    if(open(rcmd->file, rcmd->mode) < 0){
      fprintf(stderr, "open %s failed\n", rcmd->file);
      exit(1);
    }
    runcmd(rcmd->cmd);
    break;

  case LIST:
    lcmd = (struct listcmd*)cmd;
    if(fork1() == 0)
      runcmd(lcmd->left);
    wait();
    runcmd(lcmd->right);
    break;

  case PIPE:
    pcmd = (struct pipecmd*)cmd;
    if(pipe(p) < 0)
      panic("pipe");
    if(fork1() == 0){
      close(1);
      dup(p[1]);
      close(p[0]);
      close(p[1]);
      runcmd(pcmd->left);
    }
    if(fork1() == 0){
      close(0);
      dup(p[0]);
      close(p[0]);
      close(p[1]);
      runcmd(pcmd->right);
    }
    close(p[0]);
    close(p[1]);
    wait();
    wait();
    break;

  case BACK:
    bcmd = (struct backcmd*)cmd;
    if(fork1() == 0)
      runcmd(bcmd->cmd);
    break;
  }
  exit(0);
}

char *readline();
void free_history();

int
main(void)
{
  char *buf;
  int fd;

  // Assumes three file descriptors open.
  while((fd = open("console", O_RDWR)) >= 0){
    if(fd >= 3){
      close(fd);
      break;
    }
  }

  // Read and run input commands.
  while((buf = readline())){
    if(strncmp(buf, "cd ", 3) == 0){
      // Clumsy but will have to do for now.
      // Chdir has no effect on the parent if run in the child.
      buf += 3;
      while (*buf == ' ') ++buf;
      if(chdir(buf) < 0)
        fprintf(stderr, "cannot cd %s\n", buf);
      continue;
    }
    if(fork1() == 0)
      runcmd(parsecmd(buf));
    wait();
  }

  free_history();
  exit(0);
}

void
panic(char *s)
{
  fprintf(stderr, "%s\n", s);
  exit(1);
}

int
fork1(void)
{
  int pid;

  pid = fork();
  if(pid == -1)
    panic("fork");
  return pid;
}

// Constructors

struct cmd*
execcmd(void)
{
  struct execcmd *cmd;

  cmd = malloc(sizeof(*cmd));
  memset(cmd, 0, sizeof(*cmd));
  cmd->type = EXEC;
  return (struct cmd*)cmd;
}

struct cmd*
redircmd(struct cmd *subcmd, char *file, char *efile, int mode, int fd)
{
  struct redircmd *cmd;

  cmd = malloc(sizeof(*cmd));
  memset(cmd, 0, sizeof(*cmd));
  cmd->type = REDIR;
  cmd->cmd = subcmd;
  cmd->file = file;
  cmd->efile = efile;
  cmd->mode = mode;
  cmd->fd = fd;
  return (struct cmd*)cmd;
}

struct cmd*
pipecmd(struct cmd *left, struct cmd *right)
{
  struct pipecmd *cmd;

  cmd = malloc(sizeof(*cmd));
  memset(cmd, 0, sizeof(*cmd));
  cmd->type = PIPE;
  cmd->left = left;
  cmd->right = right;
  return (struct cmd*)cmd;
}

struct cmd*
listcmd(struct cmd *left, struct cmd *right)
{
  struct listcmd *cmd;

  cmd = malloc(sizeof(*cmd));
  memset(cmd, 0, sizeof(*cmd));
  cmd->type = LIST;
  cmd->left = left;
  cmd->right = right;
  return (struct cmd*)cmd;
}

struct cmd*
backcmd(struct cmd *subcmd)
{
  struct backcmd *cmd;

  cmd = malloc(sizeof(*cmd));
  memset(cmd, 0, sizeof(*cmd));
  cmd->type = BACK;
  cmd->cmd = subcmd;
  return (struct cmd*)cmd;
}
// Parsing

char whitespace[] = " \t\r\n\v";
char symbols[] = "<|>&;()";

int
gettoken(char **ps, char *es, char **q, char **eq)
{
  char *s;
  int ret;

  s = *ps;
  while(s < es && strchr(whitespace, *s))
    s++;
  if(q)
    *q = s;
  ret = *s;
  switch(*s){
  case 0:
    break;
  case '|':
  case '(':
  case ')':
  case ';':
  case '&':
  case '<':
    s++;
    break;
  case '>':
    s++;
    if(*s == '>'){
      ret = '+';
      s++;
    }
    break;
  default:
    ret = 'a';
    while(s < es && !strchr(whitespace, *s) && !strchr(symbols, *s))
      s++;
    break;
  }
  if(eq)
    *eq = s;

  while(s < es && strchr(whitespace, *s))
    s++;
  *ps = s;
  return ret;
}

int
peek(char **ps, char *es, char *toks)
{
  char *s;

  s = *ps;
  while(s < es && strchr(whitespace, *s))
    s++;
  *ps = s;
  return *s && strchr(toks, *s);
}

struct cmd *parseline(char**, char*);
struct cmd *parsepipe(char**, char*);
struct cmd *parseexec(char**, char*);
struct cmd *nulterminate(struct cmd*);

struct cmd*
parsecmd(char *s)
{
  char *es;
  struct cmd *cmd;

  es = s + strlen(s);
  cmd = parseline(&s, es);
  peek(&s, es, "");
  if(s != es){
    fprintf(stderr, "leftovers: %s\n", s);
    panic("syntax");
  }
  nulterminate(cmd);
  return cmd;
}

struct cmd*
parseline(char **ps, char *es)
{
  struct cmd *cmd;

  cmd = parsepipe(ps, es);
  while(peek(ps, es, "&")){
    gettoken(ps, es, 0, 0);
    cmd = backcmd(cmd);
  }
  if(peek(ps, es, ";")){
    gettoken(ps, es, 0, 0);
    cmd = listcmd(cmd, parseline(ps, es));
  }
  return cmd;
}

struct cmd*
parsepipe(char **ps, char *es)
{
  struct cmd *cmd;

  cmd = parseexec(ps, es);
  if(peek(ps, es, "|")){
    gettoken(ps, es, 0, 0);
    cmd = pipecmd(cmd, parsepipe(ps, es));
  }
  return cmd;
}

struct cmd*
parseredirs(struct cmd *cmd, char **ps, char *es)
{
  int tok;
  char *q, *eq;

  while(peek(ps, es, "<>")){
    tok = gettoken(ps, es, 0, 0);
    if(gettoken(ps, es, &q, &eq) != 'a')
      panic("missing file for redirection");
    switch(tok){
    case '<':
      cmd = redircmd(cmd, q, eq, O_RDONLY, 0);
      break;
    case '>':
      cmd = redircmd(cmd, q, eq, O_WRONLY|O_CREATE, 1);
      break;
    case '+':  // >>
      cmd = redircmd(cmd, q, eq, O_WRONLY|O_CREATE, 1);
      break;
    }
  }
  return cmd;
}

struct cmd*
parseblock(char **ps, char *es)
{
  struct cmd *cmd;

  if(!peek(ps, es, "("))
    panic("parseblock");
  gettoken(ps, es, 0, 0);
  cmd = parseline(ps, es);
  if(!peek(ps, es, ")"))
    panic("syntax - missing )");
  gettoken(ps, es, 0, 0);
  cmd = parseredirs(cmd, ps, es);
  return cmd;
}

struct cmd*
parseexec(char **ps, char *es)
{
  char *q, *eq;
  int tok, argc;
  struct execcmd *cmd;
  struct cmd *ret;

  if(peek(ps, es, "("))
    return parseblock(ps, es);

  ret = execcmd();
  cmd = (struct execcmd*)ret;

  argc = 0;
  ret = parseredirs(ret, ps, es);
  while(!peek(ps, es, "|)&;")){
    if((tok=gettoken(ps, es, &q, &eq)) == 0)
      break;
    if(tok != 'a')
      panic("syntax");
    cmd->argv[argc] = q;
    cmd->eargv[argc] = eq;
    argc++;
    if(argc >= MAXARGS)
      panic("too many args");
    ret = parseredirs(ret, ps, es);
  }
  cmd->argv[argc] = 0;
  cmd->eargv[argc] = 0;
  return ret;
}

// NUL-terminate all the counted strings.
struct cmd*
nulterminate(struct cmd *cmd)
{
  int i;
  struct backcmd *bcmd;
  struct execcmd *ecmd;
  struct listcmd *lcmd;
  struct pipecmd *pcmd;
  struct redircmd *rcmd;

  if(cmd == 0)
    return 0;

  switch(cmd->type){
  case EXEC:
    ecmd = (struct execcmd*)cmd;
    for(i=0; ecmd->argv[i]; i++)
      *ecmd->eargv[i] = 0;
    break;

  case REDIR:
    rcmd = (struct redircmd*)cmd;
    nulterminate(rcmd->cmd);
    *rcmd->efile = 0;
    break;

  case PIPE:
    pcmd = (struct pipecmd*)cmd;
    nulterminate(pcmd->left);
    nulterminate(pcmd->right);
    break;

  case LIST:
    lcmd = (struct listcmd*)cmd;
    nulterminate(lcmd->left);
    nulterminate(lcmd->right);
    break;

  case BACK:
    bcmd = (struct backcmd*)cmd;
    nulterminate(bcmd->cmd);
    break;
  }
  return cmd;
}


/* readline library */

#define PROMPT      "$ "
#define PROMPT_LEN   2
#define HISTORY     16
#define TMP_UNIT    64
#define REALLOC(p, size) \
  do if (! (p = realloc(p, size))) { fprintf(stderr, "realloc failed\n"); exit(1); } while (0)

char *hist[HISTORY], *tmp;
int hist_index, cur_index;
int tmp_size;
int pos, len, col = 80;

void extend_tmp()
{
  tmp_size += TMP_UNIT;
  REALLOC(tmp, tmp_size + 1);
}

void move_cursor(int target, int opt)
{
  int cx = ((opt ? len : pos) + PROMPT_LEN) % col;
  int cy = ((opt ? len : pos) + PROMPT_LEN) / col;
  int tx = (target + PROMPT_LEN) % col;
  int ty = (target + PROMPT_LEN) / col;
  if (ty < cy) printf("\x1b[%dA", cy - ty);
  if (ty > cy) printf("\x1b[%dB", ty - cy);
  if (tx > cx) printf("\x1b[%dC", tx - cx);
  if (tx < cx) printf("\x1b[%dD", cx - tx);
  pos = target;
}

void key_left()  { if (pos > 0)   move_cursor(pos - 1, 0); }
void key_right() { if (pos < len) move_cursor(pos + 1, 0); }
void key_home()  { move_cursor(0, 0); }
void key_end()   { move_cursor(len, 0); }

void move_history(int idx)
{
  cur_index = idx;
  key_home();
  pos = len;
  memset(tmp, ' ', len);
  printf("%s", tmp);
  if ((len + PROMPT_LEN) % col == 0)
    printf("\n");
  key_home();
  if (idx == hist_index) {
    len = 0;
    tmp[0] = '\0';
    return;
  }
  pos = len = strlen(hist[idx]);
  if (tmp_size < len) {
    tmp_size = (len / TMP_UNIT + 1) * TMP_UNIT;
    REALLOC(tmp, tmp_size + 1);
  }
  memcpy(tmp, hist[idx], len + 1);
  printf("%s", tmp);
  if ((len + PROMPT_LEN) % col == 0)
    printf("\n");
}

void key_up()
{
  int idx = (cur_index - 1 + HISTORY) % HISTORY;
  if (idx == hist_index || hist[idx] == NULL)
    return;
  move_history(idx);
}

void key_down()
{
  if (cur_index == hist_index)
    return;
  move_history((cur_index + 1) % HISTORY);
}

void key_delete()
{
  int i;
  if (pos == len)
    return;
  for (i = pos; i < len; ++i)
    tmp[i] = tmp[i + 1];
  printf("%s ", tmp + pos);
  if ((len + PROMPT_LEN) % col == 0)
    printf("\n");
  move_cursor(pos, 1);
  --len;
}

void key_backspace()
{
  if (pos == 0)
    return;
  key_left();
  key_delete();
}

void key_enter()
{
  int prv;
  key_end();
  printf("\n");
  while (len > 0 && tmp[len - 1] == ' ')
    tmp[--len] = '\0';
  prv = (hist_index - 1 + HISTORY) % HISTORY;
  if (len == 0 || tmp[0] == ' ' || (hist[prv] && !strcmp(tmp, hist[prv])))
    return;
  REALLOC(hist[hist_index], len + 1);
  memcpy(hist[hist_index], tmp, len + 1);
  hist_index = (hist_index + 1) % HISTORY;
}

void insert_char(int c)
{
  int i;
  if (len == tmp_size)
    extend_tmp();
  for (i = len; i >= pos; --i)
    tmp[i + 1] = tmp[i];
  tmp[pos] = c;
  printf("%s", tmp + pos);
  ++pos; ++len;
  if ((len + PROMPT_LEN) % col == 0)
    printf("\n");
  move_cursor(pos, 1);
}

// returned pointer is valid until next readline call
char *readline()
{
  static int init_term = 0;
  static struct termios original, settings;

  int state = 0, ctrl_d = 0;

  tmp_size = TMP_UNIT;
  REALLOC(tmp, tmp_size + 1);

  printf(PROMPT);
  fflush(stdout);

  if (!init_term) {
    init_term = 1;
    tcgetattr(0, &original);
    settings = original;
    cfmakeraw(&settings);
  }
  tcsetattr(0, TCSANOW, &settings);

  tmp[0] = '\0';
  pos = len = 0;
  cur_index = hist_index;

  while (1) {
    char c;
    read(0, &c, 1);
    if (c == '\x1b') {
      state = 1;
    } else if (state == 1) {    // \x1b
      state = 0;
      if (c == '[') state = 2;
      if (c == 'O') state = 3;
    } else if (state == 2) {    // \x1b[
      switch (c) {
        case 'A': state = 0; key_up();    break;
        case 'B': state = 0; key_down();  break;
        case 'C': state = 0; key_right(); break;
        case 'D': state = 0; key_left();  break;
        case '1': state = 4; break;
        case '3': state = 5; break;
        case '4': state = 6; break;
        case '2': case '5': case '6': state = 7; break;
        default:  state = 0; break;
      }
    } else if (state == 3) {    // \x1bO
      state = 0;
      if (c == 'H') key_home();
      if (c == 'F') key_end();
    } else if (state == 4) {    // \x1b[1
      state = 0;
      if (c == '~') key_home();
      if (c == ';') state = 8;
    } else if (state == 5) {    // \x1b[3
      state = 0;
      if (c == '~') key_delete();
    } else if (state == 6) {    // \x1b[4
      state = 0;
      if (c == '~') key_end();
    } else if (state == 7) {
      state = 0;
    } else if (state == 8) {    // \x1b[1;
      state = c == '5' ? 9 : 0;
    } else if (state == 9) {    // \x1b[1;5
      state = 0;
      if (c == 'C') key_end();
      if (c == 'D') key_home();
    } else if (c == 127) {
      key_backspace();
    } else if (c < 32) {
      if (c == 10 || c == 13) { key_enter(); break; }
      if (c == 4) {
        if (! len) { ctrl_d = 1; break; }
        else key_delete();
      }
      if (c ==  1) key_home();
      if (c ==  2) key_left();
      if (c ==  5) key_end();
      if (c ==  6) key_right();
      if (c ==  8) key_backspace();
      if (c == 14) key_down();
      if (c == 16) key_up();
    } else {
      insert_char(c);
    }
    fflush(stdout);
  }

  tcsetattr(0, TCSANOW, &original);

  if (ctrl_d) {
    printf("\n");
    fflush(stdout);
    return NULL;
  }

  fflush(stdout);
  return tmp;
}

void free_history() {
  int i;
  for (i = 0; i < HISTORY; ++i)
    free(hist[i]);
  free(tmp);
}



<|start_filename|>syshalt.c<|end_filename|>
#include <sys/types.h>
#include "gaia.h"
#include "memlayout.h"

extern uint entrypgdir[];

int
sys_halt(void)
{
  cli(); // interrupt off

  // set pde
  *(int*)PDADDR = V2P(entrypgdir);
  __asm(".space 40\n");

  // go to phys addr
  __asm("mov r1, sys_halt_destination - 0x80000000\n");
  __asm("jr r1\n");
  __asm("sys_halt_destination:\n");

  *(int*)VAENABLE = 0; // mmu off

  // go to boot loader
  __asm("mov r1, 0x80000000\n");
  __asm("jr r1\n");
}


<|start_filename|>main.c<|end_filename|>
#include <sys/types.h>
#include <xv6/param.h>
#include "defs.h"
#include "memlayout.h"
#include "mmu.h"
#include "proc.h"
#include "gaia.h"

static void mpmain(void);
extern pde_t *kpgdir;

extern char end[];

// Bootstrap processor starts running C code here.
// Allocate a real stack and switch to it, first
// doing some setup required for memory allocator to work.
int
main(void)
{
  kinit1(end, P2V(1024*1024)); // phys page allocator
  kvmalloc();      // kernel page table
  mpinit();       // collect info about this machine
  cprintf("\ncpu%d: starting xv6\n\n", cpu->id);

  consoleinit();   // I/O devices & their interrupts
  deviceinit();
  uartinit();      // serial port

  pinit();         // process table
  trapinit();        // trap vectors
  binit();         // buffer cache
  fileinit();      // file table
  iinit();         // inode cache
  ideinit();       // disk
  if(!ismp)
    timerinit();   // uniprocessor timer

  kinit2(P2V(1024*1024), P2V(PHYSTOP)); // must come after startothers()
  userinit();      // first user process
  // Finish setting up this processor in mpmain.
  mpmain();
}


// Common CPU setup code.
static void
mpmain(void)
{
  cprintf("cpu%d: starting\n", cpu->id);
  cpu->started = 1;
  scheduler();     // start running processes
}


<|start_filename|>include/stddef.h<|end_filename|>
#ifndef _UCC_STDDEF_H
#define _UCC_STDDEF_H

#define NULL 0
typedef unsigned size_t;
typedef int ssize_t;
typedef int ptrdiff_t;

#endif  /* stddef.h */


<|start_filename|>include/fcntl.h<|end_filename|>
#ifndef _UCC_FCNTL_H
#define _UCC_FCNTL_H

#define O_RDONLY  0x000
#define O_WRONLY  0x001
#define O_RDWR    0x002
#define O_CREATE  0x200

int open(const char *, int);

#endif


<|start_filename|>include/math.h<|end_filename|>
#ifndef _MATH_H
#define _MATH_H

double sqrt(double);
double fabs(double);
double sin(double);
double cos(double);
double tan(double);
double asin(double);
double acos(double);
double atan(double);
double sinh(double);
double cosh(double);
double tanh(double);
double exp(double);
double log(double);
double pow(double, double);
double floor(double);

#endif /* math.h */


<|start_filename|>syscall.c<|end_filename|>
#include <sys/types.h>
#include <xv6/param.h>
#include <sys/syscall.h>
#include "defs.h"
#include "memlayout.h"
#include "mmu.h"
#include "proc.h"
#include "gaia.h"

// User code makes a system call with syscall
// System call number in r1.
// Arguments on the stack, from the user call to the C
// library system call function. The saved user rsp points
// to a saved program counter, and then the first argument.

// Fetch the int at addr from the current process.
int
fetchint(uint addr, int *ip)
{
  if(addr >= proc->sz || addr+4 > proc->sz)
    return -1;
  *ip = *(int*)(addr);
  return 0;
}

// Fetch the nul-terminated string at addr from the current process.
// Doesn't actually copy the string - just sets *pp to point at it.
// Returns length of string, not including nul.
int
fetchstr(uint addr, char **pp)
{
  char *s, *ep;

  if(addr >= proc->sz)
    return -1;
  *pp = (char*)addr;
  ep = (char*)proc->sz;
  for(s = *pp; s < ep; s++)
    if(*s == 0)
      return s - *pp;
  return -1;
}

// Fetch the nth 32-bit system call argument.
int
argint(int n, int *ip)
{
  return fetchint(proc->tf->r30 + 4 + 4*n, ip);
}

// Fetch the nth word-sized system call argument as a pointer
// to a block of memory of size n bytes.  Check that the pointer
// lies within the process address space.
int
argptr(int n, char **pp, int size)
{
  int i;

  if(argint(n, &i) < 0)
    return -1;
  if((uint)i >= proc->sz || (uint)i+size > proc->sz)
    return -1;
  *pp = (char*)i;
  return 0;
}

// Fetch the nth word-sized system call argument as a string pointer.
// Check that the pointer is valid and the string is nul-terminated.
// (There is no shared writable memory, so the string can't change
// between this check and being used by the kernel.)
int
argstr(int n, char **pp)
{
  int addr;
  if(argint(n, &addr) < 0)
    return -1;
  return fetchstr(addr, pp);
}

extern int sys_chdir(void);
extern int sys_close(void);
extern int sys_dup(void);
extern int sys_exec(void);
extern int sys_exit(void);
extern int sys_fork(void);
extern int sys_fstat(void);
extern int sys_getpid(void);
extern int sys_kill(void);
extern int sys_link(void);
extern int sys_mkdir(void);
extern int sys_mknod(void);
extern int sys_open(void);
extern int sys_pipe(void);
extern int sys_read(void);
extern int sys_sbrk(void);
extern int sys_sleep(void);
extern int sys_unlink(void);
extern int sys_wait(void);
extern int sys_write(void);
extern int sys_uptime(void);
extern int sys_halt(void);
extern int sys_ioctl(void);
extern int sys_procdump(void);

int callsys (int num) {
  switch(num){
  case SYS_fork   : return sys_fork();
  case SYS_exit   : return sys_exit();
  case SYS_wait   : return sys_wait();
  case SYS_pipe   : return sys_pipe();
  case SYS_read   : return sys_read();
  case SYS_kill   : return sys_kill();
  case SYS_exec   : return sys_exec();
  case SYS_fstat  : return sys_fstat();
  case SYS_chdir  : return sys_chdir();
  case SYS_dup    : return sys_dup();
  case SYS_getpid : return sys_getpid();
  case SYS_sbrk   : return sys_sbrk();
  case SYS_sleep  : return sys_sleep();
  case SYS_uptime : return sys_uptime();
  case SYS_open   : return sys_open();
  case SYS_write  : return sys_write();
  case SYS_mknod  : return sys_mknod();
  case SYS_unlink : return sys_unlink();
  case SYS_link   : return sys_link();
  case SYS_mkdir  : return sys_mkdir();
  case SYS_close  : return sys_close();
  case SYS_halt   : return sys_halt();
  case SYS_ioctl  : return sys_ioctl();
  case SYS_procdump : return sys_procdump();
  default         : return -1;
  }
}

void
syscall(void)
{
  int num;
  num = proc->tf->r1;
  if(num <= 0){
    cprintf("%d %s: unknown sys call %d\n", proc->pid, proc->name, num);
    panic("unknown sys call");
  } else {
    proc->tf->r1 = callsys(num);
  }
}


<|start_filename|>gaia.h<|end_filename|>
#ifndef __ASSEMBLER__
#include "memlayout.h"
#include "traps.h"
#endif

#define PL_USER 3
#define PL_KERN 0

#define HEADER_SIZE 4

#ifndef __ASSEMBLER__

// Routines to let C code use special GAIA instructions and memory addresses.

static inline void
cli(void)
{
  *(int*)INTENABLE = 0;
}

static inline void
sti(void)
{
  *(int*)INTENABLE = 1;
}

// read interrupt flag
static inline uchar
is_interruptible(void)
{
  return *(int*)INTENABLE;
}


static inline void
setpd(uint val)
{
  *(int*)PDADDR = val;
  __asm(".space 40\n"); // 10 nops
}

// read trap no
static inline uint
readtrapno()
{
  return *(int*)CAUSE;
}
// read trap return address
static inline uint
readtreturn()
{
  switch(readtrapno()){
    case T_SYSCALL:
      return *(int*)EPC; // GAIA stores the correct interrupted address for sysenter exception.
    default:
      return *(int*)EPC - 4; // GAIA stores interrupted address + 4 for the others.
  }
}

// Layout of the trap frame built on the stack by the
// hardware and by trapasm.S, and passed to trap().
struct trapframe {
  uint privilege;
  // trapno: set in trap.c
  uint trapno;
  uint retaddr;

  // general registers
  uint r31;
  uint r30;
  uint r29;
  uint r28;
  uint r27;
  uint r26;
  uint r25;
  uint r24;
  uint r23;
  uint r22;
  uint r21;
  uint r20;
  uint r19;
  uint r18;
  uint r17;
  uint r16;
  uint r15;
  uint r14;
  uint r13;
  uint r12;
  uint r11;
  uint r10;
  uint r9;
  uint r8;
  uint r7;
  uint r6;
  uint r5;
  uint r4;
  uint r3;
  uint r2;
  uint r1;
};
#endif


<|start_filename|>proc.h<|end_filename|>
// Segments in proc->gdt.
#define NSEGS     7

// Per-CPU state
struct cpu {
  int privilege;               // Make up for GAIA's lack of privilege control.
  uchar id;                    // Local APIC ID; index into cpus[] below
  struct context *scheduler;   // swtch() here to enter scheduler
  volatile uint started;       // Has the CPU started?
  int ncli;                    // Depth of pushcli nesting.
  int intena;                  // Were interrupts enabled before pushcli?

  // Cpu-local storage variables; see below
  struct cpu *cpu;
  struct proc *proc;           // The currently-running process.
};

extern struct cpu cpus[NCPU];
extern int ncpu;

// Per-CPU variables, holding pointers to the
// current cpu and to the current process.

extern struct cpu *cpu;
extern struct proc *proc;

// Saved registers for kernel context switches.
// Don't need to save the all registers, because the
// calling convention is that the caller has saved most of them.
// Contexts are stored at the bottom of the stack they
// describe; the stack pointer is the address of the context.
// The layout of the context matches the layout of the stack in swtch.S
// at the "Switch stacks" comment. Switch doesn't save pc explicitly,
// but it is on the stack and allocproc() manipulates it.
struct context {
  uint r28;
  uint r29;
  uint rbp;
};

enum procstate { UNUSED, EMBRYO, SLEEPING, RUNNABLE, RUNNING, ZOMBIE };

// Per-process state
struct proc {
  uint sz;                     // Size of process memory (bytes)
  pde_t* pgdir;                // Page table
  char *kstack;                // Bottom of kernel stack for this process
  enum procstate state;        // Process state
  int pid;                     // Process ID
  struct proc *parent;         // Parent process
  struct trapframe *tf;        // Trap frame for current syscall
  struct context *context;     // swtch() here to run process
  void *chan;                  // If non-zero, sleeping on chan
  int killed;                  // If non-zero, have been killed
  struct file *ofile[NOFILE];  // Open files
  struct inode *cwd;           // Current directory
  char name[16];               // Process name (debugging)
};


<|start_filename|>uart.c<|end_filename|>
// Intel 8250 serial port (UART).

#include <sys/types.h>
#include <sys/file.h>
#include <xv6/param.h>
#include <xv6/fs.h>
#include "defs.h"
#include "traps.h"
#include "spinlock.h"
#include "mmu.h"
#include "proc.h"
#include "gaia.h"
#include "memlayout.h"

static int uart;    // is there a uart?

void
uartinit(void)
{
  char *p;
  uart = 1;
  // Announce that we're here.
  for(p="xv6...\n"; *p; p++){
    uartputc(*p);
  }
}

void
microdelay()
{
}

void
uartputc(int c)
{
  int i;
  if(!uart)
    return;
  while(*(int*)SERIALWE == 0) microdelay();
  *(int*)SERIAL = c;
}

static int
uartgetc(void)
{
  if(!uart)
    return -1;
  return *(int*)SERIAL;
}

void
uartintr(void)
{
  consoleintr(uartgetc);
}


<|start_filename|>usr/halt.c<|end_filename|>
#include <unistd.h>

int
main(int argc, char *argv[])
{
  halt();
}


<|start_filename|>entry.c<|end_filename|>
#include <sys/types.h>
#include "mmu.h"
#include "memlayout.h"

void set_entrypgdir(pde_t *entrypgdir, pde_t *entrypgtable)
{
  int i;

  // Create boot page table.
  for (i = 0; i < 256; i++) {
    entrypgtable[i] = (i << 12) | PTE_P | PTE_W;
  }
  entrypgtable[0] |= 0x80000000;
  entrypgtable[1] |= 0x80000000;
  // Map VA's [0, EXTMEM) to PA's [KERNBASE, KERNLINK)
  // Map VA's [EXTMEM, 1MB) to PA's [EXTMEM, 1MB)
  entrypgdir[0] = (pde_t) entrypgtable | PTE_P | PTE_W;
  // Map VA's [KERNLINK, KERNBASE+1MB) to PA's [EXTMEM,1MB)
  // Map VA's [KERNBASE, KERNLINK) to PA's [KERNBASE, KERNLINK]
  entrypgdir[KERNBASE >> PDXSHIFT] = (pde_t) entrypgtable | PTE_P | PTE_W;
}


<|start_filename|>include/termios.h<|end_filename|>
#ifndef _UCC_TERMIOS_H
#define _UCC_TERMIOS_H

typedef unsigned int  tcflag_t;
typedef unsigned char cc_t;

#define NCCS 32
struct termios {
  tcflag_t c_iflag;      /* input modes */
  tcflag_t c_oflag;      /* output modes */
  tcflag_t c_cflag;      /* control modes */
  tcflag_t c_lflag;      /* local modes */
  cc_t     c_cc[NCCS];   /* special characters */
};

int tcgetattr(int,  struct termios *);
void cfmakeraw(struct termios *);
int tcsetattr(int, int, const struct termios *);

/* c_lflag bits */
#define ECHO	0000010
#define ICANON	0000002

/* tcsetattr uses these */
#define	TCSANOW		0

#endif


<|start_filename|>include/stdlib.h<|end_filename|>
#ifndef _UCC_STDLIB_H
#define _UCC_STDLIB_H

#include <stddef.h>

#define RAND_MAX 2147483647

void abort(void);
int abs(int);
long strtol(const char *, char **, int);
int rand(void);
void srand(unsigned);
void *malloc(size_t);
void *realloc(void *, size_t);
void *calloc(size_t, size_t);
void free(void *);
void exit(int);
int atoi(const char*);

#endif  /* stdlib.h */


<|start_filename|>usr/as/vector.c<|end_filename|>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "vector.h"
#define max(a,b) (a) > (b) ? (a) : (b)


Vector *
vec_create(int l)
{
  Vector *v = malloc(sizeof(Vector));
  if (l != 0)
    v->body = malloc(sizeof(void *) * l);
  v->sz = 0;
  v->nalloc = l;
  return v;
}

void *
vec_get(Vector *v, int idx)
{

  assert(idx < v->sz);

  return v->body[idx];

}



static void
expand(Vector *v, int i)
{

  int n;
  if (v->sz + i < v->nalloc) {
    return;
  }

  n = v->nalloc + max(v->nalloc, i);

  v->body = realloc(v->body, n);
  assert(!v->body);

  v->nalloc = n;

}


void
vec_push(Vector *v, void *val)
{

  expand(v, 1);
  v->body[v->sz++] = val;

}


int
vec_lengh(Vector *v)
{

  return v->sz;

}


<|start_filename|>lib/libm.c<|end_filename|>
/*
 * math.h
 */

static double __pow_fi(double a,int n){
  // return a^x
  double r = 1.0;
  while(n-- > 0) r *= a;
  return r;
}


/*
 * sqrt
 * fabs
 *
 */
double sqrt(double x){
  __asm("\
  mov r1, [rbp + 4]     \n\
  mov     r4, 0.5       \n\
  mov     r5, 1.5       \n\
  mov     r3, 0x5f375a86\n\
  shr     r2, r1, 1     \n\
  sub     r2, r3, r2    \n\
  fmul    r4, r1, r4    \n\
  fmul    r3, r2, r4    \n\
  fmul    r3, r2, r3    \n\
  fsub    r3, r5, r3    \n\
  fmul    r2, r2, r3    \n\
  fmul    r3, r2, r4    \n\
  fmul    r3, r2, r3    \n\
  fsub    r3, r5, r3    \n\
  fmul    r2, r2, r3    \n\
  fmul    r3, r2, r4    \n\
  fmul    r3, r2, r3    \n\
  fsub    r3, r5, r3    \n\
  fmul    r2, r2, r3    \n\
  fmul    r1, r1, r2    \n\
  ret\n");
}

double fabs(double x){
  return x < 0 ? -x : x;
}

/*
 * kernel sin
 * kernel cos
 *
 * x is in range [-pi/4, pi/4]
 *
 */
static double __kernel_sin(double x){
  double a1, a2, a3, a4;

  a1 = 0.1666667;
  a2 = 0.0500000;
  a3 = 0.0238095;
  a4 = 0.0138888;

  return x*(1-a1*x*x*(1-a2*x*x*(1-a3*x*x*(1-a4*x*x))));
}
static double __kernel_cos(double x){
  double a1, a2, a3, a4;

  a1 = 0.5000000;
  a2 = 0.0833333;
  a3 = 0.0333333;
  a4 = 0.0178571;

  return (1-a1*x*x*(1-a2*x*x*(1-a3*x*x*(1-a4*x*x))));
}

/*
 * __frem_for_triangle
 *
 * i is a quotient, x = pi/4 * i + (return value)
 *
 */
static double __frem_for_triangle(double x, int *i){
  double pi4;

  *i=0;
  pi4 = 0.7853981; // const value

  while(x - (*i)*pi4 >= 0) (*i) += 1;
  *i -= 1;

  return (x - (*i)*pi4);
}

/*
 * sin
 *   sin(x) = -sin(-x)
 * cos
 *   cos(x) = cos(-x)
 * tan
 *   tan(x) = tan(x + pi/2)
 */
double sin(double x){
  int i, neg;
  double y;

  neg = x > 0 ? 1 : -1;
  x   = x > 0 ? x : -x;
  y   = __frem_for_triangle(x, &i);

  if(i%8 >= 4 && neg == 1) neg = -1;
  else if(i%8 >= 4 && neg == -1) neg = 1;

  switch(i%4){
    case 0:
      return neg * __kernel_sin(y);
    case 1:
      return neg * __kernel_cos(0.7853981 - y);
    case 2:
      return neg * __kernel_cos(y);
    default:
      return neg * __kernel_sin(0.7853981 - y);
  }
}
double cos(double x){
  int i;
  double y;

  x = x > 0 ? x : -x;
  y = __frem_for_triangle(x, &i);

  switch(i%8){
    case 0:
      return __kernel_cos(y);
    case 1:
      return __kernel_sin(0.7853981 - y);
    case 2:
      return - __kernel_sin(y);
    case 3:
      return - __kernel_cos(0.7853981 - y);
    case 4:
      return - __kernel_cos(y);
    case 5:
      return - __kernel_sin(0.7853981 - y);
    case 6:
      return __kernel_sin(y);
    default:
      return __kernel_cos(0.7853981 - y);
  }
}
double tan(double x){
  return sin(x)/cos(x);
}

static double __arctan_sub(double x){
  return x*(1.0 - 0.33333333*x*x*(1.0 - 0.60*x*x*(1.0 - 2.1428571*x*x)));
}

/*
 * arctan
 *
 * arctan(x) = - arctan(-x)
 *
 * Algorithm:
 *  0 <= x <= sqrt(2) - 1:
 *    x -  1/3 x^3 + 1/5 x^5 + ...
 *  sqrt(2) - 1 < x < 1
 *    pi/4 - arctan((1-x)/(1+x))
 *  1 <= x < 1 + sqrt(2)
 *    z = 1/x
 *    arctan(x) = pi/2 - arctan(z)
 *  1 + sqrt(2) <= x
 *    z = 1/x
 *    arctan(x) = pi/2 - arctan(z)
 *
 */
double atan(double x){
  int sign;

  sign = x >= 0 ? 1 : -1;
  x    = x >= 0 ? x : -x;

  if(0.0 <= x && x <= 0.41421356){
    return sign * __arctan_sub(x);
  }else if(0.41421356 < x && x <= 1.0){
    double tmp;
    tmp = (1.0 - x) / (1.0 + x);
    return sign * (0.7853981 - __arctan_sub(tmp));
  }else if(1.0 <= x && x <= 2.41421356){
    double tmp;
    tmp = (x - 1.0)/(x + 1.0);
    return sign * (0.7853981 + __arctan_sub(tmp));
  }else{
    double tmp;
    tmp = 1.0/x;
    return sign * (1.5707963 - __arctan_sub(tmp));
  }
}

double asin(double x){
  if(x < -1.0 || x > 1.0) return -1024; // error
  if(x == -1.0) return -1.5707963;
  if(x == 1.0) return 1.5707963;

  if(x > 0.816){
    return atan(x/sqrt((1+x)*(1-x)));
  }else{
    return atan(x/sqrt(1-x*x));
  }
}
double acos(double x){
  if(x < -1.0 || x > 1.0) return -1024; // error
  if(x == -1.0) return 3.14159265;
  if(x == 1.0) return 0.0;

  if(x > 0.816){
    return 1.5707963 - atan(x/sqrt((1+x)*(1-x)));
  }else{
    return 1.5707963 - atan(x/sqrt(1-x*x));
  }
}

static double __exp_sub(double x){
  int i, j;
  double res, a;

  res = 0;
  for(i=0; i<10; i++){
    a=1.0;
    for(j=1; j<=i; j++){
      a *= x/(double)j;
    }
    res += a;
  }
  return res;
}
static double __frem_for_exp(double x, int *i){
  double log2;

  *i=0;
  log2 = 0.693147180; // const value

  while(x - (*i)*log2 >= 0) (*i) += 1;
  *i -= 1;

  return (x - (*i)*log2);
}

/*
 * exp
 *
 * Algorithm:
 *  0 <= x < log_e(2):
 *    1 + x + x^2/2 + ...
 *  log_e(2) <= x
 *    x = m*log_e(2) + z
 *    e^x = e^z * 2^m
 *  x < 0
 *    z = -x
 *    exp(x) = 1.0/exp(z)
 *
 */
double exp(double x){
  if(x < 0){
    return 1.0/exp(-x);
  }else if(x < 0.693147180){
    return __exp_sub(x);
  }else{
    int d, m;
    double z;

    z = __frem_for_exp(x, &m);

    d = 1;
    while(m-- > 0) d *= 2;

    return d * __exp_sub(z);
  }
}

/*
 * log(log_e)
 *   log(x) = -1 if x <= 0
 *   generally, return nan (x < 0) and -inf (x = 0)
 *
 *  Algorithm:
 *    x = 2^m * z (1 <= z < 2)
 *    y = (z-1)/(z+1)
 *    log((1+x)/(1-x)) = 2(x + x^3/3 + ...)
 *     -> log z = log((1+y)/(1-y))
 *    log x = log z + m*log(2)
 *
 * pow
 *   use exp and log
 *   a^x = exp(x * log_e(a))
 */
double log(double x){
  int i, m;
  double z, y, t;

  if(x <= 0)
    return -1;

  m = 0;
  z = x/__pow_fi(2.0, m);
  while(2.0 <= z){
    m++;
    z = x/__pow_fi(2.0, m);
  }

  y = (z-1)/(z+1);
  t = 0;

  for(i=0; i<10; i++){
    t += __pow_fi(y, 2*i+1)/(2*i + 1);
  }

  return (2.0*t + m*0.693147180);
}
double pow(double a, double x){
  return exp(x * log(a));
}

/*
 * hyperbolic function
 *
 */
double sinh(double x){
  return (exp(x) - exp(-x))/2.0;
}
double cosh(double x){
  return (exp(x) + exp(-x))/2.0;
}
double tanh(double x){
  return sinh(x)/cosh(x);
}

/*
 * floor
 */

double floor(double x) {
  __asm("\
  mov r1, [rbp + 4]     \n                      \
  floor r1, r1          \n                      \
  ret                   \n                      \
");
}


<|start_filename|>usr/as/vector.h<|end_filename|>
#ifndef VECTOR_H
#define VECTOR_H
typedef struct {
  void **body;
  int sz;
  int nalloc;
} Vector;
Vector *vec_create(int );
void   *vec_get(Vector *, int);
void    vec_push(Vector *, void *);
int     vec_lengh(Vector *);
void    vec_free(Vector *);
#endif


<|start_filename|>usr/as/ops.h<|end_filename|>
#ifndef OPS_H
#define OPS_H
int find_alu4(char *);
int find_misc0(char *);
int find_misc1(char *);
int find_misc2(char *);
int find_misc3(char *);
#endif


<|start_filename|>min-rt.c<|end_filename|>

/****************************************************************/
/*                                                              */
/* Ray Tracing Program for C                                    */
/*                                                              */
/* Original Program by <NAME>                          */
/* Arranged for Chez Scheme by <NAME>                  */
/* Arranged for Objective Caml by <NAME> and <NAME>          */
/* Added diffuse ray tracer by Y.Ssugawara                      */
/* Arranged for C by K.Watanabe and <NAME>                */
/*                                                              */
/****************************************************************/

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <math.h>
#include <unistd.h>

typedef struct {
  double x, y, z;
} vec_t;

typedef struct {
  double x, y, z, w;
} vec4_t;

typedef struct {
  int    tex, shape, surface;
  bool   isrot;
  vec_t  abc, xyz;
  bool   invert;
  double  surfparams[2];
  vec_t  color, rot123;
  vec4_t ctbl;
} obj_t;

typedef struct {
  vec_t   rgb;
  vec_t  *isect_ps;
  int    *sids;
  int    *cdif;
  vec_t  *engy;
  vec_t  *r20p;
  int     gid;
  vec_t  *nvectors;
} pixel_t;


typedef struct {
  vec_t   vec;
  double *cnst[120]; /* cnstの各要素は定数の配列(長さ4~6でオブジェクトの形による) */
} dvec_t;

typedef struct {
  int   sid;
  dvec_t  dv;
  double br;
} refl_t;


/**************** グローバル変数の宣言 ****************/

/* オブジェクトの個数 */
int n_objects = 0;

/* オブジェクトのデータを入れるベクトル（最大60個）*/
obj_t objects[60];

/* Screen の中心座標 */
vec_t screen;

/* 視点の座標 */
vec_t viewpoint;

/* 光源方向ベクトル (単位ベクトル) */
vec_t light;

/* 鏡面ハイライト強度 (標準=255) */
double beam = 255.0;

/* AND ネットワークを保持 */
int *and_net[50];

/* OR ネットワークを保持 */
int **or_net;

/* 以下、交差判定ルーチンの返り値格納用 */
/* solver の交点 の t の値 */
double solver_dist = 0.0;

/* 交点の直方体表面での方向 */
int intsec_rectside = 0;

/* 発見した交点の最小の t */
double tmin = 1000000000.0;

/* 交点の座標 */
vec_t intersection_point;

/* 衝突したオブジェクト番号 */
int intersected_object_id = 0;

/* 法線ベクトル */
vec_t nvector;

/* 交点の色 */
vec_t texture_color;

/* 計算中の間接受光強度を保持 */
vec_t diffuse_ray;
/* スクリーン上の点の明るさ */
vec_t rgb;

/* 画像サイズ */
int image_size[2];

/* 画像の中心 = 画像サイズの半分 */
int image_center[2];

/* 3次元上のピクセル間隔 */
double scan_pitch;

/* judge_intersectionに与える光線始点 */
vec_t startp;

/* judge_intersection_fastに与える光線始点 */
vec_t startp_fast;

/* 画面上のx,y,z軸の3次元空間上の方向 */
vec_t screenx_dir;
vec_t screeny_dir;
vec_t screenz_dir;

/* 直接光追跡で使う光方向ベクトル */
vec_t ptrace_dirvec;

/* 間接光サンプリングに使う方向ベクトル */
dvec_t *dirvecs[5];

/* 光源光の前処理済み方向ベクトル */
dvec_t light_dirvec;

/* 鏡平面の反射情報 */
refl_t reflections[180];

/* reflectionsの有効な要素数 */
int n_reflections;

/******************************************************************************
   Runtime
*****************************************************************************/

#define fneg(x)    (-(x))
#define fispos(x)  ((x) > 0.0)
#define fisneg(x)  ((x) < 0.0)
#define fiszero(x) ((x) == 0.0)
#define fhalf(x)   ((x) * 0.5)
#define fsqr(x)    ((x) * (x))

#define int_of_double(f) ((int)(f))
#define float_of_int(i) ((double)(i))

int read_int() {
  unsigned n = 0;
  n += getchar();
  n += getchar() << 8;
  n += getchar() << 16;
  n += getchar() << 24;
  return n;
}

double read_float() {
  union {unsigned i; float f;} u;
  u.i = read_int();
  return u.f;
}

void print_char(char c) {
  printf("%c", c);
}

void print_int(int i) {
  printf("%d", i);
}


/******************************************************************************
   ユーティリティー
*****************************************************************************/

/* 符号 */
double sgn (double x) {
  if (fiszero(x)) {
    return 0.0;
  } else if (fispos(x)) {
    return 1.0;
  } else {
    return -1.0;
  }
}

/* 条件付き符号反転 */
#define fneg_cond(cond, x) ((cond) ? (x) : fneg(x))


/******************************************************************************
   ベクトル操作のためのプリミティブ
*****************************************************************************/

/* 値代入 */
#define vecset(v, a, b, c)                      \
  do {                                          \
    (v)->x = a;                                 \
    (v)->y = b;                                 \
    (v)->z = c;                                 \
  } while(0)


/* 零初期化 */
#define vecbzero(v)                             \
  ((v)->x = (v)->y = (v)->z = 0.0)


/* 符号付正規化 ゼロ割チェック*/
void vecunit_sgn (vec_t *v, int inv) {
  double l  = sqrt (fsqr(v->x) + fsqr(v->y) + fsqr(v->z));
  double il;
  if (fiszero(l)) {
    il = 1.0;
  } else if (inv) {
    il = -1.0 / l;
  } else {
    il = 1.0 / l;
  }
  v->x = v->x * il;
  v->y = v->y * il;
  v->z = v->z * il;
}

/* 内積 */
#define veciprod(v, w)                                  \
  ((v)->x * (w)->x + (v)->y * (w)->y + (v)->z * (w)->z)

/* 内積 */
#define veciprod_d(v, w)                                            \
  ((v)->vec.x * (w)->x + (v)->vec.y * (w)->y + (v)->vec.z * (w)->z)

/* 内積 引数形式が異なる版 */
#define veciprod2(v, w0, w1, w2)                  \
  ((v)->x * (w0) + (v)->y * (w1) + (v)->z * (w2))


/* 別なベクトルの定数倍を加算 */
#define vecaccum(dest, scale, v)                \
  do {                                          \
    (dest)->x += (scale) * (v)->x;              \
    (dest)->y += (scale) * (v)->y;              \
    (dest)->z += (scale) * (v)->z;              \
  } while(0)

/* ベクトルの和 */
#define vecadd(dest, v)                         \
  do {                                          \
    (dest)->x += (v)->x;                        \
    (dest)->y += (v)->y;                        \
    (dest)->z += (v)->z;                        \
  } while(0)



/* ベクトルを定数倍 */
#define vecscale(dest, scale)                   \
  do {                                          \
    (dest)->x *= (scale);                       \
    (dest)->y *= (scale);                       \
    (dest)->z *= (scale);                       \
  } while(0)

/* 他の２ベクトルの要素同士の積を計算し加算 */
#define vecaccumv(dest, v, w)                   \
  do {                                          \
      (dest)->x += (v)->x * (w)->x;             \
      (dest)->y += (v)->y * (w)->y;             \
      (dest)->z += (v)->z * (w)->z;             \
      } while(0)

/******************************************************************************
   オブジェクトデータ構造へのアクセス関数
*****************************************************************************/

/* テクスチャ種 0:無し 1:市松模様 2:縞模様 3:同心円模様 4:斑点*/
#define o_texturetype(m) ((m)->tex)

/* 物体の形状 0:直方体 1:平面 2:二次曲面 3:円錐 */
#define o_form(m) ((m)->shape)

/* 反射特性 0:拡散反射のみ 1:拡散＋非完全鏡面反射 2:拡散＋完全鏡面反射 */
#define o_reflectiontype(m) ((m)->surface)

/* 曲面の外側が真かどうかのフラグ true:外側が真 false:内側が真 */
#define o_isinvert(m) ((m)->invert)

/* 回転の有無 true:回転あり false:回転無し 2次曲面と円錐のみ有効 */
#define o_isrot(m) ((m)->isrot)

/* 物体形状の aパラメータ */
#define o_param_a(m) ((m)->abc.x)
/* 物体形状の bパラメータ */
#define o_param_b(m) ((m)->abc.y)
/* 物体形状の cパラメータ */
#define o_param_c(m) ((m)->abc.z)


/* 物体形状の abcパラメータ */
#define o_param_abc(m) (&(m)->abc)


/* 物体の中心x座標 */
#define o_param_x(m) ((m)->xyz.x)
/* 物体の中心y座標 */
#define o_param_y(m) ((m)->xyz.y)
/* 物体の中心z座標 */
#define o_param_z(m) ((m)->xyz.z)


/* 物体の拡散反射率 0.0 -- 1.0 */
#define o_diffuse(m) ((m)->surfparams[0])

/* 物体の不完全鏡面反射率 0.0 -- 1.0 */
#define o_hilight(m) ((m)->surfparams[1])

/* 物体色の R成分 */
#define o_color_red(m)   ((m)->color.x)
/* 物体色の G成分 */
#define o_color_green(m) ((m)->color.y)
/* 物体色の B成分 */
#define o_color_blue(m)  ((m)->color.z)


/* 物体の曲面方程式の y*z項の係数 2次曲面と円錐で、回転がある場合のみ */
#define o_param_r1(m) ((m)->rot123.x)

/* 物体の曲面方程式の x*z項の係数 2次曲面と円錐で、回転がある場合のみ */
#define o_param_r2(m) ((m)->rot123.y)

/* 物体の曲面方程式の x*y項の係数 2次曲面と円錐で、回転がある場合のみ */
#define o_param_r3(m) ((m)->rot123.z)

/* 光線の発射点をあらかじめ計算した場合の定数テーブル */
/*
  0 -- 2 番目の要素: 物体の固有座標系に平行移動した光線始点
  3番目の要素:
  直方体→無効
  平面→ abcベクトルとの内積
  二次曲面、円錐→二次方程式の定数項
*/
#define o_param_ctbl(m) (&(m)->ctbl)

/******************************************************************************
   Pixelデータのメンバアクセス関数群
*****************************************************************************/

/* 直接光追跡で得られたピクセルのRGB値 */
#define p_rgb(p) (&(p)->rgb)

/* 飛ばした光が物体と衝突した点の配列 */
#define p_intersection_points(p) ((p)->isect_ps)

/* 飛ばした光が衝突した物体面番号の配列 */
/* 物体面番号は オブジェクト番号 * 4 + (solverの返り値) */
#define p_surface_ids(p) ((p)->sids)

/* 間接受光を計算するか否かのフラグ */
#define p_calc_diffuse(p) ((p)->cdif)

/* 衝突点の間接受光エネルギーがピクセル輝度に与える寄与の大きさ */
#define p_energy(p) ((p)->engy)

/* 衝突点の間接受光エネルギーを光線本数を1/5に間引きして計算した値 */
#define p_received_ray_20percent(p) ((p)->r20p)

/* このピクセルのグループ ID */
/*
  スクリーン座標 (x,y)の点のグループIDを (x+2*y) mod 5 と定める
  結果、下図のような分け方になり、各点は上下左右4点と別なグループになる
  0 1 2 3 4 0 1 2 3 4
  2 3 4 0 1 2 3 4 0 1
  4 0 1 2 3 4 0 1 2 3
  1 2 3 4 0 1 2 3 4 0
*/

#define p_group_id(p) ((p)->gid)

/* グループIDをセットするアクセス関数 */
#define p_set_group_id(p, id) ((p)->gid = (id))

/* 各衝突点における法線ベクトル */
#define p_nvectors(p) ((p)->nvectors)

/******************************************************************************
   前処理済み方向ベクトルのメンバアクセス関数
*****************************************************************************/

/* ベクトル */
#define d_vec(d) (&(d)->vec)

/* 各オブジェクトに対して作った solver 高速化用定数テーブル */
#define d_const(d) ((d)->cnst)

/******************************************************************************
   平面鏡面体の反射情報
*****************************************************************************/

/* 面番号 オブジェクト番号*4 + (solverの返り値) */
#define r_surface_id(r) ((r)->sid)

/* 光源光の反射方向ベクトル(光と逆向き) */
#define r_dvec(r)  &((r)->dv)

/* 物体の反射率 */
#define r_bright(r) ((r)->br)

/******************************************************************************
   データ読み込みの関数群
*****************************************************************************/

/* ラジアン */
double rad (double x) {
  return x * 0.017453293;
}

/**** 環境データの読み込み ****/

void read_screen_settings (void) {
  double v1, cos_v1, sin_v1;
  double v2, cos_v2, sin_v2;
  screen.x = read_float();
  screen.y = read_float();
  screen.z = read_float();

  v1 = rad(read_float());
  v2 = rad(read_float());
  cos_v1 = cos(v1);
  sin_v1 = sin(v1);
  cos_v2 = cos(v2);
  sin_v2 = sin(v2);

  screenz_dir.x = cos_v1 * sin_v2 * 200.0;
  screenz_dir.y = sin_v1 * (-200.0);
  screenz_dir.z = cos_v1 * cos_v2 * 200.0;
  screenx_dir.x = cos_v2;
  screenx_dir.y = 0.0;
  screenx_dir.z = - sin_v2;
  screeny_dir.x = - sin_v1 * sin_v2;
  screeny_dir.y = - cos_v1;
  screeny_dir.z = - sin_v1 * cos_v2;
  viewpoint.x = screen.x - screenz_dir.x;
  viewpoint.y = screen.y - screenz_dir.y;
  viewpoint.z = screen.z - screenz_dir.z;
}


void read_light(void) {
  int nl = read_int();
  double l1 = rad(read_float());
  double sl1 = sin(l1);
  double l2 = rad(read_float());
  double cl1 = cos(l1);
  double sl2 = sin(l2);
  double cl2 = cos(l2);
  light.y = - sl1;
  light.x = cl1 * sl2;
  light.z = cl1 * cl2;
  beam = read_float();
}

void rotate_quadratic_matrix(vec_t *abc, vec_t *rot) {
  /* 回転行列の積 R(z)R(y)R(x) を計算する */
  double cos_x = cos(rot->x);
  double sin_x = sin(rot->x);
  double cos_y = cos(rot->y);
  double sin_y = sin(rot->y);
  double cos_z = cos(rot->z);
  double sin_z = sin(rot->z);

  double m00 = cos_y * cos_z;
  double m01 = sin_x * sin_y * cos_z - cos_x * sin_z;
  double m02 = cos_x * sin_y * cos_z + sin_x * sin_z;

  double m10 = cos_y * sin_z;
  double m11 = sin_x * sin_y * sin_z + cos_x * cos_z;
  double m12 = cos_x * sin_y * sin_z - sin_x * cos_z;

  double m20 = - sin_y;
  double m21 = sin_x * cos_y;
  double m22 = cos_x * cos_y;

  /* a, b, cの元の値をバックアップ */
  double ao = abc->x;
  double bo = abc->y;
  double co = abc->z;

  /* R^t * A * R を計算 */

  /* X^2, Y^2, Z^2成分 */
  abc->x = ao * fsqr(m00) + bo * fsqr(m10) + co * fsqr(m20);
  abc->y = ao * fsqr(m01) + bo * fsqr(m11) + co * fsqr(m21);
  abc->z = ao * fsqr(m02) + bo * fsqr(m12) + co * fsqr(m22);

  /* 回転によって生じた XY, YZ, ZX成分 */
  rot->x = 2.0 * (ao * m01 * m02 + bo * m11 * m12 + co * m21 * m22);
  rot->y = 2.0 * (ao * m00 * m02 + bo * m10 * m12 + co * m20 * m22);
  rot->z = 2.0 * (ao * m00 * m01 + bo * m10 * m11 + co * m20 * m21);
}

/**** オブジェクト1つのデータの読み込み ****/
bool read_nth_object(int n) {

  int texture = read_int();
  if (texture != -1) {
    int form;
    int refltype;
    int isrot_p;
    vec_t abc;
    vec_t xyz;
    int m_invert;
    double reflparam[2];
    vec_t color;
    vec_t rotation;

    bool m_invert2;
    vec4_t ctbl;
    form = read_int();
    refltype = read_int();
    isrot_p = read_int();
    abc.x = read_float();
    abc.y = read_float();
    abc.z = read_float();


    xyz.x = read_float();
    xyz.y = read_float();
    xyz.z = read_float();

    m_invert = fisneg (read_float());

    reflparam[0] = read_float(); /* diffuse */
    reflparam[1] = read_float(); /* hilight */

    color.x = read_float();
    color.y = read_float();
    color.z = read_float(); /* 15 */

    if (isrot_p != 0) {
      rotation.x = rad (read_float());
      rotation.y = rad (read_float());
      rotation.z = rad (read_float());
    }

    /* パラメータの正規化 */

    /* 注: 下記正規化 (form = 2) 参照 */
    m_invert2 = form == 2 ? true : m_invert;



    if (form == 3) {
      /* 2次曲面: X,Y,Z サイズから2次形式行列の対角成分へ */

      double a = abc.x;
      double b = abc.y;
      double c = abc.z;
      abc.x = (a == 0.0) ? 0.0 : (sgn(a) / fsqr(a)); /* X^2 成分 */
      abc.y = (b == 0.0) ? 0.0 : (sgn(b) / fsqr(b)); /* Y^2 成分 */
      abc.z = (c == 0.0) ? 0.0 : (sgn(c) / fsqr(c)); /* Z^2 成分 */
    } else if (form == 2) {
      /* 平面: 法線ベクトルを正規化, 極性を負に統一 */
      vecunit_sgn(&abc, !m_invert);
    }

    /* 2次形式行列に回転変換を施す */
    if (isrot_p != 0) {
      rotate_quadratic_matrix(&abc, &rotation);
    }


    {
      /* ここからあとは abc と rotation しか操作しない。*/
      objects[n].tex     = texture;
      objects[n].shape   = form;
      objects[n].surface = refltype;
      objects[n].isrot   = isrot_p;

      objects[n].abc = abc;
      objects[n].xyz = xyz;

      objects[n].invert  = m_invert2;

      /* reflection paramater */
      objects[n].surfparams[0] = reflparam[0];
      objects[n].surfparams[1] = reflparam[1];

      objects[n].color = color;
      objects[n].rot123 = rotation;

      objects[n].ctbl = ctbl;
    }

    return true;
  } else {
    return false; /* データの終了 */
  }
}

/**** 物体データ全体の読み込み ****/
void read_all_object() {
  int i;
  for(i = 0; i < 60; ++i) {
    if(!read_nth_object(i)) {
      n_objects = i;
      return;
    }
  }
  assert(false); /* failwith "too many objects" */
}

/**** AND, OR ネットワークの読み込み ****/

/* ネットワーク1つを読み込みベクトルにして返す */
int *read_net_item(int length) {
  int item = read_int();
  if (item == -1) {
    int *ary = (int *) malloc(sizeof(int) * (length + 1));
    memset(ary, -1, sizeof(int) * (length + 1));
    return ary;
  }else {
    int *v = read_net_item(length + 1);
    v[length] = item;
    return v;
  }
}

int **read_or_network(int length) {
  int *net = read_net_item(0);
  if (net[0] == -1) {
    int **ary = (int **) malloc(sizeof(int*) * (length + 1));
    int i;
    for (i = 0; i < length + 1; ++i) {
      ary[i] = net;
    }
    return ary;
  } else {
    int **v = read_or_network (length + 1);
    v[length] = net;
    return v;
  }
}


void read_and_network (int n) {
  int *net = read_net_item(0);
  if (net[0] != -1) {
    free(and_net[n]);
    and_net[n] = net;
    read_and_network(n + 1);
  }
}

void read_parameter() {
  read_screen_settings();
  read_light();
  read_all_object();
  read_and_network(0);
  or_net = read_or_network(0);
}

/******************************************************************************
   直線とオブジェクトの交点を求める関数群
*****************************************************************************/

/* solver :
   オブジェクト (の index) と、ベクトル L, P を受けとり、
   直線 Lt + P と、オブジェクトとの交点を求める。
   交点がない場合は 0 を、交点がある場合はそれ以外を返す。
   この返り値は nvector で交点の法線ベクトルを求める際に必要。
   (直方体の場合)

   交点の座標は t の値として solver_dist に格納される。
*/

/* 直方体の指定された面に衝突するかどうか判定する */
/* i0 : 面に垂直な軸のindex X:0, Y:1, Z:2         i2,i3は他の2軸のindex */
bool solver_rect_surface(obj_t *m, vec_t *dirvec, double b0, double b1, double b2, int i0, int i1, int i2) {
  double *dirvec_arr = (double *) dirvec;
  if (dirvec_arr[i0] == 0.0) {
    return false;
  } else {
    vec_t *abc = o_param_abc(m);
    double *abc_arr = (double *) abc;
    double d = fneg_cond(o_isinvert(m) ^ fisneg(dirvec_arr[i0]), abc_arr[i0]);

    double d2 = (d - b0) / dirvec_arr[i0];
    if ((fabs(d2 * dirvec_arr[i1] + b1)) < abc_arr[i1]) {
      if ((fabs(d2 * dirvec_arr[i2] + b2)) < abc_arr[i2]) {
        solver_dist = d2;
        return true;
      }else {
        return false;
      }
    }
    else {
      return false;
    }
  }
}



/***** 直方体オブジェクトの場合 ****/
int solver_rect (obj_t *m, vec_t *dirvec, double b0, double b1, double b2) {
  if (solver_rect_surface(m, dirvec, b0, b1, b2, 0, 1, 2)) {
    return 1;   /* YZ 平面 */
  } else if (solver_rect_surface(m, dirvec, b1, b2, b0, 1, 2, 0)) {
    return 2;   /* ZX 平面 */
  } else if (solver_rect_surface(m, dirvec, b2, b0, b1, 2, 0, 1)) {
    return 3;   /* XY 平面 */
  } else {
    return 0;
  }
}


/* 平面オブジェクトの場合 */
int solver_surface(obj_t *m, vec_t *dirvec, double b0, double b1, double b2) {
  /* 点と平面の符号つき距離 */
  /* 平面は極性が負に統一されている */
  vec_t *abc = o_param_abc(m);
  double d = veciprod(dirvec, abc);
  if (d > 0.0) {
    solver_dist = fneg(veciprod2(abc, b0, b1, b2)) / d;
    return 1;
  } else {
    return 0;
  }
}

/* 3変数2次形式 v^t A v を計算 */
/* 回転が無い場合は対角部分のみ計算すれば良い */
double quadratic(obj_t *m, double v0, double v1, double v2) {
  double diag_part =
    fsqr(v0) * o_param_a(m) + fsqr(v1) * o_param_b(m) + fsqr(v2) * o_param_c(m);
  if (o_isrot(m) == 0) {
    return diag_part;
  } else {
    return diag_part
      + v1 * v2 * o_param_r1(m)
      + v2 * v0 * o_param_r2(m)
      + v0 * v1 * o_param_r3(m);
  }
}

/* 3変数双1次形式 v^t A w を計算 */
/* 回転が無い場合は A の対角部分のみ計算すれば良い */
double bilinear(obj_t *m, double v0, double v1, double v2, double w0, double w1, double w2) {
  double diag_part =
    v0 * w0 * o_param_a(m)
    + v1 * w1 * o_param_b(m)
    + v2 * w2 * o_param_c(m);
  if (o_isrot(m) == 0) {
    return diag_part;
  } else {
    return diag_part + fhalf
      ((v2 * w1 + v1 * w2) * o_param_r1(m)
       + (v0 * w2 + v2 * w0) * o_param_r2(m)
       + (v0 * w1 + v1 * w0) * o_param_r3(m));
  }
}

/* 2次曲面または円錐の場合 */
/* 2次形式で表現された曲面 x^t A x - (0 か 1) = 0 と 直線 base + dirvec*t の
   交点を求める。曲線の方程式に x = base + dirvec*t を代入してtを求める。
   つまり (base + dirvec*t)^t A (base + dirvec*t) - (0 か 1) = 0、
   展開すると (dirvec^t A dirvec)*t^2 + 2*(dirvec^t A base)*t  +
   (base^t A base) - (0か1) = 0 、よってtに関する2次方程式を解けば良い。*/

int solver_second(obj_t *m, vec_t *dirvec, double b0, double b1, double b2) {
  /* 解の公式 (-b' ± sqrt(b'^2 - a*c)) / a  を使用(b' = b/2) */
  /* a = dirvec^t A dirvec */
  double aa = quadratic(m, dirvec->x, dirvec->y, dirvec->z);

  if (aa == 0.0) {
    return 0; /* 正確にはこの場合も1次方程式の解があるが、無視しても通常は大丈夫 */
  } else {

    /* b' = b/2 = dirvec^t A base   */
    double bb = bilinear(m, dirvec->x, dirvec->y, dirvec->z, b0, b1, b2);
    /* c = base^t A base  - (0か1)  */
    double cc0 = quadratic(m, b0, b1, b2);
    double cc = o_form(m) == 3 ? cc0 - 1.0 : cc0;
    /* 判別式 */
    double d = bb * bb - aa * cc;

    if (d > 0.0) {
      double sd = sqrt(d);
      double t1 = o_isinvert(m) ? sd : - sd;
      solver_dist = (t1 - bb) /  aa;
      return 1;
    } else {
      return 0;
    }
  }
}

/**** solver のメインルーチン ****/
int solver(int index, vec_t *dirvec, vec_t *org) {
  obj_t *m = &objects[index];
  /* 直線の始点を物体の基準位置に合わせて平行移動 */
  double b0 =  org->x - o_param_x(m);
  double b1 =  org->y - o_param_y(m);
  double b2 =  org->z - o_param_z(m);
  int m_shape = o_form(m);
  /* 物体の種類に応じた補助関数を呼ぶ */
  int ret;
  if (m_shape == 1) {
    ret = solver_rect(m, dirvec, b0, b1, b2);    /* 直方体 */
  } else if (m_shape == 2) {
    ret = solver_surface(m, dirvec, b0, b1, b2); /* 平面 */
  } else {
    ret = solver_second(m, dirvec, b0, b1, b2);  /* 2次曲面/円錐 */
  }
  return ret;
}

/******************************************************************************
   solverのテーブル使用高速版
*****************************************************************************/
/*
  通常版solver と同様、直線 start + t * dirvec と物体の交点を t の値として返す
  t の値は solver_distに格納

  solver_fast は、直線の方向ベクトル dirvec について作ったテーブルを使用
  内部的に solver_rect_fast, solver_surface_fast, solver_second_fastを呼ぶ

  solver_fast2 は、dirvecと直線の始点 start それぞれに作ったテーブルを使用
  直方体についてはstartのテーブルによる高速化はできないので、solver_fastと
  同じく solver_rect_fastを内部的に呼ぶ。それ以外の物体については
  solver_surface_fast2またはsolver_second_fast2を内部的に呼ぶ

  変数dconstは方向ベクトル、sconstは始点に関するテーブル
*/

/***** solver_rectのdirvecテーブル使用高速版 ******/
int solver_rect_fast(obj_t *m, vec_t *v, double *dconst, double b0, double b1, double b2) {
  double d0 = (dconst[0] - b0) * dconst[1];
  bool tmp0;
  double d1 = (dconst[2] - b1) * dconst[3];
  bool tmp_zx;
  double d2 = (dconst[4] - b2) * dconst[5];
  bool tmp_xy;

  /* YZ平面との衝突判定 */
  if (fabs (d0 * v->y + b1) < o_param_b(m)) {
    if (fabs (d0 * v->z + b2) < o_param_c(m)) {
      tmp0 = dconst[1] != 0.0;
    }
    else {
      tmp0 = false;
    }
  }
  else tmp0 = false;
  if (tmp0 != false) {
    solver_dist = d0;
    return 1;
  }

  /* ZX平面との衝突判定 */
  if (fabs (d1 * v->x + b0) < o_param_a(m)) {
    if (fabs (d1 * v->z + b2) < o_param_c(m)) {
      tmp_zx = dconst[3] != 0.0;
    } else {
      tmp_zx = false;
    }
  }
  else tmp_zx = false;
  if (tmp_zx != false) {
    solver_dist = d1;
    return 2;
  }

  /* XY平面との衝突判定 */
  if (fabs (d2 * v->x + b0) < o_param_a(m)) {
    if (fabs (d2 * v->y + b1) < o_param_b(m)) {
      tmp_xy = dconst[5] != 0.0;
    }
    else tmp_xy = false;
  }
  else tmp_xy = false;
  if (tmp_xy != false) {
    solver_dist = d2;
    return 3;
  }
  return 0;
}


/**** solver_surfaceのdirvecテーブル使用高速版 ******/
int solver_surface_fast(obj_t *m, double *dconst, double b0, double b1, double b2) {
  if (fisneg(dconst[0])) {
    solver_dist = dconst[1] * b0 + dconst[2] * b1 + dconst[3] * b2;
    return 1;
  } else {
    return 0;
  }
}


/**** solver_second のdirvecテーブル使用高速版 ******/
int solver_second_fast(obj_t *m, double *dconst, double b0, double b1, double b2) {
  double aa = dconst[0];
  if (fiszero(aa)) {
    return 0;
  } else {
    double neg_bb = dconst[1] * b0 + dconst[2] * b1 + dconst[3] * b2;
    double cc0 = quadratic(m, b0, b1, b2);
    double cc = o_form(m) == 3 ? cc0 - 1.0 : cc0;
    double d = fsqr(neg_bb) - aa * cc;
    if (fispos(d)) {
      if (o_isinvert(m)) {
        solver_dist = (neg_bb + sqrt(d)) * dconst[4];
      } else {
        solver_dist = (neg_bb - sqrt(d)) * dconst[4];
      }
      return 1;
    } else {
      return 0;
    }
  }
}

/**** solver のdirvecテーブル使用高速版 *******/
int solver_fast(int index, dvec_t *dirvec, vec_t *org) {
  obj_t *m = &objects[index];
  double b0 = org->x - o_param_x(m);
  double b1 = org->y - o_param_y(m);
  double b2 = org->z - o_param_z(m);
  double **dconsts = d_const(dirvec);
  double  *dconst  = dconsts[index];
  int m_shape = o_form(m);
  int ret;
  if (m_shape == 1) {
    ret = solver_rect_fast(m, d_vec(dirvec), dconst, b0, b1, b2);
  } else if (m_shape == 2) {
    ret = solver_surface_fast(m, dconst, b0, b1, b2);
  } else {
    ret = solver_second_fast(m, dconst, b0, b1, b2);
  }
  return ret;
}


/* solver_surfaceのdirvec+startテーブル使用高速版 */
int solver_surface_fast2(obj_t *m, double *dconst, vec4_t *sconst, double b0, double b1, double b2) {
  if (fisneg(dconst[0])) {
    solver_dist = dconst[0] * sconst->w;
    return 1;
  } else {
    return 0;
  }
}

/* solver_secondのdirvec+startテーブル使用高速版 */
int solver_second_fast2(obj_t *m, double *dconst, vec4_t *sconst, double b0, double b1, double b2) {
  double aa = dconst[0];
  if (fiszero(aa)) {
    return 0;
  } else {
    double neg_bb = dconst[1] * b0 + dconst[2] * b1 + dconst[3] * b2;
    double cc = sconst->w;
    double d = fsqr(neg_bb) - aa * cc;
    if (fispos(d)) {
      if (o_isinvert(m)) {
        solver_dist = (neg_bb + sqrt(d)) * dconst[4];
      } else {
        solver_dist = (neg_bb - sqrt(d)) * dconst[4];
      }
      return 1;
    } else {
      return 0;
    }
  }
}

/* solverの、dirvec+startテーブル使用高速版 */
int solver_fast2(int index, dvec_t *dirvec) {
  obj_t *m = &objects[index];
  vec4_t *sconst = o_param_ctbl(m);
  double b0 = sconst->x;
  double b1 = sconst->y;
  double b2 = sconst->z;
  double **dconsts = d_const(dirvec);
  double  *dconst  = dconsts[index];
  int m_shape = o_form(m);
  if (m_shape == 1) {
    return solver_rect_fast(m, d_vec(dirvec), dconst, b0, b1, b2);
  } else if (m_shape == 2) {
    return solver_surface_fast2(m, dconst, sconst, b0, b1, b2);
  } else {
    return solver_second_fast2(m, dconst, sconst, b0, b1, b2);
  }
}

/******************************************************************************
   方向ベクトルの定数テーブルを計算する関数群
*****************************************************************************/

/* 直方体オブジェクトに対する前処理 */
double* setup_rect_table(vec_t *vec, obj_t *m) {
  double *consts = (double*)malloc(6 * sizeof(double));

  if (fiszero(vec->x)) { /* YZ平面 */
    consts[1] = 0.0;
  } else {
    /* 面の X 座標 */
    consts[0] = fneg_cond(o_isinvert(m)^fisneg(vec->x), o_param_a(m));
    /* 方向ベクトルを何倍すればX方向に1進むか */
    consts[1] = 1.0 / vec->x;
  }
  if (fiszero(vec->y)) { /* ZX平面 : YZ平面と同様*/
    consts[3] = 0.0;
  } else {
    consts[2] = fneg_cond(o_isinvert(m)^fisneg(vec->y), o_param_b(m));
    consts[3] = 1.0 / vec->y;
  }
  if (fiszero(vec->z)) { /* XY平面 : YZ平面と同様*/
    consts[5] = 0.0;
  } else {
    consts[4] = fneg_cond(o_isinvert(m)^fisneg(vec->z), o_param_c(m));
    consts[5] = 1.0 / vec->z;
  }
  return consts;
}

/* 平面オブジェクトに対する前処理 */
double* setup_surface_table(vec_t *vec, obj_t *m) {
  double *consts = (double*)malloc(4 * sizeof(double));
  double d = vec->x * o_param_a(m) + vec->y * o_param_b(m) + vec->z * o_param_c(m);
  if (fispos(d)) {
    /* 方向ベクトルを何倍すれば平面の垂直方向に 1 進むか */
    consts[0] = -1.0 / d;
    /* ある点の平面からの距離が方向ベクトル何個分かを導く3次一形式の係数 */
    consts[1] = fneg(o_param_a(m) / d);
    consts[2] = fneg(o_param_b(m) / d);
    consts[3] = fneg(o_param_c(m) / d);
  } else {
    consts[0] = 0;
    consts[1] = 0;
    consts[2] = 0;
    consts[3] = 0;
  }
  return consts;
}


/* 2次曲面に対する前処理 */
double* setup_second_table(vec_t *v, obj_t *m) {
  double *consts = malloc(5 * sizeof(double));
  double aa = quadratic(m, v->x, v->y, v->z);
  double c1 = fneg(v->x * o_param_a(m));
  double c2 = fneg(v->y * o_param_b(m));
  double c3 = fneg(v->z * o_param_c(m));

  consts[0] = aa;  /* 2次方程式の a 係数 */

  /* b' = dirvec^t A start だが、(dirvec^t A)の部分を計算しconst.(1:3)に格納。
     b' を求めるにはこのベクトルとstartの内積を取れば良い。符号は逆にする */
  if (o_isrot(m) != 0) {
    consts[1] = c1 - fhalf(v->z * o_param_r2(m) + v->y * o_param_r3(m));
    consts[2] = c2 - fhalf(v->z * o_param_r1(m) + v->x * o_param_r3(m));
    consts[3] = c3 - fhalf(v->y * o_param_r1(m) + v->x * o_param_r2(m));
  } else {
    consts[1] = c1;
    consts[2] = c2;
    consts[3] = c3;
  }

  if (!fiszero(aa)) {
    consts[4] = 1.0 / aa; /* a係数の逆数を求め、解の公式での割り算を消去 */
  } else {
    consts[4] = 0.0;
  }

  return consts;
}


/* 各オブジェクトについて補助関数を呼んでテーブルを作る */
void iter_setup_dirvec_constants (dvec_t *dirvec, int index) {
  while (index >= 0) {
    obj_t *m = &objects[index];
    double **dconst = d_const(dirvec);
    vec_t *v = d_vec(dirvec);
    int m_shape = o_form(m);

    if (m_shape == 1) { /* rect */
      dconst[index] = setup_rect_table(v, m);
    } else if (m_shape == 2) { /* surface */
      dconst[index] = setup_surface_table(v, m);
    } else { /* second */
      dconst[index] = setup_second_table(v, m);
    }
    --index;
  }
}

void setup_dirvec_constants(dvec_t *dirvec) {
  iter_setup_dirvec_constants(dirvec, n_objects - 1);
}

/******************************************************************************
   直線の始点に関するテーブルを各オブジェクトに対して計算する関数群
*****************************************************************************/

void setup_startp_constants(vec_t *p, int index) {
  if (index >= 0) {
    obj_t *obj = &objects[index];
    vec4_t *sconst = o_param_ctbl(obj);
    int m_shape = o_form(obj);

    sconst->x = p->x - o_param_x(obj);
    sconst->y = p->y - o_param_y(obj);
    sconst->z = p->z - o_param_z(obj);

    if (m_shape == 2) { /* surface */
      sconst->w = veciprod2(o_param_abc(obj), sconst->x, sconst->y, sconst->z);
    } else if (m_shape > 2) { /* second */
      double cc0 = quadratic(obj, sconst->x, sconst->y, sconst->z);
      sconst->w = (m_shape == 3 ? cc0 - 1.0 : cc0);
    }

    setup_startp_constants(p, index - 1);
  }
}

void setup_startp(vec_t *p) {
  startp_fast = *p;
  setup_startp_constants(p, n_objects - 1);
}

/******************************************************************************
   与えられた点がオブジェクトに含まれるかどうかを判定する関数群
*****************************************************************************/

/**** 点 q がオブジェクト m の外部かどうかを判定する ****/

/* 直方体 */
bool is_rect_outside(obj_t *m, double p0, double p1, double p2) {
  bool b0 = fabs(p0) < o_param_a(m);
  bool b1 = fabs(p1) < o_param_b(m);
  bool b2 = fabs(p2) < o_param_c(m);
  if(b0 && b1 && b2){
    return o_isinvert(m);
  } else {
    return !o_isinvert(m);
  }
}

/* 平面 */
bool is_plane_outside(obj_t *m, double p0, double p1, double p2) {
  double w = veciprod2(o_param_abc(m), p0, p1, p2);
  return !(o_isinvert(m) ^ fisneg(w));
}

/* 2次曲面 */
bool is_second_outside(obj_t *m, double p0, double p1, double p2) {
  double w  = quadratic(m, p0, p1, p2);
  double w2 = (o_form(m) == 3 ? w - 1.0 : w);
  return !(o_isinvert(m) ^ fisneg(w2));
}

/* 物体の中心座標に平行移動した上で、適切な補助関数を呼ぶ */
bool is_outside(obj_t *m, double q0, double q1, double q2) {
  double p0 = q0 - o_param_x(m);
  double p1 = q1 - o_param_y(m);
  double p2 = q2 - o_param_z(m);
  int m_shape = o_form(m);
  if (m_shape == 1) {
    return is_rect_outside(m, p0, p1, p2);
  } else if (m_shape == 2) {
    return is_plane_outside(m, p0, p1, p2);
  } else {
    return is_second_outside(m, p0, p1, p2);
  }
}

bool check_all_inside(int ofs, int *iand, double q0, double q1, double q2) {
  int head;
  while((head = iand[ofs]) != -1){

    if (is_outside(&objects[head], q0, q1, q2)) {
      return false;
    }

    ++ofs;
  }
  return true;
}


/******************************************************************************
   衝突点が他の物体の影に入っているか否かを判定する関数群
*****************************************************************************/

/* 点 intersection_point から、光線ベクトルの方向に辿り、   */
/* 物体にぶつかる (=影にはいっている) か否かを判定する。*/

/**** AND ネットワーク iand の影内かどうかの判定 ****/
bool shadow_check_and_group(int iand_ofs, int *and_group) {

  while (and_group[iand_ofs] != -1) {
    int obj   = and_group[iand_ofs];
    int t0  = solver_fast(obj, &light_dirvec, &intersection_point);
    double t0p = solver_dist;

    if (t0 != 0 && t0p < -0.2) {
      /* Q: 交点の候補。実際にすべてのオブジェクトに */
      /* 入っているかどうかを調べる。*/
      double t  = t0p + 0.01;
      double q0 = light.x * t + intersection_point.x;
      double q1 = light.y * t + intersection_point.y;
      double q2 = light.z * t + intersection_point.z;
      if (check_all_inside(0, and_group, q0, q1, q2)) {
        return true;
      }
    } else {
      /* 交点がない場合: 極性が正(内側が真)の場合、    */
      /* AND ネットの共通部分はその内部に含まれるため、*/
      /* 交点はないことは自明。探索を打ち切る。        */
      if (!o_isinvert(&objects[obj])) {
        return false;
      }
    }

    /* 次のオブジェクトから候補点を探す */
    ++iand_ofs;
  }

  return false;
}

/**** OR グループ or_group の影かどうかの判定 ****/
bool shadow_check_one_or_group(int ofs, int *or_group) {
  int head;
  while((head = or_group[ofs]) != -1) {
    int *and_group = and_net[head];
    bool shadow_p = shadow_check_and_group(0, and_group);
    if (shadow_p) {
      return true;
    }
    ++ofs;
  }
  return false;
}

/**** OR グループの列のどれかの影に入っているかどうかの判定 ****/
bool shadow_check_one_or_matrix(int ofs, int **or_matrix) {

  while(1) {
    int *head = or_matrix[ofs];
    int range_primitive = head[0];
    bool test = false;
    if (range_primitive == -1) { /* OR行列の終了マーク */
      return false;
    }

    /* range primitive が無いか、またはrange_primitiveと交わる事を確認 */
    if (range_primitive == 99) { /* range primitive が無い */
      test = true;
    } else {
      int t = solver_fast(range_primitive, &light_dirvec, &intersection_point);
      /* range primitive とぶつからなければ */
      /* or group との交点はない            */
      test = (t != 0 && solver_dist < -0.1 && shadow_check_one_or_group(1, head));
    }

    if (test && shadow_check_one_or_group(1, head)) {
      return true; /* 交点があるので、影に入る事が判明。探索終了 */
    }

    ++ofs;

  }

  return false;
}


/******************************************************************************
   光線と物体の交差判定
*****************************************************************************/

/**** あるANDネットワークが、レイトレースの方向に対し、****/
/**** 交点があるかどうかを調べる。                    ****/
void solve_each_element(int iand_ofs, int *and_group, vec_t *dirvec) {
  int iobj;
  while ((iobj = and_group[iand_ofs]) != -1) {
    int t0 = solver(iobj, dirvec, &startp);
    if (t0 != 0) {
      /* 交点がある時は、その交点が他の要素の中に含まれるかどうか調べる。*/
      /* 今までの中で最小の t の値と比べる。*/
      double t0p = solver_dist;
      if (0.0 < t0p && t0p < tmin) {
        double t = t0p + 0.01;
        vec_t *v = dirvec;
        double q0 = v->x * t + startp.x;
        double q1 = v->y * t + startp.y;
        double q2 = v->z * t + startp.z;
        if (check_all_inside(0, and_group, q0, q1, q2)) {
          tmin = t;
          vecset(&intersection_point, q0, q1, q2);
          intersected_object_id = iobj;
          intsec_rectside = t0;
        }
      }
    } else {
      /* 交点がなく、しかもその物体は内側が真ならこれ以上交点はない */
      if (!o_isinvert(&objects[iobj])) {
        return;
      }
    }
    ++iand_ofs;
  }
}


/**** 1つの OR-group について交点を調べる ****/
void solve_one_or_network(int ofs, int *or_group, vec_t *dirvec) {
  int head;
  while ((head = or_group[ofs]) != -1) {
    int *and_group = and_net[head];
    solve_each_element(0, and_group, dirvec);
    ++ofs;
  }
}


/**** ORマトリクス全体について交点を調べる。****/
void trace_or_matrix(int ofs, int **or_network, vec_t *dirvec) {
  while (1) { /* 全オブジェクト終了 */
    int *head = or_network[ofs++];
    int range_primitive = head[0];
    if (range_primitive == -1) {
      return;
    }
    if (range_primitive == 99) { /* range primitive なし */
      solve_one_or_network(1, head, dirvec);
    } else {
      /* range primitive の衝突しなければ交点はない */
      double t = solver(range_primitive, dirvec, &startp);
      if (t != 0 && solver_dist < tmin) {
        solve_one_or_network(1, head, dirvec);
      }
    }
  }
}

/**** トレース本体 ****/
/* トレース開始点 ViewPoint と、その点からのスキャン方向ベクトル */
/* Vscan から、交点 crashed_point と衝突したオブジェクト        */
/* crashed_object を返す。関数自体の返り値は交点の有無の真偽値。 */
bool judge_intersection(vec_t *dirvec) {
  double t;
  tmin = 1000000000.0;
  trace_or_matrix(0, or_net, dirvec);
  t = tmin;
  if (-0.1 < t) {
    return t < 100000000.0;
  }
  return false;
}

/******************************************************************************
   光線と物体の交差判定 高速版
*****************************************************************************/

void solve_each_element_fast(int iand_ofs, int *and_group, dvec_t *dirvec) {
  vec_t *vec = d_vec(dirvec);
  int iobj;
  while ((iobj = and_group[iand_ofs++]) != -1) {
    int t0 = solver_fast2(iobj, dirvec);
    if (t0 != 0) {
      /* 交点がある時は、その交点が他の要素の中に含まれるかどうか調べる。*/
      /* 今までの中で最小の t の値と比べる。*/
      if (0.0 < solver_dist && solver_dist < tmin) {
        double t  = solver_dist + 0.01;
        double q0 = vec->x * t + startp_fast.x;
        double q1 = vec->y * t + startp_fast.y;
        double q2 = vec->z * t + startp_fast.z;
        if (check_all_inside(0, and_group, q0, q1, q2)) {
          tmin = t;
          vecset(&intersection_point, q0, q1, q2);
          intersected_object_id = iobj;
          intsec_rectside = t0;
        }
      }
    } else if (!o_isinvert(&objects[iobj])) {
      /* 交点がなく、しかもその物体は内側が真ならこれ以上交点はない */
      return;
    }
  }
}

/**** 1つの OR-group について交点を調べる ****/
void solve_one_or_network_fast(int ofs, int *or_group, dvec_t *dirvec) {
  int head;
  while ((head = or_group[ofs++]) != -1) {
    int *and_group = and_net[head];
    solve_each_element_fast(0, and_group, dirvec);
  }
}

/**** ORマトリクス全体について交点を調べる。****/
void trace_or_matrix_fast(int ofs, int **or_network, dvec_t *dirvec) {
  while (1) {
    int *head = or_network[ofs++];
    int range_primitive = head[0];
    if (range_primitive == -1) { /* 全オブジェクト終了 */
      return;
    }
    if (range_primitive == 99) { /* range primitive なし */
      solve_one_or_network_fast(1, head, dirvec);
    } else {
      /* range primitive の衝突しなければ交点はない */
      double t = solver_fast2(range_primitive, dirvec);
      if (t != 0 && solver_dist < tmin) {
        solve_one_or_network_fast(1, head, dirvec);
      }
    }
  }
}

/**** トレース本体 ****/
bool judge_intersection_fast(dvec_t *dirvec) {
  double t;
  tmin = 1000000000.0;
  trace_or_matrix_fast(0, or_net, dirvec);
  t = tmin;
  if (-0.1 < t) {
    return t < 100000000.0;
  } else {
    return false;
  }
}


/******************************************************************************
   物体と光の交差点の法線ベクトルを求める関数
*****************************************************************************/

/**** 交点から法線ベクトルを計算する ****/
/* 衝突したオブジェクトを求めた際の solver の返り値を */
/* 変数 intsec_rectside 経由で渡してやる必要がある。 */
/* nvector もグローバル。 */
void get_nvector_rect(vec_t *dirvec) {
  int rectside = intsec_rectside;
  /* solver の返り値はぶつかった面の方向を示す */
  vecbzero(&nvector);
  switch(rectside-1) {
  case 0:
    nvector.x = fneg(sgn(dirvec->x));
    break;
  case 1:
    nvector.y = fneg(sgn(dirvec->y));
    break;
  case 2:
    nvector.z = fneg(sgn(dirvec->z));
    break;
  default:
    abort(); /* Error */
  }

}


/* 平面 */
void get_nvector_plane(obj_t *m) {
  /* m_invert は常に true のはず */
  nvector.x = fneg(o_param_a(m));
  nvector.y = fneg(o_param_b(m));
  nvector.z = fneg(o_param_c(m));
}

/* 2次曲面 :  grad x^t A x = 2 A x を正規化する */
void get_nvector_second(obj_t *m) {
  double p0 = intersection_point.x - o_param_x(m);
  double p1 = intersection_point.y - o_param_y(m);
  double p2 = intersection_point.z - o_param_z(m);

  double d0 = p0 * o_param_a(m);
  double d1 = p1 * o_param_b(m);
  double d2 = p2 * o_param_c(m);

  if (o_isrot(m) == 0) {
    nvector.x = d0;
    nvector.y = d1;
    nvector.z = d2;
  } else {
    nvector.x = d0 + fhalf(p1 * o_param_r3(m) + p2 * o_param_r2(m));
    nvector.y = d1 + fhalf(p0 * o_param_r3(m) + p2 * o_param_r1(m));
    nvector.z = d2 + fhalf(p0 * o_param_r2(m) + p1 * o_param_r1(m));
  }
  vecunit_sgn(&nvector, o_isinvert(m));
}

void get_nvector(obj_t *m, vec_t *dirvec) {
  int m_shape = o_form(m);
  if (m_shape == 1) {
    get_nvector_rect(dirvec);
  } else if (m_shape == 2) {
    get_nvector_plane(m);
  } else { /* 2次曲面 or 錐体 */
    get_nvector_second(m);
  }
}


/******************************************************************************
   物体表面の色(色付き拡散反射率)を求める
*****************************************************************************/


/**** 交点上のテクスチャの色を計算する ****/
void utexture(obj_t *m, vec_t *p) {
  int m_tex = o_texturetype(m);
  /* 基本はオブジェクトの色 */
  texture_color.x = o_color_red(m);
  texture_color.y = o_color_green(m);
  texture_color.z = o_color_blue(m);
  if (m_tex == 1) {
    /* zx方向のチェッカー模様 (G) */
    double w1 = p->x - o_param_x(m);
    double d1 = (floor(w1 * 0.05)) * 20.0;
    double w3 = p->z - o_param_z(m);
    double d2 = (floor(w3 * 0.05)) * 20.0;
    int flag1 = (w1-d1 < 10.0);
    int flag2 = (w3-d2 < 10.0);
    if (flag1 ^ flag2) {
      texture_color.y = 0.0;
    } else {
      texture_color.y = 255.0;
    }
  } else if (m_tex == 2) {
    /* y軸方向のストライプ (R-G) */
    double w2 = fsqr(sin(p->y * 0.25));
    texture_color.x = 255.0 * w2;
    texture_color.y = 255.0 * (1.0 - w2);
  } else if (m_tex == 3) {
    /* ZX面方向の同心円 (G-B) */
    double w1 = p->x - o_param_x(m);
    double w3 = p->z - o_param_z(m);
    double w2 = sqrt (fsqr(w1) + fsqr(w3)) / 10.0;
    double w4 = (w2 - floor(w2)) * 3.1415927;
    double cws= fsqr(cos(w4));
    texture_color.y = cws * 255.0;
    texture_color.z = (1.0 - cws) * 255.0;
  } else if (m_tex == 4) {
    /* 球面上の斑点 (B) */
    double w1 = (p->x - o_param_x(m)) * (sqrt(o_param_a(m)));
    double w2 = (p->z - o_param_y(m)) * (sqrt(o_param_b(m)));
    double w3 = (p->z - o_param_z(m)) * (sqrt(o_param_c(m)));
    double w4 = fsqr(w1) + fsqr(w3);
    double w5 = fabs(w3 / w1);
    double w6 = fabs(w2 / w4);
    double w7, w8, w9, w10, w11, w12;
    if (fabs(w1) < 1.0e-4) {
      w7 = 15.0; /* atan +infty = pi/2 */
    } else {
      w7 = (atan(w5) * 30.0) / 3.1415927;
    }
    if (fabs(w4) < 1.0e-4) {
      w8 = 15.0; /* atan +infty = pi/2 */
    } else {
      w8 = (atan(w6) * 30.0) / 3.1415927;
    }
    w9  = w7 - floor(w7);
    w10 = w8 - floor(w8);
    w11 = 0.15 - fsqr(0.5 - w9) - fsqr(0.5 - w10);
    w12 = (fisneg(w11)) ? 0.0 : w11;
    texture_color.z = (255.0 * w12) / 0.3;
  }
}

/******************************************************************************
   衝突点に当たる光源の直接光と反射光を計算する関数群
*****************************************************************************/

/* 当たった光による拡散光と不完全鏡面反射光による寄与をRGB値に加算 */
void add_light(double bright, double hilight, double hilight_scale) {

  /* 拡散光 */
  if (fispos(bright)) {
    vecaccum(&rgb, bright, &texture_color);
  }

  /* 不完全鏡面反射 cos ^4 モデル */
  if (fispos(hilight)) {
    double ihl = fsqr(fsqr(hilight)) * hilight_scale;
    rgb.x += ihl;
    rgb.y += ihl;
    rgb.z += ihl;
  }

}


/* 各物体による光源の反射光を計算する関数(直方体と平面のみ) */
void trace_reflections(int index, double diffuse, double hilight_scale, vec_t *dirvec) {
  while (index >= 0) {
    refl_t *rinfo = &reflections[index--]; /* 鏡平面の反射情報 */
    dvec_t *dvec  = r_dvec(rinfo);       /* 反射光の方向ベクトル(光と逆向き */

    /*反射光を逆にたどり、実際にその鏡面に当たれば、反射光が届く可能性有り */
    if (judge_intersection_fast(dvec)) {
      int surface_id = intersected_object_id * 4 + intsec_rectside;
      if (surface_id == r_surface_id(rinfo)) {
        /* 鏡面との衝突点が光源の影になっていなければ反射光は届く */
        if (!shadow_check_one_or_matrix(0, or_net)) {
          /* 届いた反射光による RGB成分への寄与を加算 */
          double p = veciprod_d(dvec, &nvector);
          double scale = r_bright(rinfo);
          double bright = scale  * diffuse * p;
          double hilight = scale * veciprod(dirvec, d_vec(dvec));
          add_light(bright, hilight, hilight_scale);
        }
      }
    }
  }
}

/******************************************************************************
   直接光を追跡する
*****************************************************************************/

void trace_ray(int nref, double energy, vec_t *dirvec, pixel_t *pixel, double dist) {
  if (nref <= 4) {
    int *surface_ids = p_surface_ids(pixel);
    if (judge_intersection(dirvec)) {
      /* オブジェクトにぶつかった場合 */
      int obj_id = intersected_object_id;
      obj_t *obj = &objects[obj_id];
      int m_surface = o_reflectiontype(obj);
      double diffuse = o_diffuse(obj) * energy;
      vec_t *intersection_points;
      int *calc_diffuse;
      double w, hilight_scale;
      get_nvector(obj, dirvec); /* 法線ベクトルを get */
      startp = intersection_point;  /* 交差点を新たな光の発射点とする */
      utexture(obj, &intersection_point); /*テクスチャを計算 */

      /* pixel tupleに情報を格納する */
      surface_ids[nref] = obj_id * 4 + intsec_rectside;
      intersection_points = p_intersection_points(pixel);
      intersection_points[nref] = intersection_point;
      /* 拡散反射率が0.5以上の場合のみ間接光のサンプリングを行う */

      calc_diffuse = p_calc_diffuse(pixel);
      if (o_diffuse(obj) < 0.5) {
        calc_diffuse[nref] = false;
      } else {
        vec_t *energya  = p_energy(pixel);
        vec_t *nvectors = p_nvectors(pixel);
        calc_diffuse[nref] = true;
        energya[nref] = texture_color;
        vecscale(&energya[nref],
                 (1.0 / 256.0) * diffuse);
        nvectors[nref] = nvector;
      }

      w = (-2.0) * veciprod(dirvec, &nvector);
      vecaccum(dirvec, w, &nvector);

      hilight_scale = energy * o_hilight(obj);
      /* 光源光が直接届く場合、RGB成分にこれを加味する */
      if (!(shadow_check_one_or_matrix(0, or_net))) {
        double bright = fneg(veciprod(&nvector, &light)) * diffuse;
        double hilight = fneg(veciprod(dirvec, &light));
        add_light(bright, hilight, hilight_scale);
      }

      /* 光源光の反射光が無いか探す */
      setup_startp(&intersection_point);
      trace_reflections(n_reflections-1, diffuse, hilight_scale, dirvec);

      /* 重みが 0.1より多く残っていたら、鏡面反射元を追跡する */
      if (0.1 < energy) {
        if (nref < 4) {
          surface_ids[nref+1] = -1;
        }
        if (m_surface == 2) {
          double energy2 = energy * (1.0 - o_diffuse(obj));
          trace_ray(nref+1, energy2, dirvec, pixel, dist + tmin);
        }
      }

    } else {
      /* どの物体にも当たらなかった場合。光源からの光を加味 */
      surface_ids[nref] = -1;
      if (nref != 0) {
        double hl = fneg(veciprod(dirvec, &light));
        /* 90°を超える場合は0 (光なし) */
        if (fispos(hl)) {
          /* ハイライト強度は角度の cos^3 に比例 */
          double ihl = fsqr(hl) * hl * energy * beam;
          rgb.x += ihl;
          rgb.y += ihl;
          rgb.z += ihl;
        }

      }

    }
  }
}


/******************************************************************************
   間接光を追跡する
*****************************************************************************/

/* ある点が特定の方向から受ける間接光の強さを計算する */
/* 間接光の方向ベクトル dirvecに関しては定数テーブルが作られており、衝突判定
   が高速に行われる。物体に当たったら、その後の反射は追跡しない */
void trace_diffuse_ray(dvec_t *dirvec, double energy) {
  /* どれかの物体に当たるか調べる */
  if (judge_intersection_fast(dirvec)) {
    obj_t *obj = &objects[intersected_object_id];
    get_nvector(obj, d_vec(dirvec));
    utexture(obj, &intersection_point);

    /* その物体が放射する光の強さを求める。直接光源光のみを計算 */
    if (!shadow_check_one_or_matrix(0, or_net)) {
      double br = fneg(veciprod(&nvector, &light));
      double bright = (fispos(br) ? br : 0.0);
      vecaccum(&diffuse_ray,
               energy * bright * o_diffuse(obj),
               &texture_color);
    }
  }

}

/* あらかじめ決められた方向ベクトルの配列に対し、各ベクトルの方角から来る
   間接光の強さをサンプリングして加算する */
void iter_trace_diffuse_rays(dvec_t *dirvec_group, vec_t *nvector, vec_t *org, int index) {
  while (index >= 0) {
    double p = veciprod(d_vec(&dirvec_group[index]), nvector);

    /* 配列の 2n 番目と 2n+1 番目には互いに逆向の方向ベクトルが入っている
       法線ベクトルと同じ向きの物を選んで使う */
    if (fisneg(p)) {
      trace_diffuse_ray(&dirvec_group[index+1], p / -150.0);
    } else {
      trace_diffuse_ray(&dirvec_group[index],   p /  150.0);
    }
    index -= 2;
  }
}

/* 与えられた方向ベクトルの集合に対し、その方向の間接光をサンプリングする */
void trace_diffuse_rays(dvec_t *dirvec_group, vec_t *nvector, vec_t *org) {
  setup_startp(org);

  /* 配列の 2n 番目と 2n+1 番目には互いに逆向の方向ベクトルが入っていて、
     法線ベクトルと同じ向きの物のみサンプリングに使われる */
  /* 全部で 120 / 2 = 60本のベクトルを追跡 */
  iter_trace_diffuse_rays(dirvec_group, nvector, org, 118);
}

/* 半球方向の全部で300本のベクトルのうち、まだ追跡していない残りの240本の
   ベクトルについて間接光追跡する。60本のベクトル追跡を4セット行う */
void trace_diffuse_ray_80percent(int group_id, vec_t *nvector, vec_t *org) {

  int i;

  for (i = 0; i <= 4; ++i) {
    if (group_id != i) {
      trace_diffuse_rays(dirvecs[i], nvector, org);
    }
  }

}

/* 上下左右4点の間接光追跡結果を使わず、300本全部のベクトルを追跡して間接光を
   計算する。20%(60本)は追跡済なので、残り80%(240本)を追跡する */
void calc_diffuse_using_1point(pixel_t *pixel, int nref) {
  vec_t *ray20p = p_received_ray_20percent(pixel);
  vec_t *nvectors = p_nvectors(pixel);
  vec_t *intersection_points = p_intersection_points(pixel);
  vec_t *energya = p_energy(pixel);
  diffuse_ray = ray20p[nref];
  trace_diffuse_ray_80percent(p_group_id(pixel),
                              &nvectors[nref],
                              &intersection_points[nref]);
  vecaccumv(&rgb, &energya[nref], &diffuse_ray);
}

/* 自分と上下左右4点の追跡結果を加算して間接光を求める。本来は 300 本の光を
   追跡する必要があるが、5点加算するので1点あたり60本(20%)追跡するだけで済む */
void calc_diffuse_using_5points(int x, pixel_t *prev, pixel_t *cur, pixel_t *next, int nref) {
  vec_t *r_up     = p_received_ray_20percent(&prev[x]);
  vec_t *r_left   = p_received_ray_20percent(&cur[x-1]);
  vec_t *r_center = p_received_ray_20percent(&cur[x]);
  vec_t *r_right  = p_received_ray_20percent(&cur[x+1]);
  vec_t *r_down   = p_received_ray_20percent(&next[x]);

  vec_t *energya  = p_energy(&cur[x]);

  diffuse_ray = r_up[nref];

  vecadd(&diffuse_ray, &r_left[nref]);
  vecadd(&diffuse_ray, &r_center[nref]);
  vecadd(&diffuse_ray, &r_right[nref]);
  vecadd(&diffuse_ray, &r_down[nref]);

  vecaccumv(&rgb, &energya[nref], &diffuse_ray);

}

/* 上下左右4点を使わずに直接光の各衝突点における間接受光を計算する */
void do_without_neighbors(pixel_t *pixel, int nref) {
  while (nref <= 4) {
    /* 衝突面番号が有効(非負)かチェック */
    int *surface_ids = p_surface_ids(pixel), *calc_diffuse;
    if (surface_ids[nref] < 0) {
      return;
    }
    calc_diffuse = p_calc_diffuse(pixel);
    if (calc_diffuse[nref]) {
      calc_diffuse_using_1point(pixel, nref);
    }
    ++nref;
  }
}

/* 画像上で上下左右に点があるか(要するに、画像の端で無い事)を確認 */
bool neighbors_exist(int x, int y, pixel_t *next) {
  if (0 < y && y+1 < image_size[1]) {
    if (0 < x && x+1 < image_size[0]) {
      return true;
    }
  }
  return false;
}

int get_surface_id(pixel_t *pixel, int index) {
  int *surface_ids = p_surface_ids(pixel);
  return surface_ids[index];
}

/* 上下左右4点の直接光追跡の結果、自分と同じ面に衝突しているかをチェック
   もし同じ面に衝突していれば、これら4点の結果を使うことで計算を省略出来る */
bool neighbors_are_available(int x, pixel_t *prev, pixel_t *cur, pixel_t *next, int nref) {
  int sid_center = get_surface_id(&cur[x], nref);
  if (get_surface_id(&prev[x],  nref) == sid_center) {
    if (get_surface_id(&next[x],  nref) == sid_center) {
      if (get_surface_id(&cur[x-1], nref) == sid_center) {
        if (get_surface_id(&cur[x+1], nref) == sid_center) {
          return true;
        }
      }
    }
  }
  return false;
}

/* 直接光の各衝突点における間接受光の強さを、上下左右4点の結果を使用して計算
   する。もし上下左右4点の計算結果を使えない場合は、その時点で
   do_without_neighborsに切り替える */
void try_exploit_neighbors(int x, int y, pixel_t *prev, pixel_t *cur, pixel_t *next, int nref) {
  pixel_t *pixel = &cur[x];
  while (nref <= 4) {
    int *calc_diffuse;
    /* 衝突面番号が有効(非負)か */
    if (get_surface_id(pixel, nref) < 0) {
      return;
    }

    /* 周囲4点を補完に使えるか */
    if (!neighbors_are_available(x, prev, cur, next, nref)) {
      /* 周囲4点を補完に使えないので、これらを使わない方法に切り替える */
        do_without_neighbors(&cur[x], nref);
        return;
    }

    /* 間接受光を計算するフラグが立っていれば実際に計算する */
    calc_diffuse = p_calc_diffuse(pixel);
    if (calc_diffuse[nref]) {
      calc_diffuse_using_5points(x, prev, cur, next, nref);
    }
    /* 次の反射衝突点へ */
    ++nref;
  }

}


/******************************************************************************
   PPMファイルの書き込み関数
*****************************************************************************/
void write_ppm_header() {
  print_char(80); /* 'P' */
  print_char(48 + 3); /* +6 if binary */ /* 48 = '0' */
  print_char(10);
  print_int(image_size[0]);
  print_char(32);
  print_int(image_size[1]);
  print_char(32);
  print_int(255);
  print_char(10);
}

void write_rgb_element(double x) {
  int ix = int_of_double(x);
  int elem = ix;
  if (ix > 255) {
    elem = 255;
  } else if (ix < 0) {
    elem = 0;
  }
  print_int(elem);
}


void write_rgb() {
  write_rgb_element(rgb.x); /* Red */
  print_char(32);
  write_rgb_element(rgb.y); /* Green */
  print_char(32);
  write_rgb_element(rgb.z); /* Blue */
  print_char(10);
}

/******************************************************************************
   あるラインの計算に必要な情報を集めるため次のラインの追跡を行っておく関数群
*****************************************************************************/

/* 間接光のサンプリングでは上下左右4点の結果を使うので、次のラインの計算を
   行わないと最終的なピクセルの値を計算できない */

/* 間接光を 60本(20%)だけ計算しておく関数 */
void pretrace_diffuse_rays(pixel_t *pixel, int nref) {
  while (nref <= 4 && get_surface_id(pixel, nref) >= 0) {
    /* 間接光を計算するフラグが立っているか */
    int *calc_diffuse = p_calc_diffuse(pixel);
    if (calc_diffuse[nref]) {
      int group_id = p_group_id(pixel);
      vec_t *nvectors;
      vec_t *intersection_points;
      vec_t *ray20p;
      vecbzero(&diffuse_ray);

      /* 5つの方向ベクトル集合(各60本)から自分のグループIDに対応する物を
         一つ選んで追跡 */
      nvectors = p_nvectors(pixel);
      intersection_points = p_intersection_points(pixel);
      trace_diffuse_rays(dirvecs[group_id],
                         &nvectors[nref],
                         &intersection_points[nref]);
      ray20p = p_received_ray_20percent(pixel);
      ray20p[nref] = diffuse_ray;
    }
    ++nref;
  }
}


/* 各ピクセルに対して直接光追跡と間接受光の20%分の計算を行う */
void pretrace_pixels(pixel_t *line, int x, int group_id, double lc0, double lc1, double lc2) {
  while (x >= 0) {
    double xdisp = scan_pitch * float_of_int(x - image_center[0]);
    ptrace_dirvec.x = xdisp * screenx_dir.x + lc0;
    ptrace_dirvec.y = xdisp * screenx_dir.y + lc1;
    ptrace_dirvec.z = xdisp * screenx_dir.z + lc2;
    vecunit_sgn(&ptrace_dirvec, false);
    vecbzero(&rgb);
    startp = viewpoint;

    /* 直接光追跡 */
    trace_ray(0, 1.0, &ptrace_dirvec, &line[x], 0.0);
    *p_rgb(&line[x]) = rgb;
    p_set_group_id(&line[x], group_id);

    /* 間接光の20%を追跡 */
    pretrace_diffuse_rays(&line[x], 0);

    --x;
    group_id = (group_id + 1) % 5;
  }
}


/* あるラインの各ピクセルに対し直接光追跡と間接受光20%分の計算をする */
void pretrace_line(pixel_t *line, int y, int group_id) {
  double ydisp = scan_pitch * float_of_int(y - image_center[1]);
  /* ラインの中心に向かうベクトルを計算 */
  double lc0 = ydisp * screeny_dir.x + screenz_dir.x;
  double lc1 = ydisp * screeny_dir.y + screenz_dir.y;
  double lc2 = ydisp * screeny_dir.z + screenz_dir.z;
  pretrace_pixels(line, image_size[0] - 1, group_id, lc0, lc1, lc2);
}

/******************************************************************************
   直接光追跡と間接光20%追跡の結果から最終的なピクセル値を計算する関数
*****************************************************************************/

/* ピクセル値を計算 */
void scan_lines(pixel_t *prev, pixel_t *cur, pixel_t *next, int group_id) {
  int y, x;
  pixel_t *t;
  for (y = 0; y < image_size[1]; ++y) {

    if (y < image_size[1] - 1) {
      pretrace_line(next, y + 1, group_id);
    }

    for (x = 0; x < image_size[0]; ++x) {
      /* まず、直接光追跡で得られたRGB値を得る */
      rgb = *p_rgb(&cur[x]);

      /* 次に、直接光の各衝突点について、間接受光による寄与を加味する */
      if (neighbors_exist(x, y, next)) {
        try_exploit_neighbors(x, y, prev, cur, next, 0);
      } else {
        do_without_neighbors(&cur[x], 0);
      }

      /* 得られた値をPPMファイルに出力 */
      write_rgb();
    }
    t = prev;
    prev = cur;
    cur  = next;
    next = t;
    group_id += 2;
    if(group_id >= 5) {
      group_id -= 5;
    }
  }
}


/******************************************************************************
   ピクセルの情報を格納するデータ構造の割り当て関数群
 *****************************************************************************/
/* ピクセルを表すtupleを割り当て */
void create_pixel(pixel_t *pixel) {
  vecbzero(&pixel->rgb);
  pixel->isect_ps = calloc(sizeof(vec_t), 5);
  pixel->sids = calloc(sizeof(int), 5);
  pixel->cdif = calloc(sizeof(int), 5);
  pixel->engy = calloc(sizeof(vec_t), 5);
  pixel->r20p = calloc(sizeof(vec_t), 5);
  pixel->gid = 0;
  pixel->nvectors = calloc(sizeof(vec_t), 5);
}

/* 横方向1ライン分のピクセル配列を作る */
pixel_t *create_pixelline() {
  pixel_t *line = calloc(sizeof(pixel_t), image_size[0]);
  int i;
  for (i = 0; i < image_size[0]; ++i) {
    create_pixel(&line[i]);
  }
  return line;
}

/******************************************************************************
   間接光のサンプリングにつかう方向ベクトル群を計算する関数群
*****************************************************************************/

/* ベクトル達が出来るだけ一様に分布するよう、600本の方向ベクトルの向きを定める
   立方体上の各面に100本ずつ分布させ、さらに、100本が立方体上の面上で10 x 10 の
   格子状に並ぶような配列を使う。この配列では方角によるベクトルの密度の差が
   大きいので、これに補正を加えたものを最終的に用いる */

/* ベクトル達が出来るだけ球面状に一様に分布するよう座標を補正する */
double adjust_position(double h, double ratio) {
  double l = sqrt(h * h + 0.1);
  double tan_h = 1.0 / l;
  double theta_h = atan(tan_h);
  double tan_m = tan(theta_h * ratio);
  return tan_m * l;
}

/* ベクトル達が出来るだけ球面状に一様に分布するような向きを計算する */
void calc_dirvec(int icount, double x, double y, double rx, double ry, int group_id, int index) {
  double l, vx, vy, vz;
  dvec_t *dgroup;

  for(; icount < 5; ++icount) {
    x = adjust_position(y, rx);
    y = adjust_position(x, ry);
  }

  l  = sqrt(fsqr(x) + fsqr(y) + 1.0);
  vx = x   / l;
  vy = y   / l;
  vz = 1.0 / l;

  /* 立方体的に対称に分布させる */
  dgroup = dirvecs[group_id];
  vecset(d_vec(&dgroup[index]),    vx, vy, vz);
  vecset(d_vec(&dgroup[index+40]), vx, vz, fneg(vy));
  vecset(d_vec(&dgroup[index+80]), vz, fneg(vx), fneg(vy));
  vecset(d_vec(&dgroup[index+1]),  fneg(vx), fneg(vy), fneg(vz));
  vecset(d_vec(&dgroup[index+41]), fneg(vx), fneg(vz), vy);
  vecset(d_vec(&dgroup[index+81]), fneg(vz), vx, vy);

}

/* 立方体上の 10x10格子の行中の各ベクトルを計算する */
void calc_dirvecs(int col, double ry, int group_id, int index) {
  while (col >= 0) {
    double rx, rx2;
    /* 左半分 */
    rx = float_of_int(col) * 0.2 - 0.9; /* 列の座標 */
    calc_dirvec(0, 0.0, 0.0, rx, ry, group_id, index);
    /* 右半分 */
    rx2 = float_of_int(col) * 0.2 + 0.1;  /* 列の座標 */
    calc_dirvec(0, 0.0, 0.0, rx2, ry, group_id, (index + 2));

    --col;
    if(++group_id >= 5) {
      group_id -= 5;
    }
  }
}

/* 立方体上の10x10格子の各行に対しベクトルの向きを計算する */
void calc_dirvec_rows(int row, int group_id, int index) {
  while (row >= 0) {
    double ry = float_of_int(row) * 0.2 - 0.9; /* 行の座標 */
    calc_dirvecs(4, ry, group_id, index); /* 一行分計算 */
    --row;
    group_id += 2;
    if(group_id >= 5) {
      group_id -= 5;
    }
    index += 4;
  }
}

void create_dirvecs(int index) {

  while(index >= 0) {
    dirvecs[index] = calloc(120, sizeof(dvec_t));
    --index;
  }

}


/******************************************************************************
   補助関数達を呼び出してdirvecの初期化を行う
*****************************************************************************/
void init_dirvec_constants(dvec_t vecset[], int index) {
  while (index >= 0) {
    setup_dirvec_constants(&vecset[index]);
    --index;
  }
}

void init_vecset_constants(int index) {
  while (index >= 0) {
    init_dirvec_constants(dirvecs[index], 119);
    --index;
  }
}

void init_dirvecs() {
  create_dirvecs(4);
  calc_dirvec_rows(9, 0, 0);
  init_vecset_constants(4);
}


/******************************************************************************
   完全鏡面反射成分を持つ物体の反射情報を初期化する
*****************************************************************************/

/* 反射平面を追加する */
void add_reflection(int index, int surface_id, double bright, double v0, double v1, double v2) {
  dvec_t *dvec = &reflections[index].dv;
  vecset(d_vec(dvec), v0, v1, v2); /* 反射光の向き */
  setup_dirvec_constants(dvec);
  reflections[index].sid = surface_id;
  reflections[index].br  = bright;
}

/* 直方体の各面について情報を追加する */
void setup_rect_reflection(int obj_id, obj_t *obj) {
  int sid = obj_id * 4;
  int nr  = n_reflections;
  double br = 1.0 - o_diffuse(obj);
  double n0 = fneg(light.x);
  double n1 = fneg(light.y);
  double n2 = fneg(light.z);
  add_reflection(nr, sid + 1, br, light.x, n1, n2);
  add_reflection(nr + 1, sid + 2, br, n0, light.y, n2);
  add_reflection(nr + 2, sid + 3, br, n0, n1, light.z);
  n_reflections += 3;
}


/* 平面について情報を追加する */
void setup_surface_reflection(int obj_id, obj_t *obj) {
  int sid = obj_id * 4 + 1;
  int nr  = n_reflections;
  double br = 1.0 - o_diffuse(obj);
  double p = veciprod(&light, o_param_abc(obj));
  add_reflection(nr, sid, br,
                 2.0 * o_param_a(obj) * p - light.x,
                 2.0 * o_param_b(obj) * p - light.y,
                 2.0 * o_param_c(obj) * p - light.z);
  n_reflections += 1;
}

/* 各オブジェクトに対し、反射する平面があればその情報を追加する */
void setup_reflections(int obj_id) {
  if (obj_id >= 0) {
    obj_t *obj = &objects[obj_id];
    if (o_reflectiontype(obj) == 2) {
      if (o_diffuse(obj) < 1.0) {
        int m_shape = o_form(obj);
        if (m_shape == 1) {
          setup_rect_reflection(obj_id, obj);
        } else if (m_shape == 2) {
          setup_surface_reflection(obj_id, obj);
        }
      }
    }
  }
}

/*****************************************************************************
   全体の制御
*****************************************************************************/

/* レイトレの各ステップを行う関数を順次呼び出す */
void rt (int size_x, int size_y) {
  pixel_t *prev, *cur, *next;
  image_size[0] = size_x;
  image_size[1] = size_y;
  image_center[0] = size_x / 2;
  image_center[1] = size_y / 2;
  scan_pitch = 128.0 / float_of_int(size_x);
  prev = create_pixelline();
  cur  = create_pixelline();
  next = create_pixelline();
  read_parameter();
  write_ppm_header();
  init_dirvecs();
  *d_vec(&light_dirvec) = light;
  setup_dirvec_constants(&light_dirvec);
  setup_reflections(n_objects - 1);
  pretrace_line(cur, 0, 0);
  scan_lines(prev, cur, next, 2);
}


int main(int argc, char *argv[]) {
  int i;
  char *p;
  int size = 8;

  if (argc > 1)
    size = atoi(argv[1]);

  for(i = 0; i < 50; ++i) {
    and_net[i] = malloc(sizeof(int));
    and_net[i][0] = -1;
  }
  p = malloc(64 * 1024);
  if(p==0) {
    fprintf(stderr, "malloc error\n");
    exit(1);
  }
  p += 64 * 1024;

  __asm("mov r1, [rbp - 12]\n");
  __asm("mov rsp, [rbp - 8]\n");
  __asm("mov rbp, [rbp - 8]\n");
  __asm("push r1\n");
  __asm("push r1\n");
  __asm("call rt\n");

  exit(0);
}


<|start_filename|>usr/as/ops.c<|end_filename|>
#include<string.h>
#include "ops.h"

static const char alu4_table[][8] = {
  "add", "sub",
  "shl", "shr", "sar",
  "and", "or", "xor",
  "cmpult", "cmpule",
  "cmpne", "cmpeq",
  "cmplt", "cmple"
};

static const int alu4_code[] = {
   0,  1,
   2,  3, 4,
   5,  6, 7,
  22, 23,
  24, 25,
  26, 27
};

static const char misc0_table[][12] = {
  "sysenter", "sysexit"
};

static const int misc0_code[] = {
  12, 13
};

static const char misc2_table[][8] = {
  "ldl", "jl"
};
static const int misc2_code[] = {
  2, 4
};

static const char misc3_table[][8] = {
  "ldh", "ld", "ldb", "st", "stb", "bne", "beq"
};

static const int misc3_code[] = {
  3, 6, 7, 8, 9, 14, 15
};

int find_misc0(char *op) {
  unsigned i;
  for(i = 0; i < sizeof(misc0_code)/sizeof(int); ++i) {
    if(strcmp(op, misc0_table[i]) == 0)
      return misc0_code[i];
  }
  return -1;
}


int find_alu4(char *op) {
  unsigned i;
  for(i = 0; i < sizeof(alu4_code)/sizeof(int); ++i) {
    if(strcmp(op, alu4_table[i]) == 0)
      return alu4_code[i];
  }
  return -1;
}

int find_misc2(char *op) {
  unsigned i;
  for(i = 0; i < sizeof(misc2_code)/sizeof(int); ++i) {
    if(strcmp(op, misc2_table[i]) == 0)
      return misc2_code[i];
  }
  return -1;
}

int find_misc3(char *op) {
  unsigned i;
  for(i = 0; i < sizeof(misc3_code)/sizeof(int); ++i) {
    if(strcmp(op, misc3_table[i]) == 0)
      return misc3_code[i];
  }
  return -1;
}


<|start_filename|>include/stdarg.h<|end_filename|>
#ifndef _UCC_STDARG_H
#define _UCC_STDARG_H

#define va_arg(ap, type)   (*((type *)(ap = (type *)ap + 1) - 1))
#define va_start(ap, arg)  (ap = &(arg) + 1)
#define va_end(ap)         ((void) 0)
typedef void *va_list;

#endif  /* stdarg.h */


<|start_filename|>usr/pwd.c<|end_filename|>
#include <sys/types.h>
#include <sys/stat.h>
#include <xv6/fs.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

int
inum(char *path)
{
  struct stat st;
  int fd;

  fd = open(path, O_RDONLY);
  if(fstat(fd, &st) < 0){
    fprintf(stderr, "pwd: cannot stat %s\n", path);
    exit(1);
  }
  close(fd);
  return st.ino;
}

void
dirent_by_inum(char *dir_path, int inum, struct dirent *res)
{
  struct dirent de;
  int dir;

  dir = open(dir_path, O_RDONLY);
  while(read(dir, &de, sizeof(de)) == sizeof(de)){
    if(de.inum == inum){
      break;
    }
  }
  close(dir);
  *res = de;
}

void
strprepend(char *dest, char *src, int n)
{
  memmove(dest + strlen(src), dest, n - strlen(src));
  memmove(dest, src, strlen(src));
}

int
main(int argc, char *argv[])
{
  char cur[256] = ".", parent[256] = "..";
  char res[256] = "";

  while(inum(cur) != inum(parent)){
    struct dirent cur_dirent;
    dirent_by_inum(parent, inum(cur), &cur_dirent);
    strprepend(res, cur_dirent.name, sizeof(res));
    strprepend(res, "/", sizeof(res));

    strcpy(cur, parent);
    strprepend(parent, "../", sizeof(parent));
  }
  if(res[0] == '\0'){
    strprepend(res, "/", sizeof(res));
  }
  printf("%s\n", res);

  exit(0);
}


<|start_filename|>exec.c<|end_filename|>
#include <sys/types.h>
#include <xv6/param.h>
#include "memlayout.h"
#include "mmu.h"
#include "proc.h"
#include "defs.h"
#include "gaia.h"

int
exec(char *path, char **argv)
{
  char *s, *last;
  int i, off;
  uint argc, sz, sp, ustack[3+MAXARG+1];
  int program_size;
  struct inode *ip;
  pde_t *pgdir, *oldpgdir;

  begin_op();
  if((ip = namei(path)) == 0){
    end_op();
    return -1;
  }
  ilock(ip);
  pgdir = 0;

  // read program header.
  if(readi(ip, (char*)&program_size, 0, sizeof(int)) < sizeof(int))
    goto bad;

  if((pgdir = setupkvm()) == 0)
    goto bad;

  // Load program into memory.
  off = HEADER_SIZE;
  if((sz = allocuvm(pgdir, 0, program_size)) == 0)
    goto bad;
  if(loaduvm(pgdir, (char*)0, ip, HEADER_SIZE, program_size) < 0)
    goto bad;
  iunlockput(ip);
  end_op();
  ip = 0;
  // Allocate two pages at the next page boundary.
  // Make the first inaccessible.  Use the second as the user stack.
  sz = PGROUNDUP(sz);
  if((sz = allocuvm(pgdir, sz, sz + 2*PGSIZE)) == 0)
    goto bad;
  clearpteu(pgdir, (char*)(sz - 2*PGSIZE));
  sp = sz;
  // Push argument strings, prepare rest of stack in ustack.
  for(argc = 0; argv[argc]; argc++) {
    if(argc >= MAXARG)
      goto bad;
    sp = (sp - (strlen(argv[argc]) + 1)) & ~3;
    if(copyout(pgdir, sp, argv[argc], strlen(argv[argc]) + 1) < 0)
      goto bad;
    ustack[3+argc] = sp;
  }
  ustack[3+argc] = 0;

  ustack[2] = sp - (argc+1)*4;  // argv pointer
  ustack[1] = argc;
  ustack[0] = sp -= (3+argc+1) * 4;  // rbp = rsp

  if(copyout(pgdir, sp, ustack, (3+argc+1)*4) < 0)
    goto bad;

  // Save program name for debugging.
  for(last=s=path; *s; s++)
    if(*s == '/')
      last = s+1;
  safestrcpy(proc->name, last, sizeof(proc->name));
  // Commit to the user image.
  oldpgdir = proc->pgdir;
  proc->pgdir = pgdir;
  proc->sz = sz;
  proc->tf->retaddr = 0;  // entry point of user programs
  proc->tf->r30 = sp;
  proc->tf->r31 = sp;
  switchuvm(proc);
  freevm(oldpgdir);
  return 0;

 bad:
  cprintf("exec bad\n");
  if(pgdir)
    freevm(pgdir);
  if(ip){
    iunlockput(ip);
    end_op();
  }
  return -1;
}


<|start_filename|>Makefile<|end_filename|>
ASMS = \
	        _entryasm.s\
	_entry.s\
	_bio.s\
	_console.s\
	_devicefile.s\
	_exec.s\
	_file.s\
	_fs.s\
	_ide.s\
	_kalloc.s\
	_log.s\
	_main.s\
	_mp.s\
	_pipe.s\
	_proc.s\
	_spinlock.s\
	_string.s\
	_swtch.s\
	_syscall.s\
	_sysfile.s\
	_syshalt.s\
	_sysproc.s\
	_timer.s\
	_trapasm.s\
	_trap.s\
	_uart.s\
	_vm.s\

NATIVECC = clang
UCCDIR = ../ucc
GAIASOFTDIR = ../gaia-software
UCCLIBS = $(UCCDIR)/lib/libucc.s

CC = $(UCCDIR)/bin/ucc
ifeq ($(wildcard $(GAIASOFTDIR)),) # if gaia-software does not exist then
  AS = $(UCCDIR)/bin/as
  SIM = $(UCCDIR)/bin/sim
else
  AS = $(GAIASOFTDIR)/asm.py
  SIM = $(GAIASOFTDIR)/sim
endif

CFLAGS = -I. -I./include
NATIVECFLAGS = $(CFLAGS)
ASFLAGS = -v -Wno-unused-label
SIMFLAGS = -stat -debug
VPATH = lib:usr:usr/as

xv6.img: kernelmemfs
	dd if=kernelmemfs of=xv6.img

initcode: initcode.S
	$(NATIVECC) $(NATIVECFLAGS) -E -o _initcode.s $<
	$(AS) -c -Wno-unused-label _initcode.s -r -e 0 -o initcode

# kernelmemfs is a copy of kernel that maintains the
# disk image in memory instead of writing to a disk.
# This is not so useful for testing persistent storage or
# exploring disk buffering implementations, but it is
# great for testing the kernel on real hardware without
# needing a scratch disk.
# We use memfs as default because our CPU architecture has no disk.
MEMFSASMS = $(filter-out _ide.s,$(ASMS)) _memide.s
kernelmemfs: $(MEMFSASMS) initcode _min-rt fs.img
	./tools/gen_binary_blobs 0x80002000 initcode _min-rt fs.img
	$(AS) $(ASFLAGS) -c -o _kernelmemfs -e 0x80002000 -start _start $(MEMFSASMS) _binary_blobs.s $(UCCLIBS) -f __UCC_HEAP_START
	./tools/gen_binary_blobs `ruby -e "print open('_kernelmemfs').size + 0x80002000"` initcode _min-rt fs.img
	$(AS) $(ASFLAGS) -c -o _kernelmemfs -e 0x80002000 -start _start $(MEMFSASMS) _binary_blobs.s $(UCCLIBS) -f __UCC_HEAP_START
	cat _kernelmemfs initcode _min-rt fs.img > kernelmemfs
	rm _kernelmemfs
	./tools/attach_boot_header kernelmemfs

tags: $(ASMS) _init
	etags *.S *.c

LIBC = lib/_libc.s lib/_usys.s
LIBM = lib/_libm.s

_%.s: %.S
	$(NATIVECC) $(NATIVECFLAGS) -E -I. -o $@ $<

_%.s: %.c
	$(CC) $(CFLAGS) -s -o $@ $<

lib/_usys.s: lib/usys.S
	$(NATIVECC) $(NATIVECFLAGS) -E -I. -o $@ $<
	sed -i "s/;/\n/g" $@

_%: _%.s $(LIBC)
	$(AS) $(ASFLAGS) -e 0 -o $@ $< $(LIBC) $(UCCLIBS) -f __UCC_HEAP_START

_sl: lib/_curses.s usr/_sl.s
	$(AS) $(ASFLAGS) -e 0 -o $@ usr/_sl.s lib/_curses.s $(LIBC) $(UCCLIBS) -f __UCC_HEAP_START
ASASMS=usr/as/_as.s usr/as/_ops.s usr/as/_parse.s usr/as/_vector.s
_as: $(ASASMS)
	$(AS) $(ASFLAGS) -e 0 -o _as $(ASASMS) $(LIBC) $(UCCLIBS) -f __UCC_HEAP_START

_min-rt: min-rt.c $(LIBC) $(LIBM)
	$(CC) $(CFLAGS) -s -o _min-rt.s min-rt.c
	$(AS) $(ASFLAGS) -e 0 -o _min-rt _min-rt.s $(LIBM) $(LIBC) $(UCCLIBS) -f __UCC_HEAP_START


mkfs: tools/mkfs.c
	gcc -Werror -Wall -o mkfs tools/mkfs.c -idirafter ./include -idirafter . -g

# Prevent deletion of intermediate files, e.g. cat.o, after first build, so
# that disk image changes after first build are persistent until clean.  More
# details:
# http://www.gnu.org/software/make/manual/html_node/Chained-Rules.html
.PRECIOUS: _%.s

UPROGS=\
	_cat\
	_echo\
	_grep\
	_init\
	_kill\
	_ln\
	_ls\
	_mkdir\
	_rm\
	_sh\
	_wc\
	_sl\
	_sed\
	_halt\
	_2048\
	_minesweeper\
	_pwd\
	_vi\
	_as\
	_ps\
# remove this to save file system size.
#_forktest\
#_stressfs\
#_zombie\
#_usertests\

fs.img: mkfs README $(UPROGS)
	./mkfs fs.img README hello.s contest.bin $(UPROGS)

-include *.d

clean:
	rm -f *.tex *.dvi *.idx *.aux *.log *.ind *.ilg \
	*.o *.d *.asm *.sym vectors.S bootblock \
	initcode initcode.out kernel xv6.img fs.img kernelmemfs mkfs \
	.gdbinit \
	$(ASMS) \
	$(ASASMS) \
	$(UPROGS) _*.s \
	lib/*.o lib/*.d lib/_*.s \
	usr/*.o usr/*.d usr/*.sym usr/*.asm usr/_*.s

sim: xv6.img
	$(SIM) $(SIMFLAGS) xv6.img
