CRC32 functions in libbb

Rob Landley rob at landley.net
Sat Apr 8 02:08:01 UTC 2006


On Friday 07 April 2006 9:42 am, Rob Sullivan wrote:
> As a result of the discussion (
> http://www.busybox.net/lists/busybox/2006-March/019399.html) about placing
> a more flexible CRC32 implementation in libbb, I've got a working algorithm
> - it encompasses the CRC32 routines in both bunzip2 and gzip at least,

Is it smaller or larger than what we have now?

> and 
> should support 6 other types of CRC32.

Which we don't use.

> You use it by first generating a lookup table within the applet with the
> bb_crc32_filltable function, which takes the endian-ness desired as an
> argument. The table can then be passed along with the data to
> bb_crc32_calc, which actually calculates the CRC. I favour this over a
> global lookup table, as it keeps information separate for each applet - if
> gzip and bunzip2 were both running at the same time, for instance, each
> time one of them calculated a CRC the global table would have to be
> regenerated due to one being little-endian and the other being big-endian.

I looked at this and the end result was significantly _bigger_ than what we're 
doing now.

> Anyway, as there are only 2 CRC implementations in Busybox at the moment,
> it makes little difference having a table for each applet.
> bb_crc32_calc also allows initial values to be set (0 or ~0), and what to
> XOR the final CRC with (again 0 or ~0).

Do we need generic code for something that's three lines to do inline and 
shows up in a small number of places?

> I think that covers about 
> everything - here's a sample calculation of a big-endian CRC with initial
> value 0xffffffff (~0 on 32-bit) and no final XOR:

I suspect nm --size-sort is likely to say moving it out of line and adding a 
function call overhead makes it bigger than the code we've got now.  It's 
pretty small and there aren't enough uses of it to amortize a shared 
implementation over...

> unsigned long *table = bb_crc32_filltable(1);
> unsigned long crc = bb_crc32_calc("123456789", 9, table, 1, 1, 0);
>
> The patch to add these two functions to libbb is attached; any opinions? Is
> it too inflexible/flexible/unwieldy?

Could you give me a size comparison?  I already think I know the answer, but I 
could be wrong...

> Rob

Rob
-- 
Never bet against the cheap plastic solution.



More information about the busybox mailing list