 Multiply Two Numbers Using Shifts
This function multiplies two numbers using shift and add operations.
The parameters are passed on the stack. The procedure stores the two parameters in the word registers bx and dx, and accumulates the result in eax, providing 16 bit ¥ 16 bit = 32-bit multiplication. For each bit that is on in dx, it adds the value "bx shifted left the appropriate number of bits" to eax. When it has checked every bit in dx, the correct result will be in eax, which is where the procedure is defined to return it.
The procedure does preserve the passed-in value of registers, and is responsible for popping parameters off the stack. Note that the two numbers are pushed on the stack as words, not dwords.
The test instruction sets the flags as if it were a logical and, without actually modifying the value of the operands.
Source Code
1. multiply:
2. ; save registers we use
3. push ebp
4. mov ebp, esp
5. push ebx
6. push edx
7.
8. xor ebx, ebx ; ensure high 16 bits are zeroed out
9. mov dx, [ebp+8] ; second parameter
10. mov bx, [ebp+10] ; first parameter
11.
12. ; eax accumulates the result
13. mov eax, 0
14.
15. mainloop:
16. cmp dx, 0
17. je done ; no bits left in ax
18.
19. test dx, 1
20. jz noton ; this bit is not on, so don't add
21. add eax, ebx
22. shl ebx, 1 ; ebx = ebx * 2
23. noton:
24. shr dx, 1 ; try the next bit
25. jmp mainloop
26.
27. done:
28. ; restore saved values
29. pop edx
30. pop ebx
31. pop ebp
32.
33. ret 4 ; pop 2 word parameters
Suggestions
What is the goal of the first iteration through mainloop on lines 15-25? What is an input that causes mainloop to iterate exactly once? The two numbers to be multiplied are stored in bx and dx. How come it is necessary to clear the high 16 bits of ebx (on line 8) but not of edx? Does the program save/restore registers properly and access the pushed parameters at the correct offset from ebp?
Hints
Walk through the procedure with the following two words pushed on the stack (the current stack location is at the bottom; numbers are shown in binary for convenience):
Only one bit on in the second number: 101 1 Same scenario in reverse: 1 101 Two bits in each word: 11 11 The high bit is on in each number: 1000000000000000 1000000000000000
Explanation of the Bug
The code on line 22 to shift ebx to the left
shl ebx, 1 ; ebx = ebx * 2
must be executed each time through mainloop, not only in cases where the low bit of dx was on. It should be moved down one line to be after the noton label. Otherwise, the program works incorrectly unless the second parameter (the one stored in dx) is one less than a power of 2, which means its binary representation looks like 1, 11, 111, etc. For numbers like that, the missed shifts won't affect the final result.
This could be an F.location error, but it is more likely an A.logic error.
| 
