C++ 将整数的大小压缩到 2 位？

Question

我现在正在做一个小的游戏物理网络项目，我正在尝试使用本指南优化我发送的数据包：

https://gafferongames.com/post/snapshot_compression/

在 "Optimize Quaternions" 部分说：

Don’t always drop the same component due to numerical precision issues. Instead, find the component with the largest absolute value and ENCODE its index using two bits [0,3] (0=x, 1=y, 2=z, 3=w), then send the index of the largest component and the smallest three components over the network

现在我的问题是，如何将整数编码到 2 位...或者我误解了任务？

我对压缩数据知之甚少，但将 4 字节整数（32 位）减少到仅 2 位对我来说似乎有点疯狂。这有可能吗，还是我完全误解了一切？

编辑：这是我到目前为止的一些代码：

void HavNetConnection::sendBodyPacket(HavNetBodyPacket bp)
{
  RakNet::BitStream bsOut;
  bsOut.Write((RakNet::MessageID)ID_BODY_PACKET);

  float maxAbs = std::abs(bp.rotation(0));
  int maxIndex = 0;
  for (int i = 1; i < 4; i++)
  {
    float rotAbs = std::abs(bp.rotation(i));
    if (rotAbs > maxAbs) {
      maxAbs = rotAbs;
      maxIndex = i;
    }
  }

  bsOut.Write(bp.position(0));
  bsOut.Write(bp.position(1));
  bsOut.Write(bp.position(2));
  bsOut.Write(bp.linearVelocity(0));
  bsOut.Write(bp.linearVelocity(1));
  bsOut.Write(bp.linearVelocity(2));
  bsOut.Write(bp.rotation(0));
  bsOut.Write(bp.rotation(1));
  bsOut.Write(bp.rotation(2));
  bsOut.Write(bp.rotation(3));
  bsOut.Write(bp.bodyId.toRawInt(bp.bodyId));
  bsOut.Write(bp.stepCount);

  // Send body packets over UDP (UNRELIABLE), priority could be low.
  m_peer->Send(&bsOut, MEDIUM_PRIORITY, UNRELIABLE, 
      0, RakNet::UNASSIGNED_SYSTEM_ADDRESS, true);
}

Answer 1

我猜他们希望您将这 2 位放入您已经发送的不需要所有可用位的某个值中，或者将几个小位字段打包到一个 int 中以进行传输。

你可以这样做：

// these are going to be used as 2 bit fields,
// so we can only go to 3.
enum addresses
{
    x = 0,    // 00
    y = 1,    // 01
    z = 2,    // 10
    w = 3     // 11
};

int val_to_send;

// set the value to send, and shift it 2 bits left.
val_to_send = 1234;
// bit pattern:  0000 0100 1101 0010

// bit shift left by 2 bits
val_to_send = val_to_send << 2;
// bit pattern:  0001 0011 0100 1000

// set the address to the last 2 bits.
// this value is address w (bit pattern 11) for example...
val_to_send |= w;
// bit pattern: 0001 0011 0100 1011

send_value(val_to_send);

接收端：

receive_value(&rx_value);

// pick off the address by masking with the low 2 bits
address = rx_value & 0x3;
// address now = 3 (w)

// bit shift right to restore the value
rx_value = rx_value >> 2;
// rx_value = 1234 again.

您可以这样 'pack' 位，一次任意数量的位。

int address_list;
// set address to w (11)
address_list = w;
// 0000 0011

// bit shift left by 2 bits
address_list = address_list << 2;
// 0000 1100

// now add address x (00)
address_list |= x;
// 0000 1100

// bit shift left 2 more bits
address_list = address_list << 2;
// 0011 0000

// add the address y (01)
address_list |= y;
// 0011 0001

// bit shift left 2 more bits
address_list = address_list << 2;
// 1100 0100

// add the address z. (10)
address_list |= z;
// 1100 0110
// w x  y z are now in the lower byte of 'address_list'

这将4个地址打包到'address_list'的低字节；

你只需要在另一端拆包即可。

这有一些实施细节需要解决。您现在只有 30 位的值，而不是 32 位。如果数据是带符号的 int，您需要做更多的工作来避免将符号位向左移等。

但是，从根本上说，这就是将位模式填充到要发送的数据中的方法。

显然，这假设发送比将位打包成字节和整数等的工作更昂贵。这种情况经常发生，尤其是在涉及低波特率的情况下，如在串行端口中。

Answer 2

这里有很多可能的理解和误解。解决了您发送少于一个字节的技术问题。我想再重申一下理论性的点。

这还没有完成

您最初误解了引用的段落。我们不使用两位表示“不发送 2121387”，但要说“不发送 z-component”。这些完全匹配，应该很容易看出。

这是不可能的

如果您想发送一个 32 位整数，它可能采用 2^32 个可能值中的任何一个，您至少需要 32 位。由于 n 位最多只能表示 2^n 个状态，任何少量的比特都不够。

这有点可能

超出您的实际问题：当我们放宽我们将始终使用 2 位的要求时并有足够强的假设关于值的概率分布，我们可以得到比特数下降的期望值。链接文章中到处都使用了这样的想法。

例子

设 c 是几乎所有时间都为 0 的整数（比如 97%）其余时间可以取任何值 (3%)。然后我们可以用一位来判断“c是否为零” 大多数时候不需要更多位。在 c 不为零的情况下，我们又花了 32 位来定期对其进行编码。总共我们需要 0.97*1+0.03*(1+32) = 1.96 位平均。但是我们有时需要33位，这使得这与我之前关于不可能的断言相符。

这很复杂

根据您的背景（数学、bit-fiddling 等），它可能看起来像是一个巨大的、不可知的黑魔法。（不是。你可以学习这些东西。）你似乎并没有完全迷失，而且学得很快但我同意你似乎超出了你的深度。

你真的需要这样做吗？ 还是您过早地进行了优化？如果它运行足够好，让它运行。专注于重要的事情。

Answer 3

解决您问题的最简单方法是使用 bitfields:

// working type (use your existing Quaternion implementation instead)
struct Quaternion{
    float w,x,y,z;
    Quaternion(float w_=1.0f, float x_=0.0f, float y_=0.0f, float z_=0.0f) : w(w_), x(x_), y(y_), z(z_) {}
};

struct PacketQuaternion
{
    enum LargestElement{
        W=0, X=1, Y=2, Z=3,
    };
    LargestElement le : 2; // 2 bits;
    signed int i1 : 9, i2 : 9, i3 : 9;  // 9 bits each

    PacketQuaternion() : le(W), i1(0), i2(0), i3(0) {}

    operator Quaternion() const { // convert packet quaternion to  regular quaternion
        const float s = 1.0f/float(1<<8); // scale int to [-1, 1]; you could also scale to [-sqrt(.5), sqrt(.5)]
        const float f1=s*i1, f2 = s*i2, f3 = s*i3;
        const float f0 = std::sqrt(1.0f - f1*f1-f2*f2-f3*f3);
        switch(le){
        case W: return Quaternion(f0, f1, f2, f3);
        case X: return Quaternion(f1, f0, f2, f3);
        case Y: return Quaternion(f1, f2, f0, f3);
        case Z: return Quaternion(f1, f2, f3, f0);
        }
        return Quaternion(); // default, can't happen
    }
};

如果你看一下它生成的汇编代码，你会看到一些移位，将 le 和 i1 提取到 i3 —— 本质上与你的代码相同也可以手写。

您的 PacketQuaternion 结构将始终占用整数个字节，因此（在任何 non-exotic 平台上）您仍然会浪费 3 位（您可以在这里为每个整数字段使用 10 位，除非你对这些位有其他用途）。

我省略了从常规四元数转换为 PacketQuaternion 的代码，但这应该也相对简单。

通常（涉及网络时一如既往），要格外小心，确保数据在所有方向上都正确转换，尤其是在涉及不同体系结构或不同编译器的情况下！

此外，正如其他人指出的那样，在此处进行积极优化之前，请确保网络带宽确实是一个瓶颈。

C++ 将整数的大小压缩到 2 位？

C++ Compressing size of integer down to 2 bits?

c++

compression

encode

integer

bits

这还没有完成

这是不可能的

这有点可能

例子

这很复杂