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