"Fossies" - the Fresh Open Source Software Archive

Member "src/Boot/Windows/Decompressor.c" (10 Oct 2018, 16995 Bytes) of package /windows/misc/VeraCrypt_1.23-Hotfix-2_Source.zip:


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 "Decompressor.c" see the Fossies "Dox" file reference documentation.

    1 /*
    2   puff.c
    3   Copyright (C) 2002-2004 Mark Adler, all rights reserved
    4   version 1.8, 9 Jan 2004
    5 
    6   This software is provided 'as-is', without any express or implied
    7   warranty.  In no event will the author be held liable for any damages
    8   arising from the use of this software.
    9 
   10   Permission is granted to anyone to use this software for any purpose,
   11   including commercial applications, and to alter it and redistribute it
   12   freely, subject to the following restrictions:
   13 
   14   1. The origin of this software must not be misrepresented; you must not
   15      claim that you wrote the original software. If you use this software
   16      in a product, an acknowledgment in the product documentation would be
   17      appreciated but is not required.
   18   2. Altered source versions must be plainly marked as such, and must not be
   19      misrepresented as being the original software.
   20   3. This notice may not be removed or altered from any source distribution.
   21 
   22   Mark Adler    madler@alumni.caltech.edu
   23 */
   24 
   25 /* Adapted for TrueCrypt */
   26 /* Adapted for VeraCrypt */
   27 
   28 
   29 #define local static            /* for local function definitions */
   30 #define NIL ((unsigned char *)0)        /* for no output option */
   31 
   32 /*
   33  * Maximums for allocations and loops.  It is not useful to change these --
   34  * they are fixed by the deflate format.
   35  */
   36 #define MAXBITS 15              /* maximum bits in a code */
   37 #define MAXLCODES 286           /* maximum number of literal/length codes */
   38 #define MAXDCODES 30            /* maximum number of distance codes */
   39 #define MAXCODES (MAXLCODES+MAXDCODES)  /* maximum codes lengths to read */
   40 #define FIXLCODES 288           /* number of fixed literal/length codes */
   41 
   42 /* input and output state */
   43 struct state {
   44     /* output state */
   45     unsigned char *out;         /* output buffer */
   46     unsigned int outlen;       /* available space at out */
   47     unsigned int outcnt;       /* bytes written to out so far */
   48 
   49     /* input state */
   50     unsigned char *in;          /* input buffer */
   51     unsigned int inlen;          /* available input at in */
   52     unsigned int incnt;        /* bytes read so far */
   53     int bitbuf;                 /* bit buffer */
   54     int bitcnt;                 /* number of bits in bit buffer */
   55 };
   56 
   57 
   58 local int bits(struct state *s, int need)
   59 {
   60     long val;           /* bit accumulator (can use up to 20 bits) */
   61 
   62     /* load at least need bits into val */
   63     val = s->bitbuf;
   64     while (s->bitcnt < need) {
   65         val |= (long)(s->in[s->incnt++]) << s->bitcnt;  /* load eight bits */
   66         s->bitcnt += 8;
   67     }
   68 
   69     /* drop need bits and update buffer, always zero to seven bits left */
   70     s->bitbuf = (int)(val >> need);
   71     s->bitcnt -= need;
   72 
   73     /* return need bits, zeroing the bits above that */
   74     return (int)(val & ((1L << need) - 1));
   75 }
   76 
   77 
   78 local int stored(struct state *s)
   79 {
   80     unsigned len;       /* length of stored block */
   81 
   82     /* discard leftover bits from current byte (assumes s->bitcnt < 8) */
   83     s->bitbuf = 0;
   84     s->bitcnt = 0;
   85 
   86     if (s->incnt + 4 > s->inlen)
   87         return 2;                               /* not enough input */
   88 
   89     /* get length and check against its one's complement */
   90     len = s->in[s->incnt++];
   91     len |= s->in[s->incnt++] << 8;
   92     if (s->in[s->incnt++] != (~len & 0xff) ||
   93         s->in[s->incnt++] != ((~len >> 8) & 0xff))
   94         return -2;                              /* didn't match complement! */
   95 
   96     if (s->incnt + len > s->inlen)
   97         return 2;                               /* not enough input */
   98 
   99     /* copy len bytes from in to out */
  100     if (s->out != NIL) {
  101         if (s->outcnt + len > s->outlen)
  102             return 1;                           /* not enough output space */
  103         while (len--)
  104             s->out[s->outcnt++] = s->in[s->incnt++];
  105     }
  106     else {                                      /* just scanning */
  107         s->outcnt += len;
  108         s->incnt += len;
  109     }
  110 
  111     /* done with a valid stored block */
  112     return 0;
  113 }
  114 
  115 
  116 struct huffman {
  117     short *count;       /* number of symbols of each length */
  118     short *symbol;      /* canonically ordered symbols */
  119 };
  120 
  121 /* reduce code size by using slow version of the decompressor */
  122 #define SLOW
  123 
  124 #ifdef SLOW
  125 local int decode(struct state *s, struct huffman *h)
  126 {
  127     int len;            /* current number of bits in code */
  128     int code;           /* len bits being decoded */
  129     int first;          /* first code of length len */
  130     int count;          /* number of codes of length len */
  131     int index;          /* index of first code of length len in symbol table */
  132 
  133     code = first = index = 0;
  134     for (len = 1; len <= MAXBITS; len++) {
  135         code |= bits(s, 1);             /* get next bit */
  136         count = h->count[len];
  137         if (code < first + count)       /* if length len, return symbol */
  138             return h->symbol[index + (code - first)];
  139         index += count;                 /* else update for next length */
  140         first += count;
  141         first <<= 1;
  142         code <<= 1;
  143     }
  144     return -9;                          /* ran out of codes */
  145 }
  146 
  147 /*
  148  * A faster version of decode() for real applications of this code.   It's not
  149  * as readable, but it makes puff() twice as fast.  And it only makes the code
  150  * a few percent larger.
  151  */
  152 #else /* !SLOW */
  153 local int decode(struct state *s, struct huffman *h)
  154 {
  155     int len;            /* current number of bits in code */
  156     int code;           /* len bits being decoded */
  157     int first;          /* first code of length len */
  158     int count;          /* number of codes of length len */
  159     int index;          /* index of first code of length len in symbol table */
  160     int bitbuf;         /* bits from stream */
  161     int left;           /* bits left in next or left to process */
  162     short *next;        /* next number of codes */
  163 
  164     bitbuf = s->bitbuf;
  165     left = s->bitcnt;
  166     code = first = index = 0;
  167     len = 1;
  168     next = h->count + 1;
  169     while (1) {
  170         while (left--) {
  171             code |= bitbuf & 1;
  172             bitbuf >>= 1;
  173             count = *next++;
  174             if (code < first + count) { /* if length len, return symbol */
  175                 s->bitbuf = bitbuf;
  176                 s->bitcnt = (s->bitcnt - len) & 7;
  177                 return h->symbol[index + (code - first)];
  178             }
  179             index += count;             /* else update for next length */
  180             first += count;
  181             first <<= 1;
  182             code <<= 1;
  183             len++;
  184         }
  185         left = (MAXBITS+1) - len;
  186         if (left == 0) break;
  187         bitbuf = s->in[s->incnt++];
  188         if (left > 8) left = 8;
  189     }
  190     return -9;                          /* ran out of codes */
  191 }
  192 #endif /* SLOW */
  193 
  194 
  195 local int construct(struct huffman *h, short *length, int n)
  196 {
  197     int symbol;         /* current symbol when stepping through length[] */
  198     int len;            /* current length when stepping through h->count[] */
  199     int left;           /* number of possible codes left of current length */
  200     short offs[MAXBITS+1];      /* offsets in symbol table for each length */
  201 
  202     /* count number of codes of each length */
  203     for (len = 0; len <= MAXBITS; len++)
  204         h->count[len] = 0;
  205     for (symbol = 0; symbol < n; symbol++)
  206         (h->count[length[symbol]])++;   /* assumes lengths are within bounds */
  207     if (h->count[0] == n)               /* no codes! */
  208         return 0;                       /* complete, but decode() will fail */
  209 
  210     /* check for an over-subscribed or incomplete set of lengths */
  211     left = 1;                           /* one possible code of zero length */
  212     for (len = 1; len <= MAXBITS; len++) {
  213         left <<= 1;                     /* one more bit, double codes left */
  214         left -= h->count[len];          /* deduct count from possible codes */
  215         if (left < 0) return left;      /* over-subscribed--return negative */
  216     }                                   /* left > 0 means incomplete */
  217 
  218     /* generate offsets into symbol table for each length for sorting */
  219     offs[1] = 0;
  220     for (len = 1; len < MAXBITS; len++)
  221         offs[len + 1] = offs[len] + h->count[len];
  222 
  223     /*
  224      * put symbols in table sorted by length, by symbol order within each
  225      * length
  226      */
  227     for (symbol = 0; symbol < n; symbol++)
  228         if (length[symbol] != 0)
  229             h->symbol[offs[length[symbol]]++] = symbol;
  230 
  231     /* return zero for complete set, positive for incomplete set */
  232     return left;
  233 }
  234 
  235 
  236 local int codes(struct state *s,
  237                 struct huffman *lencode,
  238                 struct huffman *distcode)
  239 {
  240     int symbol;         /* decoded symbol */
  241     int len;            /* length for copy */
  242     unsigned dist;      /* distance for copy */
  243     static const short lens[29] = { /* Size base for length codes 257..285 */
  244         3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
  245         35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258};
  246     static const short lext[29] = { /* Extra bits for length codes 257..285 */
  247         0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
  248         3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0};
  249     static const short dists[30] = { /* Offset base for distance codes 0..29 */
  250         1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
  251         257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
  252         8193, 12289, 16385, 24577};
  253     static const short dext[30] = { /* Extra bits for distance codes 0..29 */
  254         0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
  255         7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
  256         12, 12, 13, 13};
  257 
  258     /* decode literals and length/distance pairs */
  259     do {
  260         symbol = decode(s, lencode);
  261         if (symbol < 0) return symbol;  /* invalid symbol */
  262         if (symbol < 256) {             /* literal: symbol is the byte */
  263             /* write out the literal */
  264             if (s->out != NIL) {
  265                 if (s->outcnt == s->outlen) return 1;
  266                 s->out[s->outcnt] = symbol;
  267             }
  268             s->outcnt++;
  269         }
  270         else if (symbol > 256) {        /* length */
  271             /* get and compute length */
  272             symbol -= 257;
  273             if (symbol >= 29) return -9;        /* invalid fixed code */
  274             len = lens[symbol] + bits(s, lext[symbol]);
  275 
  276             /* get and check distance */
  277             symbol = decode(s, distcode);
  278             if (symbol < 0) return symbol;          /* invalid symbol */
  279             dist = dists[symbol] + bits(s, dext[symbol]);
  280             if (dist > s->outcnt)
  281                 return -10;     /* distance too far back */
  282 
  283             /* copy length bytes from distance bytes back */
  284             if (s->out != NIL) {
  285                 if (s->outcnt + len > s->outlen) return 1;
  286                 while (len--) {
  287                     s->out[s->outcnt] = s->out[s->outcnt - dist];
  288                     s->outcnt++;
  289                 }
  290             }
  291             else
  292                 s->outcnt += len;
  293         }
  294     } while (symbol != 256);            /* end of block symbol */
  295 
  296     /* done with a valid fixed or dynamic block */
  297     return 0;
  298 }
  299 
  300 
  301 local int fixed(struct state *s)
  302 {
  303     static int virgin = 1;
  304     static short lencnt[MAXBITS+1], lensym[FIXLCODES];
  305     static short distcnt[MAXBITS+1], distsym[MAXDCODES];
  306     static struct huffman lencode = {lencnt, lensym};
  307     static struct huffman distcode = {distcnt, distsym};
  308 
  309     /* build fixed huffman tables if first call (may not be thread safe) */
  310     if (virgin) {
  311         int symbol;
  312         short lengths[FIXLCODES];
  313 
  314         /* literal/length table */
  315         for (symbol = 0; symbol < 144; symbol++)
  316             lengths[symbol] = 8;
  317         for (; symbol < 256; symbol++)
  318             lengths[symbol] = 9;
  319         for (; symbol < 280; symbol++)
  320             lengths[symbol] = 7;
  321         for (; symbol < FIXLCODES; symbol++)
  322             lengths[symbol] = 8;
  323         construct(&lencode, lengths, FIXLCODES);
  324 
  325         /* distance table */
  326         for (symbol = 0; symbol < MAXDCODES; symbol++)
  327             lengths[symbol] = 5;
  328         construct(&distcode, lengths, MAXDCODES);
  329 
  330         /* do this just once */
  331         virgin = 0;
  332     }
  333 
  334     /* decode data until end-of-block code */
  335     return codes(s, &lencode, &distcode);
  336 }
  337 
  338 
  339 local int dynamic(struct state *s)
  340 {
  341     int nlen, ndist, ncode;             /* number of lengths in descriptor */
  342     int index;                          /* index of lengths[] */
  343     int err;                            /* construct() return value */
  344     short lengths[MAXCODES];            /* descriptor code lengths */
  345     short lencnt[MAXBITS+1], lensym[MAXLCODES];         /* lencode memory */
  346     short distcnt[MAXBITS+1], distsym[MAXDCODES];       /* distcode memory */
  347     struct huffman lencode = {lencnt, lensym};          /* length code */
  348     struct huffman distcode = {distcnt, distsym};       /* distance code */
  349     static const short order[19] =      /* permutation of code length codes */
  350         {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
  351 
  352     /* get number of lengths in each table, check lengths */
  353     nlen = bits(s, 5) + 257;
  354     ndist = bits(s, 5) + 1;
  355     ncode = bits(s, 4) + 4;
  356     if (nlen > MAXLCODES || ndist > MAXDCODES)
  357         return -3;                      /* bad counts */
  358 
  359     /* read code length code lengths (really), missing lengths are zero */
  360     for (index = 0; index < ncode; index++)
  361         lengths[order[index]] = bits(s, 3);
  362     for (; index < 19; index++)
  363         lengths[order[index]] = 0;
  364 
  365     /* build huffman table for code lengths codes (use lencode temporarily) */
  366     err = construct(&lencode, lengths, 19);
  367     if (err != 0) return -4;            /* require complete code set here */
  368 
  369     /* read length/literal and distance code length tables */
  370     index = 0;
  371     while (index < nlen + ndist) {
  372         int symbol;             /* decoded value */
  373         int len;                /* last length to repeat */
  374 
  375         symbol = decode(s, &lencode);
  376         if (symbol < 0)
  377             return symbol;          /* invalid symbol */
  378         if (symbol < 16)                /* length in 0..15 */
  379             lengths[index++] = symbol;
  380         else {                          /* repeat instruction */
  381             len = 0;                    /* assume repeating zeros */
  382             switch(symbol)
  383             {
  384                case 16: {         /* repeat last length 3..6 times */
  385                   if (index == 0) return -5;      /* no last length! */
  386                   len = lengths[index - 1];       /* last length */
  387                   symbol = 3 + bits(s, 2);
  388                   break;
  389                }
  390                case  17:      /* repeat zero 3..10 times */
  391                   symbol = 3 + bits(s, 3);
  392                   break;
  393                default:                  /* == 18, repeat zero 11..138 times */
  394                    symbol = 11 + bits(s, 7);
  395                    break;
  396              }
  397             if ((index + symbol > nlen + ndist))
  398                 return -6;              /* too many lengths! */
  399             while (symbol--)            /* repeat last or zero symbol times */
  400                 lengths[index++] = len;
  401         }
  402     }
  403 
  404     /* check for end-of-block code -- there better be one! */
  405     if (lengths[256] == 0)
  406         return -9;
  407 
  408     /* build huffman table for literal/length codes */
  409     err = construct(&lencode, lengths, nlen);
  410     if (err < 0 || (err > 0 && nlen - lencode.count[0] != 1))
  411         return -7;      /* only allow incomplete codes if just one code */
  412 
  413     /* build huffman table for distance codes */
  414     err = construct(&distcode, lengths + nlen, ndist);
  415     if (err < 0 || (err > 0 && ndist - distcode.count[0] != 1))
  416         return -8;      /* only allow incomplete codes if just one code */
  417 
  418     /* decode data until end-of-block code */
  419     return codes(s, &lencode, &distcode);
  420 }
  421 
  422 
  423 void _acrtused () { }
  424 
  425 // Decompress deflated data
  426 int far main (
  427          unsigned char *dest,         /* pointer to destination pointer */
  428          unsigned int destlen,        /* amount of output space */
  429          unsigned char *source,       /* pointer to source data pointer */
  430          unsigned int sourcelen)
  431 {
  432     struct state s;             /* input/output state */
  433     int last, type;             /* block information */
  434     int err;                    /* return value */
  435 
  436     /* initialize output state */
  437     s.out = dest;
  438     s.outlen = destlen;                /* ignored if dest is NIL */
  439     s.outcnt = 0;
  440 
  441     /* initialize input state */
  442     s.in = source;
  443     s.inlen = sourcelen;
  444     s.incnt = 0;
  445     s.bitbuf = 0;
  446     s.bitcnt = 0;
  447 
  448     /* process blocks until last block or error */
  449     do {
  450         last = bits(&s, 1);         /* one if last block */
  451         type = bits(&s, 2);         /* block type 0..3 */
  452         switch(type)
  453         {
  454         case 0:
  455             err = stored(&s);
  456             break;
  457         case 1:
  458             err = fixed(&s);
  459             break;
  460         case 2:
  461             err = dynamic(&s);
  462             break;
  463         default:
  464             err = -1; /* type == 3, invalid */
  465             break;
  466         }
  467 
  468         if (err != 0) break;        /* return with error */
  469     } while (!last);
  470 
  471     return err;
  472 }