深入理解GIF文件格式

大家好，本文我將給大家介紹一個完整的GIF(GraphicsInterChangeFormat)解碼器，使用了LZW（Lempel-Ziv-Welch Encoding，串標壓縮演算法）解壓縮器。

GIF本身已有25年的歷史，是最古老的圖像壓縮格式，至今仍在普遍使用。雖然它與流行的PNG和JPG格式有競爭，但它仍然是一種相當常見的圖像壓縮方法。正如你將看到的，GIF格式背後的許多設計考慮都是基於當時的硬體，而硬體本身現在已經過時了，但是格式總體上已經經受住了時間的考驗。

顏色表：

示例1：索引四色笑臉圖像

示例1演示了一個粗略繪製的笑臉圖像。因為它只有四種顏色，所以只需要四個調色板條目。這些調色板條目是從一個大的顏色空間中繪製的，但是這裡的每個像素都可以用2位表示。

這種「調色板」的圖像像素壓縮得相當多。原則上每個像素需要3個位元組來描述真彩色格式的圖像，但是通過這種方法對圖像進行調色板化，16色圖像的大小可以立即縮小6倍，因為每個像素只需要4位。更清晰的顏色意味著更少的壓縮，但是256色是相當多的，甚至一個256色調色板也代表了3：1的壓縮比。

GIF允許更複雜的壓縮，因為它允許編碼器將圖像分割成單獨的塊，每個塊都可能有自己的調色板，例如在左上象限中最常出現的具有256種顏色的圖像，可以將此象限指定為自己的塊，具有和其他象限不同的單獨的調色板。事實證明，沒有人利用這種超壓縮能力，而是改造它，以允許GIF動畫。我稍後再談這個。

GIF通過將LZW壓縮演算法應用於這些調色板索引，進一步壓縮索引數據本身。它以一種相當粗糙的方式實現——索引本身被視為一個長的線性位元組序列，LZW被應用到位元組本身。這種方法沒有考慮到這樣一個事實，即，任何給定行的第一個像素與前一行的第一個像素，比上一行的最後一個像素更有可能與前一行的第一個像素相同(LZW演算法就是這樣看待像素的)。

示例2：100像素寬的GIF

在示例2中，像素1和101比像素100和101更有可能是相同的，但是LZW演算法將看到像素101在100之後。儘管如此，LZW演算法最終提供了相當好的壓縮效果，它識別出單個行中的相似點，並重複從一行到下一行的模式。

與任何文件格式一樣，GIF以標準化的頭文件開頭：

下一個位元組是「欄位」位元組。欄位位元組被分解為(從最高有效位到最低有效位)如下：

W：標記全局顏色表的存在。回想一下，GIF允許編碼器將圖像細分為更大的壓縮塊，每個塊都有自己的顏色表，或者，可以給出一個所有塊都使用的單一「全局」顏色表，如果設置了這個位，則標題後面立即是一個全局顏色表。你會發現，幾乎所有的GIF都包含一個全局顏色表。

X：顏色解析度位數減1。這是顯示單元被認為能夠支持的顏色數的基數為2的對數——這與實際GIF中的顏色數不一樣。如果顯示器只能顯示16種顏色，而GIF表示它期望顯示器支持256種，那麼軟體很可能就會中止該顯示器。現在，這個值是信息性的(充其量)。

Y：「排序」標誌。為了理解排序標誌的效用，假設一個只能夠顯示16種顏色的顯示器顯示了一個64色的GIF。GIF編碼器可以使低解析度顯示器通過對調色板按顏色的頻率排序來近似顯示(可能完全跳過其他顏色或試圖找到它們最接近的匹配)。如果編碼器這樣做，則設置此標誌。如今，這面標誌的設置並不是特別重要，因為16色顯示器已經相當少了。

z：全局顏色表中的位數減1。因此，全局顏色表包含2z+1項。

背景顏色索引：如果沒有指定由該GIF描述的矩形區域中的任何像素，則將其設置為顏色。你可能會問，如何將其不設置像素值？畢竟，GIF本身被描述為一個矩形。然而，回想一下，GIF允許圖像被細分成更小的塊，它們本身不一定佔據整個圖像顯示區域。如果由於某種原因，左上和右下象限被定義，但是塊的其餘部分不是，則一些像素將被取消設置。

像素長寬比：同樣，這也是信息性的(充其量)，這告訴解碼器在原始圖像中像素寬度與高度的比值是多少。沒有描述解碼器如何利用這些信息，我不知道有哪個GIF解碼器會對此給予任何關注。

然後，可以像以下清單1所示那樣解析GIF標頭：

typedef struct{ unsigned short width; unsigned short height; unsigned char fields; unsigned char background_color_index; unsigned char pixel_aspect_ratio;}screen_descriptor_t;/** * @param gif_file the file descriptor of a file containing a * GIF-encoded file. This should point to the first byte in * the file when invoked. */static void process_gif_stream( int gif_file ){ unsigned char header[ 7 ]; screen_descriptor_t screen_descriptor; int color_resolution_bits; // A GIF file starts with a Header (section 17) if ( read( gif_file, header, 6 ) != 6 ) { perror( "Invalid GIF file (too short)" ); return; } header[ 6 ] = 0x0; // XXX there"s another format, GIF87a, that you may still find // floating around. if ( strcmp( "GIF89a", header ) ) { fprintf( stderr, "Invalid GIF file (header is "%s", should be "GIF89a")
", header ); return; } // Followed by a logical screen descriptor // Note that this works because GIFs specify little-endian order; on a // big-endian machine, the height & width would need to be reversed. // Can"t use sizeof here since GCC does byte alignment; // sizeof( screen_descriptor_t ) = 8! if ( read( gif_file, &screen_descriptor, 7 ) > 4 ) + 1;

如果欄位指示GIF包含一個全局顏色表，則它緊跟在標頭之後。大小是由標誌給出的，它指示全局顏色表包含了多少個3位元組的條目，每個標記分別指示每個索引的紅色、綠色和藍色的強度。以下清單2演示了全局顏色表的解析：

typedef struct{ unsigned char r; unsigned char g; unsigned char b;}rgb;...static void process_gif_stream( int gif_file ){ unsigned char header[ 7 ]; screen_descriptor_t screen_descriptor; int color_resolution_bits; int global_color_table_size; // number of entries in global_color_table rgb *global_color_table;... if ( screen_descriptor.fields & 0x80 ) { int i; // If bit 7 is set, the next block is a global color table; read it global_color_table_size = 1

這就結束了GIF文件的標題部分。標題後面是一系列塊，每個塊用一個位元組的塊類型標識符標出。其中最重要的是圖像描述符塊0x2C，這是存儲實際圖像索引的地方。其次是掛載塊0x3B，它指示一個GIF的結束——如果在文件結束之前沒有遇到這個掛載塊，則該文件以某種方式損壞。

因此，一旦解析了主標題和全局顏色表(如果有的話)，接下來要做的就是開始查找塊，並根據它們的類型解析它們，如下列清單3所示：

#define IMAGE_DESCRIPTOR 0x2C#define TRAILER 0x3B...static void process_gif_stream( int gif_file ){ unsigned char header[ 7 ]; screen_descriptor_t screen_descriptor; int color_resolution_bits; int global_color_table_size; // number of entries in global_color_table rgb *global_color_table; unsigned char block_type = 0x0;... while ( block_type != TRAILER ) { if ( read( gif_file, &block_type, 1 )

圖像描述符塊本身以一個9位元組的頭結構開始：

左端，頂部，寬度、高度表明在整個圖像的上下文中這個塊的起點和終點。記住，GIF允許幾個塊組成一個完整的圖像。

這些欄位又被分成以下幾個部分：

W：本地顏色表標誌。

X：交錯標誌。

Y：排序標誌。

Z：局部顏色表的大小。

第3項和第4項為「保留」且沒有定義，它們應該始終設置為0。

本地顏色表、排序標誌和本地顏色表的大小的解析與全局顏色表相同，本地顏色表的解析與全局顏色表的解析完全相同，這裡不再重複。不管怎樣，你會發現很少有.gif文件具有帶有本地顏色表的圖像描述符。

在全局標頭定義的標誌位元組中沒有類似項的一個位是隔行（interlace）標誌。要記住，GIF是針對慢速顯示硬體進行優化的，隔行掃描背後的理念是，顯示器可以在解析過程的早期以粗糙的格式顯示圖像，並逐步顯示越來越多的細節，直到圖像完全處理完畢。因此，如果設置了隔行標誌，則圖像中的行將不按順序排列：首先，每隔8行；接下來，從每8行的第4行開始；然後，從每4行的第2行開始；最後每隔一行，完成圖像。

示例3：26行GIF的交錯

示例3說明了如何存儲交錯文件。解釋來說就是，綠色標記的行將被讀取和顯示，首先是黃色標記的行，然後是藍色標記的行，最後是所有剩餘的行。儘管如此，即使在今天，你還是會發現互聯網上漂浮著一些交錯的GIF文件。

忽略LCT的解析，解析圖像描述符頭，如下列清單4所示：

typedef struct{ unsigned short image_left_position; unsigned short image_top_position; unsigned short image_width; unsigned short image_height; unsigned char fields;}image_descriptor_t;...static int process_image_descriptor( int gif_file, rgb *gct, int gct_size, int resolution_bits ){ image_descriptor_t image_descriptor; int disposition; // TODO there could actually be lots of these if ( read( gif_file, &image_descriptor, 9 )

在圖像描述符頭之後，在邏輯上仍然包含在圖像描述符塊本身中，這是一系列的數據子塊。這些數據子塊是活動顏色表中的LZW壓縮索引，如果圖像描述符塊包含一個局部顏色表，則這些是本地顏色表中的索引，否則，它們是全局顏色表中的索引。數據子塊本身被進一步細分為255個位元組的塊，每個塊聲明其長度為它的第一個單位元組。顯然，由於單個GIF可以是655356x65536=4294967296像素(理論上來說)，所以幾乎所有的圖像描述符都將由多個數據子塊組成，即使它們是壓縮的。然而，解碼器目前沒有足夠的信息來判斷有多少位元組的壓縮數據會跟隨而來。因此，解碼器必須轉而繼續讀取數據子塊，直到遇到一個零長度子塊，表示數據的壓縮結束。

這些壓縮數據的子塊可以讀入內存，如以下清單5所示。在這裡，我選擇通過反覆調用realloc來將整個混亂的東西塞進內存，任何值得認真對待的GIF實現都會在讀取數據時對其進行解壓縮，但這種實現更容易理解。

static int read_sub_blocks( int gif_file, unsigned char **data ){ int data_length; int index; unsigned char block_size; // Everything following are data sub-blocks, until a 0-sized block is // encountered. data_length = 0; *data = NULL; index = 0; while ( 1 ) { if ( read( gif_file, &block_size, 1 )

此時，壓縮數據完全包含在由COMPUT_DATA指定的緩衝區中，下一件要做的事就是解壓縮它。但是，要使用壓縮的GIF數據，需要做一些修改：

1.使用strcmp和strcat來實現LZW字典對GIF索引不起作用，因為它們包含嵌入零點，C的字元串操作將其解釋為「字元串結尾」。

2.該實現假設壓縮數據從8位代碼開始，並在字典填充時擴展到9位。實際上，GIF允許可變的起始大小，一直到4位代碼.。

要解決第一個問題，必須對字典本身進行改造。字典不是字元串數組，而是作為指針結構實現的。當遇到一個新的字典索引時，它是通過在最近的字典條目之上連接（使用strcat）最近讀取的代碼來創建的。更靈活的方法是定義一個結構，允許每個條目指向其前身，如下述清單6所示：

typedef struct{ unsigned char byte; int prev; int len;}dictionary_entry_t;

現在，由5個0x0位元組組成的字元串將在內存中表示為：

這些結構中的每一個都將由一個字典條目來指示，字典的索引(現在是指向DECUDY_ENTITY_t的指針數組)是從文件中讀取的擴展代碼。所以，如果前五個位元組都是0(這很常見)，並且全局顏色表包含64個條目：

在這裡，長度聲明只是一種便利，它不是絕對必要的(大多數GIF實現都省略了它，以加快解壓縮速度)。如果在數據流中遇到代碼69，解壓縮器將查找字典[69]，發現它的位元組是0，發出0，然後跟蹤反向指針&Dictory[68]，發出另一個0，依此類推。但是，這些條目是以「向後」的方式構建的，因此有必要以相反的順序發出它們。大多數GIF實現將位元組推送到堆棧上，然後將其彈出，以執行實際的解壓縮，與之相反的是，我會跟蹤長度，這樣我就知道在發出第一段代碼時，輸出緩衝區中要向前跳轉多少位元組。

一旦這個被平方，解決第二個問題——可變大小的LZW代碼的問題——就很簡單了：只需將起始代碼大小傳遞到解壓縮常式中即可。

清單7是完成的GIF友好解壓縮常式。請注意，有一個12位代碼的硬編碼限制，一旦字典擴展到212=4096項，就不允許再增長了，由編碼器來決定活動字典是否仍然在壓縮方面做得很好，或者它是否應該發送一個清晰的代碼，然後從頭開始。

int uncompress( int code_length, const unsigned char *input, int input_length, unsigned char *out ){ int maxbits; int i, bit; int code, prev = -1; dictionary_entry_t *dictionary; int dictionary_ind; unsigned int mask = 0x01; int reset_code_length; int clear_code; // This varies depending on code_length int stop_code; // one more than clear code int match_len; clear_code = 1 12 bits) dictionary[ dictionary_ind ].prev = -1; dictionary[ dictionary_ind ].len = 1; } // 2^code_len + 1 is the special "end" code; don"t give it an entry here dictionary_ind++; dictionary_ind++; // TODO verify that the very last byte is clear_code + 1 while ( input_length ) { code = 0x0; // Always read one more bit than the code length for ( i = 0; i 12 bits) dictionary[ dictionary_ind ].prev = -1; dictionary[ dictionary_ind ].len = 1; } dictionary_ind++; dictionary_ind++; prev = -1; continue; } else if ( code == stop_code ) { if ( input_length > 1 ) { fprintf( stderr, "Malformed GIF (early stop code)
" ); exit( 0 ); } break; } // Update the dictionary with this character plus the _entry_ // (character or string) that came before it if ( ( prev > -1 ) && ( code_length dictionary_ind ) { fprintf( stderr, "code = %.02x, but dictionary_ind = %.02x
", code, dictionary_ind ); exit( 0 ); } // Special handling for KwKwK if ( code == dictionary_ind ) { int ptr = prev; while ( dictionary[ ptr ].prev != -1 ) { ptr = dictionary[ ptr ].prev; } dictionary[ dictionary_ind ].byte = dictionary[ ptr ].byte; } else { int ptr = code; while ( dictionary[ ptr ].prev != -1 ) { ptr = dictionary[ ptr ].prev; } dictionary[ dictionary_ind ].byte = dictionary[ ptr ].byte; } dictionary[ dictionary_ind ].prev = prev; dictionary[ dictionary_ind ].len = dictionary[ prev ].len + 1; dictionary_ind++; // GIF89a mandates that this stops at 12 bits if ( ( dictionary_ind == ( 1

我不想詳細討論這是如何工作的，但是等等，解壓縮的調用方如何知道解壓縮程序應該讀取多少位？GIF實際上要求圖像描述符的數據區域的第一個位元組(在數據子塊本身之前)是一個位元組，指示第一個代碼的長度。

unsigned char lzw_code_size;... if ( read( gif_file, &lzw_code_size, 1 )

通過定義解壓縮，並且已知起始代碼長度，圖像描述符處理器現在可以對索引數據進行解壓縮。

int uncompressed_data_length = 0; unsigned char *uncompressed_data = NULL;... compressed_data_length = read_sub_blocks( gif_file, &compressed_data ); uncompressed_data_length = image_descriptor.image_width * image_descriptor.image_height; uncompressed_data = malloc( uncompressed_data_length ); uncompress( lzw_code_size, compressed_data, compressed_data_length, uncompressed_data ); disposition = 1;...done: if ( compressed_data ) free( compressed_data ); if ( uncompressed_data ) free( uncompressed_data ); return disposition;}

就是這樣，顯示圖像現在是一個索引的顏色表和反交錯的數據行(如有必要的話)。所以，你可能會理所當然的想知道，為什麼有一個以上的塊類型定義時，圖像描述符塊類型包含整個圖像。GIF"87標準認識到該規範可能需要再擴展，因此包含了一個特殊的塊類型0x21以允許擴展。擴展塊首先包括一個指示其描述的擴展類型的位元組，下一個位元組指示擴展的長度——通過將擴展的長度作為擴展的標準部分，不能識別擴展的解碼器可以跳過擴展，但仍然會正確的處理文件。當然，擴展的剩餘位元組是特定於擴展的類型的。所有擴展後面都有數據子塊，其格式與圖像數據本身中的數據塊完全相同——如果擴展沒有任何關聯數據，則後跟單個0位元組的數據子塊。

GIF"87沒有定義任何擴展，但GIF"89編寫了四個擴展：純文本、注釋、特定於應用程序和圖形控制項擴展。

·注釋擴展：這種擴展很少使用，它允許將可變長度的文本作為只讀注釋包含在GIF流中，這個注釋不會顯示在屏幕上，也沒有明確說明用戶如何能查看到它。

·文本擴展：與注釋擴展一樣，該擴展允許在GIF中包含文本數據。但是，與注釋擴展不同的是，此文本數據應該被覆蓋在此圖像的頂部，並作為其顯示的一部分。編碼器無法指定字體數據(事實上，這個擴展只允許固定寬度的字體，不允許可變寬度的字體)，這也是非常罕見的。

·特定於應用程序：此擴展允許將任意數據填充到GIF中，它由標識應用程序的8個位元組和表示版本的3個位元組組成。顯然，子塊中後面的數據依賴於應用程序ID。

·最後也是最複雜的一個擴展類型是圖形控制擴展（graphic control extension）。請記住，我提到沒有人使用GIF的多塊功能來對圖像文件進行超壓縮——相反，這用於創建動畫圖像文件。雖然GIF87a規範聲明，當遇到多個圖像塊時，「圖像之間沒有暫停，每個圖像都被處理器立即處理」，大多數GIF解碼器用延遲覆蓋圖像以創造動畫的幻覺。由於當時的軟體開始時相當慢，我懷疑這種動畫能力更像是意外，但它變得非常普遍，以至於現在有相當多的人相信GIF就是動畫GIF。

問題是，沒有標準的方法來表明這些動畫的幀之間應該經過多長時間 。GIF89接受了這一點並將其與圖形控制項擴展編碼。這種擴展很常見，不僅僅是動畫GIF，而且你會一直遇到這些。圖形控制項擴展以位元組位元組開頭：

r r x x x y z

r：保留，設置為0。

x：處理方法。這表示解碼器在單獨幀的顯示之間應該做什麼、是否應該空出顯示區域。

y：用戶輸入標誌。如果未設置，GIF動畫應自動顯示；否則，預期用戶將在動畫幀之間單擊。

z：透明度，如果是真，那麼擴展的最後一個位元組是透明索引。

標誌位元組之後是幀之間的2位元組延遲時間（以百分之一秒為單位）和單位元組透明度索引，記住不能覆蓋此索引，因為我們要使得底層框架可以「顯示」。

要處理這些擴展類型，請添加新的塊類型，如下述清單10所示：

#define EXTENSION_INTRODUCER 0x21#define IMAGE_DESCRIPTOR 0x2C...static void process_gif_stream( int gif_file ){ ... switch ( block_type ) { case EXTENSION_INTRODUCER: if ( !process_extension( gif_file ) ) { return; } break; case IMAGE_DESCRIPTOR:

然後處理擴展自身，如下述清單11所示：

#define EXTENSION_INTRODUCER 0x21#define IMAGE_DESCRIPTOR 0x2C#define TRAILER 0x3B#define GRAPHIC_CONTROL 0xF9#define APPLICATION_EXTENSION 0xFF#define COMMENT_EXTENSION 0xFE#define PLAINTEXT_EXTENSION 0x01typedef struct{ unsigned char extension_code; unsigned char block_size;}extension_t;typedef struct{ unsigned char fields; unsigned short delay_time; unsigned char transparent_color_index;}graphic_control_extension_t;typedef struct{ unsigned char application_id[ 8 ]; unsigned char version[ 3 ];}application_extension_t;typedef struct{ unsigned short left; unsigned short top; unsigned short width; unsigned short height; unsigned char cell_width; unsigned char cell_height; unsigned char foreground_color; unsigned char background_color;}plaintext_extension_t;static int process_extension( int gif_file ){ extension_t extension; graphic_control_extension_t gce; application_extension_t application; plaintext_extension_t plaintext; unsigned char *extension_data = NULL; int extension_data_length; if ( read( gif_file, &extension, 2 )

當然，在這種情況下，我所做的只是解析數據，我不是在解釋它或用它做任何事情。請注意，在這種情況下，我正在硬編碼每個擴展結構的長度——嚴格來說，這是不必要的，因為長度由擴展標頭本身中的一個位元組指示。我也終止了一個無法識別的擴展，違反了規範，其實我應該跳過它們的。下一步是將索引擴展為實際圖像並顯示它，同時遵守透明度和動畫規範，我會把它留給真正的GIF解碼器。到現在為止，你應該已經非常了解GIF圖像格式的來龍去脈了。

參考文獻：

1.特里韋爾奇「高性能數據壓縮技術」，IEEE計算機，1984年6月。

2.GIF"89規範。

本文的源代碼：

http://commandlinefanatic.com/gif.c

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！