LZWを使わずにGIFファイルを作ろう！

　ホームページにパレットインデックス画像(いわゆる256色画像)を貼りつける ときには、しばしばGIFという形式が使われます。 この、GIFという形式はLZWという圧縮法を利用しており、 それなりの圧縮率が得られます。 しかし、このLZWという圧縮法はアメリカでUNISYS社により1985年に、 「High Speed Data Compression and Decompression」として特許になっています。 また、日本においても平5-68893により同様の特許が成立しています。 したがって、LZWを利用したソフトウェアを開発する場合には、フリーソフトで あってもライセンスを取得しなければなりません。 そこで、ここではgd1.3で使われている、LZWを使わずにRun Length Encodingで GIFファイルを保存する方法の一部を解説します。

　GIFではデータ列テーブルへのインデックスをファイルに保存します。 256色GIF、つまり8bitのデータを保存するときには、このテーブルは 8bitで表現できる0〜255、256(クリアコード)、257(EOFコード) と、動的に生成されるデータ列である258以降から構成されます。 このテーブルはGIFでは最大12bit(4096エントリ)です。 テーブルが一杯になってもそのまま使えますが、クリアコードを出力すれば テーブルは初期状態に戻ります。 この辞書はデータを１つ出力するごとに１つエントリが増加します。

　GIFのLZWの動的なデータ列テーブル生成アルゴリズムについての詳細は知りませんが、 Run Length Encodingを利用してGIF互換のデータを作るためには、 まず、ラン長を数えます。例えば、10というパレットが 8ドット連続しているのであればラン長n=8となります。 次に、最初の１つはデータそのものを出力します。つまり、10を出力します。 そして、テーブルの最大ラン長m=2とします。 このとき、１ドット出力したのでn=7となります。 その後、n>=mであれば、GIFテーブルの最大値を出力し、 nの値をm減らしmを１増やします。 n<mとなったら、n=0なら出力終了、n=1ならデータそのものを出力して終了です。 また、n>=2のときは (GIFテーブルの最大値 - ( m - n ) )を出力すれば終了となります。

　基本的に、ラン長が最低3以上でなければ圧縮効果はありません。 ただし、ラン長が2でも前のテーブルを再利用すれば圧縮効果はあります。 gd 1.3ではクリア直後のテーブルを再利用するように工夫しています。

　また、この方法ではテーブルが大きくなっても出力ビット数が増えてしまうだけです から、GIFテーブルの最大値が511以上となったら速やかにクリアコードを出力し、 257に戻してやる必要があります。

　実際のソースコードですが、エンコードはクリアするかどうかのコスト計算などが あって複雑になってしまうので、デコードのメイン部分をのせておきます。

static tINT GIFDecodeRLE( GIFLOAD* pgl )
{
    tUINT   cPrev = 0;
    tUINT   cCur;
    tUINT   cRun = 0;
    tUINT   cBase;
    tUINT   n;
    tUINT   cRLTablePixel = 0;
    tUINT   cRLTableMax = 0;
    tUINT   nRLTableMode = 0;

    while ( 1 )
    {
        cCur = GIFInput( pgl );
        if ( cCur >= pgl->cCodeMax )
            return 1;
        if ( cCur > pgl->cEOF )
        {
            /* RLE */
            cRun = 0;
            cBase = pgl->cCodeMax - 1;
            while ( cCur == ( pgl->cCodeMax - 1 ) )
            {
                cRun += cCur - cBase + 2;
                if ( nRLTableMode == 1 )
                    cRLTableMax++;
                cCur = GIFInput( pgl );
            }

            if ( cCur >= cBase && cCur < pgl->cCodeMax )
            {
                cRun += cCur - cBase + 2;
                if ( nRLTableMode == 1 )
                    cRLTableMax++;
                cCur = GIFInput( pgl );
            }
            else
            if ( nRLTableMode == 1 && cCur == cPrev )
            {
                cRLTableMax++;
            }

            nRLTableMode++;

            for ( n = 0; n < cRun; n++ )
            {
                if ( GIFPutPixel( pgl, (tBYTE)cPrev ) )
                    return 0;
            }

            /* RLE with Table */
            if ( cCur > pgl->cEOF )
            {
                cRun = 0;
                cBase = pgl->cEOF + 1;
                while ( cCur >= cBase && cCur <= cBase + cRLTableMax - 2 )
                {
                    cRun += cCur - cBase + 2;
                    cCur = GIFInput( pgl );
                }

                for ( n = 0; n < cRun; n++ )
                {
                    if ( GIFPutPixel( pgl, (tBYTE)cRLTablePixel ) )
                        return 0;
                }
            }

            if ( cCur >= pgl->cCodeMax )
                return 1;
            if ( cCur > pgl->cEOF )
                return -1;
        }

        if ( cCur == pgl->cClear )
        {
            pgl->cFinal         = pgl->cInitFinal;
            pgl->cInBitsCur     = pgl->cInBitsInit;
            pgl->cCodeMax       = pgl->cEOF;
            nRLTableMode = 0;
            cRLTableMax = 0;
        }
        else
        if ( cCur == pgl->cEOF )
        {
            return 1;
        }
        else
        {
            if ( GIFPutPixel( pgl, (tBYTE)cCur ) )
                return 0;
            cPrev = cCur;
            if ( nRLTableMode++ == 0 )
            {
                cRLTablePixel = cCur;
                cRLTableMax = 1;
            }
        }
    }
}