压缩算法 | 基于FPGA的Varint编码实现(附代码)

admin

压缩算法 | 基于FPGA的Varint编码实现(附代码)
今天是画师第二次和各位大侠见面，执笔绘画FPGA江湖，本人最近项目经验，写了篇基于FPGA的Varint编码（压缩算法）实现，这里分享给大家，仅供参考。如有转载，请在文章底部留言，请勿随意转载，否则有责必究。

概念

什么是Varint编码呢？首先我们来介绍一下Varint编码，Varint编码就是一种用一个或多个字节将数据序列化，并对数据进行压缩的方法，因此也可以称之为Varint压缩算法。

在进行数据传输过程，我们经常用大位宽来进行数据的传输。有时候是32位或者64位传输某个数据，然而，一直使用大位宽来传输数据也有它的缺点，比如传输很小的数据时，会造成资源的浪费。

例如，我们要传送一个1，而用64位来传输的话就需要表示为00000000_00000000_00000000_00000000_00000000_000000000_00000000_00000001，用这样的方式来传输一个1需要消耗8Byte的存储，属实是很浪费存储空间，而使用Varint编码对它进行压缩后，我们只需要一个Byte就能将它传输出去，大大节省了存储空间，避免了资源的浪费。

2

设计原理

下面我们就来介绍一下Varint编码是如何对原有数据进行编码处理的。在介绍Varint编码原理之前，我们先介绍一下字节数据的两种排序方式，大端和小端。大端数据指的是将高位的数据存在低位的地址中，例如将0x01234567存入一个64位的寄存器reg，则存入高位reg[7]的是7，然后依次是reg[6]=6、reg[5]=5、reg[4]=4、reg[3]=3、reg[2]=2、reg[1]=1、reg[0]=0，即逆序存入寄存器中，这种方式就称之为大端序。小端序即反之，高位的数据存入高地址，低位的数据放入低地址。

在这基础上我们再来讲Varint编码的原理，Varint编码使用的就是大端序。Varint编码将有无效数据去除，然后将效数据分成若干个组，每个组为8位，即一个字节，除去最后一个字节外，其余有效组最高位均为1，最后一个字节最高位为0。有效组最高位为1即代表这个字节后面还有有效数据组，当有效数据组最高位为0时则代表当前有效组为最后一个有效字节，除去最高位，其余位均为有效数据。

我们可以举个例子来更加详细的说明这个原理。  仍然以64位数据为例，如00000000_00000000_00010001_11011001_00110011_10101001_11001100_00110011。编码步骤如下：

（1）首先从最后一个字节开始进行编码，最后一个字节为00110011，按照编码规则我们取后七位，即截取0110011，因为后面还有数据，则最高位取1，然后与截取的有效数据组合在一起组成第一个有效数据组10110011，然后放在整个数据的最高位。

（2）然后是第二个数据，同样往前取七位，得到0011000，同样在本组最高位补1，即得到10011000，组合第一个数据组则为10110011_10011000。

（3）第三个数据，再往前取七位，得到0100111，在本有效数据组最高位补1，得到10100111，再拼接到前面的有效数据组之后，即10110011_10011000_10100111。

（4）第四个数据，同样的方式往前取七位，得到0011101，最高位补1，得到10011101，继续拼接在有效数据组后面，即10110011_10011000_10100111_10011101。

（5）第五个数据，再往前取七位，得到0010011，在最高位补1，得到10010011，继续往有效数据组后拼接，得到10110011_10011000_10100111_10011101_10010011。

（6）第六个数据，按照上述方法，可得10111011，拼接后可得10110011_10011000_10100111_10011101_10010011_10111011。

（7）第七个数据，取得0000100，由观察得知，这个有效数据组之后均为0，即有效数据已全部截取完毕，则按照Varint编码规则，最高位补0，完成编码，将数据全部拼接后得到进行Varint编码后的数据，即10110011_10011000_10100111_10011101_10010011_10111011_00000100。

将上述进行Varint编码后得到的有效数据组与原数据相比，节省了一个字节的存储资源。解码只要将上述过程逆序进行即可，这里就不过多赘述。熟悉完了Varint编码的原理，下面我们就可以开始进行设计了。

点击文首链接跳转阅读全文