Utility Functions

Keywords: utility bit byte pack unpack repack shift

The utility module contains useful functions, primarily for bit fast bit manipulation. This includes packing/unpacking byte arrays, counting ones in an integer, computing a binary dot-product, and others.

liquid_pack_bytes(), liquid_unpack_bytes(), and liquid_repack_bytes()

Byte packing is used extensively in the fec ([ref:section-fec] ) and framing ([ref:section-framing] ) modules. These methods resize symbols represented by various numbers of bits. This is necessary to move between raw data arrays which use full bytes (eight bits per symbol) to methods expecting symbols of different sizes. In particular, the liquid_repack_bytes() method is useful when one wants to transmit a block of 64 data bytes using an 8-PSK modem which requires a 3-bit input symbol. For example repacking two 8-bit symbols 00000000 , 11111111 into six 3-bit symbols gives 000 , 000 , 001 , 111 , 111 , 100 . Because 16 bits cannot be divided evenly among 3-bit symbols, the last symbol is padded with zeros.

liquid_pack_array(), liquid_unpack_array()

The liquid_pack_array() and liquid_unpack_array() methods pack an array with symbols of arbitrary length. These methods are similar to those in[ref:section-utility-pack_bytes] but are capable of packing symbols of any arbitrary length. These are convenient for digital modulation and demodulation of a block of symbols with different modulation schemes. For example packing an array with five symbols 1000 , 011 , 11010 , 1 , 000 yields two bytes: 10000111,10101000 . Here are the basic interfaces for packing and unpacking arrays:

// pack binary array with symbol(s)
void liquid_pack_array(unsigned char * _src,        // source array [size- _n x 1]
                       unsigned int _n,             // input source array length
                       unsigned int _k,             // bit index to write in _src
                       unsigned int _b,             // number of bits in input symbol
                       unsigned char _sym_in);      // input symbol

// unpack symbols from binary array
void liquid_unpack_array(unsigned char * _src,      // source array [size- _n x 1]
                         unsigned int _n,           // input source array length
                         unsigned int _k,           // bit index to write in _src
                         unsigned int _b,           // number of bits in output symbol
                         unsigned char * _sym_out); // output symbol

Listed below is a simple example of packing symbols of varying lengths into a fixed array of bytes;

#include <liquid/liquid.h>

int main() {
    unsigned int sym_size[9] = {8, 2, 3, 6, 1, 3, 3, 4, 3};
    unsigned char input[9] = {
        0x81,   // 1000 0001
        0x03,   //        11
        0x05,   //       101
        0x3a,   //   11 1010
        0x01,   //         1
        0x07,   //       111
        0x06,   //       110
        0x0a,   //      1010
        0x04    //     10[0] <- last bit is stripped
    };

    unsigned char output[4];

    unsigned int k=0;
    unsigned int i;
    for (i=0; i<9; i++) {
        liquid_pack_array(output, 4, k, sym_size[i], input[i]);
        k += sym_size[i];
    }
    // output       : 1000 0001 1110 1111 0101 1111 1010 1010
    // symbol       : 0000 0000 1122 2333 3334 5556 6677 7788
    // output is now {0x81, 0xEF, 0x5F, 0xAA};
}

liquid_lbshift(), liquid_rbshift()

Binary shifting.

liquid_lbshift()

// input        : 1000 0001 1110 1111 0101 1111 1010 1010
// output [0]   : 1000 0001 1110 1111 0101 1111 1010 1010
// output [1]   : 0000 0011 1101 1110 1011 1111 0101 0100
// output [2]   : 0000 0111 1011 1101 0111 1110 1010 1000
// output [3]   : 0000 1111 0111 1010 1111 1101 0101 0000
// output [4]   : 0001 1110 1111 0101 1111 1010 1010 0000
// output [5]   : 0011 1101 1110 1011 1111 0101 0100 0000
// output [6]   : 0111 1011 1101 0111 1110 1010 1000 0000
// output [7]   : 1111 0111 1010 1111 1101 0101 0000 0000

liquid_rbshift()

// input        : 1000 0001 1110 1111 0101 1111 1010 1010
// output [0]   : 1000 0001 1110 1111 0101 1111 1010 1010
// output [1]   : 0100 0000 1111 0111 1010 1111 1101 0101
// output [2]   : 0010 0000 0111 1011 1101 0111 1110 1010
// output [3]   : 0001 0000 0011 1101 1110 1011 1111 0101
// output [4]   : 0000 1000 0001 1110 1111 0101 1111 1010
// output [5]   : 0000 0100 0000 1111 0111 1010 1111 1101
// output [6]   : 0000 0010 0000 0111 1011 1101 0111 1110
// output [7]   : 0000 0001 0000 0011 1101 1110 1011 1111

liquid_lbcircshift(), liquid_rbcircshift()

Binary circular shifting.

liquid_lbcircshift()

// input        : 1001 0001 1110 1111 0101 1111 1010 1010
// output [0]   : 1001 0001 1110 1111 0101 1111 1010 1010
// output [1]   : 0010 0011 1101 1110 1011 1111 0101 0101
// output [2]   : 0100 0111 1011 1101 0111 1110 1010 1010
// output [3]   : 1000 1111 0111 1010 1111 1101 0101 0100
// output [4]   : 0001 1110 1111 0101 1111 1010 1010 1001
// output [5]   : 0011 1101 1110 1011 1111 0101 0101 0010
// output [6]   : 0111 1011 1101 0111 1110 1010 1010 0100
// output [7]   : 1111 0111 1010 1111 1101 0101 0100 1000

liquid_rbcircshift()

// input        : 1001 0001 1110 1111 0101 1111 1010 1010
// output [0]   : 1001 0001 1110 1111 0101 1111 1010 1010
// output [1]   : 0100 1000 1111 0111 1010 1111 1101 0101
// output [2]   : 1010 0100 0111 1011 1101 0111 1110 1010
// output [3]   : 0101 0010 0011 1101 1110 1011 1111 0101
// output [4]   : 1010 1001 0001 1110 1111 0101 1111 1010
// output [5]   : 0101 0100 1000 1111 0111 1010 1111 1101
// output [6]   : 1010 1010 0100 0111 1011 1101 0111 1110
// output [7]   : 0101 0101 0010 0011 1101 1110 1011 1111

liquid_lshift(), liquid_rshift()

Byte-wise shifting.

liquid_lshift()

// input        : 1000 0001 1110 1111 0101 1111 1010 1010
// output [0]   : 1000 0001 1110 1111 0101 1111 1010 1010
// output [1]   : 1110 1111 0101 1111 1010 1010 0000 0000
// output [2]   : 0101 1111 1010 1010 0000 0000 0000 0000
// output [3]   : 1010 1010 0000 0000 0000 0000 0000 0000
// output [4]   : 0000 0000 0000 0000 0000 0000 0000 0000

liquid_rshift()

// input        : 1000 0001 1110 1111 0101 1111 1010 1010
// output [0]   : 1000 0001 1110 1111 0101 1111 1010 1010
// output [1]   : 0000 0000 1000 0001 1110 1111 0101 1111
// output [2]   : 0000 0000 0000 0000 1000 0001 1110 1111
// output [3]   : 0000 0000 0000 0000 0000 0000 1000 0001
// output [4]   : 0000 0000 0000 0000 0000 0000 0000 0000

liquid_lcircshift(), liquid_rcircshift()

Byte-wise circular shifting.

liquid_lcircshift()

// input        : 1000 0001 1110 1111 0101 1111 1010 1010
// output [0]   : 1000 0001 1110 1111 0101 1111 1010 1010
// output [1]   : 1110 1111 0101 1111 1010 1010 1000 0001
// output [2]   : 0101 1111 1010 1010 1000 0001 1110 1111
// output [3]   : 1010 1010 1000 0001 1110 1111 0101 1111
// output [4]   : 1000 0001 1110 1111 0101 1111 1010 1010

liquid_rcircshift()

// input        : 1000 0001 1110 1111 0101 1111 1010 1010
// output [0]   : 1000 0001 1110 1111 0101 1111 1010 1010
// output [1]   : 1010 1010 1000 0001 1110 1111 0101 1111
// output [2]   : 0101 1111 1010 1010 1000 0001 1110 1111
// output [3]   : 1110 1111 0101 1111 1010 1010 1000 0001
// output [4]   : 1000 0001 1110 1111 0101 1111 1010 1010

miscellany

This section describes the bit-counting methods which are used extensively throughout liquid , particularly the fec ([ref:section-fec] ) and sequence ([ref:section-sequence] ) modules. Integer sizes vary for different machines; when liquid is initially configured (see [ref:section-installation] ), the size of the integer is computed such that the fastest method can be computed without performing unnecessary loop iterations or comparisons.

  • liquid_count_ones(x) counts the number of 1 s that exist in the integer \(x\) . For example, the number 237 is represented in binary as 11101101 , therefore liquid_count_ones(237) returns 6 .
  • liquid_count_ones_mod2(x) counts the number of 1 s that exist in the integer \(x\) , modulo 2; in other words, it returns 1 if the number of ones in \(x\) is odd, 0 if the number is even. For example, liquid_count_ones_mod2(237) return 0 .
  • liquid_bdotprod(x,y) computes the binary dot-product between two integers \(x\) and \(y\) as the sum of ones in \(x \land y\) , modulo 2 (where \(\land\) is the logical and operation). This is useful in linear feedback shift registers (see [ref:section-sequence-msequence] on \(m\) -sequences) as well as certain forward error-correction codes (see [ref:section-fec-hamming] on Hamming codes). For example, the binary dot product between 10110011 and 11101110 is 1 because 10110011 \(\land\) 11101110 \(=\) 10100010 which has an odd number of 1 s.
  • liquid_count_leading_zeros(x) counts the number of leading zeros in the integer \(x\) . This is dependent upon the size of the integer for the target machine which is usually either two or four bytes.
  • liquid_msb_index(x) computes the index of the most-significant bit in the integer \(x\) . The function will return 0 for \(x=0\) . For example if \(x=129\) ( 10000001 ), the function will return 8 .