本篇隸屬于文集：《H264/AVC 句法和語義詳解》伍茄，查看文集全部文章淹朋，請(qǐng)點(diǎn)擊文字鏈接。
想看最新文章唱蒸，可以直接關(guān)注微信公眾號(hào)：金架構(gòu)
上篇中我們介紹了Exp-Golomb的理論部分邦鲫，這一篇我們就使用C語言來實(shí)現(xiàn)它。
我們已經(jīng)知道神汹，在H.264中庆捺，指數(shù)哥倫布編碼有四個(gè)描述子，分別為ue(v)屁魏、se(v)滔以、me(v)、te(v)氓拼。其中me(v)是最簡(jiǎn)單的你画，它直接靠查表來實(shí)現(xiàn)。而剩余的se(v)和te(v)桃漾，是在ue(v)的基礎(chǔ)上來實(shí)現(xiàn)的坏匪。所以它們的利害關(guān)系不明而喻，ue(v)就代表了指數(shù)哥倫布編碼撬统。
下面我們就先重點(diǎn)介紹适滓，無符號(hào)指數(shù)哥倫布編碼：ue(v)。
1. ue(v)的編碼實(shí)現(xiàn)
由上一篇總結(jié)出恋追，指數(shù)哥倫布編碼的實(shí)現(xiàn)粒竖，可以分為以下幾步：
而考慮到是使用C語言，我們需要把步驟明確的更利于代碼實(shí)現(xiàn)：
圖中的Buffer几于，通常稱為緩沖器，其實(shí)在這里就是一個(gè)數(shù)組沿后。在圖中整個(gè)過程最重要的沿彭，就是要有這么一個(gè)工具，它能向Buffer中尖滚，循環(huán)寫入n個(gè)比特值喉刘。并且編碼下一個(gè)數(shù)時(shí)瞧柔，它還能接著在上一個(gè)比特末尾，繼續(xù)寫入睦裳。
而在編程語言中呢造锅，我們通常是在字節(jié)的級(jí)別上進(jìn)行操作，C語言也不例外廉邑，比如數(shù)組的取值和賦值哥蔚。所以我們需要定義這樣一個(gè)結(jié)構(gòu)體，來保存當(dāng)前指針在Buffer中的位置蛛蒙，也即指針正在指向哪個(gè)字節(jié)糙箍，以及在這個(gè)字節(jié)中，剩余可用的比特?cái)?shù)牵祟。
1.1 比特流操作結(jié)構(gòu)體
這個(gè)結(jié)構(gòu)體如下：
typedef struct
{
uint8_t*start; // 指向buf頭部指針
uint8_t*p; // 當(dāng)前指針位置
uint8_t* end; // 指向buf尾部指針
int bits_left; // 當(dāng)前讀取字節(jié)的剩余可用比特個(gè)數(shù)
} bs_t;
1.2 初始化對(duì)象
以面向?qū)ο蟮乃枷肷詈唬Y(jié)構(gòu)體就是一個(gè)類贡这。所以我們寫一個(gè)構(gòu)造器邑茄，使用Buffer來初始化這個(gè)比特流操作對(duì)象艾帐。
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; // 默認(rèn)剩余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;
}
同時(shí)別忘了釋放：
void bs_free(bs_t* b)
{
free(b);
}
1.3 寫入1個(gè)比特
然后我們可以拿這個(gè)對(duì)象（或句柄）荡陷，寫入1個(gè)比特换衬。
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.判斷是否寫到字節(jié)末尾定硝，如果是指針位置移向下一字節(jié)毫捣，比特位初始為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; } }
每次調(diào)用這個(gè)函數(shù)搭综，會(huì)向Buffer中寫入1個(gè)比特值筹淫。其中第二步包含四步：
（1）(v & 0x01)：按位與計(jì)算站辉，輸入?yún)?shù)v的末尾比特的值，就這個(gè)函數(shù)來講损姜，v為0或1饰剥，所以(v & 0x01)的值也即v的值
（2）((v & 0x01) << b->bits_left)：將第（1）步計(jì)算出的比特值，移位至剩余可用比特位的最高位摧阅。
（3） (*(b->p)) | ((v & 0x01) << b->bits_left)：按位或運(yùn)算汰蓉，保留b->p指向字節(jié)之前寫入比特值的同時(shí)，把第(2)步新寫入的比特值加上
（4）把第（3）步結(jié)果賦值給*(b->p)
1.4 寫入n個(gè)比特
/**
寫入n個(gè)比特
@param b 比特流操作句柄
@param n 參數(shù)v所需的比特位個(gè)數(shù)
@param v 待寫入的值
*/
void bs_write_u(bs_t* b, int n, uint32_t v)
{
int i;
for (i = 0; i < n; i++)
{
// 循環(huán)調(diào)用bs_write_u1()棒卷，寫入n個(gè)比特
bs_write_u1(b, (v >> ( n - i - 1 ))&0x01 );
}
}
其中(v >> ( n - i - 1 ))&0x01分為兩步：
（1）v >> ( n - i - 1 )：把參數(shù)v向右移( n - i - 1 )位
（2）計(jì)算經(jīng)過第(1)步移位后顾孽，位于最低比特位的值
1.5 寫入指數(shù)哥倫布編碼后的值
這一步最重要的，就是需要計(jì)算指數(shù)哥倫布編碼后比规，所需要的比特位個(gè)數(shù)若厚，然后直接調(diào)用bs_write_u()寫入即可。
/**ue(v) 無符號(hào)指數(shù)哥倫布編碼*/
void bs_write_ue( bs_t *b, unsigned int val)
{
// val + 1所需的比特個(gè)數(shù)
int i_size = 0;
// 1.值為0~255時(shí)蜒什，所需的比特位個(gè)數(shù)表
static const int i_size0_255[256] =
{
1, // 0的二進(jìn)制所需的比特個(gè)數(shù)
1, // 1的二進(jìn)制所需的比特個(gè)數(shù)
2,2, // 2~3的二進(jìn)制所需的比特個(gè)數(shù)
3,3,3,3, // 4~7的二進(jìn)制所需的比特個(gè)數(shù)
4,4,4,4,4,4,4,4, // 8~15的二進(jìn)制所需的比特個(gè)數(shù)
5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5, // 16~31的二進(jìn)制所需的比特個(gè)數(shù)
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, // 32~63的二進(jìn)制所需的比特個(gè)數(shù)
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的二進(jìn)制所需的比特個(gè)數(shù)
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的二進(jìn)制所需的比特個(gè)數(shù)
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.指數(shù)哥倫布編碼第一步，先把輸入值+1
unsigned int tmp = ++val;
// 2.判斷所需比特個(gè)數(shù)是否大于16位
if( tmp >= 0x00010000 )
{
i_size += 16;
tmp >>= 16;
}
// 3.判斷此時(shí)所需比特個(gè)數(shù)是否大于8位
if( tmp >= 0x100 )
{
i_size += 8;
tmp >>= 8;
}
// 4.最終tmp移位至8位以內(nèi)，去查表
i_size += i_size0_255[tmp];
// 5.最終得出編碼val所需的總比特?cái)?shù)：2 * i_size - 1
// 寫入Buffer
bs_write_u( b, 2 * i_size - 1, val );
}
}
其中的表i_size0_255[]是個(gè)關(guān)鍵霎冯，在H.264的各個(gè)編解碼器中铃拇，查表是個(gè)很常見的優(yōu)化方法。而在這里沈撞，i_size0_255[]這個(gè)表慷荔，就包含了值為0~255時(shí)，所對(duì)應(yīng)的二進(jìn)制值的比特位個(gè)數(shù)缠俺。
這樣我們肯定會(huì)有疑問显晶，既然表中數(shù)據(jù)只能查0~255以內(nèi)的，那超過255的該怎么辦晋修？
這就是if判斷中吧碾，else的處理步驟。我們都知道墓卦，2的8次方就是256倦春，而256的二進(jìn)制剛好占用(8+1)=9個(gè)比特，而小于256的值例如255落剪，占用最多8個(gè)比特睁本。
所以如果我們最終是想查表獲得，則需要把大于8比特的值忠怖，都移位至8比特以內(nèi)呢堰，這就是else處理的核心。
首先凡泣，我們需要判斷val+1的值枉疼，是否大于16位，也即大于0x10000鞋拟。如果是骂维，則把所需比特個(gè)數(shù)i_size加16，然后向右移16位贺纲。
然后航闺，再判斷處理后的值，是否大于8位猴誊，也即大于0x100潦刃。如果是，則把所需比特個(gè)數(shù)i_size加8懈叹，然后向右移8位乖杠。
這樣一來，只要是32位以內(nèi)的數(shù)澄成，肯定能縮短至8位以內(nèi)滑黔，然后嗨皮的去查表就可以了笆包。當(dāng)然會(huì)有人說，那大于32位的數(shù)該怎么辦略荡？這個(gè)請(qǐng)放寬心，這個(gè)是絕對(duì)不可能出現(xiàn)的歉胶，要知道2的32次方是多少汛兜？是四十多億，沒錯(cuò)通今，是億級(jí)別的粥谬！所以這個(gè)是幾乎不可能的！
而且從上一篇我們就知道辫塌，指數(shù)哥倫布編碼漏策，只適合小數(shù)值比大數(shù)值概率高的編碼，數(shù)值越大占得位數(shù)越大臼氨。所以除非不懂指數(shù)哥倫布編碼掺喻，否則我們不可能用這么大的數(shù)。
所以最終呢储矩，我們就得到ue(v)所需的總比特?cái)?shù)2 * i_size - 1感耙，然后調(diào)用bs_write_u()寫入buffer就可以了。
2. se(v)的編碼實(shí)現(xiàn)
實(shí)現(xiàn)了ue(v)持隧，再實(shí)現(xiàn)se(v)就很簡(jiǎn)單了即硼。因?yàn)閟e(v)也稱有符號(hào)指數(shù)哥倫布編碼，也即把ue(v)無符號(hào)指數(shù)哥倫布編碼拓展至了負(fù)數(shù)屡拨。它的編碼方式是：
當(dāng)待編碼整數(shù)x≤0時(shí)只酥，映射為偶數(shù)-2x，然后對(duì)-2x使用無符號(hào)指數(shù)哥倫布編碼
當(dāng)待編碼整數(shù)x>0時(shí)呀狼，映射為奇整數(shù)2x-1裂允，然后對(duì)2x-1使用無符號(hào)指數(shù)哥倫布編碼
所以se(v)的實(shí)現(xiàn)如下：
/**se(v) 有符號(hào)指數(shù)哥倫布編碼*/
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)的編碼實(shí)現(xiàn)
/** te(v) 截?cái)嘀笖?shù)哥倫布編碼 */
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)進(jìn)行編碼。
最后注意她奥，給Buffer開辟存儲(chǔ)空間時(shí)瓮增，要使用calloc()，不要用malloc()哩俭，否則會(huì)出現(xiàn)初始值不為0的情況绷跑。
本文源碼地址如下：
1、GitHub：https://github.com/Gosivn/Exp-Golomb-C-implementation
2凡资、CSDN：https://download.csdn.net/download/u011399342/10321706
[注]：本文的實(shí)現(xiàn)嚴(yán)重參考x264源碼砸捏！
