bitv.c
Go to the documentation of this file.
1 /* B I T V . C
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
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 #include "common.h"
22
23 #include <stdio.h>
24 #include <stdlib.h>
25 #include <string.h>
26 #include <ctype.h>
27 #include <errno.h>
28 #include <limits.h>
29
30 #include "bu/bitv.h"
31 #include "bu/log.h"
32 #include "bu/malloc.h"
33 #include "bu/vls.h"
34 #include "./bu_internals.h"
35
36 /**
37  * Private 32-bit recursive reduction using "SIMD Within A Register"
38  * (SWAR) to count the number of one bits in a given integer. The
39  * first step is mapping 2-bit values into sum of 2 1-bit values in
40  * sneaky way. This technique was taken from the University of
41  * Kentucky's Aggregate Magic Algorithms collection.
42  *
43  * LLVM 3.2 complains about a static inline function here, so use a macro instead
44  */
45 #define COUNT_ONES32(x) { \
46  x -= ((x >> 1) & 0x55555555); \
47  x = (((x >> 2) & 0x33333333) + (x & 0x33333333)); \
48  x = (((x >> 4) + x) & 0x0f0f0f0f); \
49  x += (x >> 8); \
50  x += (x >> 16); \
51  x &= 0x0000003f; \
52 }
53
54
55 /**
56  * Private 32-bit recursive reduction using "SIMD Within A Register"
57  * (SWAR) to compute a base-2 integer logarithm for a given integer.
58  * This technique was taken from the University of Kentucky's
59  * Aggregate Magic Algorithms collection.
60  *
61  * LLVM 3.2 complains about a static inline function here, so use a macro instead
62  */
63 #define FLOOR_ILOG2(x) { \
64  x |= (x >> 1); \
65  x |= (x >> 2); \
66  x |= (x >> 4); \
67  x |= (x >> 8); \
68  x |= (x >> 16); \
69  x >>= 1; \
70  COUNT_ONES32(x) \
71 }
72
73
74 /**
75  * Wrap the above private routines for computing the bitv shift size.
76  * Users should not call this directly, instead calling the
78  */
79 inline size_t
81 {
82  size_t x = sizeof(bitv_t) * BITS_PER_BYTE;
83
84  FLOOR_ILOG2(x);
85
86  return x;
87 }
88
89
90 struct bu_bitv *
92 {
93  struct bu_bitv *bv;
94  size_t bv_bytes;
95  size_t total_bytes;
96
97  bv_bytes = BU_BITS2BYTES(nbits);
98  total_bytes = sizeof(struct bu_bitv) - 2*sizeof(bitv_t) + bv_bytes;
99
100  /* allocate bigger than struct, bits array extends past the end */
101  bv = (struct bu_bitv *)bu_malloc(total_bytes, "struct bu_bitv");
102
103  /* manually initialize */
105  bv->nbits = bv_bytes * BITS_PER_BYTE;
106  BU_BITV_ZEROALL(bv);
107
108  return bv;
109 }
110
111
112 void
114 {
115  BU_CK_BITV(bv);
116
117  bv->l.forw = bv->l.back = BU_LIST_NULL; /* sanity */
118  bu_free((char *)bv, "struct bu_bitv");
119 }
120
121
122 void
124 {
125  BU_CK_BITV(bv);
126
127  BU_BITV_ZEROALL(bv);
128 }
129
130
131 void
132 bu_bitv_or(struct bu_bitv *ov, const struct bu_bitv *iv)
133 {
134  register bitv_t *out;
135  register const bitv_t *in;
136  register size_t words;
137
138  if (UNLIKELY(ov->nbits != iv->nbits))
139  bu_bomb("bu_bitv_or: length mis-match");
140
141  out = ov->bits;
142  in = iv->bits;
143  words = BU_BITS2WORDS(iv->nbits);
144 #ifdef VECTORIZE
145  for (--words; words >= 0; words--)
146  out[words] |= in[words];
147 #else
148  while (words-- > 0)
149  *out++ |= *in++;
150 #endif
151 }
152
153
154 void
155 bu_bitv_and(struct bu_bitv *ov, const struct bu_bitv *iv)
156 {
157  register bitv_t *out;
158  register const bitv_t *in;
159  register size_t words;
160
161  if (UNLIKELY(ov->nbits != iv->nbits))
162  bu_bomb("bu_bitv_and: length mis-match");
163
164  out = ov->bits;
165  in = iv->bits;
166  words = BU_BITS2WORDS(iv->nbits);
167 #ifdef VECTORIZE
168  for (--words; words >= 0; words--)
169  out[words] &= in[words];
170 #else
171  while (words-- > 0)
172  *out++ &= *in++;
173 #endif
174 }
175
176
177 void
178 bu_bitv_vls(struct bu_vls *v, register const struct bu_bitv *bv)
179 {
180  int seen = 0;
181  register size_t i;
182  size_t len;
183
184  BU_CK_VLS(v);
185  BU_CK_BITV(bv);
186
187  len = bv->nbits;
188
189  bu_vls_strcat(v, "(");
190
191  /* Visit all the bits in ascending order */
192  for (i = 0; i < len; i++) {
193  if (BU_BITTEST(bv, i) == 0)
194  continue;
195  if (seen)
196  bu_vls_strcat(v, ", ");
197  bu_vls_printf(v, "%lu", i);
198  seen = 1;
199  }
200  bu_vls_strcat(v, ")");
201 }
202
203
204 void
205 bu_pr_bitv(const char *str, register const struct bu_bitv *bv)
206 {
207  struct bu_vls v = BU_VLS_INIT_ZERO;
208
209  BU_CK_BITV(bv);
210
211  if (str) {
212  bu_vls_strcat(&v, str);
213  bu_vls_strcat(&v, ": ");
214  }
215  bu_bitv_vls(&v, bv);
217  bu_vls_free(&v);
218 }
219
220
221 void
222 bu_bitv_to_hex(struct bu_vls *v, const struct bu_bitv *bv)
223 {
224  size_t word_count = 0;
225  size_t chunksize = 0;
226  /* necessarily volatile to keep the compiler from complaining
227  * about unreachable code during optimization.
228  */
229  volatile size_t BVS = sizeof(bitv_t);
230
231  BU_CK_VLS(v);
232  BU_CK_BITV(bv);
233
234  word_count = bv->nbits / BITS_PER_BYTE / BVS;
235  bu_vls_extend(v, word_count * BVS * 2 + 1);
236
237  while (word_count--) {
238  chunksize = BVS;
239  while (chunksize--) {
240  unsigned long val = (unsigned long)((bv->bits[word_count] & ((bitv_t)(0xff)<<(chunksize * BITS_PER_BYTE))) >> (chunksize * BITS_PER_BYTE)) & (bitv_t)0xff;
241  bu_vls_printf(v, "%02lx", val);
242  }
243  }
244 }
245
246
247 struct bu_bitv *
248 bu_hex_to_bitv(const char *str)
249 {
250  char abyte[3];
251  const char *str_start;
252  unsigned int len = 0;
253  int bytes;
254  struct bu_bitv *bv;
255  size_t word_count;
256  size_t chunksize = 0;
257  volatile size_t BVS = sizeof(bitv_t);
258
259  abyte[2] = '\0';
260
261  /* skip over any initial white space */
262  while (isspace((int)(*str)))
263  str++;
264
265  str_start = str;
266  /* count hex digits */
267  while (isxdigit((int)(*str)))
268  str++;
269
270  len = str - str_start;
271
272  if (len < 2 || len % 2) {
273  /* Must be two digits per byte */
274  bu_log("ERROR: bitv length is not a multiple of two.\nIllegal hex bitv: [%s]\n", str_start);
275  return (struct bu_bitv *)NULL;
276  }
277
278  bytes = len / 2; /* two hex digits per byte */
279  word_count = bytes / BVS;
280  chunksize = bytes % BVS;
281  if (chunksize == 0) {
282  chunksize = BVS;
283  } else {
284  /* handle partial chunk before using chunksize == BVS */
285  word_count++;
286  }
287
288  bv = bu_bitv_new(len * 4); /* 4 bits per hex digit */
289
290  str = str_start;
291  while (word_count--) {
292  while (chunksize--) {
293  unsigned long ulval;
294  /* prepare for error checking the next conversion */
295  char *endptr;
296  errno = 0;
297
298  /* get next two hex digits from string */
299  abyte[0] = *str++;
300  abyte[1] = *str++;
301
302  /* convert into an unsigned long */
303  ulval = strtoul(abyte, &endptr, 16);
304
305  /* check for various errors (from 'man strol') */
306  if ((errno == ERANGE && (ulval == ULONG_MAX))
307  || (errno != 0 && ulval == 0)) {
308  bu_log("ERROR: strtoul: %s\n", strerror(errno));
309  bu_bitv_free(bv);
310  bv = (struct bu_bitv *)NULL;
311  goto ERROR_RETURN;
312  }
313  if (endptr == abyte) {
314  bu_log("ERROR: no digits were found in '%s'\n", abyte);
315  bu_bitv_free(bv);
316  bv = (struct bu_bitv *)NULL;
317  goto ERROR_RETURN;
318  }
319  /* parsing was successful */
320
321  /* set the appropriate bits in the bit vector */
322  bv->bits[word_count] |= (bitv_t)ulval<<(chunksize * BITS_PER_BYTE);
323  }
324  chunksize = BVS;
325  }
326
327 ERROR_RETURN:
328
329  return bv;
330 }
331
332
333 struct bu_bitv *
334 bu_bitv_dup(register const struct bu_bitv *bv)
335 {
336  struct bu_bitv *bv2;
337
338  if (!bv)
339  return bu_bitv_new(0);
340
341  bv2 = bu_bitv_new(bv->nbits);
342  bu_bitv_or(bv2, bv);
343
344  return bv2;
345 }
346
347
348 void
349 bu_bitv_to_binary(struct bu_vls *v, const struct bu_bitv *bv)
350 {
351  int i;
352  size_t len;
353
354  BU_CK_VLS(v);
355  BU_CK_BITV(bv);
356
357  len = bv->nbits;
358
359  /* clear incoming vls, then extend to ensure enough room */
360  bu_vls_trunc(v, 0);
361  bu_vls_extend(v, len);
362
363  /* we use the GCC binary format: '0bnnnnn..." */
364  bu_vls_strcat(v, "0b");
365
366  /* Visit all the bits from left (len - 1) to right (0) */
367  for (i = (int)len - 1; i >= 0; --i) {
368  if (!BU_BITTEST(bv, i))
369  bu_vls_strcat(v, "0");
370  else
371  bu_vls_strcat(v, "1");
372  }
373 }
374
375
376 struct bu_bitv *
377 bu_binary_to_bitv(const char *str)
378 {
379  /* The incoming binary string is expected to be in the GCC format:
380  * "0b<1 or more binary digits>'" (and it may have leading and
381  * trailing spaces). The input bit length will be increased to a
382  * multiple of eight if necessary when converting to a bitv_t.
383  *
384  * Example 1: " 0b00110100 " ('b' may be 'B' if desired)
385  *
386  * Note that only the zeroes and ones are actually tested and any
387  * other character will ignored. So one can ease producing the
388  * binary input string by using spaces or other characters to
389  * group the bits as shown in Examples 2, 3, and 4:
390  *
391  * Example 2: " 0b 0011 0100 "
392  *
393  * Example 3: " 0b_0011_0100 "
394  *
395  * Example 4: " 0b|0011|0100 "
396  *
397  * Note also that an empty input ('0b') results in a valid but
398  * zero-value bitv.
399  *
400  */
401  return bu_binary_to_bitv2(str, 0);
402 }
403
404
405 struct bu_bitv *
406 bu_binary_to_bitv2(const char *str, const int nbytes)
407 {
408  /* The incoming binary string is expected to be in the GCC format:
409  * "0b<1 or more binary digits>'" (and it may have leading and
410  * trailing spaces). The input bit length will be increased to a
411  * multiple of eight if necessary when converting to a bitv_t.
412  * The "nbytes" argument may be zero if the user has no minimum
413  * length preference.
414  *
415  * Example 1: " 0b00110100 " ('b' may be 'B' if desired)
416  *
417  * Note that only the zeroes and ones are actually tested and any
418  * other character will ignored. So one can ease producing the
419  * binary input string by using spaces or other characters
420  * to group the bits as shown in Examples 2, 3, and 4:
421  *
422  * Example 2: " 0b 0011 0100 "
423  *
424  * Example 3: " 0b_0011_0100 "
425  *
426  * Example 4: " 0b|0011|0100 "
427  *
428  * Note also that an empty input ('0b') results in a valid but
429  * zero-value bitv.
430  *
431  */
432  struct bu_vls v = BU_VLS_INIT_ZERO;
433  struct bu_vls v2 = BU_VLS_INIT_ZERO;
434  unsigned nbits = nbytes > 0 ? nbytes * BITS_PER_BYTE : 0;
435  size_t i, j, vlen, new_vlen, len = 0;
436  int err = 0;
437  struct bu_bitv *bv;
438  char abyte[9];
439  size_t word_count;
440  size_t chunksize = 0;
441  volatile size_t BVS = sizeof(bitv_t); /* should be 1 byte as defined in bu/bitv.h */
442  unsigned bytes;
443
444  /* copy the input string and remove leading and trailing white space */
445  bu_vls_strcpy(&v, str);
446  bu_vls_trimspace(&v);
447
448  /* check first two chars (and remove them) */
449  if (*bu_vls_cstr(&v) != '0')
450  ++err;
451  bu_vls_nibble(&v, 1);
452
453  if (*bu_vls_cstr(&v) != 'b' && *bu_vls_cstr(&v) != 'B')
454  ++err;
455  bu_vls_nibble(&v, 1);
456
457  /* close up any embedded non-zero or non-one spaces */
458  bu_vls_extend(&v2, nbits ? 2 * nbits : 2 * bu_vls_strlen(&v));
459  bu_vls_trunc(&v2, 0);
460  for (i = 0; i < bu_vls_strlen(&v); ++i) {
461  const char c = bu_vls_cstr(&v)[i];
462  if (c != '0' && c != '1')
463  continue;
464  bu_vls_printf(&v2, "%c", c);
465  }
466
467  if (err)
468  bu_exit(1, "Incorrect binary format '%s' (should be '0b<binary digits>').\n", str);
469
470  /* zero-length input is okay, but we always need to add leading
471  * zeroes to get a bit-length which is a multiple of eight
472  */
473  vlen = bu_vls_strlen(&v2);
474  new_vlen = nbits > vlen ? nbits : vlen;
475  if (new_vlen < BITS_PER_BYTE) {
476  new_vlen = BITS_PER_BYTE;
477  }
478  else if (new_vlen % BITS_PER_BYTE) {
479  new_vlen = (new_vlen / BITS_PER_BYTE) * BITS_PER_BYTE + BITS_PER_BYTE;
480  }
481
482  if (new_vlen > vlen) {
483  size_t needed_zeroes = new_vlen - vlen;
484  for (i = 0; i < needed_zeroes; ++i) {
485  bu_vls_prepend(&v2, "0");
486  }
487  vlen = new_vlen;
488  }
489
490  len = vlen;
491  bv = bu_bitv_new(len); /* note it is initialized to all zeroes */
492  BU_CK_BITV(bv);
493
494  /* note the final length of the bitv may be greater due to word sizes, etc. */
495
496  abyte[8] = '\0';
497  bytes = len / BITS_PER_BYTE; /* eight digits per byte */
498  word_count = bytes / BVS;
499  chunksize = bytes % BVS;
500
501  if (chunksize == 0) {
502  chunksize = BVS;
503  } else {
504  /* handle partial chunk before using chunksize == BVS */
505  word_count++;
506  }
507
508  j = 0;
509  while (word_count--) {
510  while (chunksize--) {
511  unsigned long ulval;
512  /* prepare for error checking the next conversion */
513  char *endptr;
514  errno = 0;
515
516  /* get next eight binary digits from string */
517  for (i = 0; i < BITS_PER_BYTE; ++i) {
518  abyte[i] = bu_vls_cstr(&v2)[j++];
519  }
520
521  /* convert into an unsigned long */
522  ulval = strtoul(abyte, (char **)&endptr, 2);
523
524  /* check for various errors (from 'man strol') */
525  if ((errno == ERANGE && (ulval == ULONG_MAX))
526  || (errno != 0 && ulval == 0)) {
527  bu_log("ERROR: strtoul: %s\n", strerror(errno));
528  bu_bitv_free(bv);
529  bv = (struct bu_bitv *)NULL;
530  goto ERROR_RETURN;
531  }
532  if (endptr == abyte) {
533  bu_log("ERROR: no digits were found in '%s'\n", abyte);
534  bu_bitv_free(bv);
535  bv = (struct bu_bitv *)NULL;
536  goto ERROR_RETURN;
537  }
538  /* parsing was successful */
539
540  /* set the appropriate bits in the bit vector */
541  bv->bits[word_count] |= (bitv_t)ulval << (chunksize * BITS_PER_BYTE);
542  }
543  chunksize = BVS;
544  }
545
546 ERROR_RETURN:
547
548  bu_vls_free(&v);
549  bu_vls_free(&v2);
550
551  return bv;
552 }
553
554
555 int
556 bu_bitv_compare_equal(const struct bu_bitv *bv1, const struct bu_bitv *bv2)
557 {
558  /* Returns 1 (true) iff lengths are the same and each bit is
559  * identical, 0 (false) otherwise.
560  */
561  int i;
562
563  BU_CK_BITV(bv1);
564  BU_CK_BITV(bv2);
565
566  if (bv1->nbits != bv2->nbits)
567  return 0;
568
569  for (i = 0; i < (int)bv1->nbits; ++i) {
570  int i1 = BU_BITTEST(bv1, i) ? 1 : 0;
571  int i2 = BU_BITTEST(bv2, i) ? 1 : 0;
572  if (i1 != i2)
573  return 0;
574  }
575
576  return 1;
577 }
578
579
580 int
581 bu_bitv_compare_equal2(const struct bu_bitv *bv1, const struct bu_bitv *bv2)
582 {
583  /* Returns 1 (true) iff each non-zero bit is identical, 0 (false) otherwise. */
584  BU_CK_BITV(bv1);
585  BU_CK_BITV(bv2);
586
587  if (bv1->nbits > bv2->nbits) {
588  int i, j;
589  int maxlen = (int)bv1->nbits;
590  int minlen = (int)bv2->nbits;
591  for (i = 0; i < minlen; ++i) {
592  int i1 = BU_BITTEST(bv1, i) ? 1 : 0;
593  int i2 = BU_BITTEST(bv2, i) ? 1 : 0;
594  if (i1 != i2)
595  return 0;
596  }
597  /* remainder of bv1 bits must be zero */
598  for (j = i; j < maxlen; ++j) {
599  int i1 = BU_BITTEST(bv1, j) ? 1 : 0;
600  if (i1)
601  return 0;
602  }
603  } else if (bv2->nbits > bv1->nbits) {
604  int i, j;
605  int maxlen = (int)bv2->nbits;
606  int minlen = (int)bv1->nbits;
607  for (i = 0; i < minlen; ++i) {
608  int i1 = BU_BITTEST(bv1, i) ? 1 : 0;
609  int i2 = BU_BITTEST(bv2, i) ? 1 : 0;
610  if (i1 != i2)
611  return 0;
612  }
613  /* remainder of bv2 bits must be zero */
614  for (j = i; j < maxlen; ++j) {
615  int i1 = BU_BITTEST(bv2, j) ? 1 : 0;
616  if (i1)
617  return 0;
618  }
619  } else {
620  /* equal nbits */
621  int i;
622  int len = (int)bv1->nbits;
623  for (i = 0; i < len; ++i) {
624  int i1 = BU_BITTEST(bv1, i) ? 1 : 0;
625  int i2 = BU_BITTEST(bv2, i) ? 1 : 0;
626  if (i1 != i2)
627  return 0;
628  }
629  }
630
631  return 1;
632 }
633
634
635 int
636 bu_binstr_to_hexstr(const char *bstr, struct bu_vls *h)
637 {
638  struct bu_vls b = BU_VLS_INIT_ZERO;
639  struct bu_vls tmp = BU_VLS_INIT_ZERO;
640  size_t len;
641  size_t i;
642  char abyte[BITS_PER_BYTE + 1];
643  int have_prefix = 0;
645
646  if (!bstr) {
647  bu_log("ERROR: NULL 'bstr'\n");
649  goto ERROR_RETURN;
650  }
651  if (!h) {
652  bu_log("ERROR: NULL 'h'\n");
654  goto ERROR_RETURN;
655  }
656
657  bu_vls_strcpy(&b, bstr);
658  bu_vls_trimspace(&b);
659  len = bu_vls_strlen(&b);
660
661  /* check for '0b' or '0B' */
662  if (bu_vls_cstr(&b)[0] == '0' && len >= 2) {
663  const char c1 = bu_vls_cstr(&b)[1];
664  if (c1 == 'b' || c1 == 'B') {
665  have_prefix = 1;
666  bu_vls_nibble(&b, 2);
667  len = bu_vls_strlen(&b);
668  }
669  }
670
671  /* eliminate non-binary characters used for user-spacing */
672  bu_vls_vlscatzap(&tmp, &b);
673  for (i = 0; i < len; ++i) {
674  const char c = bu_vls_cstr(&tmp)[i];
675  if (c == '0' || c == '1')
676  bu_vls_putc(&b, c);
677  }
678  len = bu_vls_strlen(&b);
679
680  /* check valid length, pad with leading zeroes if necessary to get
681  * an integral number of bytes */
682  if (len < BITS_PER_BYTE || len % BITS_PER_BYTE) {
684  bu_log("WARNING: Incoming string length (%zu) not an integral number of bytes,\n", len);
686  if (len < BITS_PER_BYTE)
687  new_len = BITS_PER_BYTE;
688  else
689  new_len = (len/BITS_PER_BYTE) * BITS_PER_BYTE + BITS_PER_BYTE;
690  leading_zeroes = new_len - len;
691  for (i = 0; i < leading_zeroes; ++i)
692  bu_vls_prepend(&b, "0");
693  len = bu_vls_strlen(&b);
694  }
695
696  abyte[BITS_PER_BYTE] = '\0';
697
698  bu_vls_trunc(h, 0);
699  bu_vls_extend(h, len);
700  for (i = 0; i < len; /* i is incremented inside first loop below */) {
701  int j, k = BITS_PER_HEXCHAR;
702  unsigned long ulval;
703  /* prepare for error checking the next conversion */
704  char *endptr;
705  errno = 0;
706
707  /* get next eight binary digits (one byte) from string; note i
708  * is incremented here */
709  for (j = 0; j < BITS_PER_BYTE; ++j) {
710  abyte[j] = bu_vls_cstr(&b)[i++];
711  }
712
713  /* convert into an unsigned long */
714  ulval = strtoul(abyte, (char **)&endptr, BINARY_BASE);
715 #if 0
716  bu_log("DEBUG: abyte: '%s'; ulval: 0x%08x\n", abyte, ulval);
717 #endif
718
719  /* check for various errors (from 'man strol') */
720  if ((errno == ERANGE && (ulval == ULONG_MAX))
721  || (errno != 0 && ulval == 0)) {
722  bu_log("ERROR: strtoul: %s\n", strerror(errno));
724  goto ERROR_RETURN;
725  }
726  if (endptr == abyte) {
727  bu_log("ERROR: no digits were found in '%s'\n", abyte);
729  goto ERROR_RETURN;
730  }
731  /* parsing was successful */
732
733  for (j = 0; j < HEXCHARS_PER_BYTE; ++j, k -= BITS_PER_HEXCHAR)
734  bu_vls_printf(h, "%1lx", (ulval >> k) & 0xf);
735  }
736  bu_vls_putc(h, '\0');
737
738  if (have_prefix)
739  bu_vls_prepend(h, "0x");
740
741 ERROR_RETURN:
742
743  bu_vls_free(&b);
744  bu_vls_free(&tmp);
745
746  return results;
747 }
748
749
750 int
751 bu_hexstr_to_binstr(const char *hstr, struct bu_vls *b)
752 {
753  struct bu_vls h = BU_VLS_INIT_ZERO;
754  struct bu_vls tmp = BU_VLS_INIT_ZERO;
755  size_t len;
756  size_t i;
757  char abyte[HEXCHARS_PER_BYTE + 1];
758  int have_prefix = 0;
760
761  if (!hstr) {
762  bu_log("ERROR: NULL 'hstr'\n");
764  goto ERROR_RETURN;
765  }
766  if (!b) {
767  bu_log("ERROR: NULL 'b'\n");
769  goto ERROR_RETURN;
770  }
771
772  bu_vls_strcpy(&h, hstr);
773  bu_vls_trimspace(&h);
774  len = bu_vls_strlen(&h);
775
776  /* check for '0x' or '0X' */
777  if (bu_vls_cstr(&h)[0] == '0' && len >= 2) {
778  const char c1 = bu_vls_cstr(&h)[1];
779  if (c1 == 'x' || c1 == 'X') {
780  have_prefix = 1;
781  bu_vls_nibble(&h, 2);
782  len = bu_vls_strlen(&h);
783  }
784  }
785
786  /* eliminate non-hex characters used for user-spacing */
787  bu_vls_vlscatzap(&tmp, &h);
788  for (i = 0; i < len; ++i) {
789  const unsigned char c = bu_vls_cstr(&tmp)[i];
790  if (isxdigit(c))
791  bu_vls_putc(&h, c);
792  }
793  len = bu_vls_strlen(&h);
794
795  /* check valid length, pad with leading zeroes if necessary to get
796  * an integral number of bytes */
797  if (len < HEXCHARS_PER_BYTE || len % HEXCHARS_PER_BYTE) {
799  bu_log("WARNING: Incoming string length (%zu) not an integral number of bytes,\n", len);
801  if (len < HEXCHARS_PER_BYTE)
802  new_len = HEXCHARS_PER_BYTE;
803  else
804  new_len = (len/HEXCHARS_PER_BYTE) * HEXCHARS_PER_BYTE + HEXCHARS_PER_BYTE;
805  leading_zeroes = new_len - len;
806  for (i = 0; i < leading_zeroes; ++i)
807  bu_vls_prepend(&h, "0");
808  len = bu_vls_strlen(&h);
809  }
810
811  abyte[HEXCHARS_PER_BYTE] = '\0';
812
813  bu_vls_trunc(b, 0);
814  bu_vls_extend(b, len * BITS_PER_HEXCHAR + (have_prefix ? 2 : 0));
815  for (i = 0; i < len; /* i is incremented inside first loop below */) {
816  size_t j, k = BITS_PER_BYTE;
817  unsigned long ulval;
818  /* prepare for error checking the next conversion */
819  char *endptr;
820  errno = 0;
821
822  /* get next two hex digits (one byte) from string; note i is
823  * incremented here */
824  for (j = 0; j < HEXCHARS_PER_BYTE; ++j) {
825  abyte[j] = bu_vls_cstr(&h)[i++];
826  }
827
828  /* convert into an unsigned long */
829  ulval = strtoul(abyte, (char **)&endptr, HEX_BASE);
830 #if 0
831  bu_log("DEBUG: abyte: '%s'; ulval: 0x%08x\n", abyte, ulval);
832 #endif
833
834  /* check for various errors (from 'man strol') */
835  if ((errno == ERANGE && (ulval == ULONG_MAX))
836  || (errno != 0 && ulval == 0)) {
837  bu_log("ERROR: strtoul: %s\n", strerror(errno));
839  goto ERROR_RETURN;
840  }
841  if (endptr == abyte) {
842  bu_log("ERROR: no digits were found in '%s'\n", abyte);
844  goto ERROR_RETURN;
845  }
846  /* parsing was successful */
847
848  for (j = 0; j < BITS_PER_BYTE; ++j)
849  bu_vls_printf(b, "%1lx", (ulval >> --k) & 0x00000001);
850  }
851  bu_vls_putc(b, '\0');
852
853  if (have_prefix)
854  bu_vls_prepend(b, "0b");
855
856 ERROR_RETURN:
857
858  bu_vls_free(&h);
859  bu_vls_free(&tmp);
860
861  return results;
862
863 }
864
865
866 /*
867  * Local Variables:
868  * mode: C
869  * tab-width: 8
870  * indent-tabs-mode: t
871  * c-file-style: "stroustrup"
872  * End:
873  * ex: shiftwidth=4 tabstop=8
874  */
Definition: db_flip.c:35
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
void bu_log(const char *,...) _BU_ATTR_PRINTF12
Definition: log.c:176
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
struct bu_bitv * bu_binary_to_bitv2(const char *str, const int nbytes)
Definition: bitv.c:406
void bu_vls_strcat(struct bu_vls *vp, const char *s)
Definition: vls.c:368
size_t nbits
Definition: bitv.h:107
void bu_vls_trunc(struct bu_vls *vp, int len)
Definition: vls.c:198
void bu_vls_nibble(struct bu_vls *vp, off_t len)
Definition: vls.c:217
int bu_hexstr_to_binstr(const char *hstr, struct bu_vls *b)
Definition: bitv.c:751
int bu_bitv_compare_equal(const struct bu_bitv *bv1, const struct bu_bitv *bv2)
Definition: bitv.c:556
void * bu_malloc(size_t siz, const char *str)
Definition: malloc.c:314
#define FLOOR_ILOG2(x)
Definition: bitv.c:63
void bu_vls_free(struct bu_vls *vp)
Definition: vls.c:248
#define BU_CK_VLS(_vp)
Definition: vls.h:69
#define BU_BITV_MAGIC
Definition: magic.h:47
void bu_exit(int status, const char *fmt,...) _BU_ATTR_NORETURN _BU_ATTR_PRINTF23
Definition: bomb.c:195
#define BU_BITTEST(_bv, bit)
Definition: bitv.h:168
struct bu_list l
Definition: bitv.h:106
void bu_bitv_or(struct bu_bitv *ov, const struct bu_bitv *iv)
Definition: bitv.c:132
struct bu_bitv * bu_bitv_dup(register const struct bu_bitv *bv)
Definition: bitv.c:334
Definition: defines.h:71
struct bu_list * back
"back", "last"
Definition: list.h:121
#define BU_LIST_INIT_MAGIC(_hp, _magic)
Definition: list.h:156
size_t bu_bitv_shift(void)
Definition: bitv.c:80
void bu_bitv_vls(struct bu_vls *v, register const struct bu_bitv *bv)
Definition: bitv.c:178
size_t bu_vls_strlen(const struct bu_vls *vp)
Definition: vls.c:189
#define HEXCHARS_PER_BYTE
Definition: bu_internals.h:31
goto out
Definition: nmg_mod.c:3846
const char * bu_vls_cstr(const struct bu_vls *vp)
Definition: vls.c:103
char * bu_vls_addr(const struct bu_vls *vp)
Definition: vls.c:111
#define BU_BITV_ZEROALL(_bv)
Definition: bitv.h:191
#define BINARY_BASE
Definition: bu_internals.h:33
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 *bstr, struct bu_vls *h)
Definition: bitv.c:636
#define BU_BITS2BYTES(_nb)
Definition: bitv.h:164
void bu_pr_bitv(const char *str, register const struct bu_bitv *bv)
Definition: bitv.c:205
void bu_bitv_to_binary(struct bu_vls *v, const struct bu_bitv *bv)
Definition: bitv.c:349
void bu_vls_printf(struct bu_vls *vls, const char *fmt,...) _BU_ATTR_PRINTF23
Definition: vls.c:694
#define BU_BITS2WORDS(_nb)
Definition: bitv.h:158
void bu_vls_extend(struct bu_vls *vp, size_t extra)
Definition: vls.c:136
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
void bu_vls_trimspace(struct bu_vls *vp)
Definition: vls.c:678
#define BU_LIST_NULL
Definition: list.h:124
#define HEX_BASE
Definition: bu_internals.h:32
void bu_vls_strcpy(struct bu_vls *vp, const char *s)
Definition: vls.c:310
void bu_free(void *ptr, const char *str)
Definition: malloc.c:328
#define BU_VLS_INIT_ZERO
Definition: vls.h:84
int bu_bitv_compare_equal2(const struct bu_bitv *bv1, const struct bu_bitv *bv2)
Definition: bitv.c:581
struct bu_list * forw
"forward", "next"
Definition: list.h:120
void bu_vls_prepend(struct bu_vls *vp, char *str)
Definition: vls.c:796
Definition: bitv.h:105
#define BITS_PER_BYTE
Definition: bu_internals.h:29
Definition: vls.h:56
Definition: defines.h:72
void bu_bomb(const char *str) _BU_ATTR_NORETURN
Definition: bomb.c:91
#define BITS_PER_HEXCHAR
Definition: bu_internals.h:30
struct bu_bitv * bu_hex_to_bitv(const char *str)
Definition: bitv.c:248
#define BU_CK_BITV(_bp)
Definition: bitv.h:116
void bu_vls_putc(struct bu_vls *vp, int c)
Definition: vls.c:666
void bu_vls_vlscatzap(struct bu_vls *dest, struct bu_vls *src)
Definition: vls.c:433
#define UNLIKELY(expression)
Definition: common.h:282