More Bugs during Decoding adds More error to data

[JohnMcJohn]

Thanks for the explanation from issue 7

However it seems you don't quiet understand how Reed Solomon codes work.

There are two distinct properties of an RS code (lets not even consider erasures at this time.):

1. The number of errors the code can DETECT
2. The number of errors the code can CORRECT

Your library does not correctly handle the case of a 2 error detecting 1 error correcting code as described in the following piece of code:

#include <string>
#include <iostream>

#include "ezpwd/rs"

int main()
{
     ezpwd::RS<255,253> rs;
     std::string orig(253,' ');
     std::string copy = orig;
     rs.encode( copy );
     copy[3] = 'x';
     copy[4] = 'x';
     int count = rs.decode( copy );
     copy.resize( copy.size() - rs.nroots() );
     if ( copy != orig ) {
         std::cout << "Failed to restore origin data." << std::endl;
     }
     return 0;
}

Your library not only does not given an indication to failure of the decode operation but It further ADDS more ERRORS to the message. It may not have been able to correct the errors, but it should be able to detect the fact that there are errors, and at the very least it should not add more errors, perhaps just leave it alone or something similar. Do you not agree that is a reasonable response?

I believe this to be not only a bug but a serious implementation issue. I tried to read the code, but it is so messy I could not make heads or tails of whats going on.

It looks like the code has been rearranged in such a way to look extremely difficult to understand or to look very different from some other reasonable form. Also if Tab's were the issue, if they were consistent in the code, would it matter if one had 4 or 8 or 17 spaces set, it should look readable at least.

Note: Please do not close this issue until at least you understand what is going on. I think you want to fix this problem, but given the previous response I do not think you quite understand how RS codes work and as a result are forced to provide elongated and somewhat nonsensical explanations about why the buggy behavior is correct in your opinion.

[pjkundert]

Hi, John!

This is free software (free, as in GPL)! So, of course you don't have to use it if disappoints you in any way!

There exist error checking codes that can "correct" 1 and "detect" 2 bit errors. Reed Solomon is not like that. When the error detection/correction threshold is exceeded, the algorithm will (with a certain probability), locate a "nearby" Reed-Solomon codeword, and will correct the codeword to that. You can calculate precisely the probabilities of this occurring, depending on error load (once again, from the output of rsvalidate. Very often, the R-S codec will (correctly) reject an invalid codeword (one with too many errors) as uncorrectable. But, with a certain probability, it will recover to a nearby codeword.

In order to properly apply Reed Solomon, you must use other means to (try to) ensure that your error load stays below the maximum threshold for the R-S codec. Only then, will you retain any assurance that your data was recovered correctly. As soon as you exceed the error capacity threshold for the R-S codec -- you're toast. You cannot guarantee detection.

As for Reed Solomon; I didn't write these algorithms. I'm not that smart! You can thank the mighty Phil Karn. I simply transposed the algorithms written by him (and tested by me in a massive industrial setting over more than a decade), that are used directly in the Linux Kernel, to C++, and added some simple wrappers. In addition, I added detection of a corner-case that Phil's (wonderful) implementation didn't directly detect.

So, if you want to take Phil to task for his algorithms -- be my guest. I wouldn't recommend it. He'd eat you (and me), for lunch.

If you view the Linux Kernel code with your editor, and it doesn't look precisely like it does for Linus Torvalds (because you set your tab stops to something other than 8) -- then I would say that it is you that is wrong, not Linus. Or any other classic code writer. Tabs stops are every 8 columns.

Finally; you haven't engaged me to provide services to you. So, I would be happy if you would temper your tone to avoid the implication that I am "wronging" you somehow.

Cheers,