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