Challenge: write the fastest (average number of cycles) or shortest 6502 routine (smallest number of bytes, including executable code and data tables) that will reverse the order of bits in a byte. For instance, 10000100 should become 00100001, and 11010111 should become 11101011. The byte to reverse is initially in the accumulator, and the result should also be in the accumulator. http://graphics.stanford.edu/~seander/bithacks.html has interesting techniques for doing this, but they might not be so useful on a 6502. Paul Guertin pg@sff.net Probably not the fastest or smallest, but something to kick the competition off with. 27 cycles, 48 bytes pha and #$0F tax pla lsr lsr lsr lsr tay lda tbl1,x ora tbl2,y tbl1 dc '$00, $80, $40, $C0, $20, $A0, $60, $E0' dc '$10, $90, $50, $D0, $30, $B0, $70, $F0' tbl2 dc '$00, $08, $04, $0C, $02, $0A, $06, $0E' dc '$01, $09, $05, $0D, $03, $0B, $07, $0F' -Lucas lscharen@d.umn.edu wrote in message news:... > Probably not the fastest or smallest, but something to kick the > competition off with. 27 cycles, 48 bytes Here's a slow but short version that uses recursion and must be called as a subroutine. Up to 208 cycles, but only 12 bytes bitrev anop beq .2 pha asl jsr bitrev plx cpx #$80 rol .2 rts -Lucas > 26 bytes, using a zero-page variable > > 10 bytes, using X and zero-page 56 bytes, 42.5 cycles (average), inlined, using no other registers, or memory. This one uses the fact, that, to swap bits X and Y in a bytes, we can perform the operation X = X xor (X xor Y) Y = Y xor (X xor Y) The three BIT/BEQ pairs are what computes this value. If someone can figure out a way to compute the XOR between any two bits in a byte more efficiently that what I've got, the code can be improved. Try to come up with something of the semantics "If (bit X xor bit Y) == 0, then branch". bit #$81 beq .2 bit #$80 beq .1 bit #$01 beq .2 .1 eor #$81 .2 bit #$42 beq .4 bit #$40 beq .3 bit #$02 beq .4 .3 eor #$42 .4 bit #$24 beq .6 bit #$20 beq .5 bit #$04 beq .6 .5 eor #$24 .6 bit #$18 beq .8 bit #$10 beq .7 bit #$08 beq .8 .7 eor #$18 .8 done -Lucas On 21 Mar 2004 11:46:30 -0800, lscharen@d.umn.edu (Lucas) wrote: > > 26 bytes, using a zero-page variable > > > > 10 bytes, using X and zero-page > > 56 bytes, 42.5 cycles (average), inlined, using no other registers, > or memory 10 bytes, inlined, using only stack memory, 136 cycles maximum. bit #$0 .1 php asl bne .1 .2 rol plp bne .2 (Note: bit immediate is a 65C02 instruction; on a 6502, you need to bit $zp where zp contains zero). Paul Guertin pg@sff.net Paul Guertin wrote in message news:... > On 21 Mar 2004 11:46:30 -0800, lscharen@d.umn.edu (Lucas) wrote: > > > > 26 bytes, using a zero-page variable > > > > > > 10 bytes, using X and zero-page > > > > 56 bytes, 42.5 cycles (average), inlined, using no other registers, > > or memory > > 10 bytes, inlined, using only stack memory, 136 cycles maximum. > > bit #$0 > .1 php > asl > bne .1 > .2 rol > plp > bne .2 > > (Note: bit immediate is a 65C02 instruction; on a 6502, you need > to bit $zp where zp contains zero). That is brilliant! I had forgotten all about the php/plpl instructions. They certainly do the trick here. Very elegant, I especially like the use of BIT to guarantee that P=0. I've not seen that trick before. -Lucas I tried implementing a classic hacker's trick for flipping bits "in parallel". To my surprise, it was reasonably efficient. 36 bytes, 56 cycles, uses X and one zero page byte. Replace TAX -> PHA and TXA -> PLA throughout to free X at the cost of 6 cycles. tax ;swap contiguous bits and #$55 asl sta $00 txa and #$AA lsr ora $00 tax ;swap contiguous pairs and #$33 asl asl sta $00 txa and #$CC lsr lsr ora $00 asl ;swap contiguous nibbles rol ;(see previous thread) rol rol sta $00 and #$7 adc $00 Paul Guertin pg@sff.net Lucas wrote: |lscharen@d.umn.edu wrote in message news:... |> Probably not the fastest or smallest, but something to kick the |> competition off with. 27 cycles, 48 bytes | |Here's a slow but short version that uses recursion and must be called |as a subroutine. Up to 208 cycles, but only 12 bytes | |bitrev anop | beq .2 | pha | asl | jsr bitrev | plx | cpx #$80 | rol |.2 rts plx? Don't you mean pla? After all, he did say 6502, not 65816. And if you use pla, you are going to have to change cpx #$80 to cmp #$80. And if you just want bit 7 moved into the carry, you could always save one byte by changing it to asl.