 Make Change for a Dollar
This function returns the change from a dollar for a specified number of cents.
The number of cents is the only argument and it is pushed on the stack. The valid range for this argument is between 0 and 100 (inclusive). The procedure is not responsible for checking that the argument is in the proper range.
The coin values are 25 cents, 10 cents, 5 cents, and 1 cent. The procedure returns as many of the largest coins as possible, then the next largest, and so on.
The procedure returns a dword in eax. The high byte is the number of quarters, then the number of dimes and nickels, and the low byte is the number of pennies. To calculate the result, it uses the magic-looking hexadecimal number 0x190a0501, which has the face value of each coin in each corresponding byte (face value of a quarter in the high byte, and so on).
The procedure is responsible for removing the argument from the stack. It does not worry, however, about preserving the passed-in values of registers.
The program uses the rol instruction "rotate left". The rotate instructions, rol and ror, are like shl and shr (shift left and shift right), except that they wrap the bits that are shifted out the top or bottom around to the other end. For example, if al has the binary value 01001100, after
rol al, 2
it will have the value 00110001.
Source Code
1. make_change:
2. sub esp, 4 ; local variable
3. mov dword ptr [esp], 0x190a0501
4. ; coins are 25, 10, 5, 1
5. mov eax, 100 ; change is from 100 cents
6. sub eax, [esp+8] ; [esp+8] is the parameter
7.
8. ; al holds the amount of money that we are trying
9. ; to total the coins up to; as a new coin is added,
10. ; we subtract its face value from al.
11.
12. mov ebx, 0 ; ebx will hold the result
13.
14. top:
15. cmp dword ptr[esp], 0 ; done with all coins?
16. je done
17. rol ebx, 8 ; new coin, save old counts
18.
19. testagain:
20. cmp al, byte ptr [esp] ; is al < current coin?
21. jl nextcoin ; yes, so try the next smaller coin
22.
23. inc bl ; count one of current coin...
24. sub al, byte ptr [esp]
25. ; ...and subtract from amount left
26. jmp testagain
27.
28. nextcoin:
29. shr dword ptr [esp], 8 ; done with that coin
30. jmp top
31.
32. done:
33. add esp, 4 ; remove local variable
34.
35. mov eax, ebx
36. ret 4 ; take argument off the stack
Suggestions
What is the "loop counter" of the top loop, running from lines 14-30? Where is this loop counter changed? How many times will this loop iterate? In the trivial case, there will be no change returned, which means that eax should be zero at the end (no quarters, no dimes, no nickels, and no pennies). What input causes this to happen? Does the code handle it correctly? Does the use of the al variable match how it is described in the comment on lines 8-10?
Hints
Walk through the function with the following value pushed on the stack as the parameter:
The maximum amount of change: 0 Almost the maximum amount of change: 1 Skip all face values but the smallest one: 99 Change has at least one of every coin: 58
Explanation of the Bug
The value of all the possible coins is initialized incorrectly on line 3:
mov dword ptr [esp], 0x190a0501
It does correctly correspond to the expected result in that the high byte has the face value of a quarter and the result is supposed to have the number of quarters in the high byte. However, the program later accesses this data by using byte ptr [esp], rotating it through after each coin. Because the x86 stores numbers in little-endian format, the first time through the top loop, byte ptr [esp] will be 0x01, not 0x19.
This is a D.number error because of the way numbers are stored in memory. The fix is to swap the bytes in the number. So, the initialization on line 3 becomes the following:
mov dword ptr [esp], 0x01050a19
The effect of the code as written is that it initially tries to make change with pennies, which means that it determines that the proper change for any number n is n pennies. However, it then stores this count in the high byte of the result, indicating that it feels that the proper change is n quarters.
|
