|
QuickCppLib 0.10
Eliminate all the tedious hassle when making state-of-the-art C++ 14 - 23 libraries!
|
Calculates the single error correcting Hamming Error Correcting Code for a blocksize block of bytes. For example, a hamming_ecc<8> would be the very common 72,64 Hamming code used in ECC RAM, or a hamming_ecc<4096> would be for a 32784,32768 Hamming code. More...
#include "hamming_ecc.hpp"
Public Types | |
| enum | verify_status { corrupt = 0 , okay = 1 , healed = 2 } |
| The outcomes from verify(). More... | |
| typedef unsigned int | result_type |
| The largest ECC which can be calculated. | |
Public Member Functions | |
| constexpr | hamming_ecc () |
| Constructs an instance, configuring the necessary lookup tables. | |
| constexpr result_type | result_bits_valid () const noexcept |
| The number of bits valid in result_type. | |
| result_type | operator() (result_type ecc, const char *buffer) const noexcept |
| Accumulate ECC from fixed size buffer. | |
| result_type | operator() (result_type ecc, const char *buffer, size_t length) const noexcept |
| Accumulate ECC from partial buffer where length <= blocksize. | |
| result_type | operator() (const char *buffer) const noexcept |
| result_type | operator() (const char *buffer, size_t length) const noexcept |
| result_type | find_bad_bit (result_type good_ecc, result_type bad_ecc) const noexcept |
| verify_status | verify (char *buffer, result_type good_ecc) const noexcept |
Calculates the single error correcting Hamming Error Correcting Code for a blocksize block of bytes. For example, a hamming_ecc<8> would be the very common 72,64 Hamming code used in ECC RAM, or a hamming_ecc<4096> would be for a 32784,32768 Hamming code.
The number of parity bits is chosen by the plain Hamming condition (data bits + parity bits + 1) <= 2^parity bits. That is all this class appends: there is no additional overall-parity bit, and therefore no double error detection. To be unambiguous about what you are getting:
Therefore you MUST combine this with a strong hash or checksum over the data (as this documentation has always recommended), and you must not use its return value to conclude that a block is intact. The only sound use is to repair a single flipped bit cheaply once a hash has already told you that something is wrong; it must never be the thing which tells you that a block is fine.
A true SECDED code would need one extra overall-parity bit, which raises result_bits_valid() and changes the wire format of every stored ECC. That is deliberately not implemented: this class has no production users, so an honest name and this documentation are worth more than a new code format.
Did you know that some non-ECC RAM systems can see 1e-12 flips/bit/hour, which is 3.3 bits flipped in a 16Gb RAM system per 24 hours). See Schroeder, Pinheiro and Weber (2009) 'DRAM Errors in the Wild: A Large-Scale Field Study'.
After construction during which lookup tables are built, no state is modified and therefore this class is safe for static storage (indeed if C++ 14 is available, the constructor is constexpr). The maximum number of bits in a code is a good four billion, I did try limiting it to 65536 for performance but it wasn't worth it, and one might want > 8Kb blocks maybe. As with any single error correcting Hamming code, an ECC which is itself incorrect, or a block with more than one bad bit, is not reliably reported as such - see the section above, which is why you must combine this with a robust hash which can tell you definitively if a buffer is error free or not rather than relying on this to do so.
The main intended use case for this routine is calculating the ECC on data being written to disc, and hence that is where performance has been maximised. It is not expected that this routine will be frequently called on data being read from disc i.e. only when its hash doesn't match its contents which should be very rare, and then a single bit heal using this routine is attempted before trying again with the hash. Care was taken that really enormous codes are fast, in fact tuning was mostly done for the 32784,32768 code which can heal one bad bit per 4Kb page as the main thing we have in mind is achieving reliable filing system code on computers without ECC RAM and in which sustained large quantities of random disc i/o produce a worrying number of flipped bits in a 24 hour period (anywhere between 0 and 3 on my hardware here, average is about 0.8).
For a Skylake CPU:
Note that better than 1Gb/sec is easily possible if I rewrite the implementation.
| typedef unsigned int quickcpplib::_xxx::algorithm::hamming_ecc::hamming_ecc< blocksize >::result_type |
The largest ECC which can be calculated.
| enum quickcpplib::_xxx::algorithm::hamming_ecc::hamming_ecc::verify_status |
The outcomes from verify().
|
inlineconstexpr |
Constructs an instance, configuring the necessary lookup tables.
|
inlineconstexprnoexcept |
The number of bits valid in result_type.
|
inlinenoexcept |
Accumulate ECC from fixed size buffer.
|
inlinenoexcept |
Accumulate ECC from partial buffer where length <= blocksize.
|
inlinenoexcept |
|
inlinenoexcept |
|
inlinenoexcept |
Given the original ECC and the new ECC for a buffer, find the bad bit. Return (result_type)-1 if not found (e.g. ECC corrupt)
|
inlinenoexcept |
Verifies and heals when possible a buffer. A non-zero return does NOT prove the buffer is error free: a two bit error is normally reported as healed - see the class documentation.