False Positives

[meerd]

Hello @brian-armstrong and others,

I am still evaluating libcorrect for one of my projects. In the application, an eight-byte payload exists, and it consists of 4 bytes data + 4 bytes RS error correction code. Please see my test code below. There are three functions:

1st - A basic encoding/decoding code that works as expected. 2nd - This function works on five different payloads. Some bits of the payloads corrupted, but all of them are expected to recover. The library successfully decodes these payloads as expected. 3rd - This function encodes five different data (all is 4 bytes long) and obtains payloads. (4 bytes + 4 bytes = 8 bytes) Then, in the code, I intentionally distort ECC part of the payload. The expected behavior would be seeing all with decoding errors, but interestingly the library successfully decodes 3 of 5 payloads.

Is it a bug? Or am I doing something wrong?

Looking forward to seeing your feedback.

Thanks in advance. meerd

---

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>

#include <correct.h>

/* ################################ ========================================= */

#define DATA_LENGTH     4
#define ECC_LENGTH      4
#define PAYLOAD_LENGTH  (DATA_LENGTH + ECC_LENGTH)

#define SAMPLE_COUNT   5

#define dump_bytes(msg, buf, size) \
    do { \
        unsigned int ctr_dump_bytes = 0; \
        printf("| %s | = ", msg); \
        for (; ctr_dump_bytes < (size); ++ctr_dump_bytes) \
            printf("0x%02x ", ((uint8_t *)(buf))[ctr_dump_bytes]); \
        printf("\n"); \
    } while (0)

/* ################################ ========================================= */
/* A simple encode & decode test. */
/* ################################ ========================================= */
void rs_test1(correct_reed_solomon *ctx)
{
    const uint8_t data[DATA_LENGTH]                 = { 0xde, 0xad, 0xbe, 0xef };
    const uint8_t expected_payload[PAYLOAD_LENGTH]  = { 0xde, 0xad, 0xbe, 0xef, 0x83, 0x86, 0xc9, 0xee }; 
    uint8_t encoded[PAYLOAD_LENGTH]                 = { 0x00 };
    uint8_t decoded[PAYLOAD_LENGTH]                 = { 0x00 };
    ssize_t result; 

    fprintf(stdout, "Running %s...\n", __FUNCTION__); 

    dump_bytes("Encoded bytes:", encoded, PAYLOAD_LENGTH);
    /* Compare */
    result = correct_reed_solomon_encode(ctx, data, DATA_LENGTH, encoded);
    /* 255 is returned by the library */
    assert(255 == result);

    /* Compare the expected output with encoded buffer.  */
    result = memcmp(expected_payload, encoded, PAYLOAD_LENGTH);
    dump_bytes("Encoded bytes:", encoded, PAYLOAD_LENGTH);
    assert(0 == result);

    /* Decode the encoded buffer. */
    result = correct_reed_solomon_decode(ctx, encoded, PAYLOAD_LENGTH, decoded);
    /* See if the remaining bytes are still zero. */
    dump_bytes("Decoded bytes:", decoded, PAYLOAD_LENGTH);
    assert(DATA_LENGTH == result);

    /* Compare the decoded buffer with the original data. */
    result = memcmp(data, decoded, DATA_LENGTH);
    assert(result == 0);

    fprintf(stdout, "###################################\n");
    fprintf(stdout, "%s passed!\n", __FUNCTION__); 
    fprintf(stdout, "###################################\n");
}

/* ################################ ========================================= */
/* Some of the payloads includes errors, but all should be able to be recovered. */
/* ################################ ========================================= */

void rs_test2(correct_reed_solomon *ctx)
{
    uint8_t recoverable_payload[SAMPLE_COUNT][PAYLOAD_LENGTH] = { 
                                                                   { 0x11, 0x11, 0x11, 0x11, 0x6a, 0xec, 0x1b, 0x9d },
                                                                   { 0x56, 0xd4, 0xaa, 0xe3, 0x19, 0x90, 0xac, 0xee },
                                                                   { 0xff, 0xff, 0xff, 0xff, 0x1c, 0x8d, 0x99, 0x60 },
                                                                   { 0xaa, 0x00, 0xaa, 0xaa, 0xa3, 0xf6, 0x00, 0xbb },
                                                                   { 0x24, 0x00, 0x38, 0x90, 0x8b, 0x71, 0xff, 0x76 }
                                                                };
    int failure = 0;
    int i;

    fprintf(stdout, "Running %s...\n", __FUNCTION__); 

    for (i = 0; i < SAMPLE_COUNT; ++i) {
        uint8_t buf[DATA_LENGTH] = { 0x00 };
        ssize_t result = correct_reed_solomon_decode(ctx, recoverable_payload[i], PAYLOAD_LENGTH, buf);

        failure += (DATA_LENGTH != result);
        fprintf(stdout, "Decoding result for distorted input (idx: %d): %s\n", i, ((DATA_LENGTH == result) ? "SUCCESS" : "FAILURE")) ;
    }    

    fprintf(stdout, "###################################\n");
    /* If no failures has been detected so far, then the test passed! */
    if (0 == failure)
        fprintf(stdout, "%s passed!\n", __FUNCTION__);
    else
        fprintf(stdout, "%s FAILED!\n", __FUNCTION__);
    fprintf(stdout, "###################################\n");
}

/* ################################ ========================================= */
/* The last four bytes of all payloads distorted intentionally. All of the 
 * decoding attempts are expected to fail. */
/* ################################ ========================================= */
void rs_test3(correct_reed_solomon *ctx)
{

    uint8_t sample_data[SAMPLE_COUNT][DATA_LENGTH] = { 
                                                        { 0xaa, 0xaa, 0xaa, 0xaa }, 
                                                        { 0xff, 0xff, 0xff, 0xff },
                                                        { 0x4f, 0xf3, 0x89, 0x18 },
                                                        { 0x12, 0x34, 0x56, 0x78 },
                                                        { 0x24, 0xff, 0x38, 0x90 }
                                                     };

    uint8_t expected_payload[SAMPLE_COUNT][PAYLOAD_LENGTH] = {
                                                                { 0xaa, 0xaa, 0xaa, 0xaa, 0xa3, 0xf6, 0xee, 0xbb },
                                                                { 0xff, 0xff, 0xff, 0xff, 0x7c, 0x8d, 0x99, 0x68 },
                                                                { 0x4f, 0xf3, 0x89, 0x18, 0x31, 0x23, 0x07, 0x38 },
                                                                { 0x12, 0x34, 0x56, 0x78, 0x54, 0x56, 0x20, 0x2a },
                                                                { 0x24, 0xff, 0x38, 0x90, 0x8b, 0x71, 0xff, 0x76 }
                                                            };

    uint8_t distorted_ecc[SAMPLE_COUNT][ECC_LENGTH] = {
                                                        { 0x00, 0x00, 0x00, 0x00 },
                                                        { 0xff, 0xff, 0xff, 0xff },
                                                        { 0xb7, 0x1f, 0xff, 0x75 },
                                                        { 0xff, 0xff, 0xff, 0xff },
                                                        { 0x8b, 0x71, 0xff, 0x76 }
                                                     };

    int failure = 0;

    uint8_t buf[PAYLOAD_LENGTH];
    int i;

    fprintf(stdout, "Running %s...\n", __FUNCTION__); 

    for (i = 0; i < SAMPLE_COUNT; ++i) {
        /* Clean the contents */
        memset(buf, 0x00, sizeof(buf));
        /* Encode sample_data[i] */

        ssize_t result = correct_reed_solomon_encode(ctx, sample_data[i], DATA_LENGTH, buf);

        assert(255 == result);

        fprintf(stdout, "Checking encoded data integrity (%d)...\n", i);
        dump_bytes("Encoded value:", buf, PAYLOAD_LENGTH);

        if (memcmp(expected_payload[i], buf, PAYLOAD_LENGTH)) {
            dump_bytes("Expected payload:", expected_payload[i], PAYLOAD_LENGTH);
            fprintf(stdout, "\n Encoding failed!\n");
            abort();
        } else {
            fprintf(stdout, " OK!\n");
        }
    }

    for (i = 0; i < SAMPLE_COUNT; ++i) {
       uint8_t output[PAYLOAD_LENGTH] = { 0x00 };
       ssize_t result = 0;

       /* Copy data */
       memcpy(buf, sample_data[i], DATA_LENGTH);
       /* Intentionally distort ecc values completely */
       memcpy(buf + DATA_LENGTH, distorted_ecc[i], ECC_LENGTH);
       /* Print modified payload */ 
       dump_bytes("Data with distorted ECC:", buf, PAYLOAD_LENGTH);
       /* Decode modified payload. The function is EXPECTED to fail! */
       result = correct_reed_solomon_decode(ctx, buf, PAYLOAD_LENGTH, output);

       fprintf(stdout, "Decoding result for distorted input (idx: %d): %s\n", i, ((DATA_LENGTH == result) ? "DECODING SUCCESS (False Positive!)" : "DECODING FAILURE")) ;
       failure += (DATA_LENGTH == result);
    }

    fprintf(stdout, "###################################\n");
    /* If no failures has been detected so far, then the test passed! */
    if (0 == failure)
        fprintf(stdout, "%s passed!\n", __FUNCTION__); 
    else
        fprintf(stdout, "%s FAILED!\n", __FUNCTION__); 
    fprintf(stdout, "###################################\n");
}

/* ################################ ========================================= */

int main(void)
{
    const uint16_t primitive_polynomial   = correct_rs_primitive_polynomial_8_4_3_2_0;
    const uint8_t  first_consecutive_root = 0;
    const uint8_t  generator_root_gap     = 1;
    const uint8_t  num_roots              = 4;

    /* Create reed solomon codec instance */
    correct_reed_solomon *ctx = correct_reed_solomon_create(primitive_polynomial,
                                                            first_consecutive_root,
                                                            generator_root_gap,
                                                            num_roots);
    assert(0 != ctx);

    rs_test1(ctx);
    rs_test2(ctx);
    rs_test3(ctx);

    /* Destroy rs codec instance. */
    correct_reed_solomon_destroy(ctx);

    fprintf(stdout, "All tests completed successfully!\n");

    return 0;
}

[brian-armstrong]

Hi @meerd

In general, Reed-Solomon doesn't make any guarantees about what happens once you exceed the error-correction capabilities. There simply isn't enough information present to know whether this has happened. If you want to check the integrity of your data, add a checksum/CRC. You can verify your checksum after error correction, so that the checksum will only fail when the error rate exceeds the correction capacity.