 Sum a Signed Array
This function sums an array of signed dwords.
The program returns a dword as the final value, but allows the intermediate result to be larger than a dword can hold. It tracks the "result," which is the dword total of the elements in the array, as well as an overflow/underflow "counter." Each time the cumulative sum of the elements overflows (meaning it is more than 231-1, the highest value a signed dword can hold), the counter is incremented; each time the cumulative sum underflows (meaning it is less than -231, the lowest value a signed dword can hold), the counter is decremented. The net effect is that the counter functions as the high bits (above 31) of the result. If at the end of summing the array the counter is zero, then the 32-bit result is correct.
The program calls itself recursively to add up every element but the first one, then adds that result to the first element to produce the final result.
It is passed four parameters, pushed on the stack in order: the address to store the result, the address to store the overflow/underflow counter, the length of the array, and the address of the array. The length of the array is in elements, not bytes.
The procedure has to preserve registers; when calling itself recursively, the calling code is responsible for cleaning the parameters off the stack.
The program checks the carry and overflow flags (the overflow flag is checked with the jo instruction, the carry flag with jc). Because of how two's complement notation works, an arithmetic operation such as add or subtract is unaffected by whether the user is treating the variables as signed or unsigned. The carry and overflow flags can be checked depending on which interpretation is desired. The carry flag is set if the operation, when treated as unsigned, resulted in a value that was too large or too small. The overflow flag is set if the operation, when treated as signed, resulted in a value that was too large or too small (the "too small" condition is known as an "underflow," but it still affects the overflow flag).
The conditions when the carry flag is set are fairly straightforward; since all bits are treated as positive in an unsigned number, an unsigned addition can never result in a number that is too small, and an unsigned subtraction can never result in a number that is too large. An add instruction will set the carry bit if the result is greater than 232-1, and a sub instruction will set the carry bit if the result is less than 0.
The overflow flag is less obvious; the valid range of signed numbers is -231 to 231-1. Thus, an addition of two positive numbers may result in an overflow, but the addition of two negative numbers may result in an underflow. Similarly, a signed subtract can either overflow or underflow.
Remember that in the two's complement notation, a signed number will have the high bit off if it is positive, and the high bit on if it is negative. When adding numbers, the program first checks the overflow flag to see if the result did not fit in a signed dword; it then checks the carry flag to differentiate between overflow and underflow, so it can adjust the overflow/underflow counter appropriately.
As with any recursive function, the stack will eventually overflow if the array is large enough, but that should not be considered a bug.
Source Code
1. sum_array:
2. push ebp
3. mov ebp, esp
4. sub esp, 8 ; local vars for result/counter
5. push edi
6. push esi
7. push ecx
8.
9. mov ecx, dword ptr [ebp+12] ; size of array
10. cmp ecx, 0 ; is array empty?
11. jne notzero
12. mov dword ptr [ebp-8], 0 ; yes, so counter...
13. mov dword ptr [ebp-4], 0 ; ...and result are 0
14. jmp done ; and we're done
15.
16. notzero:
17. ; first make a recursive call for the rest of
18. ; the array (not including the first element)
19. lea esi, dword ptr [ebp-4]
20. push esi ; push address of result
21. lea esi, dword ptr [ebp-8]
22. push esi ; and address of counter
23. sub ecx, 1
24. push ecx ; and count-1
25. mov esi, dword ptr [ebp+8]
26. add esi, 4
27. push esi ; and address of array+4
28.
29. call sum_array ; result/counter in [ebp-8]/[ebp-4]
30.
31. add esp, 16 ; take parameters off the stack
32. sub esi, 4 ; point esi back to current element
33. mov ecx, dword ptr [esi]
34. add dword ptr [ebp-4], ecx ; add result
35. jo overflowed ; did it overflow/underflow?
36. jmp done ; no, so we're done
37.
38. overflowed:
39. jc toobig ; did it overflow too large?
40.
41. ; no, overflowed too small
42. dec dword ptr [ebp-8] ; decrement counter
43. jmp done
44.
45. toobig:
46. inc dword ptr [ebp-8] ; increment counter
47.
48. done:
49. ; copy our updated result/counter to the locations
50. ; passed as parameters to this call
51. mov edi, dword ptr [ebp+16]
52. lea esi, dword ptr [ebp-8]
53. movsd ; copy overflow/underflow counter
54. mov edi, dword ptr [ebp+20]
55. lea esi, dword ptr [ebp-4]
56. movsd ; copy result
57. pop ecx
58. pop esi
59. pop edi
60. add esp, 8
61. pop ebp
62.
63. ret
Suggestions
sum_array has four parameters, addressed as [ebp+8], [ebp+12], [ebp+16], and [ebp+20], as well as two local variables, [ebp-4] and [ebp-8]. Check that these are correctly indexed from ebp, and assign them more meaningful names that you can use when walking through the program. Ensure that the recursion eventually terminates. Verify that the movsd instructions on lines 53 and 56 actually move the correct data. Check that everything pushed on the stack is eventually popped off the stack, in the proper order, before the procedure returns.
Hints
Walk through the program with the following arrays (assume the address, length, and space for the result and counter are pushed correctly to the outer call to sum_array):
Check a trivial case, a single element (the recursive call within this will test the empty case of no elements): 5 Two elements, that will result in a "too large" overflow: 231-1
1 Two elements, that will result in a "too small" underflow: -231 -1 Three elements, that will overflow, then swing back to the valid range (remember that 230+230 is equal to 231): -1 230
230
Explanation of the Bug
The program uses the wrong check when determining whether the overflow flag was set because of the result being too large or too small.
Consider the case where the overflow flag is set because of the addition of two positive numbers. Positive signed numbers do not have the high bit (bit 32, if the low bit is numbered 1) set; therefore the addition of any pair of them can't set the carry flag-the most the addition of two positive signed numbers can do is carry from bit 31 into bit 32. The carry flag, on the other hand, indicates that the result overflowed from bit 32 into (nonexistent) bit 33. As a result, after a "too large" signed overflow, the carry flag will be cleared, not set.
Meanwhile, negative signed numbers do have bit 32 set, so the addition of any pair of them will set the carry flag. So if there is an overflow and the carry flag is set, it was because of the addition of two negative numbers, so it must be a "too small" underflow.
Because of this, the check for overflow versus underflow on line 39
jc toobig ; did it overflow too large?
although it may seem intuitively correct, is actually reversed. It should be checking if the carry flag is not set:
jnc toobig ; did it overflow too large?
This is a D.number error, because it is based on a misunderstanding of how two's complement numbers are stored.
The effect of the bug is that the counter goes off in the wrong direction, being negative when it should be positive, and vice versa. If the counter winds up at zero, however, the result is correct.
|
