JPEGハフマン・テーブル – 解読実践(8)

さあ大分進みましたね。まあ自分で思っているだけで、分かっている方々から見れば、「なあにやってるの? 未だそんなレベルなの?」でしょうが、いいんだ いいんだ
ここまでのことを纏めましょう。何しろもう一つ配列が必要だと分かりました。この配列もバイト配列で良いでしょう。その個数はハフマン符号語の個数ですから これは動的に確保せねばならない、ということになります。何故ならばハフマン符号語の数は、それぞれのハフマン・テーブルが変化するからです。あるいは大きめの配列を確保してメモリーを無駄遣いしても良いのですが、なんかなあ スマートじゃないなあ 僕の美学に反するなあ
という訳で、BITS[]も動的に確保することにします。これなんかは何時でも16個と決まっているので、それも変な話しですが・・・
という訳で、まずはこれらの作業領域の確保部分です

typedef unsigned char u_char; // これ以降長いので
               // u_charという型を定義した
u_char * BITS = new u_char[16]; // バイト配列16個確保

for (int i=0; i<16; i++) { // データをセット
  BITS[i] = 0x00;
}
BITS[1] = 0x01; BITS[2] = 0x05; BITS[3] = 0x01;
BITS[4] = 0x01; BITS[5] = 0x01; BITS[6] = 0x01; 
BITS[7] = 0x01; BITS[8] = 0x01;

int sum=0;
for (int i=0; i<16; i++) {
  sum += BITS[i]; // これでハフマン符号語の総数を求める
}

u_char * HUFFBITS = new u_char[sum];
         // これでハフマン符号語長を保持する
         // HUFFBITS配列が動的に確保された
int * HUFFCODE = new int[sum];
         // ついでにハフマン符号語を入れる
         // 配列HUFFCODEも動的に確保する

さあこれで良いかな?
何しろ C++使うの2年ぶりなので、すっかり文法を忘れています。まあ、コンパイルすれば誤りは分かるのでまたその時点で修正しましょう。

JPEGハフマン・テーブル – 解読実践(7)

さて実際にコードをコンパイルする前に ハンド・デバッグをしてみます。
まず、外側の走査の最初 つまり i=0の時を見てみます。
さて先ほど確保したBITS[]配列からどのようにしてハフマン符号を導けば良いでしょうか? さっき書いたアルゴリズムをそのままプログラムにすれば良い筈です

int code = 0;  // ハフマン符号初期値は0である
for (int i=0; i<16; i++) { // これでBitS[]配列全体を走査する
  for (int j=0; j<BITS[i]; j++) { 
    code+=1;  // BITS[i]の値だけハフマン符号に1 bit足す
    std::cout << code << std::endl;  // できたハフマン符号を出力する
  }
  code <<= 1;  // 次のビット数のハフマン符号のために、左に1 bitシフトする
}

これでどうでしょうか?
そんなに簡単に行く訳ありませんよね、デバッグするのも大変です。
ですから、内側のループつまり、jをカウンターとするループですが、BITS[i]は0x00でしたので、このループは回りません。従って、code+=1の命令は走りませんので、codeは0のままです。
そして、内側のループを出て、外側のループに入りますので、ここではcodeは 1 bit左シフトしますので、0x00となります。しかし問題は、このハフマン符号が 2 bitsのものだ、ということをどこかに記録せねばなりませんね。そうでないと、integer型の0x00は何ビットzeroが並んでいるのか誰にも分かりません。
そういうことで、このハンド・デバッグで、もう一つ何ビット長のハフマン符号であるかを記録する配列が必要、ということが分かりました。これは重要な進歩です。

JPEGハフマン・テーブル – 解読実践(6)

さて先ほど確保したBITS[]配列からどのようにしてハフマン符号を導けば良いでしょうか? さっき書いたアルゴリズムをそのままプログラムにすれば良い筈です

int code = 0;  // ハフマン符号初期値は0である
for (int i=0; i<16; i++) { // これでBitS[]配列全体を走査する
  for (int j=0; j<BITS[i]; j++) { 
    code+=1;  // BITS[i]の値だけハフマン符号に1 bit足す
    std::cout << code << std::endl;  // できたハフマン符号を出力する
  }
  code <<= 1;  // 次のビット数のハフマン符号のために、左に1 bitシフトする
}

これでどうでしょうか?
そんなに簡単に行く訳ありませんよね、デバッグするのも大変です。

JPEGハフマン・テーブル – 解読実践(5)

それでは前回のアルゴリズムをC++で書きましょう

まずは、何ビットのハフマン符号がいくつあるのか? つまり、例の青い部分の16 bytesを抱えるメモリーが必要ですね これを

unsigned char BITS[16];

で宣言します。そして、さっきの値を代入します

BITS[0] = 0x00; BITS[1] = 0x01; BITS[2] = 0x05; BITS[3] = 0x01;
BITS[4] = 0x01; BITS[5] = 0x01; BITS[6] = 0x01; BITS[7] = 0x01;
BITS[8] = 0x01; BITS[9] = 0x00; BITS[10] = 0x00; BITS[11] = 0x00;
BITS[12] = 0x00; BITS[13] = 0x00; BITS[14] = 0x00; BITS{15] = 0x00;

はい、これで準備整いました。
もちろん、できるだけコンピューターにやらせてしまおうとすれば、少しはプログラムらしく

for (int i=0; i<16; i++) {
  BITS[i] = 0x00;
}
BITS[1] = 0x01; BITS[2] = 0x05; BITS[3] = 0x01;
BITS[4] = 0x01; BITS[5] = 0x01; BITS[6] = 0x01; 
BITS[7] = 0x01; BITS[8] = 0x01; 

としても良いわけですが・・・

JPEGハフマン・テーブル – 解読実践(4)

さてさっきの一意瞬時復号符号であったハフマン符号はどのような規則に則って作成したでしょうか?
それは簡単な規則なのです。

  1. ハフマン符号はビット0から開始する(これは取り決めなので文句言わないでね)
  2. 次のハフマン符号は+1したものとする
  3. ビット数を増加させるハフマン符号になる時には、これまでのハフマン符号に1を足してから、これを左に1 bitシフトして、最後のビットに0を追加する これによって、ビット数が1 bit増加したハフマン符号となる

これを繰り返すのみです。

あっ、もう朝カンファランスの時間