Knuth shuffle: Difference between revisions
Content added Content deleted
Puppydrum64 (talk | contribs) m (→When the array address is known before runtime: forgot label to beginning of loop) |
Puppydrum64 (talk | contribs) (→{{header|6502 Assembly}}: Overhauled this section with a solution that can work with any range of values) |
||
Line 127: | Line 127: | ||
=={{header|6502 Assembly}}== |
=={{header|6502 Assembly}}== |
||
===When the array address is known before runtime=== |
===When the array address is known before runtime=== |
||
Runs on easy6502, which has a random number generated memory-mapped at zero page address <code>$FE</code> that updates after every instruction. Works on any array size up to and including 256 bytes. (The code I wrote here prior to this edit was much faster but only worked on arrays of exactly 256 bytes in size). The reason for this was that constraining a random number generator that can produce any 8-bit value to a subset is tricky, since just "rolling again" if out of range will eventually cause the program to lock up if it can't produce a value in range purely by chance. This method uses a bit mask that shifts right as the loop counter decreases to zero, which means that even when only a few bytes still need to be shuffled, the routine is just as quick as it was at the beginning. |
|||
This is a bit easier since you can use both the X and Y registers to index the same array. |
|||
If the array is exactly 256 bytes, and the RNG can output anything from 0-255, the shuffle will be much faster since there's no way |
|||
to index out of bounds. '''The code below assumes both are true and won't work properly otherwise.''' |
|||
Runs on easy6502. |
|||
<lang 6502asm>define sysRandom $fe |
<lang 6502asm>define sysRandom $fe |
||
define |
define tempMask $ff |
||
define range $00 |
|||
define tempX $01 |
|||
define tempY $02 |
|||
define tempRandIndex $03 |
|||
define temp $04 |
|||
CreateIdentityTable: |
CreateIdentityTable: |
||
txa |
txa |
||
sta $0200,x |
sta $0200,x |
||
sta $1000,x |
|||
inx |
inx |
||
bne CreateIdentityTable |
bne CreateIdentityTable |
||
;creates a sorted array from 0-255 starting at addr $1000 |
|||
;also creates another one at $0200 for our test input |
|||
lda #1 |
|||
KnuthShuffle: |
|||
sta range |
|||
lda $0200,y |
|||
sta temp |
|||
ConstrainRNG: |
|||
lda $0200,x |
|||
ldx #255 |
|||
sta $0200,y |
|||
;max range of RNG |
|||
lda range |
|||
bne outerloop |
|||
jmp end |
|||
outerloop: |
|||
lda temp |
|||
cpx range |
|||
sta $0200,x |
|||
bcc continue ;if X >= range, we need to lower X |
|||
pha |
|||
txa |
|||
sta tempX |
|||
lsr |
|||
cmp range |
|||
bne KnuthShuffle |
|||
bcc continue2 |
|||
tax |
|||
pla |
|||
jmp outerloop |
|||
continue2: |
|||
pla |
|||
ldx tempX |
|||
continue: |
|||
brk ;end program</lang> |
|||
ldy range |
|||
===Using pointers=== |
|||
Unfortunately, we are limited to using Y for offsetting. This means there are more temp variables to keep track of. |
|||
(Even though the array's location is still fixed in the example, in practice you'll want a function that can shuffle arrays anywhere, |
|||
so the code assumes that the location isn't already known.) |
|||
<lang 6502asm>define sysRandom $fe |
|||
define temp $00 |
|||
define HL $02 |
|||
define L $02 |
|||
define H $03 |
|||
define tempY $04 |
|||
define tempY_random $05 |
|||
CreateIdentityTable: |
|||
txa |
|||
sta $0200,x |
|||
inx |
|||
bne CreateIdentityTable |
|||
lda #$00 |
|||
sta L |
|||
lda #$02 |
|||
sta H ;lda HL,$0200 |
|||
ldy #0 ;i |
|||
KnuthShuffle: |
KnuthShuffle: |
||
lda sysRandom |
|||
sty tempY |
|||
and $1000,x ;and with range constrictor |
|||
ldy sysRandom |
|||
tay |
|||
lda (HL),y |
|||
sta temp |
|||
sty tempY_random |
|||
ldy tempY |
|||
lda (HL),y ;lda (HL),i |
|||
lda $0200,y |
|||
sty tempRandIndex |
|||
sta temp |
|||
ldy range |
|||
lda $0200,y |
|||
pha |
pha |
||
lda temp |
lda temp |
||
sta |
sta $0200,y |
||
pla |
pla |
||
ldy tempRandIndex |
|||
sta $0200,y |
|||
dec range |
|||
jmp ConstrainRNG |
|||
end: |
|||
ldy tempY_random |
|||
brk</lang> |
|||
sta (HL),y ;sta (HL), sysRandom |
|||
ldy tempY |
|||
dey ;i-- |
|||
bne KnuthShuffle |
|||
brk ;end program</lang> |
|||
===Using self-modifying code to speed up the previous method=== |
|||
Once again, this method assumes an array size of 256 and a random number generator that is equally likely to produce any outcome from 0 to 255. |
|||
<lang 6502asm>define sysRandom $fe |
|||
define temp $00 |
|||
define tempX $01 |
|||
CreateIdentityTable: |
|||
txa |
|||
sta $0200,x |
|||
inx |
|||
bne CreateIdentityTable ;creates a sorted array of values from 0-255 |
|||
LDA #$00 |
|||
LDX #$00 |
|||
LDY #$02 |
|||
KnuthShuffle: |
|||
;input: A = the array size (max 256, use 0 for 256) |
|||
;X = low byte of addr. where array begins |
|||
;y = high byte of addr. where array begins |
|||
stx smc_KnuthShuffle_alpha+1 |
|||
stx smc_KnuthShuffle_beta+1 |
|||
stx smc_KnuthShuffle_gamma+1 |
|||
stx smc_KnuthShuffle_delta+1 |
|||
sty smc_KnuthShuffle_alpha+2 |
|||
sty smc_KnuthShuffle_beta+2 |
|||
sty smc_KnuthShuffle_gamma+2 |
|||
sty smc_KnuthShuffle_delta+2 |
|||
tax ;get array size into x, to act as the loop counter |
|||
doKnuthShuffle: |
|||
ldy sysRandom |
|||
smc_KnuthShuffle_alpha: |
|||
lda $BEEF,y ;B9 EF BE (BEEF will get overwritten with the desired address in all four cases) |
|||
sta temp |
|||
smc_KnuthShuffle_beta: |
|||
lda $BEEF,x ;BD EF BE |
|||
smc_KnuthShuffle_gamma: |
|||
sta $BEEF,y ;99 EF BE |
|||
lda temp |
|||
smc_KnuthShuffle_delta: |
|||
sta $BEEF,x ;9D EF BE |
|||
dex |
|||
bne doKnuthShuffle |
|||
brk ;end program</lang> |
|||
=={{header|AArch64 Assembly}}== |
=={{header|AArch64 Assembly}}== |