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