RE: [PATCH] add slice by 8 algorithm to crc32.c

["Bob Pearson" <rpearson@systemfabricworks.com>]

> -----Original Message-----
> From: linux-kernel-owner@vger.kernel.org [mailto:linux-kernel-
> owner@vger.kernel.org] On Behalf Of George Spelvin
> Sent: Monday, August 08, 2011 3:45 PM
> To: joakim.tjernlund@transmode.se; linux@horizon.com;
> rpearson@systemfabricworks.com
> Cc: akpm@linux-foundation.org; fzago@systemfabricworks.com; linux-
> kernel@vger.kernel.org
> Subject: RE: [PATCH] add slice by 8 algorithm to crc32.c
> 
> > Happy to consider this. I have been asking the list for comments about
the
> > idea of dropping the BITS=2 and BITS=4 algorithms altogether which would
> > make the table size just 256. So far no one has claimed that they
actually
> > care about those algorithms except as 'examples'. The 'Sarwate'
algorithm
> > (which I added as an 8 bit version) is faster and only adds 2x4KB of
table.
> 
> Um, I thought the Sarwate agorithm was what was already there as BITS=8.
> (The original paper stores the CRC in two 8-bit variables and two
> 8-bit tables rather than using 16-bit words, but other than that,
> it's identical.)

In the current i.e. original version of crc32.c BITS=8 is the 32 bit
algorithm. The Sarwate version is not used. In the patched version that was
moved to BITS=32 and another one slipped in as BITS=8 which is Sarwate.

> 
> And that requires just 1KB of table per endianness.

You're right! Its 2X1KB not 2X4KB. There are 2 tables (le and be).

> 
> Anyway, I thought the complaint about laarge tables was
> not so much the memory as the L1 cache pollution. 

As far as performance goes cache pollution is the more important effect.
That is why you can't just extend the 2, 4, 8 sequence which has the tables
growing exponentially with BITS. The Slicing-by-N algorithm though has table
size growing linearly with N. But, if you are trying to run Linux on a small
embedded CPU even linear table size might be important. Back in the good old
days you could strip Linux down to a very small kernel.

> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/