Created
May 9, 2023 22:32
-
-
Save ped7g/5b29c9199494bf35ee5b0aeacf98df75 to your computer and use it in GitHub Desktop.
Z80 quicksort of array with pointers to 64 byte long strings
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| ; 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