压缩算法：基于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 

五、总结

在进行原理理解与设计实现的时候，需要注意，逆序是字节的逆序，并非每一bit的数据都要进行逆序，且最高位是补位，代表后面还有无数据，并非是实际数据，在进行解码的时候要注意去掉每一个有效数据组的最高位，再进行拼接，这样得到的数据才是正确的数据，否则得到的将是错误数据。考虑到FPGA位宽定义的局限性，需要对每一个可能性的位宽大小均进行定义，并且定义一个相应的脉冲信号，告诉后级模块哪一个数据是有效的，这样设计才不会出错，否则输出的大小与原来输入的大小相同，也就失去了设计的意义。