Variant编码

内容目录

概述

谷歌的Protocol Buffers实现了一种名为varint的可变长度整数编码。

现在我们来看一下Varint编码是如何对整数进行变长编码的。

编码过程就是将证书转换为字节数组的过程,在计算机中通用的整数的字节数一般为1,2,4,8四种,分别表示代表int8,int16,int32和int64,如果再加上无符号的话就有int8/uint8,int16/uint16,int32/uint32,int64/uint64。

int8
int16
int32
int64
uint8
uint16
uint32
uint64

file

原理

Varint编码基本原理是将整数以7位为一组对整数进行拆分,每组再补充1位作为是否后面还有字节的标识。补充的这1位如果为1则表示还有,0为没有,没有就表示是一个完整的数字字节数了。

Varint编码最小字节为1个即8位,最大为10个字节。

整数与最大字节数对应如下:
file

编码

Varint编码算法在编码时会以7位为一个单位,判断字节的最高位是否为0,为0和不为0的处理如下:

  1. 如果为0,那么表示后续没有字节
  2. 如果为1,那么表示后续还有字节

怎么理解?
我们来举几个例子。
例1: 1个字节的整数:int8与uint8, 根据两个类型的范围我们来选择两个数字,我们先不涉及负数,因为负数是有符号的,有符号的需要使用Zigzag编码。
int8选择127, uint8选择128,接下来我们来看下varint编码后两个数字会是什么二进制数据。

  1. 127 编码(int8)
    file

  2. 128 编码(uint8)
    file

  3. 32767 编码(int32)
    编码
    file

解码

解码就是编码的逆过程。

代码实现

编码


// PutUvarint encodes a uint64 into buf and returns the number of bytes written.
// If the buffer is too small, PutUvarint will panic.
func PutUvarint(buf []byte, x uint64) int {
    i := 0
    for x >= 0x80 {
        buf[i] = byte(x) | 0x80
        x >>= 7
        i++
    }
    buf[i] = byte(x)
    return i + 1
}

解码


// ReadUvarint reads an encoded unsigned integer from r and returns it as a uint64.
// The error is EOF only if no bytes were read.
// If an EOF happens after reading some but not all the bytes,
// ReadUvarint returns io.ErrUnexpectedEOF.
func ReadUvarint(r io.ByteReader) (uint64, error) {
    var x uint64
    var s uint
    for i := 0; i < MaxVarintLen64; i++ {
        b, err := r.ReadByte()
        if err != nil {
            if i > 0 && err == io.EOF {
                err = io.ErrUnexpectedEOF
            }
            return x, err
        }
        if b < 0x80 {
            if i == MaxVarintLen64-1 && b > 1 {
                return x, errOverflow
            }
            return x | uint64(b)<<s, nil
        }
        x |= uint64(b&0x7f) << s
        s += 7
    }
    return x, errOverflow
}

优劣

在Google的Protocol Buffers等序列化数据格式中,varints(variable length integers,可变长度整数)被广泛应用,主要原因是它能够更好地优化存储空间和传输效率。不过,这种方案也有其优点和缺点。

优势

  1. 空间优化。对于较小的数,varints可以用更少的字节来表示,从而节省了存储和传输的空间。

  2. 计算资源优化。对于大型数据集,由于使用更少的字节来表示小整数,这意味着需要更少的计算资源来处理和传输数据。

劣势

  1. 运算复杂度较高。由于varints的存储大小是可变的,所以需要更多的计算才能确定一共需要读取和写入多少个字节。

  2. 无法直接反向查找。普通整数可以直接通过偏移量查找,但是由于varints的可变长度,很难直接定位到特定位置的整数。

  3. 对于较大的数,varints可能需要使用更多的字节来表示。虽然经常需要处理的数值大多数情况下并不大,但一旦碰到需要处理较大的数,使用varints可能会比直接使用普通整数需要更多的空间。

总结

Varint编解码使用的变长编码方式为我们提供了更加紧凑的编码,Varint可以对无符号整型进行编码不能对有符号整型编码,同时增加了解码复杂度。

发表评论

您的电子邮箱地址不会被公开。 必填项已用 * 标注

滚动至顶部