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

Discussion in 'C Programming' started by weidongtom@gmail.com, May 7, 2007.

  1. Guest

    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));
    change_endian(&(*membuffer));
    dprintf("%08x", (*membuffer));
    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 = 0;
    dprintf(" %08x", um->r);
    }
    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);
    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;
    }
     
    , May 7, 2007
    #1
    1. Advertising

  2. <> 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.


    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 ___
    \__________________________ http://toerring.de
     
    Jens Thoms Toerring, May 7, 2007
    #2
    1. Advertising

  3. Old Wolf Guest

    > 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.h> of 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;
    }
     
    Old Wolf, May 8, 2007
    #3
  4. Guest

    On May 8, 7:37 am, Old Wolf <> wrote:
    > > 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.h> of 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.h> found 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));
    change_endian(&(*membuffer));
    dprintf("%08x", (*membuffer));
    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 = 0;
    dprintf(" %08x", um->r);
    }
    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);
    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;
    }
     
    , May 8, 2007
    #4
  5. Re: Virtual Machine implementation problem, Please help me to spot thebug

    "" 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
     
    Dietmar Schindler, May 15, 2007
    #5
  6. On 7 May 2007 23:18:00 -0700, ""
    <> wrote:
    <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.h> found 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 snipped> stat() </> 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.

    <offtopic> Also, 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
     
    David Thompson, May 21, 2007
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. urocrane

    spot the bug

    urocrane, Jul 12, 2003, in forum: C++
    Replies:
    3
    Views:
    423
    John Carson
    Jul 12, 2003
  2. IK
    Replies:
    2
    Views:
    612
    hemraj
    Jul 23, 2004
  3. Sathyaish

    Please spot out the cause of this bug

    Sathyaish, Nov 19, 2004, in forum: C Programming
    Replies:
    2
    Views:
    388
    Charlie Gordon
    Nov 24, 2004
  4. Andreas Vinther

    Please help me spot the difference

    Andreas Vinther, Oct 23, 2006, in forum: C Programming
    Replies:
    9
    Views:
    417
    Andreas Vinther
    Nov 6, 2006
  5. shapper
    Replies:
    2
    Views:
    246
    shapper
    Nov 7, 2008
Loading...

Share This Page