1994.12.16 22:04 "Re: JBIG compression", by Rick Richardson

Also, can the current libtiff G4 decompression implementation be improved? What sort of improvements can be expected?

What's wrong with the current implementation?

The current implementation is fine, but.. I have in my hands a commercial product (no source) that does decompression in noticable less time. That suggests that there are faster ways to decompress G4 in software, alas my question.

I cannot speak for the G4 decompression in libtiff, but I can vouch for the fact that the libtiff G3 decompression is not as fast as at least my own implementation. However, I am not at liberty to provide the source code since it belongs to my employer.

In my experience with G3, I found the fastest way was to completely unroll the decompression. I tried numerous different 'elegant' algorithmic approaches over a period of about 3 years and discovered that the simple brute force unrolled approach was always fastest. The decoder itself is something like 700 lines of nested C language if-else statements.

I did not write those 700 lines, though. Instead, I wrote a program that wrote those lines for me. From time to time, I've been tempted to change the decoder-generator program to output assembler instead of C code. I think that would ultimately be the fastest possible implementation for any particular architecture (with the exception of a full lookup table which takes up an impractical amount of RAM on typical machines available today).

-- 
Rick Richardson        Senior Staff Engineer   Visit my WWW home page:
DigiBoard APD          Email: rick@digibd.com  http://www.digibd.com/people/rick
6801 Shady Oak Rd.     Fax:   (612) 947-1129   
Eden Prarie, MN 55344  Tel:   (612) 947-1111   <standard disclaimer>