学期末プロジェクト
Grid Challenge in SACSIS 2005
とりあえず復号・解凍の部分と、APIを用いてファイル等を取得する部分を書いてみました。
間違いやこうしたほうがいい、というようなところがあると思うので、見つけたら教えて下さい。
復号・解凍部分
関数
char* decryption(Data, DATA_SIZE, Key, KEY_SIZE, WIDTH, HEIGHT)
unsigned char *Data : 画像ファイルのデータ
int DATA_SIZE : 画像ファイルのデータサイズ
char *Key : 複合化鍵
int KEY_SIZE : 鍵のサイズ
int *WIDTH : 復号化後の画像ファイルの幅
int *HEIGHT : 復号化後の画像ファイルの高さ
@return
char *Image_Data : 解凍後の画像データ
二値画像なので１ピクセルの表示には１ビットあればいいことになるが、
ビット列の扱い方がよくわからないので、char型の配列を用いる。
もし実行中にメモリが足りなくなるなどの事態が起きたらビット列で取り扱う方法を考える。
復号化
画像ファイル中の各byteと復号化鍵中の各byteを順にXOR演算することにより復号を行う。
for(i=0; i < DATA_SIZE; i++)
Data[i] = Data[i] ^ Key[i%KEY_SIZE];
画像データ
復号化後の画像ファイルは、4bytesのヘッダ部とそれに続くデータ部からなる。
ヘッダ部は以下のような構造である。
0--1byte 画像の幅(ピクセル)
2--3byte 画像の高さ(ピクセル)
バイトオーダーはリトルエンディアン(低位バイトが下位8bits) である。
*WIDTH = Data[1]*256 + Data[0]; // little endian
*HEIGHT = Data[3]*256 + Data[2]; // little endian
（引数で渡す関係上、ポインタにしている）
今回はそれぞれの画像ファイルは正方形であるため、幅と高さは同じ値になる。
よってどちらか一方だけ求めればよいが、確認のため両方求める。
解凍
run-length圧縮で圧縮されたデータを解凍する。
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)ピクセル連続して現われる。
char data : 連続データ（0 又は 1）
int length : 連続データの個数
char *Image_Data : 解凍後の画像データ
k = 0;
for(i=4; i < DATA_SIZE; i++){
data = (Data[i] & 0x40) >> 6; // data (0 or 1)
/* get the length of straight data */
if(Data[i]>>7 == 0) // 1 byte run
length = (Data[i] & 0x3f)+1;
else{ // 2 byte run
length = (Data[i] & 0x3f)*256+Data[i+1]+1;
i++;
}
for(j=0; j < length; j++) Image_Data[k++] = data; // unpack
}
API部分
データ復号化鍵などを取得
問題１を解く場合、/home/shibuya/grid/data01を指定する。
int w, h : ファイルの分割数
const char *original_key : データ復号化鍵
if(get_problem(1, "/home/shibuya/grid/data01", &original_key, &w, &h)!=0){
perror("get_proglem");
exit(EXIT_FAILURE);
}
入力ファイル名の取得
呼び出したノードにおいてアクセス可能な全画像ファイル(マスター、レプリカすべて)
のフルパス名を連結した文字列が返されるアドレスを取得する。
また、各ファイル名の直後には全て : (コロン)が置かれている。
const char *files : 入力ファイル名
if(get_problem_files(1, original_key, "/home/shibuya/grid/data01", &files)!=0){
perror("get_proglem_files");
exit(EXIT_FAILURE);
}
ファイルに関する情報の取得
ファイルの個数は縦、横の分割数をかければ求められる。
各画像ファイルは以下のようなファイル名を持つ。
マスター: PPXXXYYY.mdt
レプリカ: PPXXXYYY.rdt
ただし、PPは問題番号(2桁)、XXXはファイルのX位置(3桁)、YYYはファイルのY位置(3桁)である。
よってファイル名は一定（8桁）であるので、これに拡張子とフルパス名を連結した文字列
の長さも一定である。したがってget_problem_filesで取得した文字列の長さは
（フルパスを連結したファイル名の長さ）×（ファイルの個数）＋（コロンの数）
となる。これによりフルパスを連結したファイル名の長さを求める。
以下の項目にも当てはまるが、配列等を作成する場合、サイズを決め打ちするのではなく、
入力に応じて動的にサイズを求めるようにしている。
int File_num : ファイルの個数
int file_name_length : ファイル名の長さ
char **File : ファイルの配列
File_num = w*h; // number of the files
/* length of the individual file name */
file_name_length = (strlen(files)+1)/File_num - 1;
/* memory allocation */
File = (char **)malloc(File_num*sizeof(char *));
for(i=0; i < File_num; i++){
File[i] = (char *)malloc((file_name_length+1)*sizeof(char));
}
個々のファイル名へ分割
ファイル名の集合を個々のファイルに分割する。
各ファイル名の直後には全て : (コロン)が置かれているので、
'：'によってファイル名を分割する。
/* parse "files" & divide into individual file */
for(i=j=k=0; files[i]!='\0'; i++){
if(files[i]==':'){
File[k][j] = '\0';
k++; j=0;
}else{
File[k][j++]=files[i];
}
}
復号化鍵の作成
get_problemで取得される鍵文字列は"XXXX-YYYYYY"という形式の文字列である。
`-'(ハイフン) 以前のXXXXという部分は、16進ASCII表現による復号化鍵である。
XXXXという部分のみが必要であるが、復号化鍵の長さは固定ではないため、
`-'の位置によって判断する。
また、復号化鍵の長さをL bytesとすると、Lは4以上256以下で4の倍数であることが保証される。
復号化鍵の各byteは左にゼロ詰めされた2桁16進で表される。そのため、XXXXの部分の長さは2*L文字である。
まずは`-'までの文字数を数えて複合化鍵の文字の長さを求める。
復号化鍵の各byteは左にゼロ詰めされた2桁16進で表されるので、復号化鍵のサイズは
復号化鍵の文字の長さの半分となる。
よって、2つの文字を連結して、それを整数に変換する。（16進→10進）
/* get the length of the key */
i=0;
while(original_key[i]!='-') i++; // skip until '-' appears
/* size of the key */
Key_size = i/2; // 1 byte = two character (ex)c9a03e -> c9 a0 3e
Key = (char *)malloc(Key_size*sizeof(char));
/* convert string to number */
for(i=0; i < Key_size; i++){
sprintf(temp, "%s%c%c", "0x", original_key[2*i], original_key[2*i+1]);
Key[i] = (char)strtol(temp, (char **)NULL, 16);
}
ファイルからデータの読み込み
ファイルからデータを読み込む。char型の配列に読み込むので、配列の長さは
ファイルのサイズに等しい。ファイルのサイズを求めるのにはlstat()関数を
用いる。ファイルから1文字ずつ読み込み、配列に格納していく。
unsigned char *Data : 画像ファイルデータ
int Data_size : 画像ファイルデータのサイズ
struct stat buf : stat構造体
FILE *fp : ファイルのストリーム
/* get the file information */
if((lstat(File[i], &buf))<0){
perror(File[i]);
exit(EXIT_FAILURE);
}
/* get the file size */
Data_size = buf.st_size;
Data = (char *)malloc(Data_size*sizeof(char));
/* file open */
if((fp=fopen(File[i], "r")) == NULL){
perror(File[i]);
exit(EXIT_FAILURE);
}
/* read the data */
for(j=0; j < Data_size; j++){
Data[j]=fgetc(fp);
}
fclose(fp);
戻る