How can I store variable length codes sequentially in memory?

Question

Say I have a two dimensional array where each entry contains a length and a value:

int array[4][2] =  { /* {length, value}, */
                   {5, 3},
                   {6, 7},
                   {1, 0},
                   {8, 15},
                   };

I want to store them sequentially into memory with leading zeros to make each field the appropriate length. The example above would be:

    00011 000111 0 00001111

The first block is five bits long and stores decimal 3. The second block is six bits long and stores decimal seven. The third block is one bit long and stores decimal 0, and the last block is eight bits long and stores decimal 15.

I can do it with some bitwise manipulation but I thought I would ask to see if there is an easier way.

I am coding in C for a Tensilica 32-bit RISC processor.

The purpose is to write a sequence of Exponential-Golomb codes.

EDIT: SOLUTION:

int main(int argc, char *argv[])
{
    unsigned int i = 0, j = 0;
    unsigned char bit = 0;
    unsigned int bit_num = 0;
    unsigned int field_length_bits = 0;
    unsigned int field_length_bytes = 0;
    unsigned int field_array_length = 0;
    unsigned int field_list[NUM_FIELDS][2] = {
                                            /*{Length, Value},*/ 
                                            {4,  3},
                                            {5,  5},
                                            {6,  9},
                                            {7,  11},
                                            {8,  13},
                                            {9, 15},
                                            {10, 17},
                                         };

    unsigned char *seq_array;

    // Find total length of field list in bits
    for (i = 0; i < NUM_FIELDS; i++) 
        field_length_bits += field_list[i][LENGTH];

    // Number of bytes needed to store FIELD parameters
    for (i = 0; i < (field_length_bits + i) % 8 != 0; i++) ;

    field_length_bytes = (field_length_bits + i) / 8;

    // Size of array we need to allocate (multiple of 4 bytes)
    for (i = 0; (field_length_bytes + i) % 4 != 0; i++) ;

    field_array_length = (field_length_bytes + i);

    // Allocate memory
    seq_array = (unsigned char *) calloc(field_array_length, sizeof(unsigned char));

    // Traverse source and set destination
    for(i = 0; i < NUM_FIELDS; i++)
    {
        for(j = 0; j < field_list[i][LENGTH]; j++)
        {
            bit = 0x01 & (field_list[i][VALUE] >> (field_list[i][LENGTH] - j - 1));
            if (bit)
                setBit(seq_array, field_array_length, bit_num, 1);
            else
                setBit(seq_array, field_array_length, bit_num, 0);
            bit_num++;

        }
    }

    return 0;
}



void setBit(unsigned char *array, unsigned int array_len, unsigned int bit_num, unsigned int bit_value)
{
    unsigned int byte_location = 0;
    unsigned int bit_location = 0;

    byte_location = bit_num / 8;
    if(byte_location > array_len - 1)
    {
        printf("setBit(): Unauthorized memory access");
        return;
    }
    bit_location = bit_num % 8;

    if(bit_value)
        array[byte_location] |= (1 << (7-bit_location));
    else
        array[byte_location] &= ~(1 << (7-bit_location)); 

    return;
}

Answer 1

Do you mean something like a bit field?

struct myBF
{
    unsigned int v1 : 5;
    unsigned int v2 : 5;
    unsigned int v3 : 1;
    unsigned int v4 : 8;
};

struct myBF b = { 3, 7, 0, 15 };

I may be misunderstanding your requirements entirely. Please comment if that's the case.

---

Update: Suppose you want to do this dynamically. Let's make a function that accepts an array of pairs, like in your example, and an output buffer:

/* Fill dst with bits.
 * Returns one plus the number of bytes used or 0 on error.
 */
size_t bitstream(int (*arr)[2], size_t arrlen,
                          unsigned char * dst, size_t dstlen)
{
    size_t total_bits = 0, bits_so_far = 0;

    /* Check if there's enough space */
    for (size_t i = 0; i != arrlen; ++i) { total_bits += arr[i][0]; }
    if (dst == NULL || total_bits > CHAR_BIT * dstlen)  { return 0; }

    /* Set the output range to all zero */
    memset(dst, 0, dstlen);

    /* Populate the output range */
    for (size_t i = 0; i != arrlen; ++i)
    {
        for (size_t bits_to_spend = arr[i][0], value = arr[i][1];
             bits_to_spend != 0; /* no increment */ )
        {
            size_t const bit_offset = bits_so_far % CHAR_BIT;
            size_t const byte_index = bits_so_far / CHAR_BIT;
            size_t const cur_byte_capacity = CHAR_BIT - bit_offset;

            /* Debug: Watch it work! */
            printf("Need to store %zu, %zu bits to spend, capacity %zu.\n",
                   value, bits_to_spend, cur_byte_capacity);

            dst[byte_index] |= (value << bit_offset);

            if (cur_byte_capacity < bits_to_spend)
            {
                value        >>= cur_byte_capacity;
                bits_so_far   += cur_byte_capacity;
                bits_to_spend -= cur_byte_capacity;
            }
            else
            {
                bits_so_far += bits_to_spend;
                bits_to_spend = 0;
            }
        }
    }

    return (bits_so_far + CHAR_BIT - 1) / CHAR_BIT;
}

Notes:

• If the number arr[i][1] does not fit into arr[i][0] bits, only the residue modulo 2^arr[i][0] is stored.

• To be perfectly correct, the array type should be unsigned as well, otherwise the initialization size_t value = arr[i][1] may be undefined behaviour.

• You can modify the error handling behaviour. For example, you could forgo transactionality and move the length check into the main loop. Also, instead of returning 0, you could return the num­ber of required bytes, so that the user can figure out how big the destination array needs to be (like snptrintf does).

Usage:

unsigned char dst[N];
size_t n = bitstream(array, sizeof array / sizeof *array, dst, sizeof dst);
for (size_t i = 0; i != n; ++i) { printf("0x%02X ", dst[n - i - 1]); }

For your example, this will produce 0x00 0xF0 0xE3, which is:

  0x00     0xF0     0xE3
00000000 11110000 11100011

0000 00001111 0 000111 00011
padd    15    0    7     3

Answer 2

You can use a bitstream library:

Highly recommended bitstream library:

http://cpansearch.perl.org/src/KURIHARA/Imager-QRCode-0.033/src/bitstream.c

http://cpansearch.perl.org/src/KURIHARA/Imager-QRCode-0.033/src/bitstream.h

Because this bitstream library seems to be very self-contained, and doesn't seem to require external includes.

---

http://www.codeproject.com/Articles/32783/CBitStream-A-simple-C-class-for-reading-and-writin - C library, but using windows WORD, DWORD types (you can still typedef to use this library)

http://code.google.com/p/youtube-mobile-ffmpeg/source/browse/trunk/libavcodec/bitstream.c?r=8 - includes quite a few other include files to use the bitstream library

---

If you just want exponential golomb codes, there are open-source C implementations:

http://www.koders.com/c/fid8A317DF502A7D61CC96EC4DA07021850B6AD97ED.aspx?s=gcd

---

Or you can use bit manipulation techniques.

For example:

unsigned int array[4][2] = ???
unsigned int mem[100] = {};
int index=0,bit=0;
for (int i=0;i<4;i++) {
  int shift = (32 - array[i][0] - bit);
  if (shift>0) mem[index] &= array[i][1] << shift;
  else {
    mem[index] &= array[i][1] >> -shift;
    mem[index+1] &= array[i][1] << (32+shift);
  }

  bit += array[i][1];

  if (bit>=32) {
    bit-=32;
    index++;
  }
}

Disclaimer:

The code only works if your computer byte-order is little endian, and the result will actually be little-endian within each 4-byte boundary, and big-endian across 4-byte boundaries. If you convert mem from int type to char, and replace the constants 32 to 8, you will get a big-endian representation of your bit-array.

It also assumes that the length is less than 32. Obviously, the code you actually want will depend on the bounds of valid input, and what you want in terms of byte-ordering.

Answer 3

In standard C there's no way to access anything smaller than a char by any way other than the 'bitwise manipulation` you mention. I'm afraid you're out of luck, unless you come across a library somewhere out there that can help you.