Bit Vectors

Routines for managing efficient high-performance bit vectors of arbitrary length. More...

Collaboration diagram for Bit Vectors:

Files
file	bitv.h

Data Structures
struct	bu_bitv

Macros
#define	BU_BITV_SHIFT   6
#define	BU_BITV_MASK   ((1<<BU_BITV_SHIFT)-1)
#define	BU_BITV_NULL   ((struct bu_bitv *)0)
#define	BU_CK_BITV(_bp)   BU_CKMAG(_bp, BU_BITV_MAGIC, "bu_bitv")
#define	BU_BITV_INIT(_bp)
#define	BU_BITV_INIT_ZERO   { {BU_BITV_MAGIC, BU_LIST_NULL, BU_LIST_NULL}, sizeof(bitv_t)*8, {0} }
#define	BU_BITV_IS_INITIALIZED(_bp)   (((struct bu_bitv *)(_bp) != BU_BITV_NULL) && LIKELY((_bp)->l.magic == BU_BITV_MAGIC))
#define	BU_WORDS2BITS(_nw)   ((size_t)(_nw>0?_nw:0)*sizeof(bitv_t)*8)
#define	BU_BITS2WORDS(_nb)   (((size_t)(_nb>0?_nb:0)+BU_BITV_MASK)>>BU_BITV_SHIFT)
#define	BU_BITS2BYTES(_nb)   (BU_BITS2WORDS(_nb)*sizeof(bitv_t))
#define	BU_BITSET(_bv, bit)    ((_bv)->bits[(bit)>>BU_BITV_SHIFT] |= (((bitv_t)1)<<((bit)&BU_BITV_MASK)))
#define	BU_BITCLR(_bv, bit)    ((_bv)->bits[(bit)>>BU_BITV_SHIFT] &= ~(((bitv_t)1)<<((bit)&BU_BITV_MASK)))
#define	BU_BITTEST(_bv, bit)    (((_bv)->bits[(bit)>>BU_BITV_SHIFT] & (((bitv_t)1)<<((bit)&BU_BITV_MASK)))!=0)
#define	BU_BITV_ZEROALL(_bv)   bu_bitv_clear(_bv)
#define	BU_BITV_BITNUM_CHECK(_bv, _bit)
#define	BU_BITV_NBITS_CHECK(_bv, _nbits)
#define	BU_BITV_LOOP_START(_bv)
#define	BU_BITV_LOOP_END

Typedefs
typedef uint64_t	bitv_t
typedef struct bu_bitv	bu_bitv_t

Functions
size_t	bu_bitv_shift (void)
void	bu_bitv_set (struct bu_bitv *bv, size_t bit)
void	bu_bitv_clear_bit (struct bu_bitv *bv, size_t bit)
int	bu_bitv_test (const struct bu_bitv *bv, size_t bit)
size_t	bu_bitv_length (const struct bu_bitv *bv)
size_t	bu_bitv_count_set (const struct bu_bitv *bv)
void	bu_bitv_foreach (const struct bu_bitv *bv, void(*callback)(size_t bit, void *data), void *data)
struct bu_bitv *	bu_bitv_new (size_t nbits)
void	bu_bitv_free (struct bu_bitv *bv)
void	bu_bitv_clear (struct bu_bitv *bv)
void	bu_bitv_or (struct bu_bitv *ov, const struct bu_bitv *iv)
void	bu_bitv_and (struct bu_bitv *ov, const struct bu_bitv *iv)
void	bu_bitv_not (struct bu_bitv *ov)
void	bu_bitv_xor (struct bu_bitv *ov, const struct bu_bitv *iv)
void	bu_bitv_shift_vector (struct bu_bitv *ov, int shift)
void	bu_bitv_vls (struct bu_vls *v, const struct bu_bitv *bv)
void	bu_pr_bitv (const char *str, const struct bu_bitv *bv)
void	bu_bitv_to_hex (struct bu_vls *v, const struct bu_bitv *bv)
struct bu_bitv *	bu_hex_to_bitv (const char *str)
void	bu_bitv_to_binary (struct bu_vls *v, const struct bu_bitv *bv)
struct bu_bitv *	bu_binary_to_bitv (const char *str)
struct bu_bitv *	bu_binary_to_bitv2 (const char *str, const int nbytes)
int	bu_bitv_compare_equal (const struct bu_bitv *, const struct bu_bitv *)
int	bu_bitv_compare_equal2 (const struct bu_bitv *, const struct bu_bitv *)
struct bu_bitv *	bu_bitv_dup (const struct bu_bitv *bv)
int	bu_hexstr_to_binstr (const char *hexstr, struct bu_vls *b)
int	bu_binstr_to_hexstr (const char *binstr, struct bu_vls *h)
void	bu_printb (const char *label, unsigned long bits, const char *format)
	Bit field printing implementation.
void	bu_vls_printb (struct bu_vls *vls, const char *label, unsigned long bits, const char *format)

Detailed Description

Routines for managing efficient high-performance bit vectors of arbitrary length.

The basic type "bitv_t" is defined in include/bu.h; it is the widest integer datatype for which efficient hardware support exists. BU_BITV_SHIFT and BU_BITV_MASK are also defined in bu.h

These bit vectors are "little endian", bit 0 is in the right hand side of the [0] word.

Macro Definition Documentation

BU_BITV_SHIFT

#define BU_BITV_SHIFT   6

Bit vector shift size

Should equal to: log2(sizeof(bitv_t)*8.0). Using bu_bitv_shift() will return a run-time computed shift size if the size of a bitv_t changes. Performance impact is rather minimal for most models but disabled for a handful of primitives that heavily rely on bit vectors.

(8-bit type: 3, 16-bit type: 4, 32-bit type: 5, 64-bit type: 6)

Definition at line 74 of file bitv.h.

BU_BITV_MASK

#define BU_BITV_MASK   ((1<<BU_BITV_SHIFT)-1)

Bit vector mask

Definition at line 77 of file bitv.h.

BU_BITV_NULL

#define BU_BITV_NULL   ((struct bu_bitv *)0)

Definition at line 101 of file bitv.h.

BU_CK_BITV

#define BU_CK_BITV

(

_bp

)

BU_CKMAG(_bp, BU_BITV_MAGIC, "bu_bitv")

asserts the integrity of a non-head node bu_bitv struct.

Definition at line 106 of file bitv.h.

BU_BITV_INIT

#define BU_BITV_INIT

(

_bp

)

Value:

        { \
	BU_LIST_INIT_MAGIC(&(_bp)->l, BU_BITV_MAGIC); \
        (_bp)->nbits = sizeof(bitv_t) * 8; \
        (_bp)->bits[0] = 0; \
    }

Initializes a bu_bitv struct without allocating any memory. This macro is not suitable for initializing a head list node.

Because struct bu_bitv embeds one full bitv_t word (currently 64 bits) inline, a stack-allocated instance already provides 64 usable bits without any heap allocation. Callers that need at most 64 bits can avoid bu_bitv_new() entirely:

struct bu_bitv bv;
BU_BITV_INIT(&bv);
BU_BITSET(&bv, 3);
if (BU_BITTEST(&bv, 3)) { ... }
// no bu_bitv_free() needed -- stack memory

nbits is set to sizeof(bitv_t)*8 (64) to reflect the capacity actually available in the embedded bits[1] field.

Definition at line 128 of file bitv.h.

BU_BITV_INIT_ZERO

#define BU_BITV_INIT_ZERO   { {BU_BITV_MAGIC, BU_LIST_NULL, BU_LIST_NULL}, sizeof(bitv_t)*8, {0} }

Macro suitable for declaration-statement initialization of a bu_bitv struct on the stack or as a static/global. Does not allocate memory and is not suitable for a head node.

The initialized vector has 64 bits of usable capacity matching the embedded bits[1] storage. Example:

struct bu_bitv bv = BU_BITV_INIT_ZERO;
BU_BITSET(&bv, 7);

Definition at line 147 of file bitv.h.

BU_BITV_IS_INITIALIZED

#define BU_BITV_IS_INITIALIZED

(

_bp

)

(((struct bu_bitv *)(_bp) != BU_BITV_NULL) && LIKELY((_bp)->l.magic == BU_BITV_MAGIC))

returns truthfully whether a bu_bitv has been initialized

Definition at line 152 of file bitv.h.

BU_WORDS2BITS

#define BU_WORDS2BITS

(

_nw

)

((size_t)(_nw>0?_nw:0)*sizeof(bitv_t)*8)

Convert a number of words into the corresponding (bitv_t type) size as a bit-vector size.

Definition at line 166 of file bitv.h.

BU_BITS2WORDS

#define BU_BITS2WORDS

(

_nb

)

(((size_t)(_nb>0?_nb:0)+BU_BITV_MASK)>>BU_BITV_SHIFT)

Convert a bit-vector (stored in a bitv_t array) size into the corresponding word size.

Definition at line 172 of file bitv.h.

BU_BITS2BYTES

#define BU_BITS2BYTES

(

_nb

)

(BU_BITS2WORDS(_nb)*sizeof(bitv_t))

Convert a bit-vector (stored in a bitv_t array) size into the corresponding total memory size (in bytes) of the bitv_t array.

Definition at line 178 of file bitv.h.

BU_BITSET

#define BU_BITSET	(		_bv,
			bit
	)		((_bv)->bits[(bit)>>BU_BITV_SHIFT] |= (((bitv_t)1)<<((bit)&BU_BITV_MASK)))

Definition at line 188 of file bitv.h.

BU_BITCLR

#define BU_BITCLR	(		_bv,
			bit
	)		((_bv)->bits[(bit)>>BU_BITV_SHIFT] &= ~(((bitv_t)1)<<((bit)&BU_BITV_MASK)))

Definition at line 191 of file bitv.h.

BU_BITTEST

#define BU_BITTEST	(		_bv,
			bit
	)		(((_bv)->bits[(bit)>>BU_BITV_SHIFT] & (((bitv_t)1)<<((bit)&BU_BITV_MASK)))!=0)

Definition at line 197 of file bitv.h.

BU_BITV_ZEROALL

#define BU_BITV_ZEROALL

(

_bv

)

bu_bitv_clear(_bv)

zeros all of the internal storage bytes in a bit vector array

Definition at line 203 of file bitv.h.

BU_BITV_BITNUM_CHECK

#define BU_BITV_BITNUM_CHECK	(		_bv,
			_bit
	)

Value:

    /* Validate bit number */ \
    if (UNLIKELY(((unsigned)(_bit)) >= (_bv)->nbits)) {\
	bu_log("BU_BITV_BITNUM_CHECK bit number (%u) out of range (0..%u)\n", \
               ((unsigned)(_bit)), (_bv)->nbits); \
	bu_bomb("process self-terminating\n");\
    }

Definition at line 210 of file bitv.h.

BU_BITV_NBITS_CHECK

#define BU_BITV_NBITS_CHECK	(		_bv,
			_nbits
	)

Value:

    /* Validate number of bits */ \
    if (UNLIKELY(((unsigned)(_nbits)) > (_bv)->nbits)) {\
	bu_log("BU_BITV_NBITS_CHECK number of bits (%u) out of range (> %u)", \
               ((unsigned)(_nbits)), (_bv)->nbits); \
	bu_bomb("process self-terminating"); \
    }

Definition at line 221 of file bitv.h.

BU_BITV_LOOP_START

#define BU_BITV_LOOP_START

(

_bv

)

Value:

    { \
    int _wd;    /* Current word number */  \
    BU_CK_BITV(_bv); \
    for (_wd=BU_BITS2WORDS((_bv)->nbits)-1; _wd>=0; _wd--) {  \
    int _b;     /* Current bit-in-word number */  \
    bitv_t _val;        /* Current word value */  \
    if ((_val = (_bv)->bits[_wd])==0) continue;  \
    for (_b=0; _b < BU_BITV_MASK+1; _b++, _val >>= 1) { \
    if (!(_val & 1)) continue;

DEPRECATED: Macros to efficiently find all the ONE bits in a bit vector. Counts words down, counts bits in words going up, for speed & portability. It does not matter if the shift causes the sign bit to smear to the right.

Example:

BU_BITV_LOOP_START(bv) {
  fiddle(BU_BITV_LOOP_INDEX);
} BU_BITV_LOOP_END;

Definition at line 246 of file bitv.h.

BU_BITV_LOOP_END

#define BU_BITV_LOOP_END

Value:

        } /* end for (_b) */ \
        } /* end for (_wd) */ \
        } /* end block */

DEPRECATED: Paired with BU_BITV_LOOP_START()

Definition at line 260 of file bitv.h.

Typedef Documentation

bitv_t

typedef uint64_t bitv_t

bitv_t should be a fast integer type for implementing bit vectors.

On many machines, this is a 32-bit "long", but on some machines a compiler/vendor-specific type such as "long long" or even 'char' can give access to faster integers.

THE SIZE OF bitv_t MUST MATCH BU_BITV_SHIFT.

Definition at line 61 of file bitv.h.

bu_bitv_t

typedef struct bu_bitv bu_bitv_t

Definition at line 100 of file bitv.h.

Function Documentation

bu_bitv_shift()

size_t bu_bitv_shift ( void  )

extern

returns floor(log2(sizeof(bitv_t)*8.0)), i.e. the number of bits required with base-2 encoding to index any bit in an array of length sizeof(bitv_t)*8.0 bits long. users should not call this directly, instead calling the BU_BITV_SHIFT macro instead.

bu_bitv_set()

void bu_bitv_set ( struct bu_bitv *  bv, size_t  bit  )

extern

bu_bitv_clear_bit()

void bu_bitv_clear_bit ( struct bu_bitv *  bv, size_t  bit  )

extern

bu_bitv_test()

int bu_bitv_test ( const struct bu_bitv *  bv, size_t  bit  )

extern

bu_bitv_length()

size_t bu_bitv_length ( const struct bu_bitv *  bv )

extern

bu_bitv_count_set()

size_t bu_bitv_count_set ( const struct bu_bitv *  bv )

extern

Count the number of set bits.

bu_bitv_foreach()

void bu_bitv_foreach ( const struct bu_bitv *  bv, void(*)(size_t bit, void *data)  callback, void *  data  )

extern

Iterate over all set bits in the bit vector efficiently.

This function quickly skips over large blocks of zeroes using machine-word level operations, making it significantly faster than a bit-by-bit test loop when the bit vector is sparse. For each bit that is set to 1, the provided callback function is invoked with the index of the set bit and the user-provided data pointer.

Parameters

bv	The bit vector to iterate over.
callback	The function to call for each set bit.
data	User-provided context passed directly to the callback.

bu_bitv_new()

struct bu_bitv * bu_bitv_new ( size_t  nbits )

extern

Allocate storage for a new bit vector of at least 'nbits' in length. The bit vector itself is guaranteed to be initialized to all zero.

Because struct bu_bitv embeds one full machine word (bitv_t, currently 64 bits) inline, requests for fewer than 64 bits are silently rounded up to 64 and require no extra heap allocation beyond the struct itself. Requesting exactly 0 bits is valid and results in a usable 64-bit vector.

bu_bitv_free()

void bu_bitv_free ( struct bu_bitv *  bv )

extern

Release all internal storage for this bit vector.

It is the caller's responsibility to not use the pointer 'bv' any longer. It is the caller's responsibility to dequeue from any linked list first.

bu_bitv_clear()

void bu_bitv_clear ( struct bu_bitv *  bv )

extern

Set all the bits in the bit vector to zero.

Also available as a BU_BITV_ZEROALL macro if you don't desire the pointer checking.

bu_bitv_or()

void bu_bitv_or ( struct bu_bitv *  ov, const struct bu_bitv *  iv  )

extern

Performs an in-place bitwise OR operation on a bit vector.

Result is stored in 'ov' (ov = ov | iv). If the vectors are of differing lengths, the operation will safely process up to the bounds of the overlapping arrays. Any excess bits in 'ov' that do not exist in 'iv' are preserved as-is.

Parameters

ov	Destination and first operand bit vector.
iv	Source bit vector operand.

bu_bitv_and()

void bu_bitv_and ( struct bu_bitv *  ov, const struct bu_bitv *  iv  )

extern

Performs an in-place bitwise AND operation on a bit vector.

Result is stored in 'ov' (ov = ov & iv). If the vectors are of differing lengths, the operation will safely process up to the bounds of the overlapping arrays. For an AND operation, any excess bits in 'ov' that do not exist in 'iv' are cleared to 0.

Parameters

ov	Destination and first operand bit vector.
iv	Source bit vector operand.

bu_bitv_not()

void bu_bitv_not ( struct bu_bitv *  ov )

extern

Performs an in-place bitwise NOT operation on a bit vector.

Flips all bits in the vector (ov = ~ov). Safely preserves the unused trailing padding bits in the final machine word.

Parameters

ov	The bit vector to invert.

bu_bitv_xor()

void bu_bitv_xor ( struct bu_bitv *  ov, const struct bu_bitv *  iv  )

extern

Performs an in-place bitwise XOR (exclusive OR) operation on a bit vector.

Result is stored in 'ov' (ov = ov ^ iv). If the vectors are of differing lengths, the operation processes up to the bounds of the overlapping arrays. Excess bits in 'ov' remain unchanged.

Parameters

ov	Destination and first operand bit vector.
iv	Source bit vector operand.

bu_bitv_shift_vector()

void bu_bitv_shift_vector ( struct bu_bitv *  ov, int  shift  )

extern

Shifts entire bit vector left or right across word boundaries.

A positive shift value shifts the bits left (towards higher indices), effectively moving bit N to N+shift. A negative shift value shifts the bits right (towards lower indices), moving bit N to N-|shift|. Bits shifted out of bounds are discarded. Vacated bits are zeroed.

Parameters

ov	The bit vector to shift.
shift	The number of bits to shift.

bu_bitv_vls()

void bu_bitv_vls ( struct bu_vls *  v, const struct bu_bitv *  bv  )

extern

Print the bits set in a bit vector.

bu_pr_bitv()

void bu_pr_bitv ( const char *  str, const struct bu_bitv *  bv  )

extern

Print the bits set in a bit vector. Use bu_vls stuff, to make only a single call to bu_log().

bu_bitv_to_hex()

void bu_bitv_to_hex ( struct bu_vls *  v, const struct bu_bitv *  bv  )

extern

Convert a bit vector to an ascii string of hex digits. The string is from MSB to LSB (bytes and bits).

bu_hex_to_bitv()

struct bu_bitv * bu_hex_to_bitv ( const char *  str )

extern

Convert a string of HEX digits (as produced by bu_bitv_to_hex) into a bit vector.

bu_bitv_to_binary()

void bu_bitv_to_binary ( struct bu_vls *  v, const struct bu_bitv *  bv  )

extern

Convert a bit vector to an ascii string of binary digits in the GCC format ("0bn..."). The string is from MSB to LSB (bytes and bits).

bu_binary_to_bitv()

struct bu_bitv * bu_binary_to_bitv ( const char *  str )

extern

Convert a string of BINARY digits (as produced by bu_bitv_to_binary) into a bit vector.

bu_binary_to_bitv2()

struct bu_bitv * bu_binary_to_bitv2 ( const char *  str, const int  nbytes  )

extern

Convert a string of BINARY digits (as produced by bu_bitv_to_binary) into a bit vector. The "nbytes" argument may be zero if the user has no minimum length preference.

bu_bitv_compare_equal()

int bu_bitv_compare_equal ( const struct bu_bitv *  , const struct bu_bitv *    )

extern

Compare two bit vectors for equality. They are considered equal iff their lengths and each bit are equal. Returns 1 for true, zero for false.

bu_bitv_compare_equal2()

int bu_bitv_compare_equal2 ( const struct bu_bitv *  , const struct bu_bitv *    )

extern

Compare two bit vectors for equality. They are considered equal iff their non-zero bits are equal (leading zero bits are ignored so lengths are not considered explicitly). Returns 1 for true, 0 for false.

bu_bitv_dup()

struct bu_bitv * bu_bitv_dup ( const struct bu_bitv *  bv )

extern

Make a copy of a bit vector

bu_hexstr_to_binstr()

int bu_hexstr_to_binstr ( const char *  hexstr, struct bu_vls *  b  )

extern

Convert a string of hex characters to an equivalent string of binary characters.

The input hex string may have an optional prefix of '0x' or '0X' in which case the resulting binary string will be prefixed with '0b'.

The input string is expected to represent an integral number of bytes but will have leading zeroes prepended as necessary to fulfill that requirement.

Returns BRLCAD_OK for success, BRLCAD_ERROR for errors.

bu_binstr_to_hexstr()

int bu_binstr_to_hexstr ( const char *  binstr, struct bu_vls *  h  )

extern

Convert a string of binary characters to an equivalent string of hex characters.

The input binary string may have an optional prefix of '0b' or '0B' in which case the resulting hex string will be prefixed with '0x'.

The input string is expected to represent an integral number of bytes but will have leading zeroes prepended as necessary to fulfill that requirement.

Returns BRLCAD_OK for success, BRLCAD_ERROR for errors.

bu_printb()

void bu_printb ( const char *  label, unsigned long  bits, const char *  format  )

extern

Bit field printing implementation.

Print a bit field according to a format specification via bu_log().

Line printed is of the form "String Label: x1234 <FOO,BAR,RAB,OOF>" and is commonly used by debugging code to print which debug bits are enabled.

Parameters

label	string label
bits	integer with the bits to print
format	format specification

The 'format' begins with a desired printing base (8 or 16), i.e., \010 means print octal and \020 for hex. Remaining string is the little endian bit position (i.e., 1 to 32 encoded in octal format) followed by a label for that bit (e.g., "\010\2Bit_one\1BIT_zero")

Note octal counting is used for the bit position label: \01 -> ... \07 -> \10 -> \11 -> ... \17 -> \20 ... etc

bu_vls_printb()

void bu_vls_printb ( struct bu_vls *  vls, const char *  label, unsigned long  bits, const char *  format  )

extern

Same as bu_printb() but with output going to a vls instead of stderr