A method to compare strings lexographically using inline assembly — Parallax Forums

# A method to compare strings lexographically using inline assembly

Posts: 75
edited 2023-06-07 20:51

Hello Everybody,
I wrote this inline P2 assembly code to sort strings lexographically. I wrote a small demo program using my siblings names, no Altaira was not one of my siblings, she was in one of my favorite movies "Forbidden Planet". The sort algorithm that I used is very inefficient but easy to program, a 'bubble sort'

HydraHacker

```CON
_clkfreq = 180_000_000
numElemnts = 13

PUB main() | l, t, t1

debug("Unsorted list")

repeat l from 0 to numElemnts - 1
debug(zstr_(@@strsPtrTb[l]), dly(250))

debug(zstr_(string(" ")))

t:=getct()
bubbleSort()
t1:=getct()

debug("Sorted list")
printList()

debug(udec(t1-t-40))

repeat

org

.l              rdbyte  r, ptra++                  'read str1 byte into r, then inc ptra
rdbyte  c, ptrb++                  'read str2 byte into c, then inc ptrb
sub     r, c            wcz        'subtract c from r, set cz flags
if_z            tjnz    c, #.l                     'if r = c and c <> 0 then jmp to .l

if_c            mov     r, ##-1                    'if r < c then r = -1
if_nc_and_nz    mov     r, #1                      'if r > c and r <> c then r = 1
end

'defines what r means upon method(s) exit

PUB bubbleSort () | l, sf, t
repeat
sf := false                                                    'swap flag = false
repeat l from 0 to numElemnts - 2                              'loop through all elements minus two
if cmpStrs(@@strsPtrTb[l + 1], @@strsPtrTb[l]) == -1        'if strsPtrTb[index + 1] < strsPtrTb[index] then swap elements
t := strsPtrTb[l]
strsPtrTb[l] := strsPtrTb[l + 1]
strsPtrTb[l + 1] := t
sf := true                                               'swap flag set if two elements were swapped
while sf                                                          'repeat loop if any swaps were made

PUB printList() | l
repeat l from 0 to numElemnts - 1
debug(zstr_(@@strsPtrTb[l]), dly(250))

DAT
nme1    byte "Jeff", 0
nme2    byte "Dave", 0
nme3    byte "Brian", 0
nme4    byte "Kenny", 0
nme5    byte "Diane", 0
nme6    byte "pam", 0
nme7    byte "Jimmy", 0
nme8    byte "Debbie", 0
nme9    byte "Altaira", 0
nme10   byte 0
nme11   byte "Katherine", 0
nme12   byte "Jim", 0
nme13   byte 0

strsPtrTb word @nme1, @nme2, @nme3, @nme4, @nme5, @nme6, @nme7, @nme8, @nme9, @nme10, @nme11, @nme12 ,@nme13
```

• Posts: 4,197

Aaaa a bubble, it is evil, stop it before it is too late!

I once implemented (with some help) with a more efficient algorithm for sorting files in VentilatorOS.

```PRI sortFiles(length) : i | ip,jp,i2p,zonep,k,realsize,subsize,sizze,temp[12/4]
'' Sort the Files...

if length < 2                                              ' no need to sort if < 2 entries
return

'' Non-recursive in-place sorting algorithm
'' As relayed to me by a friendly Discord user
'' (ported to spin and optimized by me)
subsize := 12
length *= 12
repeat while subsize < length
sizze := subsize<<1
repeat i from 0 to length-12 step sizze
jp := (ip:=@sort+i)+subsize
realsize := sizze <# (length-i)
i2p := ip
repeat k from 0 to realsize-12 step 12
if jp => (ip+realsize) or i2p => jp
'pass
elseif compareNames(i2p,jp) =< 0
i2p += 12
else
zonep := jp
repeat
if (zonep+12) == (ip+realsize)
longmove(@temp, i2p,3)
longmove(i2p,jp,3)
longmove(jp,jp+12,(zonep-jp)>>2)
longmove(zonep,@temp,3)
if jp == zonep
i2p += 12
else
k -= 12
quit
elseif compareNames(zonep+12,i2p) > 0
longmove(@temp, i2p,3)
longmove(i2p,jp,3)
longmove(jp,jp+12,(zonep-jp)>>2)
longmove(zonep,@temp,3)
if jp == zonep
i2p += 12
else
k -= 12
quit
zonep += 12
subsize := sizze
```

This as-is is obviously written for 12-character strings in an array, but it of course applies to any sort operation. Also, this is Spin 1, take care.

Also, you can make the string compare much faster by using the FIFO for one of the strings

```PUB cmpStrs(str1adr, str2adr) : r | c
org

.l              rfbyte  r
rdbyte  c, ptrb++
sub     r, c            wcz
if_z    tjnz    c, #.l

if_nz   sar     r,#31
if_nz   or      r,#1
end
```
• Posts: 75

Wuerfel_21,
Thank you for speeding up my inline assembly with rdfast, I'll try that out later!

HydraHacker

• Posts: 6,540

If you can sacrifice an additional BYTE after the terminating 0, use that as an Index. So instead of moving the entire BYTE contents, just change the Index value to reflect the sort order.

• Posts: 75

Beau Schwabe,
Yes that would improve the speed, thanks for the suggestion.

HydraHacker