H.264(四)指數哥倫布編碼（實作編碼）

前面介紹了指數哥倫布編碼，可以參考H.264(三)熵編碼和指數哥倫布編碼

在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)的編碼實作 ——————————————————————————

由上一篇總結出，指數哥倫布編碼的實作，可以分為以下幾步：

H.264(四)指數哥倫布編碼（實作編碼）
而考慮到是使用C語言，我們需要把步驟明确的更利于代碼實作：

H.264(四)指數哥倫布編碼（實作編碼）

圖中的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 寫入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.4 寫入1個比特

然後我們可以拿這個對象（或句柄），寫入1個比特。
void bs_write_u1(bs_t* b, uint32_t v)
{
   // 1.剩餘比特先減1
   b->bits_left--;
   if (! bs_eof(b))
   {
	   cout<<v;
       // 2.見文章
       *(b->p) <<= 1;
       *(b->p) |= (v & 0x01);
   }
   // 3.判斷是否寫到位元組末尾，如果是指針位置移向下一位元組，比特位初始為8
   if (b->bits_left == 0) {
	   b->p++;
	   b->bits_left = 8;//這樣就保證了每次寫入不會受比特的影響
	}
}
           
*(b->p) <<= 1; ：讓高位左移一位

*(b->p) |= (v & 0x01); ：加上新增加的資料bit

整個思路就是在buf中一個位元組，一個位元組的寫，當一個位元組寫完了，就移動到下一個位元組中繼續寫資料bit。

1.5 寫入指數哥倫布編碼後的值

這一步最重要的，就是需要計算指數哥倫布編碼後，所需要的比特位個數，然後直接調用bs_write_u()寫入即可。
/**ue(v) 無符号指數哥倫布編碼*/
unsigned int 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 );
	   return (2 * i_size - 1);
   }
}
           
其中的表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的情況。

完整執行個體代碼：————————————————————————

#include <stdio.h>
#include <iostream>
using namespace std;

typedef unsigned char uint8_t;
typedef unsigned int  uint32_t;
typedef struct
{
  uint8_t *start; // 指向buf頭部指針
  uint8_t *p;     // 目前指針位置
  uint8_t *end;   // 指向buf尾部指針
  int bits_left;  // 目前讀取位元組的剩餘可用比特個數
} bs_t;
//函數申明
int bs_eof(bs_t* b);
//
bs_t* bs_init(bs_t* b, uint8_t* buf, size_t size)
{
   b->p = buf;      // 初始位置與start保持一緻
   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);
}

void bs_write_u1(bs_t* b, uint32_t v)
{
   // 1.剩餘比特先減1
   b->bits_left--;
   if (! bs_eof(b))
   {
	   cout<<v;
       // 2.見文章
	   *(b->p) <<= 1;
       *(b->p) |= (v & 0x01);
   }
   // 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;
	}
}

/**
寫入n個比特
@param b 比特流操作句柄
@param n 參數v所需的比特位個數
@param v 待寫入的值
*/
void bs_write_u(bs_t* b, int n, uint32_t v)
{
   int i;
   //cout<< "n=" << n << "v=" << v <<endl;
   cout<<"轉換後的數:"
   for (i = 0; i < n; i++)
   {
       // 循環調用bs_write_u1()，寫入 v 的後 n 個比特
       bs_write_u1(b, (v >> ( n - i - 1 ))&0x01 );
   }
   cout<<endl;
   
}

/**ue(v) 無符号指數哥倫布編碼*/
unsigned int 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 );
	   return (2 * i_size - 1);
   }
}

void my_print(char *s, unsigned int n)
{
	int j;
	int i;
	unsigned int num;
	i = n % 8; //16進制中每3位為一個位元組，為8
	//printf("n = %u\n", n);
	num = (n >> 3) + 1;//占用幾個數組元素
	j = 0;
	while (j < num) {
		
		if (j == num - 1) i = n % 8;//最高的一個位元組不需要移8位
		else              i = 8;
		//printf("j = %d i = %d num = %d\n", j, i, num);
		for (; i > 0; i--) {
			cout<< ((s[j] >> (i - 1)) & 0x01) ;
		}		
		++j;
	}
	cout<<endl;
}
int main()
{	
	uint8_t buf[64] = {0};
	unsigned int i;
	memset(buf, 0, sizeof(buf));
	bs_t *pb = bs_new(buf, sizeof(buf));
	unsigned int j = 0;
	while (1) {
		cout<<"輸入:"
		cin>> i;
		j += bs_write_ue(pb, i);
		cout<<"輸出整個資料流:"
		my_print((char*)buf, j);
		//memset(buf, 0, sizeof(buf));
	}
	bs_free(pb);
	return 0;
}

運作結果：

輸入:1
轉換後的數:010
輸出整個資料流:010
輸入:2
轉換後的數:011
輸出整個資料流:010011
輸入:3
轉換後的數:00100
輸出整個資料流:01001100100
輸入:

H.264(四)指數哥倫布編碼（實作編碼）

1. ue(v)的編碼實作 ——————————————————————————

2. se(v)的編碼實作

3. te(v)的編碼實作

繼續閱讀

Wireshark 抓包分析 RTSP/RTP/RTCP 基本工作過程

Adobe Media Server 5（AMS）的安裝及使用

音視訊學習筆記001：初識H.264初識H.264主要組織

ffmpeg指令行

Linux FFmpeg編譯支援aac、h264、h2651、下載下傳ffmpeg源碼2、安裝aac、h264、h265庫3、配置ffmpeg編譯選項4、編譯、安裝

H.264(三)熵編碼和指數哥倫布編碼

H.264(六)序列參數集（SPS）

H264 專題

gstreamer1.16指令行學習

視訊編解碼基礎

android MediaPlayer NuPlayer以及Android MediaPlayerService解析

rtp和rtcp協定詳解

RTP包的包類型

Android擷取裝置支援的編解碼器

音視訊學習（十）——ps流1. 簡介2. PS流封裝标準3. PS封裝規則