Bitwise Data Parser

Typedefs
typedef struct M_bit_parser	M_bit_parser_t

Enumerations
enum	M_bit_parser_int_format_t {   M_BIT_PARSER_SIGN_MAG = 0 ,   M_BIT_PARSER_ONES_COMP = 1 ,   M_BIT_PARSER_TWOS_COMP = 2 }

Functions
M_bit_parser_t *	M_bit_parser_create (const void *bytes, size_t nbits) M_WARN_UNUSED_RESULT M_MALLOC
M_bit_parser_t *	M_bit_parser_create_const (const void *bytes, size_t nbits) M_WARN_UNUSED_RESULT M_MALLOC
void	M_bit_parser_append (M_bit_parser_t *bparser, const void *bytes, size_t nbits)
void	M_bit_parser_append_uint (M_bit_parser_t *bparser, M_uint64 bits, size_t nbits)
M_bool	M_bit_parser_append_bitstr (M_bit_parser_t *bparser, const char *bitstr)
void	M_bit_parser_reset (M_bit_parser_t *bparser, const void *bytes, size_t nbits)
void	M_bit_parser_destroy (M_bit_parser_t *bparser) M_FREE(1)
size_t	M_bit_parser_len (const M_bit_parser_t *bparser)
size_t	M_bit_parser_current_offset (const M_bit_parser_t *bparser)
size_t	M_bit_parser_count (const M_bit_parser_t *bparser, M_uint8 bit)
void	M_bit_parser_rewind_to_start (M_bit_parser_t *bparser)
void	M_bit_parser_mark (M_bit_parser_t *bparser)
size_t	M_bit_parser_mark_len (const M_bit_parser_t *bparser)
size_t	M_bit_parser_mark_rewind (M_bit_parser_t *bparser)
M_bool	M_bit_parser_consume (M_bit_parser_t *bparser, size_t nbits)
M_bool	M_bit_parser_peek_bit (const M_bit_parser_t *bparser, M_uint8 *bit)
M_bool	M_bit_parser_read_bit (M_bit_parser_t *bparser, M_uint8 *bit)
M_bool	M_bit_parser_read_bit_buf (M_bit_parser_t *bparser, M_bit_buf_t *bbuf, size_t nbits)
M_bool	M_bit_parser_read_buf (M_bit_parser_t *bparser, M_buf_t *buf, size_t nbits)
M_bool	M_bit_parser_read_bytes (M_bit_parser_t *bparser, M_uint8 *dest, size_t *destlen, size_t nbits)
char *	M_bit_parser_read_strdup (M_bit_parser_t *bparser, size_t nbits)
M_bool	M_bit_parser_read_uint (M_bit_parser_t *bparser, size_t nbits, M_uint64 *res)
M_bool	M_bit_parser_read_int (M_bit_parser_t *bparser, size_t nbits, M_bit_parser_int_format_t fmt, M_int64 *res)
M_bool	M_bit_parser_read_range (M_bit_parser_t *bparser, M_uint8 *bit, size_t *nbits_in_range, size_t max_bits)
M_bool	M_bit_parser_consume_range (M_bit_parser_t *bparser, size_t max_bits)
M_bool	M_bit_parser_consume_to_next (M_bit_parser_t *bparser, M_uint8 bit, size_t max_bits)

Detailed Description

Buffer based data parser that reads data per-bit, instead of per-byte.

Example (creating a parser, reading some bits):

M_bit_parser_t *bparser;
const M_uint8   bytes[] = {0x70, 0x3F};
size_t          nbits   = 12;
 
M_uint8         bit;
char           *str;
size_t          nbits_in_range;
 
bparser = M_bit_parser_create_const(bytes, nbits);
 
M_bit_parser_read_bit(bparser, &bit); // bit == 0
 
str == M_bit_parser_read_strdup(bparser, 5); // str == "11100"
M_free(str);
 
M_bit_parser_read_range(bparser, &bit, &nbits_in_range, M_bit_parser_len(bparser));
// bit == 0
// nbits_in_range == 6
 
M_bit_parser_destroy(bparser);

Typedef Documentation

M_bit_parser_t

typedef struct M_bit_parser M_bit_parser_t

Enumeration Type Documentation

M_bit_parser_int_format_t

enum M_bit_parser_int_format_t

Signed integer formats understood by bit parser.

In-depth description of these formats can be found at https://en.wikipedia.org/wiki/Signed_number_representations.

See also

M_bit_parser_read_int

Enumerator
M_BIT_PARSER_SIGN_MAG	Signed magnitude format (first bit is sign, rest of bits are magnitude)
M_BIT_PARSER_ONES_COMP	One's complement
M_BIT_PARSER_TWOS_COMP	Two's complement

Function Documentation

M_bit_parser_create()

M_bit_parser_t * M_bit_parser_create	(	const void *	bytes,
		size_t	nbits
	)

Create a bit parser over the given data (copies input data).

The parser will copy the data internally, so after this function is called, the caller's copy of the data may be copied or freed without affecting the parser.

If your data isn't going to change, you can use M_bit_parser_create_const() instead to avoid duplicating the data.

Parameters

[in]	bytes	data to parse bitwise
[in]	nbits	number of bits in data

Returns

a new parser object over the given data

See also

M_bit_parser_reset

M_bit_parser_destroy

M_bit_parser_create_const()

M_bit_parser_t * M_bit_parser_create_const	(	const void *	bytes,
		size_t	nbits
	)

Create a bit parser over the given data (assumes given data won't change).

Assumes the given data pointer won't be modified until after you're done with the parser.

Warning

Violating this assumption can lead to undefined behavior (including program crashes).

Parameters

[in]	bytes	data to parse bitwise
[in]	nbits	number of bits in data

Returns

a new parser object over the given data

See also

M_bit_parser_reset

M_bit_parser_destroy

M_bit_parser_append()

void M_bit_parser_append	(	M_bit_parser_t *	bparser,
		const void *	bytes,
		size_t	nbits
	)

Append data to a bit parser object.

If you append data to a parser that was created with M_bit_parser_create_const(), the const data will be copied into internal storage before the append.

Parameters

[in]	bparser	bit parser object
[in]	bytes	bytes to read from
[in]	nbits	number of bits to append from byte array

M_bit_parser_append_uint()

void M_bit_parser_append_uint	(	M_bit_parser_t *	bparser,
		M_uint64	bits,
		size_t	nbits
	)

Append bits from a given integer to a bit parser object.

Note that the bit region being read is assumed to be justified against the least-significant end of the integer, though the bits within that region are read from most-significant to least-significant.

For example, if bits == 0x8B == (10001011)b, and nbits == 4, the bits "1011" will be added to the buffer.

Parameters

[in]	bparser	bit parser object
[in]	bits	value to draw bits from
[in]	nbits	number of bits to use (counted from least-significant end, right-to-left)

M_bit_parser_append_bitstr()

M_bool M_bit_parser_append_bitstr	(	M_bit_parser_t *	bparser,
		const char *	bitstr
	)

Append bits from a given binary-ascii string to the buffer.

A binary-ascii string is a list of 1 and 0 characters (e.g., "100010").

Any whitespace in the string will be silently ignored. So, " 1000 1 0" will add the same data as "100010".

Parameters

[in]	bparser	bit parser object
[in]	bitstr	string to draw bits from

Returns

M_FALSE on error (given bitstr had characters other than '0', '1' or whitespace)

M_bit_parser_reset()

void M_bit_parser_reset	(	M_bit_parser_t *	bparser,
		const void *	bytes,
		size_t	nbits
	)

Reset parser to use new data (copies input data).

Parser state (including any mark) is reset to initial values. Any data that was in the parser before this call is dropped.

The new data is copied into the parser, so the caller's copy of the data may be modified or freed after this call without affecting the parser.

Parameters

[in]	bparser	bit parser object
[in]	bytes	bytes to read from
[in]	nbits	number of bits to read out of input bytes

M_bit_parser_destroy()

void M_bit_parser_destroy

(

M_bit_parser_t *

bparser

)

Destroy the bit parser object.

Parameters

[in]

bparser

bit parser object

M_bit_parser_len()

size_t M_bit_parser_len

(

const M_bit_parser_t *

bparser

)

Returns the number of bits left to read in the parser.

Parameters

[in]

bparser

bit parser object

Returns

number of bits left that haven't been read yet

M_bit_parser_current_offset()

size_t M_bit_parser_current_offset

(

const M_bit_parser_t *

bparser

)

Retrieve the current position of the parser (number of bits read).

Parameters

[in]

bparser

bit parser object

Returns

current parser position, relative to start of data (in bits)

M_bit_parser_count()

size_t M_bit_parser_count	(	const M_bit_parser_t *	bparser,
		M_uint8	bit
	)

Count the number of bits left in the parser that have the given value.

If the remaining bits in the parser are "10011110", calling this function with bit=0 will return 3, and calling it with bit=1 will return 5.

Parameters

[in]	bparser	bit parser object
[in]	bit	bit value to count

Returns

number of bits left in parser with the given value

M_bit_parser_rewind_to_start()

void M_bit_parser_rewind_to_start

(

M_bit_parser_t *

bparser

)

Rewind parser (and any mark) back to start of data.

Parameters

[in]

bparser

bit parser object

See also

M_bit_parser_mark

M_bit_parser_mark_rewind

M_bit_parser_mark()

void M_bit_parser_mark

(

M_bit_parser_t *

bparser

)

Mark the current position in the stream, so we can return to it later.

Parameters

[in]

bparser

bit parser object

See also

M_bit_parser_mark_len

M_bit_parser_mark_rewind

M_bit_parser_mark_len()

size_t M_bit_parser_mark_len

(

const M_bit_parser_t *

bparser

)

Return the number of bits from a mark to the current parser position.

If no mark has been set, returns the number of bits from the start of the data.

For example, if I set a mark, read 3 bits, and then call this function, it'll return 3.

Parameters

[in]

bparser

bit parser object

Returns

number of bits read/consumed from the point where we last marked the bitstream

See also

M_bit_parser_mark

M_bit_parser_mark_rewind()

size_t M_bit_parser_mark_rewind

(

M_bit_parser_t *

bparser

)

Rewind parser back to the marked position.

This will not clear the mark - you can read and then return to a marked position multiple times.

If no mark has been set, this will rewind all the way back to the beginning of the stream.

Parameters

[in]

bparser

bit parser object

Returns

number of bits we rewound the stream

See also

M_bit_parser_rewind_to_start

M_bit_parser_mark

M_bit_parser_consume()

M_bool M_bit_parser_consume	(	M_bit_parser_t *	bparser,
		size_t	nbits
	)

Skip past the given number of bits.

Parameters

[in]	bparser	bit parser object
[in]	nbits	number of bits to consume

Returns

M_TRUE on success, M_FALSE if not enough bits left

M_bit_parser_peek_bit()

M_bool M_bit_parser_peek_bit	(	const M_bit_parser_t *	bparser,
		M_uint8 *	bit
	)

Read a single bit at the parser's current position without advancing.

Parameters

[in]	bparser	bit parser object
[out]	bit	0 or 1

Returns

M_TRUE on success, M_FALSE if there are no bits left to read

M_bit_parser_read_bit()

M_bool M_bit_parser_read_bit	(	M_bit_parser_t *	bparser,
		M_uint8 *	bit
	)

Read a single bit at the parser's current position and advance.

Parameters

[in]	bparser	bit parser object
[out]	bit	0 or 1

Returns

M_TRUE on success, M_FALSE if there are no bits left to read

M_bit_parser_read_bit_buf()

M_bool M_bit_parser_read_bit_buf	(	M_bit_parser_t *	bparser,
		M_bit_buf_t *	bbuf,
		size_t	nbits
	)

Read multiple bits and add them to the end of the given bit buffer.

Parameters

[in]	bparser	bit parser to read bits from
[in,out]	bbuf	bit buffer to store bits in
[in]	nbits	number of bits to read

Returns

M_TRUE on success, M_FALSE if there aren't enough bits left

M_bit_parser_read_buf()

M_bool M_bit_parser_read_buf	(	M_bit_parser_t *	bparser,
		M_buf_t *	buf,
		size_t	nbits
	)

Read multiple bits, zero-pad to byte boundary, then add them to the given buffer.

Padding is only added as-needed to the last byte that gets added to the buffer. Every byte before that is packed with the bits we're reading.

For example, if we add the bits "1010 1010 1100 01" using this function, two bytes are added to the buffer: "1010 1010 1100 0100" (two padding zeros on end).

Parameters

[in]	bparser	bit parser to read bits from
[in,out]	buf	buffer to store bytes in
[in]	nbits	number of bits to read

Returns

M_TRUE on success, M_FALSE if there aren't enough bits left

M_bit_parser_read_bytes()

M_bool M_bit_parser_read_bytes	(	M_bit_parser_t *	bparser,
		M_uint8 *	dest,
		size_t *	destlen,
		size_t	nbits
	)

Read multiple bits, zero-pad to byte boundary, then add them to the given array.

Padding is only added as-needed to the last byte that gets added to the buffer. Every byte before that is packed with the bits we're reading.

For example, if we add the bits "1010 1010 1100 01" using this function, two bytes are added to the buffer: "1010 1010 1100 0100" (two padding zeros on end).

Parameters

[in]	bparser	bit parser to read bits from
[in]	dest	array to store bytes in
[in,out]	destlen	length of dest in bytes. Before return, set to number of bytes written.
[in]	nbits	number of bits to read

Returns

M_TRUE on success, M_FALSE if there aren't enough bits left

M_bit_parser_read_strdup()

char * M_bit_parser_read_strdup	(	M_bit_parser_t *	bparser,
		size_t	nbits
	)

Read multiple bits, then return them as a bit string.

A bit string is just a list of '0' and '1' characters (e.g., "100101").

Warning

The caller assumes ownership of returned string, and must free it with M_free().

Parameters

[in]	bparser	bit parser to read bits from
[in]	nbits	number of bits to read

Returns

bitstring on success, NULL if there aren't enough bits left

See also

M_free

M_bit_parser_read_uint()

M_bool M_bit_parser_read_uint	(	M_bit_parser_t *	bparser,
		size_t	nbits,
		M_uint64 *	res
	)

Read multiple bits, intepret as big-endian unsigned integer.

The bits are interpreted as a single big-endian unsigned integer, then the integer value is stored in res.

For example, if a bit parser contains '11100', you would see the following in num:

• M_bit_parser_read_uint(bparser, 3, &num) --> num == 7 (b111)
• M_bit_parser_read_uint(bparser, 4, &num) --> num == 14 (b1110)
• M_bit_parser_read_uint(bparser, 5, &num) --> num == 28 (b11100)

Parameters

[in]	bparser	bit parser to read bits from
[in]	nbits	number of bits to read (must be >= 1 and <= 64)
[out]	res	read bits, converted to an unsigned integer

Returns

M_TRUE on success, M_FALSE on failure

M_bit_parser_read_int()

M_bool M_bit_parser_read_int	(	M_bit_parser_t *	bparser,
		size_t	nbits,
		M_bit_parser_int_format_t	fmt,
		M_int64 *	res
	)

Read multiple bits, interpret as a signed integer.

The bits are interpreted as a single big-endian signed integer, using the specified signed integer format.

Parameters

[in]	bparser	bit parser to read bits from
[in]	nbits	number of bits to read (must be >= 2 and <= 64)
[in]	fmt	signed integer format of the bits we're reading
[out]	res	read bits, converted to a native signed integer

Returns

M_TRUE on success, M_FALSE on failure

M_bit_parser_read_range()

M_bool M_bit_parser_read_range	(	M_bit_parser_t *	bparser,
		M_uint8 *	bit,
		size_t *	nbits_in_range,
		size_t	max_bits
	)

Read bits until we hit a bit different than the current one.

For example, if the parser contain "11100001", calling this function will move the parser's position to the first 0, and return 1 in bit and 3 in nbits_in_range

Note that this function will always read at least one bit, if any bits are left to read.

Parameters

[in]	bparser	bit parser to read bits from
[out]	bit	bit value in range we just read (0 or 1)
[out]	nbits_in_range	number of bits in range we just read
[in]	max_bits	maximum number of bits to read (if set to zero, no bits will be read)

Returns

M_TRUE if at least one bit was read, M_FALSE if no bits are left or max_bits was zero

M_bit_parser_consume_range()

M_bool M_bit_parser_consume_range	(	M_bit_parser_t *	bparser,
		size_t	max_bits
	)

Skip bits until we hit a bit different than the current one.

For example, if the parser contains "11100001", calling this function will move the parser's position to the first 0.

Note that this function will always consume at least one bit, if any bits are left to skip.

Parameters

[in]	bparser	bit parser to read bits from
[in]	max_bits	maximum number of bits to skip (if set to zero, no bits will be skipped)

Returns

M_TRUE if at least one bit was skipped, M_FALSE if no bits are left or max_bits was zero

M_bit_parser_consume_to_next()

M_bool M_bit_parser_consume_to_next	(	M_bit_parser_t *	bparser,
		M_uint8	bit,
		size_t	max_bits
	)

Consume bits up to and including the next bit with the given value.

Usage example:

M_bit_parser_t *bparser;
const M_uint8   bytes[] = {0x86, 0x00};
 
bparser = M_bit_parser_create_const(bytes, 10);
// bparser contains: "1000011000"
 
// Now, let's say we want to print the index of every set bit.
while (M_bit_parser_consume_to_next(bparser, 1, M_bit_parser_len(bparser)) {
    M_printf("set bit: %zu\n", M_bit_parser_current_offset(bparser) - 1);
}
 
// Loop will print:
//   set bit: 0
//   set bit: 5
//   set bit: 6
// After loop, bparser will be empty.

Parameters

[in]	bparser	bit parser to read bits from
[in]	bit	bit value that we're looking for
[in]	max_bits	maximum number of bits to consume (if set to zero, no bits will be consumed)

Returns

M_TRUE if we found and consumed a matching bit, M_FALSE otherwise.