midpinflate.c

来自「This is a resource based on j2me embedde」· C语言 代码 · 共 685 行 · 第 1/2 页

                    outBuffer[outOffset] = value;
                    outOffset++;
                    prev++;
                }
            }
        }
    }

    STORE_IN;
    STORE_OUT;

    if (!fixedHuffman) {
        state->freeBytes(state->heapState, lcodesMemHandle);
        state->freeBytes(state->heapState, dcodesMemHandle);
    }

    return error;
}

/*=========================================================================
 * 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 int decodeDynamicHuffmanTables(InflaterState *state,
                                      void** lcodesMemHandle,
                                      void** dcodesMemHandle) {
    DECLARE_IN_VARIABLES

    void* ccodesMemHandle;
    HuffmanCodeTable *ccodes = NULL; 

    int hlit, hdist, hclen;
    int i;
    unsigned int quickBits;
    unsigned char codelen[286 + 32];
    unsigned char *codePtr, *endCodePtr;
    int error = 0;
    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) {
            return INFLATE_CODE_TABLE_LENGTH_ERROR;
        }

        codelen[(int)ccode_idx[i]] = (unsigned char)(NEXTBITS(3));
        DUMPBITS(3);
    }

    error = makeCodeTable(state, codelen, 19, MAX_QUICK_CXD, &ccodesMemHandle);

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

    if (error != 0) {
        return error;
    }

    /* This is to support heaps with memory compaction. */
    ccodes = state->addrFromHandle(state->heapState, ccodesMemHandle);

    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
     */

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

        int val;

        if (inRemaining < 0) {
            error = INFLATE_EARLY_END_OF_CCTABLE_INPUT;
            break;
        }

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

            /*
             *  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) {
                error  = INFLATE_BAD_REPEAT_CODE;
                break;
            }

            if (val == 16) {
                if (codePtr == codelen) {
                    error = INFLATE_BAD_REPEAT_CODE;
                    break;
                }
                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 {
            error = INFLATE_BAD_CODELENGTH_CODE;
            break;
        }
    }

    /* ccodes, at this point, is unusable */
    state->freeBytes(state->heapState, ccodesMemHandle);

    while (error == 0) {

        error = makeCodeTable(state, codelen, hlit, MAX_QUICK_LXL,
                lcodesMemHandle);
        if (error != 0) {
            break;
        }

        error = makeCodeTable(state, codelen + hlit, hdist, MAX_QUICK_CXD,
                              dcodesMemHandle);
        if (error != 0) {
            break;
        }

        STORE_IN;

        /* success */
        return 0;
    }

    /* error */
    state->freeBytes(state->heapState, *dcodesMemHandle);
    *dcodesMemHandle = NULL;
    state->freeBytes(state->heapState, *lcodesMemHandle);
    *lcodesMemHandle = NULL;

    return error;
}

/**
 * Huffman code table creation
 *
 * @param codeLen code length, number of elements, type of the alphabet,
 * @param maxQuickBits
 * @param result mem handle to Huffman code table created if successful or
 *               NULL if an error occurs
 *
 * @return 0 for success or an error
 */

static int 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. */
              void** result           /* handle to heap memory*/)
{
    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;
    void* tableMemHandle;
    HuffmanCodeTable* table;
    int mainTableLength, longTableLength, numLongTables;
    int tableSize;
    int j;
    unsigned short *nextLongTable;

    *result = NULL;

    /* 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) {
        // Empty code table is allowed!
    }

    /* 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);
        }
    }

    /* 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]);

    tableMemHandle = state->mallocBytes(state->heapState, tableSize);

    if (tableMemHandle == NULL) {
        return OUT_OF_MEMORY_ERROR;
    }

    /* This is to support heaps with memory compaction. */
    table = state->addrFromHandle(state->heapState, tableMemHandle);

    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]);

    *result = tableMemHandle;
    return 0;
}