Virtual Machine implementation problem, Please help me to spot the bug

[weidongtom]

Hi,

I tried to implement the Universal Machine as described in
http://www.boundvariable.org/task.shtml, and I managed to get one
implemented (After looking at what other's have done.) But when I use
to run a UM program, I kept on getting error messages. I have used
someone else's implementation and it runs fine. I have compared my
code with other's and I still can't figure it out what's wrong with
mine. So please help me out, after 3 days of debugging I don't think I
can ever make it. Here's my implementation. Thanks in advance.

#include <stdio.h> //printf(), putchar(), fprintf(), fread(),
fputchar(), strerror()
#include <string.h> //memcpy, memset
#include <stdlib.h> //malloc()
#include <errno.h> //errno
#include <sys/stat.h> //stat()

//internal data
typedef unsigned int u32;
typedef unsigned char u8;

//debug macros
#define DUMP_FILE_NAME "memory.dmp"
//#define PRINT_DEBUG_MSG
//#define DUMP_MEMORY
#ifdef PRINT_DEBUG_MSG
#define dprintf(x,...) printf(x,...)
#else
#define dprintf(x,...)
#endif

//decode macros
#define REG_A(codex) ((codex >6) & 7)
#define REG_B(codex) ((codex >3) & 7)
#define REG_C(codex) (codex & 7)
#define OPCODE(codex) ((codex >28) & 15)
#define SPEC_A(codex) ((codex >25) & 7)
#define SPEC_V(codex) (codex & 0x0fffffffL)
//opcodes
#define OP_CMOV 0
#define OP_INDEX 1
#define OP_AMAND 2
#define OP_ADD 3
#define OP_MUL 4
#define OP_DIV 5
#define OP_NAND 6
#define OP_HALT 7
#define OP_ALLOC 8
#define OP_FREE 9
#define OP_OUT 10
#define OP_IN 11
#define OP_LOAD 12
#define OP_ORTHO 13

//32 bit Universal Machine cpu struct
typedef struct UM32_{
u32 finger;
u32 r[8];
u32* program;
}UM32;

/*Change local small-endian to UM's internal big-endian
* ###require more work for portability
* this is to replace the inet/arpa.h's ntohl()
* ###
*/
void change_endian(u32* value){
u8 tmp1[4], tmp2[4];
memcpy((u32 *)tmp1, value, sizeof(u32));
tmp2[0] = tmp1[3];
tmp2[1] = tmp1[2];
tmp2[2] = tmp1[1];
tmp2[3] = tmp1[0];
memcpy(value, (u32 *)tmp2, sizeof(u32));
}

/* A wrapper for malloc() in stdlib.h */
void *my_malloc(size_t size){
void *tmp = malloc(size);
if(tmp != NULL)
return tmp;
else{
fprintf(stderr, "Falied in my_malloc() in attempt to allocate memory
of size: %d.\n",
size);
exit(1);
}
}

/* Create an array with size size+1,
* where array[-1] is used for holding the size of the array
* return a 32 bit arrayID (currently implemented as it's address)
*/
u32 create_array(u32 size){
u32 *tmp = (u32*)my_malloc(sizeof(u32)*size+1);
memset(tmp+1, 0, sizeof(u32)*size);
*tmp = size;
return (u32)(tmp+1);
}

#define GET_ARRAY_SIZE(arrayID) (*((u32*)(arrayID-1)))
#define ARRAY(arrayID) ((u32*)(arrayID))
#define WHOLE_ARRAY(arrayID) ((u32*)(arrayID)-1)

/* Delete an array created with create_array()*/
void delete_array(u32 arrayID){
free(WHOLE_ARRAY(arrayID));
}

/* Duplicate the content in from to that of to.
* original data in to is discarded.
*/
void copy2array0(UM32 *um, u32 src){
int size = (u32)GET_ARRAY_SIZE(src);
if(!(um->program))
free(um->program);
um->program = (u32*)my_malloc(sizeof(u32)*size+1);
memcpy(um->program, WHOLE_ARRAY(src), size+1);
um->program++;
}

void load_program(u32** membuffer, const char* filename){
int i, size_read, file_size, membuffer_size;
struct stat file_info;
FILE *infile;

//Find file info
if(stat(filename, &file_info)){
fprintf(stderr, "Failed to stat file: %s. %s\n", filename,
strerror(errno));
exit(1);
}
file_size = file_info.st_size;

//Open file
dprintf("Opening file: %s ...", filename);
infile = fopen(filename, "rb");
if(infile == NULL){
fprintf(stderr, "Failed to open file: %s. %s\n", filename,
strerror(errno));
exit(1);
}
dprintf("done\n");

//Read buffer
dprintf("Reading file content with size: %d ...", file_size);
membuffer_size = sizeof(u8)*file_size/sizeof(u32);
if(!(*membuffer))
free((*membuffer));
//(*membuffer) = (u32*)my_malloc(sizeof(u32)*membuffer_size);
(*membuffer) = (u32*)create_array(membuffer_size);
size_read = fread((*membuffer), sizeof(u8), file_size,infile);
fclose(infile);
if(size_read != file_size && !feof(infile)){
fprintf(stderr, "Warning: failed to read all data.\n");
}
dprintf("done.\n");

//change the endian
dprintf("Changing small-endian data to big_endian ...\n");
for(i = 0; i < membuffer_size; i++){
dprintf(" %08x->", (*membuffer)[i]);
change_endian(&(*membuffer)[i]);
dprintf("%08x", (*membuffer)[i]);
if((i+1)%4 == 0)
dprintf("\n");
}
dprintf("\ndone.\n");
dprintf("Program of size: %d loaded.\n",
(*((*membuffer)-1))*sizeof(u32));
}

void init_um32(UM32* um, u32* program){
int i;
dprintf("Initializing the Universal Machine ...");
if(program == NULL){
fprintf(stderr, "Fatal Error in init_um32, program is NULL.\n");
exit(1);
}
dprintf("\nRegisters:");
for(i=0;i<8;i++){
um->r[i] = 0;
dprintf(" %08x", um->r[i]);
}
um->finger = 0;
um->program = program;
dprintf("\nfinger = %08x\nprogram loaded at %08x\n", um->finger,
(u32)um->program);
dprintf("done.\n");
}

void dump_memory(u32 *mem){
FILE *outfile = NULL;
int i;
if(mem == NULL){
fprintf(stderr, "UM Memory is null.\n");
exit(1);
}
outfile = fopen(DUMP_FILE_NAME, "w");
dprintf("Beginning memory dump of size: %d...\n", *(mem-1));
if(!outfile){
fprintf(stderr, "Error in dump_memory. Failed to open file: %s.
%s",
DUMP_FILE_NAME, strerror(errno));
exit(1);
}
for(i=0;i<*(mem-1); i++){
fprintf(outfile, " %08x", mem[i]);
if((i+1)%8 == 0)
fprintf(outfile, "\n");
}
dprintf("Done.\n");
fclose(outfile);
}

int bound_program(UM32 um, u32 index){
if(index *(um.program-1))
return 1;
return 0;
}

int bound_array(u32 arrayID, u32 index){
if(!ARRAY(arrayID) || index GET_ARRAY_SIZE(arrayID))
return 1;
return 0;
}

/* Execute one instruction
* return 1 on success
*/
#define R(a) um->r[a]
#define PROGRAM (um->program)
#define FINGER (um->finger)
int um_run(UM32 *um, int trace){
u8 opcode;
u32 a, b, c, codex;

if(bound_program(*um, FINGER)){
printf("Array Index out of bound.\n");
exit(1);
}
codex = PROGRAM[FINGER++];
opcode = OPCODE(codex);
a = REG_A(codex);
b = REG_B(codex);
c = REG_C(codex);

if(trace)
printf("\ncodex=%08x, opcode=%d, finger=%08x\n", codex, opcode,
FINGER);

if(opcode == OP_ORTHO){
a = SPEC_A(codex);
R(a) = SPEC_V(codex);
if(trace){
printf("OP_ORTHO, r[%d]=%u\n", a, R(a));
printf("registers: %08x, %08x, %08x, %08x, %08x, %08x, %08x, %08x
\n",
R(0), R(1), R(2), R(3), R(4), R(5), R(6), R(7));
}
return 1;
}
switch(opcode){
case OP_CMOV:
if(!R(c)){
R(a) = R(b);
if(trace){
printf("OP_CMOV, r[%d]=r[%d]=%08x\n", a, b, R(a));
}
}
break;
case OP_INDEX:
if(!R(b)){
if(bound_program(*um, R(c))){
printf("Index out of bound in accessing array0 at offset %08x\n",
R(c));
exit(0);
}
R(a) = PROGRAM[R(c)];
}
else{
if(bound_array(R(b), R(c))){
printf("Index out of bound in accessing array%d\n", R(b));
exit(1);
}
R(a) = ARRAY(R(b))[R(c)];
}
if(trace)
printf("OP_INDEX, r[%d]=array[%d][%d]=%08x\n", a, b, c, R(a));
break;
case OP_AMAND:
if(!R(a)){
if(bound_program(*um, R(b))){
printf("Index out of bound in accessing array0 at offset %08x\n",
R(c));
exit(0);
}
PROGRAM[R(b)] = R(c);
}
else{
if(bound_array(R(a), R(b))){
printf("Index out of bound in accessing array%d\n", R(b));
exit(1);
}
ARRAY(R(a))[R(b)] = R(c);
}
if(trace)
printf("OP_AMAND, array[%d][%d]=r[%d]=%08x\n", a, b, c, R(c));
break;
case OP_ADD:
R(a) = R(b) + R(c);
if(trace)
printf("OP_ADD, r[%d]=r[%d]+r[%d]=%08x\n", a, b, c, R(a));
break;
case OP_MUL:
R(a) = R(b) * R(c);
if(trace)
printf("OP_ADD, r[%d]=r[%d]*r[%d]=%08x\n", a, b, c, R(a));
break;
case OP_DIV:
R(a) = R(b) / R(c);
if(trace)
printf("OP_ADD, r[%d]=r[%d]/r[%d]=%08x\n", a, b, c, R(a));
break;
case OP_NAND:
R(a) = ~(R(b) & R(c));
if(trace)
printf("OP_ADD, r[%d]=~(r[%d]&r[%d])=%08x\n", a, b, c, R(a));
break;
case OP_HALT:
if(trace)
printf("OP_HALT, stopping program ... done.\n");
return 0;
break;
case OP_ALLOC:
R(b) = create_array(R(c));
if(trace)
printf("OP_ALLOC, r[%d]=create_array(r[%d])=%08x\n", b, c, R(b));
break;
case OP_FREE:
delete_array(R(c));
R(c) = 0;
if(trace)
printf("OP_REE, free(r[%d]=%08x)\n", c, R(c));
break;
case OP_OUT:
if(R(c) < 256){
putchar(R(c));
if(trace)
printf("OP_OUT, putchar(r[%d]=%08x)\n", c, R(c));
}
else
fprintf(stdout, "Warning, failed to output value %08x as char.\n",
R(c));
break;
case OP_IN:
R(c)=getchar();
if(trace)
printf("OP_IN, r[%d]=getchar()=%08x", c, R(c));
break;
case OP_LOAD:
if(R(b) != 0)
copy2array0(um, R(b));
FINGER = R(c);
if(trace){
printf("OP_LOAD, loading program into array0 from array[%d] at %08x
\n",
b, R(b));
printf("\tfinger=%08x\n", FINGER);
}
break;
default:
printf("Fatal Error: Bad opcode=%d, codex=%08x\n", opcode, codex);
return 0;
break;
}
if(trace)
printf("registers: %08x, %08x, %08x, %08x, %08x, %08x, %08x, %08x
\n",
R(0), R(1), R(2), R(3), R(4), R(5), R(6), R(7));
return 1;
}

int main(int argc, char *argv[]){
UM32 um;
u32 *program;
int run;

#ifndef NOT_GDB
argc = 2;
argv[1] = "sandmark.umz";
#endif
if(argc < 2){
printf("Usage: %s filename\n", argv[0]);
exit(0);
}
//load program
load_program(&program, argv[1]);
//initialize um
init_um32(&um, program);
#ifdef DUMP_MEMORY
dump_memory(program);
#endif
do{
run = um_run(&um, 1);
}while(run);
return 0;
}

[Jens Thoms Toerring]

we********@gmail.com <we********@gmail.comwrote:

I tried to implement the Universal Machine as described in
http://www.boundvariable.org/task.shtml, and I managed to get one
implemented (After looking at what other's have done.) But when I use
to run a UM program, I kept on getting error messages.

That's not a problem description. What kind of error messages?
Do you get them during compilation or at runtime? And what kind
of error messages?

I just had the usual look at places where malloc() etc. is used
and, voila, there are already things going horribly wrong.
Looking at more of the code before you correct that and tell
what kind of error messages you got doesn't make any sense.

/* Create an array with size size+1,
* where array[-1] is used for holding the size of the array
* return a 32 bit arrayID (currently implemented as it's address)
*/
u32 create_array(u32 size){
u32 *tmp = (u32*)my_malloc(sizeof(u32)*size+1);

You don't allocate enough memory here. You only allocate
memory for 'size' array elements plus a single byte. You
would need

u32 *tmp = my_malloc( ( size + 1 ) * sizeof *tmp );

memset(tmp+1, 0, sizeof(u32)*size);
*tmp = size;
return (u32)(tmp+1);
}

And then your function returns a pointer to an u32 cast
to an u32. But pointers can't be used interchangeably
with integers. You my get away with that on some 32-bit
platforms but it's not valid C. And it's unnecessary and
forces you to clutter your code with ugly casts.

#define GET_ARRAY_SIZE(arrayID) (*((u32*)(arrayID-1)))
#define ARRAY(arrayID) ((u32*)(arrayID))
#define WHOLE_ARRAY(arrayID) ((u32*)(arrayID)-1)

/* Delete an array created with create_array()*/
void delete_array(u32 arrayID){
free(WHOLE_ARRAY(arrayID));
}

Again conversions between pointer and integer types. That
function probably needs to be defined as

void delete_array( u32 *array ) {
free( array - 1 );
}

/* Duplicate the content in from to that of to.
* original data in to is discarded.
*/

Please: either use correct comments or delete them.
There is no 'from' nor 'to'. Wrong comments are worse
than none.

void copy2array0(UM32 *um, u32 src){
int size = (u32)GET_ARRAY_SIZE(src);
if(!(um->program))
free(um->program);

Wouldn't this have to be

delete_array( um->program );

Otherwise you might be trying to free() something that
you didn't get from malloc().

um->program = (u32*)my_malloc(sizeof(u32)*size+1);

And here's the same problem with allocating not enough
memory.

memcpy(um->program, WHOLE_ARRAY(src), size+1);

And here again with using integer and pointer types as if
they could be used interchangeably.

um->program++;
}

void load_program(u32** membuffer, const char* filename){
int i, size_read, file_size, membuffer_size;
struct stat file_info;
FILE *infile;

//Find file info
if(stat(filename, &file_info)){
fprintf(stderr, "Failed to stat file: %s. %s\n", filename,
strerror(errno));
exit(1);
}
file_size = file_info.st_size;

//Open file
dprintf("Opening file: %s ...", filename);
infile = fopen(filename, "rb");
if(infile == NULL){
fprintf(stderr, "Failed to open file: %s. %s\n", filename,
strerror(errno));
exit(1);
}
dprintf("done\n");

//Read buffer
dprintf("Reading file content with size: %d ...", file_size);
membuffer_size = sizeof(u8)*file_size/sizeof(u32);
if(!(*membuffer))
free((*membuffer));
//(*membuffer) = (u32*)my_malloc(sizeof(u32)*membuffer_size);

This rather likely will not allocate enough memory. Let's assume
that the file lenght is 11 and sizeof(u32) is 4. Then you end
up with a 'membuffer_size' of 2, i.e. 8 bytes.

(*membuffer) = (u32*)create_array(membuffer_size);
size_read = fread((*membuffer), sizeof(u8), file_size,infile);

And here you read 11 bytes even though your buffer only has 8 bytes.

fclose(infile);
if(size_read != file_size && !feof(infile)){

You can't use feof() on a FILE* you already closed.

Regards, Jens
--
\ Jens Thoms Toerring ___ [e-mail]
\__________________________ http://toerring.de

[Old Wolf]

But when I use

to run a UM program, I kept on getting error messages.

What error messages?

#define dprintf(x,...) printf(x,...)

This is non-standard (Conceivably your compiler allows it
as an extension; for the rest of my reply I'll assume
it doesn't).

If your compiler is compliant with C99 you can write:
#define dprintf(x, ...) printf(x, __VA_ARGS__)

after also including <stdarg.hof course. If your compiler
does not support this then you will have to do something
else, such as:
#define dprintf printf

which would work in this case.

void change_endian(u32* value){
u8 tmp1[4], tmp2[4];
memcpy((u32 *)tmp1, value, sizeof(u32));

tmp1 might not be correctly aligned for u32.

tmp2[0] = tmp1[3];
tmp2[1] = tmp1[2];
tmp2[2] = tmp1[1];
tmp2[3] = tmp1[0];
memcpy(value, (u32 *)tmp2, sizeof(u32));
}

Code like this is likely to cause problems. You should re-write
the code to:
* Not depend on any endian issues
* Not use any casts
* Not rely on alignment

Of course there are one or two rare situations when casts
are necessary, but almost every one in your code is
masking potential undefined behaviour.

The above function could be improved to: (note, better
would be to write code that doesn't use it at all, and
the following would still cause trouble on the DS9000)

void change_endian(u32* value){
u8 *ptr = (u8 *)value;
u8 temp[4];

temp[0] = ptr[3];
temp[1] = ptr[2];
temp[2] = ptr[1];
temp[3] = ptr[0];

*value = temp;
}

[weidongtom]

On May 8, 7:37 am, Old Wolf <[e-mail]:

But when I use
to run a UM program, I kept on getting error messages.

What error messages?

#define dprintf(x,...) printf(x,...)

This is non-standard (Conceivably your compiler allows it
as an extension; for the rest of my reply I'll assume
it doesn't).

If your compiler is compliant with C99 you can write:
#define dprintf(x, ...) printf(x, __VA_ARGS__)

after also including <stdarg.hof course. If your compiler
does not support this then you will have to do something
else, such as:
#define dprintf printf

which would work in this case.

void change_endian(u32* value){
u8 tmp1[4], tmp2[4];
memcpy((u32 *)tmp1, value, sizeof(u32));

tmp1 might not be correctly aligned for u32.

tmp2[0] = tmp1[3];
tmp2[1] = tmp1[2];
tmp2[2] = tmp1[1];
tmp2[3] = tmp1[0];
memcpy(value, (u32 *)tmp2, sizeof(u32));
}

Code like this is likely to cause problems. You should re-write
the code to:
* Not depend on any endian issues
* Not use any casts
* Not rely on alignment

Of course there are one or two rare situations when casts
are necessary, but almost every one in your code is
masking potential undefined behaviour.

The above function could be improved to: (note, better
would be to write code that doesn't use it at all, and
the following would still cause trouble on the DS9000)

void change_endian(u32* value){
u8 *ptr = (u8 *)value;
u8 temp[4];

temp[0] = ptr[3];
temp[1] = ptr[2];
temp[2] = ptr[1];
temp[3] = ptr[0];

*value = temp;
}

Hi,

Thanks for your assistance, and I was able to make a few changes to
the code. That was the first time I ever post on a group so I didn't
know exactly what I have to say. Well, being a novice is never
easy...dump and stupid... But thanks for your help.

The code was able to be compiled by gcc 3.4.2 <mingw-speical>. As I am
developing it on Windows (and I am a novice) I don't know if there's
any replacement on my platform for the library function ntohl()
defined in <netinet/arpa.hfound in Linux/Unix, so that I can use it
to changed the UM binary file data (which is big-endian) to my local-
intel's small-endian 32 bit data, so I came up with:
void change_endian(u32* value);
to handle the problem which seems to have worked.

So, there's no compilation problem, but there's a runtime error:
"Array index out of bound."
codex=c0000032, opcode=12, finger=0000000e
OP_LOAD, loading program into array0 from array[6] at 00000000
finger=0400005b
registers: 00000000d, 02000014, 0400005b, 06000035, 00000000, 0000000,
00000000, 00000000

when run with this UM binary file: http://www.boundvariable.org/sandmark.umz
.. There's nothing wrong with the binary file, so I suspect there's
something wrong with the way I handle the array memory allocation, or
is there something wrong with how I change the endians (which seems to
be unlikely).

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <errno.h>
#include <sys/stat.h>
#include <stdarg.h>

//internal data
typedef unsigned int u32;
typedef unsigned char u8;

//debug macros
#define DUMP_FILE_NAME "memory.dmp"
#define PRINT_DEBUG_MSG
#define DUMP_MEMORY

//decode macros
#define REG_A(codex) ((codex >6) & 7)
#define REG_B(codex) ((codex >3) & 7)
#define REG_C(codex) (codex & 7)
#define OPCODE(codex) ((codex >28) & 15)
#define SPEC_A(codex) ((codex >25) & 7)
#define SPEC_V(codex) (codex & 0x0fffffffL)
//opcodes
#define OP_CMOV 0
#define OP_INDEX 1
#define OP_AMAND 2
#define OP_ADD 3
#define OP_MUL 4
#define OP_DIV 5
#define OP_NAND 6
#define OP_HALT 7
#define OP_ALLOC 8
#define OP_FREE 9
#define OP_OUT 10
#define OP_IN 11
#define OP_LOAD 12
#define OP_ORTHO 13

//32 bit Universal Machine cpu struct
typedef struct UM32_{
u32 finger;
u32 r[8];
u32* program;
}UM32;

//function prototypes
void *my_malloc(size_t size);
u32* create_array(u32 size);
void delete_array(u32 *array);
u32 get_arrayID(u32 *array);
u32* get_array_by_ID(u32 ID);
void delete_array_by_ID(u32 ID);
u32 get_array_size(u32 *array);
void dprintf(const char *fmt, ...);

void dprintf(const char *fmt, ...){
#ifdef PRINT_DEBUG_MSG
va_list ap;
va_start(ap, fmt);
vprintf(fmt, ap);
va_end(ap);
#endif
return;
}

/*Change local small-endian to UM's internal big-endian
* this is a dirty hack to replace the netinet/arpa.h's ntohl()
*/
void change_endian(u32* value){
u8 tmp1[4], tmp2[4];
memcpy((u32 *)tmp1, value, sizeof(u32));
tmp2[0] = tmp1[3];
tmp2[1] = tmp1[2];
tmp2[2] = tmp1[1];
tmp2[3] = tmp1[0];
memcpy(value, (u32 *)tmp2, sizeof(u32));
}

/* A wrapper for malloc() in stdlib.h */
void *my_malloc(size_t size){
void *tmp = malloc(size);
if(tmp != NULL)
return tmp;
else{
fprintf(stderr, "Falied in my_malloc() in attempt to allocate memory
of size: %d.\n",
size);
exit(1);
}
}

/* Create an array with size size+1,
* where array[-1] is used for holding the size of the array.
* a pointer to array is returned.
*/
u32* create_array(u32 size){
u32 *tmp = (u32*)my_malloc((size+1)*sizeof(u32));
memset(tmp+1, 0, sizeof(u32)*size);
*tmp = size;
return (tmp+1);
}

/* Delete an array created with create_array()*/
void delete_array(u32 *array){
free(array-1);
}

/* Return the ID of an array created with create_array,
* which is the address fot its first element.
*/
u32 get_arrayID(u32 *array){
return (u32)array;
}

/* Return the array with ID ID (which is the address
* of the array.
*/
u32* get_array_by_ID(u32 ID){
return (u32*)ID;
}

/* Delete array with ID ID.*/
void delete_array_by_ID(u32 ID){
u32 *tmp = get_array_by_ID(ID);
delete_array(tmp);
}

/* Return the size of an array created with create_array.*/
u32 get_array_size(u32 *array){
return *(array-1);
}

/* Duplicate the content in from to that of to.
* original data in to is discarded.
*/
void copy_array(u32 *to, u32 *from){
int size = get_array_size(from);
if(!to)
delete_array(to);
to = create_array(size);
memcpy(to, from, size*sizeof(u32));
}

void load_program(u32** membuffer, const char* filename){
int i, size_read, file_size, membuffer_size;
struct stat file_info;
FILE *infile;

//Find file info
if(stat(filename, &file_info)){
fprintf(stderr, "Failed to stat file: %s. %s\n", filename,
strerror(errno));
exit(1);
}
file_size = file_info.st_size;

//Open file
dprintf("Opening file: %s ...", filename);
infile = fopen(filename, "rb");
if(infile == NULL){
fprintf(stderr, "Failed to open file: %s. %s\n", filename,
strerror(errno));
exit(1);
}
dprintf("done\n");

//Read buffer
dprintf("Reading file content with size: %d ...", file_size);
membuffer_size = sizeof(u8)*file_size/sizeof(u32) + 1;
if(!(*membuffer))
free((*membuffer));
(*membuffer) = create_array(membuffer_size);
size_read = fread((*membuffer), sizeof(u8), file_size, infile);
if(size_read != file_size && !feof(infile)){
fprintf(stderr, "Warning: failed to read all data.\n");
}
fclose(infile);
dprintf("done.\n");

//change the endian
dprintf("Changing small-endian data to big_endian ...\n");
for(i = 0; i < membuffer_size; i++){
dprintf(" %08x->", (*membuffer)[i]);
change_endian(&(*membuffer)[i]);
dprintf("%08x", (*membuffer)[i]);
if((i+1)%4 == 0)
dprintf("\n");
}
dprintf("\ndone.\n");
dprintf("Program of size: %d loaded.\n",
(*((*membuffer)-1))*sizeof(u32));
}

void init_um32(UM32* um, u32* program){
int i;
dprintf("Initializing the Universal Machine ...");
if(program == NULL){
fprintf(stderr, "Fatal Error in init_um32, program is NULL.\n");
exit(1);
}
dprintf("\nRegisters:");
for(i=0;i<8;i++){
um->r[i] = 0;
dprintf(" %08x", um->r[i]);
}
um->finger = 0;
um->program = program;
dprintf("\nfinger = %08x\nprogram loaded at %08x\n", um->finger,
(u32)um->program);
dprintf("done.\n");
}

void dump_memory(u32 *mem){
FILE *outfile = NULL;
int i;
if(mem == NULL){
fprintf(stderr, "UM Memory is null.\n");
exit(1);
}
outfile = fopen(DUMP_FILE_NAME, "w");
dprintf("Beginning memory dump of size: %d...\n", *(mem-1));
if(!outfile){
fprintf(stderr, "Error in dump_memory. Failed to open file: %s.
%s",
DUMP_FILE_NAME, strerror(errno));
exit(1);
}
for(i=0;i<*(mem-1); i++){
fprintf(outfile, " %08x", mem[i]);
if((i+1)%8 == 0)
fprintf(outfile, "\n");
}
dprintf("Done.\n");
fclose(outfile);
}

int bound_program(UM32 um, u32 index){
if(index *(um.program-1))
return 1;
return 0;
}

int bound_array(u32 arrayID, u32 index){
u32 *tmp = get_array_by_ID(arrayID);
if(!tmp || index get_array_size(tmp))
return 1;
return 0;
}

/* Execute one instruction
* return 1 on success
*/
#define R(a) um->r[a]
#define PROGRAM (um->program)
#define FINGER (um->finger)
int um_run(UM32 *um, int trace){
u8 opcode;
u32 a, b, c, codex;

if(bound_program(*um, FINGER)){
printf("Array Index out of bound.\n");
exit(1);
}
codex = PROGRAM[FINGER++];
opcode = OPCODE(codex);
a = REG_A(codex);
b = REG_B(codex);
c = REG_C(codex);

if(trace)
printf("\ncodex=%08x, opcode=%d, finger=%08x\n", codex, opcode,
FINGER);

if(opcode == OP_ORTHO){
a = SPEC_A(codex);
R(a) = SPEC_V(codex);
if(trace){
printf("OP_ORTHO, r[%d]=%u\n", a, R(a));
printf("registers: %08x, %08x, %08x, %08x, %08x, %08x, %08x, %08x
\n",
R(0), R(1), R(2), R(3), R(4), R(5), R(6), R(7));
}
return 1;
}
switch(opcode){
case OP_CMOV:
if(!R(c)){
R(a) = R(b);
if(trace){
printf("OP_CMOV, r[%d]=r[%d]=%08x\n", a, b, R(a));
}
}
break;
case OP_INDEX:
if(!R(b)){
if(bound_program(*um, R(c))){
printf("Index out of bound in accessing array0 at offset %08x\n",
R(c));
exit(0);
}
R(a) = PROGRAM[R(c)];
}
else{
if(bound_array(R(b), R(c))){
printf("Index out of bound in accessing array%d\n", R(b));
exit(1);
}
R(a) = get_array_by_ID(R(b))[R(c)];
}
if(trace)
printf("OP_INDEX, r[%d]=array[%d][%d]=%08x\n", a, b, c, R(a));
break;
case OP_AMAND:
if(!R(a)){
if(bound_program(*um, R(b))){
printf("Index out of bound in accessing array0 at offset %08x\n",
R(c));
exit(0);
}
PROGRAM[R(b)] = R(c);
}
else{
if(bound_array(R(a), R(b))){
printf("Index out of bound in accessing array%d\n", R(b));
exit(1);
}
get_array_by_ID(R(a))[R(b)] = R(c);
}
if(trace)
printf("OP_AMAND, array[%d][%d]=r[%d]=%08x\n", a, b, c, R(c));
break;
case OP_ADD:
R(a) = R(b) + R(c);
if(trace)
printf("OP_ADD, r[%d]=r[%d]+r[%d]=%08x\n", a, b, c, R(a));
break;
case OP_MUL:
R(a) = R(b) * R(c);
if(trace)
printf("OP_ADD, r[%d]=r[%d]*r[%d]=%08x\n", a, b, c, R(a));
break;
case OP_DIV:
R(a) = R(b) / R(c);
if(trace)
printf("OP_ADD, r[%d]=r[%d]/r[%d]=%08x\n", a, b, c, R(a));
break;
case OP_NAND:
R(a) = ~(R(b) & R(c));
if(trace)
printf("OP_ADD, r[%d]=~(r[%d]&r[%d])=%08x\n", a, b, c, R(a));
break;
case OP_HALT:
if(trace)
printf("OP_HALT, stopping program ... done.\n");
return 0;
break;
case OP_ALLOC:
R(b) = get_arrayID(create_array(R(c)));
if(trace)
printf("OP_ALLOC, r[%d]=create_array(r[%d])=%08x\n", b, c, R(b));
break;
case OP_FREE:
delete_array_by_ID(R(c));
R(c) = 0;
if(trace)
printf("OP_REE, free(r[%d]=%08x)\n", c, R(c));
break;
case OP_OUT:
if(R(c) < 256){
putchar(R(c));
if(trace)
printf("OP_OUT, putchar(r[%d]=%08x)\n", c, R(c));
}
else
fprintf(stdout, "Warning, failed to output value %08x as char.\n",
R(c));
break;
case OP_IN:
R(c)=getchar();
if(trace)
printf("OP_IN, r[%d]=getchar()=%08x", c, R(c));
break;
case OP_LOAD:
if(R(b) != 0)
copy_array(um->program, get_array_by_ID(R(b)));
FINGER = R(c);
if(trace){
printf("OP_LOAD, loading program into array0 from array[%d] at %08x
\n",
b, R(b));
printf("\tfinger=%08x\n", FINGER);
}
break;
default:
printf("Fatal Error: Bad opcode=%d, codex=%08x\n", opcode, codex);
return 0;
break;
}
if(trace)
printf("registers: %08x, %08x, %08x, %08x, %08x, %08x, %08x, %08x
\n",
R(0), R(1), R(2), R(3), R(4), R(5), R(6), R(7));
return 1;
}

int main(int argc, char *argv[]){
UM32 um;
u32 *program;
int run;

#ifndef NOT_GDB
argc = 2;
argv[1] = "sandmark.umz";
#endif
if(argc < 2){
printf("Usage: %s filename\n", argv[0]);
exit(0);
}
//load program
load_program(&program, argv[1]);
//initialize um
init_um32(&um, program);
#ifdef DUMP_MEMORY
dump_memory(program);
#endif
do{
run = um_run(&um, 1);
}while(run);
return 0;
}

[Dietmar Schindler]

"we********@gmail.com" wrote:

...
I tried to implement the Universal Machine as described in
http://www.boundvariable.org/task.shtml, and I managed to get one
implemented (After looking at what other's have done.) But when I use
to run a UM program, I kept on getting error messages. I have used
someone else's implementation and it runs fine. I have compared my
code with other's and I still can't figure it out what's wrong with
mine. So please help me out, after 3 days of debugging I don't think I
can ever make it. Here's my implementation. Thanks in advance.
...
#define SPEC_V(codex) (codex & 0x0fffffffL)

#define SPEC_V(codex) (codex & 0x01ffffffL)

(see http://www.boundvariable.org/um-spec.txt / Special Operators.)

--
DPS

[David Thompson]

On 7 May 2007 23:18:00 -0700, "we********@gmail.com"
<we********@gmail.comwrote:
<snip>

The code was able to be compiled by gcc 3.4.2 <mingw-speical>. As I am
developing it on Windows (and I am a novice) I don't know if there's
any replacement on my platform for the library function ntohl()
defined in <netinet/arpa.hfound in Linux/Unix, so that I can use it

#if OFFTOPIC /* since this group is about portable C which doesn't
include sockets */ /* oops, preproc directives can't wrap lines <G*/

mingw uses the Windows libraries, and the Windows equivalent to the
BSD/Unix sockets library does contain the {ntoh,hton}[sl] functions
among many other things all declared in <winsock2.h.

#else
OTOH doing it yourself, preferably in portable code, is also fine.
#endif

to changed the UM binary file data (which is big-endian) to my local-
intel's small-endian 32 bit data, so I came up with:
void change_endian(u32* value);
to handle the problem which seems to have worked.

So, there's no compilation problem, but there's a runtime error:
"Array index out of bound."
codex=c0000032, opcode=12, finger=0000000e
OP_LOAD, loading program into array0 from array[6] at 00000000
finger=0400005b
registers: 00000000d, 02000014, 0400005b, 06000035, 00000000, 0000000,
00000000, 00000000

To be clear, this appears to be two trace messages and an error
message generated by your program. ('Runtime error' is sometimes used
specifically to mean errors detected and/or reported by the
compiler-generated or library support code, not explicitly by user
code, although this is less often true among C programmers.)

when run with this UM binary file: http://www.boundvariable.org/sandmark.umz
. There's nothing wrong with the binary file, so I suspect there's
something wrong with the way I handle the array memory allocation, or
is there something wrong with how I change the endians (which seems to
be unlikely).

See below.

<snip>

typedef unsigned int u32;
typedef unsigned char u8;

Aside: int (signed or unsigned) isn't required to be 32 bits, and
there are systems, though fewer nowadays, where it is (they are) 16
bits, which would not work at all for your application. long (signed
and unsigned) is at least 32 bits, but sometimes more (which would
work, but be wasteful). Similarly char isn't required to be exactly 8
bits, but is at least 8, which is probably good enough for your usage.

<snip>

#define OP_CMOV 0
#define OP_INDEX 1
#define OP_AMAND 2
#define OP_ADD 3
#define OP_MUL 4
#define OP_DIV 5
#define OP_NAND 6
#define OP_HALT 7
#define OP_ALLOC 8
#define OP_FREE 9
#define OP_OUT 10
#define OP_IN 11
#define OP_LOAD 12
#define OP_ORTHO 13

Aside: while #define can give a name to any kind of literal (supported
by C) and even other things, where you have a series of names for
not-huge integers, especially consecutive integers as here, you can
instead use enum, and I would.

<snip>

/*Change local small-endian to UM's internal big-endian
* this is a dirty hack to replace the netinet/arpa.h's ntohl()
*/
void change_endian(u32* value){
u8 tmp1[4], tmp2[4];
memcpy((u32 *)tmp1, value, sizeof(u32));

You don't need to cast; if properly declared (by <string.h>, which you
do have) memcpy takes void*, and any pointer to data (not qualified as
const or volatile) will be automatically converted.

You would need to cast if you tried to do something like:
* (u32*) tmp1 = * value;
but that is a bad idea anyway, since C allows types other than
character to require alignment, and on some machines they do, and
there is no guarantee that array-4-of-u8 is correctly aligned for u32.

tmp2[0] = tmp1[3];
tmp2[1] = tmp1[2];
tmp2[2] = tmp1[1];
tmp2[3] = tmp1[0];
memcpy(value, (u32 *)tmp2, sizeof(u32));

Ditto.

}

Aside: It isn't actually necessary to copy in, swap, and then copy
out. However, as you apparently use this only when loading the initial
'program', probably a relatively modest amount of data, it probably
doesn't matter. Certainly it is more important to get the program
correct first, and only then IF performance is too low AND measurement
e.g. profiling confirms this is a (or the) problem THEN worry about
micro-optimization.

<snip>

/* Duplicate the content in from to that of to.
* original data in to is discarded.
*/
void copy_array(u32 *to, u32 *from){
int size = get_array_size(from);
if(!to)
delete_array(to);
to = create_array(size);
memcpy(to, from, size*sizeof(u32));
}

This is most likely your actual problem, and is a FAQ: 4.8, at the
usual places and http://c-faq.com/ .

You allocate a new array and modify 'to' to point to it, but only
locally within copy_array. Any variable whose value is passed by the
caller, which in this case is um->program, is NOT modified, and still
points to the old memory which is now invalid; formally this causes
Undefined Behavior (anything may happen) and practically even if this
doesn't do something really crazy it won't do what you wanted.

void load_program(u32** membuffer, const char* filename){

<snip>

membuffer_size = sizeof(u8)*file_size/sizeof(u32) + 1;
if(!(*membuffer))
free((*membuffer));
(*membuffer) = create_array(membuffer_size);

Note that in this, similar, case, you got it right: you pass a pointer
to the pointer, and both use and modify indirectly. Another approach
is to instead pass back the new/modified pointer as the return value
and require (and allow) the caller to store it where desired.

size_read = fread((*membuffer), sizeof(u8), file_size, infile);
if(size_read != file_size && !feof(infile)){
fprintf(stderr, "Warning: failed to read all data.\n");
}

Small point: why check feof? Even if set it indicates that you somehow
didn't get the right size from <offtopic and snippedstat() </which
is still probably worth at least a warning.

<snip much that looks OK although I would likely choose to do it
somewhat differently>

int main(int argc, char *argv[]){
UM32 um;
u32 *program;
int run;

#ifndef NOT_GDB
argc = 2;
argv[1] = "sandmark.umz";
#endif

This is a little dubious. There is not actually an official guarantee
that you can modify argv[] pointers, although in practice you can.
(You _are_ allowed to modify the string contents pointed to by argv[]
pointers, up to their initial length but not longer.) Officially it is
not even guaranteed/required that there be a commandname argv[0] and
thus you can have argc == 0 and argv[0] == NULL and argv[1] doesn't
even exist, though on 'normal' implementations this won't happen.

if(argc < 2){
printf("Usage: %s filename\n", argv[0]);
exit(0);
}

Moreover, it isn't necessary. Usually better practice would be
something like:

const char * program_name;
#if TESTCASE
program_name = "sandmark.umz";
#else
if( argc < 2 ) { error as above }
/* else */ program_name = argv[1];
#endif
... now proceed to use program_name ...

Note that I find the double negative (if not not-GDB) confusing, and
also prefer to have the no-macro case be the (presumed) normal case,
and the debugging case should not normally be the normal case.

<offtopicAlso, if by GDB you really do mean GDB the GNU debugger,
you _can_ give a program arguments when you run it within GDB, so you
don't need this kind of kludge in the program itself. </>

- formerly david.thompson1 || achar(64) || worldnet.att.net