” COMP 2012 写作、 辅导Programming编程2021/3/21 COMP 2012 Assignment 2: Assembly EmulatorCOMP 2012 Object-Oriented Programming and DataStructuresAssignment 2 Assembly EmulatorIntroductionIn this assignment, You will be practicing the following concepts:InheritancePolymorphismPointers and ReferencesAbstract Base ClassUpdate (Mar 20 0030):Since some students have issues with the library archiveversion of the assignment, we will switch to using the source-only version from nowon. Please check the Download section for the latest skeleton code.For those of you who have already started the assignment, you can download the newskeleton code, and copy-paste the AST.h and InstructionAST.cpp directly into the newskeleton code.The recording of the briefing session can be found here, and the accompanying slidescan be found here.We value academic integrity very highly. Please read the Honor Code section on our coursewebpage to make sure you Understand what is considered as plagiarism and what thepenalties are. The following are some of the highlights:Do NOT try your luck – we use sophisticated plagiarism detection software to findcheaters. We also review codes for potential cases manually.The penalty (for BOTH the copier and the copiee) is not just getting a zero in yourassignment. Please read the Honor Code thoroughly.Serious offenders will fail the course immediately, and there may be additionaldisciplinary actions from the department and university, upto and including expulsion.GlossaryMenuIntroductionGlossaryBackgroundAssignment DetailsDownloadSample Output andGrading SchemePA2 QA on PiazzaSubmission DeadlineFAQPage Maintained byMAK, Ching Hang(David)Email:chmakac@connect.ust.hkLast Modified:03/21/2021 184956HomepageCourse Homepage2021/3/21 COMP 2012 Assignment 2: Assembly Emulator httpss://course.cse.ust.hk/comp2012/assignments/assignment2/ 2/15This section will mainly cover the key terminology used in the rest of this description.Assembly LanguageAssembly language generally refer to low-level programming languages which can bemapped one-to-one to instructions understood by your processor. Unlike C++ (which needsto be compiled), assembly can be directly executed on your processor; In fact, C++ iscompiled into assembly.Instruction Set ArchitectureAn Instruction Set Architecture (or ISA for short) is a definition of the internals of aprocessors. This usually includes the list of instructions the architecture needs to support,how memory should be addressed, and how many and what kind of registers must bepresent.Currently, most desktop and laptop computers use x86-64 (developed by Intel andaugmented by AMD), whereas most mobile devices use AArch64 (developed by ARM).Those of you who have taken COMP2611 will also know MIPS.OpcodeOpcodes (Operation code) are names for instructions which describe what the operationdoes. You can think of an opcode as a function name in C++.OperandOperands are Parts of an instruction which specifies the input/output of the instruction. Youcan think of each instruction as a function call in C++; the operands will then be thefunctions formal parameters (arguments).RegisterRegisters are small chunks of very fast memory residing within the processor; Instructionsusually operate on registers.StackA program stack is a chunk of memory which stores variables within a function.Abstract Syntax Tree (AST)An abstract syntax tree is a tree which represents the syntactic structure of an expression.For example, the instruction mov r11, sp will generate the following AST:MovInstruction|-RegisterOperand r11|-RegisterOperand sp/r13Since mov is an instruction which has two operands, under MovInstruction there are twoRegisterOperands.The following shows a table of corresponding concepts between our flavor of assembly andC++.Assembly C++Opcode Function NameInstruction Function CallOperands Formal Parameters (Arguments)Register A 32-bit memory residing within the processor.2021/3/21 COMP 2012 Assignment 2: Assembly Emulator httpss://course.cse.ust.hk/comp2012/assignments/assignment2/ 3/15Background: Emulators ProcessorsIn this assignment, you will be implementing a small part of an ARM emulator. Emulation isusually used when you want your machine to pretend to be another machine. For example,mobile application developers use emulators to run a version of Android or iOS on their localmachine for Development.Since an emulator is effectively a software processor, we will need to replicate some partsof the processor in our emulator.Note: You do not need to implement everything stated below, it is just an overview foryou to understand the parts that have been implemented for you (and that you willneed to use).Assembly?As you may know, your compiler compiles C++ source code into assembly code. Since theflavor of assembly is depedent on the processor it is executed on, different compilers ondifferent platforms running different processors will generate different assembly code.To demonstrate this example, consider the following C++ snippet.This will be compiled to the following ARMv7-A assembly (the ISA we will be emulating).Note that @ are comments, similar to // in C++:getInt():mov r0, #0 @ Set 0 as the return valuebx lr @ Return from getInt()main:push {lr} @ Store the link-register into the stack;@ lr will be overwritten in the nextinstructionbl getInt() @ Call getInt; Return value will be in r0add r0, r0, #1 @ Add 1 to the value returned by getInt()pop {lr} @ Load the link-register from the stack@ This is to ensure we return to thecorrect locationbx lr @ Return from main()As you can see, a lot of operations are actually similar between C++ and Assembly, althoughAssembly language is significantly more verbose. There are a lot more things you need to do,for example, spilling register to the stack if we are jumping between functions, and manyone-liners in C++ are now done with multiple instructions.Dont worry if you dont understand what each instruction means or does in the aboveexample. More detailed explanation will be given in the latter parts of this description.InstructionsThe most important Functionality of a processor is to perform some work; These actionsare usually represented in processors as instructions. Instructions are single specific actionswhich a processor is able to perform.In assembly programs, instructions are usually represented as an opcode and operands. Anopcode is a name for an instruction, whereas operands are things that an instructionoperate on.int getInt() { return 0; }int main() {return getInt() + 1;2021/3/21 COMP 2012 Assignment 2: Assembly Emulator httpss://course.cse.ust.hk/comp2012/assignments/assignment2/ 4/15For example, consider the following example:add r1, r0, #1add r1, r0, #1 represents an instruction.add is the opcode.r1, r0, #1 are all operands to the instruction.Translating this to C++, this would be equivalent to:void add(Register op1, const Register op2, unsigned op3);add(r1, r0, 1);In other words, using C++ terminology:Opcodes are function names.Instructions are function calls.Operands are formal parameters (arguments).In the above Example, you will see that the first two operands are prefixed with r, whereasthe third operand is prefixed with #. These denote different types of operands.r-prefixed operands represent registers (see below).#-prefixed operands represent immediates, i.e. constant values.Operands enclosed in square brackets ([]) represent indirect operands, i.e. adereferenced memory location.For example, the operand [r0, #4] refers to the memory location pointed to byregister r0, offset by 4 (i.e. *((char*) r0 + 4) in C++).Operands enclosed in curly brackets ({}) represent register lists, i.e. a non-empty listof registers.For example, the operand {r11, sp} represents a register list containing the registersr11 and sp.In our emulator, operands are implemented as classes in OperandAST.h.Note: Operand classes and their implementation are provided to you; You do not needto do anything.RegistersWhile in C++ we have learned to see variables as bytes which have memory addresses,accessing the main memory from the processor is actually slow (approximately 10seconds). While this may sound fast, a modern processor clocks at up to 5GHz, meaningthat the same time used to access main memory can also be used to execute up to 500instructions!Enter the register. Registers are super-fast memory that resides on the processor itself, andusually takes 1 clock cycle (i.e. 10 seconds) to access. This is why most instructions tendto use registers as their operands, as they are super-fast and therefore the processor can domore work instead of waiting for data to come around.Most Instruction Sets these days will say how many registers the instruction set needs tosupport and what size each register should be. Our emulator is loosely based on ARMv7-A,so we will have 16 registers, each 32 bits wide.Of note in these 16 registers:r0 is usually used to store the return value of a function.r13 (also known as sp) is the stack pointer; See the below section.r14 (also known as lr) is The link register. The link register stores which instruction theprocessor should jump to when this function returns.r15 (also known as pc) is the program counter. The program counter stores the nextinstruction the processor should execute.-7-92021/3/21 COMP 2012 Assignment 2: Assembly Emulator httpss://course.cse.ust.hk/comp2012/assignments/assignment2/ 5/15In our emulator, you can obtain a register using u32 Processor::getRegister(u8 reg),where reg is the register index you want to access.Note: The implementation for the registers are provided to you.Stack MemoryIn C++ we always define variables in our function to help us implement our programs, and weknow that our variables are generally allocated on the stack. What is the stack then?A stack data structure (as you may recall from COMP2011) is a data structure which enablesLIFO (Last In, First Out) behavior. This same principle can be applied to variables withinfunctions.In assembly code, we generally use the stack as a backing store when there are notenough registers to store the variables in our program.Important: When the stack grows, the memory address decreases; When the stackshrinks, the memory address increases. In other words, the last-in variables arestored in lower (smaller) addresses, whereas first-in variables are stored in higher(bigger) addresses.In our emulator, you can access the stack memory using void MemStack::store(u32 value,u32 addr) and u32 MemStack::load(u32 addr) to store into and load from the stackmemory respectively.Note: The implementation for Stack Memory is provided to you; You do not need to doanything.Abstract Syntax TreeAn abstract syntax tree (AST) is a Tree used to display the syntactical structure of a program.The benefit of using ASTs is that the meaning of each instruction (and the entire program)becomes unambiguous, making it easy to write what each instruction does.In our emulator, all AST nodes are derived from the base class AST (which you will need towrite). All derived AST classes are suffixed with AST.Library ArchiveSince an emulator is very complex, we have already written some parts of the emulator foryou. These parts are distributed as a part of an archive file (.a)An archive file is generally used when distributing libraries (i.e. a bundle of C++ functions forexternal use).Assignment DetailsSince an emulator is very complex, we have already written some parts of the emulator foryou. These parts are distributed as a part of an archive file (.a). There are 15 classes you willneed to implement in 1 cpp file (around 250 lines), and 1 header file you will need to write.Generated documentation for the header files can be found here.Custom Integer Data TypesUnlike software, hardware often have more specific data type size requirements; Forexample, the Instruction Set we are emulating explicitly states that registers must be 32 bitswide. However, as mentioned in COMP2011, int and other data types in C++ only have aminimum size requirement (e.g. int must be at least 16 bits). Therefore, we have providedsome custom data types which are guaranteed to have fixed sizes across all platforms.2021/3/21 COMP 2012 Assignment 2: Assembly Emulator httpss://course.cse.ust.hk/comp2012/assignments/assignment2/ 6/15These data types are Defined as {s/u}{bits}, where s means its a signed integer, u meansits an unsigned integer, and bits is the number of bits of the data type (8/16/32/64 aredefined). Therefore, for example, u32 represents unsigned 32-bit integer, and s16 representssigned 16-bit integer.These data types are defined in Util.h.Unsigned Overflow BehaviorWhile you have learned the difference between signed and unsigned integers in COMP2011,there are other intricacies regarding these data types (which are relevant to thisassignment).In the C++ standard, signed integer overflow is undefined behavior, meaning that there areno guarantees what will happen. A notorious example is:One may assume that if i is the largest number representable by int, i + 1 will overflow andmust wraparound (i.e. become 0) and thus this works to check whether an overflow mayoccur. However, since this is undefined behavior, a compiler implementation may optimize itlike this:In a mathematical point-of-view, this makes a lot of sense; In fact, recent versions of GCCand Clang do perform this kind of optimization, as how can adding one to a value be smallerthan the value itself?This brings us to a special property of unsigned arithmetic operations: overflows willalways wraparound. In other words, it is guaranteed by the standard that adding one to thelargest unsigned number of the data type will always wraparound to 0, and subtracting 1from 0 will always wraparound to the largest unsigned number.In addition, given a (twos-complement) signed and an unsigned number with the same bitrepresentation,performing arithmetic operations on either number will return the sameresult; In other words:These properties may be useful when implementing addition and subtraction operations.Source Files to ImplementWithin the 15 classes, there are generally 4 types of functions to implement.Constructor: Implement the constructor of the class.Destructor: Implement the Destructor of the class.Accessors: Implement the accessors of the class; They may return a pointer or areference depending on whether the value is optional or not.bool checkOverflow(int i) {return i (i + 1);bool checkOverflow(int i) {return false;int lhs = 1;int rhs = -2;int sum = lhs + rhs;// For demonstration purposes only; This is not technicallycorrect.int uSum = static_castint(static_castunsigned(lhs) +static_castunsigned(rhs));sum == uSum;2021/3/21 COMP 2012 Assignment 2: Assembly Emulator httpss://course.cse.ust.hk/comp2012/assignments/assignment2/ 7/15eval(Processor processor): Implement the evaluation function of the class; Thisexecutes what is specified by the instruction on the Processor instance passed as areference parameter.Note that if the dummy implementation is not provided to you in InstructionAST.cpp, thefunction has been implemented for you in the library archive.The description for each instruction is briefly described below; Refer to the header files formore information.nop (NopInstructionAST): Does nothing.mov (MovInstructionAST): Copies the Value of a register or constant into anotherregister.mDst: The destination register to copy to.mSrc: The source register to copy from. (Only applicable toRegMovInstructionAST).mImm: The 32-bit value to copy from. (Only applicable to ImmMovInstructionAST).For example:mov r1, r0 copies the value of register r0 into register r1.mov r1, #1 copies the value 1 into register r1.str (StrInstructionAST): Stores the value of a register onto the stack.mSrc: The register whose content needs to be stored.mDst: The memory location to store the register content to.For example:str r0, [r1] stores the value of register r0 into the memory address pointed toby r1.str r0, [r1, #8] stores the value of register r0 into the memory addresspointed to by r1, additionally offseting the memory address by 8 bytes.ldr (LdrInstructionAST): Loads a value from the stack into a register.mDst: The register to load to.mSrc: The memory location to load the register content from.For example:ldr r0, [r1] loads into the register r0 by reading from the memory addresspointed to by r1.ldr r0, [r1, #8] loads into the register r0 by reading from the memory addresspointed to by r1, additionally offseting the memory address by 8 bytes.push (PushInstructionAST): Stores the values of the specified registers onto the stack,and shifts the stack pointer.mRegList: The list of registers whose content needs to be stored into the stack.For example:push {r11, sp} decrements the Stack pointer by 8 bytes (2 32-bit registers),then stores the value of register r11 and register sp into the memory pointed toby sp, with r11 storing in a lower (i.e. smaller) memory address than sp.pop (PopInstructionAST): Loads the values from the stack into the specified registers,and shifts the stack pointer.mRegList: The list of registers whose content needs to be loaded from the stack.For example:pop {r11, sp} loads the value of the register r11 and register sp by reading fromthe memory address pointed to by sp, with r11 reading from a lower (i.e. smaller)memory address, then incrementing the stack pointer by 8 bytes (2 32-bitregisters).add (AddInstructionAST): Adds the value of the two operands and stores into aregister.mDst: The destination register to store the result to.mSrc1: The register of the first operand.mSrc2: The register of the second operand. (Only applicable toRegAddInstructionAST).2021/3/21 COMP 2012 Assignment 2: Assembly Emulator httpss://course.cse.ust.hk/comp2012/assignments/assignment2/ 8/15mImm: A 32-bit value as the second operand. (Only applicable toImmAddInstructionAST).For example:add r1, r1, r0 adds the value of Registers r1 and r0, then stores the result inregister r1.add r1, r1, #1 adds the value of register r1 with the constant value 1, thenstores the result in register r1.sub (SubInstructionAST): Subtracts the value of the second operand from the firstoperand and stores into a register.mDst: The destination register to store the result to.mSrc1: The register of the first operand.mSrc2: The register of the second operand. (Only applicable toRegSubInstructionAST).mImm: A 32-bit value as the second operand. (Only applicable toImmSubInstructionAST).For example:sub r1, r1, r0 subtracts the value of register r0 from register r1, then storesthe result in register r1.sub r1, r1, #1 subtracts the constant value 1 from the register r1, then storesthe result in register r1.Header FilesYou will also need to implement the header file for the abstract base class of AST andExprAST. AST is the abstract base class for all AST nodes, and ExprAST is the abstract baseclass for AST nodes which represent an expression.For AST, the class must satisify the following requirements:There is a virtual destructor with an empty function body.There is a const pure virtual function getTokenName which returns const char*.There is a const pure virtual function print which accepts a parameter indent oftype u32 and returns void.For ExprAST, the class must satisify the following requirements:The class should inherit from AST.There is a virtual destructor With an empty function body.There is a const pure virtual function getTokenName which returns const char*.There is a const virtual function print which accepts a parameter indent of type u32and returns void.Note that you do not need to implement ExprAST::print(u32); This has been implementedfor you as part of the library archive.Other Implemented ClassesYou can refer to the generated documentation for a description of classes alreadyimplemented for youUseful Implemented FunctionsTo aid you in your implementation, we have written the rest of the emulator for you. Below isa list of possibly useful functions that you may need to use.u32 Processor::getRegister(u8): Obtains a reference to the specified register.MemStack Processor::getStack(): Obtains a reference to the stack memory.All public member functions in OperandAST.hUseful Debugging Functions2021/3/21 COMP 2012 Assignment 2: Assembly Emulator httpss://course.cse.ust.hk/comp2012/assignments/assignment2/ 9/15To aid you in debugging your code, we have written some helper functions to outputadditional information.Under most circumstances, the Most useful function for debugging is Processor::dump,which outputs the current state of the processor, including instruction to-be-executed, thecurrent register contents, and the current stack contents. A typical output will looksomething like this:Current Instruction:MovInstruction|-RegisterOperand r11|-RegisterOperand sp/r13Registers:r0 0x00000000 [dec:0]r1 0x00000000 [dec:0]r2 0x00000000 [dec:0]r3 0x00000000 [dec:0]r4 0x00000000 [dec:0]r5 0x00000000 [dec:0]r6 0x00000000 [dec:0]r7 0x00000000 [dec:0]r8 0x00000000 [dec:0]r9 0x00000000 [dec:0]r10 0x00000000 [dec:0]r11 0x00000000 [dec:0]r12 0x00000000 [dec:0]sp/r13 0x7ffffff8 [offset:8]lr/r14 0xffffffff [label:reserved instr:0xffff]pc/r15 0x00050002 [label:main instr:0x0002]Stack Memory Contents:[0:0x7fffffff~0x7ffffffc] 0xffffffff[1:0x7ffffffb~0x7ffffff8] 0x00000000Current Instruction: Displays the AST of the instruction to be executed.In this example, the AST shows the equivalent of mov r11, sp.Registers: Displays the current (hexadecimal) values of each register in the processor.The [dec:0] field shows the decimal representation of the register values.sp: The [offset:8] field shows the location of the stack pointer relative to thetop of the stack.In this example, our stack pointer is currently 8 bytes below the top of the stack.lr: The [label:reserved instr:0xffff] fields show the name and instructionoffset of the label when returning from this function.In this example, returning from this function will cause the program to jump to areserved label; Jumping to a reserved label will terminate the program,similar to returning from main.pc: The [label:main instr:0x0002] fields show the name and instruction offsetof the label which will be executed next. Note that label indices start from 0.In this example, the next instruction that will be executed is 2nd instruction in themain label.Stack Memory Contents: Displays the current (hexadecimal) values present in thestack. Note that this will only show values up to the current location of the stackpointer.The first number in the Square brackets (0) shows the index of the value relativeto the top of the stack.The hexadecimal range in the square brackets (0x7fffffff~0x7ffffffc) showsthe memory range which the value occupies.The hexadecimal outside the square brackets shows the current value of thememory range.In our example, our stack would then look something like this:2021/3/21 COMP 2012 Assignment 2: Assembly Emulator httpss://course.cse.ust.hk/comp2012/assignments/assignment2/ 10/15Top of Stack—————-| | 0x7fffffff| 0xffffffff || | 0x7ffffffc|————–|| | 0x7ffffffb| 0x00000000 || | 0x7ffffff8—————- — stack pointer (0x7ffffff8)You may also set the first parameter of the constructor (Processor::Processor(bool)) totrue to enable outputting the processor state on every instruction.There are also Functions to only print the state of the memory stack (MemStack::dump) andthe AST of the current instruction (AST::print) or program (Program::printAST).Testing Your ProgramSince you are not expected to write assembly for this course, we have provided a smallnumber of assembly programs for your to test your program. These programs are inmain.cpp of the skeleton code.In addition, you may also compile your own assembly programs using Compiler Explorer,which is a tool to inspect the assembly code generated by compilers. You can type a C++program on the left-hand side pane., and it will generate assembly on the right-hand sidepane.Note that there are several limitations.Only a very small subset of instructions are supported by our emulator. If you see themessage Unknown instruction in the program, that means that the specifiedinstruction is not supported by our emulator.Most of the functions in the C++ standard library are not supported.Allocating to the heap (i.e. new and delete) is not supported.As such, we suggest writing programs which (1) do not need to include any headers, (2) onlyperforms stack allocation, (3) does not have any struct or class. Branch instructions havebeen implemented for you, so conditional statements and loops are also supported.This assignment uses additional C++ features and/or paradigms which are not covered inclass.Pointer OwnershipIn class, you will have learned that in most cases, a class which allocates memory from theheap should be responsible for freeing it. This is generally referred to pointer ownership,where the responsibility of managing the pointer (including freeing it) lies within the class.However, sometimes the ownership of pointers may be transferred to other classes orvariables. Take the following example:You will notice that if we Dont delete ptr in line 6, we will have created a memory leak.However, it is impossible for createInt to free the pointer either, because there is nomechanism for doing so!int* createInt(int i) { return new int{i}; }int main() {int* ptr = createInt(2);int ret = *ptr;delete ptr;return ret;2021/3/21 COMP 2012 Assignment 2: Assembly Emulator httpss://course.cse.ust.hk/comp2012/assignments/assignment2/ 11/15In this case, we say that the ownership of the heap-allocated memory (referenced by thevariable ptr) is transferred to the caller of createInt, meaning that it is now theresponsibility of the main function to call delete on ptr.In our assignment, all constructor parameters will have their ownership transferred to yourclass, meaning that you will need to call delete on these pointers on destruction.Pointer-to-ImplementationThroughout the provided classes, you will see a common coding pattern similar to this:This paradigm is called pointer to implementation (or pImpl for short). The benefit of usingthis paradigm is that since the real implementation (including data members) are hidden in acpp file, you do not need to change the class definition in the header file when adding,changing, or removing members, meaning that there is no need to recompile files whichdepend on the class definition.You can read more about this here.Anonymous NamespacesAnonymous namespaces have the same effect as declaring static for a global variable: Itrestricts the variable to have internal linkage, i.e. the variable is only visible within the sameC++ source file.For more details, please refer to the self-study notes.Raw String LiteralsIn the provided main.cpp and AssemblyProgram.cpp, you will see some usages of R().This syntax (introduced in C++11) is called a raw string literal, and it is used when you wantto treat the entire String as-is. As an example:This is very convenient when you want to copy-and-paste a multiline string without adding\n yourself.Function PointerIn AssemblyProgram.cpp, you will see a function with the following prototype:bool testProgram(const std::string input,void(* setup)(Processor),u32 expected,u32(* actualExpr)(const Processor),\”
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
