Corner-case bug in Reed Solomon code?

[nasamaher]

Hi,

First, thanks for this great library. I'm just using the Reed Solomon part of it and I stumbled on I think a corner-case bug.

When using data+error_codes of size 256, if I corrupt the first byte (after ReedSolomon encoding), neither the byte is "repaired" nor an exception is thrown when decoding. It doesn't seem to matter how many error_codes I use or the data content, but it only fails for data+error_codes of size 256.

I grep'd the ReedSolomon code for literals 255 and 256 but saw nothing fishy.

Hmm, code formatter on this wiki not working for me. JUnit test below. Depends on RSEncoderDecoder class, which looks fine by inspection (attached as '.txt')
RSEncoderDecoder.txt

import java.util.Arrays;
import org.junit.Test;
import com.casualcoding.reedsolomon.RSEncoderDecoder;
public class ReedSolomonByte0Bug
{
@test
public void testRSStreamAllZeros() throws Exception
{
/*
* numEcBytes doesn't seem to matter
*/
int numEcBytes = 8;

    for (int totalBlockSizeBytes = 10; totalBlockSizeBytes <= 256; totalBlockSizeBytes++)
    {

        byte[] mesg = new byte[totalBlockSizeBytes - numEcBytes];

        for (int i = 0; i < mesg.length; i++)
        {
            mesg[i] = (byte) i;
        }

        RSEncoderDecoder rs = new RSEncoderDecoder();
        byte[] rsmesg = rs.encodeData(mesg, numEcBytes);

        /*
         * Corrupt byte 0.  Corrupting other bytes works correctly
         */
        rsmesg[0] = (byte) (rsmesg[0] + 1);

        // No exception thrown ...
        byte[] testDecode = rs.decodeData(rsmesg, numEcBytes);

        /*
         * Fails for totalBlockSize = 256
         */
        if (Arrays.equals(mesg, testDecode) == false)
        {
            System.out.println("Failed: totalBlockSizeBytes = " + totalBlockSizeBytes);
        }
    }
}

}

[srowen]

Here's a more direct version of your test:

    int numEcBytes = 8;
    for (int totalBlockSizeBytes = 9; totalBlockSizeBytes <= 256; totalBlockSizeBytes++) {
      int[] mesg = new int[totalBlockSizeBytes];
      for (int i = 0; i < mesg.length - numEcBytes; i++) {
        mesg[i] = i;
      }

      new ReedSolomonEncoder(GenericGF.QR_CODE_FIELD_256).encode(mesg, numEcBytes);
      mesg[0] += 1;
      new ReedSolomonDecoder(GenericGF.QR_CODE_FIELD_256).decode(mesg, numEcBytes);

      for (int i = 0; i < mesg.length - numEcBytes; i++) {
        Assert.assertEquals("totalBlockSizeBytes, i = " + totalBlockSizeBytes + ", " + i, i, mesg[i]);
      }
    }

I don't think this a bug though. You're using a field with 256 elements (I presume) and so the error locator can't express more than 256 distinct error locations. Your input has 257 elements though.

Try using a different field like AZTEC_DATA_10 and it will all work.

[srowen]

Hm, not quite; the failure occurs at 256 elements, not 257. I suspect my answer is still roughly correct, but the subtlety of why it works only at 255 elements is beyond me in looking at this for 15 minutes. It may still be a corner case bug, yeah, but maybe narrower than it seems.