/***********************************************************
*
*    bpe2.c
*
*      Byte Pair Encoding ファイル符号化のテスト
*      ブロックのヘッダを省略できる場合省略する
*
***********************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <ctype.h>

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の値に限らず１回のみ) */
	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 */