哥伦布编码

哥伦布编码解码
UINT GetUeValue(BYTE *pBuff, UINT nLen, UINT &nStartBit)
{
    //计算0bit的个数
    UINT nZeroNum = 0;
    while (nStartBit < nLen * 8)
    {
        if (pBuff[nStartBit / 8] & (0x80 >> (nStartBit % 8)))
        {
            break;
        }
        nZeroNum++;
        nStartBit++;
    }
    nStartBit ++;


    //计算结果
    DWORD dwRet = 0;
    for (UINT i=0; i<nZeroNum; i++)
    {
        dwRet <<= 1;
        if (pBuff[nStartBit / 8] & (0x80 >> (nStartBit % 8)))
        {
            dwRet += 1;
        }
        nStartBit++;
    }
    return (1 << nZeroNum) - 1 + dwRet;
}






1. H.264/AVC标准规定了一系列编码方法，用于把符号编码成二进制比特流。这些方法包括：
FLC (定长码)
ExpG (指数哥伦布码)
CAVLC
CABAC


位于Slice data级别之上的符号，使用FLC或ExpG编码。


2. ExpG依据变字长编码理论。在变字长编码中，编码器的编码输出码字是长度不等的码字。大概率出现的信息符号，赋以短字长的码字；小概率出现的信息符号，赋以长字长的码字。


ExpG码字的二进制结构如下：
[前导零][1][INFO]
码字包含M个前导零(M>=0)，
        bit 1，
        M-bit信息域INFO。


根据输入的参数code_num，ExpG码的编码过程是：
M = floor(log2(code_num + 1))
INFO = code_num + 1 - 2^M


相应的，解码过程是：
(1) 读取一系列连续的bit 0直到bit 1，记录bit 0的个数(M)，
(2) 读取bit 1
(3) 读取M-bit = INFO
(4) code_num = 2^M + INFO - 1


由此，ExpG的码字长度是2M+1比特。


3. 映射
H.264的语法参数k通过4种方式映射为code_num，然后对code_num使用ExpG编码，生成二进制码字。
4种映射方式：
ue 无符号直接映射，code_num = k
te 截断映射
se 有符号映射，code_num = 2|k| (k<=0)
               code_num = 2|k| - 1 (k>0)
me 根据标准中指定的表


4. ExpG解码的实现与优化
以FFMpeg中的get_ue_golomb()函数为例，ExpG的解码算法的优化既考虑运算量又考虑存储空间。
(1) 根据当前二进制ExpG码的比特地址index，读取n-bit的二进制数据到32-bit buf。
buf = swap32(*(uint32_t *)((uint8_t *)bit_stream + (index>>3))) << (index&0x07)
swap32()的作用是在按32位读取bit stream时，处理大尾数、小尾数的转换。


--------------------------
| index%8 | buf的有效位n |
--------------------------
| 0       | 32-bit       |
--------------------------
| 1       | 31-bit       |
--------------------------
| 2       | 30-bit       |
--------------------------
| 3       | 29-bit       |
--------------------------
| 4       | 28-bit       |
--------------------------
| 5       | 27-bit       |
--------------------------
| 6       | 26-bit       |
--------------------------
| 7       | 25-bit       |
--------------------------


例如，当index%8=7时，buf的[31,6]位是有效的。


(2) 通过查表与计算相结合的方法，确定ExpG的码长，再进行解码。
(2.1) FFMpeg的实现方法是对码长不超过9-bit的ExpG码字制作查找表，如下：
当(buf >= 1<<27)，取buf的最高9位，
ExpG码 00001xxxx，码长9-bit，解码结果为[15,30]；
ExpG码 0001xxxnn，码长7-bit，解码结果为[7,14]，n表示不属于该ExpG码的bit；
ExpG码 001xxnnnn，码长5-bit，解码结果为[3,6]，n表示不属于该ExpG码的bit；
ExpG码 01xnnnnnn，码长3-bit，解码结果为[1,2]，n表示不属于该ExpG码的bit；
ExpG码 1nnnnnnnn，码长1-bit，解码结果为0，n表示不属于该ExpG码的bit。


查找表为
index = [16,31]   ~ codeword_length = 9 ~ code_num = [15,30]
index = [32,63]   ~ codeword_length = 7 ~ code_num = [7,14]
index = [64,127]  ~ codeword_length = 5 ~ code_num = [3,6]
index = [128,255] ~ codeword_length = 3 ~ code_num = [1,2]
index = [256,511] ~ codeword_length = 1 ~ code_num = 0


(2.2) 对于码长大于9-bit的ExpG码，
(a) 算出bit 1的位置x
(b) ExpG码长 = 2*(31-x) + 1
(c) ExpG码 = buf >> 32 - (2*(31-x)+1) = buf >> (2*x - 31)
(d) code_num = ExpG码 - 1


当读入buf的有效位是25-bit时，FFMpeg的ExpG解码优化算法能表示的最大值为8190。