misc/libfreetype/src/gzip/infcodes.c
changeset 5172 88f2e05288ba
equal deleted inserted replaced
5171:f9283dc4860d 5172:88f2e05288ba
       
     1 /* infcodes.c -- process literals and length/distance pairs
       
     2  * Copyright (C) 1995-2002 Mark Adler
       
     3  * For conditions of distribution and use, see copyright notice in zlib.h
       
     4  */
       
     5 
       
     6 #include "zutil.h"
       
     7 #include "inftrees.h"
       
     8 #include "infblock.h"
       
     9 #include "infcodes.h"
       
    10 #include "infutil.h"
       
    11 
       
    12 /* simplify the use of the inflate_huft type with some defines */
       
    13 #define exop word.what.Exop
       
    14 #define bits word.what.Bits
       
    15 
       
    16 typedef enum {        /* waiting for "i:"=input, "o:"=output, "x:"=nothing */
       
    17       START,    /* x: set up for LEN */
       
    18       LEN,      /* i: get length/literal/eob next */
       
    19       LENEXT,   /* i: getting length extra (have base) */
       
    20       DIST,     /* i: get distance next */
       
    21       DISTEXT,  /* i: getting distance extra */
       
    22       COPY,     /* o: copying bytes in window, waiting for space */
       
    23       LIT,      /* o: got literal, waiting for output space */
       
    24       WASH,     /* o: got eob, possibly still output waiting */
       
    25       END,      /* x: got eob and all data flushed */
       
    26       BADCODE}  /* x: got error */
       
    27 inflate_codes_mode;
       
    28 
       
    29 /* inflate codes private state */
       
    30 struct inflate_codes_state {
       
    31 
       
    32   /* mode */
       
    33   inflate_codes_mode mode;      /* current inflate_codes mode */
       
    34 
       
    35   /* mode dependent information */
       
    36   uInt len;
       
    37   union {
       
    38     struct {
       
    39       inflate_huft *tree;       /* pointer into tree */
       
    40       uInt need;                /* bits needed */
       
    41     } code;             /* if LEN or DIST, where in tree */
       
    42     uInt lit;           /* if LIT, literal */
       
    43     struct {
       
    44       uInt get;                 /* bits to get for extra */
       
    45       uInt dist;                /* distance back to copy from */
       
    46     } copy;             /* if EXT or COPY, where and how much */
       
    47   } sub;                /* submode */
       
    48 
       
    49   /* mode independent information */
       
    50   Byte lbits;           /* ltree bits decoded per branch */
       
    51   Byte dbits;           /* dtree bits decoder per branch */
       
    52   inflate_huft *ltree;          /* literal/length/eob tree */
       
    53   inflate_huft *dtree;          /* distance tree */
       
    54 
       
    55 };
       
    56 
       
    57 
       
    58 local inflate_codes_statef *inflate_codes_new( /* bl, bd, tl, td, z) */
       
    59 uInt bl, uInt bd,
       
    60 inflate_huft *tl,
       
    61 inflate_huft *td, /* need separate declaration for Borland C++ */
       
    62 z_streamp z )
       
    63 {
       
    64   inflate_codes_statef *c;
       
    65 
       
    66   if ((c = (inflate_codes_statef *)
       
    67        ZALLOC(z,1,sizeof(struct inflate_codes_state))) != Z_NULL)
       
    68   {
       
    69     c->mode = START;
       
    70     c->lbits = (Byte)bl;
       
    71     c->dbits = (Byte)bd;
       
    72     c->ltree = tl;
       
    73     c->dtree = td;
       
    74     Tracev((stderr, "inflate:       codes new\n"));
       
    75   }
       
    76   return c;
       
    77 }
       
    78 
       
    79 
       
    80 local int inflate_codes( /* s, z, r) */
       
    81 inflate_blocks_statef *s,
       
    82 z_streamp z,
       
    83 int r )
       
    84 {
       
    85   uInt j;               /* temporary storage */
       
    86   inflate_huft *t;      /* temporary pointer */
       
    87   uInt e;               /* extra bits or operation */
       
    88   uLong b;              /* bit buffer */
       
    89   uInt k;               /* bits in bit buffer */
       
    90   Bytef *p;             /* input data pointer */
       
    91   uInt n;               /* bytes available there */
       
    92   Bytef *q;             /* output window write pointer */
       
    93   uInt m;               /* bytes to end of window or read pointer */
       
    94   Bytef *f;             /* pointer to copy strings from */
       
    95   inflate_codes_statef *c = s->sub.decode.codes;  /* codes state */
       
    96 
       
    97   /* copy input/output information to locals (UPDATE macro restores) */
       
    98   LOAD
       
    99 
       
   100   /* process input and output based on current state */
       
   101   while (1) switch (c->mode)
       
   102   {             /* waiting for "i:"=input, "o:"=output, "x:"=nothing */
       
   103     case START:         /* x: set up for LEN */
       
   104 #ifndef SLOW
       
   105       if (m >= 258 && n >= 10)
       
   106       {
       
   107         UPDATE
       
   108         r = inflate_fast(c->lbits, c->dbits, c->ltree, c->dtree, s, z);
       
   109         LOAD
       
   110         if (r != Z_OK)
       
   111         {
       
   112           c->mode = r == Z_STREAM_END ? WASH : BADCODE;
       
   113           break;
       
   114         }
       
   115       }
       
   116 #endif /* !SLOW */
       
   117       c->sub.code.need = c->lbits;
       
   118       c->sub.code.tree = c->ltree;
       
   119       c->mode = LEN;
       
   120     case LEN:           /* i: get length/literal/eob next */
       
   121       j = c->sub.code.need;
       
   122       NEEDBITS(j)
       
   123       t = c->sub.code.tree + ((uInt)b & inflate_mask[j]);
       
   124       DUMPBITS(t->bits)
       
   125       e = (uInt)(t->exop);
       
   126       if (e == 0)               /* literal */
       
   127       {
       
   128         c->sub.lit = t->base;
       
   129         Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
       
   130                  "inflate:         literal '%c'\n" :
       
   131                  "inflate:         literal 0x%02x\n", t->base));
       
   132         c->mode = LIT;
       
   133         break;
       
   134       }
       
   135       if (e & 16)               /* length */
       
   136       {
       
   137         c->sub.copy.get = e & 15;
       
   138         c->len = t->base;
       
   139         c->mode = LENEXT;
       
   140         break;
       
   141       }
       
   142       if ((e & 64) == 0)        /* next table */
       
   143       {
       
   144         c->sub.code.need = e;
       
   145         c->sub.code.tree = t + t->base;
       
   146         break;
       
   147       }
       
   148       if (e & 32)               /* end of block */
       
   149       {
       
   150         Tracevv((stderr, "inflate:         end of block\n"));
       
   151         c->mode = WASH;
       
   152         break;
       
   153       }
       
   154       c->mode = BADCODE;        /* invalid code */
       
   155       z->msg = (char*)"invalid literal/length code";
       
   156       r = Z_DATA_ERROR;
       
   157       LEAVE
       
   158     case LENEXT:        /* i: getting length extra (have base) */
       
   159       j = c->sub.copy.get;
       
   160       NEEDBITS(j)
       
   161       c->len += (uInt)b & inflate_mask[j];
       
   162       DUMPBITS(j)
       
   163       c->sub.code.need = c->dbits;
       
   164       c->sub.code.tree = c->dtree;
       
   165       Tracevv((stderr, "inflate:         length %u\n", c->len));
       
   166       c->mode = DIST;
       
   167     case DIST:          /* i: get distance next */
       
   168       j = c->sub.code.need;
       
   169       NEEDBITS(j)
       
   170       t = c->sub.code.tree + ((uInt)b & inflate_mask[j]);
       
   171       DUMPBITS(t->bits)
       
   172       e = (uInt)(t->exop);
       
   173       if (e & 16)               /* distance */
       
   174       {
       
   175         c->sub.copy.get = e & 15;
       
   176         c->sub.copy.dist = t->base;
       
   177         c->mode = DISTEXT;
       
   178         break;
       
   179       }
       
   180       if ((e & 64) == 0)        /* next table */
       
   181       {
       
   182         c->sub.code.need = e;
       
   183         c->sub.code.tree = t + t->base;
       
   184         break;
       
   185       }
       
   186       c->mode = BADCODE;        /* invalid code */
       
   187       z->msg = (char*)"invalid distance code";
       
   188       r = Z_DATA_ERROR;
       
   189       LEAVE
       
   190     case DISTEXT:       /* i: getting distance extra */
       
   191       j = c->sub.copy.get;
       
   192       NEEDBITS(j)
       
   193       c->sub.copy.dist += (uInt)b & inflate_mask[j];
       
   194       DUMPBITS(j)
       
   195       Tracevv((stderr, "inflate:         distance %u\n", c->sub.copy.dist));
       
   196       c->mode = COPY;
       
   197     case COPY:          /* o: copying bytes in window, waiting for space */
       
   198       f = q - c->sub.copy.dist;
       
   199       while (f < s->window)             /* modulo window size-"while" instead */
       
   200         f += s->end - s->window;        /* of "if" handles invalid distances */
       
   201       while (c->len)
       
   202       {
       
   203         NEEDOUT
       
   204         OUTBYTE(*f++)
       
   205         if (f == s->end)
       
   206           f = s->window;
       
   207         c->len--;
       
   208       }
       
   209       c->mode = START;
       
   210       break;
       
   211     case LIT:           /* o: got literal, waiting for output space */
       
   212       NEEDOUT
       
   213       OUTBYTE(c->sub.lit)
       
   214       c->mode = START;
       
   215       break;
       
   216     case WASH:          /* o: got eob, possibly more output */
       
   217       if (k > 7)        /* return unused byte, if any */
       
   218       {
       
   219         Assert(k < 16, "inflate_codes grabbed too many bytes")
       
   220         k -= 8;
       
   221         n++;
       
   222         p--;            /* can always return one */
       
   223       }
       
   224       FLUSH
       
   225       if (s->read != s->write)
       
   226         LEAVE
       
   227       c->mode = END;
       
   228     case END:
       
   229       r = Z_STREAM_END;
       
   230       LEAVE
       
   231     case BADCODE:       /* x: got error */
       
   232       r = Z_DATA_ERROR;
       
   233       LEAVE
       
   234     default:
       
   235       r = Z_STREAM_ERROR;
       
   236       LEAVE
       
   237   }
       
   238 #ifdef NEED_DUMMY_RETURN
       
   239   return Z_STREAM_ERROR;  /* Some dumb compilers complain without this */
       
   240 #endif
       
   241 }
       
   242 
       
   243 
       
   244 local void inflate_codes_free( /* c, z) */
       
   245 inflate_codes_statef *c,
       
   246 z_streamp z )
       
   247 {
       
   248   ZFREE(z, c);
       
   249   Tracev((stderr, "inflate:       codes free\n"));
       
   250 }