On Apr18, 2013, at 18:48 , Ants Aasma <a...@cybertec.at> wrote: > On Thu, Apr 18, 2013 at 5:57 PM, Ants Aasma <a...@cybertec.at> wrote: >> I'll generate an avalanche diagram for CRC32C too, but it will take a >> while even if I use a smaller dataset. > > Well that was useless... In CRC flipping each bit in the input flips > preset pattern of bits in the output regardless of the actual data on > the page. Some stats for CRC32C - input bits affect 28344 different > bit combinations. Count of bits by number of duplicated bitpatterns:
Yup, CRC is linear too. CRC is essentially long division for polynomials, i.e. you interpret the N input bits as the coefficients of a (large) polynomial of degree (N-1), and divide by the CRC polynomial. The remainder is the checksum, and consists of B bits where B is the degree of the CRC polynomial. (Polynomial here means polynomial over GF(2), i.e. over a field with only two values 0 and 1) I'm currently trying to see if one can easily explain the partial-write behaviour from that. Having lots of zeros at the end end corresponds to an input polynomial of the form p(x) * x^l where l is the number of zero bits. The CRC (q(x) is the CRC polynomial) is p(x) * x^l mod q(x) = (p(x) mod q(x)) * (x^l mod q(x)) mod q(x) That still doesn't explain it, though - the result *should* simply be the checksum of p(x), scrambled a bit by the multiplication with (x^l mod q(x)). But if q(x) is irreducible, that scrambling is invertible (as multiplication module some irreducible element always is), and thus shouldn't matter much. So either the CRC32-C polynomial isn't irreducible, or there something fishy going on. Could there be a bug in your CRC implementation? Maybe a mixup between big and little endian, or something like that? The third possibility is that I've overlooking something, of course ;-) Will think more about this tomorrow if time permits best regards, Florian Pflug -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers