Lab 8 – Treasure Hunt ECE 375 ECE 375: Computer Organization and Assembly Language Programming Lab 8 – Treasure Hunt SECTION OVERVIEW Complete the following objectives: Use your knowledge of computer organization and assembly programming to implement non-trivial mathematical formulas. Interpreting data that is not byte-aligned. PRELAB If you consult any online sources to help answer the prelab questions, you must list them as references in your prelab. 1. In this lab, you will be utilizing the Pythagorean theorem to compute dis- tances. Assuming you are working with the Cartesian coordinate system, what is the mathematical expression to measure the distance between the following two points? (X1, Y1) and (X2, Y2) 2. The AVR instruction set includes support for primitive mathematical oper- ations such as addition, subtraction, and multiplication. However, there are times when we want to perform more advanced mathematical calculations. Write pseudocode to compute the square root of a number using only the mathematical operators that are supported by the AVR instruction set. If the number is not a perfect square, round the answer upwards to the nearest integer. For example, sqrt(5) = 2.236... but for our purposes the answer is 3. 3. What is the difference between integer arithmetic and floating point arith- metic? BACKGROUND As previous labs have demonstrated, microcontrollers are well-suited for a wide variety of tasks. Earlier labs have involved I/O, arithmetic and logic compu- tations, and usage of the timer/counter modules. Prior to this point, we have implemented 16 bit and 24 bit arithmetic using the 8 bit mathematical instruc- tions that are included as part of the AVR instruction set. In this lab you will implement an algorithm to perform more complex computations on the AT- mega128. There are times when a microcontroller needs to process data that is in a “less than desirable” format. Modern CPUs read and write data most efficiently when the content of memory is aligned in such a way that it can be directly accessed via a pointer. In the case of the ATmega128, we can use the X, Y, or Z registers to point to individual bytes, so it makes sense to allocate the memory in multiples of bytes, with the data beginning on the “edge” of a byte. In the example below, an 8 bit value is being stored across two bytes. Three bits are in the left byte and five bits are in the right byte. Upper Byte Lower Byte -----XXX XXXXX--- Table 1: This 8 bit value (represented by the X’s) is not byte aligned When possible, we store data so that it is byte-aligned. This is easy to do when the data can be divided into an integer number of bytes. Upper Byte Lower Byte -------- XXXXXXXX Table 2: The 8 bit value is now byte-aligned On the other hand, suppose that you need to store a variable which occupies 10 bits. In this situation, it is very common to expand the size of the variable in order to ensure that the data will be byte-aligned. For example, if the value occupies 10 bits, we will pad the data with six 0’s, thereby treating it as a 16 bit (two byte) value. Upper Byte Lower Byte 000000XX XXXXXXXX Table 3: 10 bit value (padded to occupy 16 bits) Another advantage of this approach is that AVR instructions are generally designed to work with 8 bits at a time, so the assembly code will be easier to ©2020 Oregon State University Fall 2020 Page 1 Lab 8 – Treasure Hunt ECE 375 write if we are working with 16 bits of data instead of 10 bits. The downside of this approach is that padded variables consume excess memory that could have been used for other purposes. In our case we generally assume that memory is plentiful, and the extra padding is seen as a minor inconvenience. However, there are scenarios in which any sort of padding is seen as a serious disadvantage. In particular, network communication between computers is gen- erally focused on transmitting the most amount of data in the smallest amount of time. It is undesirable to waste time and energy transmitting bits that are solely serving as padding. In this situation, it’s common to remove the padding and pack the binary numbers together. For example, if the remote computer wants to transmit three 10 bit values (represented by A, B, and C), they could arrive as shown in Table 4. The question marks indicate bits that are not relevant. Byte 0 Byte 1 Byte 2 Byte 3 AAAAAAAA AABBBBBB BBBBCCCC CCCCCC?? Table 4: Sequence of 10 bit values received from network device In this situation it’s the programmer’s job to parse the information as necessary in order to make it byte-aligned. In this lab we will utilize a similar format. PROCEDURE Problem Statement For this lab, we are going on a treasure hunt. You will be provided with three sets of (X, Y) values, each of which indicates the Cartesian coordinates of a treasure chest. Your primary task is to utilize the Pythagorean theorem and determine which of the three treasure chests is closest to your position. In order to simplify the math, you may assume that the user is located at the origin of the grid (where X = 0 and Y = 0). You will implement other tasks as described in this assignment. You must write your code using the skeleton code that is provided on the lab page. You may not modify any portion of the skeleton code beneath the line that states “Do not change below this point”. Data Format Each of the coordinates is specified using signed 10 bit integer values. Since there are three points, you will be provided with a total of six 10 bit values. The values will be packed together inside an 8 byte program memory location labeled as TreasureInfo. The coordinates of the three treasures will be encoded as follows: Byte 0 Byte 1 Byte 2 Byte 3 AAAAAAAA AABBBBBB BBBBCCCC CCCCCCDD Byte 4 Byte 5 Byte 6 Byte 7 DDDDDDDD EEEEEEEE EEFFFFFF FFFF???? Table 5: Encoding format to indicate the position of the 3 treasures Byte 0 is located at the TreasureInfo label. Assume that the treasure coordi- nates utilize two’s complement representation and that the MSB (most significant bit) is on the left. You should ignore the value of any bits marked with a ‘?’. Table 6 explains how each set of bits is interpreted. Bits Definition AAAAAAAAAA X coordinate of first treasure BBBBBBBBBB Y coordinate of first treasure CCCCCCCCCC X coordinate of second treasure DDDDDDDDDD Y coordinate of second treasure EEEEEEEEEE X coordinate of third treasure FFFFFFFFFF Y coordinate of third treasure Table 6: Interpreting the treasure locations Results As part of your implementation, you will be saving several items into data mem- ory. For all values that occupy more than one byte, use the little-endian rep- resentation (i.e. the least significant byte will be placed at the lowest memory address). It is critical that you follow these instructions as you will not receive credit for answers that are incorrectly stored into memory. Each of the labels mentioned below is already defined in the skeleton code file. Indicate which treasure is closest by storing a value of 1, 2, or 3 into the BestChoice data memory location (one byte signed value). In the special case where all three treasures have an equal (rounded) distance, you will indicate this by storing a value of -1. ©2020 Oregon State University Fall 2020 Page 2 Lab 8 – Treasure Hunt ECE 375 Compute the average distance to a treasure chest and store this value into the AvgDistance data memory location (two byte unsigned value). Note: you can compute the average distance by summing the distance to all three treasures and then dividing the sum by three. You will also save detailed information related to your calculations for each treasure chest. More specifically, within Result1, Result2, and Result3, you will save: 1. The value of x2 + y2 (3 byte unsigned value) 2. The distance to the treasure chest (2 byte unsigned value) Table 7 illustrates the format that is used to store these results. Byte 0 Byte 1 Byte 2 Byte 3 Byte 4 AAAAAAAA AAAAAAAA AAAAAAAA BBBBBBBB BBBBBBBB Table 7: Encoding format that is used to store treasure information. The first three bytes (indicated by A’s) hold the computed value of x2 + y2 and the re- maining two bytes (indicated by B’s) hold the computed distance to the treasure chest. As an example, imagine that the three treasures are located at these coor- dinates: (5, 25), (35, -512), and (0, 511). For each treasure, we compute the following values (which have been rounded upward if the answer was not an integer): – Treasure 1: x2 + y2 = 650, Distance to treasure: 26 – Treasure 2: x2 + y2 = 263369, Distance to treasure: 514 – Treasure 3: x2 + y2 = 261121, Distance to treasure: 511 Utilizing the encoding format from Table 7, these values will be stored as shown in Tables 8-10. Byte 0 Byte 1 Byte 2 Byte 3 Byte 4 10001010 00000010 00000000 00011010 00000000 Table 8: The contents of Result1 for this example (storing 650 and 26) Byte 0 Byte 1 Byte 2 Byte 3 Byte 4 11001001 00000100 00000100 00000010 00000010 Table 9: The contents of Result2 for this example (storing 263369 and 514) Byte 0 Byte 1 Byte 2 Byte 3 Byte 4 00000001 11111100 00000011 11111111 00000001 Table 10: The contents of Result3 for this example (storing 261121 and 511) Important Details You are not required to implement any floating point operations in this lab. Since the values of X and Y are provided as signed 10 bit values, this implies that the minimum value is -512 and the maximum value is 511. The TAs will test your code using a variety of treasure locations, so be sure that you verify proper functionality and test your code. Measure distance “as the crow flies” and utilize the Pythagorean theorem. If the square root is not an integer, round upward to the nearest integer. For example, the distance to (35, -512) should be computed as 514. If the average distance is not an integer, you must again round upward. For example, if the three treasures have distances of 368, 601, and 34, you will record the average distance as 335. You may not utilize a stored table while computing the square root of a number. In order to simplify your work and ease debugging, it’s suggested that you write your code in a modular fashion and heavily utilize procedures. STUDY QUESTIONS / REPORT A full lab write-up is required for this lab. When writing your report, be sure to include a summary that details what you did and why, and explains any problems you encountered. Your write-up and code must be submitted by the end of your final (Week 10) lab session. As usual, NO LATE WORK IS ACCEPTED. ©2020 Oregon State University Fall 2020 Page 3 Lab 8 – Treasure Hunt ECE 375 Study Questions No additional questions for this lab assignment. CHALLENGE In order to earn extra credit, do not assume that the user is located at the origin (0,0). Instead, measure all distances from the user coordinates specified in program memory at the label UserLocation. The X and Y coordinates will be specified as two packed 10 bit values (similar to the treasure locations). Byte 0 Byte 1 Byte 2 XXXXXXXX XXYYYYYY YYYY???? Table 11: Format of initial user location Bits Definition XXXXXXXXXX X coordinate of user (Xuser) YYYYYYYYYY Y coordinate of user (Yuser) Table 12: Interpreting each set of bits in the user location For example, if the user is located at position (28, -274) then UserLocation will be defined with values: UserLocation: .DB 0x07, 0x2E, 0xE0 Important note: if you complete the challenge code you should no longer be storing x2 + y2 into the results for each treasure chest. Instead, you will be storing (xtreasure − xuser)2 + (ytreasure − yuser)2. If you complete the challenge code you only need to submit a single version of your source code which includes this expanded functionality. The TAs will test your code using a variety of user locations. ©2020 Oregon State University Fall 2020 Page 4
欢迎咨询51作业君
