home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 9 Archive / 09-Archive.zip / unarj32.lzh / decode.c < prev    next >
C/C++ Source or Header  |  1993-06-04  |  12KB  |  537 lines
  1. /* DECODE.C, UNARJ, R JUNG, 02/17/93
  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 ARJ archivers
  6.  *   (both compress and extract ARJ archives).
  7.  *
  8.  *   If you wish to distribute a modified version of this program, you
  9.  *   MUST indicate that it is a modified version both in the program and
  10.  *   source code.
  11.  *
  12.  *   If you modify this program, I would appreciate a copy of the new
  13.  *   source code.  I am holding the copyright on the source code, so
  14.  *   please do not delete my name from the program files or from the
  15.  *   documentation.
  16.  *
  17.  * Modification history:
  18.  * Date      Programmer  Description of modification.
  19.  * 04/05/91  R. Jung     Rewrote code.
  20.  * 04/23/91  M. Adler    Portabilized.
  21.  * 04/29/91  R. Jung     Made GETBIT independent of short size.
  22.  * 05/04/91  R. Jung     Simplified use of start[len].
  23.  * 08/28/91  R. Jung     Added KEEP_WINDOW for systems with low memory.
  24.  * 02/17/93  R. Jung     Added extra test for bad data to make_table().
  25.  *                       Added PTABLESIZE defines.
  26.  *
  27.  */
  28.  
  29. #include "unarj.h"
  30.  
  31. #ifdef MODERN
  32. #include <stdlib.h>
  33. #else /* !MODERN */
  34. extern void free();
  35. #endif /* ?MODERN */
  36.  
  37. #define THRESHOLD    3
  38. #define DDICSIZ      26624
  39. #define MAXDICBIT   16
  40. #define MATCHBIT     8
  41. #define MAXMATCH   256
  42. #define NC          (UCHAR_MAX + MAXMATCH + 2 - THRESHOLD)
  43. #define NP          (MAXDICBIT + 1)
  44. #define CBIT         9
  45. #define NT          (CODE_BIT + 3)
  46. #define PBIT         5
  47. #define TBIT         5
  48.  
  49. #if NT > NP
  50. #define NPT NT
  51. #else
  52. #define NPT NP
  53. #endif
  54.  
  55. #define CTABLESIZE  4096
  56. #define PTABLESIZE   256
  57.  
  58. #define STRTP          9
  59. #define STOPP         13
  60.  
  61. #define STRTL          0
  62. #define STOPL          7
  63.  
  64. /* Local functions */
  65.  
  66. #ifdef MODERN
  67. static void   make_table(int nchar, uchar *bitlen, int tablebits, ushort *table, int tablesize);
  68. static void   read_pt_len(int nn, int nbit, int i_special);
  69. static void   read_c_len(void);
  70. static ushort decode_c(void);
  71. static ushort decode_p(void);
  72. static void   decode_start(void);
  73. static short  decode_ptr(void);
  74. static short  decode_len(void);
  75. #endif /* MODERN */
  76.  
  77. /* Local variables */
  78.  
  79. static uchar  *text = NULL;
  80.  
  81. static short  getlen;
  82. static short  getbuf;
  83.  
  84. static ushort left[2 * NC - 1];
  85. static ushort right[2 * NC - 1];
  86. static uchar  c_len[NC];
  87. static uchar  pt_len[NPT];
  88.  
  89. static ushort c_table[CTABLESIZE];
  90. static ushort pt_table[PTABLESIZE];
  91. static ushort blocksize;
  92.  
  93. /* Huffman decode routines */
  94.  
  95. static void
  96. make_table(nchar, bitlen, tablebits, table, tablesize)
  97. int    nchar;
  98. uchar  *bitlen;
  99. int    tablebits;
  100. ushort *table;
  101. int    tablesize;
  102. {
  103.     ushort count[17], weight[17], start[18], *p;
  104.     uint i, k, len, ch, jutbits, avail, nextcode, mask;
  105.  
  106.     for (i = 1; i <= 16; i++)
  107.         count[i] = 0;
  108.     for (i = 0; (int)i < nchar; i++)
  109.         count[bitlen[i]]++;
  110.  
  111.     start[1] = 0;
  112.     for (i = 1; i <= 16; i++)
  113.         start[i + 1] = start[i] + (count[i] << (16 - i));
  114.     if (start[17] != (ushort) (1 << 16))
  115.         error(M_BADTABLE, "");
  116.  
  117.     jutbits = 16 - tablebits;
  118.     for (i = 1; (int)i <= tablebits; i++)
  119.     {
  120.         start[i] >>= jutbits;
  121.         weight[i] = 1 << (tablebits - i);
  122.     }
  123.     while (i <= 16)
  124.     {
  125.         weight[i] = 1 << (16 - i);
  126.         i++;
  127.     }
  128.  
  129.     i = start[tablebits + 1] >> jutbits;
  130.     if (i != (ushort) (1 << 16))
  131.     {
  132.         k = 1 << tablebits;
  133.         while (i != k)
  134.             table[i++] = 0;
  135.     }
  136.  
  137.     avail = nchar;
  138.     mask = 1 << (15 - tablebits);
  139.     for (ch = 0; (int)ch < nchar; ch++)
  140.     {
  141.         if ((len = bitlen[ch]) == 0)
  142.             continue;
  143.         k = start[len];
  144.         nextcode = k + weight[len];
  145.         if ((int)len <= tablebits)
  146.         {
  147.             if (nextcode > (uint)tablesize)
  148.                 error(M_BADTABLE, "");
  149.             for (i = start[len]; i < nextcode; i++)
  150.                 table[i] = ch;
  151.         }
  152.         else
  153.         {
  154.             p = &table[k >> jutbits];
  155.             i = len - tablebits;
  156.             while (i != 0)
  157.             {
  158.                 if (*p == 0)
  159.                 {
  160.                     right[avail] = left[avail] = 0;
  161.                     *p = avail++;
  162.                 }
  163.                 if (k & mask)
  164.                     p = &right[*p];
  165.                 else
  166.                     p = &left[*p];
  167.                 k <<= 1;
  168.                 i--;
  169.             }
  170.             *p = ch;
  171.         }
  172.         start[len] = nextcode;
  173.     }
  174. }
  175.  
  176. static void
  177. read_pt_len(nn, nbit, i_special)
  178. int nn;
  179. int nbit;
  180. int i_special;
  181. {
  182.     int i, n;
  183.     short c;
  184.     ushort mask;
  185.  
  186.     n = getbits(nbit);
  187.     if (n == 0)
  188.     {
  189.         c = getbits(nbit);
  190.         for (i = 0; i < nn; i++)
  191.             pt_len[i] = 0;
  192.         for (i = 0; i < 256; i++)
  193.             pt_table[i] = c;
  194.     }
  195.     else
  196.     {
  197.         i = 0;
  198.         while (i < n)
  199.         {
  200.             c = bitbuf >> (13);
  201.             if (c == 7)
  202.             {
  203.                 mask = 1 << (12);
  204.                 while (mask & bitbuf)
  205.                 {
  206.                     mask >>= 1;
  207.                     c++;
  208.                 }
  209.             }
  210.             fillbuf((c < 7) ? 3 : (int)(c - 3));
  211.             pt_len[i++] = (uchar)c;
  212.             if (i == i_special)
  213.             {
  214.                 c = getbits(2);
  215.                 while (--c >= 0)
  216.                     pt_len[i++] = 0;
  217.             }
  218.         }
  219.         while (i < nn)
  220.             pt_len[i++] = 0;
  221.         make_table(nn, pt_len, 8, pt_table, sizeof(pt_table));
  222.     }
  223. }
  224.  
  225. static void
  226. read_c_len()
  227. {
  228.     short i, c, n;
  229.     ushort mask;
  230.  
  231.     n = getbits(CBIT);
  232.     if (n == 0)
  233.     {
  234.         c = getbits(CBIT);
  235.         for (i = 0; i < NC; i++)
  236.             c_len[i] = 0;
  237.         for (i = 0; i < CTABLESIZE; i++)
  238.             c_table[i] = c;
  239.     }
  240.     else
  241.     {
  242.         i = 0;
  243.         while (i < n)
  244.         {
  245.             c = pt_table[bitbuf >> (8)];
  246.             if (c >= NT)
  247.             {
  248.                 mask = 1 << (7);
  249.                 do
  250.                 {
  251.                     if (bitbuf & mask)
  252.                         c = right[c];
  253.                     else
  254.                         c = left[c];
  255.                     mask >>= 1;
  256.                 } while (c >= NT);
  257.             }
  258.             fillbuf((int)(pt_len[c]));
  259.             if (c <= 2)
  260.             {
  261.                 if (c == 0)
  262.                     c = 1;
  263.                 else if (c == 1)
  264.                     c = getbits(4) + 3;
  265.                 else
  266.                     c = getbits(CBIT) + 20;
  267.                 while (--c >= 0)
  268.                     c_len[i++] = 0;
  269.             }
  270.             else
  271.                 c_len[i++] = (uchar)(c - 2);
  272.         }
  273.         while (i < NC)
  274.             c_len[i++] = 0;
  275.         make_table(NC, c_len, 12, c_table, sizeof(c_table));
  276.     }
  277. }
  278.  
  279. static ushort
  280. decode_c()
  281. {
  282.     ushort j, mask;
  283.  
  284.     if (blocksize == 0)
  285.     {
  286.         blocksize = getbits(16);
  287.         read_pt_len(NT, TBIT, 3);
  288.         read_c_len();
  289.         read_pt_len(NP, PBIT, -1);
  290.     }
  291.     blocksize--;
  292.     j = c_table[bitbuf >> 4];
  293.     if (j >= NC)
  294.     {
  295.         mask = 1 << (3);
  296.         do
  297.         {
  298.             if (bitbuf & mask)
  299.                 j = right[j];
  300.             else
  301.                 j = left[j];
  302.             mask >>= 1;
  303.         } while (j >= NC);
  304.     }
  305.     fillbuf((int)(c_len[j]));
  306.     return j;
  307. }
  308.  
  309. static ushort
  310. decode_p()
  311. {
  312.     ushort j, mask;
  313.  
  314.     j = pt_table[bitbuf >> (8)];
  315.     if (j >= NP)
  316.     {
  317.         mask = 1 << (7);
  318.         do
  319.         {
  320.             if (bitbuf & mask)
  321.                 j = right[j];
  322.             else
  323.                 j = left[j];
  324.             mask >>= 1;
  325.         } while (j >= NP);
  326.     }
  327.     fillbuf((int)(pt_len[j]));
  328.     if (j != 0)
  329.     {
  330.         j--;
  331.         j = (1 << j) + getbits((int)j);
  332.     }
  333.     return j;
  334. }
  335.  
  336. static void
  337. decode_start()
  338. {
  339.     blocksize = 0;
  340.     init_getbits();
  341. }
  342.  
  343. void
  344. decode()
  345. {
  346.     short i;
  347.     short j;
  348.     short c;
  349.     short r;
  350.     long count;
  351.  
  352. #ifdef KEEP_WINDOW
  353.     if (text == (uchar *) NULL)
  354.         text = (uchar *)malloc_msg(DDICSIZ);
  355. #else
  356.     text = (uchar *)malloc_msg(DDICSIZ);
  357. #endif
  358.  
  359.     disp_clock();
  360.     decode_start();
  361.     count = 0;
  362.     r = 0;
  363.  
  364.     while (count < origsize)
  365.     {
  366.         if ((c = decode_c()) <= UCHAR_MAX)
  367.         {
  368.             text[r] = (uchar) c;
  369.             count++;
  370.             if (++r >= DDICSIZ)
  371.             {
  372.                 r = 0;
  373.                 disp_clock();
  374.                 fwrite_txt_crc(text, DDICSIZ);
  375.             }
  376.         }
  377.         else
  378.         {
  379.             j = c - (UCHAR_MAX + 1 - THRESHOLD);
  380.             count += j;
  381.             i = decode_p();
  382.             if ((i = r - i - 1) < 0)
  383.                 i += DDICSIZ;
  384.             if (r > i && r < DDICSIZ - MAXMATCH - 1)
  385.             {
  386.                 while (--j >= 0)
  387.                     text[r++] = text[i++];
  388.             }
  389.             else
  390.             {
  391.                 while (--j >= 0)
  392.                 {
  393.                     text[r] = text[i];
  394.                     if (++r >= DDICSIZ)
  395.                     {
  396.                         r = 0;
  397.                         disp_clock();
  398.                         fwrite_txt_crc(text, DDICSIZ);
  399.                     }
  400.                     if (++i >= DDICSIZ)
  401.                         i = 0;
  402.                 }
  403.             }
  404.         }
  405.     }
  406.     if (r != 0)
  407.         fwrite_txt_crc(text, r);
  408.  
  409. #ifndef KEEP_WINDOW
  410.     free((char *)text);
  411. #endif
  412. }
  413.  
  414. /* Macros */
  415.  
  416. #define BFIL {getbuf|=bitbuf>>getlen;fillbuf(CODE_BIT-getlen);getlen=CODE_BIT;}
  417. #define GETBIT(c) {if(getlen<=0)BFIL c=(getbuf&0x8000)!=0;getbuf<<=1;getlen--;}
  418. #define BPUL(l) {getbuf<<=l;getlen-=l;}
  419. #define GETBITS(c,l) {if(getlen<l)BFIL c=(ushort)getbuf>>(CODE_BIT-l);BPUL(l)}
  420.  
  421. static short
  422. decode_ptr()
  423. {
  424.     short c;
  425.     short width;
  426.     short plus;
  427.     short pwr;
  428.  
  429.     plus = 0;
  430.     pwr = 1 << (STRTP);
  431.     for (width = (STRTP); width < (STOPP) ; width++)
  432.     {
  433.         GETBIT(c);
  434.         if (c == 0)
  435.             break;
  436.         plus += pwr;
  437.         pwr <<= 1;
  438.     }
  439.     if (width != 0)
  440.         GETBITS(c, width);
  441.     c += plus;
  442.     return c;
  443. }
  444.  
  445. static short
  446. decode_len()
  447. {
  448.     short c;
  449.     short width;
  450.     short plus;
  451.     short pwr;
  452.  
  453.     plus = 0;
  454.     pwr = 1 << (STRTL);
  455.     for (width = (STRTL); width < (STOPL) ; width++)
  456.     {
  457.         GETBIT(c);
  458.         if (c == 0)
  459.             break;
  460.         plus += pwr;
  461.         pwr <<= 1;
  462.     }
  463.     if (width != 0)
  464.         GETBITS(c, width);
  465.     c += plus;
  466.     return c;
  467. }
  468.  
  469. void
  470. decode_f()
  471. {
  472.     short i;
  473.     short j;
  474.     short c;
  475.     short r;
  476.     short pos;
  477.     long count;
  478.  
  479. #ifdef KEEP_WINDOW
  480.     if (text == (uchar *) NULL)
  481.         text = (uchar *)malloc_msg(DDICSIZ);
  482. #else
  483.     text = (uchar *)malloc_msg(DDICSIZ);
  484. #endif
  485.  
  486.     disp_clock();
  487.     init_getbits();
  488.     getlen = getbuf = 0;
  489.     count = 0;
  490.     r = 0;
  491.  
  492.     while (count < origsize)
  493.     {
  494.         c = decode_len();
  495.         if (c == 0)
  496.         {
  497.             GETBITS(c, CHAR_BIT);
  498.             text[r] = (uchar)c;
  499.             count++;
  500.             if (++r >= DDICSIZ)
  501.             {
  502.                 r = 0;
  503.                 disp_clock();
  504.                 fwrite_txt_crc(text, DDICSIZ);
  505.             }
  506.         }
  507.         else
  508.         {
  509.             j = c - 1 + THRESHOLD;
  510.             count += j;
  511.             pos = decode_ptr();
  512.             if ((i = r - pos - 1) < 0)
  513.                 i += DDICSIZ;
  514.             while (j-- > 0)
  515.             {
  516.                 text[r] = text[i];
  517.                 if (++r >= DDICSIZ)
  518.                 {
  519.                     r = 0;
  520.                     disp_clock();
  521.                     fwrite_txt_crc(text, DDICSIZ);
  522.                 }
  523.                 if (++i >= DDICSIZ)
  524.                     i = 0;
  525.             }
  526.         }
  527.     }
  528.     if (r != 0)
  529.         fwrite_txt_crc(text, r);
  530.  
  531. #ifndef KEEP_WINDOW
  532.     free((char *)text);
  533. #endif
  534. }
  535.  
  536. /* end DECODE.C */
  537.