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