inflate.c

Nucleus_2_kvm_Hello 是kvm移植到Nucleus系统的源代码。。。好东西啊

            } else {
                GET_HUFFMAN_ENTRY(dcodes, quickDistanceSize, d0, done_loop);
            }

            if (d0 > MAX_ZIP_DISTANCE_CODE) {
                ziperr(KVM_MSG_JAR_BAD_DISTANCE_CODE);
                goto done_loop;
            }

            NEEDBITS(MAX_ZIP_EXTRA_DISTANCE_BITS)
            distance = dist_base[d0];
            moreBits = dist_extra_bits[d0];
            distance += NEXTBITS(moreBits);
            DUMPBITS(moreBits);

            if (outOffset < distance) {
                ziperr(KVM_MSG_JAR_COPY_UNDERFLOW);
                goto done_loop;
            } else if (outOffset + length > outLength) {
                ziperr(KVM_MSG_JAR_OUTPUT_OVERFLOW);
                goto done_loop;
            } else {
                unsigned long prev = outOffset - distance;
                unsigned long end = outOffset + length;
                unsigned char value;
                while (outOffset != end) {
#ifdef INFLATE_DEBUG_FILE
                    if (state->jarDebugBytes
                      && state->jarDebugBytes[outOffset] != outFile[prev]) {
                        ziperr(KVM_MSG_JAR_DRAGON_COPY_FAILED);
                    }
#endif
                    value = INFLATER_GET_BYTE(prev); 
                    INFLATER_PUT_BYTE(outOffset, value);
                    outOffset++;
                    prev++;
                }
            }
        }
    }

 done_loop:
    STORE_IN;
    STORE_OUT;

 done:
    if (!COMPILING_FOR_KVM && !fixedHuffman) {
        freeBytes(lcodes);
        freeBytes(dcodes);
    }

    return noerror;
}

/*=========================================================================
 * FUNCTION:  decodeDynamicHuffmanTables
 * TYPE:      Huffman code Decoding
 * INTERFACE:
 *   parameters: inData Pointer, Mask Pointer, Max InLimit,
 *               literal/length codes Pointer, Decodes Pointer
 *   returns:    TRUE if successful in decoding or
 *               FALSE if an error occurs
 *=======================================================================*/

static bool_t
decodeDynamicHuffmanTables(inflaterState *state,
               HuffmanCodeTable **lcodesPtr,
               HuffmanCodeTable **dcodesPtr) {
    DECLARE_IN_VARIABLES

    HuffmanCodeTable *ccodes = NULL; 

    int hlit, hdist, hclen;
    int i;
    unsigned int quickBits;
    unsigned char codelen[286 + 32];
    unsigned char *codePtr, *endCodePtr;

    LOAD_IN;

    /* 5 Bits: hlit,  # of Literal/Length codes  (257 - 286) 
     * 5 Bits: hdist, # of Distance codes        (1 - 32) 
     * 4 Bits: hclen, # of Code Length codes     (4 - 19) 
     */
    NEEDBITS(14);
    hlit = 257 + NEXTBITS(5);
    DUMPBITS(5);
    hdist = 1 + NEXTBITS(5);
    DUMPBITS(5);
    hclen = 4 + NEXTBITS(4);
    DUMPBITS(4);

    /*
     *  hclen x 3 bits: code lengths for the code length
     *  alphabet given just above, in the order: 16, 17, 18,
     *  0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
     *
     *  These code lengths are interpreted as 3-bit integers
     *  (0-7); as above, a code length of 0 means the
     *  corresponding symbol (literal/length or distance code
     *  length) is not used.
     */
    memset(codelen, 0x0, 19);
    for (i=0; i<hclen; i++) {
        NEEDBITS(3);    
        if (inRemaining < 0) {
            goto error;
        }
        codelen[(int)ccode_idx[i]] = NEXTBITS(3);
        DUMPBITS(3);
    }

    ccodes = makeCodeTable(state, codelen, 19, MAX_QUICK_CXD);

    /* DANGER:  ccodes is a heap object.   It can become
     * unusable anytime we allocate from the heap.
     */

    if (ccodes == NULL) {
        goto error;
    }
    quickBits = ccodes->h.quickBits;

    /*
     * hlit code lengths for the literal/length alphabet,
     * encoded using the code length Huffman code.
     *
     * hdist code lengths for the distance alphabet,
     * encoded using the code length Huffman code.
     *
     * The code length repeat codes can cross from the literal/length
     * to the code length alphabets.  In other words, all code lengths form
     * a single sequence of hlit + hdist
     */

    ASSERTING_NO_ALLOCATION
        memset(codelen, 0x0, sizeof(codelen));
        for (   codePtr = codelen, endCodePtr = codePtr + hlit + hdist;
            codePtr < endCodePtr; ) {

            int val;

            if (inRemaining < 0) {
                goto error;
            }

            NEEDBITS(MAX_BITS + 7); /* 7 is max repeat bits below */
            GET_HUFFMAN_ENTRY(ccodes, quickBits, val, error);

            /*
             *  0 - 15: Represent code lengths of 0 - 15
             *      16: Copy the previous code length 3 - 6 times.
             *          3 + (2 bits of length)
             *      17: Repeat a code length of 0 for 3 - 10 times.
             *          3 + (3 bits of length)
             *      18: Repeat a code length of 0 for 11 - 138 times
             *          11 + (7 bits of length)
             */
            if (val <= 15) {
                *codePtr++ = val;
            } else if (val <= 18) {
                unsigned repeat  = (val == 18) ? 11 : 3;
                unsigned bits    = (val == 18) ? 7 : (val - 14);

                repeat += NEXTBITS(bits); /* The NEEDBITS is above */
                DUMPBITS(bits);

                if (codePtr + repeat > endCodePtr) {
                    ziperr(KVM_MSG_JAR_BAD_REPEAT_CODE);
                }

                if (val == 16) {
                    if (codePtr == codelen) {
                        ziperr(KVM_MSG_JAR_BAD_REPEAT_CODE);
                        goto error;
                    }
                    memset(codePtr, codePtr[-1], repeat);
                } else {
                    /* The values have already been set to zero, above, so
                     * we don't have to do anything */
                }
                codePtr += repeat;
            } else {
                ziperr(KVM_MSG_JAR_BAD_CODELENGTH_CODE);
                goto error;
            }
        }
    END_ASSERTING_NO_ALLOCATION

    /* ccodes, at this point, is unusable */

    *lcodesPtr = makeCodeTable(state, codelen, hlit, MAX_QUICK_LXL);
    if (*lcodesPtr == NULL) {
        goto error;
    }

    *dcodesPtr = makeCodeTable(state, codelen + hlit, hdist, MAX_QUICK_CXD);
    if (*dcodesPtr == NULL) {
        goto error;
    }

    STORE_IN;
    if (!COMPILING_FOR_KVM) {
        freeBytes(ccodes);
    }
    return TRUE;

error:
    if (!COMPILING_FOR_KVM) {
        freeBytes(ccodes);
        freeBytes(*dcodesPtr);
        freeBytes(*lcodesPtr);
        *lcodesPtr = *dcodesPtr = NULL;
    }
    return FALSE;
}

/*=========================================================================
 * FUNCTION:  makeCodeTable
 * TYPE:      Huffman code table creation
 * INTERFACE:
 *   parameters: code length, number of elements, type of the alphabet,
 *               maxQuickBits
 *   returns:    Huffman code table created if successful or
 *               NULL if an error occurs
 *=======================================================================*/

HuffmanCodeTable *
makeCodeTable(inflaterState *state,
              unsigned char *codelen, /* Code lengths */
              unsigned numElems,      /* Number of elements of the alphabet */
              unsigned maxQuickBits)  /* If the length of a code is longer than
                                       * <maxQuickBits> number of bits, the
                                       * code is stored in the sequential
                                       * lookup table instead of the quick 
                                       * lookup array. */
{
    unsigned int bitLengthCount[MAX_BITS + 1];
    unsigned int codes[MAX_BITS + 1];
    unsigned bits, minCodeLen = 0, maxCodeLen = 0;
    const unsigned char *endCodeLen = codelen + numElems;
    unsigned int code, quickMask;
    unsigned char *p;

    HuffmanCodeTable * table;
    int mainTableLength, longTableLength, numLongTables;
    int tableSize;
    int j;

    unsigned short *nextLongTable;

    /* Count the number of codes for each code length */
    memset(bitLengthCount, 0, sizeof(bitLengthCount));
    for (p = codelen; p < endCodeLen; p++) {
        bitLengthCount[*p]++;
    }

    if (bitLengthCount[0] == numElems) {
        ziperr(KVM_MSG_JAR_CODE_TABLE_EMPTY);
        return NULL;
    }

    /* Find the minimum and maximum.  It's faster to do it in a separate
     * loop that goes 1..MAX_BITS, than in the above loop that looks at
     * every code element */
    code = minCodeLen = maxCodeLen = 0;
    for (bits = 1; bits <= MAX_BITS; bits++) {
        codes[bits] = code;
        if (bitLengthCount[bits] != 0) {
            if (minCodeLen == 0) { 
                minCodeLen = bits;
            }
            maxCodeLen = bits;
            code += bitLengthCount[bits] << (MAX_BITS - bits);
        }
    }

#if INCLUDEDEBUGCODE
    if (code != (1 << MAX_BITS)) {
        code += (1 << (MAX_BITS - maxCodeLen));
        if (code != (1 << MAX_BITS)) {
            ziperr(KVM_MSG_JAR_UNEXPECTED_BIT_CODES);
        }
    }
#endif /* INCLUDEDEBUGCODE */

    /* Calculate the size of the code table and allocate it. */
    if (maxCodeLen <= maxQuickBits) {
        /* We don't need any subtables.  We may even be able to get
         * away with a table smaller than maxCodeLen
         */
        maxQuickBits = maxCodeLen;
        mainTableLength = (1 << maxCodeLen);
        numLongTables = longTableLength = 0;
    } else {
        mainTableLength = (1 << maxQuickBits);
        numLongTables = (1 << MAX_BITS) - codes[maxQuickBits + 1];
        numLongTables = numLongTables >> (MAX_BITS - maxQuickBits);
        longTableLength = 1 << (maxCodeLen - maxQuickBits);
    }

    ASSERT(mainTableLength == 1 << maxQuickBits);
    tableSize = sizeof(HuffmanCodeTableHeader)
          + (mainTableLength + numLongTables * longTableLength)
          * sizeof(table->entries[0]);
    table = (HuffmanCodeTable*)mallocBytes(tableSize);
#if !COMPILING_FOR_KVM
    if (table == NULL) {
        return NULL;
    }
#endif
    nextLongTable = &table->entries[mainTableLength];

    memset(table, 0, tableSize);

    table->h.maxCodeLen   = maxCodeLen;
    table->h.quickBits    = maxQuickBits;

    quickMask = (1 << maxQuickBits) - 1;

    for (p = codelen; p < endCodeLen; p++) {
        unsigned short huff;
        bits = *p;
        if (bits == 0) {
            continue;
        }

        /* Get the next code of the current length */
        code = codes[bits];
        codes[bits] += 1 << (MAX_BITS - bits);
        code = REVERSE_15BITS(code);
        huff = ((p - codelen) << 4) + bits;

        if (bits <= maxQuickBits) {
            unsigned stride = 1 << bits;
            for (j = code; j < mainTableLength; j += stride) {
                table->entries[j] = huff;
            }
        } else {
            unsigned short *thisLongTable;
            unsigned stride = 1 << (bits - maxQuickBits);
            unsigned int prefixCode = code & quickMask;
            unsigned int suffixCode = code >> maxQuickBits;

            if (table->entries[prefixCode] == 0) {
                /* This in the first long code with the indicated prefix.
                 * Create a pointer to the subtable */
                long delta = (char *)nextLongTable - (char *)table;
                table->entries[prefixCode] = 
                    (unsigned short)(HUFFINFO_LONG_MASK | delta);
                thisLongTable = nextLongTable;
               nextLongTable += longTableLength;
            } else {
                long delta = table->entries[prefixCode] & ~HUFFINFO_LONG_MASK;
                thisLongTable = (unsigned short *)((char *)table + delta);
            }

            for (j = suffixCode; j < longTableLength; j += stride) {
                thisLongTable[j] = huff;
            }
        }
    }

    ASSERT(nextLongTable == 
           &table->entries[mainTableLength + numLongTables * longTableLength]);

    return table;
}

#if INCLUDEDEBUGCODE

static void
ziperr(const char *message) {
    fprintf(stderr, "JAR error: %s\n", message);
}

#endif /* INCLUDEDEBUGCODE */