Bubble Sort PASM
Shawna
Posts: 508
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
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
Comments
http://obex.parallax.com/snippet/556
Though better to start with something simpler if you want to learn pasm at the same.
Sort long 0[11]
' 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 496Repeat 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 SwappedHere 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 496Shawn
' 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 fitThe 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.Can not have calculus in runtime, statements like above can only be used in code to compile it in to a fix value.
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
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
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
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.
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.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.
Because this shadow register stuff confuses the heck out of some us students.
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.
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.
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.
I want to break this down further. In the spin code for the bubble sort I have a repeat loop, like this.
Will the PASM code below do the exact same thing?
'PASM Code Repeat 'code to repeat' TJNZ Swapped,RepeatThanks
Shawn
'Spin Repeat i from 9 to 0 'Code to Repeat.'PASM mov i,#9 Repeat_While 'Code to repeat. djnz i,Repeat_While#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.
'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 11Shawn
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 1I 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
I will get back to you.
Thanks
Shawn
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
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 1change: 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
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.