Extract 14-bit values from an array of bytes in C

Question

In an arbitrary-sized array of bytes in C, I want to store 14-bit numbers (0-16,383) tightly packed. In other words, in the sequence:

0000000000000100000000000001

there are two numbers that I wish to be able to arbitrarily store and retrieve into a 16-bit integer. (in this case, both of them are 1, but could be anything in the given range) If I were to have the functions uint16_t 14bitarr_get(unsigned char* arr, unsigned int index) and void 14bitarr_set(unsigned char* arr, unsigned int index, uint16_t value), how would I implement those functions?

This is not for a homework project, merely my own curiosity. I have a specific project that this would be used for, and it is the key/center of the entire project.

I do not want an array of structs that have 14-bit values in them, as that generates waste bits for every struct that is stored. I want to be able to tightly pack as many 14-bit values as I possibly can into an array of bytes. (e.g.: in a comment I made, putting as many 14-bit values into a chunk of 64 bytes is desirable, with no waste bits. the way those 64 bytes work is completely tightly packed for a specific use case, such that even a single bit of waste would take away the ability to store another 14 bit value)

Answer 1

Well, this is bit fiddling at its best. Doing it with an array of bytes makes it more complicated than it would be with larger elements because a single 14 bit quantity can span 3 bytes, where uint16_t or anything bigger would require no more than two. But I'll take you at your word that this is what you want (no pun intended). This code will actually work with the constant set to anything 8 or larger (but not over the size of an int; for that, additional type casts are needed). Of course the value type must be adjusted if larger than 16.

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#define W 14

uint16_t arr_get(unsigned char* arr, size_t index) {
  size_t bit_index = W * index;
  size_t byte_index = bit_index / 8;
  unsigned bit_in_byte_index = bit_index % 8;
  uint16_t result = arr[byte_index] >> bit_in_byte_index;
  for (unsigned n_bits = 8 - bit_in_byte_index; n_bits < W; n_bits += 8)
    result |= arr[++byte_index] << n_bits;
  return result & ~(~0u << W);
}

void arr_set(unsigned char* arr, size_t index, uint16_t value) {
  size_t bit_index = W * index;
  size_t byte_index = bit_index / 8;
  unsigned bit_in_byte_index = bit_index % 8;
  arr[byte_index] &= ~(0xff << bit_in_byte_index);
  arr[byte_index++] |= value << bit_in_byte_index;
  unsigned n_bits = 8 - bit_in_byte_index;
  value >>= n_bits;
  while (n_bits < W - 8) {
    arr[byte_index++] = value;
    value >>= 8;
    n_bits += 8;
  }
  arr[byte_index] &= 0xff << (W - n_bits);
  arr[byte_index] |= value;
}

int main(void) {
  int mod = 1 << W;
  int n = 50000;
  unsigned x[n];
  unsigned char b[2 * n];
  for (int tries = 0; tries < 10000; tries++) {
    for (int i = 0; i < n; i++) {
      x[i] = rand() % mod;
      arr_set(b, i, x[i]);
    }
    for (int i = 0; i < n; i++)
      if (arr_get(b, i) != x[i])
        printf("Err @%d: %d should be %d\n", i, arr_get(b, i), x[i]);
  }
  return 0;
}

Faster versions Since you said in comments that performance is an issue: open coding the loops gives a roughly 10% speed improvement on my machine on the little test driver included in the original. This includes random number generation and testing, so perhaps the primitives are 20% faster. I'm confident that 16- or 32-bit array elements would give further improvements because byte access is expensive:

uint16_t arr_get(unsigned char* a, size_t i) {
  size_t ib = 14 * i;
  size_t iy = ib / 8;
  switch (ib % 8) {
  case 0:
    return (a[iy] | (a[iy+1] << 8)) & 0x3fff;
  case 2:
    return ((a[iy] >> 2) | (a[iy+1] << 6)) & 0x3fff;
  case 4:
    return ((a[iy] >> 4) | (a[iy+1] << 4) | (a[iy+2] << 12)) & 0x3fff;
  }
  return ((a[iy] >> 6) | (a[iy+1] << 2) | (a[iy+2] << 10)) & 0x3fff;
}

#define M(IB) (~0u << (IB))
#define SETLO(IY, IB, V) a[IY] = (a[IY] & M(IB)) | ((V) >> (14 - (IB)))
#define SETHI(IY, IB, V) a[IY] = (a[IY] & ~M(IB)) | ((V) << (IB))

void arr_set(unsigned char* a, size_t i, uint16_t val) {
  size_t ib = 14 * i;
  size_t iy = ib / 8;
  switch (ib % 8) {
  case 0:
    a[iy] = val;
    SETLO(iy+1, 6, val);
    return;
  case 2:
    SETHI(iy, 2, val);
    a[iy+1] = val >> 6;
    return;
  case 4:
    SETHI(iy, 4, val);
    a[iy+1] = val >> 4;
    SETLO(iy+2, 2, val);
    return;
  }
  SETHI(iy, 6, val);
  a[iy+1] = val >> 2;
  SETLO(iy+2, 4, val);
}

Another variation This is quite a bit faster yet on my machine, about 20% better than above:

uint16_t arr_get2(unsigned char* a, size_t i) {
  size_t ib = i * 14;
  size_t iy = ib / 8;
  unsigned buf = a[iy] | (a[iy+1] << 8) | (a[iy+2] << 16);
  return (buf >> (ib % 8)) & 0x3fff;
}

void arr_set2(unsigned char* a, size_t i, unsigned val) {
  size_t ib = i * 14;
  size_t iy = ib / 8;
  unsigned buf = a[iy] | (a[iy+1] << 8) | (a[iy+2] << 16);
  unsigned io = ib % 8;
  buf = (buf & ~(0x3fff << io)) | (val << io);
  a[iy] = buf;
  a[iy+1] = buf >> 8;
  a[iy+2] = buf >> 16;
}

Note that for this code to be safe you should allocate one extra byte at the end of the packed array. It always reads and writes 3 bytes even when the desired 14 bits are in the first 2.

One more variation Finally, this runs just a bit slower than the one above (again on my machine; YMMV), but you don't need the extra byte. It uses one comparison per operation:

uint16_t arr_get2(unsigned char* a, size_t i) {
  size_t ib = i * 14;
  size_t iy = ib / 8;
  unsigned io = ib % 8;
  unsigned buf = ib % 8 <= 2
      ? a[iy] | (a[iy+1] << 8)
      : a[iy] | (a[iy+1] << 8) | (a[iy+2] << 16);
  return (buf >> io) & 0x3fff;
}

void arr_set2(unsigned char* a, size_t i, unsigned val) {
  size_t ib = i * 14;
  size_t iy = ib / 8;
  unsigned io = ib % 8;
  if (io <= 2) {
    unsigned buf = a[iy] | (a[iy+1] << 8);
    buf = (buf & ~(0x3fff << io)) | (val << io);
    a[iy] = buf;
    a[iy+1] = buf >> 8;
  } else {
    unsigned buf = a[iy] | (a[iy+1] << 8) | (a[iy+2] << 16);
    buf = (buf & ~(0x3fff << io)) | (val << io);
    a[iy] = buf;
    a[iy+1] = buf >> 8;
    a[iy+2] = buf >> 16;
  }
}

Answer 2

The easiest solution is to use a struct of eight bitfields:

typedef struct __attribute__((__packed__)) EightValues {
    uint16_t v0 : 14,
             v1 : 14,
             v2 : 14,
             v3 : 14,
             v4 : 14,
             v5 : 14,
             v6 : 14,
             v7 : 14;
} EightValues;

This struct has a size of 14*8 = 112 bits, which is 14 bytes (seven uint16_t). Now, all you need is to use the last three bits of the array index to select the right bitfield:

uint16_t 14bitarr_get(unsigned char* arr, unsigned int index) {
    EightValues* accessPointer = (EightValues*)arr;
    accessPointer += index >> 3;    //select the right structure in the array
    switch(index & 7) {    //use the last three bits of the index to access the right bitfield
        case 0: return accessPointer->v0;
        case 1: return accessPointer->v1;
        case 2: return accessPointer->v2;
        case 3: return accessPointer->v3;
        case 4: return accessPointer->v4;
        case 5: return accessPointer->v5;
        case 6: return accessPointer->v6;
        case 7: return accessPointer->v7;
    }
}

Your compiler will do the bit-fiddling for you.

Answer 3

The Basis for Storage Issue

The biggest issue you are facing is the fundamental question of "What is my basis for storage going to be?" You know the basics, what you have available to you is char, short, int, etc... The smallest being 8-bits. No matter how you slice your storage scheme, it will ultimately have to rest in memory in a unit of memory based on this 8 bit per byte layout.

The only optimal, no bits wasted, memory allocation would be to declare an array of char in the least common multiple of 14-bits. It is the full 112-bits in this case (7-shorts or 14-chars). This may be the best option. Here, declaring an array of 7-shorts or 14-chars, would allow the exact storage of 8 14-bit values. Of course if you have no need for 8 of them, then it wouldn't be of much use anyway as it would waste more than the 4-bits lost on a single unsigned value.

Let me know if this is something you would like to further explore. If it is, I'm happy to help with the implementation.

Bitfield Struct

The comments regarding bitfield packing or bit packing are exactly what you need to do. This can involve a structure alone or in combination with a union, or by manually right/left shifting values directly as needed.

A short example applicable to your situation (if I understood correctly you want 2 14-bit areas in memory) would be:

#include <stdio.h>

typedef struct bitarr14 {
    unsigned n1 : 14,
             n2 : 14;
} bitarr14;

char *binstr (unsigned long n, size_t sz);

int main (void) {

    bitarr14 mybitfield;

    mybitfield.n1 = 1;
    mybitfield.n2 = 1;

    printf ("\n mybitfield in memory : %s\n\n", 
            binstr (*(unsigned *)&mybitfield, 28));

    return 0;
}

char *binstr (unsigned long n, size_t sz)
{
    static char s[64 + 1] = {0};
    char *p = s + 64;
    register size_t i = 0;

    for (i = 0; i < sz; i++) {
        p--;
        *p = (n >> i & 1) ? '1' : '0';
    }

    return p;
}

Output

$ ./bin/bitfield14

 mybitfield in memory : 0000000000000100000000000001

Note: the dereference of mybitfield for purposes of printing the value in memory breaks strict aliasing and it is intentional just for the purpose of the output example.

The beauty, and purpose for using a struct in the manner provided is it will allow direct access to each 14-bit part of the struct directly, without having to manually shift, etc.

Answer 4

Update - assuming you want big endian bit packing. This is code meant for a fixed size code word. It's based on code I've used for data compression algorithms. The switch case and fixed logic helps with performance.

typedef unsigned short uint16_t;

void bit14arr_set(unsigned char* arr, unsigned int index, uint16_t value)
{
unsigned int bitofs = (index*14)%8;
    arr += (index*14)/8;
    switch(bitofs){
        case  0:   /* bit offset == 0 */
            *arr++  = (unsigned char)(value >>  6);
            *arr   &= 0x03;
            *arr   |= (unsigned char)(value <<  2);
            break;
        case  2:   /* bit offset == 2 */
            *arr   &= 0xc0;
            *arr++ |= (unsigned char)(value >>  8);
            *arr    = (unsigned char)(value <<  0);
            break;
        case  4:   /* bit offset == 4 */
            *arr   &= 0xf0;
            *arr++ |= (unsigned char)(value >> 10);
            *arr++  = (unsigned char)(value >>  2);
            *arr   &= 0x3f;             
            *arr   |= (unsigned char)(value <<  6);
            break;
        case  6:   /* bit offset == 6 */
            *arr   &= 0xfc;
            *arr++ |= (unsigned char)(value >> 12);
            *arr++  = (unsigned char)(value >>  4);
            *arr   &= 0x0f;
            *arr   |= (unsigned char)(value <<  4);
            break;
    }
}

uint16_t bit14arr_get(unsigned char* arr, unsigned int index)
{
unsigned int bitofs = (index*14)%8;
unsigned short value;
    arr += (index*14)/8;
    switch(bitofs){
        case  0:   /* bit offset == 0 */
            value  = ((unsigned int)(*arr++)     ) <<  6;
            value |= ((unsigned int)(*arr  )     ) >>  2;
            break;
        case  2:   /* bit offset == 2 */
            value  = ((unsigned int)(*arr++)&0x3f) <<  8;
            value |= ((unsigned int)(*arr  )     ) >>  0;
            break;
        case  4:   /* bit offset == 4 */
            value  = ((unsigned int)(*arr++)&0x0f) << 10;
            value |= ((unsigned int)(*arr++)     ) <<  2;
            value |= ((unsigned int)(*arr  )     ) >>  6;
            break;
        case  6:   /* bit offset == 6 */
            value  = ((unsigned int)(*arr++)&0x03) << 12;
            value |= ((unsigned int)(*arr++)     ) <<  4;
            value |= ((unsigned int)(*arr  )     ) >>  4;
            break;
    }
    return value;
}