这个标题需要进一步解释一下,变长存储的编码方式通常用于存储无符号类型,而在Lua中一些表示如字符串长度或列表长度的字段是使用int类型存储的。也就是说,在Lua中这些类型虽然声明的是有符号类型,但实际是以无符号类型使用的,这可能会造成一点理解上的歧义。 简单来说,在Lua中存储size_t类型的数据时,使用了一种变长的编码格式进行存储以节省目标文件的大小。
变长编码
在计算机中,表示数据长度或大小的字段,通常是无符号整数,且实际上用到的数字通常是较小的——这也就意味着,这个数字的高位有很多都是0。那么,在存储这些数据时,如果能尽可能有效的压缩高位多个0,就能够节省存储这个数据所占用的空间。
其实有很多变长的编码格式,但核心思想都是基本一致的:将原本的1个字节的8个Bits缩减为7个Bits或更少,节省下来的Bits用于存储额外的信息,如当前数字是否已经结束,或当前数字是否是有符号数等各种信息。再将改写后的Bits流整理为N个Byte进行存储。
Lua中的变长编码格式
在Lua中,变长存储采用上图的方式,即一个Byte中,低7个Bits用来存储实际的数据,最高位用来当作Flags,记录当前是否为最后一个数据块。在存储任意大小的数时,将包含1的所有低位Bits数据以7个Bits进行分组,前面每组的高位补0,表示后面还有数据,最后一组数据的高位补1,表示数据已经完毕。
示例
在Lua中,若存储668这个数,则其分组如下图:
首先将668的所有有效Bits以7位进行分组,这里会分成黄色背景和绿色背景的两部分,然后分别给这两部门的高位补Flag位,非最后一组补0,最后一组补1。最终即得到0x05 0x09C这个编码后的数据。
显然,单纯这样看并没有节省大小,编码后的数据还是占用了2个字节。但如果这个数不是一个int16,而是int32或int64,那此时就大大的提高了数据的紧凑性。