Re: [PATCH RFC 01/17] lib/crc: add crc32c_flip_range() for incremental CRC update

[Eric Biggers <ebiggers@kernel.org>]

On Fri, May 08, 2026 at 08:15:23PM +0800, Baokun Li wrote:
> When a contiguous range of bits in a buffer is flipped, the CRC32c
> checksum can be updated incrementally without re-scanning the entire
> buffer, by exploiting the linearity of CRCs over GF(2):
> 
>   New_CRC = Old_CRC ^ CRC(flip_mask << trailing_bits)
> 
> Introduce crc32c_flip_range() which computes this delta using
> precomputed GF(2) shift matrices and nibble-indexed lookup tables.
> The implementation decomposes nbits and trailing_bits into
> power-of-2 components and combines them via the CRC concatenation
> property:
> 
>   CRC(A || B) = shift(CRC(A), len(B)) ^ CRC(B)
> 
> This gives O(log N) complexity with only ~9.8KB of static tables
> (fits in L1 cache).  The current maximum supported buffer size is
> 64KB (INCR_MAX_ORDER = 19, i.e. 2^19 bits = 524288 bits = 64KB).

It will be a little while before I can do a full review of this, but
just a high-level comment: "only ~9.8KB of static tables (fits in L1
cache)" isn't ideal.  Large tables tend to microbenchmark well, then
have worse real-world performance due to lots of other things contending
for the L1 cache.

Another consideration is that basically every Linux kernel has
CONFIG_CRC32 enabled, regardless of whether they would actually find
this new functionality useful.

I'm not necessarily saying this should be its own option, especially if
it's useful for ext4 even in the non-LBS case.  But I do think it would
be nice if it could be a bit smaller and more memory-optimized.

Anyway, I'll look into the algorithm more when I have time.

- Eric