Return to decompressor.c CVS log

Up to [truecrypt] / truecrypt / boot / windows

Annotation of truecrypt/boot/windows/decompressor.c, revision 1.1

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

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.