A method to compare strings lexographically using inline assembly

HydraHacker · 2023-06-07 20:33

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

PUB cmpStrs(str1adr, str2adr) : r | c
                org
                mov     ptra, str1adr              'move str1adr into ptra
                mov     ptrb, str2adr              'move str2adr into ptrb

.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

'if str1adr < str2adr then r = -1
'if str1adr > str2adr the r = 1
'if str1adr = str2adr then r = 0

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

Wuerfel_21 · 2023-06-07 20:57

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
                rdfast  #0,   str1adr
                mov     ptrb, str2adr

.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

HydraHacker · 2023-06-07 21:04

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

HydraHacker

Beau Schwabe · 2023-06-08 00:39

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.

HydraHacker · 2023-06-08 01:10

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

HydraHacker

A method to compare strings lexographically using inline assembly

Comments