/*********************************************************** * * bpe2.c * * Byte Pair Encoding ファイル符号化のテスト * ブロックのヘッダを省略できる場合省略する * ***********************************************************/ #include #include #include #include #include typedef unsigned char Uchar; typedef unsigned short Ushort; typedef unsigned int Uint; /* グローバル変数の定義 */ #define HEADER_SIZE 4 char file_header[HEADER_SIZE] = "BPE2"; char file_ext[] = ".bpe2"; char input_fname[FILENAME_MAX]; char output_fname[FILENAME_MAX]; int mode; /* 'e':encode 'd':decode */ FILE *infp, *outfp; /* 入力ファイル, 出力ファイル */ #define TRUE 1 #define FALSE 0 #define BUFMIN 128 #define BUFMAX 32511 /* 0x7eff */ int bufsize = 4096; /* データ作業領域のサイズ */ Uchar ptsize; /* ペア表の大きさ */ Uchar ptbuf[256*3]; /* 符号化用ペア表バッファ */ Uchar pairtable1[256]; /* 一時的ペア表(1番目の文字) 符号化モードでは文字が使われているかどうかの判定用 */ Uchar pairtable2[256]; /* 一時的ペア表(2番目の文字) */ Uchar srcbuf[BUFMAX + 16]; /* 元のデータのバッファ */ Uchar workbuf[BUFMAX + 16]; /* 圧縮データのバッファ */ Ushort *paircount; /* ペア出現用カウンタ(mallocで領域確保する, 符号化モードのみ使用) */ int ob_count = 0; /* *outbuf[] を使っている数 */ Uchar *outbuf[256]; /* データ出力用バッファメモリ(mallocで領域確保する, 符号化モードのみ使用) */ /* メッセージを表示し終了 */ void error(char *message) { fprintf(stderr, "%s\n", message); exit(1); } /* メモリの取得 */ void *get_memory(int size) { void *buffer = malloc(size); if (buffer == NULL) { error("Out of Memory"); } return buffer; } /*--------------------------------------------------------*/ /* 符号化処理 */ /*--------------------------------------------------------*/ /* ペア出現用カウンタを初期化 */ void paircount_init(void) { int i; for (i = 0; i < 256*256; i++) { paircount[i] = 0; } } /* srcbuf[]を符号化しworkbuf[]へ書込 */ Uint encode_buf(int size) { int i; int rpos, wpos; int srcsize = size; Uchar encch; int iflag = TRUE; memcpy(workbuf, srcbuf, size); ptsize = 0; encch = 255; while (TRUE) { Uchar c1, c2; Ushort maxcount, tcount; /* 使われていない文字encchを得る */ for (i = 0; i < 256; i++) { encch = (encch + 1) & 0xff; if (pairtable1[encch] == FALSE) break; } /* 使われていない文字が無い時終了 */ if (i == 256) break; if (iflag == TRUE) paircount_init(); /* ペア出現用カウンタを初期化 */ /* ペア出現用カウンタにカウントし、最もよく出るペア(c1,c2)を得る */ maxcount = 0; for (i = 0; i < size - 1; i++) { Uchar cn1 = workbuf[i]; Uchar cn2 = workbuf[i + 1]; tcount = ++paircount[(cn1 << 8) | cn2]; if (maxcount < tcount) { c1 = cn1; c2 = cn2; maxcount = tcount; } if (cn1 == cn2 && cn2 == workbuf[i + 2]) i++; /* 3連続同じ文字の場合 */ } /* ペア(c1,c2)の出現回数が3以下なら終了 */ if (maxcount < 4) break; /* ペア(c1,c2)をencchに置き換える 同時にペア出現用カウンタの中身を0に戻す */ paircount[(c1 << 8) | c2] = 0; rpos = wpos = 0; while (rpos < size-1) { if (workbuf[rpos] == c1 && workbuf[rpos+1] == c2) { paircount[ (workbuf[rpos+1] << 8) | workbuf[rpos+2] ] = 0; workbuf[wpos++] = encch; rpos += 2; } else { paircount[ (workbuf[rpos] << 8) | workbuf[rpos+1] ] = 0; workbuf[wpos++] = workbuf[rpos++]; } } if (rpos == size-1) { /* rposの位置が最後の1文字の場合 */ workbuf[wpos++] = workbuf[rpos]; } size = wpos; /* ペア表に設定 */ pairtable1[encch] = TRUE; ptbuf[ptsize * 3 ] = encch; ptbuf[ptsize * 3 + 1] = c1; ptbuf[ptsize * 3 + 2] = c2; ptsize++; iflag = FALSE; } /* 追加: サイズが小さくなったかを判定 */ if (ptsize > 0 && srcsize <= size + 1 + ptsize * 3 + 2) { memcpy(workbuf, srcbuf, srcsize); /* 元に戻す */ ptsize = 0; size = srcsize; } return size; } /* *outbuf[] の内容をファイルに書込 */ void flush_outbuf(void) { int i; if (ob_count == 0) return; /* ブロックヘッダ書込(ob_countの値に限らず1回のみ) */ fputc(0x7f, outfp); fputc(ob_count-1, outfp); for (i = 0; i < ob_count; i++) { fwrite(outbuf[i], 1, bufsize, outfp); } ob_count = 0; } /* データを減らせなかった時、データを *outbuf[] に貯める */ void output_data(int typ, int size) { int headcode; if (typ == 0 && bufsize == size) { if (ob_count < 256) { if (outbuf[ob_count] == NULL) { outbuf[ob_count] = (Uchar *)get_memory(bufsize); } } else { flush_outbuf(); } memcpy(outbuf[ob_count], workbuf, size); ob_count++; } else { flush_outbuf(); headcode = size + typ * 0x8000; fputc((headcode >> 8), outfp); fputc(headcode & 0xff, outfp); /* ブロックヘッダ書込 */ fwrite(workbuf, 1, size, outfp); /* 圧縮データを書込 */ } } /* 符号化 */ void encode(void) { int isize = 0; int i; /* バッファサイズの書込 */ printf("作業領域用メモリバッファ: %dByte\n", bufsize); if (bufsize < BUFMIN || BUFMAX < bufsize) error("Bad number"); fputc(bufsize >> 8, outfp); fputc(bufsize & 0xff, outfp); paircount = (Ushort *)get_memory(sizeof(Ushort) * 256*256); /* メモリ領域確保 */ while (TRUE) { int headcode, typ, destsize; int srcsize = fread(srcbuf, 1, bufsize, infp); /* ブロックサイズ分を読込 */ if (srcsize <= 0) break; /* 各文字の出現の有無をペア表に登録 */ for (i = 0; i < 256; i++) { pairtable1[i] = FALSE; } for (i = 0; i < srcsize; i++) { pairtable1[srcbuf[i]] = TRUE; } destsize = encode_buf(srcsize); /* 符号化 */ if (ptsize > 0) typ = 1; else typ = 0; output_data(typ, destsize); if (typ == 1) { /* ペア表を書込 */ fputc(ptsize, outfp); fwrite(ptbuf, 1, ptsize * 3, outfp); } /* 途中経過表示 */ isize += srcsize; printf(" %d\r", isize); } /* メモリ解放 */ free(paircount); for (i = 0; i < 256; i++) { free(outbuf[i]); } } /*--------------------------------------------------------*/ /* 復号処理 */ /*--------------------------------------------------------*/ /* workbuf[]を展開しsrcbuf[]へ書込 */ int decode_buf(int bfs, int isize) { int wpos = 0, spos = 0; Uchar stackbuf[256], stackhead = 0; /* デコード用スタック */ while (wpos < isize || stackhead > 0) { Uchar ch; if (!stackhead) { /* スタックが空の時、データから1Byte読込 */ ch = workbuf[wpos++]; } else { /* スタックから1Byte読込 */ ch = stackbuf[--stackhead]; } while (TRUE) { /* ペア表から文字を得る */ if (ch == pairtable1[ch]) { /* データをそのまま1Byte書込 */ if (spos >= bfs) error("Buffer overflow"); srcbuf[spos++] = ch; break; } /* データをスタックへ入れる */ stackbuf[stackhead++] = pairtable2[ch]; ch = pairtable1[ch]; } } return spos; } /* 復号 */ void decode(void) { int osize = 0; /* バッファサイズの読込 */ bufsize = fgetc(infp); bufsize = (bufsize << 8) | fgetc(infp); if (bufsize < BUFMIN || BUFMAX < bufsize) error("Read error"); printf("作業領域用メモリバッファ: %dByte\n", bufsize); while (TRUE) { int i, typ; int pts, ch, c2; int isize, srcsize; /* ブロックヘッダ読込 */ if (ob_count > 0) { if (fread(workbuf, 1, bufsize, infp) != (size_t)bufsize) error("Input data error 1"); fwrite(workbuf, 1, bufsize, outfp); srcsize = bufsize; ob_count--; } else { int headcode = fgetc(infp); if (headcode == EOF) break; if (headcode == 0x7f) { ob_count = fgetc(infp); headcode = bufsize; } else { headcode = (headcode << 8) | fgetc(infp); } typ = headcode >> 15; isize = headcode & 0x7fff; /* ブロックデータの読込 */ if (fread(workbuf, 1, isize, infp) != (size_t)isize) error("Input data error 1"); /* ペア表を初期化 */ for (i = 0; i < 256; i++) { pairtable1[i] = i; } if (typ) { /* ペア表の読込 */ if ((pts = fgetc(infp)) < 0) error("Input data error 2"); for (i = 0; i < pts; i++) { if ((ch = fgetc(infp)) < 0) error("Input data error 2"); if ((c2 = fgetc(infp)) < 0) error("Input data error 2"); pairtable1[ch] = c2; if ((c2 = fgetc(infp)) < 0) error("Input data error 2"); pairtable2[ch] = c2; } } srcsize = decode_buf(bufsize, isize); /* 復号処理 */ fwrite(srcbuf, 1, srcsize, outfp); } /* 途中経過表示 */ osize += srcsize; printf(" %d\r", osize); } } /*--------------------------------------------------------*/ /* ファイル入出力処理 */ /*--------------------------------------------------------*/ /* ファイルの符号化 */ void encode_file(void) { fpos_t insize, outsize; /* ファイルサイズ */ infp = fopen(input_fname, "rb"); /* 入力ファイルオープン */ if (infp == NULL) { error("入力ファイルが見つかりません"); } outfp = fopen(output_fname, "wb"); /* 出力ファイルオープン */ if (outfp == NULL) { error("出力ファイルオープンに失敗しました"); } fwrite(file_header, 1, HEADER_SIZE, outfp); /* ヘッダーの書込 */ encode(); /* 符号化 */ /* 結果表示 */ fgetpos(infp, &insize ); fgetpos(outfp, &outsize); printf("入力サイズ : %d bytes\n", insize); printf("出力サイズ : %d bytes\n", outsize); if (insize > 0) { printf("出力/入力 : %.6f\n", (double)outsize / insize); } fclose(infp); fclose(outfp); } /* ファイルの復号 */ void decode_file(void) { fpos_t outsize; /* ファイルサイズ */ int size; char header_buff[HEADER_SIZE]; infp = fopen(input_fname, "rb"); /* 入力ファイルオープン */ if (infp == NULL) { error("入力ファイルが見つかりません"); } /* ヘッダーチェック */ size = fread(header_buff, 1, HEADER_SIZE, infp); if (size != HEADER_SIZE || memcmp(file_header, header_buff, HEADER_SIZE)) { error("ファイルタイプが違います。解凍処理できません。"); } outfp = fopen(output_fname, "wb"); /* 出力ファイルオープン */ if (outfp == NULL) { error("出力ファイルオープンに失敗しました"); } decode(); /* 復号 */ /* 結果表示 */ fgetpos(outfp, &outsize); printf("出力サイズ : %d bytes\n", outsize); fclose(infp); fclose(outfp); } /* 使用方法 */ void usage(void) { printf("書式 : bpe2 [オプション] 入力ファイル名 [出力ファイル名]\n"); printf(" オプション : -d ... 解凍(デフォルト)\n"); printf(" -e ... 圧縮\n"); printf(" -bn ... バッファサイズ( n = %d 〜 %d )\n", BUFMIN, BUFMAX); printf(" (デフォルト : %d)\n", bufsize); exit(2); } /* 引数解析 */ void getargs(int argc, char *argv[]) { int i, fncount = 0; mode = 'd'; for (i = 1; i < argc; i++) { if (argv[i][0] == '-') { int opt = toupper(argv[i][1]); switch (opt) { case 'D': mode = 'd'; break; case 'E': mode = 'e'; break; case 'B': bufsize = atoi( &(argv[i][2]) ); break; case '?': usage() ; break; default : error("不正なオプションです"); } } else if (fncount == 0) { strcpy(input_fname, argv[i]); fncount++; } else if (fncount == 1) { strcpy(output_fname, argv[i]); fncount++; } } if (fncount == 0) { error("入力ファイル名がありません"); } if (fncount == 1) { strcpy(output_fname, input_fname); if (mode == 'd') strcat(output_fname, ".tst"); else strcat(output_fname, file_ext); } } /* メイン関数 */ int main(int argc, char *argv[]) { int start; getargs(argc, argv); start = clock(); if (mode == 'd') decode_file(); else encode_file(); printf("処理時間 %.3f 秒\n", (double)(clock() - start) / CLOCKS_PER_SEC); return 0; } /* end of file */