跳到主要内容

10. 解码算法

  1. 解码算法

产生未压缩数据的解码算法如下:

该算法描述 Brotli 压缩流如何按 meta-block 逐步解码. 伪代码中的字段名、数组名和符号名对应比特流格式, 因此保持英文原文. 中文说明用于解释控制流: 解码器先读取窗口大小和 meta-block 标志, 然后根据是否为未压缩块、是否存在多种 block type、上下文映射和前缀码表来恢复 literal、insert/copy length 和 distance.

  read window size
  do
     read ISLAST bit
     if ISLAST
        read ISLASTEMPTY bit
        if ISLASTEMPTY
           break from loop
     read MNIBBLES
     if MNIBBLES is zero
        verify reserved bit is zero
        read MSKIPLEN
        skip any bits up to the next byte boundary
        skip MSKIPLEN bytes
        continue to the next meta-block
     else
        read MLEN
     if not ISLAST
        read ISUNCOMPRESSED bit
        if ISUNCOMPRESSED
           skip any bits up to the next byte boundary
           copy MLEN bytes of compressed data as literals
           continue to the next meta-block

     loop for each three block categories (i = L, I, D)
        read NBLTYPESi
        if NBLTYPESi >= 2
           read prefix code for block types, HTREE_BTYPE_i
           read prefix code for block counts, HTREE_BLEN_i
           read block count, BLEN_i
           set block type, BTYPE_i to 0
           initialize second-to-last and last block types to 0 and 1
        else
           set block type, BTYPE_i to 0
           set block count, BLEN_i to 16777216
     read NPOSTFIX and NDIRECT
     read array of literal context modes, CMODE[]
     read NTREESL
     if NTREESL >= 2
        read literal context map, CMAPL[]
     else
        fill CMAPL[] with zeros
     read NTREESD
     if NTREESD >= 2
        read distance context map, CMAPD[]
     else
        fill CMAPD[] with zeros
     read array of literal prefix codes, HTREEL[]
     read array of insert-and-copy length prefix codes, HTREEI[]
     read array of distance prefix codes, HTREED[]
     do
        if BLEN_I is zero
           read block type using HTREE_BTYPE_I and set BTYPE_I
              save previous block type
           read block count using HTREE_BLEN_I and set BLEN_I
        decrement BLEN_I
        read insert-and-copy length symbol using HTREEI[BTYPE_I]
        compute insert length, ILEN, and copy length, CLEN
        loop for ILEN
           if BLEN_L is zero
              read block type using HTREE_BTYPE_L and set BTYPE_L
                 save previous block type
              read block count using HTREE_BLEN_L and set BLEN_L
           decrement BLEN_L
           look up context mode CMODE[BTYPE_L]
           compute context ID, CIDL from last two uncompressed bytes
           read literal using HTREEL[CMAPL[64*BTYPE_L + CIDL]]
           write literal to uncompressed stream
        if number of uncompressed bytes produced in the loop for
           this meta-block is MLEN, then break from loop (in this
           case the copy length is ignored and can have any value)

        if distance code is implicit zero from insert-and-copy code
           set backward distance to the last distance
        else
           if BLEN_D is zero
              read block type using HTREE_BTYPE_D and set BTYPE_D
                 save previous block type
              read block count using HTREE_BLEN_D and set BLEN_D
           decrement BLEN_D
           compute context ID, CIDD from CLEN
           read distance code using HTREED[CMAPD[4*BTYPE_D + CIDD]]
           compute distance by distance short code substitution
           if distance code is not zero,
              and distance is not a static dictionary reference,
              push distance to the ring buffer of last distances
        if distance is less than the max allowed distance plus one
           move backwards distance bytes in the uncompressed data,
           and copy CLEN bytes from this position to
           the uncompressed stream
        else
           look up the static dictionary word, transform the word as
           directed, and copy the result to the uncompressed stream
     while number of uncompressed bytes for this meta-block < MLEN
  while not ISLAST

如果流在最后一个元块完成之前结束, 则应将该流拒绝为无效.

注意, 重复字符串引用可以引用前一个元块中的字符串, 即向后距离可以跨越一个或多个元块边界. 然而, 向后复制距离不会引用到未压缩流起点之前或窗口大小之外的位置. 任何此类距离都会被解释为对静态字典词的引用. 另请注意, 被引用的字符串可以与当前位置重叠. 例如, 如果最后解码的 2 个字节值为 X 和 Y, 则 <length = 5, distance = 2> 的字符串引用会向未压缩流添加 X,Y,X,Y,X.

实现时需要特别注意三个边界条件: meta-block 必须完整结束, backward distance 不能越过允许窗口, 静态字典引用与普通向后复制必须按距离范围区分. 这些条件直接影响解码器是否接受输入流, 也影响安全性和互操作性.

从实现角度看, 该伪代码还隐含了状态维护要求: literal、insert/copy length 和 distance 三类 block type 分别拥有自己的前缀码和剩余计数, 最近距离环形缓冲区只在有效的普通距离上更新, 而输出字节数始终以当前 meta-block 的 MLEN 为边界. 因此, 解码器不能把这些步骤简单合并为一次性表查找, 必须在每次读取符号后同步更新对应状态.

Source: RFC 7932 Official Text: https://www.rfc-editor.org/rfc/rfc7932.txt

最后于 更新