typedef struct { int chr; /* 文字 */ long count; /* 子ノードの出現頻度の和 */ int parent; /* 親ノードへ */ int left; /* 左側の子ノードへ */ int right; /* 右側の子ノードへ */ } NODE; #define ROOT 0 /* ルート */ #define EOF_NODE 1 /* EOFノード */ #define CHAR_SIZE 256 #define NODE_SIZE (2*CHAR_SIZE+2) /* ノードの最大個数 */ long enFGK(unsigned char *code, long clen,unsigned char *text, long tlen){ int i, j, k; long c, len; int curChar; int zeroNode, thisNode, maxid; int node2id[NODE_SIZE]; /* ノードからそのノード番号 */ int char2node[CHAR_SIZE]; NODE node[NODE_SIZE]; int freeNode; char bit[NODE_SIZE]; char *bitp; static unsigned char bit0[8] = {~128,~64,~32,~16,~8,~4,~2,~1}; static unsigned char bit1[8] = { 128, 64, 32, 16, 8, 4, 2, 1}; if (tlen <= 0) return -1L; for (i = 0; i < CHAR_SIZE; i++) char2node[i] = 0; /* 初期ハフマン木 */ zeroNode = 2; node[2].count = 0; node[2].parent = ROOT; node[EOF_NODE].count = 1; node[EOF_NODE].parent = ROOT; node[ROOT].count = 0x7FFFFFFFL; node[ROOT].parent = 0; node[ROOT].left = zeroNode; node[ROOT].right = EOF_NODE; node2id[zeroNode] = 0; node2id[EOF_NODE] = 1; node2id[ROOT] = 2; freeNode = 3; /* 各文字を符号化 */ for (i = 0, c = 0, len = 0, bitp = bit; ; c++) { /* 入力文字に対応するノード */ if (c >= tlen) thisNode = EOF_NODE; else if ((thisNode = char2node[curChar = text[c]]) == 0) { thisNode = zeroNode; for (j = 7; j >= 0; j--) *bitp++ = curChar & bit1[j]; } /* 符号語を得る */ k = thisNode; do { int parent = node[k].parent; *bitp++ = (node[parent].left == k) ? 0 : 1; k = parent; } while (k != ROOT); /* 逆順に出力 */ do { if (*--bitp) *code |= bit1[i]; else *code &= bit0[i]; if (++i == 8) { code++; if (++len > clen) return -1L; i = 0; } } while (bitp != bit); if (c == tlen) break; /* EOF */ /* ハフマン木を更新 */ while (thisNode != ROOT) { if (thisNode == zeroNode) { for (j = 0; j < freeNode; j++) node2id[j] += 2; node[zeroNode].left = freeNode; node[freeNode].count = 0; node[freeNode].parent = zeroNode; node2id[freeNode] = 0; freeNode++; node[zeroNode].right = freeNode; node[freeNode].count = 1; node[freeNode].parent = zeroNode; node2id[freeNode] = 1; char2node[curChar] = freeNode; /* 新文字 */ freeNode++; thisNode = zeroNode; zeroNode = freeNode - 2; } else { if (node[thisNode].count == 1 && node[k = node[thisNode].parent].count == 1) { /* 0-ノードの兄弟 */ for (j = 0, maxid = thisNode; j < freeNode; j++) if (node[j].count == 1 && j != k && node2id[j] > node2id[maxid]) maxid = j; } else { for (j = 0, maxid = thisNode; j < freeNode; j++) if (node[thisNode].count == node[j].count && node2id[j] > node2id[maxid]) maxid = j; } if (maxid != thisNode) { int maxidP = node[maxid].parent; int thisP = node[thisNode].parent; int id = node2id[maxid]; if (node[maxidP].left == maxid) node[maxidP].left = thisNode; else node[maxidP].right = thisNode; if (node[thisP].left == thisNode) node[thisP].left = maxid; else node[thisP].right = maxid; node[maxid].parent = thisP; node[thisNode].parent = maxidP; node2id[maxid] = node2id[thisNode]; node2id[thisNode] = id; } node[thisNode].count++; thisNode = node[thisNode].parent; } } } if (i > 0) len++; return (len > clen) ? -1L : len; } long deFGK(unsigned char *text, long tlen,unsigned char *code, long clen){ int i, j, k; long c, len; int curChar; int zeroNode, thisNode, maxid; int node2id[NODE_SIZE]; /* ノードからそのノード番号 */ NODE node[NODE_SIZE]; int freeNode; static unsigned char bit1[8] = { 128, 64, 32, 16, 8, 4, 2, 1}; if (clen <= 0) return -1L; /* 初期ハフマン木 */ zeroNode = 2; node[2].chr = CHAR_SIZE+1; node[2].count = 0; node[2].parent = ROOT; node[EOF_NODE].chr = CHAR_SIZE; node[EOF_NODE].count = 1; node[EOF_NODE].parent = ROOT; node[ROOT].count = 0x7FFFFFFFL; node[ROOT].parent = 0; node[ROOT].left = zeroNode; node[ROOT].right = EOF_NODE; node2id[zeroNode] = 0; node2id[EOF_NODE] = 1; node2id[ROOT] = 2; freeNode = 3; /* 復号化 */ for (i = 0, c = 0, len = 0; ; ) { /* 符号語に対応する文字ノードを得る */ thisNode = ROOT; do { thisNode = (*code & bit1[i]) ? node[thisNode].right : node[thisNode].left; if (thisNode >= freeNode) return -1L; if (++i == 8) { code++; if (++c > clen) return -1L; i = 0; } } while (node[thisNode].chr < 0); if (thisNode == EOF_NODE) break; /* EOF */ if (thisNode == zeroNode) { /* 新文字 */ curChar = 0; for (j = 0; j < 8; j++) { if (*code & bit1[i]) curChar |= bit1[j]; if (++i == 8) { code++; if (++c > clen) return -1L; i = 0; } } } else curChar = node[thisNode].chr; if (++len > tlen) return -1L; *text++ = curChar; /* 文字の出力 */ /* ハフマン木を更新 */ while (thisNode != ROOT) { if (thisNode == zeroNode) { for (j = 0; j < freeNode; j++) node2id[j] += 2; node[zeroNode].left = freeNode; node[freeNode].count = 0; node[freeNode].parent = zeroNode; node2id[freeNode] = 0; node[freeNode].chr = CHAR_SIZE + 1; freeNode++; node[zeroNode].right = freeNode; node[freeNode].count = 1; node[freeNode].parent = zeroNode; node2id[freeNode] = 1; node[freeNode].chr = curChar; freeNode++; thisNode = zeroNode; node[thisNode].chr = -1; zeroNode = freeNode - 2; } else { if (node[thisNode].count == 1 && node[k = node[thisNode].parent].count == 1) { /* 0-ノードの兄弟 */ for (j = 0, maxid = thisNode; j < freeNode; j++) if (node[j].count == 1 && j != k && node2id[j] > node2id[maxid]) maxid = j; } else { for (j = 0, maxid = thisNode; j < freeNode; j++) if (node[thisNode].count == node[j].count && node2id[j] > node2id[maxid]) maxid = j; } if (maxid != thisNode) { int maxidP = node[maxid].parent; int thisP = node[thisNode].parent; int id = node2id[maxid]; if (node[maxidP].left == maxid) node[maxidP].left = thisNode; else node[maxidP].right = thisNode; if (node[thisP].left == thisNode) node[thisP].left = maxid; else node[thisP].right = maxid; node[maxid].parent = thisP; node[thisNode].parent = maxidP; node2id[maxid] = node2id[thisNode]; node2id[thisNode] = id; } node[thisNode].count++; thisNode = node[thisNode].parent; } } } return len; }