We had fun last month twiddling bits in 6502 assembly, so here is
another programming challenge.
Write the shortest 6502 program that will sort the 256-byte table
from $1000 to $10FF. Numbers in the table are interpreted as
unsigned values from 0 to 255. The sorted table (in nondecreasing
order) should be written to $2000-20FF, with the original table
still intact at $1000-10FF.
The goal is to minimize the number of bytes in the executable
code, not execution speed.
Paul Guertin
pg@sff.net
On Thu, 22 Apr 2004 22:24:07 -0400, Paul Guertin wrote:
> We had fun last month twiddling bits in 6502 assembly, so here is
> another programming challenge.
>
> Write the shortest 6502 program that will sort the 256-byte table
> from $1000 to $10FF. Numbers in the table are interpreted as
> unsigned values from 0 to 255. The sorted table (in nondecreasing
> order) should be written to $2000-20FF, with the original table
> still intact at $1000-10FF.
>
> The goal is to minimize the number of bytes in the executable
> code, not execution speed.
>
> Paul Guertin
> pg@sff.net
Ok, here's my first entry, a selection sort, at 41 bytes:
* must execute in page zero
org $b0
* copy $1000-10ff to $2000.$20ff
ldx #0
mov lda $1000
dst sta (vgl+1,x)
inc mov+1
inc vgl+1
bne mov
* sort in place
cur ldy $2000
vgl cpy $2000
bcc les
lda (vgl+1,x) ;swap current and compare locations
sta (cur+1,x)
tya
sta (vgl+1,x)
les inc vgl+1 ;increment compare address
bne cur ; and see if it is better
inc cur+1 ;current location is correct so,
lda cur+1 ; increment current address and copy
sta vgl+1 ; into compare address for next round
bne cur
I hope it can be improved upon
In article <38vg80l9dvp7oijp3f0opul9aguntihb43@4ax.com>, Paul Guertin wrote:
>Write the shortest 6502 program that will sort the 256-byte table
>from $1000 to $10FF. Numbers in the table are interpreted as
>unsigned values from 0 to 255. The sorted table (in nondecreasing
>order) should be written to $2000-20FF, with the original table
>still intact at $1000-10FF.
My entry takes 22 bytes. It also takes almost a second to run.
org $300
lda #0 ;2
tax ;1
tay ;1
Loop1
cmp $1000,y ;3
bne Skip ;2
sta $2000,x ;3
inx ;1
Skip
iny ;1
bne Loop1 ;2
clc ;1
adc #1 ;2
bne Loop1 ;2
rts ;1
This is 4+9+9 = 22 bytes.
It basically loops over all possible values 00-FF in the accumulator, looking
across the whole $1000 with a Y-loop, storing any matches to $2000,x.
So it loops over the Loop1 code 256*256 times. I calculated the
run time as: (((4+3+2+3)*256 + 2+2+3)*256 + (-1+5+2)*256 + -1 + 6 =
789765 clocks.
I tested the code and it seems to work, but I didn't test it much.
It's along the lines of a stupid radix sort.
Kent Dickey
On 23 Apr 2004 21:26:28 GMT, kadickey@alumni.princeton.edu (Kent Dickey)
wrote:
> In article <38vg80l9dvp7oijp3f0opul9aguntihb43@4ax.com>, Paul Guertin wrote:
> >Write the shortest 6502 program that will sort the 256-byte table
> >from $1000 to $10FF. Numbers in the table are interpreted as
> >unsigned values from 0 to 255. The sorted table (in nondecreasing
> >order) should be written to $2000-20FF, with the original table
> >still intact at $1000-10FF.
>
> My entry takes 22 bytes. It also takes almost a second to run.
Almost line-for-line identical with my proposed solution,
and with the same timing. Congratulations. Anyone have a better
one?
What if we require the sorted array to be written to $1000-10FF,
overwriting the original? It can be done trivially by adding the
following 9 bytes just before the rts:
loop2 lda $2000,y
sta $1000,y
iny
bne loop2
for a total of 31 bytes including the rts, but I have a
solution in 30 bytes.
Paul Guertin
pg@sff.net
Sheldon Simms wrote:
> On Fri, 23 Apr 2004 23:20:28 -0400, Paul Guertin wrote:
> > What if we require the sorted array to be written to $1000-10FF,
> > overwriting the original? It can be done trivially
> ...
> > for a total of 31 bytes including the rts, but I have a
> > solution in 30 bytes.
>
> In that case, my entry is 30 bytes when you simply delete
> the lines that move $1000-$10ff to $2000-$20ff
Indeed it is. Well done. Here is mine:
ldx #0
ldy #0
.2 lda $1000,x
cmp $1000,y
bcc .1
pha
lda $1000,y
sta $1000,x
pla
sta $1000,y
.1 inx
bne .2
iny
bne .2
rts
It can be reduced to 27 bytes by putting it in page zero and
using self-mods, similar to your routine.
Paul Guertin
pg@sff.net