inffast.c 5.4 KB
Newer Older
M
Mark Adler 已提交
1 2 3 4 5 6 7
/* inffast.c -- process literals and length/distance pairs fast
 * Copyright (C) 1995 Mark Adler
 * For conditions of distribution and use, see copyright notice in zlib.h 
 */

#include "zutil.h"
#include "inftrees.h"
M
Mark Adler 已提交
8 9
#include "infblock.h"
#include "infcodes.h"
M
Mark Adler 已提交
10 11 12
#include "infutil.h"
#include "inffast.h"

M
Mark Adler 已提交
13 14
struct inflate_codes_state {int dummy;}; /* for buggy compilers */

M
Mark Adler 已提交
15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
/* simplify the use of the inflate_huft type with some defines */
#define base more.Base
#define next more.Next
#define exop word.what.Exop
#define bits word.what.Bits

/* macros for bit input with no checking and for returning unused bytes */
#define GRABBITS(j) {while(k<(j)){b|=((uLong)NEXTBYTE)<<k;k+=8;}}
#define UNGRAB {n+=(c=k>>3);p-=c;k&=7;}

/* Called with number of bytes left to write in window at least 258
   (the maximum string length) and number of input bytes available
   at least ten.  The ten bytes are six bytes for the longest length/
   distance pair plus four bytes for overloading the bit buffer. */

int inflate_fast(bl, bd, tl, td, s, z)
uInt bl, bd;
inflate_huft *tl, *td;
M
Mark Adler 已提交
33
inflate_blocks_statef *s;
M
Mark Adler 已提交
34 35
z_stream *z;
{
M
Mark Adler 已提交
36
  inflate_huft *t;      /* temporary pointer */
M
Mark Adler 已提交
37
  uInt e;               /* extra bits or operation */
M
Mark Adler 已提交
38 39
  uLong b;              /* bit buffer */
  uInt k;               /* bits in bit buffer */
M
Mark Adler 已提交
40
  Bytef *p;             /* input data pointer */
M
Mark Adler 已提交
41
  uInt n;               /* bytes available there */
M
Mark Adler 已提交
42
  Bytef *q;             /* output window write pointer */
M
Mark Adler 已提交
43 44 45 46 47
  uInt m;               /* bytes to end of window or read pointer */
  uInt ml;              /* mask for literal/length tree */
  uInt md;              /* mask for distance tree */
  uInt c;               /* bytes to copy */
  uInt d;               /* distance back to copy from */
M
Mark Adler 已提交
48
  Bytef *r;             /* copy source pointer */
M
Mark Adler 已提交
49 50 51 52

  /* load input, output, bit values */
  LOAD

M
Mark Adler 已提交
53
  /* initialize masks */
M
Mark Adler 已提交
54 55 56 57
  ml = inflate_mask[bl];
  md = inflate_mask[bd];

  /* do until not enough input or output space for fast loop */
M
Mark Adler 已提交
58
  do {                          /* assume called with m >= 258 && n >= 10 */
M
Mark Adler 已提交
59
    /* get literal/length code */
M
Mark Adler 已提交
60
    GRABBITS(20)                /* max bits for literal/length code */
M
Mark Adler 已提交
61
    if ((e = (t = tl + ((uInt)b & ml))->exop) == 0)
M
Mark Adler 已提交
62
    {
M
Mark Adler 已提交
63
      DUMPBITS(t->bits)
M
Mark Adler 已提交
64
      Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
M
Mark Adler 已提交
65 66
                "inflate:         * literal '%c'\n" :
                "inflate:         * literal 0x%02x\n", t->base));
M
Mark Adler 已提交
67 68
      *q++ = (Byte)t->base;
      m--;
M
Mark Adler 已提交
69
      continue;
M
Mark Adler 已提交
70
    }
M
Mark Adler 已提交
71 72 73 74 75 76 77 78 79
    do {
      DUMPBITS(t->bits)
      if (e & 16)
      {
        /* get extra bits for length */
        e &= 15;
        c = t->base + ((uInt)b & inflate_mask[e]);
        DUMPBITS(e)
        Tracevv((stderr, "inflate:         * length %u\n", c));
M
Mark Adler 已提交
80

M
Mark Adler 已提交
81 82 83
        /* decode distance base of block to copy */
        GRABBITS(15);           /* max bits for distance code */
        e = (t = td + ((uInt)b & md))->exop;
M
Mark Adler 已提交
84
        do {
M
Mark Adler 已提交
85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123
          DUMPBITS(t->bits)
          if (e & 16)
          {
            /* get extra bits to add to distance base */
            e &= 15;
            GRABBITS(e)         /* get extra bits (up to 13) */
            d = t->base + ((uInt)b & inflate_mask[e]);
            DUMPBITS(e)
            Tracevv((stderr, "inflate:         * distance %u\n", d));

            /* do the copy */
            m -= c;
            if ((uInt)(q - s->window) >= d)     /* offset before dest */
            {                                   /*  just copy */
              r = q - d;
              *q++ = *r++;  c--;        /* minimum count is three, */
              *q++ = *r++;  c--;        /*  so unroll loop a little */
            }
            else                        /* else offset after destination */
            {
              e = d - (q - s->window);  /* bytes from offset to end */
              r = s->end - e;           /* pointer to offset */
              if (c > e)                /* if source crosses, */
              {
                c -= e;                 /* copy to end of window */
                do {
                  *q++ = *r++;
                } while (--e);
                r = s->window;          /* copy rest from start of window */
              }
            }
            do {                        /* copy all or what's left */
              *q++ = *r++;
            } while (--c);
            break;
          }
          else if ((e & 64) == 0)
            e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop;
          else
M
Mark Adler 已提交
124 125 126 127 128 129
          {
            z->msg = "invalid distance code";
            UNGRAB
            UPDATE
            return Z_DATA_ERROR;
          }
M
Mark Adler 已提交
130 131
        } while (1);
        break;
M
Mark Adler 已提交
132
      }
M
Mark Adler 已提交
133
      if ((e & 64) == 0)
M
Mark Adler 已提交
134
      {
M
Mark Adler 已提交
135
        if ((e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop) == 0)
M
Mark Adler 已提交
136
        {
M
Mark Adler 已提交
137 138 139 140 141 142 143
          DUMPBITS(t->bits)
          Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
                    "inflate:         * literal '%c'\n" :
                    "inflate:         * literal 0x%02x\n", t->base));
          *q++ = (Byte)t->base;
          m--;
          break;
M
Mark Adler 已提交
144
        }
M
Mark Adler 已提交
145
      }
M
Mark Adler 已提交
146 147 148 149 150 151 152 153 154 155 156 157 158 159 160
      else if (e & 32)
      {
        Tracevv((stderr, "inflate:         * end of block\n"));
        UNGRAB
        UPDATE
        return Z_STREAM_END;
      }
      else
      {
        z->msg = "invalid literal/length code";
        UNGRAB
        UPDATE
        return Z_DATA_ERROR;
      }
    } while (1);
M
Mark Adler 已提交
161 162 163 164 165 166 167
  } while (m >= 258 && n >= 10);

  /* not enough input or output--restore pointers and return */
  UNGRAB
  UPDATE
  return Z_OK;
}