Skip to content
Snippets Groups Projects
emulate.c 11.09 KiB
#include <math.h>
#include <stdint.h>
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>

#define MEMORY_SIZE 65536

// Helpful stuff (things that will probably be used to implement more than one instruction type)
// apparently int can be as little as 16 bits, so I use ints only for boolean values and values that are always smaller than 16 bits,
// and int32_t / uint32_t to represent everything else.
// uint32_t is used for binary data instead of int32_t because it behaves more predictably (especially in shifts and conversions)

// struct representing a processor:
struct ProcessorState
{
  uint32_t registers[17];
  // each uint32_t is 4 bytes large:
  uint32_t memory[MEMORY_SIZE/4];
};

// Reads bits from source in the range [start, end] (inclusive). Returns an int32_t with the result as its least significant bits.
// (e.g. getBits(8, 2, 3) == 2)
uint32_t getBits(uint32_t source, int start, int end)
{
  return (source & ((2 << end) - (1 << start))) >> start;
}

// Shorthand for getBits(source, index, index)
bool isSet(uint32_t source, int index)
{
  return (source & (1 << index));
}

// Returns 1 if the condition code 'cond' is satisfied by the processor's current state, and 0 otherwise.
// Any condition code not listed in the spec will cause this to return 0.
bool validCond(uint32_t cond, struct ProcessorState *processor)
{
  // cprs register
  uint32_t cprs = (*processor).registers[16];

  // cprs flags
  bool n = isSet(cprs, 31);
  bool z = isSet(cprs, 30);
  bool v = isSet(cprs, 28);

  switch (cond)
  {
  case 0:
    return z;
  case 1:
    return !z;
  case 10:
    return n == z;
  case 11:
    return n != z;
  case 12:
    return !z && (n == v);
  case 13:
    return z || (n != v);
  case 14:
    return 1;
  default:
    return 0;
  }
}

/*
Implements the barrel shifter.

  immediate: the I bit from the spec. Determines whether to shift by immediate value.
  operand: the entire shift instruction (12 bits long). Operand2 on the spec.
  carry: the carry-out bit (in case flags need to be updated).
  processor: the processor (needed for reading from the registers).

  this is completely untested and probably buggy, for all I know this becomes self-aware at runtime so don't trust anything it tells you
  also, this doesn't cast return types; i don't think it's a problem but this is C so who knows what it's thinking
*/
uint32_t barrelShift(bool immediate, uint32_t operand, bool *carry, struct ProcessorState *processor)
{
  if (immediate)
  {
    //*** shift using immediate value ***//
    unsigned int shiftCount = (unsigned int)getBits(operand, 8, 11);
    uint32_t operandVal = getBits(operand, 0, 7);
    //printf("%i\n%i\n", shiftCount, operandVal);

    // shifting an int32_t by 32 bits is undefined behaviour in C, and this if statement prevents it from happening later.
    if (shiftCount == 0)
    {
      return operandVal;
    }

    // set operandVal to the result after rotation
    //printf("%i\n%i\n\n", operandVal >> (2 * shiftCount), (operandVal << (32 - 2 * shiftCount)));
    operandVal = (operandVal >> (2 * shiftCount)) | (operandVal << (32 - 2 * shiftCount));
    //printf("%i\n", operandVal);
    
    // set c to the last bit of operandVal (the last bit to be rotated)
    (*carry) = isSet(operandVal, 31);
    return operandVal;
  }

  // this kind of register access is safe as 4 bits cannot reach above 17
  uint32_t operandVal = (*processor).registers[getBits(operand, 0, 3)];
  unsigned int shiftType = getBits(operand, 5, 6);
  unsigned int shiftCount;
  if (isSet(operand, 4))
  {
    //*** shift using shift count stored in a register ***//
    uint32_t shiftReg = getBits(operand, 8, 11);
    // register should not be the PC
    if(shiftReg == 15){
      printf("Invalid instruction: shift count cannot be stored in PC");
      exit(-1);
    }
    shiftCount = getBits((*processor).registers[shiftReg], 0, 7);
  }
  else
  {
    //*** shift using immediate shift count ***//
    shiftCount = getBits(operand, 7, 11);
  }

  // Exit early if not shifting. This makes some of the upcoming logic simpler.
  if (shiftCount == 0)
  {
    return operandVal;
  }

  //*** perform the shift ***//
  // the behaviour for when shiftCount >= 32 (when shiftCount comes from a register) is a little ambiguous in the spec,
  // so I got it from here: https://iitd-plos.github.io/col718/ref/arm-instructionset.pdf (bottom of page 14)
  switch (shiftType)
  {
  // logical left shift
  case 0:
    // this can happen if shiftCount comes from a register:
    if (shiftCount >= 32)
    {
      (*carry) = shiftCount == 32 ? isSet(operandVal, 0) : 0;
      return 0;
    }
    (*carry) = isSet(operandVal, 32 - shiftCount);
    return operandVal << shiftCount;

  // logical right shift
  case 1:
    // this can happen if shiftCount comes from a register:
    if (shiftCount >= 32)
    {
      (*carry) = shiftCount == 32 ? isSet(operandVal, 31) : 0;
      return 0;
    }

    (*carry) = isSet(operandVal, shiftCount - 1);
    // operandVal is a uint32_t, so C shouldn't sign-extend it
    return operandVal >> shiftCount;

  // arithmetic right shift
  case 2:
    // this can happen if shiftCount comes from a register:
    if (shiftCount >= 32)
    {
      uint32_t result = 0;
      (*carry) = isSet(operandVal, 31);
      if ((*carry))
      {
        result = ~result;
      }
      return result;
    }
    (*carry) = isSet(operandVal, shiftCount - 1);
    // convert operandVal to a signed type, then shift it
    return (int32_t)operandVal >> shiftCount;

  // rotate right
  case 3:
    // this can happen if shiftCount comes from a register:
    if (shiftCount == 32)
    {
      (*carry) = isSet(operandVal, 31);
      return operandVal;
    }
    shiftCount = shiftCount % 32;

    (*carry) = isSet(operand, shiftCount - 1);
    return (operandVal >> shiftCount) | (operandVal << (32 - shiftCount));

  default:
  // this should never happen (but gcc wants it)
    return 0;
  };
}

/*
Applies a binary operation (from an opcode) on two operators. Returns the result, and sets the supplied carry bit if it makes sense to do so.
Does not change the carry bit when performing a logical operation.

  opcode: the opcode
  operand1: The content of register Rn on the spec
  operand2: The value of Operand2 on the spec after shifting
  carry: Carry bit output
  store: A bit representing whether the result should be stored (some instructions like TST discard the result) (boolean)
*/

int32_t applyOperation(int opcode, int32_t operand1, int32_t operand2, bool *carry, bool *store)
{
  (*store) = (opcode != 8) && (opcode != 9) && (opcode != 10);

  // the phrasing in the spec is a little weird (I'm not sure what counts as a borrow for a subtraction, I'm pretty sure they mean an overflow)
  // according to https://iitd-plos.github.io/col718/ref/arm-instructionset.pdf (top of pg. 12) "The C flag will be set to the carry out of bit 31 of the ALU"
  // I'll just go with that for now
  // TODO: figure out if I interpreted that right

  switch (opcode)
  {
  // tst, and
  case 0:
    return operand1 & operand2;

  // teq, eor
  case 1:
    return operand1 ^ operand2;

  // or
  case 12:
    return operand1 | operand2;

  // rsb, sub, add respectively (also cmp)
  case 3:
    // rsb
    {
    int32_t swap = operand1;
    operand1 = operand2;
    operand2 = swap;
    }
  case 2:
    // sub
    operand2 = (~operand2) + 1;
  case 4:
    // add
    {
    uint32_t result = operand1 + operand2;
    // check for overflow (this should work in all cases):
    (*carry) = (result < operand1);
    return result;
    }

  case 13:
    return operand2;

  default:
    printf("Unrecognised opcode. Exiting...");
    exit(-1);
  };
}

/* testing helper function (very similar to the one in the slides) */
void testCond(bool ok, char *testname)
{
  printf("T %s: %s\n", testname, ok ? "\tOK" : "\tFAIL");
}

/* converts string representing a binary number to a number.
  for testing - doesn't check validity. ignores leading zeros and any spaces*/
uint32_t bin(char* number){
  uint32_t result = 0;
  int end = strlen(number) - 1;
  int spaceCount = 0;
  for(int i = end; i >= 0; i--){
    if(number[i] == ' '){
      spaceCount++;
      continue;
    }
    result = result + ((number[i] - '0') << (end - i - spaceCount));
  }
  return result;
}

void testBitGetters(){
  printf("*** getBits() tests ***\n");
  testCond(getBits(bin("11000000000000000000000101101110"), 28, 31) == 12, "leftmost bits");
  testCond(getBits(bin("11000000000000000000000101101110"), 8, 20) == 1, "middle bits");
  testCond(getBits(bin("11000000000000000000000101101110"), 0, 3) == 14, "rightmost bits");
  printf("\n");

  printf("*** isSet() tests ***\n");
  testCond(isSet(bin("11000000000000000000000101101110"), 31), "leftmost bit");
  testCond(isSet(bin("11000000000000000000000101101110"), 8), "middle bit");
  testCond(!isSet(bin("11000000000000000000000101101110"), 0), "rightmost bit");
  printf("\n");

}

/* creates a new processor, setting all registers to 0. Dynamically allocated - call free()! */
struct ProcessorState *makeProcessor(void){
  struct ProcessorState* processor = (struct ProcessorState*)malloc(sizeof(struct ProcessorState));
  for(int i = 0; i < 17; i++){
    processor->registers[i] = 0;
  }
  return processor;
}

void testBarrelShifter(){
  printf("*** barrelShifter() tests ***\n");
  struct ProcessorState *processor = makeProcessor();
  processor->registers[0] = bin("10110100000000000000000000000000");
  processor->registers[1] = 60;

  bool carry;
  testCond(barrelShift(true, bin("0001 10110100"), &carry, processor) == bin("00101101") && !carry, "Immediate rotation (small)");
  testCond(barrelShift(true, bin("0100 10110100"), &carry, processor) == bin("10110100000000000000000000000000") && carry, "Immediate rotation (large)");
  printf("\n");

  testCond(barrelShift(false, bin("0001 0 00 1 0000"), &carry, processor) == 0 && !carry, "Register value, register shift count (lsl)");
  testCond(barrelShift(false, bin("0001 0 01 1 0000"), &carry, processor) == 0 && !carry, "Register value, register shift count (lsr)");
  testCond(barrelShift(false, bin("0001 0 10 1 0000"), &carry, processor) == bin("11111111111111111111111111111111") && carry, "Register value, register shift count (asr)");
  testCond(barrelShift(false, bin("0001 0 11 1 0000"), &carry, processor) == bin("01000000000000000000000000001011") && !carry, "Register value, register shift count (ror)");
  printf("\n");

  testCond(barrelShift(false, bin("00100 00 0 0000"), &carry, processor) == bin("01000000000000000000000000000000") && carry, "Register value, constant shift count (lsl)");
  testCond(barrelShift(false, bin("00100 01 0 0000"), &carry, processor) == bin("00001011010000000000000000000000") && !carry, "Register value, constant shift count (lsr)");
  testCond(barrelShift(false, bin("00100 10 0 0000"), &carry, processor) == bin("11111011010000000000000000000000") && !carry, "Register value, constant shift count (asr)");
  testCond(barrelShift(false, bin("00100 11 0 0000"), &carry, processor) == bin("00001011010000000000000000000000") && !carry, "Register value, constant shift count (ror)");
  printf("\n");

  free(processor);
}

int main(void){
  printf("%i\n", bin("1 1"));
  testBitGetters();
  printf("\n");
  testBarrelShifter();
  return 0;
}