bitstring.h File Reference

#include <assert.h>
#include <stddef.h>
#include "base/intutils.h"
#include "debug/utils.h"

Go to the source code of this file.

Namespaces
namespace	base
Enumerations
enum	bit_t { ZERO = 0, ONE = 1 }
	Type to ensure correct arguments. More...
Functions
static uint32_t	base_high16 (uint32_t x)
	High 16 bits of an int.
static uint32_t	base_low16 (uint32_t x)
	Low 16 bits of an int.
static uint32_t	base_countBits (uint32_t x)
	Bit counting function.
static uint32_t	base_countBitsN (const uint32_t *bitString, size_t n)
	Bit counting function.
static uint32_t	base_fmsb32 (uint32_t w)
	Find most significant set bit (32-bit version).
static void	base_orBits (uint32_t *bits1, const uint32_t *bits2, size_t n)
	Bitwise or ;.
static void	base_andBits (uint32_t *bits1, const uint32_t *bits2, size_t n)
	Bitwise and ;.
static void	base_xorBits (uint32_t *bits1, const uint32_t *bits2, size_t n)
	Bitwise xor ;.
static void	base_resetBits (uint32_t *bits, size_t n)
	Reset of bits (to 0).
static void	base_setBits (uint32_t *bits, size_t n)
	Set bits to 1.
static void	base_setBitsWith (uint32_t *bits, size_t n, uint32_t value)
	Set bits to something.
static void	base_xorBitsWith (uint32_t *bits, size_t n, uint32_t mask)
	Apply a xor mask to a bitstring.
static void	base_negBits (uint32_t *bits, size_t n)
	Negate a bitstring.
static void	base_resetBits2 (uint32_t *bits1, uint32_t *bits2, size_t n)
	Reset of 2 strings of bits (to 0).
static void	base_setBits2 (uint32_t *bits1, uint32_t *bits2, size_t n)
	Set 2 strings of bits (to 1).
static BOOL	base_areBitsReset (const uint32_t *bits, size_t n)
	Equality test to 0.
static BOOL	base_areIBitsReset (const int32_t *bits, size_t n)
	Wrapper to base_areBitsResets.
static BOOL	base_areBitsEqual (const uint32_t *bits1, const uint32_t *bits2, size_t n)
	Comparison of bits.
static void	base_copyBits (uint32_t *bits1, const uint32_t *bits2, size_t n)
	Copy of bits.
static void	base_setOneBit (uint32_t *bits, size_t i)
	Set bit to 1 at position i in a table of bits.
static void	base_addOneBit (uint32_t *bits, size_t i, bit_t bit)
	Add a bit at position i in a table of bits.
static void	base_assignOneBit (uint32_t *bits, size_t i, bit_t bit)
	Assign a bit at position i in a table of bits.
static void	base_andWithOneBit (uint32_t *bits, size_t i, bit_t bit)
	"and" operation with a bit at position i in a table of bits.
static void	base_resetOneBit (uint32_t *bits, size_t i)
	Reset bit to 0 at position i in a table of bits.
static void	base_subOneBit (uint32_t *bits, size_t i, bit_t bit)
	Substract a bit at position i in a table of bits.
static void	base_toggleOneBit (uint32_t *bits, size_t i)
	Toggle bit at position i in a table of bits.
static void	base_xorOneBit (uint32_t *bits, size_t i, bit_t bit)
	Xor a bit at position i in a table of bits.
static bit_t	base_getOneBit (const uint32_t *bits, size_t i)
	Test for a set bit in a bit-string.
static uint32_t	base_readOneBit (const uint32_t *bits, size_t i)
	Test for a set bit in a bit-string.
size_t	base_bits2indexTable (const uint32_t *bits, size_t n, cindex_t *table)
	Unpack a bit table to an index table.
static std::ostream &	operator<< (std::ostream &os, const BitString &bs)
static std::ostream &	operator<< (std::ostream &os, const Bit &b)

---

Enumeration Type Documentation

enum bit_t

Type to ensure correct arguments. Enumeration values: ZERO  ONE

---

Function Documentation

static void base_addOneBit (  uint32_t *  bits, size_t  i, bit_t  bit )  [inline, static]

Add a bit at position i in a table of bits. Parameters: bits,:  the table of *int* i,:  the position of the bit bit,:  the bit to add (0 or 1) Precondition: valid pointer and no out of bounds.

static void base_andBits (  uint32_t *  bits1, const uint32_t *  bits2, size_t  n )  [inline, static]

Bitwise and ;. Parameters: bits1,:  arg1 = destination bits2,:  arg2 = source n,:  number of ints to read Returns: arg1 = arg1 & arg2

static void base_andWithOneBit (  uint32_t *  bits, size_t  i, bit_t  bit )  [inline, static]

"and" operation with a bit at position i in a table of bits. Parameters: bits,:  the table of *int* i,:  the position of the bit Bit position in a table of int = int position at i/32 == i >> 5 bit position at i32 == i & 31 Precondition: valid pointer and no out of bounds.

static BOOL base_areBitsEqual (  const uint32_t *  bits1, const uint32_t *  bits2, size_t  n )  [inline, static]

Comparison of bits. Same comment as for resetBits: better to inline this simple code for small arrays, ie, bit arrays. Optimistic implementation. Parameters: bits1,bits2,:  arrays to compare n,:  number of ints to read Returns: TRUE if array contents are the same

static BOOL base_areBitsReset (  const uint32_t *  bits, size_t  n )  [inline, static]

Equality test to 0. Optimistic implementation: works best when == 0. Parameters: bits,:  the string to test n,:  n number of ints to test Returns: true if all bits[0..n-1] == 0

static BOOL base_areIBitsReset (  const int32_t *  bits, size_t  n )  [inline, static]

Wrapper to base_areBitsResets.

static void base_assignOneBit (  uint32_t *  bits, size_t  i, bit_t  bit )  [inline, static]

Assign a bit at position i in a table of bits. Parameters: bits,:  the table of *int* i,:  the position of the bit bit,:  the bit to assign. Precondition: valid pointer and no out of bounds.

size_t base_bits2indexTable (  const uint32_t *  bits, size_t  n, cindex_t *  table )

Unpack a bit table to an index table. Useful when loading a DBM and computing initial redirection table. May be used for other things than DBMs, e.g., variables. Parameters: table,:  index redirection table bits,:  bit array n,:  size in int of the bit array Returns: number of bits in bits Precondition: table is large enough: at least uint32_t[size] where size = index of the highest bit in the bitstring bits. bits is at least a uint32_t[n] Postcondition: returned value == number of bits in bits for all bits set in bits at position i, then table[i] is defined and gives the proper indirection ; for other bits, table[i] is untouched.

static void base_copyBits (  uint32_t *  bits1, const uint32_t *  bits2, size_t  n )  [inline, static]

Copy of bits. memcpy could be used but for strings of bits of length 3-4 ints max, it is overkill. Conversely, for larger arrays, don't use this function. Parameters: bits,:  the string to reset n,:  number of ints to read. Precondition: n > 0 && valid pointer

static uint32_t base_countBits (  uint32_t  x  )  [inline, static]

Bit counting function. Returns: : the number of 1s in a given int Parameters: x,:  the int to examine.

static uint32_t base_countBitsN (  const uint32_t *  bitString, size_t  n )  [inline, static]

Bit counting function. Returns: : the number of 1s in a given string of bits Parameters: bitString,:  the string of bits to examine n,:  number of ints to read.

static uint32_t base_fmsb32 (  uint32_t  w  )  [inline, static]

Find most significant set bit (32-bit version). Function that scans a 32-bit word for the most significant set bit. For x86 this is implemented in assembler while for all other architectures it is implemented by setting all bits below the max significant set bit to 1 and counting the number of set bits. Parameters: w,:  the 32-bit word. Returns: The index (0--31) of the most significant set bit. Precondition: w != 0

static bit_t base_getOneBit (  const uint32_t *  bits, size_t  i )  [inline, static]

Test for a set bit in a bit-string. Can be used in the following way. Instead of: if (base_getOneBit(a,n)) c++; you can write: c += base_getOneBit(a,n); Returns: ONE if i'th bit is set, ZERO otherwise. Precondition: valid pointer and not out of bounds.

static uint32_t base_high16 (  uint32_t  x  )  [inline, static]

High 16 bits of an int. Useful in conjunction with hash values to store data. Parameters: x,:  the int to extract the high 16 bits.

static uint32_t base_low16 (  uint32_t  x  )  [inline, static]

Low 16 bits of an int. Useful in conjunction with hash values to store data. Parameters: x,:  the int extract the low 16 bits.

static void base_negBits (  uint32_t *  bits, size_t  n )  [inline, static]

Negate a bitstring. Parameters: bits,:  bit string to negate n,:  number of ints to change

static void base_orBits (  uint32_t *  bits1, const uint32_t *  bits2, size_t  n )  [inline, static]

Bitwise or ;. Parameters: bits1,:  arg1 = destination bits2,:  arg2 = source n,:  number of ints to read Returns: arg1 = arg1 | arg2

static uint32_t base_readOneBit (  const uint32_t *  bits, size_t  i )  [inline, static]

Test for a set bit in a bit-string. This function is not the same as base_getOneBit(). This function returns an integer with all other bits except the i'th bit masked out. I.e. it returns 0 if the bit is not set, and a power of 2 if it is set. Returns: the bit as it is in the int, ie, shifted. Precondition: valid pointer and not out of bounds.

static void base_resetBits (  uint32_t *  bits, size_t  n )  [inline, static]

Reset of bits (to 0). memset could be used but for strings of bits of length 3-4 ints max, it is overkill. Conversely, for larger arrays, don't use this function. Parameters: bits,:  the string to reset n,:  number of ints to write.

static void base_resetBits2 (  uint32_t *  bits1, uint32_t *  bits2, size_t  n )  [inline, static]

Reset of 2 strings of bits (to 0). memset could be used but for strings of bits of length 3-4 ints max, it is overkill. Conversely, for larger arrays, don't use this function. Parameters: bits1,bits2,:  the strings to reset n,:  number of ints to write.

static void base_resetOneBit (  uint32_t *  bits, size_t  i )  [inline, static]

Reset bit to 0 at position i in a table of bits. Parameters: bits,:  the table of *int* i,:  the position of the bit Bit position in a table of int = int position at i/32 == i >> 5 bit position at i32 == i & 31 NOTE: don't use setBit and resetBit as names because they are too close to resetBits that is already used. Precondition: valid pointer and not out of bounds.

static void base_setBits (  uint32_t *  bits, size_t  n )  [inline, static]

Set bits to 1. memset could be used but for strings of bits of length 3-4 ints max, it is overkill. Conversely, for larger arrays, don't use this function. Parameters: bits,:  the string to reset n,:  number of ints to write.

static void base_setBits2 (  uint32_t *  bits1, uint32_t *  bits2, size_t  n )  [inline, static]

Set 2 strings of bits (to 1). memset could be used but for strings of bits of length 3-4 ints max, it is overkill. Conversely, for larger arrays, don't use this function. Parameters: bits1,bits2,:  the strings to reset n,:  number of ints to write.

static void base_setBitsWith (  uint32_t *  bits, size_t  n, uint32_t  value )  [inline, static]

Set bits to something. memset could be used but for strings of bits of length 3-4 ints max, it is overkill. Conversely, for larger arrays, don't use this function. Parameters: bits,:  the string to reset n,:  number of ints to write. value,:  value to set.

static void base_setOneBit (  uint32_t *  bits, size_t  i )  [inline, static]

Set bit to 1 at position i in a table of bits. Parameters: bits,:  the table of *int* i,:  the position of the bit Bit position in a table of int = int position at i/32 == i >> 5 bit position at i32 == i & 31 NOTE: we don't use setBit and resetBit as names because they are too close to resetBits that is already used. Precondition: valid pointer and no out of bounds.

static void base_subOneBit (  uint32_t *  bits, size_t  i, bit_t  bit )  [inline, static]

Substract a bit at position i in a table of bits. Parameters: bits,:  the table of *int* i,:  the position of the bit Bit position in a table of int = int position at i/32 == i >> 5 bit position at i32 == i & 31 NOTE: don't use setBit and resetBit as names because they are too close to resetBits that is already used. Precondition: valid pointer and not out of bounds.

static void base_toggleOneBit (  uint32_t *  bits, size_t  i )  [inline, static]

Toggle bit at position i in a table of bits. Parameters: bits,:  the table of *int* i,:  the position of the bit Bit position in a table of int = int position at i/32 == i >> 5 bit position at i32 == i & 31 Precondition: valid pointer and not out of bounds.

static void base_xorBits (  uint32_t *  bits1, const uint32_t *  bits2, size_t  n )  [inline, static]

Bitwise xor ;. Parameters: bits1,:  arg1 = destination bits2,:  arg2 = source n,:  number of ints to read Returns: arg1 = arg1 ^ arg2

static void base_xorBitsWith (  uint32_t *  bits, size_t  n, uint32_t  mask )  [inline, static]

Apply a xor mask to a bitstring. Parameters: bits,:  the string to xor n,:  number of ints to change mask,:  the mask for the xor

static void base_xorOneBit (  uint32_t *  bits, size_t  i, bit_t  bit )  [inline, static]

Xor a bit at position i in a table of bits. Parameters: bits,:  the table of *int* i,:  the position of the bit Bit position in a table of int = int position at i/32 == i >> 5 bit position at i32 == i & 31 Precondition: valid pointer and not out of bounds.

static std::ostream& base::operator<< (  std::ostream &  os, const Bit &  b )  [inline, static]

static std::ostream& base::operator<< (  std::ostream &  os, const BitString &  bs )  [inline, static]

---