Eroxl's Notes
Assignment 1 - Numbers and Memory

Problem 1

You can get a UNIX Command Line (i.e., a shell) in one of the following ways:

  1. If you run Mac or Linux you can get a shell directly on your computer via the built-in terminal app.
  2. If you run a recent version of Windows 10, you can install the Windows Subsystem for Linux (WSL, aka Bash on Windows), which provides a usable Linux environment with a shell.

If you do it locally you will need to setup Java by installing the Java JDK.

Pick your environment. Then do the following.

  1. Create a file called HelloWorld.java and edit it so that it will print "Hello World" when it runs. You'll do this by creating a static method called main that prints that string.
  2. Compile this class from the command line using the javac command.
  3. Run this class from the command line using the java command.

Once you are confident that your program runs as expected, submit the HelloWorld.java file below. The main goal in this question is to help you understand how to submit your code, and what to expect from the interface once you submit code.

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello, World!");
    }
}

Problem 2

Consider the following representation of a portion of a memory system, corresponding to all addresses in the range of 0xf300 to 0xf3ff.

Address

Address _0 _1 _2 _3 _4 _5 _6 _7 _8 _9 _a _b _c _d _e _f
f30_ 94 CA 87 16 51 70 59 FC D6 F8 D7 20 7F 29 B6 40
f31_ 61 57 FA F5 19 1D F6 A2 35 C0 12 98 AC 30 18 F7
f32_ C9 7E 56 51 A8 B1 26 D5 11 21 7E CB 2C 8F 40 CD
f33_ 6A AF 11 23 6C 90 E7 F6 F3 90 9C 92 B7 38 2D 9A
f34_ 48 85 D5 EC 40 C6 C7 3D E0 C1 8C 7B A9 47 EE 4A
f35_ 4B E3 38 AD 59 92 50 8F E7 7D 55 E8 9F DC AB B0
f36_ 21 CA 9F 9D 88 D9 6A AD 51 31 BB 8D E3 4D C6 7C
f37_ A0 6D AD A6 2D A8 AA 51 2B 35 56 44 61 D0 67 E1
f38_ 3E 66 61 2E E2 FC 31 24 4E 5C 89 2F A0 EA 13 F6
f39_ 49 77 D4 99 5F 7B 7C 5D 66 81 84 55 68 F0 4A CF
f3a_ F7 92 E7 31 C0 E7 91 16 22 84 2D 3F D2 6D 39 97
f3b_ 47 D8 A6 B2 38 C1 CA 20 A7 60 68 9B EA DA 97 8D
f3c_ 87 72 F3 5A AE 87 B6 23 2A 9D 83 13 DB 69 63 8D
f3d_ 90 41 D9 65 47 51 99 31 61 D6 E0 69 53 F5 E2 14
f3e_ 32 64 15 1B 84 14 26 BF 48 7E 4A E0 E6 80 C0 E4
f3f_ 9C 12 64 61 E2 C2 8D 44 13 5C 54 5C 4C 1D 43 74

Provide your answers below in hexadecimal format. When expressing your answer do not include a leading 0x (i.e. 0x1234 should be expressed as 1234).

What is the value (in hex) of the little-endian, 4-byte integer stored at location 0xf328?

0xCB 7E 21 11

What is the value (in hex) of the big-endian, 8-byte integer stored at location 0xf3d8?

0x61 D6 E0 69 53 F5 E2 14

Problem 3

Give four distinct examples of 4-byte integers whose big- and little-endian representations are identical.

You may provide your answer in base 10 or base 16, but if your answer is in base 16, you must include the 0x prefix.

0x00000000
0x11111111
0x22222222
0x33333333

Problem 4

The Hubble Space Telescope labels the image data it collects with sky positions using right ascension / declination coordinates. It downloads this data as binary files that are accessible on the Internet. You've decided that you'd like to take an up-close look at a specific star whose position is RA (right ascension) 20h 47m 54.5s, D (declination) -22° 59' 6.4''.

Hubble image files encode position coordinates using two 4-byte integers, one for right ascension and the other for declination. And so the position of the star you choose would be labeled as RA=748745 and D=-827464.

So you write a program to download a portion of the Hubble dataset and search it for images containing these coordinates. You discover, however, that Hubble apparently never took any images of your star. You call the head of NASA to complain bitterly. She tells you that they have taken thousands of pictures of that star and suggest that perhaps you are an idiot.

Then you note that the computer on the Hubble that generated the coordinates is the DF-224 manufactured by Rockwell Autonetics in the 1980's and the computer on which your program is running uses an Intel Core i7 processor that you recently purchased — and then you realize that something you learned in CPSC 213 might actually be useful.

HINT: Use a calculator or a program to convert the numbers 748745 and -827464 to hex. Then think about how you might need to manipulate these hex values. Recall that to print the hex value of a number in Java:

System.out.printf("0x%x\n", i);

What are the correct values of the two integers that you should use in your program to search for images of your star? Provide your answer in base 16.

  • 0xC96C0B00
  • 0xB85FF3FF

Problem 5

Download the file Endianness.java. It contains the skeleton of an executable Java class in the file Endianness.java. Place this file directory on a UNIX machine (e.g., one of the lab machines, a Mac, or Windows running Cygwin/WSL) and compile it from the UNIX command line like this:

javac Endianness.java

You can now run this program from the command line. The program takes four command-line arguments. These arguments are the values of four consecutive bytes (in hex) of memory from which the program will construct both big-endian and the little-endian integers. For example, to see the value of the integer whose byte values are 0x01, 0x02, 0x03, and 0x04, in that order, you would type:

java Endianness 01 02 03 04

Write the code that transforms this memory into integers by replacing the TODO's with an implementation of bigEndianValue and littleEndianValue.

Important Note: You must write these two methods using only the Java built-in types and their operators (i.e., + - & | >> >>> <<). You may not use any part of the Java library.

import static java.lang.System.out;

public class Endianness {

  public static int bigEndianValue (Byte[] mem) {
    return mem[0] << 24 | (mem[1] & 0xFF) << 16 | (mem[2] & 0xFF) << 8 | (mem[3] & 0xFF);
  }
  
  public static int littleEndianValue (Byte[] mem) {
    return mem[3] << 24 | (mem[2] & 0xFF) << 16 | (mem[1] & 0xFF) << 8 | (mem[0] & 0xFF);
  }
  
  public static void main (String[] args) {
    Byte mem[] = new Byte[4];
    try {
      for (int i=0; i<4; i++)
        mem [i] = Integer.valueOf (args[i], 16) .byteValue();
    } catch (Exception e) {
      out.printf ("usage: java Endianness n0 n1 n2 n3\n");
      out.printf ("where: n0..n3 are byte values in memory at addresses 0..3 respectively, in hex (no 0x).\n");
      return;
    }
  
    int bi = bigEndianValue    (mem);
    int li = littleEndianValue (mem);
    
    out.printf ("Memory Contents\n");
    out.printf ("  Addr   Value\n");
    for (int i=0; i<4; i++)
      out.printf ("  %3d:   0x%-5x\n", i, mem[i]);
    out.printf ("The big    endian integer value at address 0 is %d\n", bi);
    out.printf ("The little endian integer value at address 0 is %d\n", li);
  }
}

Problem 6

To test your Endianness function, what 32-bit hexadecimal integer input could we use to achieve the desired result below? Do not have any spaces in your input

Little Endian and Big Endian Negative Number

0xff0000ff

Little Endian and Big Endian Positive Number

0x00F00000

Little Endian Negative Number and Big Endian Positive Number

0x000000F0

Little Endian Positive Number and Big Endian Negative Number

0xF0000000

Little Endian and Big Endian equal value

0xF0000000

Problem 7

Like a real processor, the simulator has a memory and a CPU. You will implement both of them as Java classes. This week you will implement the memory.

Some portions of the memory are already implemented. Your job is to implement and test the five methods of MainMemory.java labeled with TODOs. You will find this file in your IntelliJ environment in the arch.sm213.machine.student package. (Please refer to Question 2 "Install the Simple Machine" for the package.)

Implement the following methods:

  • isAccessAligned that determines whether an address is aligned. Be careful not to make assumptions that are not given in the specification (e.g. it doesn't require the length to be a power of 2).
  • bytestoInteger and integerToBytes that translate between an array of bytes and a big endian integer.
  • get and set that provide array-of-byte access to memory used by the CPU to fetch and to store data. Follow the specification listed in the javadoc comments carefully. Note, for example, that the address provided to these methods is not required to be aligned.
package arch.sm213.machine.student;

import machine.AbstractMainMemory;


/**
 * Main Memory of Simple CPU.
 *
 * Provides an abstraction of main memory (DRAM).
 */

public class MainMemory extends AbstractMainMemory {
  private byte [] mem;
  
  /**
   * Allocate memory.
   * @param byteCapacity size of memory in bytes.
   */
  public MainMemory (int byteCapacity) {
    mem = new byte [byteCapacity];
  }
  
  /**
   * Determine whether an address is aligned to specified length.
   * @param address memory address.
   * @param length byte length.
   * @return true iff address is aligned to length.
   */
  @Override public boolean isAccessAligned (int address, int length) {
    return (address % length) == 0;
  }
  
  /**
   * Convert an sequence of four bytes into a Big Endian integer.
   * @param byteAtAddrPlus0 value of byte with lowest memory address (base address).
   * @param byteAtAddrPlus1 value of byte at base address plus 1.
   * @param byteAtAddrPlus2 value of byte at base address plus 2.
   * @param byteAtAddrPlus3 value of byte at base address plus 3 (highest memory address).
   * @return Big Endian integer formed by these four bytes.
   */
  @Override public int bytesToInteger (byte byteAtAddrPlus0, byte byteAtAddrPlus1, byte byteAtAddrPlus2, byte byteAtAddrPlus3) {
    return ((byteAtAddrPlus0 & 0xFF) << 24) | 
           ((byteAtAddrPlus1 & 0xFF) << 16) | 
           ((byteAtAddrPlus2 & 0xFF) << 8)  | 
           (byteAtAddrPlus3 & 0xFF);
  }
  
  /**
   * Convert a Big Endian integer into an array of 4 bytes organized by memory address.
   * @param  i an Big Endian integer.
   * @return an array of byte where [0] is value of low-address byte of the number etc.
   */
  @Override public byte[] integerToBytes (int i) {
    byte[] bytes = new byte[4];
    
    bytes[0] = (byte) ((i >> 24) & 0xFF);
    bytes[1] = (byte) ((i >> 16) & 0xFF);
    bytes[2] = (byte) ((i >> 8) & 0xFF);
    bytes[3] = (byte) (i & 0xFF);
   
    return bytes;
  }
  
  /**
   * Fetch a sequence of bytes from memory.
   * @param address address of the first byte to fetch.
   * @param length  number of bytes to fetch.
   * @throws InvalidAddressException  if any address in the range address to address+length-1 is invalid.
   * @return an array of byte where [0] is memory value at address, [1] is memory value at address+1 etc.
   */
  @Override public byte[] get (int address, int length) throws InvalidAddressException {
    byte[] bytes = new byte[length];

    for (int i = 0; i < length; i++) {
      if (address + i < 0 || address + i >= mem.length) {
        throw new InvalidAddressException(address + i);
      }

      bytes[i] = mem[address + i];
    }

    return bytes;
  }
  
  /**
   * Store a sequence of bytes into memory.
   * @param  address                  address of the first byte in memory to recieve the specified value.
   * @param  value                    an array of byte values to store in memory at the specified address.
   * @throws InvalidAddressException  if any address in the range address to address+value.length-1 is invalid.
   */
  @Override public void set (int address, byte[] value) throws InvalidAddressException {
    for (int i = 0; i < value.length; i++) {
      if (address + i < 0 || address + i >= mem.length) {
        throw new InvalidAddressException(address + i);
      }
      
      mem[address + i] = value[i];
    }
  }
  
  /**
   * Determine the size of memory.
   * @return the number of bytes allocated to this memory.
   */
  @Override public int length () {
    return mem.length;
  }
}

Problem 8

Create a set of JUnit tests to test your implementation. Place all of your tests in a class named MainMemoryTest in the same package as the MainMemory class. Note that you will not actually be able to run the simulator itself yet beyond the initial screen, because you will still lack a CPU implementation.

Ensure that your tests provide good test coverage for each of the five methods you implemented. Comment each test to explain what it is testing.

package arch.sm213.machine.student;

import static org.junit.jupiter.api.Assertions.*;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;
import machine.AbstractMainMemory;

public class MainMemoryTest {
    
    private MainMemory memory;
    private static final int MEMORY_SIZE = 1024;
    
    @BeforeEach
    public void setUp() {
        memory = new MainMemory(MEMORY_SIZE);
    }
    
    @Test
    public void testIsAccessAligned() {
        // Aligned addresses
        assertTrue(memory.isAccessAligned(0, 4));
        assertTrue(memory.isAccessAligned(16, 4));
        assertTrue(memory.isAccessAligned(0, 1));
        assertTrue(memory.isAccessAligned(123, 1));

        // Unaligned addresses
        assertFalse(memory.isAccessAligned(2, 4));
        assertFalse(memory.isAccessAligned(3, 4));
    }
    
    @Test
    public void testBytesToInteger() {
        // Test typical case
        int resultZero = memory.bytesToInteger((byte) 0x00, (byte) 0x00, (byte) 0x00, (byte) 0x00);
        assertEquals(0, resultZero);

        // Make sure negative numbers are handled correctly
        int resultMax = memory.bytesToInteger((byte) 0xFF, (byte) 0xFF, (byte) 0xFF, (byte) 0xFF);
        assertEquals(-1, resultMax); // 0xFFFFFFFF is -1 in signed int

        // Ensure correct byte order
        int resultMixed = memory.bytesToInteger((byte) 0x12, (byte) 0x34, (byte) 0x56, (byte) 0x78);
        assertEquals(0x12345678, resultMixed);
    }

    @Test
    public void testIntegerToBytes() {
        // Test typical case
        byte[] bytesZero = memory.integerToBytes(0x00000000);
        assertArrayEquals(new byte[] {0x00, 0x00, 0x00, 0x00}, bytesZero);

        // Make sure negative numbers are handled correctly
        byte[] bytesMax = memory.integerToBytes(0xffffffff);
        assertArrayEquals(new byte[] {(byte) 0xFF, (byte) 0xFF, (byte) 0xFF, (byte) 0xFF}, bytesMax);

        // Ensure correct byte order
        byte[] bytesMixed = memory.integerToBytes(0x12345678);
        assertArrayEquals(new byte[] {0x12, 0x34, 0x56, 0x78}, bytesMixed);
    }

    @Test
    public void testGetAndSet() throws AbstractMainMemory.InvalidAddressException {
        byte[] dataToWrite = new byte[] {0x10, 0x20, 0x30, 0x40};
        int address = 100;
        memory.set(address, dataToWrite);
        byte[] dataRead = memory.get(address, dataToWrite.length);
        assertArrayEquals(dataToWrite, dataRead);

        assertThrows(AbstractMainMemory.InvalidAddressException.class, () -> {
            memory.get(MEMORY_SIZE + 1, 4);
        });

        assertThrows(AbstractMainMemory.InvalidAddressException.class, () -> {
            memory.set(MEMORY_SIZE - 2, new byte[] {0x01, 0x02, 0x03});
        });

        assertThrows(AbstractMainMemory.InvalidAddressException.class, () -> {
            memory.get(-1, 4);
        });

        assertThrows(AbstractMainMemory.InvalidAddressException.class, () -> {
            memory.set(-10, new byte[] {0x01, 0x02});
        });
    }
}