Harlequin RIP SDK

Macros implementing bit vectors. More...

Data Structures

struct  bitvector_iterator_t
 Iterator structure for walking bit vectors. More...
 

Macros

#define BITVECTOR_SHIFT_BYTES   3
 Right shift to convert bytes indices to element indices. More...
 
#define BITVECTOR_SHIFT_ELEMENTS   (BITVECTOR_SHIFT_BYTES + 3)
 Right shift to convert bit indices to element indices.
 
#define BITVECTOR_ELEMENT_BITS   (1u << BITVECTOR_SHIFT_ELEMENTS)
 Bit vector element size in bits.
 
#define BITVECTOR_ELEMENT_MASK   (BITVECTOR_ELEMENT_BITS - 1u)
 Mask to extract bit index within element from bit index.
 
#define BITVECTOR_ELEMENT_ZEROS   (bitvector_element_t)0
 Bitvector element containing all zeros.
 
#define BITVECTOR_ELEMENT_ONES   (bitvector_element_t)(~BITVECTOR_ELEMENT_ZEROS)
 Bitvector element containing all ones.
 
#define BITVECTOR_SIZE_ELEMENTS(length_)    (((length_) + BITVECTOR_ELEMENT_BITS - 1u) >> BITVECTOR_SHIFT_ELEMENTS)
 Size of a bitvector containing length_ bits, in elements. More...
 
#define BITVECTOR_SIZE_BYTES(length_)    (BITVECTOR_SIZE_ELEMENTS(length_) << BITVECTOR_SHIFT_BYTES)
 Size of a bitvector containing length_ bits, in bytes. More...
 
#define bitvector_t(name_, size_)    bitvector_element_t name_[BITVECTOR_SIZE_ELEMENTS(size_)]
 Declare a bitvector variable or field. More...
 
#define BITVECTOR_SET_ELEMENTS(vec_, size_, value_)
 Set all of the bits in a bit vector to a value. More...
 
#define BITVECTOR_COPY_FLIP(dest_, src_, size_, flip_)
 Copy the contents of one bit vector to another, with an optional exclusive-or operation. More...
 
#define BITVECTOR_CLEAR(vec_, bit_)    (vec_)[(bit_) >> BITVECTOR_SHIFT_ELEMENTS] &= ~((bitvector_element_t)1 << (BITVECTOR_ELEMENT_MASK & (bit_)))
 Clear a single bit in a bit vector. More...
 
#define BITVECTOR_SET(vec_, bit_)    (vec_)[(bit_) >> BITVECTOR_SHIFT_ELEMENTS] |= ((bitvector_element_t)1 << (BITVECTOR_ELEMENT_MASK & (bit_)))
 Set a single bit in a bit vector. More...
 
#define BITVECTOR_IS_SET(vec_, bit_)    ((vec_)[(bit_) >> BITVECTOR_SHIFT_ELEMENTS] & ((bitvector_element_t)1 << (BITVECTOR_ELEMENT_MASK & (bit_))))
 Test if a bit in a bit vector is set. More...
 
#define BITVECTOR_ELEMENT_BIT_MASK(element_, bit_)    (((element_) == ((bit_) >> BITVECTOR_SHIFT_ELEMENTS)) << ((bit_) & BITVECTOR_ELEMENT_MASK))
 Return a mask which can be used to test and isolate a bit in an identified element. More...
 
#define BITVECTOR_ITERATE_BITS(iterator_, size_)
 Initialise per-bit iteration over a bit vector using an element, mask pair. More...
 
#define BITVECTOR_ITERATE_BITS_MORE(iterator_)   ((iterator_).element >= 0)
 Test if per-bit iteration over a bitvector using an element, mask pair is complete. More...
 
#define BITVECTOR_ITERATE_BITS_NEXT(iterator_)
 Continue per-bit iteration over a bit vector using an element, mask pair. More...
 
#define BITVECTOR_ITERATE_BITS_N(iterator_, size_, chunk_)
 Initialise multi-bit iteration over a bit vector using an element, mask pair. More...
 
#define BITVECTOR_ITERATE_BITS_NEXT_N(iterator_, chunk_)
 Continue multi-bit iteration over a bit vector using an element, mask pair. More...
 
#define BITVECTOR_ITERATE_ELEMENTS(iterator_, size_)
 Initialise per-element iteration over a bit vector using an element, mask pair. More...
 
#define BITVECTOR_ITERATE_ELEMENTS_MORE(iterator_)   ((iterator_).element >= 0)
 Test if per-element iteration over a bitvector using an element, mask pair is complete. More...
 
#define BITVECTOR_ITERATE_ELEMENTS_NEXT(iterator_)
 Continue per-element iteration over a bit vector using an element, mask pair. More...
 

Typedefs

typedef uint64 bitvector_element_t
 An unsigned type used to implement bit vectors.
 
typedef struct bitvector_iterator_t bitvector_iterator_t
 Iterator structure for walking bit vectors. More...
 

Detailed Description

Macros implementing bit vectors.

Bit vectors are stored in units of a fundamental type, bitvector_element_t. They may be iterated, indexed and manipulated in terms of bits or the element type.

A stack or static bitvector may be declared using the bitvector_t() macro.

Individual bits in a bitvector may be cleared, set, or tested using BITVECTOR_CLEAR(), BITVECTOR_SET(), and BITVECTOR_IS_SET(). The entire bitvector may be set using BITVECTOR_SET_ELEMENTS(), or copied and transformed using BITVECTOR_COPY_FLIP().

Several ways of iterating bit vectors are provided, all using the bitvector_iterator_t type.

BITVECTOR_ITERATE_BITS(), BITVECTOR_ITERATE_BITS_MORE(), and BITVECTOR_ITERATE_BITS_NEXT() iterate one bit at a time.

BITVECTOR_ITERATE_BITS_N(), BITVECTOR_ITERATE_BITS_MORE(), and BITVECTOR_ITERATE_BITS_NEXT_N() iterate multiple bits at a time.

BITVECTOR_ITERATE_ELEMENTS(), BITVECTOR_ITERATE_ELEMENTS_MORE(), and BITVECTOR_ITERATE_ELEMENTS_NEXT() iterate by bitvector_element_t units.

Copyright (C) 2023 Global Graphics Software Ltd. All rights reserved. This source code contains the confidential and trade secret information of Global Graphics Software Ltd. It may not be used, copied or distributed for any reason except as set forth in the applicable Global Graphics license agreement.

Macro Definition Documentation

◆ BITVECTOR_CLEAR

#define BITVECTOR_CLEAR (   vec_,
  bit_ 
)     (vec_)[(bit_) >> BITVECTOR_SHIFT_ELEMENTS] &= ~((bitvector_element_t)1 << (BITVECTOR_ELEMENT_MASK & (bit_)))

Clear a single bit in a bit vector.

Parameters
vec_The bitvector to modify.
bit_The bit index to clear.

◆ BITVECTOR_COPY_FLIP

#define BITVECTOR_COPY_FLIP (   dest_,
  src_,
  size_,
  flip_ 
)
Value:
MACRO_START \
unsigned int _i_ = BITVECTOR_SIZE_ELEMENTS(size_) ; \
HQASSERT(_i_ > 0, "Bitvector has no elements") ; \
do { \
--_i_ ; \
(dest_)[_i_] = (src_)[_i_] ^ ((bitvector_element_t)!(flip_) - 1u) ; \
} while ( _i_ > 0 ) ; \
MACRO_END
uint64 bitvector_element_t
An unsigned type used to implement bit vectors.
Definition: hqbitvector.h:46
#define BITVECTOR_SIZE_ELEMENTS(length_)
Size of a bitvector containing length_ bits, in elements.
Definition: hqbitvector.h:76

Copy the contents of one bit vector to another, with an optional exclusive-or operation.

Parameters
dest_The destination bitvector.
src_The source bitvector.
size_The number of bits in the vector.
flip_A boolean, indicating if the destination should be the inverse of the source.

◆ BITVECTOR_ELEMENT_BIT_MASK

#define BITVECTOR_ELEMENT_BIT_MASK (   element_,
  bit_ 
)     (((element_) == ((bit_) >> BITVECTOR_SHIFT_ELEMENTS)) << ((bit_) & BITVECTOR_ELEMENT_MASK))

Return a mask which can be used to test and isolate a bit in an identified element.

Parameters
element_The element index being processed.
bit_The bit index to derive a mask for.

The return value is a mask that is zero if bit_ is not in element_, or set to the bit mask within element_ if it is.

This can be used to implement bulk operations in clients, without having to test if particular bits that should be treated specially are present in each element.

◆ BITVECTOR_IS_SET

#define BITVECTOR_IS_SET (   vec_,
  bit_ 
)     ((vec_)[(bit_) >> BITVECTOR_SHIFT_ELEMENTS] & ((bitvector_element_t)1 << (BITVECTOR_ELEMENT_MASK & (bit_))))

Test if a bit in a bit vector is set.

Parameters
vec_The bitvector to test.
bit_The bit index to test.

◆ BITVECTOR_ITERATE_BITS

#define BITVECTOR_ITERATE_BITS (   iterator_,
  size_ 
)
Value:
(iterator_).bit = (size_) - 1, \
(iterator_).element = (int)BITVECTOR_SIZE_ELEMENTS(size_) - 1, \
(iterator_).mask = ((bitvector_element_t)1 << ((iterator_).bit & BITVECTOR_ELEMENT_MASK))
#define BITVECTOR_ELEMENT_MASK
Mask to extract bit index within element from bit index.
Definition: hqbitvector.h:64

Initialise per-bit iteration over a bit vector using an element, mask pair.

Parameters
iterator_A bitvector_iterator_t variable to initialise.
size_The size of the bit vector.

This macro is written such that it can be used in a for-loop initialisation statement. Note that the iteration goes from the highest to lowest bits. The iterator will be initialised correctly for bitvectors of size zero or more. The idiom will usually look like this:

bitvector_t(vector, MAXBITS) ;
for ( BITVECTOR_ITERATE_BITS(iterator, bits_used) ;
if ( (vector[iterator.element] & iterator.mask) != 0 ) {
...bit iterator.bit is set...
}
}
#define BITVECTOR_ITERATE_BITS(iterator_, size_)
Initialise per-bit iteration over a bit vector using an element, mask pair.
Definition: hqbitvector.h:210
#define BITVECTOR_ITERATE_BITS_MORE(iterator_)
Test if per-bit iteration over a bitvector using an element, mask pair is complete.
Definition: hqbitvector.h:225
#define bitvector_t(name_, size_)
Declare a bitvector variable or field.
Definition: hqbitvector.h:94
#define BITVECTOR_ITERATE_BITS_NEXT(iterator_)
Continue per-bit iteration over a bit vector using an element, mask pair.
Definition: hqbitvector.h:237
Iterator structure for walking bit vectors.
Definition: hqbitvector.h:177
bitvector_element_t mask
Definition: hqbitvector.h:180
int element
Definition: hqbitvector.h:178
unsigned int bit
Definition: hqbitvector.h:179
See also
BITVECTOR_ITERATE_BITS_MORE, BITVECTOR_ITERATE_BITS_NEXT

◆ BITVECTOR_ITERATE_BITS_MORE

#define BITVECTOR_ITERATE_BITS_MORE (   iterator_)    ((iterator_).element >= 0)

Test if per-bit iteration over a bitvector using an element, mask pair is complete.

Parameters
iterator_The bitvector_iterator_t variable to test.

This macro is written such that it can be used in a for-loop condition statement. Note that the iteration goes from the highest to lowest bits.

See also
BITVECTOR_ITERATE_BITS, BITVECTOR_ITERATE_BITS_NEXT

◆ BITVECTOR_ITERATE_BITS_N

#define BITVECTOR_ITERATE_BITS_N (   iterator_,
  size_,
  chunk_ 
)
Value:
HQASSERT_EXPR(((chunk_) & ((chunk_) - 1)) == 0 && (size_) % (chunk_) == 0, \
"Iteration chunk or size mismatch", \
((iterator_).bit = (size_) - (chunk_), \
(iterator_).element = (int)BITVECTOR_SIZE_ELEMENTS(size_) - 1, \
(iterator_).mask = ((bitvector_element_t)((1 << (chunk_)) - 1) << ((iterator_).bit & BITVECTOR_ELEMENT_MASK))))
#define HQASSERT_EXPR(fCondition, pszMessage, value)
Definition: hqassert.h:204

Initialise multi-bit iteration over a bit vector using an element, mask pair.

Parameters
iterator_A bitvector_iterator_t variable to initialise.
size_The size of the bit vector.
chunk_The number of bits to iterate at a time. This should be a power of 2.

This macro is written such that it can be used in a for-loop initialisation statement. Note that the iteration goes from the highest to lowest bits. The iterator will be initialised correctly for bitvectors of size zero or more. The idiom will usually look like this:

bitvector_t(vector, MAXLEN * 2) ;
for ( BITVECTOR_ITERATE_BITS_N(iterator, bits_used, 2) ;
int chunk = ((vector[iterator.element] & iterator.mask) >> iterator.bit) ;
...
}
#define BITVECTOR_ITERATE_BITS_NEXT_N(iterator_, chunk_)
Continue multi-bit iteration over a bit vector using an element, mask pair.
Definition: hqbitvector.h:289
#define BITVECTOR_ITERATE_BITS_N(iterator_, size_, chunk_)
Initialise multi-bit iteration over a bit vector using an element, mask pair.
Definition: hqbitvector.h:270
See also
BITVECTOR_ITERATE_BITS_MORE, BITVECTOR_ITERATE_BITS_NEXT_N

◆ BITVECTOR_ITERATE_BITS_NEXT

#define BITVECTOR_ITERATE_BITS_NEXT (   iterator_)
Value:
(iterator_).bit -= 1, \
(iterator_).element -= (int)((iterator_).mask & 1), \
(iterator_).mask = ((iterator_).mask >> 1) | ((iterator_).mask << (BITVECTOR_ELEMENT_BITS - 1u))
#define BITVECTOR_ELEMENT_BITS
Bit vector element size in bits.
Definition: hqbitvector.h:61

Continue per-bit iteration over a bit vector using an element, mask pair.

Parameters
iterator_The bitvector_iterator_t variable to step.

This macro is written such that it can be used in a for-loop continuation statement. Note that the iteration goes from the highest to lowest bits.

See also
BITVECTOR_ITERATE_BITS, BITVECTOR_ITERATE_BITS_MORE

◆ BITVECTOR_ITERATE_BITS_NEXT_N

#define BITVECTOR_ITERATE_BITS_NEXT_N (   iterator_,
  chunk_ 
)
Value:
HQASSERT_EXPR(((chunk_) & ((chunk_) - 1)) == 0 && (iterator_).bit % (chunk_) == 0, \
"Iteration chunk or size mismatch", \
((iterator_).bit -= (chunk_), \
(iterator_).element -= (int)((iterator_).mask & 1), \
(iterator_).mask = (((iterator_).mask >> (chunk_)) | \
((iterator_).mask << (BITVECTOR_ELEMENT_BITS - (chunk_))))))

Continue multi-bit iteration over a bit vector using an element, mask pair.

Parameters
iterator_The bitvector_iterator_t variable to step.
chunk_The number of bits to iterate at a time. This should be a power of 2.

This macro is written such that it can be used in a for-loop continuation statement. Note that the iteration goes from the highest to lowest bits.

See also
BITVECTOR_ITERATE_BITS_MORE, BITVECTOR_ITERATE_BITS_N

◆ BITVECTOR_ITERATE_ELEMENTS

#define BITVECTOR_ITERATE_ELEMENTS (   iterator_,
  size_ 
)
Value:
(iterator_).bit = ((size_) - 1), \
(iterator_).element = (int)BITVECTOR_SIZE_ELEMENTS(size_) - 1, \
#define BITVECTOR_ELEMENT_ONES
Bitvector element containing all ones.
Definition: hqbitvector.h:70

Initialise per-element iteration over a bit vector using an element, mask pair.

Parameters
iterator_The bitvector_iterator_t variable to initialise.
size_The size of the bit vector.

This macro is written such that it can be used in a for-loop initialisation statement. Note that the iteration goes from the highest to lowest element. The iterator will be initialised correctly for bitvectors of size zero or more. The iteration idiom will usually look like this:

bitvector_t(vector, MAXBITS) ;
for ( BITVECTOR_ITERATE_ELEMENTS(iterator, bits_used) ;
if ( (vector[iterator.element] & iterator.mask) == iterator.mask ) {
...all bits set...
} else if ( (vector[iterator.element] & iterator.mask) == 0 ) {
...no bits set...
} ...etc...
}
#define BITVECTOR_ITERATE_ELEMENTS_MORE(iterator_)
Test if per-element iteration over a bitvector using an element, mask pair is complete.
Definition: hqbitvector.h:342
#define BITVECTOR_ITERATE_ELEMENTS(iterator_, size_)
Initialise per-element iteration over a bit vector using an element, mask pair.
Definition: hqbitvector.h:326
#define BITVECTOR_ITERATE_ELEMENTS_NEXT(iterator_)
Continue per-element iteration over a bit vector using an element, mask pair.
Definition: hqbitvector.h:355
See also
BITVECTOR_ITERATE_ELEMENTS_MORE, BITVECTOR_ITERATE_ELEMENTS_NEXT

◆ BITVECTOR_ITERATE_ELEMENTS_MORE

#define BITVECTOR_ITERATE_ELEMENTS_MORE (   iterator_)    ((iterator_).element >= 0)

Test if per-element iteration over a bitvector using an element, mask pair is complete.

Parameters
iterator_The bitvector_iterator_t variable to test.

The bits index to test. This macro is written such that it can be used in a for-loop condition statement. Note that the iteration goes from the highest to lowest element.

See also
BITVECTOR_ITERATE_ELEMENTS, BITVECTOR_ITERATE_ELEMENTS_NEXT

◆ BITVECTOR_ITERATE_ELEMENTS_NEXT

#define BITVECTOR_ITERATE_ELEMENTS_NEXT (   iterator_)
Value:
(iterator_).bit = ((iterator_).bit & ~BITVECTOR_ELEMENT_MASK) - 1, \
(iterator_).element -= 1, (iterator_).mask = BITVECTOR_ELEMENT_ONES

Continue per-element iteration over a bit vector using an element, mask pair.

Parameters
iterator_The bitvector_iterator_t variable to step.

This macro is written such that it can be used in a for-loop continuation statement. Note that the iteration goes from the highest to lowest element.

See also
BITVECTOR_ITERATE_ELEMENTS, BITVECTOR_ITERATE_ELEMENTS_MORE

◆ BITVECTOR_SET

#define BITVECTOR_SET (   vec_,
  bit_ 
)     (vec_)[(bit_) >> BITVECTOR_SHIFT_ELEMENTS] |= ((bitvector_element_t)1 << (BITVECTOR_ELEMENT_MASK & (bit_)))

Set a single bit in a bit vector.

Parameters
vec_The bitvector to modify.
bit_The bit index to set.

◆ BITVECTOR_SET_ELEMENTS

#define BITVECTOR_SET_ELEMENTS (   vec_,
  size_,
  value_ 
)
Value:
MACRO_START \
unsigned int _i_ = BITVECTOR_SIZE_ELEMENTS(size_) ; \
HQASSERT(_i_ > 0, "Bitvector has no elements") ; \
do { \
(vec_)[--_i_] = (value_) ; \
} while ( _i_ > 0 ) ; \
MACRO_END

Set all of the bits in a bit vector to a value.

Parameters
vec_The bitvector to clear.
size_The number of bits in the vector.
value_This should be BITVECTOR_ELEMENT_ZEROS to clear the vector, BITVECTOR_ELEMENT_ONES to set the vector.

◆ BITVECTOR_SHIFT_BYTES

#define BITVECTOR_SHIFT_BYTES   3

Right shift to convert bytes indices to element indices.

The relationship:

(1 << BITVECTOR_SHIFT_BYTES) == sizeof(bitvector_element_t)

should always hold.

◆ BITVECTOR_SIZE_BYTES

#define BITVECTOR_SIZE_BYTES (   length_)     (BITVECTOR_SIZE_ELEMENTS(length_) << BITVECTOR_SHIFT_BYTES)

Size of a bitvector containing length_ bits, in bytes.

Parameters
length_Length of the bitvector, in bits.

◆ BITVECTOR_SIZE_ELEMENTS

#define BITVECTOR_SIZE_ELEMENTS (   length_)     (((length_) + BITVECTOR_ELEMENT_BITS - 1u) >> BITVECTOR_SHIFT_ELEMENTS)

Size of a bitvector containing length_ bits, in elements.

Parameters
length_Length of the bitvector, in bits.

◆ bitvector_t

#define bitvector_t (   name_,
  size_ 
)     bitvector_element_t name_[BITVECTOR_SIZE_ELEMENTS(size_)]

Declare a bitvector variable or field.

Parameters
name_The name of the bitvector name or field.
size_A constant expression, giving the number of bits in the vector.

This macro can be used anywhere that a variable or parameter declaration can occur.

Typedef Documentation

◆ bitvector_iterator_t

Iterator structure for walking bit vectors.

This structure is transparent; the element index and the mask can be used by the client to extract and manipulate words from the bitvector directly.