Setbit and Testbit

Here you can ask questions or provide insights about how to use efficiently 6502 assembly code on the Oric.
Post Reply
User avatar
Hialmar
Flight Lieutenant
Posts: 318
Joined: Tue Mar 04, 2014 11:25 am
Location: Toulouse, France
Contact:

Setbit and Testbit

Post by Hialmar » Sun Jan 04, 2015 1:43 pm

For the game we are writing with Maximus I'd like to compress booleans in a binary array.
Like this: http://www.mathcs.emory.edu/~cheung/Cou ... array.html
But based on unsigned char instead of int.

Code: Select all

   void  SetBit( unsigned char A[ ],  int k )
   {
      int i = k/8;
      int pos = k%8;

      unsigned int flag = 1;   // flag = 0000.....00001

      flag = flag << pos;      // flag = 0000...010...000   (shifted k positions)

      A[i] = A[i] | flag;      // Set the bit at the k-th position in A[i]
   }

   int TestBit( unsigned char A[ ],  int k )
   {
      int i = k/8;
      int pos = k%8;

      unsigned int flag = 1;  // flag = 0000.....00001

      flag = flag << pos;     // flag = 0000...010...000   (shifted k positions)

      if ( A[i] & flag )      // Test the bit at the k-th position in A[i]
         return 1;
      else
         return 0;
   }
I've tried to do this in assembler. Here is my take on this. Please comment and/or optimize my code.

Note: I'm using http://skilldrick.github.io/easy6502/ to test my code and this is why my array is supposed to be in $200 (I choose this at random) in the real code this will be parametrized obviously.

Code: Select all

LDA #$15
JSR calculAY
JSR setbit
LDA #$15
JSR calculAY
JSR testbit
BRK
; computes the binary mask to apply/test in A and the array offset in Y from the value in A
calculAY:
STA $00
LSR ; divide by 8
LSR
LSR
TAY ; offset in array
ASL ; multiply by 8
ASL
ASL
STA $01 ; store this value
LDA $00 ; get back the original value
SEC
SBC $01 ; subtract
TAX ; this is the remainder of the division by 8
BEQ nul_mod
LDA #$01
loop: ; move this to compute the 1 bit mask
ASL
DEX
BNE loop
LSR
RTS
nul_mod:
LDA #$01 ; if the remainder was null we have to test the first bit (ie bit 0)
RTS
; set in memory, array starting at $200
setbit:
ORA $200,Y
STA $200,Y
RTS
; test in memory, array starting at $200 result in A (0 or 1)
testbit:
LDA $200,Y
STA $00
BIT $00
BNE ok
LDA #$00
BRK
ok:
LDA #$01
RTS
Hialmar
CEO and Silicium member.

User avatar
Chema
Game master
Posts: 1972
Joined: Tue Jan 17, 2006 10:55 am
Location: Gijón, SPAIN
Contact:

Re: Setbit and Testbit

Post by Chema » Sun Jan 04, 2015 3:44 pm

Hi.

A quick answer. First the mod 8 operation is a simple and #%111 (the three least significant bits of the parameter). Then I would use a table for the bit positions. It is much quicker. If you don't know in advance the size of your bitfield, then get the bit position with the and #7 and an 8-byte table holding: 00000001 00000010 00000100 ... 10000000 and stick to the divide by 8 by lsring.

If you know the max size of the bitfield you can use a table for the entry in your array too!


Testing should be as simple as lda $200,y : and table_bit,x. Setting is the same, but with an ora.

EDIT: 111 in binary is not 3, of course... Must have been last night's wine :)
Last edited by Chema on Sun Jan 04, 2015 4:29 pm, edited 1 time in total.

User avatar
Hialmar
Flight Lieutenant
Posts: 318
Joined: Tue Mar 04, 2014 11:25 am
Location: Toulouse, France
Contact:

Re: Setbit and Testbit

Post by Hialmar » Sun Jan 04, 2015 3:49 pm

Thanks a lot.

I'm not very good at assembler and it shows :)
Hialmar
CEO and Silicium member.

User avatar
Chema
Game master
Posts: 1972
Joined: Tue Jan 17, 2006 10:55 am
Location: Gijón, SPAIN
Contact:

Re: Setbit and Testbit

Post by Chema » Sun Jan 04, 2015 4:37 pm

I corrected a stupid mistake in the above post :) Sorry.

Also if you know in advance the maximum size of your array of bits (and it is not too huge) you can use tables for the byte and the bit. Imagine the size is 4 bytes. You can have two 32-byte tables one with 0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3 and the other with the bits 1,2,4,8,16,32,64,128,1,2,4,8,16,32,64,128,1,2,4,8,16,32,64,128,1,2,4,8,16,32,64,128 and you can load both indexing by the value of the bit number (between 0 and 31) with no additional pocesing.

The SCUMM/SPUTM engine does have an area of 1-bit flags, so I thought about this when giving it a look.... IIRC the specification that runs Monkey on The Island needed something as 2048 1-bit flags, so it was not as easy as this...

User avatar
Hialmar
Flight Lieutenant
Posts: 318
Joined: Tue Mar 04, 2014 11:25 am
Location: Toulouse, France
Contact:

Re: Setbit and Testbit

Post by Hialmar » Sun Jan 04, 2015 4:51 pm

Thanks. I will think about it a bit more to see if it is interesting for me to use only tables.

I think ultimately I will have 8*(25+15) booleans but each time I need only 40 booleans (the others are for other maps) so it will be 5 bytes long.

So I would need 2*40 bytes tables. Instead of one 8 byte table and 3 LSRs. Not sure it's interesting.
Hialmar
CEO and Silicium member.

User avatar
Dbug
Site Admin
Posts: 2322
Joined: Fri Jan 06, 2006 10:00 pm
Location: Oslo, Norway
Contact:

Re: Setbit and Testbit

Post by Dbug » Tue Jan 06, 2015 8:43 am

Since in your code example:

Code: Select all

LDA #$15
JSR calculAY
JSR setbit
LDA #$15
JSR calculAY
JSR testbit
you seem to be testing hardcoded bit values (here $15), you could just not have any code at all to compute all that and use macros.

Code makes sense only if the bit number can change at runtime.

I was thinking something like
#define SETBIT(bitfield,bitnumber) lda bitfield+bitnumber/8:ora #bitnumber&7:sta bitfield+bitnumber/8
#define GETBIT(bitfield,bitnumber) lda bitfield+bitnumber/8:and #bitnumber&7

I did not try the code, just an idea.

User avatar
Hialmar
Flight Lieutenant
Posts: 318
Joined: Tue Mar 04, 2014 11:25 am
Location: Toulouse, France
Contact:

Re: Setbit and Testbit

Post by Hialmar » Tue Jan 06, 2015 6:25 pm

Ah no it's only for testing.

In the game I will need to set any bit and test any bit.

When the party makes a combat I will set the bit corresponding to this specific combat and the next time they will go on this "tile", I will test the bit and not have the combat again (and it is the same for other "things" that need to happen only once).
Hialmar
CEO and Silicium member.

User avatar
Chema
Game master
Posts: 1972
Joined: Tue Jan 17, 2006 10:55 am
Location: Gijón, SPAIN
Contact:

Re: Setbit and Testbit

Post by Chema » Wed Jan 07, 2015 8:07 pm

Hialmar wrote:
So I would need 2*40 bytes tables. Instead of one 8 byte table and 3 LSRs. Not sure it's interesting.
80 bytes is not that much, but I agree. As I can see you don't need to optimize this for speed, so the 3 LSRs should do.

BTW: 40x8 is 320, so it doesn't fit in a byte... Maybe it would be a good idea to split your set of flags in two so the flag number does not exceed 255... Just something to consider.

User avatar
Hialmar
Flight Lieutenant
Posts: 318
Joined: Tue Mar 04, 2014 11:25 am
Location: Toulouse, France
Contact:

Re: Setbit and Testbit

Post by Hialmar » Thu Jan 08, 2015 1:27 pm

Yes it doesn't fit in a byte but I only need to address 40 bits for each map/level, so I will first compute the address of the first byte of the bit array for the specific map/level and do everything from there.

So, for example, if the whole array starts at $200 and ends at $228 (40 bytes) and I'm in map/lvl 3, the start of this level's bit array is $20a (1st lvl is from $200 to $204, 2nd lvl from $205 to $209).

The first combat will be the first bit of $20a...
Hialmar
CEO and Silicium member.

User avatar
Chema
Game master
Posts: 1972
Joined: Tue Jan 17, 2006 10:55 am
Location: Gijón, SPAIN
Contact:

Re: Setbit and Testbit

Post by Chema » Thu Jan 08, 2015 1:52 pm

Ah, I see. Nice :)

User avatar
Hialmar
Flight Lieutenant
Posts: 318
Joined: Tue Mar 04, 2014 11:25 am
Location: Toulouse, France
Contact:

Re: Setbit and Testbit

Post by Hialmar » Sat Jan 24, 2015 5:55 pm

It took some time to find some free time but the code is working now.

Here is my code which is integrated with a C program just in case someone needs it:
First a link in my dropbox with everything to build it with OSDK:
https://www.dropbox.com/sh/l3h302zae57h ... eTp_a?dl=0

Detailed:
bit_ops.h:

Code: Select all

// bit operations
extern void  SetBit( unsigned char A[ ],  unsigned char k );
extern unsigned char TestBit( unsigned char A[ ],  unsigned char k );
bit_ops.s:

Code: Select all

TableBit
    .byt 1,2,4,8,16,32,64,128

; common code
; loads the bit number to apply/test in X and the array offset in Y
calculXY
	; k is already in A lda tmp1 ; load k
	lsr ; divide A by 8
	lsr
	lsr
	tay ; offset in array
	lda tmp1 ; reload k
	and #%111 ; A mod 8
	tax ; transfers the result to x
	rts

; extern void  SetBit( unsigned char A[ ],  unsigned char k );
_SetBit
.(
	ldy #0
	lda (sp),y ; A lo
	sta tmp0
	iny
	lda (sp),y ; A hi
	sta tmp0+1
	iny
	lda (sp),y ; k
	sta tmp1
	jsr calculXY
	lda (tmp0),y
	ora TableBit,x
	sta (tmp0),y
	rts 
.)

; extern unsigned char TestBit( unsigned char A[ ],  unsigned char k );
_TestBit
.(
	ldy #0
	lda (sp),y ; A lo
	sta tmp0
	iny
	lda (sp),y ; A hi
	sta tmp0+1
	iny
	lda (sp),y ; k
	sta tmp1
	jsr calculXY
	lda (tmp0),y
	and TableBit,x
	tax ; result in x
	lda #0 ; high byte should be 0 ?
	rts 
.)
main.c:

Code: Select all

#include <lib.h>

#include "bit_ops.h"

#define NULL (char*)0

// displays in binary
// taken from here: http://stackoverflow.com/questions/699968/display-the-binary-representation-of-a-number-in-c
static char *binrep (unsigned int val, char *buff, int sz) {
    char *pbuff = buff;

    /* Must be able to store one character at least. */
    if (sz < 1) return NULL;

    /* Special case for zero to ensure some output. */
    if (val == 0) {
        *pbuff++ = '0';
        *pbuff = '\0';
        return buff;
    }

    /* Work from the end of the buffer back. */
    pbuff += sz;
    *pbuff-- = '\0';

    /* For each bit (going backwards) store character. */
    while (val != 0) {
        if (sz-- == 0) return NULL;
        *pbuff-- = ((val & 1) == 1) ? '1' : '0';

        /* Get next bit. */
        val >>= 1;
    }
    return pbuff+1;
}

unsigned char tabbit[8];

#define SZ 32
char buff[SZ+1];

void main()
{
	unsigned char i, x, y;
	
	SetBit(tabbit,0);
	SetBit(tabbit,3);
	SetBit(tabbit,5);

	SetBit(tabbit,8);
	SetBit(tabbit,14);
	SetBit(tabbit,15);

	SetBit(tabbit,16);
	SetBit(tabbit,17);
	SetBit(tabbit,18);

	SetBit(tabbit,31);
	
	SetBit(tabbit,32);
	SetBit(tabbit,33);

	SetBit(tabbit,61);
	SetBit(tabbit,62);
	SetBit(tabbit,63);
	
	for (i=0; i<8; i++)
		printf("valeur = %s\n", binrep(tabbit[i],buff,SZ));	
		
	puts("---------");

	for (i=0; i<64; i++)
		if(TestBit(tabbit, i))
			printf("Bit %d is set\n", i);	
}
Hialmar
CEO and Silicium member.

Post Reply

Who is online

Users browsing this forum: No registered users and 1 guest