以7位形式访问8位数据

Question

我有一个由100个uint8_t组成的数组，它将被视为一个800位的流，并且一次处理7位。换句话说，如果8位数组的第一个元素包含0b11001100，第二个元素包含ob11110000，那么当我以7位格式读取它时，7位数组的第一个元素将是0b1100110，第二个元素将是0b0111100，剩余的2位将保存在第三个元素中。我尝试的第一件事是一个联合...

struct uint7_t {
    uint8_t i1:7;
};

union uint7_8_t {
    uint8_t u8[100];
    uint7_t u7[115];
};

当然，所有的东西都是字节对齐的，我基本上只是丢失了每个元素的第8位。

有没有人知道我该怎么做？

为了清楚起见，这是联合结果的可视化表示：

xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx 32位8位数据

0xxxxxxx 0xxxxxxx 0xxxxxxx 0xxxxxxx 32位7位数据。

这就是我想要做的事情：

xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx 32位8位数据

xxxxxxx xxxxxxx xxxxxxx xxxxxxx xxxx 32位7位数据。

我知道最后一位可能是填充的，但这很好，我只是想要某种方法，每次访问每个字节7位，而不会丢失800位中的任何一位。到目前为止，我能想到的唯一方法是大量的位移位，这当然可以工作，但我相信有一种更干净的方法(？)

提前感谢您的回复。

Answer 1

不知道你说的“清洁工”是什么意思。这种抽象有时会出现在压缩应用程序中。当然，该方法的内部确实使用了移位和掩码。

一种相当简洁的方法是编写一个函数，该函数在无符号字符数组中的任何位索引处提取7位数。使用除法将位索引转换为字节索引，并使用模数获得字节内的位索引。然后按shift键并遮罩。输入位可以跨越两个字节，因此您必须在提取之前将16位值粘合在一起，或者执行两个较小的提取，或者将它们组合在一起来构造结果。

如果我的目标是一些中等性能的东西，我可能会采取两种方法之一：

第一个有两个状态变量，表示从当前字节和下一个字节中取多少位。它将使用移位、掩码和按位或，以产生当前输出(例如，0和127之间的数字作为int )，然后循环将通过加法和模来更新两个状态变量，并且如果第一个字节中的所有位都被消耗，则将递增当前字节指针。

第二种方法是将56位(相当于输入的8个输出)加载到64位整数中，并使用完全展开的结构来提取8个输出中的每一个。要在不使用未对齐的内存读取的情况下执行此操作，需要逐段构造64位整数。(56位是特殊的，因为起始位位置是字节对齐的。)

为了更快，我可能会尝试用Halide编写SIMD代码。我认为这超出了我们的范围。(实际上，还不清楚它会赢得多少胜利。)

一次将一个以上的字节读入一个整数的设计可能不得不考虑处理器的字节排序。

Answer 2

这是一个使用向量布尔专门化的解决方案。它还使用类似的机制，允许通过引用对象访问7位元素。

成员函数允许执行以下操作：

uint7_t x{5};               // simple value
Arr<uint7_t> arr(10);       // array of size 10
arr[0] = x;                 // set element
uint7_t y = arr[0];         // get element
arr.push_back(uint7_t{9});  // add element
arr.push_back(x);           //
std::cout << "Array size is " 
    << arr.size() << '\n';  // get size
for(auto&& i : arr) 
    std::cout << i << '\n'; // range-for to read values
int z{50};
for(auto&& i : arr)
    i = z++;                // range-for to change values
auto&& v = arr[1];          // get reference to second element
v = 99;                     // change second element via reference

完整计划：

#include <vector>
#include <iterator>
#include <iostream>

struct uint7_t {
    unsigned int i : 7;
};

struct seven_bit_ref {
    size_t begin;
    size_t end;
    std::vector<bool>& bits;

    seven_bit_ref& operator=(const uint7_t& right)
    {
        auto it{bits.begin()+begin};
        for(int mask{1}; mask != 1 << 7; mask <<= 1)
            *it++ = right.i & mask;
        return *this;
    }

    operator uint7_t() const
    {
        uint7_t r{};
        auto it{bits.begin() + begin};
        for(int i{}; i < 7; ++i)
            r.i += *it++ << i;
        return r;
    }

    seven_bit_ref operator*()
    {
        return *this;
    }

    void operator++()
    {
        begin += 7;
        end += 7;
    }

    bool operator!=(const seven_bit_ref& right)
    {
        return !(begin == right.begin && end == right.end);
    }

    seven_bit_ref operator=(int val)
    {
        uint7_t temp{};
        temp.i = val;
        operator=(temp);
        return *this;
    }

};

template<typename T>
class Arr;

template<>
class Arr<uint7_t> {
public:
    Arr(size_t size) : bits(size * 7, false) {}

    seven_bit_ref operator[](size_t index)
    {
        return {index * 7, index * 7 + 7, bits};
    }
    size_t size()
    {
        return bits.size() / 7;
    }
    void push_back(uint7_t val)
    {
        for(int mask{1}; mask != 1 << 7; mask <<= 1){
            bits.push_back(val.i & mask);
        }
    }

    seven_bit_ref begin()
    {
        return {0, 7, bits};
    }

    seven_bit_ref end()
    {
        return {size() * 7, size() * 7 + 7, bits};
    }

    std::vector<bool> bits;
};

std::ostream& operator<<(std::ostream& os, uint7_t val)
{
    os << val.i;
    return os;
}

int main()
{
    uint7_t x{5};               // simple value
    Arr<uint7_t> arr(10);       // array of size 10
    arr[0] = x;                 // set element
    uint7_t y = arr[0];         // get element
    arr.push_back(uint7_t{9});  // add element
    arr.push_back(x);           //
    std::cout << "Array size is " 
        << arr.size() << '\n';  // get size
    for(auto&& i : arr) 
        std::cout << i << '\n'; // range-for to read values
    int z{50};
    for(auto&& i : arr)
        i = z++;                // range-for to change values
    auto&& v = arr[1];          // get reference
    v = 99;                     // change via reference
    std::cout << "\nAfter changes:\n";
    for(auto&& i : arr)
        std::cout << i << '\n';
}

Answer 3

将它们以8个为一组进行处理(因为8x7可以很好地舍入为8位对齐的对象)。按位运算符是这里的主流。胡乱摆弄最后(最多)7个数字有点不靠谱，但也不是不可能。(此代码假设这些是无符号7位整数！如果bit6为1，则有符号转换将要求您考虑翻转顶部比特)

// convert 8 x 7bit ints in one go
void extract8(const uint8_t input[7], uint8_t output[8])
{
  output[0] =   input[0] & 0x7F;
  output[1] =  (input[0] >> 7)  | ((input[1] << 1) & 0x7F);
  output[2] =  (input[1] >> 6)  | ((input[2] << 2) & 0x7F);
  output[3] =  (input[2] >> 5)  | ((input[3] << 3) & 0x7F);
  output[4] =  (input[3] >> 4)  | ((input[4] << 4) & 0x7F);
  output[5] =  (input[4] >> 3)  | ((input[5] << 5) & 0x7F);
  output[6] =  (input[5] >> 2)  | ((input[6] << 6) & 0x7F);
  output[7] =   input[6] >> 1;
}

// convert array of 7bit ints to 8bit
void seven_bit_to_8bit(const uint8_t* const input, uint8_t* const output, const size_t count)
{
  size_t count8 = count >> 3;
  for(size_t i = 0; i < count8; ++i)
  {
    extract8(input + 7 * i, output + 8 * i);
  }

  // handle remaining (upto) 7 bytes 
  const size_t countr = (count % 8);
  if(countr)
  {
    // how many bytes do we need to copy from the input?
    size_t remaining_bits = 7 * countr;
    if(remaining_bits % 8)
    {
      // round to next nearest multiple of 8
      remaining_bits += (8 - remaining_bits % 8);
    }
    remaining_bits /= 8;
    {
      uint8_t in[7] = {0}, out[8] = {0};
      for(size_t i = 0; i < remaining_bits; ++i)
      {
        in[i] = input[count8 * 7 + i];
      }
      extract8(in, out);
      for(size_t i = 0; i < countr; ++i)
      {
        output[count8 * 8 + i] = in[i];
      }
    }
  }
}