123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955 |
- #include <setjmp.h> /* for setjmp(), longjmp(), and jmp_buf */
- #include "puff.h"
- #define local static
- #define NIL ((unsigned char *)0)
- #define MAXBITS 15
- #define MAXLCODES 286
- #define MAXDCODES 30
- #define MAXCODES (MAXLCODES+MAXDCODES)
- #define FIXLCODES 288
- struct state {
-
- unsigned char *out;
- unsigned long outlen;
- unsigned long outcnt;
-
- unsigned char *in;
- unsigned long inlen;
- unsigned long incnt;
- int bitbuf;
- int bitcnt;
-
- jmp_buf env;
- };
- local int bits(struct state *s, int need)
- {
- long val;
-
- val = s->bitbuf;
- while (s->bitcnt < need) {
- if (s->incnt == s->inlen) longjmp(s->env, 1);
- val |= (long)(s->in[s->incnt++]) << s->bitcnt;
- s->bitcnt += 8;
- }
-
- s->bitbuf = (int)(val >> need);
- s->bitcnt -= need;
-
- return (int)(val & ((1L << need) - 1));
- }
- local int stored(struct state *s)
- {
- unsigned len;
-
- s->bitbuf = 0;
- s->bitcnt = 0;
-
- if (s->incnt + 4 > s->inlen) return 2;
- len = s->in[s->incnt++];
- len |= s->in[s->incnt++] << 8;
- if (s->in[s->incnt++] != (~len & 0xff) ||
- s->in[s->incnt++] != ((~len >> 8) & 0xff))
- return -2;
-
- if (s->incnt + len > s->inlen) return 2;
- if (s->out != NIL) {
- if (s->outcnt + len > s->outlen)
- return 1;
- while (len--)
- s->out[s->outcnt++] = s->in[s->incnt++];
- }
- else {
- s->outcnt += len;
- s->incnt += len;
- }
-
- return 0;
- }
- struct huffman {
- short *count;
- short *symbol;
- };
- #ifdef SLOW
- local int decode(struct state *s, struct huffman *h)
- {
- int len;
- int code;
- int first;
- int count;
- int index;
- code = first = index = 0;
- for (len = 1; len <= MAXBITS; len++) {
- code |= bits(s, 1);
- count = h->count[len];
- if (code - count < first)
- return h->symbol[index + (code - first)];
- index += count;
- first += count;
- first <<= 1;
- code <<= 1;
- }
- return -10;
- }
- #else
- local int decode(struct state *s, struct huffman *h)
- {
- int len;
- int code;
- int first;
- int count;
- int index;
- int bitbuf;
- int left;
- short *next;
- bitbuf = s->bitbuf;
- left = s->bitcnt;
- code = first = index = 0;
- len = 1;
- next = h->count + 1;
- while (1) {
- while (left--) {
- code |= bitbuf & 1;
- bitbuf >>= 1;
- count = *next++;
- if (code - count < first) {
- s->bitbuf = bitbuf;
- s->bitcnt = (s->bitcnt - len) & 7;
- return h->symbol[index + (code - first)];
- }
- index += count;
- first += count;
- first <<= 1;
- code <<= 1;
- len++;
- }
- left = (MAXBITS+1) - len;
- if (left == 0) break;
- if (s->incnt == s->inlen) longjmp(s->env, 1);
- bitbuf = s->in[s->incnt++];
- if (left > 8) left = 8;
- }
- return -10;
- }
- #endif
- local int construct(struct huffman *h, short *length, int n)
- {
- int symbol;
- int len;
- int left;
- short offs[MAXBITS+1];
-
- for (len = 0; len <= MAXBITS; len++)
- h->count[len] = 0;
- for (symbol = 0; symbol < n; symbol++)
- (h->count[length[symbol]])++;
- if (h->count[0] == n)
- return 0;
-
- left = 1;
- for (len = 1; len <= MAXBITS; len++) {
- left <<= 1;
- left -= h->count[len];
- if (left < 0) return left;
- }
-
- offs[1] = 0;
- for (len = 1; len < MAXBITS; len++)
- offs[len + 1] = offs[len] + h->count[len];
-
- for (symbol = 0; symbol < n; symbol++)
- if (length[symbol] != 0)
- h->symbol[offs[length[symbol]]++] = symbol;
-
- return left;
- }
- local int codes(struct state *s,
- struct huffman *lencode,
- struct huffman *distcode)
- {
- int symbol;
- int len;
- unsigned dist;
- static const short lens[29] = {
- 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
- 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258};
- static const short lext[29] = {
- 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
- 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0};
- static const short dists[30] = {
- 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
- 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
- 8193, 12289, 16385, 24577};
- static const short dext[30] = {
- 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
- 7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
- 12, 12, 13, 13};
-
- do {
- symbol = decode(s, lencode);
- if (symbol < 0) return symbol;
- if (symbol < 256) {
-
- if (s->out != NIL) {
- if (s->outcnt == s->outlen) return 1;
- s->out[s->outcnt] = symbol;
- }
- s->outcnt++;
- }
- else if (symbol > 256) {
-
- symbol -= 257;
- if (symbol >= 29) return -10;
- len = lens[symbol] + bits(s, lext[symbol]);
-
- symbol = decode(s, distcode);
- if (symbol < 0) return symbol;
- dist = dists[symbol] + bits(s, dext[symbol]);
- #ifndef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
- if (dist > s->outcnt)
- return -11;
- #endif
-
- if (s->out != NIL) {
- if (s->outcnt + len > s->outlen) return 1;
- while (len--) {
- s->out[s->outcnt] =
- #ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
- dist > s->outcnt ? 0 :
- #endif
- s->out[s->outcnt - dist];
- s->outcnt++;
- }
- }
- else
- s->outcnt += len;
- }
- } while (symbol != 256);
-
- return 0;
- }
- local int fixed(struct state *s)
- {
- static int virgin = 1;
- static short lencnt[MAXBITS+1], lensym[FIXLCODES];
- static short distcnt[MAXBITS+1], distsym[MAXDCODES];
- static struct huffman lencode, distcode;
-
- if (virgin) {
- int symbol;
- short lengths[FIXLCODES];
-
- for (symbol = 0; symbol < 144; symbol++)
- lengths[symbol] = 8;
- for (; symbol < 256; symbol++)
- lengths[symbol] = 9;
- for (; symbol < 280; symbol++)
- lengths[symbol] = 7;
- for (; symbol < FIXLCODES; symbol++)
- lengths[symbol] = 8;
- construct(&lencode, lengths, FIXLCODES);
-
- for (symbol = 0; symbol < MAXDCODES; symbol++)
- lengths[symbol] = 5;
- construct(&distcode, lengths, MAXDCODES);
-
- lencode.count = lencnt;
- lencode.symbol = lensym;
- distcode.count = distcnt;
- distcode.symbol = distsym;
-
- virgin = 0;
- }
-
- return codes(s, &lencode, &distcode);
- }
- local int dynamic(struct state *s)
- {
- int nlen, ndist, ncode;
- int index;
- int err;
- short lengths[MAXCODES];
- short lencnt[MAXBITS+1], lensym[MAXLCODES];
- short distcnt[MAXBITS+1], distsym[MAXDCODES];
- struct huffman lencode, distcode;
- static const short order[19] =
- {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
-
- lencode.count = lencnt;
- lencode.symbol = lensym;
- distcode.count = distcnt;
- distcode.symbol = distsym;
-
- nlen = bits(s, 5) + 257;
- ndist = bits(s, 5) + 1;
- ncode = bits(s, 4) + 4;
- if (nlen > MAXLCODES || ndist > MAXDCODES)
- return -3;
-
- for (index = 0; index < ncode; index++)
- lengths[order[index]] = bits(s, 3);
- for (; index < 19; index++)
- lengths[order[index]] = 0;
-
- err = construct(&lencode, lengths, 19);
- if (err != 0) return -4;
-
- index = 0;
- while (index < nlen + ndist) {
- int symbol;
- int len;
- symbol = decode(s, &lencode);
- if (symbol < 16)
- lengths[index++] = symbol;
- else {
- len = 0;
- if (symbol == 16) {
- if (index == 0) return -5;
- len = lengths[index - 1];
- symbol = 3 + bits(s, 2);
- }
- else if (symbol == 17)
- symbol = 3 + bits(s, 3);
- else
- symbol = 11 + bits(s, 7);
- if (index + symbol > nlen + ndist)
- return -6;
- while (symbol--)
- lengths[index++] = len;
- }
- }
-
- if (lengths[256] == 0)
- return -9;
-
- err = construct(&lencode, lengths, nlen);
- if (err < 0 || (err > 0 && nlen - lencode.count[0] != 1))
- return -7;
-
- err = construct(&distcode, lengths + nlen, ndist);
- if (err < 0 || (err > 0 && ndist - distcode.count[0] != 1))
- return -8;
-
- return codes(s, &lencode, &distcode);
- }
- int puff(unsigned char *dest,
- unsigned long *destlen,
- unsigned char *source,
- unsigned long *sourcelen)
- {
- struct state s;
- int last, type;
- int err;
-
- s.out = dest;
- s.outlen = *destlen;
- s.outcnt = 0;
-
- s.in = source;
- s.inlen = *sourcelen;
- s.incnt = 0;
- s.bitbuf = 0;
- s.bitcnt = 0;
-
- if (setjmp(s.env) != 0)
- err = 2;
- else {
-
- do {
- last = bits(&s, 1);
- type = bits(&s, 2);
- err = type == 0 ? stored(&s) :
- (type == 1 ? fixed(&s) :
- (type == 2 ? dynamic(&s) :
- -1));
- if (err != 0) break;
- } while (!last);
- }
-
- if (err <= 0) {
- *destlen = s.outcnt;
- *sourcelen = s.incnt;
- }
- return err;
- }
- #ifdef TEST
- #include <stdio.h>
- #include <stdlib.h>
- local size_t bythirds(size_t size)
- {
- int n;
- size_t m;
- m = size;
- for (n = 0; m; n++)
- m >>= 1;
- if (n < 3)
- return size + 1;
- n -= 3;
- m = size >> n;
- m += m == 6 ? 2 : 1;
- m <<= n;
- return m > size ? m : (size_t)(-1);
- }
- local void *load(char *name, size_t *len)
- {
- size_t size;
- void *buf, *swap;
- FILE *in;
- *len = 0;
- buf = malloc(size = 4096);
- if (buf == NULL)
- return NULL;
- in = name == NULL ? stdin : fopen(name, "rb");
- if (in != NULL) {
- for (;;) {
- *len += fread((char *)buf + *len, 1, size - *len, in);
- if (*len < size) break;
- size = bythirds(size);
- if (size == *len || (swap = realloc(buf, size)) == NULL) {
- free(buf);
- buf = NULL;
- break;
- }
- buf = swap;
- }
- fclose(in);
- }
- return buf;
- }
- int main(int argc, char **argv)
- {
- int ret, put = 0;
- unsigned skip = 0;
- char *arg, *name = NULL;
- unsigned char *source = NULL, *dest;
- size_t len = 0;
- unsigned long sourcelen, destlen;
-
- while (arg = *++argv, --argc)
- if (arg[0] == '-') {
- if (arg[1] == 'w' && arg[2] == 0)
- put = 1;
- else if (arg[1] >= '0' && arg[1] <= '9')
- skip = (unsigned)atoi(arg + 1);
- else {
- fprintf(stderr, "invalid option %s\n", arg);
- return 3;
- }
- }
- else if (name != NULL) {
- fprintf(stderr, "only one file name allowed\n");
- return 3;
- }
- else
- name = arg;
- source = load(name, &len);
- if (source == NULL) {
- fprintf(stderr, "memory allocation failure\n");
- return 4;
- }
- if (len == 0) {
- fprintf(stderr, "could not read %s, or it was empty\n",
- name == NULL ? "<stdin>" : name);
- free(source);
- return 3;
- }
- if (skip >= len) {
- fprintf(stderr, "skip request of %d leaves no input\n", skip);
- free(source);
- return 3;
- }
-
- len -= skip;
- sourcelen = (unsigned long)len;
- ret = puff(NIL, &destlen, source + skip, &sourcelen);
- if (ret)
- fprintf(stderr, "puff() failed with return code %d\n", ret);
- else {
- fprintf(stderr, "puff() succeeded uncompressing %lu bytes\n", destlen);
- if (sourcelen < len) fprintf(stderr, "%lu compressed bytes unused\n",
- len - sourcelen);
- }
-
- if (put) {
- dest = malloc(destlen);
- if (dest == NULL) {
- fprintf(stderr, "memory allocation failure\n");
- free(source);
- return 4;
- }
- puff(dest, &destlen, source + skip, &sourcelen);
- fwrite(dest, 1, destlen, stdout);
- free(dest);
- }
-
- free(source);
- return ret;
- }
- #endif
|