压缩算法：基于FPGA的Varint编码实现(附代码)
原创压缩算法：基于FPGA的Varint编码实现(附代码)
原创
压缩算法：基于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就能将它传输出去，大大节省了存储空间，避免了资源的浪费。
二、设计原理
下面我们就来介绍一下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编码的原理，下面我们就可以开始进行设计了。
三、架构设计
设计架构如下图：
将本设计模块命名为varint_encode，clk为输入时钟，rst_n为复位信号，idata为64位是输入数据，ivalid为数据有效信号，odata0~odata7为输出的有效数据，ovalid0~ovalid7为伴随输出有效数据的数据有效信号。由于FPGA输出的数据位宽都是固定的，因此需要将各个压缩后的位宽都定义一遍。
四、Verilog 代码实现
功能模块实现代码如下：
module varint_encode(
input wire clk,
input wire rst_n,
input wire [63:0] idata,
input wire ivalid,
output reg [63:0] odata0,
output reg [55:0] odata1,
output reg [47:0] odata2,
output reg [39:0] odata3,
output reg [31:0] odata4,
output reg [23:0] odata5,
output reg [15:0] odata6,
output reg [7:0] odata7,
output reg ovalid0,
output reg ovalid1,
output reg ovalid2,
output reg ovalid3,
output reg ovalid4,
output reg ovalid5,
output reg ovalid6,
output reg ovalid7
);
reg [63:0] idata_r;
reg [7:0] buff0;
reg [7:0] buff1;
reg [7:0] buff2;
reg [7:0] buff3;
reg [7:0] buff4;
reg [7:0] buff5;
reg [7:0] buff6;
reg [7:0] buff7;
reg [7:0] buff8;
reg [7:0] buff9;
reg buff0_req;
reg buff1_req;
reg buff2_req;
reg buff3_req;
reg buff4_req;
reg buff5_req;
reg buff6_req;
reg buff7_req;
reg buff8_req;
reg buff9_req;
always @ (posedge clk,negedge rst_n) begin
if (rst_n == 1'b0)
idata_r <= 64'd0;
else
if (ivalid == 1'b1)
idata_r <= idata;
else
idata_r <= idata_r;
end
always @ (posedge clk,negedge rst_n) begin
if (rst_n == 1'b0) begin
buff0 <= 8'd0;
buff0_req <= 1'b0;
end
else
if (idata_r[6:0] > 0) begin
buff0 <= {1'b1,idata_r[6:0]};
buff0_req <= 1'b1;
end
else begin
buff0 <= 8'd0;
buff0_req <= 1'b0;
end
end
always @ (posedge clk,negedge rst_n) begin
if (rst_n == 1'b0) begin
buff1 <= 8'd0;
buff1_req <= 1'b0;
end
else
if (idata_r[13:7] > 0) begin
buff1 <= {1'b1,idata_r[13:7]};
buff1_req <= 1'b1;
end
else begin
buff1 <= 8'd0;
buff1_req <= 1'b0;
end
end
always @ (posedge clk,negedge rst_n) begin
if (rst_n == 1'b0) begin
buff2 <= 8'd0;
buff2_req <= 1'b0;
end
else
if (idata_r[20:14] > 0) begin
buff2 <= {1'b1,idata_r[20:14]};
buff2_req <= 1'b1;
end
else begin
buff2 <= 8'd0;
buff2_req <= 1'b0;
end
end
always @ (posedge clk,negedge rst_n) begin
if (rst_n == 1'b0) begin
buff3 <= 8'd0;
buff3_req <= 1'b0;
end
else
if (idata_r[27:21] > 0) begin
buff3 <= {1'b1,idata_r[27:21]};
buff3_req <= 1'b1;
end
else begin
buff3 <= 8'd0;
buff3_req <= 1'b0;
end
end
always @ (posedge clk,negedge rst_n) begin
if (rst_n == 1'b0) begin
buff4 <= 8'd0;
buff4_req <= 1'b0;
end
else
if (idata_r[34:28] > 0) begin
buff4 <= {1'b1,idata_r[34:28]};
buff4_req <= 1'b1;
end
else begin
buff4 <= 8'd0;
buff4_req <= 1'b0;
end
end
always @ (posedge clk,negedge rst_n) begin
if (rst_n == 1'b0) begin
buff5 <= 8'd0;
buff5_req <= 1'b0;
end
else
if (idata_r[41:35] > 0) begin
buff5 <= {1'b1,idata_r[41:35]};
buff5_req <= 1'b1;
end
else begin
buff5 <= 8'd0;
buff5_req <= 1'b0;
end
end
always @ (posedge clk,negedge rst_n) begin
if (rst_n == 1'b0) begin
buff6 <= 8'd0;
buff6_req <= 1'b0;
end
else
if (idata_r[48:42] > 0) begin
buff6 <= {1'b1,idata_r[48:42]};
buff6_req <= 1'b1;
end
else begin
buff6 <= 8'd0;
buff6_req <= 1'b0;
end
end
always @ (posedge clk,negedge rst_n) begin
if (rst_n == 1'b0) begin
buff7 <= 8'd0;
buff7_req <= 1'b0;
end
else
if (idata_r[55:49] > 0) begin
buff7 <= {1'b1,idata_r[55:49]};
buff7_req <= 1'b1;
end
else begin
buff7 <= 8'd0;
buff7_req <= 1'b0;
end
end
always @ (posedge clk,negedge rst_n) begin
if (rst_n == 1'b0) begin
buff8 <= 8'd0;
buff8_req <= 1'b0;
end
else
if (idata_r[62:56] > 0) begin
buff8 <= {1'b1,idata_r[62:56]};
buff8_req <= 1'b1;
end
else begin
buff8 <= 8'd0;
buff8_req <= 1'b0;
end
end
always @ (posedge clk,negedge rst_n) begin
if (rst_n == 1'b0) begin
buff9 <= 8'd0;
buff9_req <= 1'b0;
end
else
if (idata_r[63] == 1'b1) begin
buff9 <= {1'b0,5'b00000,idata_r[63]};
buff9_req <= 1'b1;
end
else begin
buff9 <= 8'd0;
buff9_req <= 1'b0;
end
end
always @ (posedge clk,negedge rst_n) begin
if (rst_n == 1'b0) begin
odata0 <= 64'd0;
odata1 <= 56'd0;
odata2 <= 48'd0;
odata3 <= 40'd0;
odata4 <= 32'd0;
odata5 <= 24'd0;
odata6 <= 16'd0;
odata7 <= 8'd0;
ovalid0 <= 1'b0;
ovalid1 <= 1'b0;
ovalid2 <= 1'b0;
ovalid3 <= 1'b0;
ovalid4 <= 1'b0;
ovalid5 <= 1'b0;
ovalid6 <= 1'b0;
ovalid7 <= 1'b0;
end
else
casex({buff0_req,buff1_req,buff2_req,buff3_req,buff4_req,buff5_req,buff6_req,buff7_req})
8'b0000_0000 : begin
odata0 <= 64'd0; ovalid0 <= 1'b0;
odata1 <= 56'd0; ovalid1 <= 1'b0;
odata2 <= 48'd0; ovalid1 <= 1'b0;
odata3 <= 40'd0; ovalid1 <= 1'b0;
odata4 <= 32'd0; ovalid1 <= 1'b0;
odata5 <= 24'd0; ovalid1 <= 1'b0;
odata6 <= 16'd0; ovalid1 <= 1'b0;
odata7 <= 8'd0; ovalid1 <= 1'b0;
end
8'b1000_0000 : begin
odata0 <= 64'd0; ovalid0 <= 1'b0;
odata1 <= 56'd0; ovalid1 <= 1'b0;
odata2 <= 48'd0; ovalid1 <= 1'b0;
odata3 <= 40'd0; ovalid1 <= 1'b0;
odata4 <= 32'd0; ovalid1 <= 1'b0;
odata5 <= 24'd0; ovalid1 <= 1'b0;
odata6 <= 16'd0; ovalid1 <= 1'b0;
odata7 <= buff0; ovalid7 <= 1'b1;
end
8'bx100_0000 : begin
odata0 <= 64'd0; ovalid0 <= 1'b0;
odata1 <= 56'd0; ovalid1 <= 1'b0;
odata2 <= 48'd0; ovalid1 <= 1'b0;
odata3 <= 40'd0; ovalid1 <= 1'b0;
odata4 <= 32'd0; ovalid1 <= 1'b0;
odata5 <= 24'd0; ovalid1 <= 1'b0;
odata6 <= {buff0,buff1}; ovalid6 <= 1'b1;
odata7 <= 8'd0; ovalid7 <= 1'b0;
end
8'bxx10_0000 : begin
odata0 <= 64'd0; ovalid0 <= 1'b0;
odata1 <= 56'd0; ovalid1 <= 1'b0;
odata2 <= 48'd0; ovalid1 <= 1'b0;
odata3 <= 40'd0; ovalid1 <= 1'b0;
odata4 <= 32'd0; ovalid1 <= 1'b0;
odata5 <= {buff0,buff1,buff2}; ovalid5 <= 1'b1;
odata6 <= 16'd0; ovalid1 <= 1'b0;
odata7 <= 8'd0; ovalid7 <= 1'b0;
end
8'bxxx1_0000 : begin
odata0 <= 64'd0; ovalid0 <= 1'b0;
odata1 <= 56'd0; ovalid1 <= 1'b0;
odata2 <= 48'd0; ovalid1 <= 1'b0;
odata3 <= 40'd0; ovalid1 <= 1'b0;
odata4 <= {buff0,buff1,buff2,buff3}; ovalid4 <= 1'b1;
odata5 <= 24'd0; ovalid1 <= 1'b0;
odata6 <= 16'd0; ovalid1 <= 1'b0;
odata7 <= 8'd0; ovalid7 <= 1'b0;
end
8'bxxxx_1000 : begin
odata0 <= 64'd0; ovalid0 <= 1'b0;
odata1 <= 56'd0; ovalid1 <= 1'b0;
odata2 <= 48'd0; ovalid1 <= 1'b0;
odata3 <= {buff0,buff1,buff2,buff3,buff4}; ovalid3 <= 1'b1;
odata4 <= 32'd0; ovalid1 <= 1'b0;
odata5 <= 24'd0; ovalid1 <= 1'b0;
odata6 <= 16'd0; ovalid1 <= 1'b0;
odata7 <= 8'd0; ovalid7 <= 1'b0;
end
8'bxxxx_x100 : begin
odata0 <= 64'd0; ovalid0 <= 1'b0;
odata2 <= {buff0,buff1,buff2,buff3,buff4,buff5}; ovalid2 <= 1'b1;
odata3 <= 40'd0; ovalid1 <= 1'b0;
odata4 <= 32'd0; ovalid1 <= 1'b0;
odata5 <= 24'd0; ovalid1 <= 1'b0;
odata6 <= 16'd0; ovalid1 <= 1'b0;
odata7 <= 8'd0; ovalid1 <= 1'b0;
end
8'bxxxx_xx10 : begin
odata0 <= 64'd0; ovalid0 <= 1'b0;
odata1 <= {buff0,buff1,buff2,buff3,buff4,buff5,buff6}; ovalid1 <= 1'b1;
odata2 <= 48'd0; ovalid1 <= 1'b0;
odata3 <= 40'd0; ovalid1 <= 1'b0;
odata4 <= 32'd0; ovalid1 <= 1'b0;
odata5 <= 24'd0; ovalid1 <= 1'b0;
odata6 <= 16'd0; ovalid1 <= 1'b0;
odata7 <= 8'd0; ovalid1 <= 1'b0;
end
8'bxxxx_xxx1 : begin
odata0 <= {buff0,buff1,buff2,buff3,buff4,buff5,buff6,buff7}; ovalid0 <= 1'b1;
odata1 <= 56'd0; ovalid1 <= 1'b0;
odata2 <= 48'd0; ovalid1 <= 1'b0;
odata3 <= 40'd0; ovalid1 <= 1'b0;
odata4 <= 32'd0; ovalid1 <= 1'b0;
odata5 <= 24'd0; ovalid1 <= 1'b0;
odata6 <= 16'd0; ovalid1 <= 1'b0;
odata7 <= 8'd0; ovalid1 <= 1'b0;
end
default : begin
odata0 <= {buff0,buff1,buff2,buff3,buff4,buff5,buff6,buff7}; ovalid0 <= 1'b1;
odata1 <= 56'd0; ovalid1 <= 1'b0;
odata2 <= 48'd0; ovalid1 <= 1'b0;
odata3 <= 40'd0; ovalid1 <= 1'b0;
odata4 <= 32'd0; ovalid1 <= 1'b0;
odata5 <= 24'd0; ovalid1 <= 1'b0;
odata6 <= 16'd0; ovalid1 <= 1'b0;
odata7 <= 8'd0; ovalid1 <= 1'b0;
end
endcase
end
endmodule 五、仿真测试及结果
仿真测试代码如下：
`timescale 1ns/1ps
module varint_encode_tb;
reg clk;
reg rst_n;
reg ivalid;
reg [63:0] idata;
wire [63:0] odata0;
wire [55:0] odata1;
wire [47:0] odata2;
wire [39:0] odata3;
wire [31:0] odata4;
wire [23:0] odata5;
wire [15:0] odata6;
wire [7:0] odata7;
wire ovalid0;
wire ovalid1;
wire ovalid2;
wire ovalid3;
wire ovalid4;
wire ovalid5;
wire ovalid6;
wire ovalid7;
varint_encode varint_encode_inst(
.clk (clk),
.rst_n (rst_n),
.idata (idata),
.ivalid (ivalid),
.odata0 (odata0),
.odata1 (odata1),
.odata2 (odata2),
.odata3 (odata3),
.odata4 (odata4),
.odata5 (odata5),
.odata6 (odata6),
.odata7 (odata7),
.ovalid0 (ovalid0),
.ovalid1 (ovalid1),
.ovalid2 (ovalid2),
.ovalid3 (ovalid3),
.ovalid4 (ovalid4),
.ovalid5 (ovalid5),
.ovalid6 (ovalid6),
.ovalid7 (ovalid7)
);
initial clk = 1'b0;
always # 10 clk = ~clk;
initial begin
rst_n = 1'b0;
ivalid = 1'b0;
idata = 64'd0;
# 201;
rst_n = 1'b1;
# 200;
@ (posedge clk);
# 2;
idata = 64'b00000000_00000000_00010001_11011001_00110011_10101001_11001100_00110011;
ivalid = 1'b1;
@ (posedge clk);
# 2;
idata = 64'd0;
ivalid = 1'b0;
@ (posedge clk);
# 2;
idata = 64'b00000000_00000001_00010001_11011001_00110011_10101001_11001100_00110011;
ivalid = 1'b1;
@ (posedge clk);
# 2;
idata = 64'd0;
ivalid = 1'b0;
@ (posedge clk);
# 2;
idata = 64'b00000000_00000000_00000001_11011001_00110011_10101001_11001100_00110011;
ivalid = 1'b1;
@ (posedge clk);
# 2;
idata = 64'd0;
ivalid = 1'b0;
@ (posedge clk);
# 2;
idata = 64'b00000000_00000000_00000000_00000001_00110011_10101001_11001100_00110011;
ivalid = 1'b1;
@ (posedge clk);
# 2;
idata = 64'd0;
ivalid = 1'b0;
@ (posedge clk);
# 2;
idata = 64'b00000000_00000000_00000000_00000000_00000000_10101001_11001100_00110011;
ivalid = 1'b1;
@ (posedge clk);
# 2;
idata = 64'd0;
ivalid = 1'b0;
# 2000;
$stop;
end
endmodule 仿真结果：
将得到的仿真结果与上文经过Varint编码压缩后的结果对比可知，仿真结果正确。
五、总结
在进行原理理解与设计实现的时候，需要注意，逆序是字节的逆序，并非每一bit的数据都要进行逆序，且最高位是补位，代表后面还有无数据，并非是实际数据，在进行解码的时候要注意去掉每一个有效数据组的最高位，再进行拼接，这样得到的数据才是正确的数据，否则得到的将是错误数据。考虑到FPGA位宽定义的局限性，需要对每一个可能性的位宽大小均进行定义，并且定义一个相应的脉冲信号，告诉后级模块哪一个数据是有效的，这样设计才不会出错，否则输出的大小与原来输入的大小相同，也就失去了设计的意义。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
