"Fossies" - the Fresh Open Source Software Archive

Member "unarj-2.65/decode.c" (5 Jun 2002, 11903 Bytes) of package /linux/misc/old/unarj-2.65.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "decode.c" see the Fossies "Dox" file reference documentation.

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