Erasure duplicate makes decoder to fail

[Hi-Angel]

Steps to reproduce

code:

#include <ezpwd/rs>
#include <array>
#include <cstdint>
#include <vector>

using namespace std;

const ushort sz_codeword = 255,
    sz_payload = 128,
    sz_parity = sz_codeword - sz_payload;

const array<uint8_t, sz_codeword> rs_block_original = {
    0x6d, 0xde, 0x8c, 0x66, 0x05, 0x6a, 0x63, 0xd0, 0x7e, 0xa0, 0x9e, 0xed, 0xe9, 0xa6, 0x66, 0x5f,
    0x11, 0xde, 0x8c, 0xf1, 0x99, 0x70, 0x76, 0x27, 0x3b, 0x9f, 0xc1, 0xc8, 0xb4, 0xbc, 0x52, 0x86,
    0x53, 0x3c, 0x6e, 0xe6, 0x0e, 0xff, 0xca, 0x4e, 0x41, 0x5d, 0x49, 0x90, 0x6c, 0x88, 0x5f, 0xa3,
    0xea, 0xbb, 0xa1, 0x4d, 0x42, 0xe1, 0x79, 0xcc, 0x23, 0xd2, 0xf6, 0x86, 0xb0, 0x85, 0x72, 0x5b,
    0xba, 0xa4, 0x19, 0x0c, 0xc9, 0x2d, 0xda, 0x38, 0xfa, 0xfd, 0x2b, 0x19, 0x81, 0x3e, 0x74, 0x49,
    0xa6, 0x27, 0x07, 0xbb, 0xaa, 0xe7, 0x34, 0x96, 0xe8, 0x8a, 0xac, 0xee, 0x6e, 0xef, 0xb1, 0x39,
    0xe5, 0x63, 0xdb, 0x66, 0xa2, 0xd3, 0xaf, 0xe8, 0x10, 0x88, 0x4b, 0x2c, 0xac, 0x19, 0x44, 0x7c,
    0x57, 0xda, 0xcd, 0xfb, 0x75, 0xa1, 0xe6, 0x6d, 0x4d, 0x4a, 0xb0, 0xdd, 0xa9, 0x88, 0x76, 0xce,
    0xcc, 0x7f, 0xd7, 0xd5, 0xe1, 0xc7, 0x02, 0x7b, 0x10, 0x12, 0x84, 0x21, 0xb9, 0x37, 0xbb, 0x91,
    0x16, 0x94, 0x04, 0x80, 0x21, 0xe8, 0xaf, 0x8e, 0xa1, 0xee, 0xb6, 0x17, 0x33, 0x60, 0x78, 0x06,
    0xce, 0x2b, 0x7c, 0x1c, 0x03, 0x0e, 0x92, 0x82, 0xf1, 0x87, 0x1a, 0x72, 0xb1, 0x11, 0xc0, 0xe3,
    0x7e, 0xe3, 0xdc, 0x32, 0x14, 0x8e, 0x06, 0xe2, 0xe4, 0xca, 0x97, 0x6e, 0x43, 0xe1, 0xdb, 0xd7,
    0xa8, 0xb3, 0x46, 0xdb, 0x9e, 0xd0, 0xce, 0x51, 0xc3, 0xd3, 0x3d, 0x8f, 0xf5, 0xee, 0x31, 0x1c,
    0x6f, 0xdf, 0xb6, 0xc9, 0x96, 0x2b, 0x26, 0x4d, 0x3b, 0xec, 0x25, 0x7a, 0x4c, 0x48, 0xd7, 0x49,
    0xf3, 0x01, 0xb2, 0x6f, 0xe3, 0xcd, 0x03, 0xcf, 0x34, 0x4e, 0x31, 0x13, 0x6e, 0x84, 0x44, 0x5c,
    0x94, 0x2c, 0x06, 0x5d, 0xb4, 0x45, 0xae, 0x7b, 0x8b, 0xcc, 0xf0, 0x14, 0xd8, 0x4f, 0x8d };

const array<uint8_t, sz_codeword> rs_block_with_erasures = {
    0x6d, 0xde, 0x8c, 0x00, 0x00, 0x00, 0x63, 0xd0, 0x7e, 0xa0, 0x9e, 0xed, 0xe9, 0x00, 0x00, 0x5f,
    0x11, 0xde, 0x8c, 0xf1, 0x99, 0x70, 0x00, 0x00, 0x00, 0x00, 0xc1, 0xc8, 0xb4, 0xbc, 0x52, 0x86,
    0x00, 0x00, 0x00, 0xe6, 0x0e, 0xff, 0xca, 0x4e, 0x41, 0x5d, 0x00, 0x00, 0x00, 0x88, 0x5f, 0xa3,
    0xea, 0xbb, 0xa1, 0x4d, 0x00, 0x00, 0x00, 0x00, 0x23, 0xd2, 0xf6, 0x86, 0xb0, 0x85, 0x00, 0x00,
    0x00, 0xa4, 0x19, 0x0c, 0xc9, 0x2d, 0xda, 0x38, 0x00, 0x00, 0x00, 0x19, 0x81, 0x3e, 0x74, 0x49,
    0xa6, 0x27, 0x00, 0x00, 0x00, 0x00, 0x34, 0x96, 0xe8, 0x8a, 0xac, 0xee, 0x00, 0x00, 0x00, 0x39,
    0xe5, 0x63, 0xdb, 0x66, 0xa2, 0xd3, 0x00, 0x00, 0x00, 0x88, 0x4b, 0x2c, 0xac, 0x19, 0x44, 0x7c,
    0x00, 0x00, 0x00, 0x00, 0x75, 0xa1, 0xe6, 0x6d, 0x4d, 0x4a, 0x00, 0x00, 0x00, 0x88, 0x76, 0xce,
    0xcc, 0x7f, 0xd7, 0xd5, 0x00, 0x00, 0x00, 0x7b, 0x10, 0x12, 0x84, 0x21, 0xb9, 0x37, 0x00, 0x00,
    0x00, 0x00, 0x04, 0x80, 0x21, 0xe8, 0xaf, 0x8e, 0x00, 0x00, 0x00, 0x17, 0x33, 0x60, 0x78, 0x06,
    0xce, 0x2b, 0x00, 0x00, 0x00, 0x0e, 0x92, 0x82, 0xf1, 0x87, 0x1a, 0x72, 0x00, 0x00, 0x00, 0x00,
    0x7e, 0xe3, 0xdc, 0x32, 0x14, 0x8e, 0x00, 0x00, 0x00, 0xca, 0x97, 0x6e, 0x43, 0xe1, 0xdb, 0xd7,
    0x00, 0x00, 0x00, 0xdb, 0x9e, 0xd0, 0xce, 0x51, 0xc3, 0xd3, 0x00, 0x00, 0x00, 0x00, 0x31, 0x1c,
    0x6f, 0xdf, 0xb6, 0xc9, 0x00, 0x00, 0x00, 0x4d, 0x3b, 0xec, 0x25, 0x7a, 0x4c, 0x48, 0x00, 0x00,
    0x00, 0x01, 0xb2, 0x6f, 0xe3, 0xcd, 0x03, 0xcf, 0x00, 0x00, 0x00, 0x00, 0x6e, 0x84, 0x44, 0x5c,
    0x94, 0x2c, 0x00, 0x00, 0x00, 0x45, 0xae, 0x7b, 0x8b, 0xcc, 0xf0, 0x14, 0x00, 0x00, 0x00 };

const array<int, 86> erasures_pos = { 3, 4, 5, 13, 13, 14, 22, 23, 24, 25, 32, 33, 34, 42, 43, 44, 52, 53,
                                      54, 55, 62, 63, 64, 72, 73, 74, 82, 83, 84, 85, 92, 93, 94, 102, 103,
                                      104, 112, 113, 114, 115, 122, 123, 124, 132, 133, 134, 142, 143, 144,
                                      145, 152, 153, 154, 162, 163, 164, 172, 173, 174, 175, 182, 183, 184,
                                      192, 193, 194, 202, 203, 204, 205, 212, 213, 214, 222, 223, 224, 232,
                                      233, 234, 235, 242, 243, 244, 252, 253, 254 };

int main() {
    ezpwd::RS<sz_codeword, sz_payload> rs;
    auto data     = vector<uint8_t>(rs_block_with_erasures.begin(), rs_block_with_erasures.end()),
        original  = vector<uint8_t>(rs_block_original.begin(), rs_block_original.end());
    auto erasures = vector<int>(erasures_pos.begin(), erasures_pos.end());
    int fixed = rs.decode(data, erasures);
    if (fixed == -1 && data != original)
        puts("Decoding failed!");
}

building'n'running;

$ g++ test.cpp -o a -g3 -O0 -Wall -Wextra -Wsign-conversion -std=c++17 -pedantic -fsanitize=address -isystem/usr/include/ezpwd-reed-solomon
$ ./a
Decoding failed!
$ sed -i "s/86> erasures_pos = { 3, 4, 5, 13, 13, /85> erasures_pos = { 3, 4, 5, 13, /g" test.cpp
$ g++ test.cpp -o a -g3 -O0 -Wall -Wextra -Wsign-conversion -std=c++17 -pedantic -fsanitize=address -isystem/usr/include/ezpwd-reed-solomon
$ ./a

The reason for fail is duplicate erasure position 13, 13, which is removed as part of the steps. I'm not sure if it's expected behavior.

[pjkundert]

Yes, it doesn't handle duplicate erasure positions; good catch. This is inherited behaviour from the original Phil Karn implementation. I don't know if it's worthwhile sorting and uniquing the incoming erasure position vector; I think it should remain an error: the erasure positions should be unique. This should be documented.

[Hi-Angel]

I don't know if it's worthwhile sorting and uniquing the incoming erasure position vector; I think it should remain an error: the erasure positions should be unique. This should be documented.

Agree, sorting and uniquing would take unnecessary overhead, in this case it's better to leave to users. It's just that I thought it would come without the cost — like, restoring same position twice is the same as once. But granted, I don't know implementation details.

To be honest, in my case it revealed a bug. I imagine it could be nice to have the check, say, for debug mode only — just for a user to see they did something wrong. Otherwise all they see would be ezpwd failing to decode a block — "why? who knows".