11 29
Base128变长编码

最近在使用google的protobuf的时候,有一个地方引起了我的好奇,下面是一段样例代码:

type KeyValue struct {

    Key []byte `protobuf:"bytes,1,opt,name=key,proto3" json:"key,omitempty"`

    CreateRevision int64 `protobuf:"varint,2,opt,name=create_revision,json=createRevision,proto3" json:"create_revision,omitempty"`

    ModRevision int64 `protobuf:"varint,3,opt,name=mod_revision,json=modRevision,proto3" json:"mod_revision,omitempty"`

    Value []byte `protobuf:"bytes,5,opt,name=value,proto3" json:"value,omitempty"`

    Lease int64 `protobuf:"varint,6,opt,name=lease,proto3" json:"lease,omitempty"`
}

上面代码中,varint几乎都出现在每个字段属性的定义中,当时我在想,这个varint是用来做什么的呢?于是我查阅了Protocol Buffers的文档中对 varints的说明

varints是protobuf的序列化整型数据的一种编码方式,它的优点是整型数据的值越小,编码后所用的字节数越小

在base128中,有效存储的只有7位,其中第8位是用于存储标志位:如果这一位是1,就表示这个字节后面还有其他字节,如果这个位是0的话,就表示这是最后一个字节了,这样一来,就可以准确的知道一个整数的结束位置。

对于编码的步骤,可以看skoo的 《Base 128 Varint, 一种处理整数的变长二进制编码算法》

下面是一个go的实现例子,我们尝试把占用8字节的int64的整数,转换为更小”长度”的整数

package main

import (
    "bytes"
    "fmt"
)

func marshall128Int(out *bytes.Buffer, n int64) (err error) {
    if n == 0 {
        err = out.WriteByte(0)
        return
    }

    l := 0
    for i := n; i > 0; i >>= 7 {
        l++
    }

    for i := l - 1; i >= 0; i-- {
        o := byte(n >> uint(i*7))
        o &= 0x7f
        if i != 0 {
            o |= 0x80
        }
        err = out.WriteByte(o)
        if err != nil {
            return
        }
    }

    return nil
}

func unmashallBase128Int(bytes []byte, initOffset int) (ret, offset int, err error) {
    offset = initOffset
    for shifted := 0; offset < len(bytes); shifted++ {
        if shifted > 4 {
            err = fmt.Errorf("Structural Error: base 128 integer too large")
            return
        }
        ret <<= 7
        b := bytes[offset]
        ret |= int(b & 0x7f)
        offset++
        if b&0x80 == 0 {
            return
        }
    }
    err = fmt.Errorf("Syntax Error: truncated base 128 integer")
    return
}

func main() {
    num := int64(30)
    b := bytes.Buffer{}
    marshall128Int(&b, num)
    fmt.Printf("%v\n", b.Bytes())

    num2 := int64(300)
    b2 := bytes.Buffer{}
    marshall128Int(&b2, num2)
    ret, offset, _ := unmashallBase128Int(b2.Bytes(), 0)
    fmt.Printf("%v\n", b2.Bytes())
    fmt.Printf("%d , size: %d \n", ret, offset)
}


输出结果:

[30]
[130 44]
300 , size: 2

通过varint,我们可以用更小的内存存储我们的数据,而不是统一固定用4个字节或者8个字节。好处显然是非常明显的,特别是在二进制网络协议设计的时候,对整数进行变长编码很有必要。