Algorithm 版 (精华区)

发信人: lofe ()感激生活(), 信区: Algorithm
标  题: ar002--Maketbl.c
发信站: 哈工大紫丁香 (Sun Sep  3 08:28:27 2000), 转信

/***********************************************************
        maketbl.c -- make table for decoding
***********************************************************/
#include "ar.h"

void make_table(int nchar, uchar bitlen[], int tablebits, ushort table[])
{
        ushort count[17], weight[17], start[18], *p;
        uint i, k, len, ch, jutbits, avail, nextcode, mask;

        for (i = 1; i <= 16; i++) count[i] = 0;
        for (i = 0; i < nchar; i++) count[bitlen[i]]++;

        start[1] = 0;
        for (i = 1; i <= 16; i++)
                start[i + 1] = start[i] + (count[i] << (16 - i));
        if (start[17] != (ushort)(1U << 16)) error("Bad table");

        jutbits = 16 - tablebits;
        for (i = 1; i <= tablebits; i++) {
                start[i] >>= jutbits;
                weight[i] = 1U << (tablebits - i);
        }
        while (i <= 16) weight[i++] = 1U << (16 - i);

        i = start[tablebits + 1] >> jutbits;
        if (i != (ushort)(1U << 16)) {
                k = 1U << tablebits;
                while (i != k) table[i++] = 0;
        }

        avail = nchar;
        mask = 1U << (15 - tablebits);
        for (ch = 0; ch < nchar; ch++) {
                if ((len = bitlen[ch]) == 0) continue;
                nextcode = start[len] + weight[len];
                if (len <= tablebits) {
                        for (i = start[len]; i < nextcode; i++) table[i] = ch;
                } else {
                        k = start[len];
                        p = &table[k >> jutbits];
                        i = len - tablebits;
                        while (i != 0) {
                                if (*p == 0) {
                                        right[avail] = left[avail] = 0;
                                        *p = avail++;
                                }
                                if (k & mask) p = &right[*p];
                                else          p = &left[*p];
                                k <<= 1;  i--;
                        }
                        *p = ch;
                }
                start[len] = nextcode;
        }
}

--
We Are the World!
                        infosite@263.net
※ 修改:．haojs 于 Sep  3 08:26:01 修改本文．[FROM: bbs.hit.edu.cn]
--
※ 转寄:．武汉白云黄鹤站 bbs.whnet.edu.cn．[FROM: bbs.hit.edu.cn]

--
☆ 来源:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: haojs.bbs@bbs.whnet.]