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 bu_bitv_shift()

#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}, 0, {0, 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_BITTEST(_bv, bit) (((_bv)->bits[(bit)>>BU_BITV_SHIFT] & (((bitv_t)1)<<((bit)&BU_BITV_MASK)))!=0)

#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_BITV_ZEROALL(_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_INDEX ((_wd << BU_BITV_SHIFT) \| _b)

#define	BU_BITV_LOOP_END

Typedefs
typedef unsigned char	bitv_t

typedef struct bu_bitv	bu_bitv_t

Functions
size_t	bu_bitv_shift (void)

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_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. More...

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 bu_bitv_shift()

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 86 of file bitv.h.

◆ BU_BITV_MASK

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

Bit vector mask

Definition at line 90 of file bitv.h.

◆ BU_BITV_NULL

#define BU_BITV_NULL ((struct bu_bitv *)0)

Definition at line 114 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 119 of file bitv.h.

◆ BU_BITV_INIT

#define BU_BITV_INIT ( _bp )

Value:

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

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

Definition at line 125 of file bitv.h.

◆ BU_BITV_INIT_ZERO

#define BU_BITV_INIT_ZERO { {BU_BITV_MAGIC, BU_LIST_NULL, BU_LIST_NULL}, 0, {0, 0} }

macro suitable for declaration statement initialization of a bu_bitv struct. does not allocate memory. not suitable for a head node.

Definition at line 136 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 141 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 155 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 161 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 167 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 171 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 186 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 188 of file bitv.h.

◆ BU_BITV_ZEROALL

#define BU_BITV_ZEROALL ( _bv )

Value:

    { \
        if (LIKELY((_bv) && (_bv)->nbits != 0)) { \
            unsigned char *bvp = (unsigned char *)(_bv)->bits; \
            size_t nbytes = BU_BITS2BYTES((_bv)->nbits); \
            do { \
                *bvp++ = (unsigned char)0; \
            } while (--nbytes != 0); \
        } \
    }

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

Definition at line 194 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;

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;

BU_BITV_LOOP_START
#define BU_BITV_LOOP_START(_bv)
Definition: bitv.h:246

BU_BITV_LOOP_INDEX
#define BU_BITV_LOOP_INDEX
Definition: bitv.h:261

BU_BITV_LOOP_END
#define BU_BITV_LOOP_END
Definition: bitv.h:266

Definition at line 246 of file bitv.h.

◆ BU_BITV_LOOP_INDEX

#define BU_BITV_LOOP_INDEX ((_wd << BU_BITV_SHIFT) | _b)

This macro is valid only between a BU_BITV_LOOP_START/LOOP_END pair, and gives the bit number of the current iteration.

Definition at line 261 of file bitv.h.

◆ BU_BITV_LOOP_END

#define BU_BITV_LOOP_END

Value:

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

Paired with BU_BITV_LOOP_START()

Definition at line 266 of file bitv.h.

Typedef Documentation

◆ bitv_t

typedef unsigned char 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 62 of file bitv.h.

◆ bu_bitv_t

typedef struct bu_bitv bu_bitv_t

Definition at line 113 of file bitv.h.

Function Documentation

◆ bu_bitv_shift()

size_t bu_bitv_shift ( void )

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_new()

struct bu_bitv * bu_bitv_new ( size_t nbits )

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.

◆ bu_bitv_free()

void bu_bitv_free ( struct bu_bitv * bv )

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 )

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
	)

TBD

◆ bu_bitv_and()

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

TBD

◆ bu_bitv_vls()

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

Print the bits set in a bit vector.

◆ bu_pr_bitv()

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

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
	)

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 )

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
	)

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 )

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
	)

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 *
	)

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 *
	)

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 )

Make a copy of a bit vector

◆ bu_hexstr_to_binstr()

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

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
	)

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
	)

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
	)

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

Files

Data Structures

Macros

Typedefs

Functions

Detailed Description

Macro Definition Documentation

◆ BU_BITV_SHIFT

◆ BU_BITV_MASK

◆ BU_BITV_NULL

◆ BU_CK_BITV

◆ BU_BITV_INIT

◆ BU_BITV_INIT_ZERO

◆ BU_BITV_IS_INITIALIZED

◆ BU_WORDS2BITS

◆ BU_BITS2WORDS

◆ BU_BITS2BYTES

◆ BU_BITTEST

◆ BU_BITSET

◆ BU_BITCLR

◆ BU_BITV_ZEROALL

◆ BU_BITV_BITNUM_CHECK

◆ BU_BITV_NBITS_CHECK

◆ BU_BITV_LOOP_START

◆ BU_BITV_LOOP_INDEX

◆ BU_BITV_LOOP_END

Typedef Documentation

◆ bitv_t

◆ bu_bitv_t

Function Documentation

◆ bu_bitv_shift()

◆ bu_bitv_new()

◆ bu_bitv_free()

◆ bu_bitv_clear()

◆ bu_bitv_or()

◆ bu_bitv_and()

◆ bu_bitv_vls()

◆ bu_pr_bitv()

◆ bu_bitv_to_hex()

◆ bu_hex_to_bitv()

◆ bu_bitv_to_binary()

◆ bu_binary_to_bitv()

◆ bu_binary_to_bitv2()

◆ bu_bitv_compare_equal()

◆ bu_bitv_compare_equal2()

◆ bu_bitv_dup()

◆ bu_hexstr_to_binstr()

◆ bu_binstr_to_hexstr()

◆ bu_printb()

◆ bu_vls_printb()