; At the start: 
;    esi: pointer to the current byte in the input stream.
;    eax: the current dword of the stream.
;    ch: how many bits remains for reading in eax
;    cl: how many bits to be read in edx.
; At the end:
;    edx - bits read from the stream.
        or      edx, -1
        shl     edx, cl
        not     edx

        and     edx, eax
        shr     eax, cl

        sub     ch, cl
        jg      @f

        add     esi, 2
        cmp     esi, [.pEnd]
        jae     .error

        mov     cl, ch
        mov     eax, [esi]
        add     ch, $10
        rol     eax, cl

@@:    

; The same as the above, but read fixed count of 5 bits.
; It does not need bit mask to be constructed.
        mov     edx, eax
        shr     eax, 5

        and     edx, $1f

        sub     ch, 5
        jg      @f

        add     esi, 2
        cmp     esi, [.pEnd]
        jae     .error

        mov     cl, ch
        mov     eax, [esi]
        add     ch, $10
        rol     eax, cl

@@:    

.mode_typedo:
        cmp     dword [rbx+zlib_istate_last_ofs], 0
        jne     .mode_typedo_last
        zlib_inflate_needbits 3
        mov     eax, r12d
        and     eax, 1
        mov     dword [rbx+zlib_istate_last_ofs], eax
        zlib_inflate_dropbits 1
        mov     eax, r12d
        and     eax, 3
        cmp     eax, 0
        je      .mode_typedo_stored
        cmp     eax, 1
        je      .mode_typedo_fixed
        cmp     eax, 2
        je      .mode_typedo_dynamic
        ; invalid block type
        zlib_inflate_dropbits 2
        jmp     .mode_bad
    

        ; zlib_inflate_needbits:
        ; we smash ecx, edx
macro zlib_inflate_needbits n* {
        ; r12 == hold
        ; r13d == bits
        ; r14 == source pointer
        ; r15 == bytes remaining
        local   .getfour, .allgood
        cmp     r13d, n
        jae     .allgood
        cmp     r15, 4
        jae     .getfour
        ; less than 4 bytes remain, determine existing bits + (remaining bytes *  is >= n, else goto .inf_leave
        ; it will be safe here to pull a dword even if it is past the end of input
        mov     ecx, r13d
        mov     edx, dword [r14]
        shl     rdx, cl
        add     r12, rdx                ; add vs or makes no diff
        add     r14, r15                ; move pointer forward
        shl     r15d, 3
        add     r13d, r15d              ; number of bits we really added
        xor     r15d, r15d      ; no more bytes left
        cmp     r13d, n
        jae     .allgood
        jmp     .inf_leave
.getfour:
        mov     ecx, r13d
        mov     edx, dword [r14]
        shl     rdx, cl
        add     r12, rdx                ; add vs or makes no diff
        add     r13d, 32
        add     r14, 4
        sub     r15, 4
        ; fallthrough to allgood
.allgood:
}
    

macro zlib_inflate_dropbits n* {
        shr     r12, n
        sub     r13d, n
}
    

it ends up being pretty much the same amount of work in the end I spose..

BTW, isn't 12K too much for such an algorithm? My implementation is 1400 bytes (well after some size optimizations) and it inlines all inner loops code because of the speed optimizations. (Read it as "All code", because Inflate is actually one big inner loop )

So, after some optimization, my routine is now about 20% faster than gzip implementation and is under 1300 bytes in size, which I decided is good enough result.

@JohnFound - http://www.imfm.si/preprinti/PDF/00600.pdf

The paper describes a mutation of the huffman tree with an added code size based lookup table that can improve the performance.

I am not using zlib for testing. Simply have one big compressed file and use "time gzip -d testfile.gz" and "time TestDeflate" in order to test the speed. Notice that I am not handling zip or gz files formats. I am implementing only Inflate algorithm. My test program reads the compressed file, decompress it and writes the output file. And this is implemented only as a quick test code, not to be released as a gzip replacement. But all the integrity and error checks for the Deflate stream are implemented and working. My main goal is to provide the algorithm for using in PNG decoding library. That is why for now only Inflate part is implemented. Maybe later, some day, I will write Deflate as well, but not now.

CFLAGS="-O3 -DJOHNFOUND=1" ./configure    

make    

make distclean
./configure
make    

JOHNFOUND minigzip: time ./minigzip -d -c test.input.gz >/dev/null

real    0m0.760s
user    0m0.745s
sys     0m0.016s

REFERENCE version (aka gzip): time ./minigzip -d -c test.input.gz >/dev/null

real    0m1.259s
user    0m1.248s
sys     0m0.012s
    

Well, crc32 is much faster than the Inflate decoder, so I don't think there will be significant difference.

But still I am not trying to beat gzip. I only wanted to have a code with normal performance.

what is the fastest way