BRL-CAD
bitv.h
Go to the documentation of this file.
1 /* B I T V . H
2  * BRL-CAD
3  *
4  * Copyright (c) 2004-2014 United States Government as represented by
5  * the U.S. Army Research Laboratory.
6  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public License
9  * version 2.1 as published by the Free Software Foundation.
10  *
11  * This library is distributed in the hope that it will be useful, but
12  * WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14  * Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with this file; see the file named COPYING for more
18  * information.
19  */
20 
21 #ifndef BU_BITV_H
22 #define BU_BITV_H
23 
24 #include "common.h"
25 
26 #include "bu/defines.h"
27 #include "bu/magic.h"
28 #include "bu/list.h"
29 #include "bu/vls.h"
30 
32 
33 /*----------------------------------------------------------------------*/
34 /** @addtogroup bitv */
35 /** @{*/
36 /** @file libbu/bitv.c
37  *
38  * Routines for managing efficient high-performance bit vectors of
39  * arbitrary length.
40  *
41  * The basic type "bitv_t" is defined in include/bu.h; it is the
42  * widest integer datatype for which efficient hardware support
43  * exists. BU_BITV_SHIFT and BU_BITV_MASK are also defined in bu.h
44  *
45  * These bit vectors are "little endian", bit 0 is in the right hand
46  * side of the [0] word.
47  *
48  */
49 
50 /**
51  * bitv_t should be a fast integer type for implementing bit vectors.
52  *
53  * On many machines, this is a 32-bit "long", but on some machines a
54  * compiler/vendor-specific type such as "long long" or even 'char'
55  * can give access to faster integers.
56  *
57  * THE SIZE OF bitv_t MUST MATCH BU_BITV_SHIFT.
58  */
59 typedef unsigned char bitv_t;
60 
61 /**
62  * Bit vector shift size
63  *
64  * Should equal to: log2(sizeof(bitv_t)*8.0). Using bu_bitv_shift()
65  * will return a run-time computed shift size if the size of a bitv_t
66  * changes. Performance impact is rather minimal for most models but
67  * disabled for a handful of primitives that heavily rely on bit
68  * vectors.
69  *
70  * (8-bit type: 3, 16-bit type: 4, 32-bit type: 5, 64-bit type: 6)
71  */
72 #ifdef CHAR_BIT
73 # if CHAR_BIT == 8
74 # define BU_BITV_SHIFT 3
75 # elif CHAR_BIT == 16
76 # define BU_BITV_SHIFT 4
77 # elif CHAR_BIT == 32
78 # define BU_BITV_SHIFT 5
79 # elif CHAR_BIT == 64
80 # define BU_BITV_SHIFT 6
81 # endif
82 #else
83 # define BU_BITV_SHIFT bu_bitv_shift()
84 #endif
85 
86 /** Bit vector mask */
87 #define BU_BITV_MASK ((1<<BU_BITV_SHIFT)-1)
88 
89 /**
90  * Bit vector data structure.
91  *
92  * bu_bitv uses a little-endian encoding, placing bit 0 on the right
93  * side of the 0th word.
94  *
95  * This is done only because left-shifting a 1 can be done in an
96  * efficient word-length-independent manner; going the other way would
97  * require a compile-time constant with only the sign bit set, and an
98  * unsigned right shift, which some machines don't have in hardware,
99  * or an extra subtraction.
100  *
101  * Application code should *never* peek at the bit-buffer; use the
102  * macros. The external hex form is most significant byte first (bit
103  * 0 is at the right). Note that MUVES does it differently.
104  */
105 struct bu_bitv {
106  struct bu_list l; /**< linked list for caller's use */
107  size_t nbits; /**< actual size of bits[], in bits */
108  bitv_t bits[2]; /**< variable size array */
109 };
110 typedef struct bu_bitv bu_bitv_t;
111 #define BU_BITV_NULL ((struct bu_bitv *)0)
112 
113 /**
114  * asserts the integrity of a non-head node bu_bitv struct.
115  */
116 #define BU_CK_BITV(_bp) BU_CKMAG(_bp, BU_BITV_MAGIC, "bu_bitv")
117 
118 /**
119  * initializes a bu_bitv struct without allocating any memory. this
120  * macro is not suitable for initializing a head list node.
121  */
122 #define BU_BITV_INIT(_bp) { \
123  BU_LIST_INIT_MAGIC(&(_bp)->l, BU_BITV_MAGIC); \
124  (_bp)->nbits = 0; \
125  (_bp)->bits[0] = 0; \
126  (_bp)->bits[1] = 0; \
127  }
128 
129 /**
130  * macro suitable for declaration statement initialization of a bu_bitv
131  * struct. does not allocate memory. not suitable for a head node.
132  */
133 #define BU_BITV_INIT_ZERO { {BU_BITV_MAGIC, BU_LIST_NULL, BU_LIST_NULL}, 0, {0, 0} }
134 
135 /**
136  * returns truthfully whether a bu_bitv has been initialized
137  */
138 #define BU_BITV_IS_INITIALIZED(_bp) (((struct bu_bitv *)(_bp) != BU_BITV_NULL) && LIKELY((_bp)->l.magic == BU_BITV_MAGIC))
139 
140 /**
141  * returns floor(log2(sizeof(bitv_t)*8.0)), i.e. the number of bits
142  * required with base-2 encoding to index any bit in an array of
143  * length sizeof(bitv_t)*8.0 bits long. users should not call this
144  * directly, instead calling the BU_BITV_SHIFT macro instead.
145  */
146 BU_EXPORT extern size_t bu_bitv_shift(void);
147 
148 /**
149  * Convert a number of words into the corresponding (bitv_t type) size
150  * as a bit-vector size.
151  */
152 #define BU_WORDS2BITS(_nw) ((size_t)(_nw>0?_nw:0)*sizeof(bitv_t)*8)
153 
154 /**
155  * Convert a bit-vector (stored in a bitv_t array) size into the
156  * corresponding word size.
157  */
158 #define BU_BITS2WORDS(_nb) (((size_t)(_nb>0?_nb:0)+BU_BITV_MASK)>>BU_BITV_SHIFT)
159 
160 /**
161  * Convert a bit-vector (stored in a bitv_t array) size into the
162  * corresponding total memory size (in bytes) of the bitv_t array.
163  */
164 #define BU_BITS2BYTES(_nb) (BU_BITS2WORDS(_nb)*sizeof(bitv_t))
165 
166 
167 #if 1
168 #define BU_BITTEST(_bv, bit) \
169  (((_bv)->bits[(bit)>>BU_BITV_SHIFT] & (((bitv_t)1)<<((bit)&BU_BITV_MASK)))!=0)
170 #else
171 static __inline__ int BU_BITTEST(volatile void * addr, int nr)
172 {
173  int oldbit;
174 
175  __asm__ __volatile__(
176  "btl %2, %1\n\tsbbl %0, %0"
177  :"=r" (oldbit)
178  :"m" (addr), "Ir" (nr));
179  return oldbit;
180 }
181 #endif
182 
183 #define BU_BITSET(_bv, bit) \
184  ((_bv)->bits[(bit)>>BU_BITV_SHIFT] |= (((bitv_t)1)<<((bit)&BU_BITV_MASK)))
185 #define BU_BITCLR(_bv, bit) \
186  ((_bv)->bits[(bit)>>BU_BITV_SHIFT] &= ~(((bitv_t)1)<<((bit)&BU_BITV_MASK)))
187 
188 /**
189  * zeros all of the internal storage bytes in a bit vector array
190  */
191 #define BU_BITV_ZEROALL(_bv) \
192  { \
193  if (LIKELY((_bv) && (_bv)->nbits != 0)) { \
194  unsigned char *bvp = (unsigned char *)(_bv)->bits; \
195  size_t nbytes = BU_BITS2BYTES((_bv)->nbits); \
196  do { \
197  *bvp++ = (unsigned char)0; \
198  } while (--nbytes != 0); \
199  } \
200  }
201 
202 
203 /* This is not done by default for performance reasons */
204 #ifdef NO_BOMBING_MACROS
205 # define BU_BITV_BITNUM_CHECK(_bv, _bit) BU_IGNORE((_bv))
206 #else
207 # define BU_BITV_BITNUM_CHECK(_bv, _bit) /* Validate bit number */ \
208  if (UNLIKELY(((unsigned)(_bit)) >= (_bv)->nbits)) {\
209  bu_log("BU_BITV_BITNUM_CHECK bit number (%u) out of range (0..%u)\n", \
210  ((unsigned)(_bit)), (_bv)->nbits); \
211  bu_bomb("process self-terminating\n");\
212  }
213 #endif
214 
215 #ifdef NO_BOMBING_MACROS
216 # define BU_BITV_NBITS_CHECK(_bv, _nbits) BU_IGNORE((_bv))
217 #else
218 # define BU_BITV_NBITS_CHECK(_bv, _nbits) /* Validate number of bits */ \
219  if (UNLIKELY(((unsigned)(_nbits)) > (_bv)->nbits)) {\
220  bu_log("BU_BITV_NBITS_CHECK number of bits (%u) out of range (> %u)", \
221  ((unsigned)(_nbits)), (_bv)->nbits); \
222  bu_bomb("process self-terminating"); \
223  }
224 #endif
225 
226 
227 /**
228  * Macros to efficiently find all the ONE bits in a bit vector.
229  * Counts words down, counts bits in words going up, for speed &
230  * portability. It does not matter if the shift causes the sign bit
231  * to smear to the right.
232  *
233  * @par Example:
234  @code
235 
236  BU_BITV_LOOP_START(bv) {
237  fiddle(BU_BITV_LOOP_INDEX);
238  } BU_BITV_LOOP_END;
239 
240  @endcode
241  *
242  */
243 #define BU_BITV_LOOP_START(_bv) \
244  { \
245  int _wd; /* Current word number */ \
246  BU_CK_BITV(_bv); \
247  for (_wd=BU_BITS2WORDS((_bv)->nbits)-1; _wd>=0; _wd--) { \
248  int _b; /* Current bit-in-word number */ \
249  bitv_t _val; /* Current word value */ \
250  if ((_val = (_bv)->bits[_wd])==0) continue; \
251  for (_b=0; _b < BU_BITV_MASK+1; _b++, _val >>= 1) { \
252  if (!(_val & 1)) continue;
253 
254 /**
255  * This macro is valid only between a BU_BITV_LOOP_START/LOOP_END
256  * pair, and gives the bit number of the current iteration.
257  */
258 #define BU_BITV_LOOP_INDEX ((_wd << BU_BITV_SHIFT) | _b)
259 
260 /**
261  * Paired with BU_BITV_LOOP_START()
262  */
263 #define BU_BITV_LOOP_END \
264  } /* end for (_b) */ \
265  } /* end for (_wd) */ \
266  } /* end block */
267 
268 /**
269  * Allocate storage for a new bit vector of at least 'nbits' in
270  * length. The bit vector itself is guaranteed to be initialized to
271  * all zero.
272  */
273 BU_EXPORT extern struct bu_bitv *bu_bitv_new(size_t nbits);
274 
275 /**
276  * Release all internal storage for this bit vector.
277  *
278  * It is the caller's responsibility to not use the pointer 'bv' any
279  * longer. It is the caller's responsibility to dequeue from any
280  * linked list first.
281  */
282 BU_EXPORT extern void bu_bitv_free(struct bu_bitv *bv);
283 
284 /**
285  * Set all the bits in the bit vector to zero.
286  *
287  * Also available as a BU_BITV_ZEROALL macro if you don't desire the
288  * pointer checking.
289  */
290 BU_EXPORT extern void bu_bitv_clear(struct bu_bitv *bv);
291 
292 /**
293  * TBD
294  */
295 BU_EXPORT extern void bu_bitv_or(struct bu_bitv *ov, const struct bu_bitv *iv);
296 
297 /**
298  * TBD
299  */
300 BU_EXPORT extern void bu_bitv_and(struct bu_bitv *ov, const struct bu_bitv *iv);
301 
302 /**
303  * Print the bits set in a bit vector.
304  */
305 BU_EXPORT extern void bu_bitv_vls(struct bu_vls *v, const struct bu_bitv *bv);
306 
307 /**
308  * Print the bits set in a bit vector. Use bu_vls stuff, to make only
309  * a single call to bu_log().
310  */
311 BU_EXPORT extern void bu_pr_bitv(const char *str, const struct bu_bitv *bv);
312 
313 /**
314  * Convert a bit vector to an ascii string of hex digits. The string
315  * is from MSB to LSB (bytes and bits).
316  */
317 BU_EXPORT extern void bu_bitv_to_hex(struct bu_vls *v, const struct bu_bitv *bv);
318 
319 /**
320  * Convert a string of HEX digits (as produced by bu_bitv_to_hex) into
321  * a bit vector.
322  */
323 BU_EXPORT extern struct bu_bitv *bu_hex_to_bitv(const char *str);
324 
325 /**
326  * Convert a bit vector to an ascii string of binary digits in the GCC
327  * format ("0bn..."). The string is from MSB to LSB (bytes and bits).
328  */
329 BU_EXPORT extern void bu_bitv_to_binary(struct bu_vls *v, const struct bu_bitv *bv);
330 
331 /**
332  * Convert a string of BINARY digits (as produced by
333  * bu_bitv_to_binary) into a bit vector.
334  */
335 BU_EXPORT extern struct bu_bitv *bu_binary_to_bitv(const char *str);
336 
337 /**
338  * Convert a string of BINARY digits (as produced by
339  * bu_bitv_to_binary) into a bit vector. The "nbytes" argument may be
340  * zero if the user has no minimum length preference.
341  */
342 BU_EXPORT extern struct bu_bitv *bu_binary_to_bitv2(const char *str, const int nbytes);
343 
344 /**
345  * Compare two bit vectors for equality. They are considered equal iff
346  * their lengths and each bit are equal. Returns 1 for true, zero for
347  * false.
348  */
349 BU_EXPORT extern int bu_bitv_compare_equal(const struct bu_bitv *, const struct bu_bitv *);
350 
351 /**
352  * Compare two bit vectors for equality. They are considered equal iff
353  * their non-zero bits are equal (leading zero bits are ignored so
354  * lengths are not considered explicitly). Returns 1 for true, 0 for
355  * false.
356  */
357 BU_EXPORT extern int bu_bitv_compare_equal2(const struct bu_bitv *, const struct bu_bitv *);
358 
359 /**
360  * Make a copy of a bit vector
361  */
362 BU_EXPORT extern struct bu_bitv *bu_bitv_dup(const struct bu_bitv *bv);
363 
364 
365 /**
366  * Convert a string of hex characters to an equivalent string of
367  * binary characters.
368  *
369  * The input hex string may have an optional prefix of '0x' or '0X' in
370  * which case the resulting binary string will be prefixed with '0b'.
371  *
372  * The input string is expected to represent an integral number of
373  * bytes but will have leading zeroes prepended as necessary to fulfill
374  * that requirement.
375  *
376  * Returns BRLCAD_OK for success, BRLCAD_ERROR for errors.
377  */
378 BU_EXPORT extern int bu_hexstr_to_binstr(const char *hexstr, struct bu_vls *b);
379 
380 
381 /**
382  * Convert a string of binary characters to an equivalent string of
383  * hex characters.
384  *
385  * The input binary string may have an optional prefix of '0b' or '0B'
386  * in which case the resulting hex string will be prefixed with '0x'.
387  *
388  * The input string is expected to represent an integral number of
389  * bytes but will have leading zeroes prepended as necessary to fulfill
390  * that requirement.
391  *
392  * Returns BRLCAD_OK for success, BRLCAD_ERROR for errors.
393  *
394  */
395 BU_EXPORT extern int bu_binstr_to_hexstr(const char *binstr, struct bu_vls *h);
396 
397 /** @file libbu/printb.c
398  *
399  * print bitfields
400  *
401  */
402 
403 /**
404  * Format a value a la the %b format of the kernel's printf
405  *
406  * @param vls variable length string to put output in
407  * @param s title string
408  * @param v the integer with the bits in it
409  * @param bits a string which starts with the desired base (8 or 16)
410  * as \\010 or \\020, followed by
411  * words preceded with embedded low-value bytes indicating
412  * bit number plus one,
413  * in little-endian order, e.g.:
414  * "\010\2Bit_one\1BIT_zero"
415  */
416 BU_EXPORT extern void bu_vls_printb(struct bu_vls *vls,
417  const char *s, unsigned long v,
418  const char *bits);
419 
420 /**
421  * Format and print, like bu_vls_printb().
422  */
423 BU_EXPORT extern void bu_printb(const char *s,
424  unsigned long v,
425  const char *bits);
426 
427 /** @} */
428 
430 
431 #endif /* BU_BITV_H */
432 
433 /*
434  * Local Variables:
435  * mode: C
436  * tab-width: 8
437  * indent-tabs-mode: t
438  * c-file-style: "stroustrup"
439  * End:
440  * ex: shiftwidth=4 tabstop=8
441  */
void bu_pr_bitv(const char *str, const struct bu_bitv *bv)
struct bu_bitv * bu_binary_to_bitv(const char *str)
Definition: bitv.c:377
void bu_bitv_clear(struct bu_bitv *bv)
Definition: bitv.c:123
Definition: list.h:118
struct bu_bitv * bu_bitv_new(size_t nbits)
Definition: bitv.c:91
unsigned char bitv_t
Definition: bitv.h:59
bitv_t bits[2]
Definition: bitv.h:108
if lu s
Definition: nmg_mod.c:3860
struct bu_bitv * bu_binary_to_bitv2(const char *str, const int nbytes)
Definition: bitv.c:406
size_t nbits
Definition: bitv.h:107
int bu_hexstr_to_binstr(const char *hexstr, struct bu_vls *b)
Definition: bitv.c:751
Header file for the BRL-CAD common definitions.
int bu_bitv_compare_equal(const struct bu_bitv *, const struct bu_bitv *)
Definition: bitv.c:556
void bu_vls_printb(struct bu_vls *vls, const char *s, unsigned long v, const char *bits)
#define BU_BITTEST(_bv, bit)
Definition: bitv.h:168
struct bu_list l
Definition: bitv.h:106
#define __BEGIN_DECLS
Definition: common.h:73
void bu_bitv_or(struct bu_bitv *ov, const struct bu_bitv *iv)
Definition: bitv.c:132
size_t bu_bitv_shift(void)
Definition: bitv.c:80
void bu_printb(const char *s, unsigned long v, const char *bits)
void bu_bitv_vls(struct bu_vls *v, const struct bu_bitv *bv)
struct bu_bitv * bu_bitv_dup(const struct bu_bitv *bv)
void bu_bitv_to_hex(struct bu_vls *v, const struct bu_bitv *bv)
Definition: bitv.c:222
int bu_binstr_to_hexstr(const char *binstr, struct bu_vls *h)
Definition: bitv.c:636
void bu_bitv_to_binary(struct bu_vls *v, const struct bu_bitv *bv)
Definition: bitv.c:349
void bu_bitv_free(struct bu_bitv *bv)
Definition: bitv.c:113
void bu_bitv_and(struct bu_bitv *ov, const struct bu_bitv *iv)
Definition: bitv.c:155
#define __END_DECLS
Definition: common.h:74
int bu_bitv_compare_equal2(const struct bu_bitv *, const struct bu_bitv *)
Definition: bitv.c:581
Definition: bitv.h:105
Definition: vls.h:56
struct bu_bitv * bu_hex_to_bitv(const char *str)
Definition: bitv.c:248