C言語／C++/lzwdec - Sample is best!

開発環境	Microsoft Visual C++ 2010 Express (SP1)
実行環境	Microsoft Windows XP Home Edition (SP3)
プロジェクトの種類	Win32 コンソール アプリケーション
プロジェクト名	lzwdec
アプリケーションの種類	コンソール アプリケーション
追加のオプション	空のプロジェクト

LZWの勉強用で制限事項、改良の余地多々あり。

参考

GIFフォーマットの詳細 http://www.tohoho-web.com/wwwgif.htm

時雨エノキオプト-アセンブリホール2nd-自作ソフト-GIFデコーダ http://www.geocities.jp/warotarock/asen2ndgif001.html

辞書テーブルを利用しない新ＬＺＷ法 http://homepage1.nifty.com/uchi/lzw.htm

GIF89a Specification http://www.w3.org/Graphics/GIF/spec-gif89a.txt

LZW and GIF explained http://www.martinreddy.net/gfx/2d/GIF-comp.txt

lzwdec.c

#include <stdio.h>
#include <stdlib.h>
 
// 型定義
typedef unsigned char	UCHAR;
typedef unsigned int	UINT;
 
// 関数プロトタイプ宣言
int LZWDecode(void);
int FetchCodeData(int iCodeSize);
int AddImageData(int iCode);
int AddDicTable(void);
int PrintImageData(void);
 
// グローバル変数
static UCHAR*	g_pucImageData;		// 画像データ
static int	g_iImageData;		// 画像データのサイズ
static int	g_iImageIndex;		// 画像データの指標
static int	g_aiDicTable[0x1000];	// 辞書テーブル
static int	g_iDicIndex;		// 辞書テーブルの指標
static UCHAR*	g_pucCodeData;		// コード化データ
static int	g_iCodeData;		// コード化データのサイズ
static int	g_iCodeIndex;		// コード化データの指標
static UCHAR	g_ucLZWMinimumCodeSize;	// 最小コードビット数
static int	g_iClearCode;		// クリアコード
static int	g_iEoICode;		// 終了コード
static int	g_iCodeSize;		// コードのビット数
 
int main()
{
	UCHAR	aucImageData[256 * 256];
	UCHAR	aucCodeData[] = {
//0x00, 0x01, 0x04, 0x04		// 0
//0x00, 0x01, 0x08, 0x04, 0x10, 0x10	// 0 0 0 0
0x00, 0x03, 0xFC, 0x13, 0x48, 0xF0, 0x5F, 0x40	// 1 255 1 255 1 255 1 255
	};
 
	g_ucLZWMinimumCodeSize = 8;
	g_iClearCode	= 1 << g_ucLZWMinimumCodeSize;
	g_iEoICode	= g_iClearCode + 1;
	g_iCodeSize	= g_ucLZWMinimumCodeSize + 1;
 
	g_pucImageData	= aucImageData;
	g_iImageData	= _countof(aucImageData);
	g_iImageIndex	= 0;
	FetchCodeData(0);
 
	g_pucCodeData	= aucCodeData;
	g_iCodeData	= _countof(aucCodeData);
	g_iCodeIndex	= 0;
	LZWDecode();
 
	PrintImageData();
	return 0;
}
 
int LZWDecode(void)
{
	int	iCode;
 
	while (1) {
		iCode = FetchCodeData(g_iCodeSize);
		printf("%d\n", iCode);
		if (iCode < 0) {
			return 1;
		}
		if (iCode == g_iClearCode) {
			// 辞書テーブルのクリア
			g_iDicIndex = g_iClearCode + 1;
			g_aiDicTable[g_iDicIndex] = g_iImageIndex;
			g_iCodeSize = g_ucLZWMinimumCodeSize + 1;
			continue;
		}
		if (iCode == g_iEoICode) {
			break;
		}
		if (g_iDicIndex < iCode) {
			fprintf(stderr, "error: StringTable %u %d\n",
				g_iDicIndex, iCode);
			return -1;
		}
		AddImageData(iCode);
		AddDicTable();
		if ((1 << g_iCodeSize) <= g_iDicIndex) {
			g_iCodeSize++;
		}
	}
	return 0;
}
 
// コードの取得
// 戻り値：-1=失敗 0以上=コード
int FetchCodeData(int iCodeSize)
{
	static UINT	uiBits;
	static int	iBits;
	int		iCode;
 
	if (iCodeSize <= 0) {
		uiBits	= 0;
		iBits	= 0;
		return -1;
	}
	while (iBits < iCodeSize) {
		if (g_iCodeData <= g_iCodeIndex) {
			return -1;
		}
		uiBits |= g_pucCodeData[g_iCodeIndex++] << iBits;
		iBits += 8;
	}
	iCode = uiBits & ((1 << iCodeSize) - 1);
	uiBits >>= iCodeSize;
	iBits -= iCodeSize;
	return iCode;
}
 
// 文字データの追加
int AddImageData(int iCode)
{
	int	iEnd;
	int	i;
 
	if (iCode < g_iClearCode) {
		if (g_iImageData <= g_iImageIndex) {
			return -1;
		}
		g_pucImageData[g_iImageIndex++] = iCode;
		return 0;
	}
	iEnd = g_aiDicTable[iCode];
	for (i = g_aiDicTable[iCode - 1]; i <= iEnd; i++) {
		if (g_iImageData <= g_iImageIndex) {
			return -1;
		}
		g_pucImageData[g_iImageIndex++] = g_pucImageData[i];
	}
	return 0;
}
 
// 辞書テーブルの追加
int AddDicTable(void)
{
	if (_countof(g_aiDicTable) <= ++g_iDicIndex) {
		return -1;
	}
	g_aiDicTable[g_iDicIndex] = g_iImageIndex;
	return 0;
}
 
// 文字データの出力
int PrintImageData(void)
{
	int	i;
 
	for (i = 0; i < g_iImageIndex; i++) {
		printf("%d:%u\n", i, g_pucImageData[i]);
	}
	return 0;
}
 

出力

256
1
255
258
260
255
257
0:1
1:255
2:1
3:255
4:1
5:255
6:1
7:255