这指的是“可变整数编码”,其中序列化时用于存储整数的位数不固定为 4 个字节。有一个很好的描述Protocol buffer 文档中的 varint http://code.google.com/apis/protocolbuffers/docs/encoding.html#varints.
它用于编码Google 的协议缓冲区 http://code.google.com/apis/protocolbuffers/,您可以浏览.
The CodedOutputStream
包含精确的编码函数:
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
mask 使其表示“编码的最后一个字节”。 (当进行“或”运算时0x80
,最高位始终是1
,然后最后一个字节清除最高位(通过 AND'ing0x7f
)。因此,在读取 varint 时,您会一直读取直到获得最高位为零的字节。
我刚刚意识到您专门询问了“Group VarInt 编码”。抱歉,该代码是关于基本 VarInt 编码(仍然比 7 位快)。基本思想看起来很相似。不幸的是,这是not用于在协议缓冲区中存储 64 位数字的内容。如果该代码在某处开源,我不会感到惊讶。
使用来自的想法varint
以及幻灯片中的“Group varint”图表,自己制作应该不会太难:)
这是另一页描述组 VarInt 压缩 http://www.ir.uwaterloo.ca/book/addenda-06-index-compression.html,其中包含解码代码。不幸的是,他们提到了公开可用的实现,但没有提供参考。
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;
}
}