从C中的字节数组中提取14位值 [英] Extract 14-bit values from an array of bytes in C

问题描述

在C中任意大小的字节数组中，我要存储紧密包装的14位数字(0-16383).换句话说，按照以下顺序:

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

我希望有两个数字可以任意存储并检索为16位整数. (在这种情况下，它们都为1，但可以是给定范围内的任何值).如果我要具有功能uint16_t 14bitarr_get(unsigned char* arr, unsigned int index)和void 14bitarr_set(unsigned char* arr, unsigned int index, uint16_t value)，我将如何实现这些功能?

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.

我不希望在其中具有14位值的结构数组，因为这会为存储的每个结构生成浪费的位.我希望能够将尽可能多的14位值紧密封装到字节数组中. (例如:在我的评论中，希望将尽可能多的14位值放入64字节的块中，而不会浪费比特.这64字节的工作方式对于特定的用例是完全紧紧包装的，因此，即使是浪费一点就可以消除存储另外14位值的能力)

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)

推荐答案

好吧，这是最好的事情.用一个字节数组来做比使用较大的元素要复杂得多，因为一个14位的数量可以跨越3个字节，其中uint16_t或任何更大的内容将不超过两个.但是，我想告诉您，这就是您想要的(无双关语).这段代码实际上可以将常量设置为8或更大(但不能超过int的大小；为此，需要额外的类型转换).当然，如果值类型大于16，则必须对其进行调整.

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

更快速的版本由于您在评论中说性能是一个问题:在原始程序中包含的小测试驱动程序上，对循环进行开放式编码可使我的计算机的速度提高大约10％.这包括随机数的生成和测试，因此原始图元的速度可能提高了20％.我相信16位或32位数组元素会带来进一步的改进，因为字节访问非常昂贵:

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

另一种变化 这在我的机器上还快了不少，比上面提高了约20％:

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

请注意，为使此代码安全，应在打包数组的末尾分配一个额外的字节.即使所需的14位在前2个字节中，它始终会读写3个字节.

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.

另一个变种最后，它的运行速度比上面的变种慢一点(同样在我的计算机上为YMMV)，但是您不需要额外的字节.每次操作使用一个比较:

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

这篇关于从C中的字节数组中提取14位值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！