[net.lang.c] Portable arrays of bits

bayers@kodak.UUCP (mitch bayersdorfer) (11/06/86)

Is there a standard, machine independant way of defining an array 
of bits?  I am writing code and do not want to have to do a function
call each time I reference a bit, but want a Boolean array packed
as tightly as possible.

      - Mitch Bayersdorfer
        Applied Technology Organization 
        Artificial Intelligence Laboratory
        Floor 4, Building 23, Kodak Park
        Rochester, NY 14650
        (716) 477-1792


...!rochester!kodak!bayers

rbutterworth@watmath.UUCP (Ray Butterworth) (11/06/86)

> Is there a standard, machine independant way of defining an array 
> of bits?  I am writing code and do not want to have to do a function
> call each time I reference a bit, but want a Boolean array packed
> as tightly as possible.

Some machines have fast function calls and assembler instructions for
directly addressing bits.   But if you want portable, how about this?
It should run on any C with an appropriate setting of the first define.
Make sure that the _BPW_ is 36 or 16 or however many bits there are in
an (int) on your machine.  Make sure you use (int) and not (long) or (char)
for the array; on many machines accessing a (char) is a lot more work than
accessing an (int).

#define _BPW_ (36)      /* bits per word (natural machine size, not char) */

#define _BIT_(bit) (1<<((bit)%_BPW_))                     /* internal use */
#define _WORD_(name,bit) ((name)[(bit)/_BPW_])            /* internal use */

#define DECLARE(name,bits) int name[1+((bits)/_BPW_)]

#define SET(name,bit)   (_WORD_(name,bit)|=_BIT_(bit))
#define CLEAR(name,bit) (_WORD_(name,bit)&=~_BIT_(bit))
#define FLIP(name,bit)  (_WORD_(name,bit)^=_BIT_(bit))

#define TEST(name,bit) ((_WORD_(name,bit)&_BIT_(bit))!=0)
#define SAME(name1,name2,bit) \
  (((_WORD_(name1,bit)^_WORD_(name2,bit))&_BIT_(bit))==0)
etc.

brisco@caip.RUTGERS.EDU (Thomas Paul Brisco) (11/06/86)

>Is there a standard, machine independant way of defining an array 
>of bits?  I am writing code and do not want to have to do a function
>call each time I reference a bit, but want a Boolean array packed
>as tightly as possible.


	The immediate (and naive) approach is to say:
	struct{
		bit:1
		}[LOTS]

	However, C does not support bit fields directly. For every bit
field it will allocate a full word. This is distressing particularly
if you have a sparse structure, and many of them.

	A better approach is to define a subroutine or macro as
following:

#define getbit(x,p) ((x >> p)&~(~0 << 1))

	This is from K&R (God bless 'em). A "setbit" macro could be
fudged up fairly similiarly.  Of course for this to work *really*
good, you should make sure that the struct uses char's ,not int's --
vaxes have a (literally) twisted concept of how bytes fit into ints.
By using chars you avoid the little/big -endian problems. Also, you'll
probably want (somewhere) a #define for the number of bits in a
character (just to cover all bases) for computational purposes.

	The structure I used look like this:
	unsigned char bitmap[1024][1024]
and used the previous macro as a sub-routine to reference bits within
the char's.  I set bits by simple multiplications.




				tp.
-- 
                  ----------------------------------------------------------
                  -                  ARPA: Brisco@rutgers                  -
                  -  UUCP: (ihnp4!ut-sally, allegra!packard) !caip!brisco  -
                  ----------------------------------------------------------