home *** CD-ROM | disk | FTP | other *** search
/ QBasic & Borland Pascal & C / Delphi5.iso / C / Samples / COMPRESS.ARJ / ARJ / DECODE.C next >
Encoding:
C/C++ Source or Header  |  1991-04-06  |  10.4 KB  |  497 lines
  1. /* DECODE.C, UNARJ, R JUNG, 04/05/91
  2. /* Decode ARJ archive
  3. /* Copyright (c) 1991 by Robert K Jung.  All rights reserved.
  4. /*
  5. /*   This code may be freely used in programs that are NOT archivers.
  6. /*
  7. /* Modification history:
  8. /* Date      Programmer  Description of modification.
  9. /* 04/05/91  R. Jung     Rewrote code.
  10. /*
  11.  */
  12.  
  13. #include "unarj.h"
  14.  
  15. #include <stdlib.h>
  16. #include <string.h>
  17.  
  18. #define THRESHOLD    3
  19. #define DDICSIZ      26624
  20. #define MAXDICBIT   16
  21. #define MATCHBIT     8
  22. #define MAXMATCH   256        /* not more than UCHAR_MAX + 1 */
  23. #define NC        (UCHAR_MAX + MAXMATCH + 2 - THRESHOLD)
  24. #define NP          (MAXDICBIT + 1)
  25. #define CBIT         9
  26. #define NT          (CODE_BIT + 3)
  27. #define PBIT         5      /* smallest integer such that (1U << PBIT) > NP */
  28. #define TBIT         5      /* smallest integer such that (1U << TBIT) > NT */
  29.  
  30. #if NT > NP
  31. #define NPT NT
  32. #else
  33. #define NPT NP
  34. #endif
  35.  
  36. #define CTABLESIZE  4096
  37.  
  38. #define STRTP          9
  39. #define STOPP         13
  40.  
  41. #define STRTL          0
  42. #define STOPL          7
  43.  
  44. /* Local variables */
  45.  
  46. static short  getlen;
  47. static short  getbuf;
  48.  
  49. static ushort left[2 * NC - 1];
  50. static ushort right[2 * NC - 1];
  51. static uchar  c_len[NC];
  52. static uchar  pt_len[NPT];
  53.  
  54. static ushort c_table[CTABLESIZE];
  55. static ushort pt_table[256];
  56. static ushort blocksize;
  57.  
  58. /* Huffman decode routines */
  59.  
  60. static void
  61. make_table(int nchar, uchar bitlen[], int tablebits, ushort table[])
  62. {
  63.     ushort count[17], weight[17], start[18], *p;
  64.     uint i, k, len, ch, jutbits, avail, nextcode, mask;
  65.  
  66.     for (i = 1; i <= 16; i++)
  67.     count[i] = 0;
  68.     for (i = 0; (int)i < nchar; i++)
  69.     count[bitlen[i]]++;
  70.  
  71.     start[1] = 0;
  72.     for (i = 1; i <= 16; i++)
  73.     start[i + 1] = start[i] + (count[i] << (16 - i));
  74.     if (start[17] != (ushort) (1U << 16))
  75.         error(M_BADTABLE, 0);
  76.  
  77.     jutbits = 16 - tablebits;
  78.     for (i = 1; (int)i <= tablebits; i++)
  79.     {
  80.     start[i] >>= jutbits;
  81.     weight[i] = 1U << (tablebits - i);
  82.     }
  83.     while (i <= 16)
  84.     weight[i++] = 1U << (16 - i);
  85.  
  86.     i = start[tablebits + 1] >> jutbits;
  87.     if (i != (ushort) (1U << 16))
  88.     {
  89.     k = 1U << tablebits;
  90.     while (i != k)
  91.         table[i++] = 0;
  92.     }
  93.  
  94.     avail = nchar;
  95.     mask = 1U << (15 - tablebits);
  96.     for (ch = 0; (int)ch < nchar; ch++)
  97.     {
  98.     if ((len = bitlen[ch]) == 0)
  99.         continue;
  100.     nextcode = start[len] + weight[len];
  101.         if ((int)len <= tablebits)
  102.     {
  103.         for (i = start[len]; i < nextcode; i++)
  104.         table[i] = ch;
  105.     }
  106.     else
  107.     {
  108.         k = start[len];
  109.         p = &table[k >> jutbits];
  110.         i = len - tablebits;
  111.         while (i != 0)
  112.         {
  113.         if (*p == 0)
  114.         {
  115.             right[avail] = left[avail] = 0;
  116.             *p = avail++;
  117.         }
  118.         if (k & mask)
  119.             p = &right[*p];
  120.         else
  121.             p = &left[*p];
  122.         k <<= 1;
  123.         i--;
  124.         }
  125.         *p = ch;
  126.     }
  127.     start[len] = nextcode;
  128.     }
  129. }
  130.  
  131. static void
  132. read_pt_len(short nn, short nbit, short i_special)
  133. {
  134.     short i, c, n;
  135.     ushort mask;
  136.  
  137.     n = getbits(nbit);
  138.     if (n == 0)
  139.     {
  140.         c = getbits(nbit);
  141.         for (i = 0; i < nn; i++)
  142.             pt_len[i] = 0;
  143.         for (i = 0; i < 256; i++)
  144.             pt_table[i] = c;
  145.     }
  146.     else
  147.     {
  148.         i = 0;
  149.         while (i < n)
  150.         {
  151.             c = bitbuf >> (16 - 3);
  152.             if (c == 7)
  153.             {
  154.         mask = 1U << (16 - 4);
  155.         while (mask & bitbuf)
  156.                 {
  157.                     mask >>= 1;
  158.                     c++;
  159.                 }
  160.             }
  161.             fillbuf((c < 7) ? 3 : c - 3);
  162.         pt_len[i++] = (uchar)c;
  163.             if (i == i_special)
  164.             {
  165.                 c = getbits(2);
  166.                 while (--c >= 0)
  167.                     pt_len[i++] = 0;
  168.             }
  169.         }
  170.         while (i < nn)
  171.             pt_len[i++] = 0;
  172.         make_table(nn, pt_len, 8, pt_table);
  173.     }
  174. }
  175.  
  176. static void
  177. read_c_len(void)
  178. {
  179.     short i, c, n;
  180.     ushort mask;
  181.  
  182.     n = getbits(CBIT);
  183.     if (n == 0)
  184.     {
  185.         c = getbits(CBIT);
  186.         for (i = 0; i < NC; i++)
  187.             c_len[i] = 0;
  188.         for (i = 0; i < CTABLESIZE; i++)
  189.             c_table[i] = c;
  190.     }
  191.     else
  192.     {
  193.         i = 0;
  194.         while (i < n)
  195.         {
  196.             c = pt_table[bitbuf >> (16 - 8)];
  197.             if (c >= NT)
  198.             {
  199.         mask = 1U << (16 - 9);
  200.         do
  201.                 {
  202.                     if (bitbuf & mask)
  203.                         c = right[c];
  204.                     else
  205.                         c = left[c];
  206.                     mask >>= 1;
  207.                 } while (c >= NT);
  208.             }
  209.             fillbuf(pt_len[c]);
  210.             if (c <= 2)
  211.             {
  212.                 if (c == 0)
  213.                     c = 1;
  214.                 else if (c == 1)
  215.                     c = getbits(4) + 3;
  216.                 else
  217.                     c = getbits(CBIT) + 20;
  218.                 while (--c >= 0)
  219.                     c_len[i++] = 0;
  220.             }
  221.             else
  222.         c_len[i++] = (uchar)(c - 2);
  223.         }
  224.         while (i < NC)
  225.             c_len[i++] = 0;
  226.         make_table(NC, c_len, 12, c_table);
  227.     }
  228. }
  229.  
  230. static ushort
  231. decode_c(void)
  232. {
  233.     ushort j, mask;
  234.  
  235.     if (blocksize == 0)
  236.     {
  237.         blocksize = getbits(16);
  238.         read_pt_len(NT, TBIT, 3);
  239.         read_c_len();
  240.         read_pt_len(NP, PBIT, -1);
  241.     }
  242.     blocksize--;
  243.     j = c_table[bitbuf >> 4];
  244.     if (j >= NC)
  245.     {
  246.         mask = 1U << (16 - 1 - 12);
  247.     do
  248.     {
  249.         if (bitbuf & mask)
  250.         j = right[j];
  251.         else
  252.         j = left[j];
  253.         mask >>= 1;
  254.     } while (j >= NC);
  255.     }
  256.     fillbuf(c_len[j]);
  257.     return j;
  258. }
  259.  
  260. static ushort
  261. decode_p(void)
  262. {
  263.     ushort j, mask;
  264.  
  265.     j = pt_table[bitbuf >> (16 - 8)];
  266.     if (j >= NP)
  267.     {
  268.         mask = 1U << (16 - 1 - 8);
  269.     do
  270.     {
  271.         if (bitbuf & mask)
  272.         j = right[j];
  273.         else
  274.         j = left[j];
  275.         mask >>= 1;
  276.     } while (j >= NP);
  277.     }
  278.     fillbuf(pt_len[j]);
  279.     if (j != 0)
  280.     {
  281.         j--;
  282.         j = (1U << j) + getbits(j);
  283.     }
  284.     return j;
  285. }
  286.  
  287. static void
  288. decode_start(void)
  289. {
  290.     blocksize = 0;
  291.     init_getbits();
  292. }
  293.  
  294. void
  295. decode(void)
  296. {
  297.     short i;
  298.     short j;
  299.     short c;
  300.     short r;
  301.     uchar *text;
  302.     long count;
  303.  
  304.     text = (uchar *)malloc_msg(DDICSIZ);
  305.  
  306.     decode_start();
  307.     count = 0;
  308.     r = 0;
  309.  
  310.     while (count < origsize)
  311.     {
  312.         if ((c = decode_c()) <= UCHAR_MAX)
  313.         {
  314.         text[r] = (uchar) c;
  315.             count++;
  316.             if (++r >= DDICSIZ)
  317.             {
  318.                 r = 0;
  319.                 putc('.', stdout);
  320.                 fwrite_txt_crc(text, DDICSIZ);
  321.             }
  322.         }
  323.         else
  324.         {
  325.             j = c - (UCHAR_MAX + 1 - THRESHOLD);
  326.             count += j;
  327.             i = decode_p();
  328.             if ((i = r - i - 1) < 0)
  329.                 i += DDICSIZ;
  330.             if (r > i && r < DDICSIZ - MAXMATCH - 1)
  331.             {
  332.                 while (--j >= 0)
  333.                     text[r++] = text[i++];
  334.             }
  335.             else
  336.             {
  337.                 while (--j >= 0)
  338.                 {
  339.                     text[r] = text[i];
  340.                     if (++r >= DDICSIZ)
  341.                     {
  342.                         r = 0;
  343.                         putc('.', stdout);
  344.                         fwrite_txt_crc(text, DDICSIZ);
  345.                     }
  346.                     if (++i >= DDICSIZ)
  347.                         i = 0;
  348.                 }
  349.             }
  350.         }
  351.     }
  352.     if (r != 0)
  353.         fwrite_txt_crc(text, r);
  354.  
  355. exit:
  356.     free(text);
  357. }
  358.  
  359. /* Macros */
  360.  
  361. #define GETBIT(c)                       \
  362. {                                       \
  363.     if (getlen <= 0)                    \
  364.     {                                   \
  365.         getbuf |= bitbuf >> getlen;     \
  366.         fillbuf(CODE_BIT-getlen);       \
  367.         getlen = CODE_BIT;              \
  368.     }                                   \
  369.     c = getbuf < 0;                     \
  370.     getbuf <<= 1;                       \
  371.     getlen--;                           \
  372. }
  373.  
  374. #define GETBITS(c, len)                 \
  375. {                                       \
  376.     if (getlen < (len))                 \
  377.     {                                   \
  378.         getbuf |= bitbuf >> getlen;     \
  379.         fillbuf(CODE_BIT-getlen);       \
  380.         getlen = CODE_BIT;              \
  381.     }                                   \
  382.     c = (ushort)getbuf>>(CODE_BIT-(len));\
  383.     getbuf <<= (len);                   \
  384.     getlen -= (len);                    \
  385. }
  386.  
  387. static short
  388. decode_ptr(void)
  389. {
  390.     short c;
  391.     short width;
  392.     short plus;
  393.     short pwr;
  394.  
  395.     plus = 0;
  396.     pwr = 1 << (STRTP);
  397.     for (width = (STRTP); width < (STOPP) ; width++)
  398.     {
  399.         GETBIT(c);
  400.         if (c == 0)
  401.             break;
  402.         plus += pwr;
  403.         pwr <<= 1;
  404.     }
  405.     if (width != 0)
  406.         GETBITS(c, width);
  407.     c += plus;
  408.     return c;
  409. }
  410.  
  411. static short
  412. decode_len(void)
  413. {
  414.     short c;
  415.     short width;
  416.     short plus;
  417.     short pwr;
  418.  
  419.     plus = 0;
  420.     pwr = 1 << (STRTL);
  421.     for (width = (STRTL); width < (STOPL) ; width++)
  422.     {
  423.         GETBIT(c);
  424.         if (c == 0)
  425.             break;
  426.         plus += pwr;
  427.         pwr <<= 1;
  428.     }
  429.     if (width != 0)
  430.         GETBITS(c, width);
  431.     c += plus;
  432.     return c;
  433. }
  434.  
  435. void
  436. decode_f(void)
  437. {
  438.     short i;
  439.     short j;
  440.     short c;
  441.     short r;
  442.     short pos;
  443.     long count;
  444.     uchar *text;
  445.  
  446.     text = (uchar *)malloc_msg(DDICSIZ);
  447.  
  448.     init_getbits();
  449.     getlen = getbuf = 0;
  450.     count = 0;
  451.     r = 0;
  452.  
  453.     while (count < origsize)
  454.     {
  455.         c = decode_len();
  456.         if (c == 0)
  457.         {
  458.             GETBITS(c, CHAR_BIT);
  459.         text[r] = (uchar)c;
  460.             count++;
  461.             if (++r >= DDICSIZ)
  462.             {
  463.                 r = 0;
  464.                 putc('.', stdout);
  465.                 fwrite_txt_crc(text, DDICSIZ);
  466.             }
  467.         }
  468.         else
  469.         {
  470.             j = c - 1 + THRESHOLD;
  471.             count += j;
  472.             pos = decode_ptr();
  473.             if ((i = r - pos - 1) < 0)
  474.                 i += DDICSIZ;
  475.             while (j-- > 0)
  476.             {
  477.                 text[r] = text[i];
  478.                 if (++r >= DDICSIZ)
  479.                 {
  480.                     r = 0;
  481.                     putc('.', stdout);
  482.                     fwrite_txt_crc(text, DDICSIZ);
  483.                 }
  484.                 if (++i >= DDICSIZ)
  485.                     i = 0;
  486.             }
  487.         }
  488.     }
  489.     if (r != 0)
  490.         fwrite_txt_crc(text, r);
  491.  
  492. exit:
  493.     free(text);
  494. }
  495.  
  496. /* end DECODE.C */
  497.