?login_element?

Subversion Repositories NedoOS

Rev

Blame | Last modification | View Log | Download | RSS feed

  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.         ld (.itemsize),de
  15. ;adjust data for djnz+dec_c loop
  16.         ld a,c
  17.         dec bc
  18.         inc b
  19.         ld c,b
  20.         ld b,a
  21.         ld (.numitems),bc
  22. ;create array with pointers to items
  23.         ld ix,RADIXSORT_WORKBUFFER
  24.         ld (.srcbuf),ix
  25. .fillptrsloop
  26.         ld (ix),hl
  27.         add hl,de
  28.         inc ix
  29.         inc ix
  30.         djnz .fillptrsloop
  31.         dec c
  32.         jr nz,.fillptrsloop
  33.         ld (.dstbuf),ix
  34. ;main loop iterating through the key
  35.         pop bc
  36.         pop hl
  37. .keysizeloop
  38.         ld e,(hl)
  39.         inc hl
  40.         ld d,(hl)
  41.         inc hl
  42.         ld (.keyoffset),de
  43.         ld (.keyoffset1),de
  44.         push bc
  45.         push hl
  46. ;clear histogram
  47.         ld hl,RADIXSORT_HISTOGRAM
  48.         ld de,RADIXSORT_HISTOGRAM+1
  49.         ld bc,511
  50.         ld (hl),0
  51.         ldir
  52. ;fill histogram
  53. .srcbuf=$+2
  54.         ld ix,0
  55. .numitems=$+1
  56.         ld bc,0
  57. .buildhistogramloop
  58.         ld hl,(ix)
  59.         inc ix
  60.         inc ix
  61. .keyoffset=$+1
  62.         ld de,0
  63.         add hl,de
  64.         ld e,(hl)
  65.         ld d,0
  66.         ld hl,RADIXSORT_HISTOGRAM
  67.         add hl,de
  68.         add hl,de
  69.         inc (hl)
  70.         jr nz,$+4
  71.         inc hl
  72.         inc (hl)
  73.         djnz .buildhistogramloop
  74.         dec c
  75.         jr nz,.buildhistogramloop
  76. ;histogram prefix sum
  77.         ld ix,RADIXSORT_HISTOGRAM
  78. .dstbuf=$+1
  79.         ld hl,0
  80.         ld b,0
  81. .prefixsumloop
  82.         ld de,(ix)
  83.         ld (ix),hl
  84.         add hl,de
  85.         add hl,de
  86.         inc ix
  87.         inc ix
  88.         djnz .prefixsumloop
  89. ;shuffle pointers
  90.         ld ix,(.srcbuf)
  91.         ld iy,(.numitems)
  92. .copypointersloop
  93.         ld bc,(ix)
  94.         inc ix
  95.         inc ix
  96. .keyoffset1=$+1
  97.         ld hl,0
  98.         add hl,bc
  99.         ld e,(hl)
  100.         ld d,0
  101.         ld hl,RADIXSORT_HISTOGRAM
  102.         add hl,de
  103.         add hl,de
  104.         ld e,(hl)
  105.         inc hl
  106.         ld d,(hl)
  107.         ex de,hl
  108.         ld (hl),c
  109.         inc hl
  110.         ld (hl),b
  111.         inc hl
  112.         ex de,hl
  113.         ld (hl),d
  114.         dec hl
  115.         ld (hl),e
  116.         dec iyh
  117.         jr nz,.copypointersloop
  118.         dec iyl
  119.         jr nz,.copypointersloop
  120. ;swap buffers
  121.         ld hl,(.srcbuf)
  122.         ld de,(.dstbuf)
  123.         ld (.srcbuf),de
  124.         ld (.dstbuf),hl
  125.         pop hl
  126.         pop bc
  127.         dec b
  128.         jp nz,.keysizeloop
  129. ;move sorted items to destination buffer
  130.         ld iy,(.numitems)      
  131.         ld ix,de
  132.         pop de
  133. .copyitemsloop
  134.         ld hl,(ix)
  135.         inc ix
  136.         inc ix
  137. .itemsize=$+1
  138.         ld bc,0
  139.         ldir
  140.         dec iyh
  141.         jr nz,.copyitemsloop
  142.         dec iyl
  143.         jr nz,.copyitemsloop
  144.         ret
  145.