Subversion Repositories NedoOS

Rev

Details | Last modification | View Log

Rev Author Line No. Line
1637 galstaff 1 
RADIXSORT_HISTOGRAM = 0xc000
2 
RADIXSORT_WORKBUFFER = RADIXSORT_HISTOGRAM + 512
3 
 
4 
radixsort
5 
;a = key size in bytes
6 
;ix = array of dwords, each element is an offset to n-th byte of the key
7 
;hl = items ptr (input)
8 
;de = item size
9 
;bc = num items
10 
;iy = sorted items ptr (output)
11 
        push iy
12 
        push ix
13 
        push af
14 
 
15 
        ld (.itemsize),de
16 
 
17 
;adjust data for djnz+dec_c loop
18 
        ld a,c
19 
        dec bc
20 
        inc b
21 
        ld c,b
22 
        ld b,a
23 
        ld (.numitems),bc
24 
 
25 
;create array with pointers to items
26 
        ld ix,RADIXSORT_WORKBUFFER
27 
        ld (.srcbuf),ix
28 
.fillptrsloop
29 
        ld (ix),hl
30 
        add hl,de
31 
        inc ix
32 
        inc ix
33 
        djnz .fillptrsloop
34 
        dec c
35 
        jr nz,.fillptrsloop
36 
        ld (.dstbuf),ix
37 
 
38 
;main loop iterating through the key
39 
        pop bc
40 
        pop hl
41 
.keysizeloop
42 
        ld e,(hl)
43 
        inc hl
44 
        ld d,(hl)
45 
        inc hl
46 
        ld (.keyoffset),de
47 
        ld (.keyoffset1),de
48 
 
49 
        push bc
50 
        push hl
51 
 
52 
;clear histogram
53 
        ld hl,RADIXSORT_HISTOGRAM
54 
        ld de,RADIXSORT_HISTOGRAM+1
55 
        ld bc,511
56 
        ld (hl),0
57 
        ldir
58 
 
59 
;fill histogram
60 
.srcbuf=$+2
61 
        ld ix,0
62 
.numitems=$+1
63 
        ld bc,0
64 
.buildhistogramloop
65 
        ld hl,(ix)
66 
        inc ix
67 
        inc ix
68 
.keyoffset=$+1
69 
        ld de,0
70 
        add hl,de
71 
        ld e,(hl)
72 
        ld d,0
73 
        ld hl,RADIXSORT_HISTOGRAM
74 
        add hl,de
75 
        add hl,de
76 
        inc (hl)
77 
        jr nz,$+4
78 
        inc hl
79 
        inc (hl)
80 
        djnz .buildhistogramloop
81 
        dec c
82 
        jr nz,.buildhistogramloop
83 
 
84 
;histogram prefix sum
85 
        ld ix,RADIXSORT_HISTOGRAM
86 
.dstbuf=$+1
87 
        ld hl,0
88 
        ld b,0
89 
.prefixsumloop
90 
        ld de,(ix)
91 
        ld (ix),hl
92 
        add hl,de
93 
        add hl,de
94 
        inc ix
95 
        inc ix
96 
        djnz .prefixsumloop
97 
 
98 
;shuffle pointers
99 
        ld ix,(.srcbuf)
100 
        ld iy,(.numitems)
101 
.copypointersloop
102 
        ld bc,(ix)
103 
        inc ix
104 
        inc ix
105 
.keyoffset1=$+1
106 
        ld hl,0
107 
        add hl,bc
108 
        ld e,(hl)
109 
        ld d,0
110 
        ld hl,RADIXSORT_HISTOGRAM
111 
        add hl,de
112 
        add hl,de
113 
        ld e,(hl)
114 
        inc hl
115 
        ld d,(hl)
116 
        ex de,hl
117 
        ld (hl),c
118 
        inc hl
119 
        ld (hl),b
120 
        inc hl
121 
        ex de,hl
122 
        ld (hl),d
123 
        dec hl
124 
        ld (hl),e
125 
        dec iyh
126 
        jr nz,.copypointersloop
127 
        dec iyl
128 
        jr nz,.copypointersloop
129 
 
130 
        ld hl,(.srcbuf)
131 
        ld de,(.dstbuf)
132 
        ld (.srcbuf),de
133 
        ld (.dstbuf),hl
134 
        pop hl
135 
        pop bc
136 
        dec b
137 
        jp nz,.keysizeloop
138 
 
139 
;move sorted items to destination buffer
140 
        ld iy,(.numitems)      
141 
        ld ix,de
142 
        pop de
143 
.copyitemsloop
144 
        ld hl,(ix)
145 
        inc ix
146 
        inc ix
147 
.itemsize=$+1
148 
        ld bc,0
149 
        ldir
150 
        dec iyh
151 
        jr nz,.copyitemsloop
152 
        dec iyl
153 
        jr nz,.copyitemsloop
154 
        ret