Osmocom bit vector abstraction utility routines. More...

Files
file	bitvec.h

file	bitvec.c

Data Structures
struct	bitvec
	structure describing a bit vector More...

Macros
#define	BITNUM_FROM_COMP(byte, bit) ((byte*8)+bit)

Enumerations
enum	bit_value { ZERO = 0 , ONE = 1 , L = 2 , H = 3 }
	A single GSM bit. More...

Functions
void	bitvec_add_range1024 (struct bitvec bv, const struct gsm48_range_1024 r)

enum bit_value	bitvec_get_bit_pos (const struct bitvec *bv, unsigned int bitnr)
	check if the bit is 0 or 1 for a given position inside a bitvec More...

enum bit_value	bitvec_get_bit_pos_high (const struct bitvec *bv, unsigned int bitnr)
	check if the bit is L or H for a given position inside a bitvec More...

unsigned int	bitvec_get_nth_set_bit (const struct bitvec *bv, unsigned int n)
	get the Nth set bit inside the bit vector More...

int	bitvec_set_bit_pos (struct bitvec *bv, unsigned int bitnr, enum bit_value bit)
	set a bit at given position in a bit vector More...

int	bitvec_set_bit (struct bitvec *bv, enum bit_value bit)
	set the next bit inside a bitvec More...

int	bitvec_get_bit_high (struct bitvec *bv)
	get the next bit (low/high) inside a bitvec More...

int	bitvec_set_bits (struct bitvec bv, const enum bit_value bits, unsigned int count)
	set multiple bits (based on array of bitvals) at current pos More...

int	bitvec_set_u64 (struct bitvec *bv, uint64_t v, uint8_t num_bits, bool use_lh)
	set multiple bits (based on numeric value) at current pos. More...

int	bitvec_set_uint (struct bitvec *bv, unsigned int ui, unsigned int num_bits)
	set multiple bits (based on numeric value) at current pos. More...

int	bitvec_get_uint (struct bitvec *bv, unsigned int num_bits)
	get multiple bits (based on numeric value) from current pos More...

int	bitvec_find_bit_pos (const struct bitvec *bv, unsigned int n, enum bit_value val)
	find first bit set in bit vector More...

int	bitvec_spare_padding (struct bitvec *bv, unsigned int up_to_bit)
	pad all remaining bits up to a given bit number More...

int	bitvec_get_bytes (struct bitvec bv, uint8_t bytes, unsigned int count)
	get multiple bytes from current pos Assumes MSB first encoding. More...

int	bitvec_set_bytes (struct bitvec bv, const uint8_t bytes, unsigned int count)
	set multiple bytes at current pos Assumes MSB first encoding. More...

struct bitvec *	bitvec_alloc (unsigned int size, void *ctx)
	Allocate a bit vector. More...

void	bitvec_free (struct bitvec *bv)
	Free a bit vector (release its memory) More...

int	bitvec_unhex (struct bitvec bv, const char src)
	read hexadecimap string into a bit vector More...

unsigned int	bitvec_pack (const struct bitvec bv, uint8_t buffer)
	Export a bit vector to a buffer. More...

unsigned int	bitvec_unpack (struct bitvec bv, const uint8_t buffer)
	Copy buffer of unpacked bits into bit vector. More...

uint64_t	bitvec_read_field (struct bitvec bv, unsigned int read_index, unsigned int len)
	read part of the vector More...

int	bitvec_write_field (struct bitvec bv, unsigned int write_index, uint64_t val, unsigned int len)
	write into the vector More...

int	bitvec_fill (struct bitvec *bv, unsigned int num_bits, enum bit_value fill)
	fill num_bits with \fill starting from the current position More...

char	bit_value_to_char (enum bit_value v)
	convert enum to corresponding character More...

void	bitvec_to_string_r (const struct bitvec bv, char str)
	prints bit vector to provided string It's caller's responsibility to ensure that we won't shoot him in the foot: the provided buffer should be at lest cur_bit + 1 bytes long More...

void	bitvec_zero (struct bitvec *bv)
	force bit vector to all 0 and current bit to the beginnig of the vector More...

unsigned	bitvec_rl (const struct bitvec *bv, bool b)
	Return number (bits) of uninterrupted bit run in vector starting from the MSB. More...

unsigned	bitvec_rl_curbit (struct bitvec *bv, bool b, unsigned int max_bits)
	Return number (bits) of uninterrupted bit run in vector starting from the current bit. More...

void	bitvec_shiftl (struct bitvec *bv, unsigned int n)

int16_t	bitvec_get_int16_msb (const struct bitvec *bv, unsigned int num_bits)
	get multiple bits (num_bits) from beginning of vector (MSB side) More...

unsigned int	bitvec_add_array (struct bitvec bv, const uint32_t array, unsigned int array_len, bool dry_run, unsigned int num_bits)
	Add given array to bitvec. More...

static unsigned int	bitvec_used_bytes (const struct bitvec *bv)
	Return the number of bytes used within the bit vector. More...

static unsigned int	bitvec_tailroom_bits (const struct bitvec *bv)
	Return the tailroom in number of unused bits remaining in the bit-vector. More...

static unsigned int	bytenum_from_bitnum (unsigned int bitnum)

static uint8_t	bitval2mask (enum bit_value bit, uint8_t bitnum)

static unsigned	leading_bits (uint8_t x, bool b)

void	bitvec_shiftl (struct bitvec *bv, unsigned n)
	Shifts bitvec to the left, n MSB bits lost. More...

Detailed Description

Osmocom bit vector abstraction utility routines.

These functions assume a MSB (most significant bit) first layout of the bits, so that for instance the 5 bit number abcde (a is MSB) can be embedded into a byte sequence like in xxxxxxab cdexxxxx. The bit count starts with the MSB, so the bits in a byte are numbered (MSB) 01234567 (LSB). Note that there are other incompatible encodings, like it is used for the EGPRS RLC data block headers (there the bits are numbered from LSB to MSB).

Macro Definition Documentation

◆ BITNUM_FROM_COMP

#define BITNUM_FROM_COMP	(	byte,
		bit
	)	((byte*8)+bit)

Enumeration Type Documentation

◆ bit_value

enum bit_value

A single GSM bit.

In GSM mac blocks, every bit can be 0 or 1, or L or H. L/H are defined relative to the 0x2b padding pattern

Enumerator
ZERO	A zero (0) bit.
ONE	A one (1) bit.
L	A CSN.1 "L" bit.
H	A CSN.1 "H" bit.

Function Documentation

◆ bit_value_to_char()

char bit_value_to_char ( enum bit_value v )

convert enum to corresponding character

Parameters

v	input value (bit)

Returns: single character, either 0, 1, L or H

References H, L, ONE, osmo_panic(), and ZERO.

Referenced by bitvec_to_string_r().

◆ bitval2mask()

static uint8_t bitval2mask	(	enum bit_value	bit,
		uint8_t	bitnum
	)

static

References H, L, ONE, and ZERO.

Referenced by bitvec_get_bit_pos(), bitvec_get_bit_pos_high(), and bitvec_set_bit_pos().

◆ bitvec_add_array()

unsigned int bitvec_add_array	(	struct bitvec *	bv,
		const uint32_t *	array,
		unsigned int	array_len,
		bool	dry_run,
		unsigned int	num_bits
	)

Add given array to bitvec.

Parameters

[in,out]	bv	bit vector to work with
[in]	array	elements to be added
[in]	array_len	length of array
[in]	dry_run	indicates whether to return number of bits required instead of adding anything to bv for real
[in]	num_bits	number of bits to consider in each element of array

Returns: number of bits necessary to add array elements if dry_run is true, 0 otherwise (only in this case bv is actually changed)

N. B: no length checks are performed on bv - it's caller's job to ensure enough space is available - for example by calling with dry_run = true first.

Useful for common pattern in CSN.1 spec which looks like: { 1 < XXX : bit (num_bits) > } ** 0 which means repeat any times (between 0 and infinity), start each repetition with 1, mark end of repetitions with 0 bit see app. note in 3GPP TS 24.007 § B.2.1 Rule A2

References bitvec_set_bit(), and bitvec_set_uint().

◆ bitvec_alloc()

struct bitvec * bitvec_alloc	(	unsigned int	size,
		void *	ctx
	)

Allocate a bit vector.

Parameters

[in]	size	Number of bytes in the vector
[in]	ctx	Context from which to allocate

Returns: pointer to allocated vector; NULL in case of error

References cur_bit, data, and data_len.

◆ bitvec_fill()

int bitvec_fill	(	struct bitvec *	bv,
		unsigned int	num_bits,
		enum bit_value	fill
	)

fill num_bits with \fill starting from the current position

Returns: 0 on success; negative otherwise (out of vector boundary)

References bitvec_set_bit(), and cur_bit.

Referenced by bitvec_spare_padding().

◆ bitvec_find_bit_pos()

int bitvec_find_bit_pos	(	const struct bitvec *	bv,
		unsigned int	n,
		enum bit_value	val
	)

find first bit set in bit vector

Returns: 0 on success; negative otherwise

References bitvec_get_bit_pos(), data_len, and n.

◆ bitvec_free()

void bitvec_free ( struct bitvec * bv )

Free a bit vector (release its memory)

Parameters

[in] bit vector to free

References data.

◆ bitvec_get_bit_high()

int bitvec_get_bit_high ( struct bitvec * bv )

get the next bit (low/high) inside a bitvec

Returns: value of th next bit in the vector

References bitvec_get_bit_pos_high(), and cur_bit.

◆ bitvec_get_bit_pos()

enum bit_value bitvec_get_bit_pos	(	const struct bitvec *	bv,
		unsigned int	bitnr
	)

check if the bit is 0 or 1 for a given position inside a bitvec

Parameters

[in]	bv	the bit vector on which to check
[in]	bitnr	the bit number inside the bit vector to check

Returns: value of the requested bit

References bitval2mask(), bytenum_from_bitnum(), data, data_len, ONE, and ZERO.

Referenced by bitvec_find_bit_pos(), bitvec_get_nth_set_bit(), bitvec_get_uint(), and bitvec_to_string_r().

◆ bitvec_get_bit_pos_high()

enum bit_value bitvec_get_bit_pos_high	(	const struct bitvec *	bv,
		unsigned int	bitnr
	)

check if the bit is L or H for a given position inside a bitvec

Parameters

[in]	bv	the bit vector on which to check
[in]	bitnr	the bit number inside the bit vector to check

Returns: value of the requested bit

References bitval2mask(), bytenum_from_bitnum(), data, data_len, H, and L.

Referenced by bitvec_get_bit_high().

◆ bitvec_get_bytes()

int bitvec_get_bytes	(	struct bitvec *	bv,
		uint8_t *	bytes,
		unsigned int	count
	)

get multiple bytes from current pos Assumes MSB first encoding.

Parameters

[in]	bv	bit vector
[in]	bytes	array
[in]	count	number of bytes to copy

Returns: 0 on success; negative otherwise

References bytenum_from_bitnum(), c, cur_bit, data, and data_len.

◆ bitvec_get_int16_msb()

int16_t bitvec_get_int16_msb	(	const struct bitvec *	bv,
		unsigned int	num_bits
	)

get multiple bits (num_bits) from beginning of vector (MSB side)

Returns: 16bit signed integer retrieved from bit vector

References cur_bit, data, and osmo_load16be().

◆ bitvec_get_nth_set_bit()

unsigned int bitvec_get_nth_set_bit	(	const struct bitvec *	bv,
		unsigned int	n
	)

get the Nth set bit inside the bit vector

Parameters

[in]	bv	the bit vector to use
[in]	n	the bit number to get

Returns: the bit number (offset) of the Nth set bit in bv

References bitvec_get_bit_pos(), data_len, k, n, and ONE.

◆ bitvec_get_uint()

int bitvec_get_uint	(	struct bitvec *	bv,
		unsigned int	num_bits
	)

get multiple bits (based on numeric value) from current pos

Returns: integer value retrieved from bit vector

References bitvec_get_bit_pos(), and cur_bit.

◆ bitvec_pack()

unsigned int bitvec_pack	(	const struct bitvec *	bv,
		uint8_t *	buffer
	)

Export a bit vector to a buffer.

Parameters

[in]	bitvec	(unpacked bits)
[out]	buffer	for the unpacked bits

Returns: number of bytes (= bits) copied

References data, and data_len.

◆ bitvec_read_field()

uint64_t bitvec_read_field	(	struct bitvec *	bv,
		unsigned int *	read_index,
		unsigned int	len
	)

read part of the vector

Parameters

[in]	bv	The boolean vector to work on
[in,out]	read_index	Where reading supposed to start in the vector
[in]	len	How many bits to read from vector

Returns: An integer made up of the bits read.

In case of an error, errno is set to a non-zero value. Otherwise it holds 0.

References bytenum_from_bitnum(), cur_bit, data, data_len, and len().

Referenced by bitvec_rl_curbit().

◆ bitvec_rl()

unsigned bitvec_rl	(	const struct bitvec *	bv,
		bool	b
	)

Return number (bits) of uninterrupted bit run in vector starting from the MSB.

Parameters

[in]	bv	The boolean vector to work on
[in]	b	The boolean, sequence of which is looked at from the vector start

Returns: Number of consecutive bits of b in bv

References cur_bit, data, and leading_bits().

Referenced by osmo_t4_encode().

◆ bitvec_rl_curbit()

unsigned bitvec_rl_curbit	(	struct bitvec *	bv,
		bool	b,
		unsigned int	max_bits
	)

Return number (bits) of uninterrupted bit run in vector starting from the current bit.

Parameters

[in]	bv	The boolean vector to work on
[in]	b	The boolean, sequence of 1's or 0's to be checked
[in]	max_bits	Total Number of Uncmopresed bits

Returns: Number of consecutive bits of b in bv and cur_bit will \go to cur_bit + number of consecutive bit

References bitvec_read_field(), cur_bit, data, and leading_bits().

◆ bitvec_set_bit()

int bitvec_set_bit	(	struct bitvec *	bv,
		enum bit_value	bit
	)

inline

set the next bit inside a bitvec

Parameters

[in]	bv	bit vector to be used
[in]	bit	value of the bit to be set

Returns: 0 on success, negative value on error

References bitvec_set_bit_pos(), and cur_bit.

Referenced by bitvec_add_array(), bitvec_fill(), bitvec_set_bits(), and bitvec_set_u64().

◆ bitvec_set_bit_pos()

int bitvec_set_bit_pos	(	struct bitvec *	bv,
		unsigned int	bitnr,
		enum bit_value	bit
	)

inline

set a bit at given position in a bit vector

Parameters

[in]	bv	bit vector on which to operate
[in]	bitnr	number of bit to be set
[in]	bit	value to which the bit is to be set

Returns: 0 on success, negative value on error

References bitval2mask(), bytenum_from_bitnum(), data, data_len, and ONE.

Referenced by bitvec_set_bit().

◆ bitvec_set_bits()

int bitvec_set_bits	(	struct bitvec *	bv,
		const enum bit_value *	bits,
		unsigned int	count
	)

set multiple bits (based on array of bitvals) at current pos

Parameters

[in]	bv	bit vector
[in]	bits	array of bit_value
[in]	count	number of bits to set

Returns: 0 on success; negative in case of error

References bitvec_set_bit().

◆ bitvec_set_bytes()

int bitvec_set_bytes	(	struct bitvec *	bv,
		const uint8_t *	bytes,
		unsigned int	count
	)

set multiple bytes at current pos Assumes MSB first encoding.

Parameters

[in]	bv	bit vector
[in]	bytes	array
[in]	count	number of bytes to copy

Returns: 0 on success; negative otherwise

References bytenum_from_bitnum(), c, cur_bit, data, and data_len.

◆ bitvec_set_u64()

int bitvec_set_u64	(	struct bitvec *	bv,
		uint64_t	v,
		uint8_t	num_bits,
		bool	use_lh
	)

set multiple bits (based on numeric value) at current pos.

Parameters

[in]	bv	bit vector.
[in]	v	mask representing which bits needs to be set.
[in]	num_bits	number of meaningful bits in the mask.
[in]	use_lh	whether to interpret the bits as L/H values or as 0/1.

Returns: 0 on success; negative in case of error.

References bitvec_set_bit(), H, and L.

Referenced by bitvec_set_uint(), and bitvec_write_field().

◆ bitvec_set_uint()

int bitvec_set_uint	(	struct bitvec *	bv,
		unsigned int	ui,
		unsigned int	num_bits
	)

set multiple bits (based on numeric value) at current pos.

Returns: 0 in case of success; negative in case of error.

References bitvec_set_u64().

Referenced by bitvec_add_array(), and t4_rle().

◆ bitvec_shiftl() [1/2]

void bitvec_shiftl	(	struct bitvec *	bv,
		unsigned int	n
	)

Referenced by osmo_t4_encode().

◆ bitvec_shiftl() [2/2]

void bitvec_shiftl	(	struct bitvec *	bv,
		unsigned	n
	)

Shifts bitvec to the left, n MSB bits lost.

References bitvec_zero(), cur_bit, data, data_len, n, osmo_load16be(), and osmo_store16be().

◆ bitvec_spare_padding()

int bitvec_spare_padding	(	struct bitvec *	bv,
		unsigned int	up_to_bit
	)

pad all remaining bits up to a given bit number

Returns: 0 on success; negative otherwise

References bitvec_fill(), cur_bit, L, and n.

◆ bitvec_tailroom_bits()

static unsigned int bitvec_tailroom_bits ( const struct bitvec * bv )

inlinestatic

Return the tailroom in number of unused bits remaining in the bit-vector.

References cur_bit, and data_len.

◆ bitvec_to_string_r()

void bitvec_to_string_r	(	const struct bitvec *	bv,
		char *	str
	)

prints bit vector to provided string It's caller's responsibility to ensure that we won't shoot him in the foot: the provided buffer should be at lest cur_bit + 1 bytes long

References bit_value_to_char(), bitvec_get_bit_pos(), and cur_bit.

◆ bitvec_unhex()

int bitvec_unhex	(	struct bitvec *	bv,
		const char *	src
	)

read hexadecimap string into a bit vector

Parameters

[in]	src	string containing hex digits
[out]	bv	unpacked bit vector

Returns: 0 in case of success; 1 in case of error

References cur_bit, data, data_len, and osmo_hexparse().

◆ bitvec_unpack()

unsigned int bitvec_unpack	(	struct bitvec *	bv,
		const uint8_t *	buffer
	)

Copy buffer of unpacked bits into bit vector.

Parameters

[in]	buffer	unpacked input bits
[out]	bv	unpacked bit vector

Returns: number of bytes (= bits) copied

References data, and data_len.

◆ bitvec_used_bytes()

static unsigned int bitvec_used_bytes ( const struct bitvec * bv )

inlinestatic

Return the number of bytes used within the bit vector.

References cur_bit.

◆ bitvec_write_field()

int bitvec_write_field	(	struct bitvec *	bv,
		unsigned int *	write_index,
		uint64_t	val,
		unsigned int	len
	)

write into the vector

Parameters

[in]	bv	The boolean vector to work on
[in,out]	write_index	Where writing supposed to start in the vector
[in]	len	How many bits to write

Returns: 0 on success, negative value on error

References bitvec_set_u64(), cur_bit, and len().

◆ bitvec_zero()

void bitvec_zero ( struct bitvec * bv )

force bit vector to all 0 and current bit to the beginnig of the vector

References cur_bit, data, and data_len.

Referenced by bitvec_shiftl(), and osmo_t4_encode().

◆ bytenum_from_bitnum()

static unsigned int bytenum_from_bitnum ( unsigned int bitnum )

inlinestatic

Referenced by bitvec_get_bit_pos(), bitvec_get_bit_pos_high(), bitvec_get_bytes(), bitvec_read_field(), bitvec_set_bit_pos(), and bitvec_set_bytes().

◆ leading_bits()

static unsigned leading_bits	(	uint8_t	x,
		bool	b
	)

inlinestatic

References x.

Referenced by bitvec_rl(), and bitvec_rl_curbit().

Files

Data Structures

Macros

Enumerations

Functions

Detailed Description

Macro Definition Documentation

◆ BITNUM_FROM_COMP

Enumeration Type Documentation

◆ bit_value

Function Documentation

◆ bit_value_to_char()

◆ bitval2mask()

◆ bitvec_add_array()

◆ bitvec_alloc()

◆ bitvec_fill()

◆ bitvec_find_bit_pos()

◆ bitvec_free()

◆ bitvec_get_bit_high()

◆ bitvec_get_bit_pos()

◆ bitvec_get_bit_pos_high()

◆ bitvec_get_bytes()

◆ bitvec_get_int16_msb()

◆ bitvec_get_nth_set_bit()

◆ bitvec_get_uint()

◆ bitvec_pack()

◆ bitvec_read_field()

◆ bitvec_rl()

◆ bitvec_rl_curbit()

◆ bitvec_set_bit()

◆ bitvec_set_bit_pos()

◆ bitvec_set_bits()

◆ bitvec_set_bytes()

◆ bitvec_set_u64()

◆ bitvec_set_uint()

◆ bitvec_shiftl() [1/2]

◆ bitvec_shiftl() [2/2]

◆ bitvec_spare_padding()

◆ bitvec_tailroom_bits()

◆ bitvec_to_string_r()

◆ bitvec_unhex()

◆ bitvec_unpack()

◆ bitvec_used_bytes()

◆ bitvec_write_field()

◆ bitvec_zero()

◆ bytenum_from_bitnum()

◆ leading_bits()