Slow implementation of inflate in C (zlib ~2x faster)

slow_inflate.c

const static unsigned char LENGTH_CODE_EXTRA_BITS[] = {0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0};
const static unsigned char DISTANCE_CODE_EXTRA_BITS[] = {0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13};
const static unsigned char CODE_LENGTHS_ORDER[] = {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
static unsigned short LENGTH_CODE[sizeof(LENGTH_CODE_EXTRA_BITS)];
static unsigned short DISTANCE_CODE[sizeof(DISTANCE_CODE_EXTRA_BITS)];
static unsigned char BIT_REVERSE[256];
const static unsigned int BLOCK_END = 256;
const static unsigned char READ_BITS_FOR_CODE[]={2,3,7}, ADD_COUNT_FOR_CODE[]={3,3,11};
static short HUFFTREE_LITLEN[(1 << 24)+1];
static short HUFFTREE_DIST[(1 << 24)+1];
static unsigned char *maxinput, *maxoutput;
static unsigned int blockcount = 0;

unsigned int readForwardBits(unsigned char bitCount, unsigned char *input, unsigned int *inputBitPos) {
    unsigned int ibp = *inputBitPos;
    unsigned int bytePos = ibp>>3;
    unsigned char bitPos = ibp&7;
    ibp+=bitCount;
    *inputBitPos=ibp;
    unsigned int mask = (1<<bitCount)-1;
    unsigned int n=input[bytePos];
    unsigned int bytePosEnd = ibp>>3;
    if (bytePos < bytePosEnd) {
        n |= (input[++bytePos]) << 8;
        if (bytePos < bytePosEnd) {
            n |= (input[++bytePos]) << 16;
            if (bytePos < bytePosEnd) {
                n |= (input[++bytePos]) << 24;
            }
        }
    }
    return (n >> bitPos) & mask;
}

unsigned int readReverseBits(unsigned char bitCount, unsigned char *input, unsigned int *inputBitPos) {
    unsigned int ibp = *inputBitPos;
    unsigned int bytePos = ibp>>3;
    ibp+=bitCount;
    *inputBitPos = ibp;
    unsigned int mask = (1<<bitCount)-1;
    unsigned int n = BIT_REVERSE[input[bytePos]];
    unsigned int bytePosEnd = ibp >> 3;
    unsigned char bitPosEnd = ibp & 7;
    if (bytePos < bytePosEnd) {
        n=(n<<8) | BIT_REVERSE[input[++bytePos]];
        if (bytePos < bytePosEnd) {
            n=(n<<8) | BIT_REVERSE[input[++bytePos]];
            if (bytePos < bytePosEnd) {
                n=(n<<8) | BIT_REVERSE[input[++bytePos]];
            }
        }
    }
    return (n>>(8-bitPosEnd)) & mask;
}

short *buildHuffmanMap(short *map, unsigned char *bitLengths, unsigned short start, unsigned short end) {
    unsigned char maxBits = 0;
    for(unsigned short i=start; i<end; i++) {
        unsigned char bitLength = bitLengths[i];
        if (bitLength>maxBits) maxBits=bitLength;
    }
    short *mptr = map;
    *(mptr++) = maxBits;
    int repeats = 1 << maxBits;
    for(int bits=1; bits<=maxBits; bits++) {
        repeats >>=1;
        int xbits = (maxBits-bits)<<9;
        for(int i=start;i<end;i++)
            if (bitLengths[i]==bits)
                for(short x=i-start+xbits, *e=mptr+repeats; mptr<e; ) *(mptr++)=x;
    }
    return map;
}

unsigned int readCodeWithHuffmanMap(short *map, unsigned char *input, unsigned int *inputBitPos) {
    short bits = *(map++);
    unsigned int v = readReverseBits(bits, input, inputBitPos);
    short xc = map[v];
    *inputBitPos = (*inputBitPos) - (xc >> 9);
    return xc & 0x1FF;
}

unsigned char *errorBlock(unsigned char *input, unsigned int *inputBitPos, unsigned char *output) {
    // printf("error - unrecognized block type");
    return NULL;
}

unsigned char *storedBlockInflate(unsigned char *input, unsigned int *inputBitPos, unsigned char *output) {
    unsigned int ibp = *inputBitPos;
    while(ibp & 7) ibp++;
    *inputBitPos = ibp;
    unsigned short len = readForwardBits(16, input, inputBitPos), nlen = readForwardBits(16, input, inputBitPos);
    if(~nlen != len) return NULL;
    input = &input[(*inputBitPos) >> 3];
    *inputBitPos += len;
    unsigned char *outputend = output+len;
    while(output<outputend) *(output++)=*(input++);
    return output;
}

unsigned char *fixedHuffmanBlockInflate(unsigned char *input, unsigned int *inputBitPos, unsigned char *output) {
    for(;;) {
        unsigned short code7 = readReverseBits(7, input, inputBitPos);
        unsigned short code;
        if(code7<0x60) {
            if(code7<0x18) {
                if(!code7) break; // BLOCK_END
                code = code7+256;
            } else {
                code = ((code7<<1) | readReverseBits(1, input, inputBitPos)) - 0x30; // 0-0x18*2
                *output = (unsigned char)code;
                continue;
            }
        } else if(code7 < 0x64) {
            code = ((code7 << 1) | readReverseBits(1, input, inputBitPos)) + 88; // 280 - 0x60*2
        } else {
            code = ((code7 <<2) | readReverseBits(2, input, inputBitPos))-256; // 144-0x64*4
            *output = (unsigned char)code;
            continue;
        }
        unsigned short lcode = code-257;
        unsigned short length = LENGTH_CODE[lcode] + readForwardBits(LENGTH_CODE_EXTRA_BITS[lcode], input, inputBitPos);
        unsigned short dcode = readReverseBits(5, input, inputBitPos);
        unsigned short distance = DISTANCE_CODE[dcode] + readForwardBits(DISTANCE_CODE_EXTRA_BITS[dcode], input, inputBitPos);
        unsigned char *src = output; src-=distance;
        unsigned char *outputend = output; outputend+=length;
        while(output<outputend) *(output++)=*(src++);
    }
    return output;
}

unsigned char *dynamicHuffmanBlockInflate(unsigned char *input, unsigned int *inputBitPos, unsigned char *output) {
    unsigned short lengthCodeCount = readForwardBits(5, input, inputBitPos);
    unsigned short literalAndLengthsCodeCount = lengthCodeCount+257;
    unsigned short distanceCodesCount = readForwardBits(5, input, inputBitPos)+1;
    unsigned short codeLengthsCount = readForwardBits(4, input, inputBitPos)+4;
    unsigned char codeLengths[sizeof(CODE_LENGTHS_ORDER)];
    const unsigned char *clo = &CODE_LENGTHS_ORDER[0], *cloe = &CODE_LENGTHS_ORDER[codeLengthsCount], *cloe2 = &CODE_LENGTHS_ORDER[sizeof(CODE_LENGTHS_ORDER)];
    while(clo<cloe) codeLengths[*(clo++)] = (unsigned char)readForwardBits(3, input, inputBitPos);
    while(clo<cloe2) codeLengths[*(clo++)] = 0;
    short *huffCodeLens = buildHuffmanMap(HUFFTREE_LITLEN, codeLengths, 0, sizeof(codeLengths));
    
    unsigned short allCodeCount = literalAndLengthsCodeCount+distanceCodesCount;
    unsigned char allCodeLengths[allCodeCount];
    unsigned char *allCodeLengthsPtr = allCodeLengths, *allCodeLengthsPtrEnd = allCodeLengthsPtr+allCodeCount;
    while(allCodeLengthsPtr < allCodeLengthsPtrEnd) {
        int codeLengthCode = readCodeWithHuffmanMap(huffCodeLens, input, inputBitPos);
        if (codeLengthCode<16) {
            *(allCodeLengthsPtr++) = codeLengthCode;
        } else {
            codeLengthCode-=16;
            unsigned short copyCount = readForwardBits(READ_BITS_FOR_CODE[codeLengthCode], input, inputBitPos)+ADD_COUNT_FOR_CODE[codeLengthCode];
            unsigned char src = codeLengthCode ? 0 : *(allCodeLengthsPtr-1);
            while(copyCount--) *(allCodeLengthsPtr++)=src;
        }
    }
    short *huffmanLiteralsAndLengths = buildHuffmanMap(HUFFTREE_LITLEN, allCodeLengths, 0, literalAndLengthsCodeCount);
    short *huffmanDistanceLengths = buildHuffmanMap(HUFFTREE_DIST, allCodeLengths, literalAndLengthsCodeCount, allCodeCount);
    
    for(unsigned int code; (code = readCodeWithHuffmanMap(huffmanLiteralsAndLengths, input, inputBitPos)) != BLOCK_END; ) {
        if(code<BLOCK_END) { //literal
            *(output++) = (unsigned char) code;
            continue;
        }
        unsigned int lcode = code-257;
        unsigned int length = LENGTH_CODE[lcode]+readForwardBits(LENGTH_CODE_EXTRA_BITS[lcode], input, inputBitPos);
        unsigned int dcode = readCodeWithHuffmanMap(huffmanDistanceLengths, input, inputBitPos);
        unsigned int distance = DISTANCE_CODE[dcode] + readForwardBits(DISTANCE_CODE_EXTRA_BITS[dcode], input, inputBitPos);
        unsigned char *src = output-distance;
        unsigned char *outputend = output+length;
        while(output<outputend) *(output++)=*(src++);
    }
    return output;
}

static unsigned char *(*fnBlockInflaters[])(unsigned char *, unsigned int *, unsigned char *) = {storedBlockInflate, fixedHuffmanBlockInflate, dynamicHuffmanBlockInflate, errorBlock};

void inflate(unsigned char *input, unsigned char *output) {
    for(unsigned int inputBitPos = 0;;blockcount++) {
        unsigned char finalBlock = readForwardBits(1, input, &inputBitPos), blockType = readForwardBits(2, input, &inputBitPos);
        output = fnBlockInflaters[blockType](input, &inputBitPos, output);
        if(finalBlock) break;
        if(output==NULL) break;
    }
}

void inflateyInit(void) {
    const unsigned char *lcxb = LENGTH_CODE_EXTRA_BITS, *lcxbe = lcxb+sizeof(LENGTH_CODE_EXTRA_BITS)-1;
    unsigned short *lc = LENGTH_CODE;
    unsigned short len=3; while(lcxb<lcxbe) { *(lc++)=len; len+=1 << *(lcxb++); }
    *(--lc)=len-1;
    
    const unsigned char *dcxb = DISTANCE_CODE_EXTRA_BITS, *dcxbe = dcxb+sizeof(DISTANCE_CODE_EXTRA_BITS);
    unsigned short *dc = DISTANCE_CODE;
    unsigned short dist=1; while(dcxb<dcxbe) { *(dc++)=dist; dist+=1 << *(dcxb++); }
    
    unsigned char *br = BIT_REVERSE;
    for(unsigned short i=0;i<256;i++)
        *(br++) = (unsigned char)(((i & 1) << 7) | ((i & 2) << 5) | ((i & 4) << 3) | ((i & 8) << 1) | ((i & 16) >> 1) | ((i & 32) >> 3) | ((i & 64) >> 5) | ((i & 128) >> 7));
}