Re: crc32() optimization

Wolfgang Denk
2002-11-10T20:30:27Z

In message <006901c288f4$79e2ce20$0200a8c0@telia.com> you wrote:
>
> What's "Duff's Device"?

It's a tricky way to implement general loop unrolling directly in C.
Applied to your problem, code that looks like this (instead of 8 any
other loop count may be used, but you need to adjust the "case"
statements then):

register int n = (len + (8-1)) / 8;

switch (len % 8) {
case 0: do { val = crc32_table ... ;
case 7: val = crc32_table ... ;
case 6: val = crc32_table ... ;
case 5: val = crc32_table ... ;
case 4: val = crc32_table ... ;
case 3: val = crc32_table ... ;
case 2: val = crc32_table ... ;
case 1: val = crc32_table ... ;
} while (--n > 0);
}

BTW: this is strictly legal ANSI C!

For an explanation see http://www.lysator.liu.se/c/duffs-device.html

Best regards,

Wolfgang Denk

--
Software Engineering: Embedded and Realtime Systems, Embedded Linux
Phone: (+49)-8142-4596-87 Fax: (+49)-8142-4596-88 Email: wd@denx.de
See us @ electronica 2002 in Munich, Nov 12-15, Hall A3, Booth A3.325