Skip to content

Instantly share code, notes, and snippets.

@mengstr

mengstr/sorttest.asm

Last active May 7, 2019 18:03
Show Gist options
  • Save mengstr/66c658a3a97d58adf0351087865f818e to your computer and use it in GitHub Desktop.
Save mengstr/66c658a3a97d58adf0351087865f818e to your computer and use it in GitHub Desktop.
Download ZIP
Atari 2600 sorting of 8 byts of data
Raw
sorttest.asm
;
; Results for sorting 8 bytes
;
; First value is the number of scanlines required for pre-sorted data, second is
; for data that is fully reverse order.
;
; Yellow 3.0 - 7.5 (369 bytes) Continous Unrolled
; Orange 7.5 - 12.0 (262 bytes) Continous Subroutined
; Red 4.0 - 9.0 (138 bytes) Continous Fallthrough
; Blue 2.4 - 29.9 ( 51 bytes) Bubblesort
; Green 12.1 - 14.0 ( 53 bytes) Optisort
processor 6502
VSYNC = $00
VBLANK = $01
WSYNC = $02
COLUPF = $08
COLUBK = $09
TIMINT = $285
TIM64T = $296
BLACK = $00
MIDGREY = $04
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
seg.u Variables
org $80
NVAL ds 1 ; Used by OptSort & BubbleSort8 as array-length
output ds 8 ; The sorted array
input ds 8 ; The array data to be sorted
ZPADD ds 2 ; Used by OptSort & BubbleSort8 as pointer to array
WORK1 ds 1 ; Used by OptSort & BubbleSort8 as scratch
WORK2 ds 1 ; Used by OptSort & BubbleSort8 as scratch
WORK3 ds 1 ; Used by OptSort & BubbleSort8 as scratch
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
echo "----",($00FE - *) , "bytes of RAM left"
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
MAC CLEAN_START
sei
cld
ldx #0
txa
tay
.CLEAR_STACK
dex
txs
pha
bne .CLEAR_STACK ; SP=$FF, X = A = Y = 0
ENDM
MAC START_VSYNC_AND_BLANKING_TIMER
lda #2
sta WSYNC
sta VSYNC ; Turn on vertical sync signal
sta VBLANK ; Turn on forced blanking
lda #47 ; Set timer to end of vertical blanking
sta TIM64T
sta WSYNC ; Line 1 of vsync
sta WSYNC ; Line 2 of vsync
lda #0
sta WSYNC ; Line 3 of vsync
sta VSYNC ; Turn off vertical sync signal
sta VBLANK ; Turn off forced blanking
ENDM
MAC WAITLINES
.cnt SET {1}
REPEAT .cnt
sta WSYNC
REPEND
ENDM
MAC CHECK_SWAP
.fi SET {1}
.se SET {2}
cmp output+.fi
bcs .ok
tax
lda output+.fi
sta output+.se
txa
sta output+.fi
.ok
ENDM
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; CODE START
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
seg Code
org $f000
Start
CLEAN_START
NextFrame
START_VSYNC_AND_BLANKING_TIMER
lda #BLACK
sta COLUPF
WaitBL ; Wait for blanking to end
sta WSYNC
bit TIMINT
bpl WaitBL
; Video drawing kernel
lda #227
sta TIM64T
lda #MIDGREY
sta COLUBK
WAITLINES 3
jsr ClearOutput
jsr SetInputPresorted
sta WSYNC
lda #$18
sta COLUBK
jsr ContinousUnrolled
lda #MIDGREY
sta COLUBK
WAITLINES 3
jsr ClearOutput
jsr SetInputReversed
sta WSYNC
lda #$18
sta COLUBK
jsr ContinousUnrolled
lda #MIDGREY
sta COLUBK
WAITLINES 3
jsr ClearOutput
jsr SetInputPresorted
sta WSYNC
lda #$2A
sta COLUBK
jsr ContinousSubroutined
lda #MIDGREY
sta COLUBK
WAITLINES 3
jsr ClearOutput
jsr SetInputReversed
sta WSYNC
lda #$2A
sta COLUBK
jsr ContinousSubroutined
lda #MIDGREY
sta COLUBK
WAITLINES 3
jsr ClearOutput
jsr SetInputPresorted
sta WSYNC
lda #$4A
sta COLUBK
jsr ContinousFallthrough
lda #MIDGREY
sta COLUBK
WAITLINES 3
jsr ClearOutput
jsr SetInputReversed
sta WSYNC
lda #$4A
sta COLUBK
jsr ContinousFallthrough
lda #MIDGREY
sta COLUBK
WAITLINES 3
jsr SetOutputPresorted
sta WSYNC
lda #$76
sta COLUBK
lda #8
sta NVAL
lda #<output-1
sta ZPADD+0
lda #>output
sta ZPADD+1
jsr BubbleSort8
lda #MIDGREY
sta COLUBK
WAITLINES 3
jsr SetOutputReversed
sta WSYNC
lda #$76
sta COLUBK
lda #8
sta NVAL
lda #<output-1
sta ZPADD+0
lda #>output
sta ZPADD+1
jsr BubbleSort8
lda #MIDGREY
sta COLUBK
WAITLINES 3
jsr SetOutputPresorted
sta WSYNC
lda #$B8
sta COLUBK
lda #8
sta NVAL
lda #<output-1
sta ZPADD+0
lda #>output
sta ZPADD+1
jsr OptSort
lda #MIDGREY
sta COLUBK
WAITLINES 3
jsr SetOutputReversed
sta WSYNC
lda #$B8
sta COLUBK
lda #8
sta NVAL
lda #<output-1
sta ZPADD+0
lda #>output
sta ZPADD+1
jsr OptSort
lda #MIDGREY
sta COLUBK
WaitKE ; Wait for kernel to end
sta WSYNC
bit TIMINT
bpl WaitKE
; Start the overscan timer
lda #33
sta TIM64T
lda #BLACK
sta COLUBK
WaitOS ; Wait for overscan to end
sta WSYNC
bit TIMINT
bpl WaitOS
jmp NextFrame
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Bubble sort
; http://6502.org/source/sorting/bubble8.htm
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
BubbleSort8
LDY #$00 ;TURN EXCHANGE FLAG OFF (= 0)
STY WORK1
LDA (ZPADD),Y ;FETCH ELEMENT COUNT
TAX ; AND PUT IT INTO X
INY ;POINT TO FIRST ELEMENT IN LIST
DEX ;DECREMENT ELEMENT COUNT
NXTEL LDA (ZPADD),Y ;FETCH ELEMENT
INY
CMP (ZPADD),Y ;IS IT LARGER THAN THE NEXT ELEMENT?
BCC CHKEND
BEQ CHKEND
;YES. EXCHANGE ELEMENTS IN MEMORY
PHA ; BY SAVING LOW BYTE ON STACK.
LDA (ZPADD),Y ; THEN GET HIGH BYTE AND
DEY ; STORE IT AT LOW ADDRESS
STA (ZPADD),Y
PLA ;PULL LOW BYTE FROM STACK
INY ; AND STORE IT AT HIGH ADDRESS
STA (ZPADD),Y
LDA #$FF ;TURN EXCHANGE FLAG ON (= -1)
STA WORK1
CHKEND DEX ;END OF LIST?
BNE NXTEL ;NO. FETCH NEXT ELEMENT
BIT WORK1 ;YES. EXCHANGE FLAG STILL OFF?
BMI BubbleSort8 ;NO. GO THROUGH LIST AGAIN
RTS ;YES. LIST IS NOW ORDERE
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; SORTING SUBROUTINE CODED BY MATS ROSENGREN ([email protected])
; http://6502.org/source/sorting/optimal.htm
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
OptSort:
LDY NVAL ;START OF SUBROUTINE SORT
LDA (ZPADD),Y ;LAST VALUE IN (WHAT IS LEFT OF) SEQUENCE TO BE SORTED
STA WORK3 ;SAVE VALUE. WILL BE OVER-WRITTEN BY LARGEST NUMBER
JMP L2
L1 DEY
BEQ L3
LDA (ZPADD),Y
CMP WORK2
BCC L1
L2 STY WORK1 ;INDEX OF POTENTIALLY LARGEST VALUE
STA WORK2 ;POTENTIALLY LARGEST VALUE
JMP L1
L3 LDY NVAL ;WHERE THE LARGEST VALUE SHALL BE PUT
LDA WORK2 ;THE LARGEST VALUE
STA (ZPADD),Y ;PUT LARGEST VALUE IN PLACE
LDY WORK1 ;INDEX OF FREE SPACE
LDA WORK3 ;THE OVER-WRITTEN VALUE
STA (ZPADD),Y ;PUT THE OVER-WRITTEN VALUE IN THE FREE SPACE
DEC NVAL ;END OF THE SHORTER SEQUENCE STILL LEFT
BNE OptSort ;START WORKING WITH THE SHORTER SEQUENCE
RTS
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; This is a type of bubble sort that moves data from an unsorted
; array into the sorted array by appending each byte and at a time
; to the the end of the sorted array and then bubble bubble the byte
; up to where it belongs
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
ContinousUnrolled:
lda input+0 ; Store first byte of data
sta output+0
lda input+1 ; Append the second byte of data and check
sta output+1 ; if it is smaller to the byte above it - if so
CHECK_SWAP 0,1 ; then bubble it up until done
lda input+2 ; Same for the third data-byte, but here we need
sta output+2 ; compare with the two previos bytes
CHECK_SWAP 1,2
CHECK_SWAP 0,1
lda input+3
sta output+3
CHECK_SWAP 2,3
CHECK_SWAP 1,2
CHECK_SWAP 0,1
lda input+4
sta output+4
CHECK_SWAP 3,4
CHECK_SWAP 2,3
CHECK_SWAP 1,2
CHECK_SWAP 0,1
lda input+5
sta output+5
CHECK_SWAP 4,5
CHECK_SWAP 3,4
CHECK_SWAP 2,3
CHECK_SWAP 1,2
CHECK_SWAP 0,1
lda input+6
sta output+6
CHECK_SWAP 5,6
CHECK_SWAP 4,5
CHECK_SWAP 3,4
CHECK_SWAP 2,3
CHECK_SWAP 1,2
CHECK_SWAP 0,1
lda input+7
sta output+7
CHECK_SWAP 6,7
CHECK_SWAP 5,6
CHECK_SWAP 4,5
CHECK_SWAP 3,4
CHECK_SWAP 2,3
CHECK_SWAP 1,2
CHECK_SWAP 0,1
rts
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; This is the same as the ContinousUnrolled, but here the
; unrolled/inlined compare-and-swap macros are put into
; subroutines to reduce the code length a bit. But this
; causes a a bit of increased execution time
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
ContinousSubroutined:
lda input+0
sta output+0
lda input+1
sta output+1
jsr ContinousSubroutined01
lda input+2
sta output+2
jsr ContinousSubroutined12
jsr ContinousSubroutined01
lda input+3
sta output+3
jsr ContinousSubroutined23
jsr ContinousSubroutined12
jsr ContinousSubroutined01
lda input+4
sta output+4
jsr ContinousSubroutined34
jsr ContinousSubroutined23
jsr ContinousSubroutined12
jsr ContinousSubroutined01
lda input+5
sta output+5
jsr ContinousSubroutined45
jsr ContinousSubroutined34
jsr ContinousSubroutined23
jsr ContinousSubroutined12
jsr ContinousSubroutined01
lda input+6
sta output+6
jsr ContinousSubroutined56
jsr ContinousSubroutined45
jsr ContinousSubroutined34
jsr ContinousSubroutined23
jsr ContinousSubroutined12
jsr ContinousSubroutined01
lda input+7
sta output+7
jsr ContinousSubroutined67
jsr ContinousSubroutined56
jsr ContinousSubroutined45
jsr ContinousSubroutined34
jsr ContinousSubroutined23
jsr ContinousSubroutined12
jsr ContinousSubroutined01
rts
ContinousSubroutined01
CHECK_SWAP 0,1
rts
ContinousSubroutined12
CHECK_SWAP 1,2
rts
ContinousSubroutined23
CHECK_SWAP 2,3
rts
ContinousSubroutined34
CHECK_SWAP 3,4
rts
ContinousSubroutined45
CHECK_SWAP 4,5
rts
ContinousSubroutined56
CHECK_SWAP 5,6
rts
ContinousSubroutined67
CHECK_SWAP 6,7
rts
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Here we take advantage of the fact that it is possible to
; fall through to the next compare-and-swap function to reduce
; the number of jsr/rts's made in total
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
ContinousFallthrough:
lda input+0
sta output+0
lda input+1
sta output+1
jsr ContinoutFallthrough01
lda input+2
sta output+2
jsr ContinoutFallthrough12
lda input+3
sta output+3
jsr ContinoutFallthrough23
lda input+4
sta output+4
jsr ContinoutFallthrough34
lda input+5
sta output+5
jsr ContinoutFallthrough45
lda input+6
sta output+6
jsr ContinoutFallthrough56
lda input+7
sta output+7
jsr ContinoutFallthrough67
rts
ContinoutFallthrough67
CHECK_SWAP 6,7
ContinoutFallthrough56
CHECK_SWAP 5,6
ContinoutFallthrough45
CHECK_SWAP 4,5
ContinoutFallthrough34
CHECK_SWAP 3,4
ContinoutFallthrough23
CHECK_SWAP 2,3
ContinoutFallthrough12
CHECK_SWAP 1,2
ContinoutFallthrough01
CHECK_SWAP 0,1
rts
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; Utility functions for pre-setting the arrays to know values
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
ClearOutput:
lda #$ff
sta output+0
sta output+1
sta output+2
sta output+3
sta output+4
sta output+5
sta output+6
sta output+7
rts
SetInputPresorted:
lda #$11
sta input+0
lda #$22
sta input+1
lda #$33
sta input+2
lda #$44
sta input+3
lda #$55
sta input+4
lda #$66
sta input+5
lda #$77
sta input+6
lda #$88
sta input+7
rts
SetInputReversed:
lda #$88
sta input+0
lda #$77
sta input+1
lda #$66
sta input+2
lda #$55
sta input+3
lda #$44
sta input+4
lda #$33
sta input+5
lda #$22
sta input+6
lda #$11
sta input+7
rts
SetOutputPresorted:
lda #$11
sta output+0
lda #$22
sta output+1
lda #$33
sta output+2
lda #$44
sta output+3
lda #$55
sta output+4
lda #$66
sta output+5
lda #$77
sta output+6
lda #$88
sta output+7
rts
SetOutputReversed:
lda #$88
sta output+0
lda #$77
sta output+1
lda #$66
sta output+2
lda #$55
sta output+3
lda #$44
sta output+4
lda #$33
sta output+5
lda #$22
sta output+6
lda #$11
sta output+7
rts
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
echo "----",($FFFC - *) , "bytes of ROM left"
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
org $FFFC
.word Start ; reset vector
.word Start ; BRK vector
@mengstr
Copy link
Author

mengstr commented May 7, 2019 •
edited
Loading

Screen Shot 2019-05-07 at 8 02 37 PM

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment