Re: crc32() optimization

["Joakim Tjernlund" <Joakim.Tjernlund@lumentis.se>]

hmm , maybe. I tried 16, 8 & 4 also, but 6 was a little faster for me.
What would be great if someone that understands CRC better than me could
take a look at Algorithm 4 at http://www.cl.cam.ac.uk/Research/SRG/bluebook/21/crc/node6.html#SECTION00060000000000000000
and apply that on linux CRC32 code.  I tried but failed to get it correct.

        Jocke

> As it should.  I wonder if you'd do better changing the loop slightly.
> 
> Check for len == 0 and do a short-circuit return.  Then do this
> 
>   for (++len; len & 0x7; len >>= 3) {
>      ONCE(); // repeat eight times
>      ...
>      len >>= 3;
>   }
>   while (--len > 0)
>      ONCE();
> 
> This is the implementation I've written for another project which
> we've found to be relatively optimal.  Note that len *must* be an int
> even though contemporary convention is to use the size_t type.
> 
> 
> On Sun, Nov 10, 2002 at 04:28:00PM +0100, Joakim Tjernlund wrote:
> > Hi David
> > 
> > This patch improves my scan time with 22%( from 2.39 to 1.86 seconds).
> > Maybe you want to include it in the 2.4 branch.
> > 
> > I will put this in my next backport of the crc32 stuff from 2.5.
> > 
> >           Jocke
> > 
> > Index: fs/jffs2/crc32.h
> > ===================================================================
> > RCS file: /home/cvs/mtd/fs/jffs2/crc32.h,v
> > retrieving revision 1.3
> > diff -u -b -r1.3 crc32.h
> > --- fs/jffs2/crc32.h    26 Feb 2001 14:44:37 -0000      1.3
> > +++ fs/jffs2/crc32.h    10 Nov 2002 15:25:11 -0000
> > @@ -13,7 +13,16 @@
> >  crc32(__u32 val, const void *ss, int len)
> >  {
> >         const unsigned char *s = ss;
> > -        while (--len >= 0)
> > +        while (len >= 6){
> > +         val = crc32_table[(val ^ *s++) & 0xff] ^ (val >> 8);
> > +         val = crc32_table[(val ^ *s++) & 0xff] ^ (val >> 8);
> > +         val = crc32_table[(val ^ *s++) & 0xff] ^ (val >> 8);
> > +         val = crc32_table[(val ^ *s++) & 0xff] ^ (val >> 8);
> > +         val = crc32_table[(val ^ *s++) & 0xff] ^ (val >> 8);
> > +         val = crc32_table[(val ^ *s++) & 0xff] ^ (val >> 8);
> > +         len -= 6;
> > +        }
> > +        while (len--)
> >                  val = crc32_table[(val ^ *s++) & 0xff] ^ (val >> 8);
> >          return val;
> >  }
> > 
> > 
> > ______________________________________________________
> > Linux MTD discussion mailing list
> > http://lists.infradead.org/mailman/listinfo/linux-mtd/
> 
> ______________________________________________________
> Linux MTD discussion mailing list
> http://lists.infradead.org/mailman/listinfo/linux-mtd/