libosmocore 0.9.6-23.20170220git32ee5af8.fc42
Osmocom core library
Loading...
Searching...
No Matches
Bit vectors

Files

file  bitvec.h
 Osmocom bit vector abstraction.
 
file  bitvec.c
 Osmocom bit vector abstraction.
 

Data Structures

struct  bitvec
 structure describing a bit vector More...
 

Macros

#define BITNUM_FROM_COMP(byte, bit)
 

Enumerations

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

Functions

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
 
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
 
unsigned int bitvec_get_nth_set_bit (const struct bitvec *bv, unsigned int n)
 get the Nth set bit inside the bit vector
 
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
 
int bitvec_set_bit (struct bitvec *bv, enum bit_value bit)
 set the next bit inside a bitvec
 
int bitvec_get_bit_high (struct bitvec *bv)
 get the next bit (low/high) inside a bitvec
 
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
 
int bitvec_set_uint (struct bitvec *bv, unsigned int ui, unsigned int num_bits)
 set multiple bits (based on numeric value) at current pos
 
int bitvec_get_uint (struct bitvec *bv, unsigned int num_bits)
 get multiple bits (based on numeric value) from current pos
 
int bitvec_find_bit_pos (const struct bitvec *bv, unsigned int n, enum bit_value val)
 find first bit set in bit vector
 
int bitvec_spare_padding (struct bitvec *bv, unsigned int up_to_bit)
 pad all remaining bits up to num_bits
 
int bitvec_get_bytes (struct bitvec *bv, uint8_t *bytes, unsigned int count)
 get multiple bytes from current pos Assumes MSB first encoding.
 
int bitvec_set_bytes (struct bitvec *bv, const uint8_t *bytes, unsigned int count)
 set multiple bytes at current pos Assumes MSB first encoding.
 
struct bitvecbitvec_alloc (unsigned int size, TALLOC_CTX *ctx)
 Allocate a bit vector.
 
void bitvec_free (struct bitvec *bv)
 Free a bit vector (release its memory)
 
int bitvec_unhex (struct bitvec *bv, const char *src)
 read hexadecimap string into a bit vector
 
unsigned int bitvec_pack (const struct bitvec *bv, uint8_t *buffer)
 Export a bit vector to a buffer.
 
unsigned int bitvec_unpack (struct bitvec *bv, const uint8_t *buffer)
 Copy buffer of unpacked bits into bit vector.
 
uint64_t bitvec_read_field (struct bitvec *bv, unsigned int *read_index, unsigned int len)
 read part of the vector
 
int bitvec_write_field (struct bitvec *bv, unsigned int *write_index, uint64_t val, unsigned int len)
 write into the vector
 
int bitvec_fill (struct bitvec *bv, unsigned int num_bits, enum bit_value fill)
 fill num_bits with \fill starting from the current position
 
char bit_value_to_char (enum bit_value v)
 convert enum to corresponding character
 
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
 
void bitvec_zero (struct bitvec *bv)
 force bit vector to all 0 and current bit to the beginnig of the vector
 
unsigned bitvec_rl (const struct bitvec *bv, bool b)
 Return number (bits) of uninterrupted bit run in vector starting from the MSB.
 
unsigned bitvec_rl_curbit (struct bitvec *bv, bool b, int max_bits)
 Return number (bits) of uninterrupted bit run in vector starting from the current bit.
 
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)
 
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.
 
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.
 

Detailed Description

Macro Definition Documentation

◆ BITNUM_FROM_COMP

#define BITNUM_FROM_COMP ( byte,
bit )
Value:
((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.

A CSN.1 "L" bit.

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
vinput value (bit)
Returns
single character, either 0, 1, L or H

References H, L, ONE, and ZERO.

Referenced by bitvec_to_string_r().

◆ 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]bvbit vector to work with
[in]arrayelements to be added
[in]array_lenlength of array
[in]dry_runindicates whether to return number of bits required instead of adding anything to bv for real
[in]num_bitsnumber 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,
TALLOC_CTX * ctx )

Allocate a bit vector.

Parameters
[in]sizeNumber of bits in the vector
[in]ctxContext 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(), and data_len.

◆ bitvec_free()

void bitvec_free ( struct bitvec * bv)

Free a bit vector (release its memory)

Parameters
[in]bitvector 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]bvthe bit vector on which to check
[in]bitnrthe bit number inside the bit vector to check
Returns
value of the requested bit

References data, data_len, ONE, and ZERO.

Referenced by bitvec_find_bit_pos(), bitvec_get_nth_set_bit(), bitvec_get_uint(), bitvec_read_field(), 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]bvthe bit vector on which to check
[in]bitnrthe bit number inside the bit vector to check
Returns
value of the requested bit

References 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]bvbit vector
[in]bytesarray
[in]countnumber of bytes to copy
Returns
0 on success; negative otherwise

References 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, and data.

◆ 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]bvthe bit vector to use
[in]nthe bit number to get
Returns
the bit number (offset) of the Nth set bit in bv

References bitvec_get_bit_pos(), data_len, 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]bufferfor 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]bvThe boolean vector to work on
[in,out]read_indexWhere reading supposed to start in the vector
[in]lenHow many bits to read from vector
Returns
read bits or negative value on error

References bitvec_get_bit_pos(), and cur_bit.

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]bvThe boolean vector to work on
[in]bThe boolean, sequence of which is looked at from the vector start
Returns
Number of consecutive bits of b in bv

References cur_bit, and data.

Referenced by osmo_t4_encode().

◆ bitvec_rl_curbit()

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

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

Parameters
[in]bvThe boolean vector to work on
[in]bThe boolean, sequence of 1's or 0's to be checked
[in]max_bitsTotal 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, and data.

◆ bitvec_set_bit()

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

set the next bit inside a bitvec

Parameters
[in]bvbit vector to be used
[in]bitvalue 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(), bitvec_set_uint(), and bitvec_write_field().

◆ 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]bvbit vector on which to operate
[in]bitnrnumber of bit to be set
[in]bitvalue to which the bit is to be set
Returns
0 on success, negative value on error

References 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]bvbit vector
[in]bitsarray of bit_value
[in]countnumber 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]bvbit vector
[in]bytesarray
[in]countnumber of bytes to copy
Returns
0 on success; negative otherwise

References cur_bit, data, and data_len.

◆ 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_bit().

Referenced by bitvec_add_array(), and t4_rle().

◆ bitvec_spare_padding()

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

pad all remaining bits up to num_bits

Returns
0 on success; negative otherwise

References bitvec_fill(), cur_bit, and L.

◆ bitvec_unhex()

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

read hexadecimap string into a bit vector

Parameters
[in]srcstring containing hex digits
[out]bvunpacked bit vector
Returns
0 in case of success; 1 in case of error

References bitvec_write_field(), and data_len.

◆ bitvec_unpack()

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

Copy buffer of unpacked bits into bit vector.

Parameters
[in]bufferunpacked input bits
[out]bvunpacked bit vector
Returns
number of bytes (= bits) copied

References data, and data_len.

◆ 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]bvThe boolean vector to work on
[in,out]write_indexWhere writing supposed to start in the vector
[in]lenHow many bits to write
Returns
next write index or negative value on error

References bitvec_set_bit(), and cur_bit.

Referenced by bitvec_unhex().