Skip to content

Instantly share code, notes, and snippets.

@ped7g

ped7g/quicksort_strings.asm

Created May 9, 2023 22:32
Show Gist options
  • Save ped7g/5b29c9199494bf35ee5b0aeacf98df75 to your computer and use it in GitHub Desktop.
Save ped7g/5b29c9199494bf35ee5b0aeacf98df75 to your computer and use it in GitHub Desktop.
Download ZIP
Z80 quicksort of array with pointers to 64 byte long strings
Raw
quicksort_strings.asm
; Author: Ped7g ; (C) 2022 ; license: MIT / GPL / Public Domain (pick whichever fits best for you)
; sort array of pointers to 64 char long strings (for example filenames)
; assembled with: https://github.com/z00m128/sjasmplus/
DEFINE ORG_ADR $8080 ; using only uncontended faster memory, but smaller buffers
OPT --syntax=abf : CSPECTMAP "qsorts.map"
DEVICE ZXSPECTRUM48, ORG_ADR-1
ORG ORG_ADR
/* // C routine from z80_babel project, used for algorithm in asm code
void quicksort_c(uint16_t *A, uint16_t len) {
if (len < 2) return;
uint16_t pivot = A[len / 2];
uint16_t i, j;
for (i = 0, j = len - 1; ; i++, j--) {
while (A[i] < pivot) i++;
while (A[j] > pivot) j--;
if (i >= j) break;
uint16_t temp = A[i];
A[i] = A[j];
A[j] = temp;
}
quicksort_c(A, i);
quicksort_c(A + i, len - i);
}
*/
;--------------------------------------------------------------------------------------------------------------------
; Quicksort, inputs (__sdcccall(1) calling convention):
; HL = uint16_t* A (pointer to beginning of array)
; DE = uint16_t len (number of word elements in array)
; modifies: AF, A'F', BC, DE, HL
; WARNING: array can't be aligned to start/end of 64ki address space, like HL == 0x0000, or having last value at 0xFFFE
; WARNING: stack space required is on average about 6*log(len) (depending on the data, in extreme case it may be more)
quicksort_a:
; convert arguments to HL=A.begin(), DE=A.end() and continue with quicksort_a_impl
ex de,hl
add hl,hl
add hl,de
ex de,hl
; |
; fallthrough into implementation
; |
; v
;--------------------------------------------------------------------------------------------------------------------
; Quicksort implementation, inputs:
; HL = uint16_t* A.begin() (pointer to beginning of array)
; DE = uint16_t* A.end() (pointer beyond array)
; modifies: AF, A'F', BC, HL (DE is preserved)
quicksort_a_impl:
; array must be located within 0x0002..0xFFFD
ld c,l
ld b,h ; BC = A.begin()
; if (len < 2) return; -> if (end <= begin+2) return;
inc hl
inc hl
or a
sbc hl,de ; HL = -(2*len-2), len = (2-HL)/2
ret nc ; case: begin+2 >= end <=> (len < 2)
push de ; preserve A.end() for recursion
push bc ; preserve A.begin() for recursion
; uint16_t pivot = A[len / 2];
rr h
rr l
dec hl
res 0,l
add hl,de
ld a,(hl)
inc hl
ld l,(hl)
ld h,b
ld b,l
ld l,c
ld c,a ; HL = A.begin(), DE = A.end(), BC = pivot
; flip HL/DE meaning, it makes simpler the recursive tail and (A[j] > pivot) test
ex de,hl ; DE = A.begin(), HL = A.end(), BC = pivot
dec de ; but keep "from" address (related to A[i]) at -1 as "default" state
; for (i = 0, j = len - 1; ; i++, j--) { ; DE = (A+i-1).hi, HL = A+j+1
.find_next_swap:
; while (A[j] > pivot) j--;
.find_j:
push de
dec hl
ld d,(hl)
dec hl
ld e,(hl) ; DE = A[j]
push hl
push bc
ld h,b
ld l,c ; HL = pivot
call memcmp64 ; compare strings
pop bc
pop hl
pop de
jr z,.j_found
jp p,.find_j ; A[j][k] > pivot[k] (at char which differs)
.j_found:
; while (A[i] < pivot) i++;
.find_i:
push hl
inc de
ld a,(de)
ld l,a
inc de
ld a,(de)
ld h,a ; HL = A[i]
push de
push bc
ld e,c
ld d,b ; DE = pivot
call memcmp64 ; compare strings
pop bc
pop de
pop hl
jr z,.i_found
jp p,.find_i ; pivot[k] > A[i][k] (at char which differs)
.i_found:
; if (i >= j) break; // DE = (A+i).hi, HL = A+j, BC=pivot
or a
sbc hl,de
jr c,.swaps_done
add hl,de ; DE = (A+i).hi, HL = A+j
; swap(A[i], A[j]);
inc hl
ld a,(de)
ldd
ex af,af'
ld a,(de)
ldi
ex af,af'
ld (hl),a ; Swap(A[i].hi, A[j].hi) done
dec hl
ex af,af'
ld (hl),a ; Swap(A[i].lo, A[j].lo) done
inc bc
inc bc ; pivot value restored (was -=2 by ldd+ldi)
; --j; HL = A+j is A+j+1 for next loop (ready)
; ++i; DE = (A+i).hi is (A+i-1).hi for next loop (ready)
jp .find_next_swap
.swaps_done:
; i >= j, all elements were already swapped WRT pivot, call recursively for the two sub-parts
dec de ; DE = A+i
; quicksort_c(A, i);
pop hl ; HL = A
call quicksort_a_impl
; quicksort_c(A + i, len - i);
ex de,hl ; HL = A+i
pop de ; DE = end() (and return it preserved)
jp quicksort_a_impl
DISPLAY "quicksort_a code size: ",/A,$-quicksort_a
DISPLAY "quicksort_a_impl code size: ",/A,$-quicksort_a_impl
memcmp64:
; compare 64 bytes
;
; Input:
; HL = address 1
; DE = address 2
;
; Output:
; when a byte differs: ZF=0, A=first different byte from DE argument side
; when all bytes match: ZF=1, A=last matching byte
;
ld bc,64
.l0: ld a,(de)
inc de
cpi
ret nz
jp pe,.l0
ret
DISPLAY "memcmp64 code size: ",/A,$-memcmp64
;--------------------------------------------------------------------------------------------------------------------
; test harness to debug and tune the routine
test_start:
; check empty array and len=1 array (shouldn't touch buffer, just exit)
ld hl,test_array
ld de,test_array
call quicksort_a_impl
ld hl,test_array
ld de,test_array+2
call quicksort_a_impl
; sort fake filenames array
ld a,2
out (254),a
ld hl,test_array
ld de,test_array.end
call quicksort_a_impl
ld a,7
out (254),a
; print results to eyeball check it
ROM_ATTR_P: EQU $5C8D
ROM_CLS: EQU $0DAF
ei ; handle keyboard for Scroll? message
ld a,7<<3 ; FLASH 0 : BRIGH 0 : PAPER 7 : INK 0
ld (ROM_ATTR_P),a ; set ATTR-P
call ROM_CLS
ld hl,test_array
ld c,test_array.count
.name_l:
ld b,SFNAME
ld e,(hl)
inc hl
ld d,(hl)
inc hl
push hl
.char_l:
ld a,(de)
inc de
push bc
rst $10
pop bc
djnz .char_l
pop hl
dec c
jr nz,.name_l
ld a,4
out (254),a
jr $
STRUCT SFNAME
n TEXT 64, { 0 }
ENDS
fnames:
SFNAME { {"xzegreplinux-gnu-gcc-nm "} }
SFNAME { {"xzfgreplinux-gnu-gcc-nm-11 "} }
SFNAME { {"xzgrep-linux-gnu-gcc-ranlib "} }
SFNAME { {"xzless-linux-gnu-gcc-ranlib-11 "} }
SFNAME { {"xzmore-linux-gnu-gcov "} }
SFNAME { {"yakuakelinux-gnu-gcov-11 "} }
SFNAME { {"yaml2obj-13x-gnu-gcov-dump "} }
SFNAME { {"yaml2obj-14x-gnu-gcov-dump-11 "} }
SFNAME { {"yaml-bench-13gnu-gcov-tool "} }
SFNAME { {"yaml-bench-14gnu-gcov-tool-11 "} }
SFNAME { {"ybmtopbminux-gnu-gold "} }
SFNAME { {"yes_64-linux-gnu-gprof "} }
SFNAME { {"ypdomainname-gnu-ld "} }
SFNAME { {"yuvsplittoppmgnu-ld.bfd "} }
SFNAME { {"yuvtoppminux-gnu-ld.gold "} }
SFNAME { {"zcat64-linux-gnu-lto-dump-11 "} }
SFNAME { {"zcmp64-linux-gnu-nm "} }
SFNAME { {"zdiff4-linux-gnu-objcopy "} }
SFNAME { {"zdump4-linux-gnu-objdump "} }
SFNAME { {"zegrep-linux-gnu-pkg-config "} }
SFNAME { {"zeisstopnmux-gnu-qmake "} }
SFNAME { {"zfgrep-linux-gnu-ranlib "} }
SFNAME { {"zforce-linux-gnu-readelf "} }
SFNAME { {"zgrep4-linux-gnu-size "} }
SFNAME { {"zip_64-linux-gnu-strings "} }
SFNAME { {"zipcloakinux-gnu-strip "} }
SFNAME { {"zipdetailslinux-gnu-pkg-config "} }
SFNAME { {"zipgrepw64-mingw32-addr2line "} }
SFNAME { {"zipinfow64-mingw32-ar "} }
SFNAME { {"x86_64-w64-mingw32-as "} }
SFNAME { {"x86_64-w64-mingw32-c++ "} }
SFNAME { {"x86_64-w64-mingw32-c++filt "} }
SFNAME { {"x86_64-w64-mingw32-c++-posix "} }
SFNAME { {"x86_64-w64-mingw32-cpp "} }
SFNAME { {"x86_64-w64-mingw32-cpp-posix "} }
SFNAME { {"x86_64-w64-mingw32-cpp-win32 "} }
SFNAME { {"x86_64-w64-mingw32-c++-win32 "} }
SFNAME { {"x86_64-w64-mingw32-dlltool "} }
SFNAME { {"x86_64-w64-mingw32-dllwrap "} }
SFNAME { {"x86_64-w64-mingw32-elfedit "} }
SFNAME { {"x86_64-w64-mingw32-g++ "} }
SFNAME { {"x86_64-w64-mingw32-gcc "} }
SFNAME { {"x86_64-w64-mingw32-gcc-10-posix "} }
SFNAME { {"x86_64-w64-mingw32-gcc-10-win32 "} }
SFNAME { {"x86_64-w64-mingw32-gcc-ar "} }
SFNAME { {"x86_64-w64-mingw32-gcc-ar-posix "} }
SFNAME { {"x86_64-w64-mingw32-gcc-ar-win32 "} }
SFNAME { {"x86_64-w64-mingw32-gcc-nm "} }
SFNAME { {"x86_64-w64-mingw32-gcc-nm-posix "} }
SFNAME { {"x86_64-w64-mingw32-gcc-nm-win32 "} }
SFNAME { {"x86_64-w64-mingw32-gcc-posix "} }
SFNAME { {"x86_64-w64-mingw32-gcc-ranlib "} }
SFNAME { {"x86_64-w64-mingw32-gcc-ranlib-posix "} }
SFNAME { {"x86_64-w64-mingw32-gcc-ranlib-win32 "} }
SFNAME { {"x86_64-w64-mingw32-gcc-win32 "} }
SFNAME { {"x86_64-w64-mingw32-gcov "} }
SFNAME { {"x86_64-w64-mingw32-gcov-dump-posix "} }
SFNAME { {"x86_64-w64-mingw32-gcov-dump-win32 "} }
SFNAME { {"x86_64-w64-mingw32-gcov-posix "} }
SFNAME { {"x86_64-w64-mingw32-gcov-tool-posix "} }
SFNAME { {"x86_64-w64-mingw32-gcov-tool-win32 "} }
SFNAME { {"xzegrepw64-mingw32-gcov-win32 "} }
SFNAME { {"xzfgrepw64-mingw32-g++-posix "} }
SFNAME { {"xzgrep-w64-mingw32-gprof "} }
SFNAME { {"xzless-w64-mingw32-g++-win32 "} }
SFNAME { {"xzmore-w64-mingw32-ld "} }
SFNAME { {"yakuakew64-mingw32-ld.bfd "} }
SFNAME { {"yaml2obj-13mingw32-lto-dump-posix "} }
SFNAME { {"yaml2obj-14mingw32-lto-dump-win32 "} }
SFNAME { {"yaml-bench-13ngw32-nm "} }
SFNAME { {"yaml-bench-14ngw32-objcopy "} }
SFNAME { {"ybmtopbm64-mingw32-objdump "} }
SFNAME { {"yes_64-w64-mingw32-ranlib "} }
SFNAME { {"ypdomainnameingw32-readelf "} }
SFNAME { {"yuvsplittoppmngw32-size "} }
SFNAME { {"yuvtoppm64-mingw32-strings "} }
SFNAME { {"zcat64-w64-mingw32-strip "} }
SFNAME { {"zcmp64-w64-mingw32-windmc "} }
SFNAME { {"zdiff4-w64-mingw32-windres "} }
SFNAME { {"zdumpnergy_perf_policy "} }
SFNAME { {"zegrep "} }
SFNAME { {"zeisstopnm "} }
SFNAME { {"zfgrep "} }
SFNAME { {"zforcebm "} }
SFNAME { {"zgrepd "} }
SFNAME { {"ziplc "} }
SFNAME { {"zipcloakrd "} }
SFNAME { {"zipdetails "} }
SFNAME { {"zipgrep "} }
SFNAME { {"zipinfoe "} }
SFNAME { {"xcursorgen "} }
SFNAME { {"xcutsel "} }
SFNAME { {"xdg-dbus-proxy "} }
SFNAME { {"xdg-desktop-icon "} }
SFNAME { {"xdg-desktop-menu "} }
SFNAME { {"xdg-email "} }
SFNAME { {"xdg-icon-resource "} }
SFNAME { {"xdg-mime "} }
SFNAME { {"xdg-open "} }
SFNAME { {"xdg-screensaver "} }
SFNAME { {"xdg-settings "} }
SFNAME { {"xdg-user-dir "} }
SFNAME { {"xdg-user-dirs-update "} }
SFNAME { {"xditview "} }
SFNAME { {"xdotool "} }
SFNAME { {"xdpyinfo "} }
SFNAME { {"xdriinfo "} }
SFNAME { {"xedit "} }
SFNAME { {"xembedsniproxy "} }
SFNAME { {"xev "} }
SFNAME { {"xeyes "} }
SFNAME { {"xfd "} }
SFNAME { {"xfontsel "} }
SFNAME { {"xgamma "} }
SFNAME { {"xgc "} }
SFNAME { {"xhost "} }
SFNAME { {"ximtoppm "} }
SFNAME { {"xinit "} }
SFNAME { {"xinput "} }
SFNAME { {"xkbbell "} }
SFNAME { {"xkbcomp "} }
SFNAME { {"xkbevd "} }
SFNAME { {"xkbprint "} }
SFNAME { {"xkbvleds "} }
SFNAME { {"xkbwatch "} }
SFNAME { {"xkeystone "} }
SFNAME { {"xkill "} }
SFNAME { {"xload "} }
test_array:
DUP 128, fni
DW fnames + fni*SFNAME
EDUP
.end:
.count: EQU (.end-test_array)/2
SAVESNA "qsorts.sna", test_start ;; DEBUG snapshot
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment