All geek questions in one place

Extract 14-bit values ​​from a byte array in C

In a byte array of arbitrary size 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 want to be able to arbitrarily store and retrieve into a 16-bit integer. (in this case, both of them are equal to 1, but can be any in a given range). If I had 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 to implement these functions?

This is not for a home project, but just for my curiosity. I have a specific project for which it will be used, and this is the key / center of the whole project.

I do not need an array of structures that have 14-bit values ​​in them, as this generates bits of waste for each stored structure. I want to be able to densely pack as many 14-bit values ​​as possible into an array of bytes. (for example: in the comment I made, it is desirable that so many 14-bit values ​​be added to a piece of 64 bytes, without any bit bits. the way these 64 bytes work is fully densely packed for a particular use case, so that even one bit of waste will remove the ability to store another 14-bit value)

+4
source share
5 answers

, . , , 14- 3 , uint16_t - . , , ( ). , 8 ( int, ). , , 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;
}

. , : 10% - , . , , , 20% . , 16- 32- , :

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);
}

, 20% , :

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;
}

, , , . 3 , 14 .

. , , ( , YMMV), . :

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;
  }
}
+2

, , - : " ?" , , , char, short, int .. 8-bits. , , 8- .

, , - char 14 . 112-bits (7-shorts 14-chars). . 7- 14- 8 14-bit. , 8 , , , 4-, .

, . , .

- - , . / .

, ( , 2 14- ):

#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;
}


$ ./bin/bitfield14

 mybitfield in memory : 0000000000000100000000000001

: mybitfield , .

, , 14- , ..

+1

- , . , . , . .

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;
}
+1

- struct :

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

14*8 = 112 , 14 ( uint16_t). :

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;
    }
}

-.

+1

( ):

#define PACKWID        14                    // number of bits in packed number
#define PACKMSK    ((1 << PACKWID) - 1)

#ifndef ARCHBYTEALIGN
#define ARCHBYTEALIGN    1                // align to 1=bytes, 2=words
#endif
#define ARCHBITALIGN    (ARCHBYTEALIGN * 8)

typedef unsigned char byte;
typedef unsigned short u16;
typedef unsigned int u32;
typedef long long s64;

typedef u16 pcknum_t;                    // container for packed number
typedef u32 acc_t;                        // working accumulator

#ifndef ARYOFF
#define ARYOFF long
#endif
#define PRT(_val)    ((unsigned long) _val)
typedef unsigned ARYOFF aryoff_t;            // bit offset

// packary -- access array of packed numbers
// RETURNS: old value
extern inline pcknum_t
packary(byte *ary,aryoff_t idx,int setflg,pcknum_t newval)
// ary -- byte array pointer
// idx -- index into array (packed number relative)
// setflg -- 1=set new value, 0=just get old value
// newval -- new value to set (if setflg set)
{
    aryoff_t absbitoff;
    aryoff_t bytoff;
    aryoff_t absbitlhs;
    acc_t acc;
    acc_t nval;
    int shf;
    acc_t curmsk;
    pcknum_t oldval;

    // get the absolute bit number for the given array index
    absbitoff = idx * PACKWID;

    // get the byte offset of the lowest byte containing the number
    bytoff = absbitoff / ARCHBITALIGN;

    // get absolute bit offset of first containing byte
    absbitlhs = bytoff * ARCHBITALIGN;

    // get amount we need to shift things by:
    // (1) our accumulator
    // (2) values to set/get
    shf = absbitoff - absbitlhs;

#ifdef MODSHOW
    do {
        static int modshow;

        if (modshow > 50)
            break;
        ++modshow;

        printf("packary: MODSHOW idx=%ld shf=%d bytoff=%ld absbitlhs=%ld absbitoff=%ld\n",
            PRT(idx),shf,PRT(bytoff),PRT(absbitlhs),PRT(absbitoff));
    } while (0);
#endif

    // adjust array pointer to the portion we want (guaranteed to span)
    ary += bytoff * ARCHBYTEALIGN;

    // fetch the number + some other bits
    acc = *(acc_t *) ary;

    // get the old value
    oldval = (acc >> shf) & PACKMSK;

    // set the new value
    if (setflg) {
        // get shifted mask for packed number
        curmsk = PACKMSK << shf;

        // remove the old value
        acc &= ~curmsk;

        // ensure caller doesn't pass us a bad value
        nval = newval;
#if 0
        nval &= PACKMSK;
#endif
        nval <<= shf;

        // add in the value
        acc |= nval;

        *(acc_t *) ary = acc;
    }

    return oldval;
}

pcknum_t
int_get(byte *ary,aryoff_t idx)
{

    return packary(ary,idx,0,0);
}

void
int_set(byte *ary,aryoff_t idx,pcknum_t newval)
{

    packary(ary,idx,1,newval);
}

:

set:    354740751        7.095 -- gene
set:    203407176        4.068 -- rcgldr
set:    298946533        5.979 -- craig

get:    268574627        5.371 -- gene
get:    166839767        3.337 -- rcgldr
get:    207764612        4.155 -- craig
0

Source: https://habr.com/ru/post/1612011/

More articles:


All Articles