home *** CD-ROM | disk | FTP | other *** search
/ DOS/V Power Report 1997 December / VPR9712A.ISO / OLS / OS2 / LHA2P205 / LHA2P205.LZH / lha2-2.05pre / source.lzh / src / maketbl.c < prev    next >
C/C++ Source or Header  |  1994-10-23  |  2KB  |  107 lines
  1. /*
  2.  * maketbl.c --- makes decoding table
  3.  *   Copyright (C) 1988-1992, Haruyasu YOSHIZAKI
  4.  *
  5.  * $Log$
  6.  */
  7.  
  8.  
  9. #include <sys/types.h>
  10. #include <stdio.h>
  11. #include <limits.h>
  12. #include "typedef.h"
  13. #include "slidehuf.h"
  14. #include "intrface.h"
  15. #include "errmes.h"
  16.  
  17.  
  18. void
  19. make_table(short nchar, uchar bitlen[], short tablebits, ushort table[])
  20. {
  21.   ushort count[17];        /* コード長ごとの出現個数 */
  22.   ushort weight[17];        /* 0x10000ul >> bitlen */
  23.   ushort start[17];        /* その bitlen の最初のコード（左詰め） */
  24.   ushort total;
  25.   uint i;
  26.   int j, k, l, m, n, avail;
  27.   ushort *p;
  28.  
  29.   avail = nchar;
  30.  
  31.   /* 初期化 */
  32.   for(i = 1; i <= 16; i++)
  33.     {
  34.       count[i] = 0;
  35.       weight[i] = 1u << (16 - i);
  36.     }
  37.  
  38.   /* 出現回数を数える */
  39.   for(i = 0; i < nchar; i++)
  40.     count[bitlen[i]]++;
  41.  
  42.   /* 最初のコードの計算 */
  43.   total = 0;
  44.   for(i = 1; i <= 16; i++)
  45.     {
  46.       start[i] = total;
  47.       total += weight[i] * count[i];
  48.     }
  49.   if((total & 0xffff) != 0)
  50.     error(BROKENARC, "Bad table (5)");
  51.  
  52.   /* table 作成のため、table に入る部分を右詰めに変更 */
  53.   m = 16 - tablebits;
  54.   for(i = 1; i <= tablebits; i++)
  55.     {
  56.       start[i] >>= m;
  57.       weight[i] >>= m;
  58.     }
  59.  
  60.   /* table を溢れるコードのための初期化 */
  61.   j = start[tablebits + 1] >> m;
  62.   k = 1 << tablebits;
  63.   if(j != 0)
  64.     for(i = j; i < k; i++)
  65.       table[i] = 0;
  66.  
  67.   /* table, tree の作成 */
  68.   for(j = 0; j < nchar; j++)
  69.     {
  70.       k = bitlen[j];
  71.       if(k == 0)
  72.     continue;
  73.       l = start[k] + weight[k];
  74.       if(k <= tablebits)
  75.     {
  76.       /* table に納まるコード */
  77.       for(i = start[k]; i < l; i++)
  78.         table[i] = j;
  79.     }
  80.       else
  81.     {
  82.       /* table に納まらないコード */
  83.       p = &table[(i = start[k]) >> m];
  84.       i <<= tablebits;
  85.       n = k - tablebits;
  86.       /* 高さ n の tree を作る */
  87.       while(--n >= 0)
  88.         {
  89.           if(*p == 0)
  90.         {
  91.           /* 枝がまだ延びていなければ作る */
  92.           right[avail] = left[avail] = 0;
  93.           *p = avail++;
  94.         }
  95.           if(i & 0x8000)
  96.         p = &right[*p];
  97.           else
  98.         p = &left[*p];
  99.           i <<= 1;
  100.         }
  101.       *p = j;
  102.     }
  103.       /* bitlen が k の次の文字のコード */
  104.       start[k] = l;
  105.     }
  106. }
  107.