相当悩んだぞ

DHTの読み込みをC++で書いていて どうしても分からないことにぶち当たりました。それは、以下のような簡単なものなのです たと

えば、このようなbinary fileを作成します。

0x42 0x42 0x43 0x44 0xFF 0xC4 0x45 0x46

これはテキストとして表せばASCII Code表に則って ABCD トEF とあらわされると思います。
そこでプログラムを書いたのです。おのずと知れた JPEG DHTのタグ 0xFF 0xC4の連続する 2バイトを検出するのです。

char * buf;
fp.read(buf, 8);
for (int i=0; i<8; i++) {
  if (*buf == 0xFF) {
    std::cout << "DHTタグに入るよ\n";
  }
  std::cout << *buf << " ";
  buf++;
}

当然出力は、A B C D DHTタグに入るよ・・・
となる筈です。ところがならないのです!!!
どう考えても分からないのです。これはC++では何か変数の型チェックが厳しいのかも知れない? そのように思いました。そこで調べると charと宣言するとそれはdefaultでsigned charすなわち -127~+127を保持し、unsigned charが0~255を保持できる、と書いてあります。そんなこと分かっているのですが、ひょっとして、0xFFはsigned charではまずい値なのかも知れません。そこで

typedef unsigned char u_char;
u_char *buf;

としてみました。ところが、今度は fp.read(buf, 8); の部分で、bufをchar*に変換できません、と叱られました。そこで

typedef unsigned char u_char;
u_char *buf;
fp.read(reinterpret_cast<char *>(buf), 8);

このようにすると、無事0xFFを検出でき、

A B C D DHTタグに入るよ
ト E F

とこのように出力されるようになりました。フーッ C++は型のチェックが厳しいですね。

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

さてさてファイルを読み込むことをせねばなりません。C++ではどのようにするか? これも少し調べました 標準C++を用いて書けば以下のようにするのが良いと思います

#include "stdafx.h"  // Windowsだから必要なのね
#include <iostream>
#include <fstream>

int main(const int argc, const char* argv[])
{
	if (argc !=2) {
		std::cout << "エラー::入力ファイル名を指定して下さい\n";
		char ch = 'x';
		while (ch != 'e') {
			std::cin >> ch;
		}
		return false;
	}
	std::ifstream fp(argv[1], std::ios::in|std::ios::binary);  // ファイル・オープン
	if (fp.fail()) {
		std::cout << "エラー::入力ファイルは存在しません\n";
		char ch = 'x';
		while (ch != 'e') {
			std::cin >> ch;
		}
		return false;
	}
	std::ifstream::pos_type begp, endp, fsize;
	fp.seekg(0, std::ios_base::end);  // ファイルの最後に移動
	endp = fp.tellg();  // endpにはファイルの最後の位置がセット
	fp.seekg(0, std::ios_base::beg);  // ファイルの最初に移動
	begp = fp.tellg();  // begpにはファイルの先頭位置がセットされた
	fsize = endp - begp;  // fsizeにはファイルサイズがセットされた
	char* buffer = new char[(int)fsize];  
	if (buffer == NULL) {
		std::cout << "エラー::バッファを確保できませんでした\n";
		char ch = 'x';
		while (ch != 'e') {
			std::cin >> ch;
		}
		return false;
	}
	fp.read(buffer, fsize);  // バッファにファイルから読み込み
        fp.close();
	char * const bp = buffer;
	std::ofstream fpout("Out.txt", std::ios::out|std::ios::binary);
	fpout.write(bp, fsize);  // Out.txtというファイルに書き出し
        fpout.close();
	delete[] buffer;  // バッファの解放
	return 0;
}

何ともはやめんどくさいですね。しかし、仕方無いのです。これだけのことを我々が普段ファイルを読み書きする時に行っているのです。もちろん最終的にはgraphic interfaceを実装するつもりですよ

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

数日前にあげた 実際のDHTの例

FF C4
00 19
00
01 01 01 01 01 01 00 00 00 00 00 00 00 00 00 00
01 00 02 03 04 05
これではどうでしょうか?
データをこの通りにセットしました
その出力は以下の通り

どうやらきちんと動いているようです。
いちいちデータをマニュアルでセットしてコンパイルではやってられませんので、ファイルを読み込んでDHTを検出して、ハフマン符号を導く、それが次の課題ですね まあこれはそんなに難しいことではありません

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

できた できた できたのだ
Windows7 VisutalStudio 2010でC++でテストしました

// JPEG_Analysis.cpp : programmed by S. SAITO, MD, FACC, FSCAI, FJCC
// created at 5:00AM on August 20th Monday 2012
//

#include "stdafx.h"
#include <iostream>

typedef unsigned char u_char;  // u_char型の宣言
typedef struct {
  int HuffBit;  // ハフマン符号のビット長
  int HuffCode; // ハフマン符号
  int HuffVal;  // ハフマン符号の意味する値
} HUFFTAB;   // これでHUFFTABという型を宣言した

void outbit(const int& hc, const int& hb) {
	// 16 bitsの長さ hbのハフマン符号 hcを左詰めで出力する

	int mask = 0x0001;
	for (int i=hb; i>0; i--) {
		mask <<= (i-1);
		if ((mask & hc) != 0) {
			std::cout << '1';
		} else {
			std::cout << '0';
		}
		mask = 0x0001;
	}
	std::cout << std::endl;
};

int _tmain(int argc, _TCHAR* argv[])
{
	u_char BITS[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 huffElementNo = 0;
	for (int i=0; i<16; i++) {
		huffElementNo += BITS[i]; // これでハフマン符号語の総数を求める
	}
	//
	// ハフマンテーブル領域の動的確保
	HUFFTAB *ht = new HUFFTAB[huffElementNo]; 
	// これでハフマン表の領域が確保された

	int code = 0;  // ハフマン符号初期値は0である
	int huffElement = 0;  // 配列のカウンター
	for (int i=0; i<16; i++) { // これでBitS[]配列全体を走査する
		for (int j=0; j<BITS[i]; j++) { 
			ht[huffElement].HuffBit = i+1;
			ht[huffElement].HuffCode = code;
			ht[huffElement].HuffVal = 0;  // とりあえずdummyで0を入れておく
			huffElement++;
			code+=1;  // 次のハフマン符号のために1 bit足す
		}
		code <<= 1;  // 次のビット数のハフマン符号のために、左に1 bitシフトする
	}

	for (int i=0; i<huffElementNo; i++) {
		std::cout << "Bit = " << ht[i].HuffBit << " ::: Code = " << " ";
		outbit(ht[i].HuffCode, ht[i].HuffBit);
	}

	char ch = NULL;
	while (ch != 'e') {
		std::cin >> ch;
	}
	return 0;
}

結果出力は以下の通り

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

物事には順序が必要です。気が付けば、デバグをするためねにはプログラムを書かねばならない、そのように思いました。
どういう仕様が必要か? ハフマン符号と、その長さを入力すれば、左詰めで1と0のハフマン符号が出力される、それが必要です。
艱難辛苦の末、以下のプログラムを書きました 如何にも単純、しかし作動します。ビット演算の魔術師にかかれば、もっと高速で効率の良いプログラムを書けるでしょう。そんなことわかっています。でも、まずは確実に動くものを造り、それから改良するのです。何しろ僕は、改良が得意な日本人の一人なのですから・・・

void outbit(const int& hc, const int& hb) {
	// 16 bitsの長さ hbのハフマン符号 hcを左詰めで出力する
	
	int mask = 0x01;
	for (int i=hb; i>0; i--) {
		mask <<= (i - 1);
		if ((mask & hc) != 0) {
			std::cout << 1;
		} else {
			std::cout << 0;
		}
		mask = 0x01;
	}
	std::cout << std::endl;
};

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

何か C++の言語仕様に対して根本的に間違っていたような気がします。Webにアクセスしてもう一度考え直しました。前回のプログラム・パーツを以下のように書き換えました

typedef unsigned char u_char;  // u_char型の宣言
typedef struct {
  int HuffBit;  // ハフマン符号のビット長
  int HuffCode; // ハフマン符号
  int HuffVal;  // ハフマン符号の意味する値
} HUFFTAB;   // これでHUFFTABという型を宣言した

u_char BITS[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 huffElementNo = 0;
for (int i=0; i<16; i++) {
   huffElementNo += BITS[i]; // これでハフマン符号語の総数を求める
}
//
// ハフマンテーブル領域の動的確保
HUFFTAB *ht = new HUFFTAB[huffElementNo]; 
// これでハフマン表の領域が確保された

これで良いのですよ 今度は間違いない、と確信しています

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

さあここまでで準備できたので、少しはプログラムらしくしてみます


struct HUFFDECODE {
  int numHuffElement;  // ハフマン符号語の総数
  int * HUFFBITS;   // ハフマン符号語長
  int * HUFFCODE;   // ハフマン符号
  int * HUFFVAL;    // ハフマン符号が表すデータ
}

typedef unsigned char u_char;   // 短縮形の定義

u_char BITS[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]; // これでハフマン符号語の総数を求める
}
//
// ハフマンテーブル領域の動的確保

ああダメだ 挫折 少し頭を冷やしましょう

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

大事なデータを忘れていました。最終的に対応するハフマン符号が意味するのは、その後に続く、つまり緑の部分でした この部分は、ハフマン符号語に続く何ビットがデータを表しているかを示します この部分も配列に入れる必要がありますね そこで追加です

int * HUFFVAL = new int[sum];

うん? 待てよ ということになると動的に確保する三つの配列 つまり HUFFBITS, HUFFCODE, HUFFVALは同じインデックス同志が意味を有する、ということになりますね、だとすれば、これら三つで意味を有するので構造体として一つにまとめる方が論理的に分かりやすいですよね、そこで構造体を定義します さらには、その構造体にインデックス最大値を保持する変数も含めることにしましょう またこれまではハフマン符号語長を保持する配列 HUFFBITSをバイトで確保していましたが、これは最大 16bitsあるのでintにせねばなりませんでした そこで

struct HUFFDECODE {
  int numHuffElement;  // ハフマン符号語の総数
  int * HUFFBITS;   // ハフマン符号語長
  int * HUFFCODE;   // ハフマン符号
  int * HUFFVAL;    // ハフマン符号が表すデータ
}

このような構造体を定義しました ふーっ、道は遠い

そうそう昨日は京都で夜講演があり、久しぶりに京都の町に繰り出しました。とても暑く、また一昨日は大文字送り火だったので、ものすごい混雑でした。

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が並んでいるのか誰にも分かりません。
そういうことで、このハンド・デバッグで、もう一つ何ビット長のハフマン符号であるかを記録する配列が必要、ということが分かりました。これは重要な進歩です。