LZ77源码阅读笔记

读取的过程正好和写过程是对称：

ULONG ReadBitFromBitStream(    PUCHAR  pBuffer,    ULONG   ulBitOffset    ) {    ULONG   ulByteBoundary;    ULONG   ulOffsetInByte; //首先计算字符位置和字符内偏移量    ulByteBoundary = ulBitOffset>>3 ;    ulOffsetInByte = ulBitOffset&7; //然后通过偏移与0x00000001与运算就知道所给定的偏移位置上是0还是1    return ((*(PULONG)(pBuffer+ulByteBoundary))>>ulOffsetInByte)&1 ; }

Golomb编码：

先看一下Golomb编码的规范：

Golomb 编码。假设对正整数 x 进行 Golomb 编码，选择参数 m，令

b = 2^m

q = INT((x - 1)/b)

r = x - q^b - 1

则 x 可以被编码为两部分，第一部分是由 q 个 1 加 1 个 0 组成，第二部分为 m 位二进制数，其值为 r。我们将 m = 0, 1, 2, 3 时的 Golomb 编码表列出：

   值 x        m = 0       m = 1       m = 2       m = 3
-------------------------------------------------------------
    1             0         0 0        0 00        0 000
    2            10         0 1        0 01        0 001
    3           110        10 0        0 10        0 010
    4          1110        10 1        0 11        0 011
    5         11110       110 0       10 00        0 100
    6        111110       110 1       10 01        0 101
    7       1111110      1110 0       10 10        0 110
    8      11111110      1110 1       10 11        0 111
    9     111111110     11110 0      110 00       10 000
从表中我们可以看出，Golomb 编码不但符合前缀编码的规律，而且可以用较少的位表示
较小的 x 值，而用较长的位表示较大的 x 值。这样，如果 x 的取值倾向于比较小的数值，Golomb 编码就可以有效地节省空间。当然，根据 x 的分布规律不同，我们可以选取不同的 m 值以达到最好的压缩效果。

对我们上面讨论的三元组 len 值，我们可以采用 Golomb 方式编码。上面的讨论中 len 可能取 0，我们只需用 len + 1 的 Golomb 编码即可。至于参数 m 的选择，一般经验是取 3 或 4 即可。

ULONG WINAPI WriteGolombCode(    ULONG   x,    PUCHAR  pBuffer,    ULONG   ulBitOffset    ) {    ULONG           q, r;    int             i;    q = (x-1)>>m;    r = x-(q<<m)-1; //首先写q个1    for(i=0; (ULONG)i<q; i++, ulBitOffset++)    {        Write1ToBitStream(pBuffer, ulBitOffset);    } //q个1和m位r的2进制编码间用0隔开    Write0ToBitStream(pBuffer, ulBitOffset);    ulBitOffset++; //m位r的2进制编码    for(i=0; i<m; i++, ulBitOffset++)    {        if( (r>>i)&1 )        {            Write1ToBitStream(pBuffer, ulBitOffset);        }        else        {            Write0ToBitStream(pBuffer, ulBitOffset);        }    } //返回GolombCode长度，这个长度是解码时候计算偏移的增量有用    return m+q+1; }