EmbeddedPkg: Extend NvVarStoreFormattedLib LIBRARY_CLASS

[mirror_edk2.git] / AppPkg / Applications / Python / Python-2.7.10 / Modules / zlib / inffast.c

/* inffast.c -- fast decoding\r
 * Copyright (C) 1995-2008, 2010, 2013 Mark Adler\r
 * For conditions of distribution and use, see copyright notice in zlib.h\r
 */\r
\r
#include "zutil.h"\r
#include "inftrees.h"\r
#include "inflate.h"\r
#include "inffast.h"\r
\r
#ifndef ASMINF\r
\r
/* Allow machine dependent optimization for post-increment or pre-increment.\r
   Based on testing to date,\r
   Pre-increment preferred for:\r
   - PowerPC G3 (Adler)\r
   - MIPS R5000 (Randers-Pehrson)\r
   Post-increment preferred for:\r
   - none\r
   No measurable difference:\r
   - Pentium III (Anderson)\r
   - M68060 (Nikl)\r
 */\r
#ifdef POSTINC\r
#  define OFF 0\r
#  define PUP(a) *(a)++\r
#else\r
#  define OFF 1\r
#  define PUP(a) *++(a)\r
#endif\r
\r
/*\r
   Decode literal, length, and distance codes and write out the resulting\r
   literal and match bytes until either not enough input or output is\r
   available, an end-of-block is encountered, or a data error is encountered.\r
   When large enough input and output buffers are supplied to inflate(), for\r
   example, a 16K input buffer and a 64K output buffer, more than 95% of the\r
   inflate execution time is spent in this routine.\r
\r
   Entry assumptions:\r
\r
        state->mode == LEN\r
        strm->avail_in >= 6\r
        strm->avail_out >= 258\r
        start >= strm->avail_out\r
        state->bits < 8\r
\r
   On return, state->mode is one of:\r
\r
        LEN -- ran out of enough output space or enough available input\r
        TYPE -- reached end of block code, inflate() to interpret next block\r
        BAD -- error in block data\r
\r
   Notes:\r
\r
    - The maximum input bits used by a length/distance pair is 15 bits for the\r
      length code, 5 bits for the length extra, 15 bits for the distance code,\r
      and 13 bits for the distance extra.  This totals 48 bits, or six bytes.\r
      Therefore if strm->avail_in >= 6, then there is enough input to avoid\r
      checking for available input while decoding.\r
\r
    - The maximum bytes that a single length/distance pair can output is 258\r
      bytes, which is the maximum length that can be coded.  inflate_fast()\r
      requires strm->avail_out >= 258 for each loop to avoid checking for\r
      output space.\r
 */\r
void ZLIB_INTERNAL inflate_fast(strm, start)\r
z_streamp strm;\r
unsigned start;         /* inflate()'s starting value for strm->avail_out */\r
{\r
    struct inflate_state FAR *state;\r
    z_const unsigned char FAR *in;      /* local strm->next_in */\r
    z_const unsigned char FAR *last;    /* have enough input while in < last */\r
    unsigned char FAR *out;     /* local strm->next_out */\r
    unsigned char FAR *beg;     /* inflate()'s initial strm->next_out */\r
    unsigned char FAR *end;     /* while out < end, enough space available */\r
#ifdef INFLATE_STRICT\r
    unsigned dmax;              /* maximum distance from zlib header */\r
#endif\r
    unsigned wsize;             /* window size or zero if not using window */\r
    unsigned whave;             /* valid bytes in the window */\r
    unsigned wnext;             /* window write index */\r
    unsigned char FAR *window;  /* allocated sliding window, if wsize != 0 */\r
    unsigned long hold;         /* local strm->hold */\r
    unsigned bits;              /* local strm->bits */\r
    code const FAR *lcode;      /* local strm->lencode */\r
    code const FAR *dcode;      /* local strm->distcode */\r
    unsigned lmask;             /* mask for first level of length codes */\r
    unsigned dmask;             /* mask for first level of distance codes */\r
    code here;                  /* retrieved table entry */\r
    unsigned op;                /* code bits, operation, extra bits, or */\r
                                /*  window position, window bytes to copy */\r
    unsigned len;               /* match length, unused bytes */\r
    unsigned dist;              /* match distance */\r
    unsigned char FAR *from;    /* where to copy match from */\r
\r
    /* copy state to local variables */\r
    state = (struct inflate_state FAR *)strm->state;\r
    in = strm->next_in - OFF;\r
    last = in + (strm->avail_in - 5);\r
    out = strm->next_out - OFF;\r
    beg = out - (start - strm->avail_out);\r
    end = out + (strm->avail_out - 257);\r
#ifdef INFLATE_STRICT\r
    dmax = state->dmax;\r
#endif\r
    wsize = state->wsize;\r
    whave = state->whave;\r
    wnext = state->wnext;\r
    window = state->window;\r
    hold = state->hold;\r
    bits = state->bits;\r
    lcode = state->lencode;\r
    dcode = state->distcode;\r
    lmask = (1U << state->lenbits) - 1;\r
    dmask = (1U << state->distbits) - 1;\r
\r
    /* decode literals and length/distances until end-of-block or not enough\r
       input data or output space */\r
    do {\r
        if (bits < 15) {\r
            hold += (unsigned long)(PUP(in)) << bits;\r
            bits += 8;\r
            hold += (unsigned long)(PUP(in)) << bits;\r
            bits += 8;\r
        }\r
        here = lcode[hold & lmask];\r
      dolen:\r
        op = (unsigned)(here.bits);\r
        hold >>= op;\r
        bits -= op;\r
        op = (unsigned)(here.op);\r
        if (op == 0) {                          /* literal */\r
            Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ?\r
                    "inflate:         literal '%c'\n" :\r
                    "inflate:         literal 0x%02x\n", here.val));\r
            PUP(out) = (unsigned char)(here.val);\r
        }\r
        else if (op & 16) {                     /* length base */\r
            len = (unsigned)(here.val);\r
            op &= 15;                           /* number of extra bits */\r
            if (op) {\r
                if (bits < op) {\r
                    hold += (unsigned long)(PUP(in)) << bits;\r
                    bits += 8;\r
                }\r
                len += (unsigned)hold & ((1U << op) - 1);\r
                hold >>= op;\r
                bits -= op;\r
            }\r
            Tracevv((stderr, "inflate:         length %u\n", len));\r
            if (bits < 15) {\r
                hold += (unsigned long)(PUP(in)) << bits;\r
                bits += 8;\r
                hold += (unsigned long)(PUP(in)) << bits;\r
                bits += 8;\r
            }\r
            here = dcode[hold & dmask];\r
          dodist:\r
            op = (unsigned)(here.bits);\r
            hold >>= op;\r
            bits -= op;\r
            op = (unsigned)(here.op);\r
            if (op & 16) {                      /* distance base */\r
                dist = (unsigned)(here.val);\r
                op &= 15;                       /* number of extra bits */\r
                if (bits < op) {\r
                    hold += (unsigned long)(PUP(in)) << bits;\r
                    bits += 8;\r
                    if (bits < op) {\r
                        hold += (unsigned long)(PUP(in)) << bits;\r
                        bits += 8;\r
                    }\r
                }\r
                dist += (unsigned)hold & ((1U << op) - 1);\r
#ifdef INFLATE_STRICT\r
                if (dist > dmax) {\r
                    strm->msg = (char *)"invalid distance too far back";\r
                    state->mode = BAD;\r
                    break;\r
                }\r
#endif\r
                hold >>= op;\r
                bits -= op;\r
                Tracevv((stderr, "inflate:         distance %u\n", dist));\r
                op = (unsigned)(out - beg);     /* max distance in output */\r
                if (dist > op) {                /* see if copy from window */\r
                    op = dist - op;             /* distance back in window */\r
                    if (op > whave) {\r
                        if (state->sane) {\r
                            strm->msg =\r
                                (char *)"invalid distance too far back";\r
                            state->mode = BAD;\r
                            break;\r
                        }\r
#ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR\r
                        if (len <= op - whave) {\r
                            do {\r
                                PUP(out) = 0;\r
                            } while (--len);\r
                            continue;\r
                        }\r
                        len -= op - whave;\r
                        do {\r
                            PUP(out) = 0;\r
                        } while (--op > whave);\r
                        if (op == 0) {\r
                            from = out - dist;\r
                            do {\r
                                PUP(out) = PUP(from);\r
                            } while (--len);\r
                            continue;\r
                        }\r
#endif\r
                    }\r
                    from = window - OFF;\r
                    if (wnext == 0) {           /* very common case */\r
                        from += wsize - op;\r
                        if (op < len) {         /* some from window */\r
                            len -= op;\r
                            do {\r
                                PUP(out) = PUP(from);\r
                            } while (--op);\r
                            from = out - dist;  /* rest from output */\r
                        }\r
                    }\r
                    else if (wnext < op) {      /* wrap around window */\r
                        from += wsize + wnext - op;\r
                        op -= wnext;\r
                        if (op < len) {         /* some from end of window */\r
                            len -= op;\r
                            do {\r
                                PUP(out) = PUP(from);\r
                            } while (--op);\r
                            from = window - OFF;\r
                            if (wnext < len) {  /* some from start of window */\r
                                op = wnext;\r
                                len -= op;\r
                                do {\r
                                    PUP(out) = PUP(from);\r
                                } while (--op);\r
                                from = out - dist;      /* rest from output */\r
                            }\r
                        }\r
                    }\r
                    else {                      /* contiguous in window */\r
                        from += wnext - op;\r
                        if (op < len) {         /* some from window */\r
                            len -= op;\r
                            do {\r
                                PUP(out) = PUP(from);\r
                            } while (--op);\r
                            from = out - dist;  /* rest from output */\r
                        }\r
                    }\r
                    while (len > 2) {\r
                        PUP(out) = PUP(from);\r
                        PUP(out) = PUP(from);\r
                        PUP(out) = PUP(from);\r
                        len -= 3;\r
                    }\r
                    if (len) {\r
                        PUP(out) = PUP(from);\r
                        if (len > 1)\r
                            PUP(out) = PUP(from);\r
                    }\r
                }\r
                else {\r
                    from = out - dist;          /* copy direct from output */\r
                    do {                        /* minimum length is three */\r
                        PUP(out) = PUP(from);\r
                        PUP(out) = PUP(from);\r
                        PUP(out) = PUP(from);\r
                        len -= 3;\r
                    } while (len > 2);\r
                    if (len) {\r
                        PUP(out) = PUP(from);\r
                        if (len > 1)\r
                            PUP(out) = PUP(from);\r
                    }\r
                }\r
            }\r
            else if ((op & 64) == 0) {          /* 2nd level distance code */\r
                here = dcode[here.val + (hold & ((1U << op) - 1))];\r
                goto dodist;\r
            }\r
            else {\r
                strm->msg = (char *)"invalid distance code";\r
                state->mode = BAD;\r
                break;\r
            }\r
        }\r
        else if ((op & 64) == 0) {              /* 2nd level length code */\r
            here = lcode[here.val + (hold & ((1U << op) - 1))];\r
            goto dolen;\r
        }\r
        else if (op & 32) {                     /* end-of-block */\r
            Tracevv((stderr, "inflate:         end of block\n"));\r
            state->mode = TYPE;\r
            break;\r
        }\r
        else {\r
            strm->msg = (char *)"invalid literal/length code";\r
            state->mode = BAD;\r
            break;\r
        }\r
    } while (in < last && out < end);\r
\r
    /* return unused bytes (on entry, bits < 8, so in won't go too far back) */\r
    len = bits >> 3;\r
    in -= len;\r
    bits -= len << 3;\r
    hold &= (1U << bits) - 1;\r
\r
    /* update state and return */\r
    strm->next_in = in + OFF;\r
    strm->next_out = out + OFF;\r
    strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));\r
    strm->avail_out = (unsigned)(out < end ?\r
                                 257 + (end - out) : 257 - (out - end));\r
    state->hold = hold;\r
    state->bits = bits;\r
    return;\r
}\r
\r
/*\r
   inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):\r
   - Using bit fields for code structure\r
   - Different op definition to avoid & for extra bits (do & for table bits)\r
   - Three separate decoding do-loops for direct, window, and wnext == 0\r
   - Special case for distance > 1 copies to do overlapped load and store copy\r
   - Explicit branch predictions (based on measured branch probabilities)\r
   - Deferring match copy and interspersed it with decoding subsequent codes\r
   - Swapping literal/length else\r
   - Swapping window/direct else\r
   - Larger unrolled copy loops (three is about right)\r
   - Moving len -= 3 statement into middle of loop\r
 */\r
\r
#endif /* !ASMINF */\r