simple stack-based machine in C

Question

I have to create a simple stack-based machine. The instruction set consists of 5 instructions; push, pop, add, mult, end. I accept a source code file that has an instruction section (.text) and a data section (.data) and then i must store these in memory by simulating a memory system that uses 32-bit addresses.

An example source code file that I have to store in memory might be

    .text
main:
    push X
    push Y
    add   //remove top two words in stack and add them then put result on top of stack
    pop (some memory address)  // stores result in the address
    end

    .data
X:  3    // allocate memory store the number 3
Y:  5

Any suggestion on how to do the memory system? I should probably store data in one section (maybe an array?) and then instructions in another but i can't just use array indexes since I need to use 32-bit addresses in my code.

Edit: Also is there a way to replace the X and Y with the actual address once I've assigned the number 3 and 5 to a space in memory (in my data array)? . . . kind of like a two pass assembler might do it.

Answer 1

What's wrong with arrays? If you know the size you need, they should work.
An address in your machine code would actually be an index in the array.

Using a 32-bit index with an array isn't a problem. Of course, not all indexes would be valid - only those from 0 to the size of the array. But do you need to simulate 4GB of memory, or can you set a limit on the memory size?

Answer 2

Just to add to the ugoren' answer (and a bit OT), I think a relatively interesting approach could be to extend your specification space with a .stack section, to be initialized by default to empty (like in your example).

That can be used to describe the expected intermediate stages of the computation (save/restore the actual state at some point).

To implement, I would use very simple code, like

file stack.h:

#ifndef STACK
#define STACK

#include <stdio.h>

/* here should be implemented the constraint about 32 bits words... */
typedef int word;

typedef struct { int top; word* mem; int allocated; } stack;
typedef stack* stackp;

stackp new_stack();
void free_stack(stackp);

void push(stackp s, word w);
word pop(stackp p);

/* extension */
stackp read(FILE*);
void write(stackp, FILE*);

#endif

file stack.c:

/* example implementation, use - arbitrary - chunks of 2^N */

#include <stdlib.h>
#include "stack.h"

/* blocks are 256 words */
#define N (1 << 8)

stackp new_stack() {
  stackp s = calloc(1, sizeof(stack));
  s->mem = malloc((s->allocated = N) * sizeof(word));
  return s;
}
void free_stack(stackp s) {
  free(s->mem);
  free(s);
}

void push(stackp s, int w) {
  if (s->top == s->allocated) {
     s->allocated += N;
     s->mem = realloc(s->mem, s->allocated * sizeof(word));
  }
  s->mem[s->top++] = w;
}
word pop(stackp s) {
  if (s->top == 0) { /* exception */ }
  return s->mem[--(s->top)];
}

file main.c:

#include "stack.h"
int main() {

  stackp s = new_stack();
  word X = 3;
  word Y = 5;

  push(s, X);
  push(s, Y);
  word Z = pop(s) + pop(s);

  printf("Z=%d\n", Z);

  free_stack(s);
}

file makefile:

main: main.c stack.c

to build:

make

to test:

./main
Z=8

It's worth noting some difference WRT ugoren' answer: I stress on data hiding, a valuable part of implementation, keeping details about actual functions in a separate file. There we can add many details, for instance about a maximum stack size (actually not enforced there), error handling, etc...

edit: to get the 'address' of a pushed word

word push(stackp s, int w) {
  if (s->top == s->allocated) {
     s->allocated += N;
     s->mem = realloc(s->mem, s->allocated * sizeof(word));
  }
  s->mem[s->top] = w;
  return s->top++;
}