[SOLVED] CS algorithm assembler compiler OSU CSE 2421

OSU CSE 2421
Required Reading: Computer Systems: A Programmers Perspective, 3rd Edition
Chapter 4, Sections 4.2 through 4.2.2
Chapter 2, Sections 2.3 through 2.3.8
Chapter 8, Section 8.2 through 8.2.4
J.E.Jones

OSU CSE 2421
When examining hexadecimal numbers, as we often do with addresses, we will need to be able to do basic arithmetic operations, such as addition or subtraction when working in assembler.
The principles, of course, are the same as in decimal, but the values of the digits are different (0-F in hex instead of 0-9 in decimal).
Lets look at an example.
J. E. Jones

OSU CSE 2421
Suppose the address of the top of the stack at the beginning of some function is 0x8000.
Suppose that an 8-byte value is pushed onto the stack after the processor starts executing the functions code.
When the value is pushed onto the stack in that function, the address stored in the stack pointer will decrease by 8 bytes. Then, the value to be pushed will be written to that address.
Recall that the stack grows downward in RAM (the addresses decrease as we push more and more values onto the stack).
Therefore, to get the address where the value will be pushed onto the stack, we need to compute 0x8000 0x08.
J. E. Jones

OSU CSE 2421
0x8000 0x????
Some value Store new value here
Higher stack addresses
Lower stack addresses
J. E. Jones

OSU CSE 2421
If we were subtracting in decimal, its easy, right???
Reduce the least significant digit by 8; there must be a borrow from the next most significant digit, so we must reduce the value of the remaining digits by 1.
Thus, the result is 7992
Borrow 7 9 OperandA 8 0 OperandB 0 0
9 10 0 0 0 8 92
Difference 7 9
J. E. Jones

OSU CSE 2421
How do we subtract 8 from 8000 hex?
Reduce the least significant digit by 8; there must be a borrow from the next most significant digit, exactly like we would in a decimal subtract, except the digits we use must represent hexadecimal values.
Note Borrow in LSD (Least Significant Digit) is still 10, its just a hexadecimal value 10 (16 decimal) and other columns are F (not 9 as in decimal).
Borrow 0x7 0xF 0xF 0x10 OperandA 8 0 0 0 OperandB 0 0 0 8
Difference 7 F F 8
Thus, the result is 7FF8, and this is the address at which the first value pushed onto the stack will be stored (more on how the stack pointer changes later).
J. E. Jones

OSU CSE 2421
0x8000 0x7FF8
Some value Store new value here
Note new value is stored in addresses 0x7FF8 to 0x7fff
Higher stack addresses
Lower stack addresses
J. E. Jones

OSU CSE 2421
a (multiplicand) * b (multiplier) Consider a = 123, b = 123.
123 x 123 ==========================
3 2 4 2 3
6 6
9 (thisis123*3)
(this is 123 * 2 shifted left 1 place) (this is 123*1 shifted left 2 places)
1 ============================================
15129
J. E. Jones

OSU CSE 2421
Now consider:
a (multiplicand) * b (multiplier) where a = 1011 (11 decimal), b = 1110 (14 decimal)
1 0 1 1 x 1 1 1 0 ===================
(this is 11 in decimal) (this is 14 in decimal)
0 0 10 1 101 1
00 1
(this is 1011 x 0)
(this is 1011 x 1, shifted one position to the left) (this is 1011 x 1, shifted two positions to the left) (this is 1011 x 1, shifted three positions to the left)
+1011 ===========================
1 0 0 1 1 0 1 0
(this is 154 in decimal)
This is the same process that we use for decimal multiplication!
One could say that binary multiplication is actually easier because each row is either just a shifted copy of the multiplicand or its 0.
J. E. Jones

OSU CSE 2421
Now consider:
a (multiplicand) * b (multiplier) where a = 1011 (11 decimal), b = 1110 (14 decimal)
1011 (this is 11 in decimal) x1110 (this is 14 in decimal)
In our brain, we can hold and/or add etc. more than 2 numbers at a time. So adding these columns of numbers isnt a hard thing.
=================== 0 0 00
(this is 1011 x 0)
(this is 1011 x 1, shifted one position to the left) (this is 1011 x 1, shifted two positions to the left) (this is 1011 x 1, shifted three positions to the left)
1 0 1 1 10 1 1
Machines cant do that. Recall that hardware gates have only 3 inputs and 2 Output (sum & carry).
+101 1 ===========================
10011010 (this is 154 in decimal)
This is the same process that we use for decimal multiplication!
One could say that binary multiplication is simpler because each row is either just a shifted copy of the multiplicand or its 0.
J. E. Jones

OSU CSE 2421
Suppose we want the CPU to multiply two operands: a (multiplicand) * b (multiplier)
Typically, in the simplest version of multiplication hardware, 4 additional registers are used:
-Multiplicand register (contains a copy of the multiplicand) -Multiplier register (contains a copy of the multiplier) -Shifted multiplicand register
-Result register
J. E. Jones

OSU CSE 2421
Registers are places on the CPU where data is stored, typically 8 bytes in size.
Multiplicand register Multiplier register
Shifted multiplicand register Result register
J. E. Jones

OSU CSE 2421
For n bit multiplication, we can denote the bits in the multiplier as b0 (least significant bit) to bn-1 (most significant bit)
The hardware initializes the result register to 0
Then, the hardware does the following (pseudo-code):
for (j = 0; j w 1 op1n , overflow due to shifting will occur
So, if op2n> 1 in our example, overflow occurs.
Again, overflow may also occur due to addition, but the result above describes cases where overflow will definitely occur due to shifting.
J. E. Jones

OSU CSE 2421
If w=8, op1n=4, op2n=3 w(8) 1 op1n(4) = 3
J. E. Jones

OSU CSE 2421
If w=8, 0p1n=4, op2n=3
w(8) 1 op1n(4) = 3 Isop2n >w1op1n? 3>3?
J. E. Jones

OSU CSE 2421
If w=8, 0p1n=4, op2n=3
w(8) 1 op1n(4) = 3 Isop2n >w1op1n? 3>3? No overflow in this case.
J. E. Jones

OSU CSE 2421
Even slower than integer multiplication Dividing by powers of 2right shifting
-There are 2 types of right shifting:
-Logical unsigned: fill with 0s -Arithmetic twos complement: fill with
copy of msb
Integer division always truncates
-C float-to-integer casts round towards zero. -Division by right shifting rounds down. -These rounding errors generally accumulate
J. E. Jones

OSU CSE 2421
Dividing by 2k
Logical right shift by k (x>>k)
Then rounding down (toward zero)
Remember that logical shift will shift in zeroes to fill the most significant bits when the original bit pattern is shifted right
J. E. Jones

OSU CSE 2421
82 100 92 100 124 11 154 11 101000 101001 100 1 1 0 0 1001111
x = 8 = 1000
y = 2 = 0010 = 21 x>>1 =100 (x/y)
x = 9 = 1001
y = 2 = 0010 = 21 x>>1=100 (x/y)
10 10 100 100
00 01 100 111 00 00 100 100
001011
J. E. Jones

OSU CSE 2421
82 100 92 100 124 11 154 11 101000 101001 100 1 1 0 0 1001111
x = 8 = 1000
x = 12 = 1100
y = 2 = 0010 = 21 x>>1 =100 (x/y)
y = 4 = 0100 = 22 x>>2 =11
x = 9 = 1001
x = 15 = 1111
y = 2 = 0010 = 21 x>>1=100 (x/y)
y = 4 = 0100 = 22 x >>2 = 11
10 10 100 100
00 01 100 111 00 00 100 100
001011
J. E. Jones

OSU CSE 2421
Twos complement
Sign extend for arithmetic shift (fill with copy of msb) Rounds down (away from zero for negative results) -7/2 will yield -4 rather than -3
x=-82 y=2k
k Binary Decimal 82/2k
0 10101110 82 82.000000
1 11010111 41 41.000000
2 11101011 21 20.500000
3 11110101 11 10.250000
4 11111010 6 5.125000
5 11111101 3 2.562500
Note rounding effect
J. E. Jones