QuickCppLib 0.10
Eliminate all the tedious hassle when making state-of-the-art C++ 14 - 23 libraries!
Loading...
Searching...
No Matches
quickcpplib::_xxx::algorithm::hamming_ecc::hamming_ecc< blocksize > Class Template Reference

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

Detailed Description

template<size_t blocksize>
class quickcpplib::_xxx::algorithm::hamming_ecc::hamming_ecc< blocksize >

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.

This is a Hamming code, NOT a SECDED 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:

  • It corrects a single flipped bit within one block.
  • It does NOT detect a double bit error. A one bit and a two bit error both produce a syndrome which is the XOR of the positions in error, so for a two bit error at positions a and b the syndrome names some third position c. verify() flips c, which turns the block into a different but perfectly valid codeword, so its own re-check passes and it reports healed on data which no longer matches the original. Wrong data is returned with a success status, silently.
  • A three bit error can also land on a valid codeword (three positions XOR into one), and larger counts are no better behaved. So it is NOT true that only "more than two bits" of error is undefined: there is no error count above one which this code reports as corruption reliably.

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.

Warning
This class needs to be completely reimplemented using SSE and AVX. Its current implementation works fine, but performance is far below what it can be.

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).

Performance notes of this current implementation:

For a Skylake CPU:

  • MSVC Fixed buffer: 125.719 Mb/sec, or 23.48 cycles/byte
  • MSVC Variable buffer: 144.167 Mb/sec, or 20.48 cycles/byte
  • MSVC heal: 80.4498 Mb/sec
  • GCC7 Fixed buffer: 201.509 Mb/sec, or 14.65 cycles/byte
  • GCC7 Variable buffer: 317.97 Mb/sec, or 9.28 cycles/byte
  • GCC7 heal: 126.099 Mb/sec
  • cla6 Fixed buffer: 276.962 Mb/sec, or 10.66 cycles/byte
  • cla6 Variable buffer: 210.248 Mb/sec, or 14.04 cycles/byte
  • cla6 heal: 171.174 Mb/sec

Note that better than 1Gb/sec is easily possible if I rewrite the implementation.

Complexity
O(N) where N is the blocksize
Errors returnable
Throws constexpr exceptions in constructor only, otherwise entirely noexcept.

Member Typedef Documentation

◆ result_type

template<size_t blocksize>
typedef unsigned int quickcpplib::_xxx::algorithm::hamming_ecc::hamming_ecc< blocksize >::result_type

The largest ECC which can be calculated.

Member Enumeration Documentation

◆ verify_status

The outcomes from verify().

Enumerator
corrupt 

The ECC was invalid, or the syndrome named no data bit (e.g. a parity bit itself was wrong). This is NOT a double error report - most two bit errors return healed instead.

okay 

The ECC of the buffer matched the ECC supplied.

healed 

A single bit was flipped to make the ECC match. Beware that a two bit error is also flipped into a different valid codeword and reported as healed, so this does not mean the buffer was repaired.

432 {
433 corrupt = 0, //!< The ECC was invalid, or the syndrome named no data bit (e.g. a parity bit itself was wrong).
434 //!< This is NOT a double error report - most two bit errors return `healed` instead.
435 okay = 1, //!< The ECC of the buffer matched the ECC supplied
436 healed = 2 //!< A single bit was flipped to make the ECC match. Beware that a two bit error is also flipped
437 //!< into a different valid codeword and reported as healed, so this does not mean the buffer
438 //!< was repaired.
439 };
@ okay
The ECC of the buffer matched the ECC supplied.
Definition hamming_ecc.hpp:435

Constructor & Destructor Documentation

◆ hamming_ecc()

template<size_t blocksize>
quickcpplib::_xxx::algorithm::hamming_ecc::hamming_ecc< blocksize >::hamming_ecc ( )
inlineconstexpr

Constructs an instance, configuring the necessary lookup tables.

184 {
185 for(size_t n = 0; n < sizeof(result_type) * bits_per_byte; n++)
186 ecc_twospowers[n] = ((result_type) 1 << n);
187 result_type length = blocksize * bits_per_byte;
188 // This is (data bits + parity bits + 1) <= 2^(parity bits)
189 for(result_type p = 1; p < sizeof(result_type) * bits_per_byte; p++)
190 if((length + p + 1) <= ecc_twospowers[p])
191 {
192 bitsvalid = p;
193 break;
194 }
195 if((bits_per_byte - 1 + bitsvalid) / bits_per_byte > sizeof(result_type))
196#ifdef __cpp_exceptions
197 throw std::runtime_error("hamming_ecc: ECC would exceed the size of result_type!");
198#else
199 abort();
200#endif
201 for(result_type i = 0; i < blocksize * bits_per_byte; i++)
202 {
203 // Make a code bit
204 result_type b = i + 1;
205#if QUICKCPPLIB_HAMMING_INTRINSICS && 0 // let constexpr do its thing
206#ifdef _MSC_VER
207 unsigned long _topbit;
210#else
211 result_type topbit = bits_per_byte * sizeof(result_type) - __builtin_clz(b);
212#endif
213 b += topbit;
214 if(b >= ecc_twospowers[topbit])
215 b++;
216// while(b>ecc_twospowers(_topbit+1)) _topbit++;
217// b+=_topbit;
218// if(b>=ecc_twospowers(_topbit)) b++;
219#else
220 for(size_t p = 0; ecc_twospowers[p] < (b + 1); p++)
221 b++;
222#endif
223 ecc_table[i] = (unsigned short) b;
224 if(b > (unsigned short) -1)
225#ifdef __cpp_exceptions
226 throw std::runtime_error("hamming_ecc: Precalculated table has exceeded its bounds");
227#else
228 abort();
229#endif
230 }
231 }
Calculates the single error correcting Hamming Error Correcting Code for a blocksize block of bytes....
Definition hamming_ecc.hpp:130
unsigned int result_type
The largest ECC which can be calculated.
Definition hamming_ecc.hpp:132

Member Function Documentation

◆ result_bits_valid()

template<size_t blocksize>
result_type quickcpplib::_xxx::algorithm::hamming_ecc::hamming_ecc< blocksize >::result_bits_valid ( ) const
inlineconstexprnoexcept

The number of bits valid in result_type.

233{ return bitsvalid; }

◆ operator()() [1/4]

template<size_t blocksize>
result_type quickcpplib::_xxx::algorithm::hamming_ecc::hamming_ecc< blocksize >::operator() ( result_type ecc,
const char * buffer ) const
inlinenoexcept

Accumulate ECC from fixed size buffer.

237 {
238#ifdef _MSC_VER
239#pragma warning(push)
240#pragma warning(disable : 4127) // conditional expression is constant
241#endif
242 if(blocksize < sizeof(unit_type) * 8)
243 return (*this)(ecc, buffer, blocksize);
244#ifdef _MSC_VER
245#pragma warning(pop)
246#endif
247 // Process in lumps of eight
248 const unit_type *_buffer = (const unit_type *) buffer;
249 // #pragma omp parallel for reduction(^:ecc)
250 size_t i = 0;
251 for(; i + sizeof(unit_type) * 8 <= blocksize; i += sizeof(unit_type) * 8)
252 {
253 union
254 {
255 unsigned long long v;
256 unit_type c[8];
257 };
259 v = *(unsigned long long *) (&_buffer[0 + i / sizeof(unit_type)]); // min 1 cycle
260#define QUICKCPPLIB_HAMMING_ROUND(n) \
261 prefetch[0] = ecc_table[(i + 0) * 8 + n]; \
262 prefetch[1] = ecc_table[(i + 1) * 8 + n]; \
263 prefetch[2] = ecc_table[(i + 2) * 8 + n]; \
264 prefetch[3] = ecc_table[(i + 3) * 8 + n]; \
265 prefetch[4] = ecc_table[(i + 4) * 8 + n]; \
266 prefetch[5] = ecc_table[(i + 5) * 8 + n]; \
267 prefetch[6] = ecc_table[(i + 6) * 8 + n]; \
268 prefetch[7] = ecc_table[(i + 7) * 8 + n]; \
269 if(c[0] & ((unit_type) 1 << n)) \
270 ecc ^= prefetch[0]; \
271 if(c[1] & ((unit_type) 1 << n)) \
272 ecc ^= prefetch[1]; \
273 if(c[2] & ((unit_type) 1 << n)) \
274 ecc ^= prefetch[2]; \
275 if(c[3] & ((unit_type) 1 << n)) \
276 ecc ^= prefetch[3]; \
277 if(c[4] & ((unit_type) 1 << n)) \
278 ecc ^= prefetch[4]; \
279 if(c[5] & ((unit_type) 1 << n)) \
280 ecc ^= prefetch[5]; \
281 if(c[6] & ((unit_type) 1 << n)) \
282 ecc ^= prefetch[6]; \
283 if(c[7] & ((unit_type) 1 << n)) \
284 ecc ^= prefetch[7];
285 QUICKCPPLIB_HAMMING_ROUND(0) // prefetch = min 8, bit test and xor = min 16, total = 24
293#undef QUICKCPPLIB_HAMMING_ROUND // total should be 1+(8*24/3)=65
294 }
295 // When blocksize is not a multiple of eight the lump loop above used to
296 // read up to seven bytes past the end of the caller's buffer and index
297 // ecc_table past blocksize*bits_per_byte, i.e. a heap over-read of BOTH
298 // (reviewer P0 r3:F1). Finish any tail byte-wise - with THIS byte's
299 // table offset, which is why it cannot be delegated to the
300 // partial-buffer overload (that one always starts at offset zero and
301 // would silently compute the wrong ECC).
302 for(; i < blocksize; i++)
303 {
304 unit_type c = _buffer[i];
305 if(!c)
306 continue;
308 for(size_t n = 0; n < bits_per_byte * sizeof(unit_type); n++)
309 if(c & ((unit_type) 1 << n))
310 localecc ^= ecc_table[i * bits_per_byte + n];
311 ecc ^= localecc;
312 }
313 return ecc;
314 }
#define QUICKCPPLIB_HAMMING_ROUND(n)

◆ operator()() [2/4]

template<size_t blocksize>
result_type quickcpplib::_xxx::algorithm::hamming_ecc::hamming_ecc< blocksize >::operator() ( result_type ecc,
const char * buffer,
size_t length ) const
inlinenoexcept

Accumulate ECC from partial buffer where length <= blocksize.

317 {
318 const unit_type *_buffer = (const unit_type *) buffer;
319 // #pragma omp parallel for reduction(^:ecc)
320 for(size_t i = 0; i < length; i += sizeof(unit_type))
321 {
322 unit_type c = _buffer[i / sizeof(unit_type)]; // min 1 cycle
323 if(!c) // min 1 cycle
324 continue;
325 char bitset[bits_per_byte * sizeof(unit_type)];
326 result_type prefetch[bits_per_byte * sizeof(unit_type)];
327 // Most compilers will roll this out
328 for(size_t n = 0; n < bits_per_byte * sizeof(unit_type); n++) // min 16 cycles
329 {
330 bitset[n] = !!(c & ((unit_type) 1 << n));
331 prefetch[n] = ecc_table[i * bits_per_byte + n]; // min 8 cycles
332 }
334 for(size_t n = 0; n < bits_per_byte * sizeof(unit_type); n++)
335 {
336 if(bitset[n]) // min 8 cycles
337 localecc ^= prefetch[n]; // min 8 cycles
338 }
339 ecc ^= localecc; // min 1 cycle. Total cycles = min 43 cycles/byte
340 }
341 return ecc;
342 }

◆ operator()() [3/4]

template<size_t blocksize>
result_type quickcpplib::_xxx::algorithm::hamming_ecc::hamming_ecc< blocksize >::operator() ( const char * buffer) const
inlinenoexcept
411{ return (*this)(0, buffer); }

◆ operator()() [4/4]

template<size_t blocksize>
result_type quickcpplib::_xxx::algorithm::hamming_ecc::hamming_ecc< blocksize >::operator() ( const char * buffer,
size_t length ) const
inlinenoexcept
412{ return (*this)(0, buffer, length); }

◆ find_bad_bit()

template<size_t blocksize>
result_type quickcpplib::_xxx::algorithm::hamming_ecc::hamming_ecc< blocksize >::find_bad_bit ( result_type good_ecc,
result_type bad_ecc ) const
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)

416 {
417 result_type length = blocksize * bits_per_byte, eccdiff = good_ecc ^ bad_ecc;
418 if(_is_single_bit_set(eccdiff))
419 return (result_type) -1;
420 for(result_type i = 0, b = 1; i < length; i++, b++)
421 {
422 // Skip parity bits
423 while(_is_single_bit_set(b))
424 b++;
425 if(b == eccdiff)
426 return i;
427 }
428 return (result_type) -1;
429 }

◆ verify()

template<size_t blocksize>
verify_status quickcpplib::_xxx::algorithm::hamming_ecc::hamming_ecc< blocksize >::verify ( char * buffer,
result_type good_ecc ) const
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.

443 {
444 result_type this_ecc = (*this)(0, buffer);
445 if(this_ecc == good_ecc)
446 return verify_status::okay; // no errors
448 if((result_type) -1 == badbit)
449 return verify_status::corrupt; // parity corrupt?
450 buffer[badbit / bits_per_byte] ^= (unsigned char) ecc_twospowers[badbit % bits_per_byte];
451 this_ecc = (*this)(0, buffer);
452 if(this_ecc == good_ecc)
453 return healed; // error healed
454 // Put the bit back
455 buffer[badbit / bits_per_byte] ^= (unsigned char) ecc_twospowers[badbit % bits_per_byte];
456 return verify_status::corrupt; // more than one bit was corrupt
457 }
result_type find_bad_bit(result_type good_ecc, result_type bad_ecc) const noexcept
Definition hamming_ecc.hpp:415

The documentation for this class was generated from the following file: