Problem Set 3

Part 1

Describe, using register transfer notation (RTN), the functionality of the following subset of the Intel x86 architecture:

• Instructions: ADD, MOV, SAR, JMP.
• Addressing Modes, using ModR/M: Immediate, Register, Base+Displacement (not SIB).
• Data Types: Double Word (at least one operand must be 32 bits).
• MOV: Do not implement moffs variations, nor Control Register variants.
• You must specify the RTN for each variant of each instruction that meets the previous requirements.

For detailed information about addressing modes/instructions refer to the x86 ISA manuals.

Additional Clarifications:
SIB byte addressing modes are not required for this part of the problem set.
We always use 32-bit addressing, never 16-bit addressing.
We also simplify x86 memory addressing by avoiding the GDT. Any time an instruction accesses memory, you have to build the address based on base+displacement as specified in the Mod R/M byte of the instruction, and add the Segment Register shifted 16 bits. The Segment Register is always DS unless the stack is being accessed (e.g., push and pop instructions or any other instruction using EBP or ESP as the base register) in which case SS is the default. Note that the default Segment Register can also be overridden with a specific instruction prefix (not used in this problem set).

Example

ADD (opcode 81 /0 id): ADD r/m32, imm32

MEM[GPR + SegR<<16] <- MEM[GPR + SegR<<16] + imm32
GPR <- GPR + imm32
MEM[GPR + disp32 + SegR<<16] <- MEM[GPR + disp32 + SegR<<16] + imm32
MEM[GPR + SEXT(disp8) + SegR<<16] <- MEM[GPR + SEXT(disp8) + SegR<<16] + imm32
MEM[disp32 + SegR<<16] <- MEM[disp32 + SegR<<16] + imm32

Helpful links:

• x86 Basic Architecture
• x86 Instruction Set Reference
• x86 System Programming Guide

Part 2

Requirements

Build an instruction-level simulator for a subset of x86 ISA instructions listed below (note that this is a subset different from the one in Part 1).

You must only support user-space, without address translation, and have your simulator be able to run to completion. The address space will be 32 bits and support ModR/M and SIB.

You may use whatever language you want, but your program must be able to be run from one or two terminal commands. One input must be supported for the simulator, mem.txt. Two example terminal commands for running the simulator would look like:

    python3 isl.py mem.txt
  

    g++ isl.cpp -o isl
    ./isl mem.txt
  

Expected Outputs:

The results of this program should be a file called results.txt that displays the following information after each instruction finishes executing:

• EIP register
• All General Purpose Registers (EAX, ECX, EDX, EBX, ESP, EBP, ESI, EDI)
• All MMX registers (MM0-7)
• All Segment Registers (ES, CS, SS, DS, FS, GS)
• All Flags (CF, PF, AF, ZF, SF, DF, OF)

For example, if there are five instructions in the program you are testing, then there should be five print outs of all the information above. While there is no required format for the printing, do try to make it look presentable.

Expected Inputs:

mem.txt will have the format shown below. You are in charge of building into your code a way of loading the instructions in mem.txt into some sort of array for your simulator.

The general format is <address>: <instruction hex>. Do not assume the //<assembly mnemonic> portion shown in the figure above will be present in the input.
Also pay attention to how you're going to support the full 32-bit address space in your simulator without running into issues with size.

For this assignment, we will not be concerned with interrupts or traps/faults for illegal situations. (That comes later!)

List of Instructions to Implement:

• ADD AL, imm8
• ADD AX, imm16
• ADD EAX, imm32
• ADD r/m8, imm8
• ADD r/m16, imm16
• ADD r/m32, imm32
• ADD r/m16, imm8
• ADD r/m32, imm8
• ADD r/m8, r8
• ADD r/m16, r16
• ADD r/m32, r32
• ADD r8, r/m8
• ADD r16, r/m16
• ADD r32, r/m32
• MOVQ mm, mm/m64
• MOV Sreg, r/m16
• XCHG r/m8, r8
• CMPXCHG r/m16, r16
• JMP ptr16:32
• JNE rel32
• HLT - For HALT, simply close all output files and return from the program

List of Prefixes to Implement:

• Operand Size Override (0x66)

What to Submit:

• README.md that contains all the necessary information to run your code and interpret your output
• Source file that implements your simulator

BONUS (25%)

Add support of a 15 bit physical memory with a 32 bit virtual address space. To support this, a second input file will be added, tlb.txt. It will have the format shown below, being an 8 entry TLB. Do not worry about page faults being tested. The first two TLB entries will always be the same, the other six will be set as decided. Whenever a memory address is going to be loaded, you will have to call a virtual to physical conversion. Other than that, the design should be unchanged.

Q&A

• What language should I use? We recommend either python (easier to parse the input files) or cpp (nicer for actually implementing the simulator logic and dealing with bytes).
• How do I calculate a physical address for the bonus? Once you have the final virtual address, it can be computed as follows: {TLB frame number[2:0], virtual address[11:0]}.
• Are any exceptions/interrupts being tested in this assignment? No.
• Can I implement more instructions and prefixes than the listed ones? Yes, it is highly encouraged but not required. It will be useful for debugging your final project. If you want to get an idea of what instructions you could add, we recommend looking at the 2024 course project for Microarchitecture. The instructions used won’t be identical but will get you pointed in the right direction.
• Will mem.txt contain continuous memory locations? No, mem.txt can be in any order (i.e. line 1 is location x300, line 2 is location x15, and line three is location x1200).
• What should registers and EIP be initialized to? All registers and flags should be initialized to 0. For the EIP, it should also be 0. All programs tested will begin at both physical and virtual address 0.
• Do I have to hand assemble test cases? No, we recommend using an online assembler like the following: https://defuse.ca/online-x86-assembler.htm