detail

学期末プロジェクト
Grid Challenge in SACSIS 2005

全体の問題詳細は下記のHPを参照してください。

　リンク： Grid Challenge in SACSIS 2005

復号・解凍部分

復号化

画像ファイルは簡易暗号化されており、出題APIから得られる復号化鍵によって復号する必要がある。
画像ファイル中の各byteと復号化鍵中の各byteを順にXOR演算することにより復号が行なわれる。
復号化鍵のbyte列はcyclicに用いられる。 

つまり、以下のようになる。
暗号化画像ファイルのbyte列をC、復号後のbyte 列をPとする。
復号化鍵のbyte列をKとし、その長さがL bytesであるとすると、
P[i] = C[i]^K[i % L]となる。(ただし、^はXOR演算、%は剰余演算とする) 

画像データ

復号化後の画像ファイルは、4bytesのヘッダ部とそれに続くデータ部からなる。
ヘッダ部は以下のような構造である。 

0--1byte  画像の幅(ピクセル)  
2--3byte  画像の高さ(ピクセル)  

幅と高さはそれぞれ16bitsの整数で表されている。
バイトオーダーはリトルエンディアン(低位バイトが下位8bits) である。
本課題においてはそれぞれの画像ファイルは正方形であるため、幅と高さは同じ値である。 

データ部は、画像を表す2次元のビット配列を、Morton順序(Z順序と呼ばれることもあるが、以下ではMorton順序)
と呼ばれる順番で1列に並べ、それを run-length方式で圧縮したものである。 


run-length圧縮

run-length圧縮とは、1次元のデータ列(今の我々の議論ではデータは0 または1のみなので、以下ビット列として説明をする)中、
同じデータが連続して現れる部分を、データとその長さ(runと呼ぶ)で符合化する圧縮法である。 
具体的には、画像ファイル中のデータ部は以下のような構造をしたrunの列である。
1つのrunは1byteまたは2bytesで、それらは最上位ビットにより区別される。
以下の表において、bit7は最上位ビット(MSB)、bit0は最下位ビット(LSB) を表す。

1 bit run

0 byte目

7
6
5
4
3
2
1
0


0
data
lenm1



dataで表される色が、(lenm1+1)ピクセル連続して現われることを意味する。 

2 bit run


0 byte目
1 byte目


7
6
5
4
3
2
1
0
7
6
5
4
3
2
1
0


1
data
lenm1H
lenm1L



dataで表される色が、(lenm1H*256+lenm1L+1)ピクセル連続して現われることを意味する。 

以上をまとめると、ファイルに格納された生バイト列から、画像を表す2次元配列を以下のようにして復元することができる。
(1)ファイルの各バイトを暗号キーを使って復号化する。
(2)復号化されたバイト列のデータ部を run-length圧縮が施されたデータと見なして解凍されたビット列を得る。
(3)解凍されたビット列が、2次元画像をMorton順序で並べた物であると見なして、 2次元の画像を復元する。

0 byte目
7	6	5	4	3	2	1	0
0	data	lenm1

API部分

int get_problem(const int problem_number, const char* config_dir, const char**　key_string, int* width, int* height); 

プログラムは開始時にget_problem()を呼ぶことにより、データ復号化鍵などを取得する必要がある。
全ノードを通して一つのプロセスのみがget_problem()を呼ぶこと。

problem_number: 問題番号を指定する。 
config_dir: 
　お試しパックにおいては、正答ファイル (例えば01.ansという名前のファイル)の置いてある
　ディレクトリ (例えば/some/where/data01)を指定する。
　予選・決勝においてはNULLとすること。
key_string:
　鍵文字列が返されるアドレスである。
　鍵文字列は、データ復号化鍵を含む、0で終る文字列である(詳細は後述)。
　鍵文字列は出題API内部でstaticに確保されているので、freeしないこと。
width: 元画像の、X方向の分割数が返されるアドレスである。
height: 元画像の、Y方向の分割数が返されるアドレスである。

return value: 正常の場合は0、異常の場合は0以外が返される。

鍵文字列は"XXXX-YYYYYY"という形式の文字列である。
`-'(ハイフン) 以前のXXXXという部分は、16進ASCII表現による復号化鍵である。
復号化鍵の長さは固定ではないため、`-'の位置によって判断すること。
また、復号化鍵の長さをL bytesとすると、Lは4以上256以下で4の倍数であることが保証される。
復号化鍵の各byteは左にゼロ詰めされた2桁16進で表される。
そのため、 XXXXの部分の長さは2*L文字である。
プログラムはYYYYYYの部分について気にする必要はないが、文字列全体をそのままget_problem_files()とanswer_problem()に渡す必要がある。 


int get_problem_files(const int problem_number, const char* key_string, const char* problem_dir, const char** problem_file_list);

計算に参加する全プロセスは、get_problem_files()を呼ぶことにより入力ファイル名を取得する必要がある。
get_problem()から得られた鍵文字列が必要なので、前もって通信などを行なっておくこと。

problem_number: 問題番号を指定する。 
key_string: get_problem()から得られた、鍵文字列を指定する。
problem_dir:
　お試しパックにおいては、問題ファイルの置いてあるディレクトリ (例ば/some/where/data01)を指定する。
　予選・決勝においてはNULLとすること。
problem_file_list:
　呼び出したノードにおいてアクセス可能な全画像ファイル(マスター、レプリカすべて)
　のフルパス名を連結した文字列が返されるアドレスである。
　各ファイル名の直後には全て : (コロン)が置かれている。

return value: 正常の場合は0、異常の場合は0以外が返される。 

このAPIを呼び出したマシンによって、problem_file_listに返されるファイルの集合は一般には異なっている。
具体的には、マシンA, Bでの呼出しで返される二つの集合は、
　(1) 全く同一であるか、
　(2) それらのファイル集合中に含まれるマスターファイルに全く重なりがない
のどちらかが満たされている。 
実際には、二つのマシンが同一クラスタ内のマシンである場合、それらは同一の共有ディレクトリ(ファイルサーバ)をアクセスしており、
この場合は(1)になり、そうでない場合は(2) になる。
プログラム作成にあたっては、この事実を用いても良いし用いなくても良い。

戻る