Re: crc_fast: inefficiency

From: Daryle Walker (darylew_at_[hidden])
Date: 2001-03-09 16:16:11

on 3/6/01 5:17 PM, Vladimir Prus at ghost_at_[hidden] wrote:

> crc_fast, despite its name, has a significant performance problem. Namely, if
> input is reversed, the code call a routine to reverse each byte. That
> bit-tossing routine is slow, and as far as I can tell, all practical
> implementation avoid reversing byte, but instread reverse everything else.

I just posted a new version (5) of "crc.zip" that reverses the computation
parameters instead of the byte.  I had to make some more implementation
helper classes, to extract or shift-out the remainder's highest byte (recall
that it's the LSB for reflected implementations, and the MSB for regular
ones).  It took me a while to figure out how to change the CRC table
computation routine (both the interim remainder and the index byte get
reflected) and how the internal reflection interacts with output reflection
(only need to output-reflect if the two reflection parameters are
different).

> I compared performance of current crc_fast with implementation that uses
> optimization mentioned above. On 1Meg buffer with random data crc_fast is 10
> times slower. Without bytes reversing, it's only 2 times slower. So, changing
> code seems worthwhile.

I wonder what this version speed will be.

-- 
Daryle Walker
Mac, Internet, and Video Game Junkie
darylew AT mac DOT com