typedef struct {
long count; /* 출현 빈도 */
int chr; /* 문자 */
int len; /* 부호어의 비트수 */
unsigned char code[8]; /* 부호어 */
int info; /* 0:처리대, 1:Group 선두,2:처리필 */
} CELL;
#define CHAR_SIZE 256 /* 기호 종류 */
long enShannon(unsigned char *code, long clen, unsigned char *text, long tlen){
int i, j, k;
long c, len;
long max;
CELL *cell;
int cellsize;
long count[CHAR_SIZE+1];
int char2cell[CHAR_SIZE+1];
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};
CELL *getCode();
if (tlen <= 0 || clen <= 512) return -1L;
/* 각 문자의 출현 빈도를 계산 */
for (i = 0; i < CHAR_SIZE; i++) count[i] = 0;
for (c = 0; c < tlen; c++) count[text[c]]++;
/* 최대 출현 빈도의 값이 2바이트를 넘지 않게 조정한다 */
for (i = 0, max = 0; i < CHAR_SIZE; i++)
if (count[i] > max) max = count[i];
if ((k = max/0x10000L) > 0)
for (i = 0, k++; i < CHAR_SIZE; i++)
if (count[i] > 0) {
count[i] /= k;
if (count[i] == 0) count[i] = 1;
}
/* 각 문자의 출현 빈도를 출력 */
for (i = 0; i < CHAR_SIZE; i++) {
*code++ = (count[i] >> 8) & 0xff;
*code++ = count[i] & 0xff;
}
count[CHAR_SIZE] = 1; /* EOF */
/* 부호어를 얻는다 */
if ((cell = getCode(&cellsize, count)) == NULL) return -1L;
/* 문자를 부호어와 대응시킨다 */
for (i = 0; i < cellsize; i++) char2cell[cell[i]. chr] = i;
/* 각 문자를 encode */
for (c = 0, i = 0, len = 512; ; c++) {
k = (c == tlen) ? 256 : text[c];
k = char2cell[k];
/* 부호어를 출력 */
for (j = 0; j < cell[k]. len; j++) {
if (cell[k]. code[j>>3] & bit1[j&7]) *code |= bit1[i];
else *code &= bit0[i];
if (++i == 8) {
code++;
if (++len > clen) {
free(cell);
return -1L;
}
i = 0;
}
}
if (c == tlen) break;
}
free(cell);
if (i > 0) len++;
return (len > clen) ? -1L : len;
}
long deShannon(unsigned char *text, long tlen,
unsigned char *code, long clen)
{
int i, j, k;
long c, len;
CELL *cell;
int cellsize;
long count[CHAR_SIZE+1];
# define NODE_SIZE (2*CHAR_SIZE+2)
struct { int chr, left, right; } node[NODE_SIZE];
int root, freeNode;
static unsigned char bit1[8] = {128,64,32,16,8,4,2,1};
CELL *getCode();
if (clen <= 512) return -1L;
/* 각 문자의 출현 빈도를 세트 */
for (i = 0; i < CHAR_SIZE; i++) count[i] = 0;
for (i = 0; i < 256; i++) {
count[i] = *code++;
count[i] = (count[i] << 8) | *code++;
}
/* EOF */
count[256] = 1;
/* 부호어를 얻는다 */
if ((cell = getCode(&cellsize, count)) == NULL) return -1L;
/* 부호어에 대응하는 부호나무를 만든다 */
for (i = 0; i < NODE_SIZE; i++) {
node[i]. chr = NODE_SIZE;
node[i]. left = node[i]. right = 0;
}
root = 0; freeNode = 1;
for (i = 0; i < cellsize; i++) {
for (j = 0, k = root; j < cell[i]. len; j++) {
if (cell[i]. code[j>>3] & bit1[j&7]) {
if (node[k]. right == 0) node[k]. right = freeNode++;
k = node[k]. right;
} else {
if (node[k]. left == 0) node[k]. left = freeNode++;
k = node[k]. left;
}
}
node[k]. chr = cell[i]. chr;
}
/* 복호화 */
for (i = 0, len = 0, c = 512; ; ) {
/* 부호어에 대응하는 문자 노드를 얻는다 */
k = root;
do {
k = (*code & bit1[i]) ? node[k]. right : node[k]. left;
if (++i == 8) {
code++;
if (++c > clen) return -1L;
i = 0;
}
} while (node[k]. chr > CHAR_SIZE);
if (node[k]. chr == CHAR_SIZE) break;
if (++len > tlen) {
free(cell);
return -1L;
}
*text++ = node[k]. chr;
}
free(cell);
return len;
}
/* 부호어를 얻는다 */
static CELL *getCode(int *cellsize, long *count){
int i, j, k;
CELL *cell;
int size;
long sum, half;
int left, mid, right;
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};
/* 그룹 크기의 결정 */
for (i = 0, size = 0; i <= CHAR_SIZE; i++) if (count[i] > 0) size++;
if ((cell = (CELL *) malloc(sizeof(CELL) *size)) == NULL) return NULL;
/* 문자의 출현 빈도를 내림차순에 소트 */
for (i = 0, j = 0; i <= CHAR_SIZE; i++)
if (count[i] > 0) {
cell[j]. count = count[i];
cell[j]. chr = i;
cell[j]. len = 0;
cell[j]. info = 0;
j++;
}
for (i = 0; i < size - 1; i++) {
k = i;
for (j = i+1; j < size; j++)
if (cell[j]. count > cell[k]. count) k = j;
if (k ! = i) {
long tcount = cell[k]. count;
int tchr = cell[k]. chr;
cell[k]. count = cell[i]. count;
cell[i]. count = tcount;
cell[k]. chr = cell[i]. chr;
cell[i]. chr = tchr;
}
}
cell[0]. info = 1;
/* 그룹을 세분비율 해, 부호어를 얻는다 */
for ( ; ; ) {
/* 그룹의 선두를 찾아낸다 */
for (i = 0, left = -1; i < size; i++)
if (cell[i]. info == 1) {
left = i;
break;
}
if (left < 0) break;
/* 그룹의 말미를 찾아낸다 */
for (i = left + 1, right = size - 1; i < size; i++)
if (cell[i]. info > 0) {
right = i - 1;
break;
}
/* 그룹내의 출현 빈도의 화 */
for (i = left, sum = 0; i <= right; i++) sum += cell[i]. count;
/* 그룹의 분할 위치 */
for (mid = left, half = 0; mid < right && half < sum/2; mid++)
half += cell[mid]. count;
/* 부호어의 추가 */
for (i = left; i <= right; i++) {
if (i<mid) cell[i]. code[cell[i]. len>>3]&=bit0[cell[i]. len&7];
else cell[i]. code[cell[i]. len>>3]|=bit1[cell[i]. len&7];
cell[i]. len++;
}
if (mid == left + 1) cell[left]. info = 2;
cell[mid]. info = (mid == right) ? 2 : 1;
}
*cellsize = size;
return cell;
}