/* * 13-Jan-03 * * RCS: $Id: simulate.c,v 1.1 1998/04/21 13:19:24 kenmac Exp $ * sim-base: instruction-level simulator for LC-2200 */ /****************************************************************************\ * * * The LC is a 32-bit computer with 16 general registers plus a separate * * program counter (PC) register. All addresses are word addresses. * * Register 0 is wired to zero: it always reads as zero and writes to it * * are ignored. * * * * ----------------------------------------------------------------- * * Instruction Formats * * ----------------------------------------------------------------- * * There are four instruction formats. Bit 0 is the least-significant: * * * * R-type instructions (add, nand): * * bits 31-28: opcode * * bits 27-24: reg A * * bits 23-20: reg B * * bits 19-4: unused (should be all 0s) * * bits 3-0: reg DST * * * * I-type instructions (addi, lw, sw, beq): * * bits 31-28: opcode * * bits 27-24: reg A * * bits 23-20: reg B * * bits 19-0: OFFSET (a 20-bit, 2s complement number with a range * * of -524288 to +524287 * * * * J-type instructions (jalr): * * bits 31-28: opcode * * bits 27-24: reg A * * bits 23-20: reg B * * bits 19-0: unused (should be all 0s) * * * * O-type instructions (halt, noop): * * bits 31-28: opcode * * bits 27-0: unused (should be all 0s) * * * * ----------------------------------------------------------------- * * Assembly Syntax * * ----------------------------------------------------------------- * * Registers indicated with a '$' sign. The register names in assembly * * are according to their use in the assembly convention: * * * * regno name use callee-save * * ----- ---- ------------------------- ----------- * * 0 $zero always zero (by hardware) n.a. * * 1 $at reserved for assembler n.a. * * 2 $v0 return value no * * 3 $a0 argument or temporary no * * 4 $a1 argument or temporary no * * 5 $a2 argument or temporary no * * 6 $a3 argument or temporary no * * 7 $a4 argument or temporary no * * 8 $s0 saved register YES * * 9 $s1 saved register YES * * 10 $s2 saved register YES * * 11 $s3 saved register YES * * 12 $k0 reserved for OS/traps n.a. * * 13 $sp stack pointer YES * * 14 $fp frame pointer YES * * 15 $ra return address YES * * * * ----------------------------------------------------------------- * * Description of Machine Instructions * * ----------------------------------------------------------------- * * Assembly language Opcode in binary Action * * name for instruction (bits 31/30/29/28) * * ----------------------------------------------------------------- * * add (R-type format) 0000 add contents of A with * * ex: add $v0, $a0, $a1 contents of B, store results in * * DST. Ex: $v0 := $a0 + $a1 * * * * nand (R-type format) 0001 nand contents of A with * * ex: nand $v0, $a0, $a1 contents of B, store results in * * DST. Ex: $v0 := ~($a0 & $a1) * * * * addi (I-type format) 0010 Add OFFSET to the contents of A * * ex: addi $v0, $a0, 25 and store the result in B. * * Ex: $v0 := $a0 + 25 * * * * lw (I-type format) 0011 load B from memory. The memory * * ex: lw $v0, 0x42($fp) address is formed by adding * * OFFSET to the contents of A. * * Ex: $v0 := memory[$fp + 0x42] * * * * sw (I-type format) 0100 store B into memory. The memory * * ex: sw $a0, 0x42($fp) address is formed by adding * * OFFSET to the contents of A. * * Ex: memory[$fp + 0x42] := $a0 * * * * beq (I-type format) 0101 compare the contents of A and B. * * ex: beq $a0, $a1, done If they are the same, then * * branch to the address * * PC+1+OFFSET, where PC is the * * address of the beq instruction. * * Ex: if ($a0 == $a1) * * PC := PC+1+OFFSET * * * * *** NOTE *** * * * * For programmer convenience (and * * implementor confusion), the * * assembler *computes* the OFFSET * * value from the number or symbol * * given in the instruction and the * * assemblers idea of the PC. In the * * example, the assembler stores * * done-(PC+1) in OFFSET so that * * the machine will branch to label * * "done" at run time. * * * * jalr (J-type format) 0110 First store PC+1 into B, * * ex: jalr $at, $ra where PC is the address of the * * jalr instruction. Then branch to * * the address now contained in A. * * Note that if A is the same as B, * * the processor will first store * * PC+1 into that register, then end * * up branching to PC+1. * * Ex: $ra := PC+1; PC := $a0 * * * * halt (O-type format) 0111 halt the machine: i.e. do nothing * * ex: halt and let the simulator notice that * * the machine halted. * * * * noop (pseudo-op) n.a. No operation: does nothing (actually * * ex: noop Emits "add $zero, $zero, $zero") * * * * .word (pseudo-op) n.a. fill word with a value. * * ex: .word 32 Ex: fill the current location * * .word fib with the 32-bit represenation of * * the number "32" or the value of * * the symbol "fib". * * * \****************************************************************************/ #include #include /* strtol() */ #include /* strtok() */ #include /* index() */ #include #define MAXLINELEN 1024 #define MEMORY_SIZE 0x10000 /* 64K words */ #define COMMENTCHAR '!' /* comments between ! and end-of-line */ /* * memory mapped I/O: block of MEMORY_SIZE words at the bottom plus * a DISPLAY_SIZE memory-mapped display starting at address * DISPLAY_BASE. The lower bits of each word are intepreted as a character * to display (in print_state()). */ #define DISPLAY_BASE 0xf0000000 /* address of display */ #define DISPLAY_ADDRBITS 6 /* 6 bits --> 64 words */ #define DISPLAY_SIZE (1 << DISPLAY_ADDRBITS) /* * 1. representation of a single instruction & selector functions */ #define OP_BITS 4 /* 4-bit opcodes */ #define REG_BITS 4 /* 16 registers */ #define OFFSET_BITS 20 /* 20-bit signed offset */ #define OP_OFFSET 28 /* position in the instruction word */ #define A_OFFSET 24 #define B_OFFSET 20 #define DST_OFFSET 0 #define OFFSET_OFFSET 0 #define NOPS (1 << OP_BITS) /* i.e. 16 */ #define NREGS (1 << REG_BITS) /* i.e. 16 */ #define OP_ADD 0 /* opcodes */ #define OP_NAND 1 #define OP_ADDI 2 #define OP_LW 3 #define OP_SW 4 #define OP_BEQ 5 #define OP_JALR 6 #define OP_HALT 7 static char *register_names[NREGS] = { "$zero", /* 0 */ "$at", /* 1 */ "$v0", /* 2 */ "$a0", /* 3 */ "$a1", /* 4 */ "$a2", /* 5 */ "$a3", /* 6 */ "$a4", /* 7 */ "$s0", /* 8 */ "$s1", /* 9 */ "$s2", /* 10 */ "$s3", /* 11 */ "$k0", /* 12 */ "$sp", /* 13 */ "$fp", /* 14 */ "$ra" /* 15 */ }; /* * 2. machine model in static variables. */ static int registers[NREGS]; static int memory[MEMORY_SIZE]; static int display[DISPLAY_SIZE]; /* memory-mapped alphanumeric display */ static int memused = 0; /* highest value written */ static int pc = 0; static int cycle = 0; /* cycle number (= instruction number) */ /* * cute hack: a number encoding which memory or register changed. The * number is either a positive memory address or a negative number * encoding the register number. Out of range numbers mean nothing changed. * see print_state() */ #define NOTCHANGED MEMORY_SIZE #define DISPLAYCHANGED (MEMORY_SIZE + 1) #define MEMCHANGED(x) (x) #define REGCHANGED(x) (- ((x) + 1)) static int changed = NOTCHANGED; /**************************************************************************\ * * * Print_state dumps the machine state The state display is animated * * with two pointers: * * * * 1. The position of the PC is indicated with a "<-PC" flag. * * 2. The last memory/register item changed is indicated with a "<--" * * flag. This animation requires the cooperation of the simulator * * to set the "changed" variable as follows: * * * * changed = MEMCHANGED(n) if memory[n] was written (= n) * * changed = REGCHANGED(n) if registers[n] was written (= -(n+1)) * * changed = NOTCHANGED if nothing written (= out of range) * * * \**************************************************************************/ static void print_state(void) { int limit = (memused > NREGS + 6 ? memused : NREGS + 6); char memstring[64]; char regstring[64]; int index, kount; printf("----------------------------------------------------------------\n"); printf("Instr = %-10d PC = 0x%04X\n", cycle, pc); printf("Memory: Registers:\n"); for (index = 0; index < limit; index++) { /* * 1. left side of the picture: memory or nothing */ if (index < memused) sprintf(memstring, "0x%04X = 0x%08X %s%s", index, memory[index], (changed == MEMCHANGED(index)) ? "<--" : " ", (pc == index) ? "<- PC" : " "); else strcpy(memstring, " "); /* * 2. right side of the picture: registers, display or nothing */ if (index < NREGS) sprintf(regstring, " %5s = 0x%08X %s", register_names[index], registers[index], (changed == REGCHANGED(index)) ? "<--" : " "); else if (index == NREGS + 1) strcpy(regstring, " Display:"); else if (index > NREGS + 1 && index <= NREGS + 5) { strcpy(regstring, " |................|"); for (kount = 0; kount < 16; kount++) { int blah = display[(index - (NREGS + 2)) * 16 + kount]; if (blah >= 32 && blah < 0x7f) regstring[kount + 10] = blah; } } else regstring[0] = '\0'; /* * 3. print the two sides */ printf("%s%s\n", memstring, regstring); } printf("----------------------------------------------------------------\n"); } /**************************************************************************\ * * * Handy routines to check memory addresses for range violations. Writes * * are allowed anywhere inside the memory array. Reads are required to * * be inside the "memused" range, which also has the effect of helping to * * check for reads of locations that have not yet been written. * * * * Returns 1 if okay, else 0. * * * \**************************************************************************/ static int check_read_address(int address, char *name) { if (!(address >= 0 && address < memused)) { printf("%s: read address of 0x%08X is out of 0 to %d\n", name, address, memused); return(0); } return(1); } static int check_write_address(int address, char *name) { if (!((address >= 0 && address < MEMORY_SIZE) || (address >= DISPLAY_BASE && address < DISPLAY_BASE + DISPLAY_SIZE))) { printf("%s: read address of 0x%08X is out of 0 to %d\n", name, address, memused); return(0); } return(1); } /*************************************************************************\ * * * The simulator needs to extract bit fields from the machine code * * instructions. Since these extractions are all similar, here are some * * selector functions for bit fields. * * * \*************************************************************************/ static int selector_unsigned(int machinecode, int offset, int bits) { int mask = (1 << bits) - 1; /* 1 in each bit of the bitfield */ int result; result = (machinecode >> offset) & mask; return(result); } static int selector_signed(int machinecode, int offset, int bits) { int mask = (1 << bits) - 1; /* a 1 in each bit of the bitfield */ int signmask = mask & ~(mask >> 1); /* a 1 in the sign (top) bit only */ int result; result = (machinecode >> offset) & mask; if (result & signmask) /* if the sign bit is a 1 */ result = result | ~mask; /* then set _all_ upper bits to 1 */ return(result); } #define selector_OP(x) selector_unsigned(x, OP_OFFSET, OP_BITS) #define selector_A(x) selector_unsigned(x, A_OFFSET, REG_BITS) #define selector_B(x) selector_unsigned(x, B_OFFSET, REG_BITS) #define selector_DST(x) selector_unsigned(x, DST_OFFSET, REG_BITS) #define selector_OFFSET(x) selector_signed(x, OFFSET_OFFSET, OFFSET_BITS) /**************************************************************************\ * * * Here's the guts of the simulator. The driver loop * * fetches-decodes-executes each instruction and performs the appropriate * * housekeeping. * * * \**************************************************************************/ static void driver(int quiet) { int machinecode; int a, b, op, dst, offset; int address; while (1) { /* * fetch instruction */ if (!check_read_address(pc, "fetch")) break; machinecode = memory[pc]; pc = pc + 1; /* * decode instruction */ op = selector_OP(machinecode); a = selector_A(machinecode); b = selector_B(machinecode); dst = selector_DST(machinecode); offset = selector_OFFSET(machinecode); /* * execute instruction */ switch (op) { case OP_ADD: registers[dst] = registers[a] + registers[b]; changed = REGCHANGED(dst); break; case OP_NAND: registers[dst] = ~(registers[a] & registers[b]); changed = REGCHANGED(dst); break; case OP_ADDI: registers[b] = registers[a] + offset; changed = REGCHANGED(b); break; case OP_LW: address = registers[a] + offset; if (!check_read_address(address, "lw")) return; registers[b] = memory[address]; changed = REGCHANGED(b); break; case OP_SW: address = registers[a] + offset; if (!check_write_address(address, "sw")) return; if ((unsigned int)address < MEMORY_SIZE) { memory[address] = registers[b]; changed = MEMCHANGED(address); if (address >= memused) memused = address + 1; } else if ((unsigned int)address >= DISPLAY_BASE) { display[address - DISPLAY_BASE] = registers[b]; changed = DISPLAYCHANGED; } break; case OP_BEQ: address = offset + pc; /* (PC has already been incremented) */ if (!check_read_address(address, "beq")) return; if (registers[a] == registers[b]) pc = address; changed = NOTCHANGED; break; case OP_JALR: registers[b] = pc; /* first store PC+1 into regB */ registers[0] = 0; /* force R0 to be zero if it was the target */ address = registers[a]; if (!check_read_address(address, "beq")) return; pc = address; changed = REGCHANGED(b); break; case OP_HALT: /* printf("halt: normal exit\n"); */ changed = NOTCHANGED; cycle = cycle + 1; return; default: printf("bogus: bad instruction 0x%08x at PC %d\n", machinecode, pc); changed = NOTCHANGED; return; /* always halt */ } /* [end of switch on op] */ /* * housekeeping */ registers[0] = 0; /* force R0 to be zero */ cycle = cycle + 1; if (!quiet || changed == DISPLAYCHANGED) print_state(); } /* [end of big while loop] */ } /* [end of driver()] */ /*********************************************************\ * * * hextoi(), since strtoul() is apparently not portable. * * * \*********************************************************/ static int hextoi(char *string) { int number = 0; int index; /* * if it does NOT look like a hex number, assume decimal and use atoi. */ if (!(string[0] == '0' && (string[1] == 'x' || string[1] == 'X'))) return(atoi(string)); /* * otherwise, read a hex number. */ for (index = 2; string[index] != '\0'; index++) { char blah = string[index]; int digit; if (blah >= '0' && blah <= '9') digit = blah - '0'; else if (blah >= 'A' && blah <= 'F') digit = blah - 'A' + 10; else if (blah >= 'a' && blah <= 'f') digit = blah - 'a' + 10; else break; number = number * 16 + digit; } return(number); } /******************************************\ * * * poweron_reset initializes the machine. * * * \******************************************/ static void power_on_reset(int argc, char *argv[]) { char line[MAXLINELEN]; char *filename; FILE *input; int index; /* * open the filename. */ filename = argv[1]; input = fopen(filename, "r"); if (input == NULL) { fprintf(stderr, "Unable to open '%s' for read\n", filename); exit(1); } /* * 1. Init all registers to zero, then initialize registers $a0 ... * with numbers from the extra arguments, if any. */ for (index = 0; index < NREGS; index++) registers[index] = 0; for (index = 1; index < argc - 1; index++) registers[index + 2] = hextoi(argv[index + 1]); /* * 2. As a debugging aid, set unused memory to an obviously bogus value. * Then init the bottom of memory from the input file. */ for (index = 0; index < MEMORY_SIZE; index++) memory[index] = 0xdeadbeef; for (index = 0; fgets(line, MAXLINELEN, input); ) if (line[0] >= '0' && line[0] <= '9') memory[index++] = hextoi(line); memused = index; /* * 3. init PC, cycle count, "changed" variable for print_state() */ pc = 0; cycle = 0; changed = NOTCHANGED; fclose(input); } /*****************\ * * * main program. * * * \*****************/ int main(int argc, char *argv[]) { int quiet = 0; /* * read the filename argument and open it. */ if (argc < 2) { fprintf(stderr, "Usage: %s [-q] [ ...]\n", argv[0]); fprintf(stderr, " Reads LC machine code from the named\n"); fprintf(stderr, " file. Initialize registers $a0 ... n with\n"); fprintf(stderr, " arg0 ... n if present. Runs the program and\n"); fprintf(stderr, " dumps state to stdout. With the -q argument,\n"); fprintf(stderr, " dumps only initial and final states.\n"); return(1); } if (!strcmp(argv[1], "-q")) { quiet = 1; argc--; argv++; } /* * initialize the machine */ power_on_reset(argc, argv); /* * simulate the program */ print_state(); /* initial state */ driver(quiet); print_state(); /* final state */ /* * success! */ return(0); }