C++ Сжимать размер целого числа до 2 бит?
Я сейчас занимаюсь небольшим сетевым проектом по физике игр и пытаюсь оптимизировать пакеты, которые отправляю, используя это руководство:
https://gafferongames.com/post/snapshot_compression/
В разделе "Оптимизировать кватернионы" говорится:
Не всегда отбрасывайте один и тот же компонент из-за проблем с числовой точностью. Вместо этого найдите компонент с наибольшим абсолютным значением и ЗАПИШИТЕ его индекс, используя два бита [0,3] (0=x, 1=y, 2=z, 3=w), затем отправьте индекс наибольшего компонента и самые маленькие три компонента по сети
Теперь мой вопрос: как мне кодировать целое число до 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);
}
3 ответа
Самое простое решение вашей проблемы - использовать битовые поля:
// 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 структура всегда будет занимать целое число байтов, поэтому (на любой неэкзотической платформе) вы все равно будете тратить 3 бита (вы можете просто использовать 10 бит на целое поле здесь, если только у вас нет другого использования этих битов).
Я пропустил код для преобразования из обычного кватерниона в PacketQuaternion, но это должно быть относительно просто.
Как правило (как всегда, когда речь идет о сетевом взаимодействии), будьте особенно осторожны, чтобы данные были преобразованы правильно во всех направлениях, особенно, если задействованы разные архитектуры или разные компиляторы!
Кроме того, как уже отмечали другие, убедитесь, что пропускная способность сети действительно является узким местом, прежде чем проводить агрессивную оптимизацию здесь.
Я предполагаю, что они хотят, чтобы вы вписали 2 бита в какое-то значение, которое вы уже отправляете, которому не нужны все доступные биты, или для упаковки нескольких небольших битовых полей в одно целое для передачи.
Вы можете делать такие вещи:
// 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.
Вы можете "упаковывать" биты таким образом, любое количество битов за раз.
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. Если данные являются целыми числами со знаком, вам нужно проделать большую работу, чтобы избежать смещения бит знака влево и т. Д.
Но, по сути, это то, как вы можете вставить битовые шаблоны в данные, которые вы отправляете.
Очевидно, это предполагает, что отправка обходится дороже, чем работа по упаковке битов в байты и байты и т. Д. Это часто имеет место, особенно когда речь идет о низких скоростях передачи, как в последовательных портах.
Здесь есть много возможных пониманий и недоразумений. ttemple решает вашу техническую проблему отправки меньше байта. Я хочу повторить более теоретические положения.
Это не сделано
Вы изначально неправильно поняли процитированный отрывок. Мы используем не два бита, чтобы сказать "не отправлять 2121387", а сказать "не отправлять z-компонент". То, что они точно совпадают, должно быть легко увидеть.
Это невозможно
Если вы хотите отправить 32-битное целое число, которое может принимать любое из 2^32 возможных значений, вам нужно не менее 32 бит. Поскольку n битов может представлять не более 2^n состояний, любое меньшее количество битов будет недостаточным.
Это своего рода возможно
Помимо вашего фактического вопроса: когда мы ослабим требование, что мы всегда будем использовать 2 бита и будем иметь достаточно сильные предположения о распределении вероятностей значений, мы можем уменьшить ожидаемое значение количества битов. Подобные идеи используются повсеместно в связанной статье.
пример
Пусть c - некоторое целое число, которое почти всегда равно 0 (скажем, 97%) и может принимать любое значение в остальное время (3%). Затем мы можем взять один бит, чтобы сказать, является ли "с нулем" и не нужно ли больше битов большую часть времени. В случаях, когда c не равен нулю, мы тратим еще 32 бита для его регулярного кодирования. Всего нам нужно в среднем0,97*1+0,03*(1+32) = 1,96 бит. Но иногда нам нужно 33 бита, что делает это совместимым с моим ранним утверждением о невозможности.
Это сложно
В зависимости от вашего фона (в математике, мелочах и т. Д.) Это может показаться огромным, непостижимым произведением черной магии. (Это не так. Вы можете выучить этот материал.) Вы не кажетесь полностью потерянным и быстро учащимся, но я согласен с Реми Лебо, что вы, кажется, не в себе.
Вам действительно нужно это сделать? Или ты оптимизируешь преждевременно? Если он работает достаточно хорошо, пусть работает. Сконцентрируйтесь на важных вещах.