【H264/AVC 句法和语义详解】：C语言实现Exp-Golo
转载自：https://www.jianshu.com/p/06e7c742de44
上篇中我们介绍了Exp-Golomb的理论部分，这一篇我们就使用C语言来实现它。
我们已经知道，在H.264中，指数哥伦布编码有四个描述子，分别为ue(v)、se(v)、me(v)、te(v)。其中me(v)是最简单的，它直接靠查表来实现。而剩余的se(v)和te(v)，是在ue(v)的基础上来实现的。所以它们的利害关系不明而喻，ue(v)就代表了指数哥伦布编码。
下面我们就先重点介绍，无符号指数哥伦布编码：ue(v)。
1. ue(v)的编码实现
由上一篇总结出，指数哥伦布编码的实现，可以分为以下几步：
image
而考虑到是使用C语言，我们需要把步骤明确的更利于代码实现：
image
图中的Buffer，通常称为缓冲器，其实在这里就是一个数组。在图中整个过程最重要的，就是要有这么一个工具，它能向Buffer中，循环写入n个比特值。并且编码下一个数时，它还能接着在上一个比特末尾，继续写入。
而在编程语言中呢，我们通常是在字节的级别上进行操作，C语言也不例外，比如数组的取值和赋值。所以我们需要定义这样一个结构体，来保存当前指针在Buffer中的位置，也即指针正在指向哪个字节，以及在这个字节中，剩余可用的比特数。
1.1 比特流操作结构体
这个结构体如下：
typedef struct
{
uint8_t*start; // 指向buf头部指针
uint8_t*p; // 当前指针位置
uint8_t* end; // 指向buf尾部指针
int bits_left; // 当前读取字节的剩余可用比特个数
} bs_t;
1.2 初始化对象
以面向对象的思想，结构体就是一个类。所以我们写一个构造器，使用Buffer来初始化这个比特流操作对象。
bs_t* bs_init(bs_t* b, uint8_t* buf, size_t size)
{
b->start = buf; // 指向buf起始位置
b->p = buf; // 初始位置与start保持一致
b->end = buf + size; // 指向buf末尾
b->bits_left = 8; // 默认剩余8比特可用
return b;
}
bs_t* bs_new(uint8_t* buf, size_t size)
{
bs_t* b = (bs_t*)malloc(sizeof(bs_t));
bs_init(b, buf, size);
return b;
}
同时别忘了释放：
void bs_free(bs_t* b)
{
free(b);
}
1.3 写入1个比特
然后我们可以拿这个对象（或句柄），写入1个比特。
void bs_write_u1(bs_t* b, uint32_t v)
{
// 1.剩余比特先减1
b->bits_left--;
if (! bs_eof(b))
{
// 2.见文章
(*(b->p)) |= ((v & 0x01) << b->bits_left);
}
// 3.判断是否写到字节末尾，如果是指针位置移向下一字节，比特位初始为8
if (b->bits_left == 0) { b->p ++; b->bits_left = 8; }
}
/** 是否已读到末尾（end_of_file） */
int bs_eof(bs_t* b) { if (b->p >= b->end) { return 1; } else { return 0; } }
每次调用这个函数，会向Buffer中写入1个比特值。其中第二步包含四步：
（1）(v & 0x01)：按位与计算，输入参数v的末尾比特的值，就这个函数来讲，v为0或1，所以(v & 0x01)的值也即v的值
（2）((v & 0x01) << b->bits_left)：将第（1）步计算出的比特值，移位至剩余可用比特位的最高位。
（3） (*(b->p)) | ((v & 0x01) << b->bits_left)：按位或运算，保留b->p指向字节之前写入比特值的同时，把第(2)步新写入的比特值加上
（4）把第（3）步结果赋值给*(b->p)
1.4 写入n个比特
/**
写入n个比特
@param b 比特流操作句柄
@param n 参数v所需的比特位个数
@param v 待写入的值
*/
void bs_write_u(bs_t* b, int n, uint32_t v)
{
int i;
for (i = 0; i < n; i++)
{
// 循环调用bs_write_u1()，写入n个比特
bs_write_u1(b, (v >> ( n - i - 1 ))&0x01 );
}
}
其中(v >> ( n - i - 1 ))&0x01分为两步：
（1）v >> ( n - i - 1 )：把参数v向右移( n - i - 1 )位
（2）计算经过第(1)步移位后，位于最低比特位的值
1.5 写入指数哥伦布编码后的值
这一步最重要的，就是需要计算指数哥伦布编码后，所需要的比特位个数，然后直接调用bs_write_u()写入即可。
/**ue(v) 无符号指数哥伦布编码*/
void bs_write_ue( bs_t *b, unsigned int val)
{
// val + 1所需的比特个数
int i_size = 0;
// 1.值为0~255时，所需的比特位个数表
static const int i_size0_255[256] =
{
1, // 0的二进制所需的比特个数
1, // 1的二进制所需的比特个数
2,2, // 2~3的二进制所需的比特个数
3,3,3,3, // 4~7的二进制所需的比特个数
4,4,4,4,4,4,4,4, // 8~15的二进制所需的比特个数
5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5, // 16~31的二进制所需的比特个数
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, // 32~63的二进制所需的比特个数
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, // 64~127的二进制所需的比特个数
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, // 128~255的二进制所需的比特个数
8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
};
if( val == 0 ) // 输入为0，直接编码为1
{
bs_write_u1( b, 1 );
}
else
{
// 1.指数哥伦布编码第一步，先把输入值+1
unsigned int tmp = ++val;
// 2.判断所需比特个数是否大于16位
if( tmp >= 0x00010000 )
{
i_size += 16;
tmp >>= 16;
}
// 3.判断此时所需比特个数是否大于8位
if( tmp >= 0x100 )
{
i_size += 8;
tmp >>= 8;
}
// 4.最终tmp移位至8位以内，去查表
i_size += i_size0_255[tmp];
// 5.最终得出编码val所需的总比特数：2 * i_size - 1
// 写入Buffer
bs_write_u( b, 2 * i_size - 1, val );
}
}
其中的表i_size0_255[]是个关键，在H.264的各个编解码器中，查表是个很常见的优化方法。而在这里，i_size0_255[]这个表，就包含了值为0~255时，所对应的二进制值的比特位个数。
这样我们肯定会有疑问，既然表中数据只能查0~255以内的，那超过255的该怎么办？
这就是if判断中，else的处理步骤。我们都知道，2的8次方就是256，而256的二进制刚好占用(8+1)=9个比特，而小于256的值例如255，占用最多8个比特。
所以如果我们最终是想查表获得，则需要把大于8比特的值，都移位至8比特以内，这就是else处理的核心。
首先，我们需要判断val+1的值，是否大于16位，也即大于0x10000。如果是，则把所需比特个数i_size加16，然后向右移16位。
然后，再判断处理后的值，是否大于8位，也即大于0x100。如果是，则把所需比特个数i_size加8，然后向右移8位。
这样一来，只要是32位以内的数，肯定能缩短至8位以内，然后嗨皮的去查表就可以了。当然会有人说，那大于32位的数该怎么办？这个请放宽心，这个是绝对不可能出现的，要知道2的32次方是多少？是四十多亿，没错，是亿级别的！所以这个是几乎不可能的！
而且从上一篇我们就知道，指数哥伦布编码，只适合小数值比大数值概率高的编码，数值越大占得位数越大。所以除非不懂指数哥伦布编码，否则我们不可能用这么大的数。
所以最终呢，我们就得到ue(v)所需的总比特数2 * i_size - 1，然后调用bs_write_u()写入buffer就可以了。
2. se(v)的编码实现
实现了ue(v)，再实现se(v)就很简单了。因为se(v)也称有符号指数哥伦布编码，也即把ue(v)无符号指数哥伦布编码拓展至了负数。它的编码方式是：
当待编码整数x≤0时，映射为偶数-2x，然后对-2x使用无符号指数哥伦布编码
当待编码整数x>0时，映射为奇整数2x-1，然后对2x-1使用无符号指数哥伦布编码
所以se(v)的实现如下：
/**se(v) 有符号指数哥伦布编码*/
void bs_write_se(bs_t* b, int32_t v)
{
if (v <= 0)
{
bs_write_ue(b, -v*2);
}
else
{
bs_write_ue(b, v*2 - 1);
}
}
3. te(v)的编码实现
/** te(v) 截断指数哥伦布编码 */
void bs_write_te( bs_t *b, int x, int val)
{
if( x == 1 )
{
bs_write_u1( b, 1&~val );
}
else if( x > 1 )
{
bs_write_ue( b, val );
}
}
其中x为语法元素范围的上限，如果上限为1，则为输入值val最低比特位的取反，否则使用ue(v)进行编码。
最后注意，给Buffer开辟存储空间时，要使用calloc()，不要用malloc()，否则会出现初始值不为0的情况。
