Skip to content

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
r/dailyprogrammer [05/22/13] Challenge #125 [Intermediate] Halt! It's simulation time!
#include "halt.h"
#include "parse.h"
#include <time.h> //for rand() seeding
#include <stdlib.h>
#include <string.h>
#include <errno.h>
bool rand_bit();
void dump_registers(cpu_state *cpu);
void step(cpu_state* cpu);
int
main(int argc, char *argv[])
{
if(argc < 2) {
die("Usage: %s assembly_file\n", argv[0]);
}
cpu_state* cpu = parse_file(argv[1]);
//seeding rand()
srand(time(NULL));
while(cpu->cycles < MAX_CYCLES && !cpu->is_halted) {
step(cpu);
}
if(cpu->is_halted) {
printf("Halted after %d cycles\n", cpu->cycles);
} else {
printf("Program did not halt after %d cycles\n", MAX_CYCLES);
}
dump_registers(cpu);
free(cpu->code);
free(cpu);
return 0;
}
void
dump_registers(cpu_state *cpu)
{
int i;
printf("Register Dump: ");
for(i = 0; i < MEMORY_SIZE; i++) {
printf("%u", cpu->data[i]);
}
printf("\n");
}
cpu_state*
cpu_new(instruction* code, size_t code_size)
{
cpu_state *cpu = malloc(sizeof(*cpu));
if(!cpu) die("ERROR: Could not allocate any memory");
cpu->code = code;
cpu->code_size = code_size;
memset(cpu->data, 0, sizeof(cpu->data));
cpu->is_halted = false;
cpu->next_instruction = 0;
cpu->cycles = 0;
return cpu;
}
void
step(cpu_state* cpu)
{
#define require_cells() {assert_memcell(ins.a); assert_memcell(ins.b);}
#define require_instruction() assert_instruction(ins.a, cpu)
assert(!cpu->is_halted);
debug("Cycle number %d", cpu->cycles);
debug("Executing instruction with index %d", cpu->next_instruction);
instruction ins = cpu->code[cpu->next_instruction];
cpu->next_instruction += 1;
switch(ins.type) {
case AND:
require_cells();
debug("AND M[%d] with M[%d] to %d", ins.a, ins.b, cpu->data[ins.a] && cpu->data[ins.b]);
cpu->data[ins.a] = cpu->data[ins.a] && cpu->data[ins.b];
break;
case OR:
require_cells();
debug("OR M[%d] with M[%d] to %d", ins.a, ins.b, cpu->data[ins.a] || cpu->data[ins.b]);
cpu->data[ins.a] = cpu->data[ins.a] || cpu->data[ins.b];
break;
case XOR:
require_cells();
debug("XOR M[%d] with M[%d] to %d", ins.a, ins.b, cpu->data[ins.a] ^ cpu->data[ins.b]);
cpu->data[ins.a] = cpu->data[ins.a] ^ cpu->data[ins.b];
break;
case NOT:
require_cells();
debug("NOT M[%d] to %d\n", ins.a, !cpu->data[ins.a]);
cpu->data[ins.a] = !cpu->data[ins.a];
break;
case MOV:
require_cells();
debug("MOV %d (content of M[%d]) to M[%d]", cpu->data[ins.b], ins.b, ins.a);
cpu->data[ins.a] = cpu->data[ins.b];
break;
case SET:
assert_memcell(ins.a);
assert_value(ins.b);
debug("SET M[%d] to %d", ins.a, ins.b);
cpu->data[ins.a] = ins.b;
break;
case RANDOM:
assert_memcell(ins.a);
bool rnd = rand_bit();
debug("RANDOM value %d into M[%d]", rnd, ins.a);
cpu->data[ins.a] = rnd;
break;
case JMP:
require_instruction();
debug("JMP to instruction %d", ins.a);
cpu->next_instruction = ins.a;
break;
case JZ:
assert_instruction(ins.a, cpu);
assert_memcell(ins.b);
#ifndef NDEBUG
if(cpu->data[ins.b] == 0) {
debug("JNZ jump to %d", ins.a);
} else {
debug("JNZ no jump");
}
#endif
cpu->next_instruction = cpu->data[ins.b] == 0 ? ins.a : cpu->next_instruction;
break;
case HALT:
debug("HALT");
cpu->is_halted = true;
break;
default:
assert(0);
}
cpu->cycles += 1;
#undef require_cells
#undef require_instruction
}
bool
rand_bit()
{
return rand() % 2;
}
#ifndef __halt_h__
#define __halt_h__
#include <stdio.h>
#include <stdbool.h>
#include <assert.h>
#define MEMORY_SIZE 32
#define MAX_CYCLES 100000
#ifdef NDEBUG
#define debug(...)
#else
#define debug(m, ...) fprintf(stderr,m "\n", ##__VA_ARGS__)
#endif
#define die(...) {printf(__VA_ARGS__); exit(1);}
#define assert_memcell(cell) assert((cell) < 32)
#define assert_instruction(instruction, cpu_p) assert((instruction) <= ((cpu_p)->code_size))
#define assert_value(val) assert((val) == 0 || (val) == 1)
typedef unsigned int value;
typedef unsigned int memory_location;
typedef struct {
char* data;
size_t len;
} buffer;
typedef enum {
AND, //M[a] = M[a] bit-wise and M[b]
OR, //M[a] = M[a] bit-wise or M[b]
XOR, //M[a] = M[a] bit-wise xor M[b]
NOT, //M[a] = bit-wise not M[a]
MOV, //M[a] = bit-wise M[b]
SET, //M[a] = c
RANDOM, //M[a] = random value (0 or 1; equal probability distribution)
JMP, //Start executing instructions at index x
JZ, //Start executing instructions at index x if M[a] == 0
HALT //Halts the program
} instruction_type;
typedef struct {
instruction_type type;
value a;
value b;
} instruction;
typedef struct {
instruction* code;
size_t code_size;
value data[MEMORY_SIZE];
memory_location next_instruction;
bool is_halted;
unsigned int cycles;
} cpu_state;
cpu_state* cpu_new(instruction* code, size_t code_size);
#endif
#include "parse.h"
#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#define current_char(p) (p)->buf.data[(p)->cur]
#define next_char(p) (p)->cur++;
#define skip(p, n) (p)->cur += (n);
#define end_of(p) ((p)->cur > (p)->buf.len)
#define parsing_error(m, ...) {fprintf(stderr, "PARSING ERROR: " m "\n", ##__VA_ARGS__); exit(1);}
#define assert_not_eof(p) if( end_of((p)) ) { \
parsing_error("Unexpected EOF");\
}
#define next_char_req(p) {next_char(p); assert_not_eof(p);}
cpu_state* parse_file(char* file_name);
buffer load_file(char* file_name);
cpu_state* parse_assembly(buffer assembly);
void skip_whitespaces(parser_state* p);
void require_whitespace(parser_state* p);
void require_line_ending(parser_state* p);
unsigned int parse_int(parser_state* p);
memory_location parse_memory_location(parser_state* p);
value parse_value(parser_state* p);
unsigned int parse_code_location(parser_state *p);
bool is_digit(char c);
void parse_instruction(parser_state* p, instruction* inst);
instruction_type parse_instruction_type(parser_state* p);
cpu_state* parse_file(char* file_name)
{
buffer buf = load_file(file_name);
cpu_state *cpu = parse_assembly(buf);
free(buf.data);
return cpu;
}
buffer
load_file(char* file_name)
{
FILE *file;
buffer buf;
file = fopen(file_name, "r");
if(!file) {
fprintf(stderr, "ERROR: Could not open file %s", file_name);
exit(1);
}
//get file length
fseek(file, 0, SEEK_END);
buf.len = ftell(file) + 1;
fseek(file, 0, SEEK_SET);
//Allocate memory
buf.data = malloc(buf.len);
if (!buf.data)
{
fprintf(stderr, "Could not allocate memory");
fclose(file);
exit(1);
}
fread(buf.data, buf.len, 1, file);
fclose(file);
return buf;
}
cpu_state*
parse_assembly(buffer assembly)
{
int i;
parser_state p = {assembly, 0, 0};
//first element in the file is the number of instructions
int num_instructions = parse_int(&p);
debug("parsed num_instructions: %d", num_instructions);
instruction *instructions = malloc(sizeof(*instructions) * num_instructions);
if(!instructions) die("ERROR: Could not allocate memory");
p.num_instructions = num_instructions;
skip_whitespaces(&p);
for(i=0; i < num_instructions; i++) {
debug("parsing instruction no. %d", i);
parse_instruction(&p, &instructions[i]);
}
return cpu_new(instructions, num_instructions*sizeof(instruction));
}
void
skip_whitespaces(parser_state* p)
{
while(!end_of(p) && current_char(p) == ' ') {
next_char(p);
}
}
void
require_whitespace(parser_state* p)
{
position cur = p->cur;
skip_whitespaces(p);
if(cur == p->cur) {
parsing_error("Expected Whitespace");
}
}
void
require_line_ending(parser_state* p)
{
if(!(current_char(p) == '\r' || current_char(p) == '\n') ) {
parsing_error("Expected line ending");
}
while(!end_of(p) && (current_char(p) == '\r' || current_char(p) == '\n') ) {
next_char(p);
}
}
unsigned int
parse_int(parser_state* p)
{
unsigned int parsed = 0;
assert_not_eof(p);
if(!is_digit(current_char(p))) {
parsing_error("Expected Integer, found '%c'", current_char(p));
}
while(!end_of(p) && is_digit(current_char(p))) {
parsed = (parsed * 10) + (current_char(p) - '0');
next_char(p);
}
return parsed;
}
memory_location
parse_memory_location(parser_state* p)
{
int mem_loc = parse_int(p);
if(mem_loc > MEMORY_SIZE) {
parsing_error("Found reference to memory cell %d, but memory is only %d cells big", mem_loc, MEMORY_SIZE);
}
return mem_loc;
}
value
parse_value(parser_state* p)
{
unsigned int val = parse_int(p);
if(val > 1) {
parsing_error("Found value %d, possible values are 0 and 1", val);
}
return val;
}
unsigned int
parse_code_location(parser_state *p)
{
unsigned int val = parse_int(p);
if(val > p->num_instructions) {
parsing_error("Found jump to %u, but there are only %zu instructions", val, p->num_instructions);
}
return val;
}
bool
is_digit(char c)
{
return c >= '0' && c <= '9';
}
void
parse_instruction(parser_state* p, instruction* inst)
{
inst->a = inst->b = 0;
assert_not_eof(p);
//parse away the line ending of the instruction before that instruction
require_line_ending(p);
inst->type = parse_instruction_type(p);
skip_whitespaces(p);
switch(inst->type) {
case AND:
case OR:
case XOR:
case MOV:
inst->a = parse_memory_location(p);
debug("parsed inst->a %d", inst->a);
require_whitespace(p);
inst->b = parse_memory_location(p);
debug("parsed inst->b %d", inst->b);
break;
case NOT:
case RANDOM:
inst->a = parse_memory_location(p);
debug("parsed inst->a %d", inst->a);
break;
case SET:
inst->a = parse_memory_location(p);
debug("parsed inst->a %d", inst->a);
require_whitespace(p);
inst->b = parse_value(p);
debug("parsed inst->b %d", inst->b);
break;
case JMP:
inst->a = parse_code_location(p);
debug("parsed inst->a %d", inst->a);
break;
case JZ:
inst->a = parse_code_location(p);
debug("parsed inst->a %d", inst->a);
require_whitespace(p);
inst->b = parse_memory_location(p);
debug("parsed inst->b %d", inst->b);
break;
case HALT:
//do nothing
break;
}
}
instruction_type
parse_instruction_type(parser_state* p)
{
assert_not_eof(p);
//exploting the fact that only JMP and JZ start with the same letter
//leads to the unintended behavior that AND and things like AWS work equally well
switch(current_char(p)) {
case 'A':
skip(p,3);
return AND;
break;
case 'O':
skip(p,2);
return OR;
break;
case 'X':
skip(p, 3);
return XOR;
break;
case 'N':
skip(p, 3);
return NOT;
break;
case 'M':
skip(p, 3);
return MOV;
break;
case 'S':
skip(p, 3);
return SET;
break;
case 'R':
skip(p, 6);
return RANDOM;
break;
case 'J':
next_char_req(p);
switch(current_char(p)) {
case 'M':
skip(p, 2); //we only have to skip M and P
return JMP;
break;
case 'Z':
skip(p, 1); //equally, we only must skip the Z
return JZ;
break;
default:
parsing_error("Unexpected character after J (Expected M or Z)");
}
break;
case 'H':
skip(p, 4);
return HALT;
break;
default:
parsing_error("Expected Instruction");
}
}
#ifndef __parse_h__
#define __parse_h__
#include "halt.h"
typedef size_t position;
typedef struct {
buffer buf;
position cur;
size_t num_instructions;
} parser_state;
cpu_state* parse_file(char* file_name);
#endif
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.