home *** CD-ROM | disk | FTP | other *** search
/ Otherware / Otherware_1_SB_Development.iso / mac / util / unix / macutil2.sha / macutil / macunpack / de_lzh.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-11-05  |  6.0 KB  |  315 lines
  1. #include "macunpack.h"
  2. #ifdef ZMA
  3. #define DELZH
  4. #endif /* ZMA */
  5. #ifdef LZH
  6. #define DELZH
  7. #endif /* LZH */
  8. #ifdef DELZH
  9. #include "globals.h"
  10. #include "../util/masks.h"
  11. #include "../fileio/wrfile.h"
  12. #include "bits_be.h"
  13.  
  14. /* This code is valid for bitsused upto 15. */
  15. #define DICBIT    13    /* 12(-lh4-) or 13(-lh5-) */
  16. #define UCHAR_MAX    255
  17. #define THRESHOLD    3
  18.  
  19. static int decoded;
  20. static int bitsused;
  21. static unsigned int blocksize;
  22. static unsigned int decode_c();
  23. static unsigned int decode_p();
  24. static void make_table();
  25.  
  26. /* lzh compression */
  27. void de_lzh(ibytes, obytes, data, bits)
  28. long ibytes;
  29. long obytes;
  30. char **data;
  31. int bits;
  32. {
  33.     unsigned int i, r, c;
  34.     int remains;
  35.  
  36.     bit_be_inbytes = ibytes;
  37.     bit_be_filestart = *data;
  38.     bitsused = bits;
  39.     bit_be_init_getbits();
  40.     blocksize = 0;
  41.     decoded = 0;
  42.     r = 0;
  43.     for(;;) {
  44.     c = decode_c();
  45.     if(decoded) {
  46.         *data = bit_be_filestart;
  47.         return;
  48.     }
  49.     if(c <= UCHAR_MAX) {
  50.         out_ptr[r++] = c;
  51.         obytes--;
  52.         if(obytes == 0) {
  53.         *data = bit_be_filestart;
  54.         return;
  55.         }
  56.     } else {
  57.         remains = c - (UCHAR_MAX + 1 - THRESHOLD);
  58.         i = (r - decode_p() - 1);
  59.         while(--remains >= 0) {
  60.         out_ptr[r++] = out_ptr[i++];
  61.         obytes--;
  62.         if(obytes == 0) {
  63.             *data = bit_be_filestart;
  64.             return;
  65.         }
  66.         }
  67.     }
  68.     }
  69. }
  70.  
  71. #define MAXMATCH 256
  72. #define NC (UCHAR_MAX + MAXMATCH + 2 - THRESHOLD)
  73. #define CBIT 9
  74. #define CODE_BIT 16
  75. #define NP (DICBIT + 1)
  76. #define NT (CODE_BIT + 3)
  77. #define PBIT 4  /* smallest integer such that (1U << PBIT) > NP */
  78. #define TBIT 5  /* smallest integer such that (1U << TBIT) > NT */
  79. #if NT > NP
  80. # define NPT NT
  81. #else
  82. # define NPT NP
  83. #endif
  84.  
  85. static unsigned int left[2 * NC - 1], right[2 * NC - 1];
  86. static unsigned char c_len[NC], pt_len[NPT];
  87. static unsigned int c_table[4096], pt_table[256];
  88.  
  89. static void read_pt_len(nn, nbit, i_special)
  90. int nn;
  91. int nbit;
  92. int i_special;
  93. {
  94.     int i, c, n;
  95.     unsigned int mask;
  96.  
  97.     n = bit_be_getbits(nbit);
  98.     if (n == 0) {
  99.     c = bit_be_getbits(nbit);
  100.     for (i = 0; i < nn; i++) {
  101.         pt_len[i] = 0;
  102.     }
  103.     for (i = 0; i < 256; i++) {
  104.         pt_table[i] = c;
  105.     }
  106.     } else {
  107.     i = 0;
  108.     while (i < n) {
  109.         c = bit_be_bitbuf >> (BITBUFSIZ - 3);
  110.         if (c == 7) {
  111.         mask = (unsigned) 1 << (BITBUFSIZ - 1 - 3);
  112.         while (mask & bit_be_bitbuf) {
  113.             mask >>= 1;
  114.             c++;
  115.         }
  116.         }
  117.         bit_be_fillbuf((c < 7) ? 3 : c - 3);
  118.         pt_len[i++] = c;
  119.         if (i == i_special) {
  120.         c = bit_be_getbits(2);
  121.         while (--c >= 0) {
  122.             pt_len[i++] = 0;
  123.         }
  124.         }
  125.     }
  126.     while (i < nn) {
  127.         pt_len[i++] = 0;
  128.     }
  129.     make_table(nn, pt_len, 8, pt_table);
  130.     }
  131. }
  132.  
  133. static void read_c_len()
  134. {
  135.     int i, c, n;
  136.     unsigned int mask;
  137.  
  138.     n = bit_be_getbits(CBIT);
  139.     if (n == 0) {
  140.     c = bit_be_getbits(CBIT);
  141.     for (i = 0; i < NC; i++) {
  142.         c_len[i] = 0;
  143.     }
  144.     for (i = 0; i < 4096; i++) {
  145.         c_table[i] = c;
  146.     }
  147.     } else {
  148.     i = 0;
  149.     while (i < n) {
  150.         c = pt_table[bit_be_bitbuf >> (BITBUFSIZ - 8)];
  151.         if (c >= NT) {
  152.         mask = (unsigned) 1 << (BITBUFSIZ - 1 - 8);
  153.         do {
  154.             if (bit_be_bitbuf & mask) {
  155.             c = right[c];
  156.             } else {
  157.             c = left [c];
  158.             }
  159.             mask >>= 1;
  160.         } while (c >= NT);
  161.         }
  162.         bit_be_fillbuf((int)pt_len[c]);
  163.         if (c <= 2) {
  164.         if (c == 0) {
  165.             c = 1;
  166.         } else if (c == 1) {
  167.             c = bit_be_getbits(4) + 3;
  168.         } else {
  169.             c = bit_be_getbits(CBIT) + 20;
  170.         }
  171.         while (--c >= 0) {
  172.             c_len[i++] = 0;
  173.         }
  174.         } else {
  175.         c_len[i++] = c - 2;
  176.         }
  177.     }
  178.     while (i < NC) {
  179.         c_len[i++] = 0;
  180.     }
  181.     make_table(NC, c_len, 12, c_table);
  182.     }
  183. }
  184.  
  185. static unsigned int decode_c()
  186. {
  187.     unsigned int j, mask;
  188.  
  189.     if (blocksize == 0) {
  190.     blocksize = bit_be_getbits(16);
  191.     if (blocksize == 0) {
  192.         decoded = 1;
  193.         return 0;
  194.     }
  195.     read_pt_len(NT, TBIT, 3);
  196.     read_c_len();
  197.     read_pt_len(bitsused + 1, PBIT, -1);
  198.     }
  199.     blocksize--;
  200.     j = c_table[bit_be_bitbuf >> (BITBUFSIZ - 12)];
  201.     if (j >= NC) {
  202.     mask = (unsigned) 1 << (BITBUFSIZ - 1 - 12);
  203.     do {
  204.         if (bit_be_bitbuf & mask) {
  205.         j = right[j];
  206.         } else {
  207.         j = left [j];
  208.         }
  209.         mask >>= 1;
  210.     } while (j >= NC);
  211.     }
  212.     bit_be_fillbuf((int)c_len[j]);
  213.     return j;
  214. }
  215.  
  216. static unsigned int decode_p()
  217. {
  218.     unsigned int j, mask;
  219.  
  220.     j = pt_table[bit_be_bitbuf >> (BITBUFSIZ - 8)];
  221.     if (j > bitsused) {
  222.     mask = (unsigned) 1 << (BITBUFSIZ - 1 - 8);
  223.     do {
  224.         if (bit_be_bitbuf & mask) {
  225.         j = right[j];
  226.         } else {
  227.         j = left [j];
  228.         }
  229.         mask >>= 1;
  230.     } while (j > bitsused);
  231.     }
  232.     bit_be_fillbuf((int)pt_len[j]);
  233.     if (j != 0) {
  234.     j = ((unsigned) 1 << (j - 1)) + bit_be_getbits((int) (j - 1));
  235.     }
  236.     return j;
  237. }
  238.  
  239. static void make_table(nchar, bitlen, tablebits, table)
  240. int nchar;
  241. unsigned char bitlen[];
  242. int tablebits;
  243. unsigned int table[];
  244. {
  245.     unsigned int count[17], weight[17], start[18], *p;
  246.     unsigned int i, k, len, ch, jutbits, avail, nextcode, mask;
  247.  
  248.     for (i = 1; i <= 16; i++) {
  249.     count[i] = 0;
  250.     }
  251.     for (i = 0; i < nchar; i++) {
  252.     count[bitlen[i]]++;
  253.     }
  254.  
  255.     start[1] = 0;
  256.     for (i = 1; i <= 16; i++) {
  257.     start[i + 1] = start[i] + (count[i] << (16 - i));
  258.     }
  259.  
  260.     jutbits = 16 - tablebits;
  261.     for (i = 1; i <= tablebits; i++) {
  262.     start[i] >>= jutbits;
  263.     weight[i] = (unsigned) 1 << (tablebits - i);
  264.     }
  265.     while (i <= 16) {
  266.        weight[i] = (unsigned) 1 << (16 - i);
  267.        i++;
  268.     }
  269.  
  270.     i = start[tablebits + 1] >> jutbits;
  271.     if (i != (unsigned int)((unsigned) 1 << 16)) {
  272.     k = 1 << tablebits;
  273.     while (i != k) {
  274.         table[i++] = 0;
  275.     }
  276.     }
  277.  
  278.     avail = nchar;
  279.     mask = (unsigned) 1 << (15 - tablebits);
  280.     for (ch = 0; ch < nchar; ch++) {
  281.     if ((len = bitlen[ch]) == 0) {
  282.         continue;
  283.     }
  284.     nextcode = start[len] + weight[len];
  285.     if (len <= tablebits) {
  286.         for (i = start[len]; i < nextcode; i++) {
  287.         table[i] = ch;
  288.         }
  289.     } else {
  290.         k = start[len];
  291.         p = &table[k >> jutbits];
  292.         i = len - tablebits;
  293.         while (i != 0) {
  294.         if (*p == 0) {
  295.             right[avail] = left[avail] = 0;
  296.             *p = avail++;
  297.         }
  298.         if (k & mask) {
  299.             p = &right[*p];
  300.         } else {
  301.             p = &left[*p];
  302.         }
  303.         k <<= 1;
  304.         i--;
  305.         }
  306.         *p = ch;
  307.     }
  308.     start[len] = nextcode;
  309.     }
  310. }
  311. #else /* DELZH */
  312. int delzh; /* keep lint and some compilers happy */
  313. #endif /* DELZH */
  314.  
  315.