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

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

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

lzwenc.c

#include <stdio.h>	// printf
#include <stdlib.h>	// _countof
#include <string.h>	// memcmp
 
// 型定義
typedef unsigned char	UCHAR;
typedef unsigned short	USHORT;
 
typedef struct {
	USHORT	usCode;
	UCHAR	ucCodeSize;
} SCode;
 
// グローバル変数
static UCHAR		g_aucCharStream[] = {	// 文字データ（コード化対象）
//1, 255, 1, 255, 1, 255, 1, 255, 
0, 0, 0, 0, 0, 0, 0, 0, 
};
static int	g_aiStringTable[0x1000];	// 辞書テーブル
static int	g_iStringIndex;			// 辞書の指標
static int	g_iStringStart;			// 辞書の先頭
static SCode	g_aCodeStream[1024];		// コード化されたデータ
static int	g_iCodeIndex = 0;		// コード化されたデータの指標
 
// 関数プロトタイプ宣言
int ClearStringTable(int iCurrentIndex);
int SearchStringTable(int iCurrentIndex, int iCharIndex);
int AddStringTable(int iCharIndex);
int AddCodeStream(int iCode, int iCodeSize);
int PrintCodeStream(void);
int PrintCodeBitStream(void);
int PrintBitStream(int iCode, int iCodeSize);
void PrintByte(UCHAR ucByte);
 
int main()
{
	int	iCharIndex;		// 文字の指標
	int	iCurrentIndex;		// 現在の文字列の指標
	int	iCurrentCode;		// 現在の文字列のコード
	int	iStringCode;		// 辞書のコード
	int	iLZWMinimumCodeSize = 8;// 最小コードビット数
	int	iClearCode;		// クリアコード
	int	iCodeSize;		// コードのビット数
	int	iCodeNext;		// コードのビット数拡大値
 
	// クリアコードの設定など
	iClearCode = 1 << iLZWMinimumCodeSize;
	if (iLZWMinimumCodeSize < 2) {
		iLZWMinimumCodeSize = 2;
	}
	g_iStringStart = iClearCode + 2;
 
	// 現在の文字列に最初の文字をセットする
	iCurrentIndex = 0;
	iCurrentCode = g_aucCharStream[iCurrentIndex];
 
	// 辞書テーブルのクリア
	ClearStringTable(iCurrentIndex);
	iCodeSize = iLZWMinimumCodeSize + 1;
	AddCodeStream(iClearCode, iCodeSize);	// Clear code
	iCodeNext = 1 << iCodeSize;
 
	for (iCharIndex = 1; iCharIndex < _countof(g_aucCharStream); iCharIndex++) {
		// 文字の指標を1つ進め、現在の文字列から辞書のコードを検索する
		iStringCode = SearchStringTable(iCurrentIndex, iCharIndex);
		if (0 <= iStringCode) {
			// 辞書にあれば、現在の文字列のコードに辞書のコードを保存する
			iCurrentCode = iStringCode;
		} else {
			// 辞書になければ、現在の文字列を辞書に追加
			AddStringTable(iCharIndex);
			// 現在の文字列のコードを出力
			AddCodeStream(iCurrentCode, iCodeSize);
			// 現在の文字列を更新する
			iCurrentIndex = iCharIndex;
			iCurrentCode = g_aucCharStream[iCurrentIndex];
			// コードのビット数拡大チェック
			if (iCodeNext <= g_iStringIndex) {
				iCodeSize++;
				if (12 < iCodeSize) {
					// 辞書テーブルのクリア
					ClearStringTable(iCurrentIndex);
					iCodeSize = iLZWMinimumCodeSize + 1;
					AddCodeStream(iClearCode, iCodeSize);
				}
				iCodeNext = 1 << iCodeSize;
			}
		}
	}
	// 現在の文字列のコードを出力
	AddCodeStream(iCurrentCode, iCodeSize);
	AddCodeStream(iClearCode + 1, iCodeSize);	// End of Information code
	PrintCodeStream();
	PrintCodeBitStream();
	return 0;
}
 
// 辞書テーブルのクリア
int ClearStringTable(int iCurrentIndex)
{
	g_iStringIndex = g_iStringStart;
	g_aiStringTable[g_iStringStart - 1] = iCurrentIndex;
	return 0;
}
 
// 辞書テーブルの検索
// 戻り値：-1=辞書にない　0以上=辞書のコード
int SearchStringTable(int iCurrentIndex, int iCharIndex)
{
	UCHAR*	pucCurrent;	// 現在の文字列のポインタ
	int	iCurrentLen;	// 現在の文字列の長さ
	int	iPrevIndex;	// 前の指標
	int	iNowIndex;	// 今の指標
	int	iStringLen;	// 辞書の文字列の長さ
	int	i;
 
	// 指標が同じなら、そこにある文字を辞書のコードとする
	if (iCurrentIndex == iCharIndex) {
		return g_aucCharStream[iCurrentIndex];
	}
	iCurrentLen = iCharIndex - iCurrentIndex + 1;
	pucCurrent = g_aucCharStream + iCurrentIndex;
	iPrevIndex = g_aiStringTable[g_iStringStart - 1];
	for (i = g_iStringStart; i < g_iStringIndex; i++) {
		iNowIndex = g_aiStringTable[i];
		iStringLen = iNowIndex - iPrevIndex + 1;
		if (iStringLen == iCurrentLen &&
		    memcmp(pucCurrent, g_aucCharStream + iPrevIndex, iCurrentLen) == 0) {
			return i;
		}
		iPrevIndex = iNowIndex;
	}
	return -1;
}
 
// 辞書テーブルの追加
int AddStringTable(int iCharIndex)
{
	if (_countof(g_aiStringTable) <= g_iStringIndex) {
		return -1;
	}
	g_aiStringTable[g_iStringIndex] = iCharIndex;
	g_iStringIndex++;
	return 0;
}
 
// コード化されたデータの追加
int AddCodeStream(int iCode, int iCodeSize)
{
	if (_countof(g_aCodeStream) <= g_iCodeIndex) {
		return -1;
	}
	g_aCodeStream[g_iCodeIndex].usCode = iCode;
	g_aCodeStream[g_iCodeIndex].ucCodeSize = iCodeSize;
	g_iCodeIndex++;
	return 0;
}
 
// コード化されたデータの出力
int PrintCodeStream(void)
{
	int	i;
 
	for (i = 0; i < g_iCodeIndex; i++) {
		printf("%d:%u %u\n", i, g_aCodeStream[i].usCode, g_aCodeStream[i].ucCodeSize);
	}
	return 0;
}
 
// コード化されたデータをビットストリーム出力する
int PrintCodeBitStream(void)
{
	int	i;
 
	for (i = 0; i < g_iCodeIndex; i++) {
		PrintBitStream(g_aCodeStream[i].usCode, g_aCodeStream[i].ucCodeSize);
	}
	PrintBitStream(-1, 0);
	return 0;
}
 
// ビットストリーム出力
int PrintBitStream(int iCode, int iCodeSize)
{
	static UCHAR	ucBits = 0;
	static int	iBits = 0;
 
	if (iCode < 0) {
		PrintByte(ucBits);
		return 0;
	}
	ucBits = (iCode << iBits) | ucBits;
	iBits += iCodeSize;
	while (8 <= iBits) {
		PrintByte(ucBits);
		iBits -= 8;
		ucBits = (iCode >> (iCodeSize - iBits));
	}
	return 0;
}
 
// バイト出力
void PrintByte(UCHAR ucByte)
{
	char	acBuf[16];
 
	_itoa_s(0x100 | ucByte, acBuf, _countof(acBuf), 2);
	printf("0x%02X:%.4s %.4s\n", ucByte, acBuf + 1, acBuf + 5);
}
 

出力

0:256 9
1:0 9
2:258 9
3:259 9
4:258 9
5:257 9
0x00:0000 0000
0x01:0000 0001
0x08:0000 1000
0x1C:0001 1100
0x28:0010 1000
0x30:0011 0000
0x20:0010 0000