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