Comparing Encoding/Decoding with another erasure coding library

[hivenet-mathieu-lacage]

Hi,

I currently use this (very nice !) library to encode and decode blocks for storage. I'd like to be able to use another python-based library to encode content to be consumed by this project, and vice-versa. I selected zfec because it appears to use the same primitive polynomial you use (0x11D).

As a start I wrote some pretty stupid code to encode random bytes with both libraries which results in different content. I double-checked that both zfec and this library do zero-padding. To be extra-safe, I did a simple test a data file of 2 random bytes, 2 data shards and 2 parity shards. This should result in zero padding for all shards.

For example:
$ dd if=/dev/random of=./2 count=1 bs=2
$ hexdump -C ./2
00000000 94 ad |..|

with this code:

package main

import (
	"flag"
	"fmt"
	"io/ioutil"
	"log"
	"os"

	"github.com/klauspost/reedsolomon"
)

func main() {
	// Define command-line parameters
	ndata := flag.Int("ndata", 2, "Number of data shards")
	nparity := flag.Int("nparity", 2, "Number of parity shards")
	flag.Parse()

	// Check if the file argument is provided
	if flag.NArg() < 1 {
		log.Fatalf("Usage: %s [options] <file>", os.Args[0])
	}
	file := flag.Arg(0)

	// Read the file content into a buffer
	data, err := ioutil.ReadFile(file)
	if err != nil {
		log.Fatalf("Error reading file: %v", err)
	}

	// Create a Reed-Solomon encoder
	enc, err := reedsolomon.New(*ndata, *nparity)
	if err != nil {
		log.Fatalf("Error creating Reed-Solomon encoder: %v", err)
	}

	// Split the data into shards
	shards, err := enc.Split(data)
	if err != nil {
		log.Fatalf("Error splitting data into shards: %v", err)
	}

	// Encode parity shards
	err = enc.Encode(shards)
	if err != nil {
		log.Fatalf("Error encoding parity shards: %v", err)
	}

	// Write each shard to a separate file
	for i, shard := range shards {
		shardFile := fmt.Sprintf("%s-%d-%d-%d", file, *ndata, *nparity, i)
		err = ioutil.WriteFile(shardFile, shard, 0644)
		if err != nil {
			log.Fatalf("Error writing shard to file: %v", err)
		}
		fmt.Printf("Wrote shard %d to %s\n", i, shardFile)
	}

	fmt.Println("Reed-Solomon encoding completed successfully")
}

and this one:

 import argparse

import zfec.easyfec


def encode(data, n_data_shards, n_parity_shards):
    encoder = zfec.easyfec.Encoder(k=n_data_shards, m=n_data_shards+n_parity_shards)
    encoded = encoder.encode(data)
    return encoded


def main():
    parser = argparse.ArgumentParser()
    parser.add_argument('--ndata', type=int, default=2)
    parser.add_argument('--nparity', type=int, default=2)
    parser.add_argument('file')
    args = parser.parse_args()

    with open(args.file, 'rb') as f:
        data = f.read()
        shards = encode(data, args.ndata, args.nparity)
        for i, shard in enumerate(shards):
            with open(f'{args.file}-{args.ndata}-{args.nparity}-{i}', 'wb+') as o:
                o.write(shard)


main()

$ hexdump -C ../go/2-2-2-3
00000000  df                                                |.|
00000001
$ hexdump -C ../py/2-2-2-3
00000000  70                                                |p|
00000001

--> The last shard (shard index 3) contains differing content.

Do you have suggestions on what I should look into that might explain this difference ?

[klauspost]

Both the poly and matrix must match. Code comments claim it is Vandermonde, but I don't have any way to check.

Neither of the other matrices match the output either.

[hivenet-mathieu-lacage]

hi @klauspost ,

Thank you for this hint. I looked carefully at the encoding matrix:
zfec vs klauspost/reedsolomon

And, yes, after a while staring at the code, it is pretty obvious that zfec is not generating its encoding matrix from a vandermonde matrix:

• zfec does not fill the last row of the matrix (that one really bothers me)
• zfec is not calculating alphai^j but something like alphai^i^j . I am not entirely sure I understand what it is calculating but I know for sure that it is not the corresponding vandermonde coefficient.

The patch below fixes both issues and appears to generate the same matrix you use in reedsolomon.go. Encoding and decoding then works cross-library. I doubt this is of much use to anyone but me and I doubt the zfec maintainers will be interested in this but, in case someone stumbles upon this problem, the below might be helpful.

diff --git a/zfec/fec.c b/zfec/fec.c
index 993f22a..7b481f2 100644
--- a/zfec/fec.c
+++ b/zfec/fec.c
@@ -456,9 +456,9 @@ fec_new(unsigned short k, unsigned short n) {
     tmp_m[0] = 1;
     for (col = 1; col < k; col++)
         tmp_m[col] = 0;
-    for (p = tmp_m + k, row = 0; row + 1 < n; row++, p += k)
+    for (p = tmp_m + k, row = 1; row < n; row++, p += k)
         for (col = 0; col < k; col++)
-            p[col] = gf_exp[modnn (row * col)];
+            p[col] = gf_exp[modnn (gf_log[row] * col)];
 
     /*
      * quick code to build systematic matrix: invert the top

[klauspost]

I don't know if the matrix is fully reversible. But you do have the option to specify a custom matrix: https://pkg.go.dev/github.com/klauspost/reedsolomon#WithCustomMatrix - it was user submitted, so I can't really tell you too much about it.

[hivenet-mathieu-lacage]

For reference, what zfec is doing is calculating a vandermonde matrix over xi=alpha^(i-1) as opposed to what you are doing, which is xi=i-1

i.e., p30:
https://www.cs.utexas.edu/users/lam/395t/papers/FEC-rizzo.pdf

So, yes, I could be using WithCustomMatrix to generate a compatible matrix. Sadly, I have a bunch of data encoded with your library so, I need to make zfec compatible with yours instead.

[hivenet-mathieu-lacage]

Patch to make zfec compatible with klauspost/reedsolomon:

tahoe-lafs/zfec#110

I have zero expectation that this will get merged so, I include it here in case anyone beyond me needs this to be interoperable.

[klauspost]

@hivenet-mathieu-lacage Thanks for the update.

If the PR gets accepted or you decide to fork, let me know and I can add it to the list of "compatible implementations".