Bit Vectors
Collaboration diagram for Bit Vectors:


This browser is not able to show SVG: try Firefox, Chrome, Safari, or Opera instead.

file  bitv.c

file  printb.c

struct  bu_bitv

## Macros

#define BU_BITV_SHIFT   bu_bitv_shift()

#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_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_bitvbu_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_bitvbu_hex_to_bitv (const char *str)

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

struct bu_bitvbu_binary_to_bitv (const char *str)

struct bu_bitvbu_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_bitvbu_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_vls_printb (struct bu_vls *vls, const char *s, unsigned long v, const char *bits)

void bu_printb (const char *s, unsigned long v, const char *bits)

## Macro Definition Documentation

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

Referenced by rt_prep_parallel().

Definition at line 87 of file bitv.h.

 #define BU_BITV_NULL   ((struct bu_bitv *)0)

Definition at line 111 of file bitv.h.

Referenced by bottie_prep_double().

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

 #define BU_BITV_INIT ( _bp )
Value:
{ \
(_bp)->nbits = 0; \
(_bp)->bits = 0; \
(_bp)->bits = 0; \
}
#define BU_BITV_MAGIC
Definition: magic.h:47
#define BU_LIST_INIT_MAGIC(_hp, _magic)
Definition: list.h:156

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

Definition at line 122 of file bitv.h.

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

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

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

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

Referenced by bu_bitv_and(), and bu_bitv_or().

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

Referenced by bu_bitv_new().

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

Definition at line 168 of file bitv.h.

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

Definition at line 183 of file bitv.h.

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

Definition at line 185 of file bitv.h.

 #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); \
} \
}
#define LIKELY(expression)
Definition: common.h:261
if(share_geom)
Definition: nmg_mod.c:3829
#define BU_BITS2BYTES(_nb)
Definition: bitv.h:164

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

Definition at line 191 of file bitv.h.

Referenced by bu_bitv_clear(), bu_bitv_new(), and rt_shootray().

 #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");\
}
void bu_log(const char *,...) _BU_ATTR_PRINTF12
Definition: log.c:176
if(share_geom)
Definition: nmg_mod.c:3829
void bu_bomb(const char *str) _BU_ATTR_NORETURN
Definition: bomb.c:91
#define UNLIKELY(expression)
Definition: common.h:282

Definition at line 207 of file bitv.h.

 #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"); \
}
void bu_log(const char *,...) _BU_ATTR_PRINTF12
Definition: log.c:176
if(share_geom)
Definition: nmg_mod.c:3829
void bu_bomb(const char *str) _BU_ATTR_NORETURN
Definition: bomb.c:91
#define UNLIKELY(expression)
Definition: common.h:282

Definition at line 218 of file bitv.h.

 #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;
Definition: bitv.h:87
unsigned char bitv_t
Definition: bitv.h:59
if(share_geom)
Definition: nmg_mod.c:3829
#define BU_BITS2WORDS(_nb)
Definition: bitv.h:158
#define BU_CK_BITV(_bp)
Definition: bitv.h:116

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:
1 BU_BITV_LOOP_START(bv) {
2  fiddle(BU_BITV_LOOP_INDEX);
3 } BU_BITV_LOOP_END;

Definition at line 243 of file bitv.h.

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

 #define BU_BITV_LOOP_END
Value:
} /* end for (_b) */ \
} /* end for (_wd) */ \
} /* end block */

Paired with BU_BITV_LOOP_START()

Definition at line 263 of file bitv.h.

## Typedef Documentation

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

 typedef struct bu_bitv bu_bitv_t

Definition at line 110 of file bitv.h.

## Function Documentation

 size_t bu_bitv_shift ( void )
inline

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.

Wrap the above private routines for computing the bitv shift size. Users should not call this directly, instead calling the BU_BITV_SHIFT macro instead.

Definition at line 80 of file bitv.c.

References BITS_PER_BYTE, and FLOOR_ILOG2.

 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.

Definition at line 91 of file bitv.c.

Here is the call graph for this function:

 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.

Definition at line 113 of file bitv.c.

References bu_list::back, BU_CK_BITV, bu_free(), BU_LIST_NULL, bu_list::forw, and bu_bitv::l.

Referenced by bu_binary_to_bitv2(), bu_hex_to_bitv(), rt_res_pieces_clean(), and rt_vshootray().

Here is the call graph for this function:

 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.

Definition at line 123 of file bitv.c.

References BU_BITV_ZEROALL, and BU_CK_BITV.

Referenced by rt_get_solidbitv().

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

TBD

Definition at line 132 of file bitv.c.

References bu_bitv::bits, BU_BITS2WORDS, bu_bomb(), bu_bitv::nbits, out, and UNLIKELY.

Referenced by bu_bitv_dup().

Here is the call graph for this function:

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

TBD

Definition at line 155 of file bitv.c.

References bu_bitv::bits, BU_BITS2WORDS, bu_bomb(), bu_bitv::nbits, out, and UNLIKELY.

Here is the call graph for this function:

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

Print the bits set in a bit vector.

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

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

Definition at line 222 of file bitv.c.

Referenced by rt_bot_export4(), rt_bot_export5(), and rt_bot_get().

Here is the call graph for this function:

 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.

Definition at line 248 of file bitv.c.

References bu_bitv::bits, BITS_PER_BYTE, bu_bitv_free(), bu_bitv_new(), and bu_log().

Referenced by rt_bot_adjust(), rt_bot_import4(), and rt_bot_import5().

Here is the call graph for this function:

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

Definition at line 349 of file bitv.c.

Here is the call graph for this function:

 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.

Definition at line 377 of file bitv.c.

References bu_binary_to_bitv2().

Here is the call graph for this function:

 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.

Definition at line 406 of file bitv.c.

Referenced by bu_binary_to_bitv().

Here is the call graph for this function:

 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.

Definition at line 556 of file bitv.c.

References BU_BITTEST, BU_CK_BITV, and bu_bitv::nbits.

 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.

Definition at line 581 of file bitv.c.

References BU_BITTEST, BU_CK_BITV, and bu_bitv::nbits.

 struct bu_bitv* bu_bitv_dup ( const struct bu_bitv * bv )

Make a copy of a bit vector

Referenced by bottie_prep_double(), dup_bot(), mk_bot_w_normals(), rt_bot_xform(), and XGLUE().

 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.

Definition at line 751 of file bitv.c.

Here is the call graph for this function:

 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.

Definition at line 636 of file bitv.c.

Here is the call graph for this function:

 void bu_vls_printb ( struct bu_vls * vls, const char * s, unsigned long v, const char * bits )

Format a value a la the b format of the kernel's printf

Parameters
 vls variable length string to put output in s title string v the integer with the bits in it bits a string which starts with the desired base (8 or 16) as \010 or \020, followed by words preceded with embedded low-value bytes indicating bit number plus one, in little-endian order, e.g.: "\010\2Bit_one\1BIT_zero"

Referenced by ged_debugbu(), ged_debuglib(), and ged_debugnmg().

 void bu_printb ( const char * s, unsigned long v, const char * bits )

Format and print, like bu_vls_printb().