Skip site navigation (1)
Skip section navigation (2)
## Re: Block-level CRC checks

### In response to

### Responses

### pgsql-hackers by date

Brian Hurt wrote: > Paul Schlie wrote: >> >> ... if that doesn't fix >> the problem, assume a single bit error, and iteratively flip >> single bits until the check sum matches ... > This can actually be done much faster, if you're doing a CRC checksum > (aka modulo over GF(2^n)). Basically, an error flipping bit n will > always create the same xor between the computed CRC and the stored > CRC. So you can just store a table- for all n, an error in bit n will > create an xor of this value, sort the table in order of xor values, > and then you can do a binary search on the table, and get exactly what > bit was wrong. > > This is actually probably fairly safe- for an 8K page, there are only > 65536 possible bit positions. Assuming a 32-bit CRC, that means that > larger corrupts are much more likely to hit one of the other > 4,294,901,760 (2^32 - 2^16) CRC values- 99.998% likely, in fact. > Actually, I think I'm going to take this back. Thinking about it, the table is going to be large-ish (~512K) and it assumes a fixed 8K page size. I think a better solution would be a tight loop, something like: r = 1u; for (i = 0; i < max_bits_per_page; ++i) { if (r == xor_difference) { return i; } else if ((r & 1u) == 1u) { r = (r >> 1) ^ CRC_POLY; } else { r >>= 1; } } Brian

- Re: Block-level CRC checks at 2008-10-01 13:55:55 from Brian Hurt

- Re: Block-level CRC checks at 2008-10-01 15:03:15 from Paul Schlie

Next: From:Tom LaneDate:2008-10-01 14:11:09Subject: Re: Common Table Expressions (WITH RECURSIVE) patchPrevious: From: Greg StarkDate: 2008-10-01 14:03:37Subject: Re: Common Table Expressions (WITH RECURSIVE) patch