Это относится к «переменному целочисленному кодированию», где число битов, используемых для хранения целого числа при сериализации, не фиксировано в 4 байта. В документации к буферу протокола есть хорошее описание varint .
Используется для кодирования буферов протокола Google , и вы можете просмотреть исходный код буфера протокола .
CodedOutputStream содержит точную функцию кодирования WriteVarint32FallbackToArrayInline :
inline uint8* CodedOutputStream::WriteVarint32FallbackToArrayInline(
uint32 value, uint8* target) {
target[0] = static_cast<uint8>(value | 0x80);
if (value >= (1 << 7)) {
target[1] = static_cast<uint8>((value >> 7) | 0x80);
if (value >= (1 << 14)) {
target[2] = static_cast<uint8>((value >> 14) | 0x80);
if (value >= (1 << 21)) {
target[3] = static_cast<uint8>((value >> 21) | 0x80);
if (value >= (1 << 28)) {
target[4] = static_cast<uint8>(value >> 28);
return target + 5;
} else {
target[3] &= 0x7F;
return target + 4;
}
} else {
target[2] &= 0x7F;
return target + 3;
}
} else {
target[1] &= 0x7F;
return target + 2;
}
} else {
target[0] &= 0x7F;
return target + 1;
}
}
Каскадные if s будут добавлять дополнительные байты только в конец массива target, если величина value гарантирует эти дополнительные байты. 0x80 маскирует записываемый байт, а value смещается вниз. Из того, что я могу сказать, маска 0x7f заставляет ее обозначать «последний байт кодировки». (Когда OR'ing 0x80, старший бит всегда будет 1, тогда последний байт очищает старший бит (с помощью AND'ing 0x7f). Таким образом, при чтении varints вы читаете, пока не получите байт с ноль в старшем бите.
Я только что понял, что вы спрашивали о "кодировке группы VarInt" специально. Извините, этот код был о базовом кодировании VarInt (все еще быстрее, чем 7-битный). Основная идея выглядит похожей. К сожалению, это , а не , что используется для хранения 64-битных чисел в буферах протокола. Я не удивлюсь, если бы этот код был где-то с открытым исходным кодом.
Используя идеи varint и диаграммы "Групповая вариация" из слайдов, не должно быть слишком сложно приготовить свою собственную:)
Вот еще одна страница, описывающая Сжатие группы VarInt , которая содержит код декодирования. К сожалению, они ссылаются на общедоступные реализации, но не дают ссылок.
void DecodeGroupVarInt(const byte* compressed, int size, uint32_t* uncompressed) {
const uint32_t MASK[4] = { 0xFF, 0xFFFF, 0xFFFFFF, 0xFFFFFFFF };
const byte* limit = compressed + size;
uint32_t current_value = 0;
while (compressed != limit) {
const uint32_t selector = *compressed++;
const uint32_t selector1 = (selector & 3);
current_value += *((uint32_t*)(compressed)) & MASK[selector1];
*uncompressed++ = current_value;
compressed += selector1 + 1;
const uint32_t selector2 = ((selector >> 2) & 3);
current_value += *((uint32_t*)(compressed)) & MASK[selector2];
*uncompressed++ = current_value;
compressed += selector2 + 1;
const uint32_t selector3 = ((selector >> 4) & 3);
current_value += *((uint32_t*)(compressed)) & MASK[selector3];
*uncompressed++ = current_value;
compressed += selector3 + 1;
const uint32_t selector4 = (selector >> 6);
current_value += *((uint32_t*)(compressed)) & MASK[selector4];
*uncompressed++ = current_value;
compressed += selector4 + 1;
}
}