 Radix Exchange Sort
This procedure performs a radix exchange sort of an array of dwords.
The radix exchange sort works by considering elements of the array one bit at a time, going from right to left (least significant to most significant). It first rearranges the array so that all elements that have a 0 in the least significant bit are before all the elements that have a 1 in the least significant bit. Then, it does the same with the second least significant bit, and so on up until the most significant bit.
The reason this works is because the algorithm takes care, when rearranging the array for bit n, to never disturb the relative position of elements that have the same value for bit n. That is, it moves elements that have bit n set to 0 up in the array so they are before elements that have bit n set to 1, but if two elements have bit n set to 0, it won't change their relative position-the one that was earlier in the array is still earlier, even though both might have moved.
It can be difficult to convince yourself that the algorithm actually works. Elements tend to move around the array somewhat randomly until magically settling into place on the last loop iteration.
However, it is not difficult to prove that it is correct. If you consider two numbers, A and B, in binary representation, they will have a certain number of most significant bits that match (this number might be 0), followed by a bit that doesn't match. The relative ordering of A and B depends only on that first bit that doesn't match. If the bit is 0 in A and 1 in B, A is less than B. If it is 1 in A and 0 in B, A is greater than B. If the "different" bit never happens, A is equal to B.
So, the algorithm proceeds from least significant bit up, moving A and B as it sees fit, until at some point it processes the most significant bit where A and B differ. At that point, it orders them properly based on that bit. From then on, because they will match in all higher bits, it won't disturb their relative order. Thus, they are properly sorted in the array. The same is true for any pair of numbers.
The program takes two parameters pushed on the stack: the length of the array and the address of the array. It has no return value. It is required to preserve the values of registers and clear the parameters off the stack.
Source Code
1. radix_sort:
2. push ebp
3. mov ebp, esp
4. push eax
5. push ebx
6. push ecx
7. push edx
8. push esi
9. push edi
10.
11. mov edx, 1 ; start with low bit
12.
13. outerloop:
14. mov eax, [ebp+8] ; address of array
15. mov ebx, [ebp+12] ; size of array
16.
17. mov esi, eax ; esi stores address of first element
18. imul ebx, 4
19. add eax, ebx ; eax stores address of last element
20.
21. lookforonebit:
22. ; start at esi, find an element with the edx bit on
23. cmp esi, eax
24. je trynextbit ; we are at the end of the array
25.
26. test [esi], edx ; does [esi] have the edx bit on?
27. jnz foundone ; yes
28. add esi, 4 ; no, advance esi and loop back
29. jmp lookforonebit
30.
31. foundone:
32. ; edx bit is on at [esi], now look for the next
33. ; element where edx bit is off. Then adjust array.
34. mov edi, esi ; use edi as the pointer
35. lookforzerobit:
36. add edi, 4
37. test [edi], edx ; does [edi] have the edx bit on?
38. jz foundzero ; no
39. checkforendthenlookforzero:
40. cmp edi, eax ; yes, see if we hit the last element
41. je trynextbit ; last element, move edx to next bit
42. jmp lookforzerobit
43.
44. foundzero:
45. ; edx bit is one from [esi] to [edi-4], and zero at
46. ; [edi]. Slide array between them down and move
47. ; [edi] to [esi].
48. mov ebx, [edi] ; save to store at [esi] later
49. push edi ; save these three
50. push ebx
51. push esi
52. mov ecx, edi
53. sub ecx, esi ; ecx has the count of bytes to move
54. add edi, 3 ; edi is last target byte of move
55. mov esi, edi
56. sub esi, 4 ; esi is last source byte of move
57.
58. ; esi > edi, so the move has to be done backwards
59. std ; set direction flag
60. rep movsb
61. cld ; clear direction flag
62.
63. pop esi ; restore what we just pushed above
64. pop ebx
65. mov [esi], ebx ; put what was at [edi] at [esi]
66. pop edi
67.
68. ; done with the move, continue the loop. We
69. ; move esi up one, and edi is now the last of
70. ; the elements we moved that had the edx bit on
71. add esi, 4
72. jmp checkforendthenlookforzero
73.
74. trynextbit:
75. shl edx, 1
76. jne outerloop
77. ; edx shifted out to zero, we are done
78.
79. pop edi
80. pop esi
81. pop edx
82. pop ecx
83. pop ebx
84. pop eax
85. pop ebp
86.
87. ret 8
Suggestions
Because the algorithm depends on not disturbing the relative order of two elements if they have the same value for the bit being considered, verify that this is done properly. Check that the main outerloop loop terminates properly. Line 36 advances edi and line 37 tests a bit in it. Only later is a check made to see if the end of the array has been hit. Can this result in an access beyond the end of the array? Is it okay on lines 24 and 41 to jump right to trynextbit, or is there possibly shifting of the array that has to happen before moving to the next bit?
Hints
Walk through the program with the arrays:
The trivial case of a single number: 1 A sorted array with numbers that differ in only one bit: 10 18 An unsorted array with numbers alternating bits on and off: 1 0 1 0 An unsorted array with every combination of bits 2 and 3, multiple times: 6 0 0 2 2 4 6 4
Explanation of the Bug
The code on lines 17-19 to initialize the start and end of the array
mov esi, eax ; esi stores address of first element
imul ebx, 4
add eax, ebx ; eax stores address of last element
produces a result in eax that is the first byte past the end of the array. However, the way the program is written, it expects eax to point to the last actual element in the array. Thus, ebx has to be adjusted back between lines 17-18:
sub ebx, 1
This is a D.limit or A.off-by-one error because the program winds up "sorting" one extra element in the array, whatever it happens to contain (unless it crashes trying to access the memory).
|
