欢迎投稿

今日深度:

SQLite 变长度整型(varint)编码解码方法,sqlitevarint

SQLite 变长度整型(varint)编码解码方法,sqlitevarint


SQLite为了节省存储空间,可以对64-bits的整型变量进行压缩。压缩后的最后一个byte的第一个bit是0,其他byte的第一个bit都是1,如下:


对于十进制数 182, 它的二进制是 10110110, 有8个bit,但是第一个bit是1,所以对其分割:


分割成两个bytes, 填充这两个bytes,使得他们符合上面提到的规则(加粗部分):


这样十进制整数 182 就被编码为一个2bytes的二进制格式了。

解码只需要把这个过程逆过来进行一遍就可以了。

还有需要注意的一点是SQLite是对64-bits的整型变量的二进制补码进行编码的,这对正数没什么影响,但是对负数编码的时候需要注意一下。


附上我的编码解码代码,我没使用补码,默认数据都是非负数:

unsigned char* IntToVar(unsigned char* dst, uint32_t v)
{
	unsigned char* ptr = dst;
	static const int B = 128;
	if (v < (1 << 7))
	{
		*(ptr++) = v;
	}
	else if (v < (1 << 14))
	{
		*(ptr++) = v | B;
		*(ptr++) = v >> 7;
	}
	else if (v < (1 << 21))
	{
		*(ptr++) = v | B;
		*(ptr++) = (v >> 7) | B;
		*(ptr++) = v >> 14;
	}
	else if (v < (1 << 28))
	{
		*(ptr++) = v | B;
		*(ptr++) = (v >> 7) | B;
		*(ptr++) = (v >> 14) | B;
		*(ptr++) = v >> 21;
	}
	else
	{
		*(ptr++) = v | B;
		*(ptr++) = (v >> 7) | B;
		*(ptr++) = (v >> 14) | B;
		*(ptr++) = (v >> 21)|B;
		*(ptr++) = v >> 28;
	}
	return ptr;
}

uint32_t VarToInt(unsigned char* tail)
{
	unsigned char* pTmp = tail;
	uint32_t Res=0;

	while ((*pTmp) & 128 == 128) 
	{
		Res = Res << 7;
		*pTmp = *pTmp ^ 128;
		Res = Res | (*pTmp);
		pTmp--;
	}

	Res = Res << 7;
	Res = Res | *pTmp;
	return Res;
}

再添加一点最近学到的:

0x81?0x81?0x81?0x81?0x01??becomes??0x10204081:
1000?0001??????????????????0000?0001??????????
1000?0001???????????????????000?0001
1000?0001?????变成->???000?0001
1000?0001???????????????????000?0001
0000?0001???????????????????000?0001

0x8a?0x91?0xd1?0xac?0x78??becomes??0x12345678:我求出来的是0xA2345678,怀疑注释错了
1000?1010???????????????????0000?1010
1001?0001????????????????????001?0001
1101?0001?????变成->????101?0001
1010?1100????????????????????010?1100
0111?1000????????????????????111?1000
源代码中的编码解码函数分别是:
/*
**?The?variable-length?integer?encoding?is?as?follows:
**
**?KEY:
**?????????A?=?0xxxxxxx????7?bits?of?data?and?one?flag?bit
**?????????B?=?1xxxxxxx????7?bits?of?data?and?one?flag?bit
**?????????C?=?xxxxxxxx????8?bits?of?data
**
**??7?bits?-?A
**?14?bits?-?BA
**?21?bits?-?BBA
**?28?bits?-?BBBA
**?35?bits?-?BBBBA
**?42?bits?-?BBBBBA
**?49?bits?-?BBBBBBA
**?56?bits?-?BBBBBBBA
**?64?bits?-?BBBBBBBBC
*/

/*
**?Write?a?64-bit?variable-length?integer?to?memory?starting?at?p[0].
**?The?length?of?data?write?will?be?between?1?and?9?bytes.??The?number
**?of?bytes?written?is?returned.
**
**?A?variable-length?integer?consists?of?the?lower?7?bits?of?each?byte
**?for?all?bytes?that?have?the?8th?bit?set?and?one?byte?with?the?8th
**?bit?clear.??Except,?if?we?get?to?the?9th?byte,?it?stores?the?full
**?8?bits?and?is?the?last?byte.
*/
static?int?SQLITE_NOINLINE?putVarint64(unsigned?char?*p,?u64?v);

/*
**?Read?a?64-bit?variable-length?integer?from?memory?starting?at?p[0].
**?Return?the?number?of?bytes?read.??The?value?is?stored?in?*v.
*/
SQLITE_PRIVATE?u8?sqlite3GetVarint(const?unsigned?char?*p,?u64?*v);

www.htsjk.Com true http://www.htsjk.com/SQLite/36064.html NewsArticle SQLite 变长度整型(varint)编码解码方法,sqlitevarint SQLite为了节省存储空间,可以对64-bits的整型变量进行压缩。 压缩后的最后一个byte的第一个bit是0,其他byte的第一个bit都是1 ,如下: 对...
相关文章
    暂无相关文章
评论暂时关闭