Re: crc_fast: inefficiency

From: Daryle Walker (darylew_at_[hidden])
Date: 2001-03-22 19:45:42

on 3/21/01 4:54 AM, Reid Sweatman at reid_of_diamonds_at_[hidden] wrote:

> Probably right on that, but you can also get pretty fast byte reversals with
> a lookup table...unless that's how the code is already doing it; haven't
> looked.

No, I wasn't using lookup tables then.  Now I do use a table.  I build the
table using all possible byte values as indices.  When not using (input)
reflection, I compute the partial CRC for a given byte and store that CRC in
the table at that byte's index.  When using reflection, the partial CRC is
reflected and the table index used is the reflection of the given byte.

In the 15 days between Vladimir's message and yours, I published some new
versions.

>> -----Original Message-----
>> From: Vladimir Prus [mailto:ghost_at_[hidden]]
>> Sent: Tuesday, March 06, 2001 7:17 AM
>> To: boost_at_[hidden]
>> Subject: [boost] crc_fast: inefficiency
>> 
>> 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 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.

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