Bubble Sort PASM

Shawna · 2013-07-12 19:12

Time for another trip into PASM.

I want to write a PASM Bubble sort routine to place in Jason Dorie's 9DOF object.

I know that the bubble sort is not very fast, but I only want to sort 11 to 21 values. I attempted to jam the pasm shell sort into Jason's 9DOD object and I was pretty close but I realized that the Shell sort was still accessing hub ram for the sort array. I want to try and avoid this. Also I do not understand the shell sort algorithm. I do understand the bubble sort algorithm.

In order to do this I have to learn more PASM and it has been awhile since I've dabbled in it.

Sort RES 11

Is this how one would declare an array in the DAT section? I am not finding anything in the manual that talks about PASM arrays. 399 pages, that is a lot of info.

Thanks
Shawn

tonyp12 · 2013-07-12 19:40

Collection of sorting algorithms for both string and decimal sorting
http://obex.parallax.com/snippet/556

Though better to start with something simpler if you want to learn pasm at the same.

SRLM · 2013-07-12 19:46

I think an int->ASCII Dec routine is a great place to start learning PASM.

Cluso99 · 2013-07-12 20:31

Sort Res 11 will reserve space at the end of the pasm program (11 longs) but it will not initialise them. If you need them to be initialised, then use
Sort long 0[11]

JonnyMac · 2013-07-12 20:37

As you're wanting to manipulate a cog-based array this fragment may be helpful -- it's what I used for reading and writing within a cog.

' basepntr = address of cog array/table
' idx = index of element to read
' value = value that is read

read                    mov     t1, basepntr
                        add     t1, idx
                        movs    :rdval, t1
                        nop
:rdval                  mov     value, 0-0
read_ret                ret


' basepntr = address of cog array/table 
' idx = index of element to write
' value = value to write

write                   mov     t1, basepntr
                        add     t1, idx
                        movd    :wrval, t1
                        nop
:wrval                  mov     0-0, value
write_ret               ret


' --------------------------------------------------------------------------------------------------

basepntr                res     1                               ' for tables r/w
idx                     res     1
value                   res     1

t1                      res     1                               ' work vars
t2                      res     1

                        fit     496

Shawna · 2013-07-12 22:16

Thanks for the info. Here is my main loop written in spin for the bubble sort.

Repeat
    Swapped := false
    Repeat i from 0 to 9
      If Sort[i] > Sort[i+1]
         temp:= Sort[i]
        Sort[i]   := Sort[i+1]
        Sort[i+1] := temp
        Swapped   := True
        
  While Swapped

Here is my first attempt at the PASM version of the bubble loop above(I have butchered it). I realize it will not do anything in its current state but I think I have the meat of it written. Its to bed for me.

DAT


        ORG 0
Bubble_Sort
              
Main_Loop                             'Repeat
              mov i,#0
              mov Swapped,#0          'Swapped := False


              cmps sort + (i + 1),sort + i wc  'If Sort[i] > Sort[i+1] 
     if_c     mov  temp,sort + i               'temp      := Sort[i]
     if_c     mov  sort + i,sort + (i + 1)     'Sort[i]   := Sort[i+1]
     if_c     mov  sort + (i + 1),temp         'Sort[i+1] := temp
     if_c     mov  Swapped,#1                  'Swapped   := True


              cmp i,#9 wz      
              add i,#1          
              
     if_z     cmp Swapped,#0  wz
     if_nz    jmp #Main_Loop


Main_Loop_RET ret
'Variables for BubbleSort
temp        long    0
i           long    0                       
swapped     long    0
sort        Res     11                       




FIT   496

Shawn

JonnyMac · 2013-07-13 00:32

There are PASM gurus here that will show you better code, I'm sure, but I decided to bash out an attempt while watching the tele. The demo includes Spin and PASM version of the sort and timing for each. The Spin version takes between 2 and 5 milliseconds, the PASM version less than 200us. The PASM code does work, but is written to be obvious, not necessarily as fast as it could be.

kuroneko · 2013-07-13 01:43

' bubble sort subroutine
 
main            mov     ecnt, #lcnt -1 wc,wz    ' loop iterations (carry clear, zero clear)

                mov     body +0, code +0        ' |
                mov     body +1, code +1        ' |
                mov     body +2, code +2        ' |
                mov     body +3, code +3        ' initialise/reset code

body            nop                             ' |
                nop                             ' |
                nop                             ' |
                nop                             ' comparison and swap

                add     body +0, d1s1           ' |
                add     body +1, d1s1           ' |
                add     body +2, d1s1           ' |
                add     body +3, d1s1           ' update array indexes

        if_c    test    $, #0 wz                ' set zero if swap happened (z |= c)

                djnz    ecnt, #body

        if_z    jmp     #main                   ' again if swapped

main_ret        ret

' initialised data and/or presets

code            cmps    data +1, data +0 wc
        if_c    xor     data +0, data +1
        if_c    xor     data +1, data +0
        if_c    xor     data +0, data +1

dst1            long    |< 9
d1s1            long    |< 9 | 1
data            long    -1[lcnt]

' uninitialised data and/or temporaries

ecnt            res     1
addr            res     1

                fit

The program is setup for 11 pseudo random entries, it first displays the SPIN results (before/after) then the PASM results with added timestamp. After a keypress a new set of values is sorted and displayed.

tonyp12 · 2013-07-13 07:52

>cmps sort + (i + 1),sort + i wc 'If Sort > Sort[i+1]

Can not have calculus in runtime, statements like above can only be used in code to compile it in to a fix value.

Shawna · 2013-07-13 09:29

Wow guys, thats a lot of information. Thanks

It is going to take awhile to sort through all of that. Well, its off to the Cornhusker State Games for a swim meet. Hopefully they will have a place for me to plug in my PC

Shawn

tonyp12 · 2013-07-13 15:06

Are the values in hub first at one time?
Are they just single longs (32bit) signed values?
Do you want a option of the numbers of variable values to sort each time?

If the above is true, could set up a mailbox.

var
long mylenght
long data[22]
cognew(@entry, @mylenght)
spin populate list
spin mylenght := 21
spin repeat until mylenght ==0 ' wait for cog to have sorted it

entry rdlong t1,par wz
if_z jmp #entry
mov t1,par
add t1,#4
rdlong t2,t1
add t1,#4
rdlong t3,t1
cmps t3,t2 wc
---bubble sort
wrlong zerobyte,par ' send $0000
jmp #entry

StephenMoore · 2013-07-13 17:07

I have a quick question on noticing the use of the cnt psuedo-register to do elapsed time (and also as a general purpose register for cogid/cogstop)...

are the psuedo-registers only updated by the corresponding system value when an actual instruction has the corresponding system value in the source field?

Most students of Prop are told not to use system registers in the dest field.

This is a great teaching example of PASM code... thank you.

sm

tonyp12 · 2013-07-13 17:22

cnt (and like par) are read only (source side)
as cnt is updated by Prop all the time, a mov par,par will take snap shoot of current 'time' and copy it to a location in destination.
In this example it's a 'free' location for you to use as cnt on the dest side is a shadow register and will not be updated by the Prop.

kuroneko · 2013-07-13 17:22

StephenMoore wrote: »

are the psuedo-registers only updated by the corresponding system value when an actual instruction has the corresponding system value in the source field?

Let's just say the value used by an insn (based on a particular register) is different depending on where the register is located (dst/src, shd = shadow register). Note that there are other oddities with the usage of max/min/cmpsub when applied to special registers.

dst     src
        
par     shd     coginit value
cnt     shd     system counter
ina     shd     pin state
inb      -       -
outa     -       -
outb     -       -
dira     -       -
dirb     -       -
ctra     -       -
ctrb     -       -
frqa     -       -
frqb     -       -
phsa    shd     counter h/w    '
phsb    shd     counter h/w    ' [COLOR="#FFA500"]writing to shd affects both shadow register and counter h/w[/COLOR]
vcfg     -       -
vscl     -       -

For example I keep aliasing par as zero and then do stuff like wrlong zero, addr.

StephenMoore wrote: »

Most students of Prop are told not to use system registers in the dest field.

And they listen to this why? Once they stumble accross the side effects they could come back asking about it or they figure it out themselves.

Duane Degn · 2013-07-13 17:57

kuroneko wrote: »

And they listen to this why?

Because this shadow register stuff confuses the heck out of some us students.

Shawna · 2013-07-13 18:15

You guys are overwhelming me with info, keep it coming.

I still haven't had enough time to look at it all in depth, I just got home.

My intent for this bubble sort is to place it in the Dat section of Jason Dorie's 9DOF object. I am going to call it after the 9DOF object reads the Accelerometer. I am going to use the bubble sort for a median filter for my raw accelerometer data. I want the arrays in cog memory only, I only need the median value from the three axis's passed to hub memory.

So what I will have are 4 arrays, 1 for each axis of the accelerometer that keeps a running array of values and dumps the oldest value every time the ACC is read. The 4th axis is a temporary array that is used to sort the 3 ACC arrays.

I will update all three arrays with the new acc values. Then I will move the first acc array into the temporary array and use the bubble sort to sort it. Then I will pull out the median value from the temporary array and place it into hub memory for use in my main spin loop. I will do the same thing for the next 2 acc arrays and then the process will start all over.

Duane Degn · 2013-07-13 18:33

Is there a reason to use the median rather than an average?

I know I have PASM code to average the values of a ring buffer in hub RAM. The ring buffer does need to be a power of two in size so shift right can be used instead of needing to divide. I'll be happy to post it if you're interested. I'm betting it's much faster than finding the median.

I'm glad you asked about PASM code for a bubble sort. I'm learning a lot in from the replies in this thread.

Shawna · 2013-07-13 19:10

Duane
I have no real proof that a median filter will be more beneficial. Actually after I run the acc values through the median filter I want to use a running average filter also. I read a blog where a guy was having problems with noise from his accelerometer, he ran the raw values through a median filter and then through a low pass filter, he seemed to be happy with the result.

If I understand the median filter properly, there is really no lag or latency or offset error from over filtering. The only latency there is, is determined by how many values are in your median filter. With a small array the latency would be very minimal.

The benefit of the median filter is this, lets say you read 5 consecutive readings from your acc and they are as follows. 10,15,89,14,12 With the median filter you will never see that value of 89 and it is probably noise any way. With an averaging filter you are going to average that value of 89 into your output no matter what. The median filter just says forget that value its garbage. At least that the theory behind it.

I have yet to actually test this on my quad. I have added it to my flight code but I have not enabled it yet. I played with the code with the acc just sitting on the table and I could see a difference in the noise level. The spin code was slow, it took 1.5ms to do all three axis. It should fly in PASM.

I am terrible with PASM though, whether this works or not it will be a good learning experience.

Shawna · 2013-07-13 19:26

The examples you guys have posted are great, thank you. I however do not want to just cut and paste your code, I want to understand how the code works and I am over my head.
I want to break this down further. In the spin code for the bubble sort I have a repeat loop, like this.

'Spin Code

Repeat
   'code to repeat'              
   While Swapped

Will the PASM code below do the exact same thing?

'PASM Code

Repeat
        'code to repeat'
        TJNZ Swapped,Repeat

Thanks
Shawn

Shawna · 2013-07-13 20:17

And then are these two pieces of code equivalent.

'Spin
        Repeat i from 9 to 0
              'Code to Repeat.

'PASM  
              mov i,#9
Repeat_While


              'Code to repeat.
              djnz i,Repeat_While

kuroneko · 2013-07-13 20:22

#19: OK (#Repeat)
#20: No, the SPIN loop runs 10 times while the PASM loop runs only 9 times (#Repeat_While). Running the SPIN loop from 9 to 1 would give you the same behaviour.

Shawna · 2013-07-13 20:28

I wondered about that, but it makes sense after reading the Prop manual closer.

DJNZ
Instruction: Decrement value and jump to address if not zero.
DJNZ Value, Address
Result: Value-1 is written to Value.
Value (d-field) is the register to decrement and test.

Shawna · 2013-07-14 08:54

OK, how about these two pieces of code, are they the same.

'Spin
long i
long sort[11]


i := 10
        If Sort[i] < Sort[i-1]
              'do something

'PASM
        mov imo,i
        sub imo,#1
        cmps Sort + i,Sort + imo wc
   if_c 'do something


imo  long 0
i      long 10
Sort Res 11

Shawn

tonyp12 · 2013-07-14 09:20

>cmps Sort + i,Sort + imo
I repeat, you can not have runtime calculus.
And bubble sort is about bubbling up, so starting at the bottom is not correct (at least visually)

pasm deals with array by self modifying code, you would have to add #1 to source and dest side of the cmps

       movs  lable,#sort
       movd  lable,#sort+1   ' pre-compile calculus allowed
       mov   t1,#9           ' lengh-1  (and a line of code is needed between movd and lable)
lable  cmps  0-0,0-0 wc
       --sort-
       add lable,mybit9_0    ' add 1 to both source and dest field
       djnz t1,#lable        ' run inner loop 9 times as you should not cmp the last value with what would be a out of bound value

mybit9_0  long  1<<9 + 1
sort      long 782,-23,4765,78,-2342,11,-22,600,700,455
t1        res 1

Shawna · 2013-07-14 09:28

Hey Tony when you said calculus in runtime I thought you meant something like this. Sort + [i+1] not this Sort + 1.

I reordered my bubble sort spin code to run from bottom up and it worked, I guess it is no longer a bubble sort.

Smile I have to go.

Thanks

Shawna · 2013-07-14 09:43

I had a reason for doing this Sort + i, but I do not remember where I came up with it.
I will get back to you.

Thanks
Shawn

StephenMoore · 2013-07-14 09:43

In running these pieces of code I realize there are many ways to be really efficient in the use of cog RAM:

e.g. moving code into body section of Kuroneko program snippet

Sometimes it gets a bit cryptic and I am far from understanding how to maximize the use of each and every register within a code/data block of cog memory.

Does anyone have an example of extremely (or the most) powerful program(s) ever loaded into a single cog? With 512 longs there has to be a limit but who has reached it and know that they can not pack another bit of functionality within 2K of logic?

There should be some sort of Parallax Hall of Fame for generally acknowledged 'super-cog' examples that the novice can shoot for.

This is probably a ridiculous piece of rhetoric but I am curious.

sm

tonyp12 · 2013-07-14 10:00

as sorting routine will also have to use selfmod code, it start looking a little complicated

        mov   t3,#9            ' run outer loop 9 times(lengh-1)  
mainloop 
        movs  lable1,#sort     ' copy the address location of sort
        movd  lable1,#sort+1   ' pre-compile calculus allowed
        movs  lable2,#sort
        movs  lable3,#sort+1
        movd  lable3,#sort
        movd  lable4,#sort+1
        mov   t1,#9            ' inner loop (lengh-1) 
lable1  cmps  0-0,0-0 wc
lable2  if_c  mov t2,0-0       ' copy sort to temp
lable3  if_c  mov 0-0,0-0      ' copy sort+1 to sort
lable4  if_c  mov 0-0,t2       ' copy temp to sort+1
        add   lable1,mybit9_0  ' add 1 to both source and dest field
        add   lable2,#1        ' add 1 to source field
        add   lable3,mybit9_0  ' add 1 to both source and dest field
        add   lable4,mybit9    ' add 1 to dest field
        djnz  t1,#lable1       ' loop 9 times as you should not cmp the last value with what would be a out of bound value
        djnz  t3,#mainloop 

mybit9_0  long  1<<9 + 1
mybit9    long  1<<9 
sort      long 782,-23,4765,78,-2342,11,-22,600,700,455
t1        res 1
t2        res 1
t3        res 1

StephenMoore · 2013-07-14 10:19

Very clean example. Short of the OBEX (wherein lies programs like F32), does anyone have a list of 'library' of PASM routines for general purpose uses?

tonyp12 · 2013-07-14 10:58

apparently in bubble sort you can stop the outer loop if a completed inner loop never changed a single pair.

change: mov t1,#9 wz ' inner loop (lengh-1) and set z=0
[insert after lable4] if_c cmpsub 0, 0 wz,nr 'set z=1 sorry need to outer loop again
change: if_z djnz t3,#mainloop

Shawna · 2013-07-14 11:02

Ok I know where I got the Sort + 1, and you just confirmed my error Tony.
I used Prop Basic to translate to PASM. I put this code in as Prop Basic.

aXhold(10) = aXhold(9)

And it spit this out as PASM.

mov axhold+10,axhold+9

axhold res 11

I figured I could use this argument anywhere. Sort + 1

I will try again.

Bubble Sort PASM

Comments