<![CDATA[;**** A P P L I C A T I O N N O T E A V R 2 2 0 ************************
;*
;* Title: Bubble Sort Algorithm
;* Version: 1.0
;* Last updated: 97.07.04
;* Target: AT90Sxx1x (Devices with SRAM)
;*
;* Support E-mail: avr@atmel.com
;*
;* DESCRIPTION
;* This Application note shows how to sort a block of data in SRAM using
;* the code efficient Bubble Sort Algorithm. The App. note contains a test
;* program which copies a 60-byte block of data from program memory to
;* SRAM and sorts the data.
;*
;***************************************************************************
.include "8515def.inc"
.equ SIZE =60 ;data block size
.equ TABLE_L =$60 ;Low SRAM address of first data element
.equ TABLE_H =$00 ;High SRAM address of first data element
rjmp RESET ;Reset Handle
;***************************************************************************
;*
;* "bubble"
;*
;* This subroutine bubble sorts the number of bytes found in "cnt1" + 1
;* with the last element in SRAM at location "last".
;* This implementation sorts the data with the highest element at the
;* lowest SRAM address. The sort order can be reversed by changing the
;* "brlo" statement to "brsh". Signed sort can be obtained by using "brlt"
;* or "brge"
;*
;* Number of words :13 + return
;* Number of cycles :6*(SIZE-1)+10*(SIZE(SIZE-1))+return (Min)
;* 6*(SIZE-1)+13*(SIZE(SIZE-1))+return (Max)
;* Low registers used :3 (A,B,cnt2)
;* High registers used :3 (cnt1,endL,endH)
;* Pointers used :Z
;*
;***************************************************************************
;***** Subroutine Register Variables
.def A =r13 ;first value to be compared
.def B =r14 ;second value to be compared
.def cnt2 =r15 ;inner loop counter
.def cnt1 =r16 ;outer loop counter
.def endL =r17 ;end of data array low address
.def endH =r18 ;end of data array high address
;***** Code
bubble:
mov ZL,endL
mov ZH,endH ;init Z pointer
mov cnt2,cnt1 ;counter2 <- counter1
i_loop: ld A,Z ;get first byte, A (n)
ld B,-Z ;decrement Z and get second byte, B (n-1)
cp A,B ;compare A with B
brlo L1 ;if A not lower
st Z,A ; store swapped
std Z+1,B
L1: dec cnt2
brne i_loop ;end inner loop
dec cnt1
brne bubble ;end outer loop
ret
;***************************************************************************
;*
;* Test Program
;*
;* This program copies 60 bytes of data from Program memory to SRAM. It
;* then calls "bubble" to get the data sorted.
;*
;***************************************************************************
RESET:
;***** Main program Register variables
.def temp =r16
;***** Code
ldi temp,low(RAMEND)
out SPL,temp
ldi temp,high(RAMEND)
out SPH,temp ;init Stack Pointer
;***** Memory fill
clr ZH
ldi ZL,tableend*2+1 ;Z-pointer <- ROM table end + 1
ldi YL,low(256*TABLE_H+TABLE_L+SIZE)
ldi YH,high(256*TABLE_H+TABLE_L+SIZE)
;Y pointer <- SRAM table end + 1
loop: lpm ;get ROM constant
st -Y,r0 ;store in SRAM and decrement Y-pointer
sbiw ZL,1 ;decrement Z-pointer
cpi YL,TABLE_L ;if not done
brne loop ; loop more
cpi YH,TABLE_H
brne loop
;***** Sort data
sort: ldi endL,low(TABLE_H*256+TABLE_L+SIZE-1)
ldi endH,high(TABLE_H*256+TABLE_L+SIZE-1)
;Z <- end of array address
ldi cnt1,SIZE-1 ;cnt1 <- size of array - 1
rcall bubble
forever:rjmp forever
;***** 60 ROM Constants
table:
.db 120,196
.db 78,216
.db 78,100
.db 43,39
.db 241,43
.db 62,172
.db 109,69
.db 48,184
.db 215,231
.db 63,133
.db 216,8
.db 121,126
.db 188,98
.db 168,205
.db 157,172
.db 108,233
.db 80,255
.db 252,102
.db 198,0
.db 171,239
.db 107,114
.db 172,170
.db 17,45
.db 42,55
.db 34,174
.db 229,250
.db 12,179
.db 187,243
.db 44,231
tableend:
.db 76,48
]]>