Bit operations

Typedefs
typedef uint8_t	bitsBuffer_t
	A bit-buffer is a sequence of 8-bits unsigned integers. More...

Enumerations
enum	bitsBltOp_t {   BITS_BLT_COPY, BITS_BLT_NOT, BITS_BLT_AND, BITS_BLT_OR,   BITS_BLT_XOR, BITS_BLT_NOT_AND }
	Possible bit operations for bitsBlt(). More...

Functions
int	bitsSet (bitsBuffer_t *b, int index, int value)
	Set or clear a bit in b. More...
int	bitsSetRange (bitsBuffer_t *b, int offset, int count, int value)
	Set a range of bits on a buffer. More...
int	bitsGet (const bitsBuffer_t *b, int index)
	Return the value of a bit in b. More...
int64_t	bitsExtractInt (const bitsBuffer_t *b, int offset, int count)
	Extract a sub-sequence of a bit buffer as an integer. More...
int	bitsAppend (const bitsBuffer_t *src, int srcOffset, int srcCount, bitsBuffer_t *dst, int dstCount)
	Append one bit buffer to another. More...
int	bitsAppendInt (uint64_t bits, int nbits, bitsBuffer_t *dst, int dstCount)
	Append the bits extracted from an integer to a bit buffer. More...
int	bitsRotateLeft (bitsBuffer_t *b, int index, int nbits, int nrotate)
	Rotate b left by nrotate bits. More...
int	bitsRotateRight (bitsBuffer_t *b, int index, int nbits, int nrotate)
	Rotate b right by nrotate bits. More...
int	bitsShiftLeft (bitsBuffer_t *b, int index, int nbits, int nshift)
	Shift b left by nshift bits. More...
int	bitsShiftRight (bitsBuffer_t *b, int index, int nbits, int nshift)
	Shift b right by nshift bits. More...
int	bitsCopy (const bitsBuffer_t *src, int srcOffset, int srcCount, bitsBuffer_t *dst, int dstOffset)
	Copy a sequence of bits from one buffer to another. More...
int	bitsBlt (const bitsBuffer_t *src, int srcOffset, int srcCount, enum bitsBltOp_t op, bitsBuffer_t *dst, int dstOffset)
	Combine two bit buffers using a bit operation. More...

Detailed Description

Rationale

Many of the protocols, standards and devices we have to deal require manipulation bit by bit of structures. Even though certain algorithms are quite simple (set bit, get bit) others can be complex (rotate, shift).

Introduction

This module manipulates sequences of bits. All functions operate on "naked" sequences of bytes, this was decided in order to keep this module low level. Users may wrap the functions to provide a more secure API, with bounds checking, for example.

Note that in all cases bellow, sizes and offsets/indices are given in bits, and all operations consider the left most bit of the left most byte as the bit index zero. As is default in C, all indices are zero-based.

A bit buffer of 16 bits, with the bit index 13 set, equals the binary value "0000000000000100" or the buffer { 0x00, 0x04 }.

Certain operations may be faster if the number of bits to operate is multiple of 8 (whole bytes), but there is no guarantee on this regard.

Typedef Documentation

typedef uint8_t bitsBuffer_t

A bit-buffer is a sequence of 8-bits unsigned integers.

Note that the actual size in bits of the buffer does not need to be a multiple of 8, but memory allocation is done in bytes.

Enumeration Type Documentation

enum bitsBltOp_t

Possible bit operations for bitsBlt().

Enumerator
BITS_BLT_COPY	Copy source bits into destination.
BITS_BLT_NOT	Copy negated source bits into destination.
BITS_BLT_AND	Logical AND of source and destination.
BITS_BLT_OR	Logical OR of source and destination.
BITS_BLT_XOR	Logical XOR of source and destination.
BITS_BLT_NOT_AND	Logical AND of negated source and destination.

Function Documentation

int bitsAppend	(	const bitsBuffer_t *	src,
		int	srcOffset,
		int	srcCount,
		bitsBuffer_t *	dst,
		int	dstCount
	)

Append one bit buffer to another.

Append the srcCount bits of src starting at offset srcOffset to a bit buffer dst that already have dstCount bits.

No bounds checking is done on dst or src.

Precondition

dst and src must not overlap.

Parameters

src	Source bit buffer.
srcOffset	Index of first bit to read from src.
srcCount	Number of bits to append.
dst	Destination bit buffer.
dstCount	Current size of dst in bits.

Returns

The new size of dst on success (dstCount + srcCount).

BASE_ERR_INVALID_PARAMETER.

int bitsAppendInt	(	uint64_t	bits,
		int	nbits,
		bitsBuffer_t *	dst,
		int	dstCount
	)

Append the bits extracted from an integer to a bit buffer.

Append, from left to right, the right most nbits bits of bits into the bit buffer dst that already have dstCount bits.

For example, given a bit buffer with value "1010", using bits = 0xC and nbits = 4 would result in the bit buffer "10101100", inserting the sequence "1100". Notice that the bits to insert should be the right most ones on the input integer, but they are inserted from left to right (most significant first).

No bounds checking is done on dst.

Parameters

bits	Value of the bits to insert.
nbits	Number of bits to insert.
dst	Destination bit buffer.
dstCount	Current size of dst in bits.

Returns

The new size of dst on success (dstCount + nbits).

BASE_ERR_INVALID_PARAMETER.

int bitsBlt	(	const bitsBuffer_t *	src,
		int	srcOffset,
		int	srcCount,
		enum bitsBltOp_t	op,
		bitsBuffer_t *	dst,
		int	dstOffset
	)

Combine two bit buffers using a bit operation.

This is a very general function that allow to combine two bit buffers using one of many bit operations. dst is replaced with the result of the operation defined by op on both src and dst (note that certain operations ignore the value of dst, for example BITS_BLT_COPY).

src and dst may overlap.

Parameters

src	Source bit buffer.
srcOffset	First index to read from src.
srcCount	Number of bits to read.
op	Which bit operation to perform.
dst	Destination bit buffer.
dstOffset	First index to modify of dst.

Returns

BASE_ERR_OK.

BASE_ERR_INVALID_PARAMETER.

int bitsCopy	(	const bitsBuffer_t *	src,
		int	srcOffset,
		int	srcCount,
		bitsBuffer_t *	dst,
		int	dstOffset
	)

Copy a sequence of bits from one buffer to another.

Copy srcCount bits starting at bit index srcOffset from src into dst at offset dstOffset. This is equivalent to calling bitsBlt() with the BITS_BLT_COPY operation.

No bounds checking is done on dst or src.

Parameters

src	Source bits buffer.
srcOffset	Index of first bit to copy, in bits.
srcCount	Number of bits to copy.
dst	Destination bits buffer.
dstOffset	Index of first bit to overwrite in dst.

Returns

BASE_ERR_OK on success.

BASE_ERR_INVALID_PARAMETER.

int64_t bitsExtractInt	(	const bitsBuffer_t *	b,
		int	offset,
		int	count
	)

Extract a sub-sequence of a bit buffer as an integer.

Interpret count bits of b starting at offset as an integer (most-significant bit first). Note that this function call can only return unsigned integers smaller than 2⁶³-1, since negative numbers are used for error reporting.

For example, the integer at offset 2, count 3 in "01101000" is "101" whose value is 5.

No bounds checking is done on dst or src.

Parameters

b	Bits buffer to read.
offset	Index of first bit to read.
count	Number of bits to read.

Returns

The non-negative value of the bits read.

BASE_ERR_INVALID_PARAMETER.

int bitsGet	(	const bitsBuffer_t *	b,
		int	index
	)

Return the value of a bit in b.

Note that this function does no bounds checking, the caller must guarantee that index is a valid bit index inside b.

Parameters

b	bitsBuffer_t to modify.
index	Index of bit to return.

Returns

The value of the bits at index as 0 (clear) or 1 (set)

BASE_ERR_INVALID_PARAMETER if b == NULL or index is invalid.

int bitsRotateLeft	(	bitsBuffer_t *	b,
		int	index,
		int	nbits,
		int	nrotate
	)

Rotate b left by nrotate bits.

Note that both the buffer size and the rotation size are in bits, it is valid to rotate 3 bits to the left a buffer of 11 bits.

When rotating, the bits that fall off on the left, are re-inserted on the right. For example, rotating "11110000" 1 bit to the left results in "11100001".

Parameters

b	bitsBuffer_t to rotate.
index	First index on b to be affected.
nbits	Number of bits of b to be affected.
nrotate	Number of bits to rotate.

Returns

BASE_ERR_OK on success.

BASE_ERR_INVALID_PARAMETER if b == NULL or nbits or nrotate are invalid.

int bitsRotateRight	(	bitsBuffer_t *	b,
		int	index,
		int	nbits,
		int	nrotate
	)

Rotate b right by nrotate bits.

Note that both the buffer size and the rotation size are in bits, it is valid to rotate 3 bits to the right a buffer of 11 bits.

When rotating, the bits that fall off on the right, are re-inserted on the left. For example, rotating "00001111" 1 bit to the right results in "10000111".

Parameters

b	bitsBuffer_t to rotate.
index	First index on b to be affected.
nbits	Number of bits of b to be affected.
nrotate	Number of bits to rotate.

Returns

BASE_ERR_OK on success.

BASE_ERR_INVALID_PARAMETER if b == NULL or nbits or nrotate are invalid.

int bitsSet	(	bitsBuffer_t *	b,
		int	index,
		int	value
	)

Set or clear a bit in b.

Note that this function does no bounds checking, the caller must guarantee that index is a valid bit index inside b.

Parameters

b	bitsBuffer_t to modify.
index	Index of bit to set.
value	Zero to clear the bit, non-zero to set it.

Returns

BASE_ERR_OK on success.

BASE_ERR_INVALID_PARAMETER if b == NULL or index is invalid.

int bitsSetRange	(	bitsBuffer_t *	b,
		int	offset,
		int	count,
		int	value
	)

Set a range of bits on a buffer.

Set count bits of b starting at index offset to value.

Parameters

b	Bit buffer to modify.
offset	Index of first bit to modify.
count	Number of bits to modify.
value	Value to set (zero to clear, non-zero to set).

Returns

BASE_ERR_OK.

BASE_ERR_INVALID_PARAMETER.

int bitsShiftLeft	(	bitsBuffer_t *	b,
		int	index,
		int	nbits,
		int	nshift
	)

Shift b left by nshift bits.

Note that both the buffer size and the shift size are in bits, it is valid to shift 3 bits to the left a buffer of 11 bits.

When shifting, zeroes are inserted on the right as the bits move left.

Parameters

b	bitsBuffer_t to shift.
index	First index on b to be affected.
nbits	Size of b in bits.
nshift	Number of bits to shift b.

Returns

BASE_ERR_OK on success.

BASE_ERR_INVALID_PARAMETER if b == NULL or nbits or nshift are invalid.

int bitsShiftRight	(	bitsBuffer_t *	b,
		int	index,
		int	nbits,
		int	nshift
	)

Shift b right by nshift bits.

Note that both the buffer size and the shift size are in bits, it is valid to shift 3 bits to the right a buffer of 11 bits.

When shifting, zeroes are inserted on the left as the bits move right.

Parameters

b	bitsBuffer_t to shift.
index	First index on b to be affected.
nbits	Size of b in bits.
nshift	Number of bits to shift b.

Returns

BASE_ERR_OK on success.

BASE_ERR_INVALID_PARAMETER if b == NULL or nbits or nshift are invalid.