www.retrosoftware.co.uk
http://www.retrosoftware.co.uk/forum/

Bit manipulation
http://www.retrosoftware.co.uk/forum/viewtopic.php?f=73&t=538		 Page 1 of 1
Author:  tautology [ Wed Nov 17, 2010 10:44 pm ]
Post subject:  Bit manipulation
I've got a question about what the best way to do the below is. I'm looking for a solution that returns the minimal number of bytes of code, rather than vast efficiency in code speed.

For the SAGA remake, I need to compress the rooms exits. The standard format is:
Code:
byte N
byte S
byte E
byte W
byte U
byte D
string description (null terminated)

Where N, S, E, W, U, D are the room that going that direction will take you to (up to 150). A 0 indicates the direction is closed.

I've already compressed the description down, so I'm thinking that I can compress this data structure by having:
Code:
string description
byte exits
byte ... Open exits

Where exits is a byte with a bit set for each location if there is an exit (e.g. bit 0 = N, bit 1 = S etc). And then a compacted list of exits for only those rooms that are open.

So I need two routines: one to count the number of exits; the other to match a given exit to the appropriate byte.

The first should be relatively easy, just using a loop like:
Code:
      lda exits
      ldx #7
      ldy #0
.loop dex
      beq out
      ror a
      bcc loop
      iny
      jmp loop
.out  tya

But the second one I can't even think of how to get started; I guess doing something similar to the above but actually increasing the pointer into the data would do?

Any ideas to improve it?
Author:  RichTW [ Thu Nov 18, 2010 12:00 am ]
Post subject:  Re: Bit manipulation
This is about as cunningly as I can do it:
Code:
.getexitindex
    ; X = 0-5 for which exit to return

    LDA #0              ; A = bitmask to test against exits bitfield
    TAY                 ; Y = index in exits list
    SEC                 ; set carry, so the ROL A below yields 1 the first time round the loop
.countbits
    ROL A               ; subsequent times round the loop yield 2, 4, 8 etc (C will be clear)
    DEX
    BMI doneallbits     ; exit loop if X<0
    BIT exits           ; is this exit defined?
    BEQ countbits       ; no - reloop
    INY                 ; yes - inc index of exits list
    BNE countbits       ; ...and reloop
.doneallbits
    AND exits           ; now see if our exit is actually defined
    BEQ return          ; it isn't - return 0
    LDA exitlist,Y      ; it is - look up actual exit number from the list
.return
    RTS

It's not tested, but I think it ought to work! I think it's about as compact a routine as it can be.

Here's another approach which uses a lookup table to calculate 2^X and which looks simpler, but is in fact a whole 7 bytes longer in total.
Code:
.getexitindex   ; using lookup table
    ; X = 0-5 for which exit to return

    LDA bittable,X      ; look up 2^n
    AND exits           ; check that bit in the exits bitfield
    BEQ return          ; if not set, return 0
    LDY #0              ; set exit list index to 0
    LDA exits           ; load exits bitfield
.countbits
    DEX
    BMI doneallbits     ; if X<0 exit loop
    LSR A               ; check for set bit
    BCC countbits       ; if clear, reloop
    INY                 ; if set, inc exit list index
    BCS countbits       ; ...and reloop
.doneallbits
    LDA exitlist,Y      ; load exit from list (we know for sure it is defined)
.return
    RTS
.bittable
    EQUB 1, 2, 4, 8, 16, 32
Author:  RichTW [ Thu Nov 18, 2010 8:55 am ]
Post subject:  Re: Bit manipulation
Just noticed, you have a bug in this code:
tautology wrote:
Code:
      lda exits
      ldx #7
      ldy #0
.loop dex
      beq out
      ror a
      bcc loop
      iny
      jmp loop
.out  tya

The ROR A should be a LSR A (because ROR shifts the carry flag into bit 7, but it is undefined each time round the loop). Also, you can save a byte by using BCS loop instead of JMP loop!
Author:  tautology [ Thu Nov 18, 2010 11:17 am ]
Post subject:  Re: Bit manipulation
Ah the joys of typing code out and not trying it out :-)

I actually thought ROR would be okay as I didn't care about the contents of the high bits (as I only do 8 shifts). It's also because I couldn't remember what the mnemonic was to do the right version of ASL :-)

I like your logic with replacing the JMP with a BCS (as I now know that INC/INY/INX doesn't affect carry - that stumped me for ages).

I'll give your routines a try. Thanks.

Whilst we're on the subject of code improvement. I find I'm doing a lot of manipulation of 16-bit pointers, all following the standard code of:
Code:
inc ptr
bne loop
inc ptr+1
jmp loop

or

lda ptr
adc #6
sta ptr
bcc loop
inc ptr+1
jmp loop   ; though we can change this to a bcs

Is this the best way to do it; any suggested improvements?
Author:  RichTW [ Thu Nov 18, 2010 12:42 pm ]
Post subject:  Re: Bit manipulation
tautology wrote:
I actually thought ROR would be okay as I didn't care about the contents of the high bits (as I only do 8 shifts). It's also because I couldn't remember what the mnemonic was to do the right version of ASL :-)
Actually, yes it's true - in this case it will work fine as you don't care about what gets rotated in to the high bit. But, in general, if you don't know the state of the carry flag, a LSR is better :)

Quote:
Whilst we're on the subject of code improvement. I find I'm doing a lot of manipulation of 16-bit pointers, all following the standard code of:
Code:
inc ptr
bne loop
inc ptr+1
jmp loop

In this case, you can normally change the JMP to either a BNE or a BPL, assuming that the address is never going to end up greater than &8000, or in the zero page.

But yeah, there's not really any other way of adding an 8 bit number to a 16 bit one - you have to go through all that each time. As I mentioned somewhere else, you might win back space if you were to make a subroutine which added A to ptr (for example).

Also you can occasionally save a CLC if you know the state of the carry flag in advance. If C is set, then:
Code:
LDA addr:ADC #5:STA addr
is equivalent to:
Code:
CLC:LDA addr:ADC #6:STA addr
Author:  tautology [ Fri Nov 19, 2010 7:14 pm ]
Post subject:  Re: Bit manipulation
RichTW wrote:
Also you can occasionally save a CLC if you know the state of the carry flag in advance.


And of course forgetting to do a CLC before an ADC may cause odd results at "random" times; as I found out about 2 hours ago!
Page 1 of 1 All times are UTC [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/