Subversion Repositories NedoOS

Rev

Blame | Last modification | View Log | Download

  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
  155.