vivint / infectious Goto Github PK

Hi! Thank you for creating this library. It seems very useful. I was playing around with the example in the README and playing with corrupting the data.

Eventually I succeeded at corrupting it enough that it would not recover, but it would also not error, thus recovering faulty data... Try this:

package main

import (
	"fmt"

	"github.com/vivint/infectious"
)

func main() {
	const (
		required = 8
		total    = 14
	)

	// Create a *FEC, which will require required pieces for reconstruction at
	// minimum, and generate total total pieces.
	f, err := infectious.NewFEC(required, total)
	if err != nil {
		panic(err)
	}

	// Prepare to receive the shares of encoded data.
	shares := make([]infectious.Share, total)
	output := func(s infectious.Share) {
		// the memory in s gets reused, so we need to make a deep copy
		shares[s.Number] = s.DeepCopy()
	}

	// the data to encode must be padded to a multiple of required, hence the
	// underscores.
	text := "hello, world! __"
	err = f.Encode([]byte(text), output)
	if err != nil {
		panic(err)
	}

	fmt.Println("----------------")
	fmt.Println("Generated shares:")
	// we now have total shares.
	for _, share := range shares {
		fmt.Printf("%d: %#v\n", share.Number, string(share.Data))
	}

	// Let's reconstitute with shares 0-5 missing and 1 piece corrupted.
	shares = shares[6:]
	shares[2].Data[1] = '!' // mutate some data

	fmt.Println("----------------")
	fmt.Println("Fucked shares:")
	for _, share := range shares {
		fmt.Printf("%d: %#v\n", share.Number, string(share.Data))
	}

	err = f.Correct(shares)
	if err != nil {
		panic(err)
	}

	result, err := f.Decode(nil, shares)
	if err != nil {
		panic(err)
	}

	// we have the original data!
	fmt.Println("----------------")
	fmt.Println("Fixed shares:")
	fmt.Printf("original text:  %#v\n", string(text))
	fmt.Printf("recovered text: %#v\n", string(result))
}

You can try the snippet above in the playground: https://play.golang.org/p/ueV5p2O6QE5

It does not panic at all; printing:

----------------
Generated shares:
0: "he"
1: "ll"
2: "o,"
3: " w"
4: "or"
5: "ld"
6: "! "
7: "__"
8: " n"
9: "P\\"
10: "\xceS"
11: "\xf28"
12: "\x94\xdc"
13: "\xd9y"
----------------
Fucked shares:
6: "! "
7: "__"
8: " !"
9: "P\\"
10: "\xceS"
11: "\xf28"
12: "\x94\xdc"
13: "\xd9y"
----------------
Fixed shares:
original text:  "hello, world! __"
recovered text: "h`l\x84oR \xd0o\xfdl\xfd! __"

In this example I require 8 "good" shares to recover. I have 8 shares, but 1 of them is corrupt, so technically I only have 7 good shares, which is not enough to decode this... yet no panic.

That's weird, no? I guess there's something I'm not understanding but I would have expected an error value if the data was too corrupt.

Now if I replace:

	// Let's reconstitute with shares 0-5 missing and 1 piece corrupted.
	shares = shares[6:]
	shares[2].Data[1] = '!' // mutate some data

...with a few mutations too many:

	// Let's corrupt shares 0-3 through mutation:
	shares[0].Data[1] = '!'
	shares[1].Data[1] = '!'
	shares[2].Data[1] = '!'
	shares[3].Data[1] = '!'

I get: panic: too many errors to reconstruct which is the kind of error I'd expect to get with my first snippet instead of decoding garbage data.

Is it a bug? or a weird edge case where the algorithm breaks?

Firstly, thank you for creating Infectious!

In method Decode we're sorting shares, but shares are already sorted in Correct method.
So we're doing work twice and for not so big amount of pieces this will lower the performance(two times of O(N * LogN) work is done)

I'm proposing to create two methods, which expects shares that are already sorted and with a linear check ensure that they're sorted (two times O(N)).

I've it already done it on my branch, will push as far as you'll agree with my proposal.

Thanks.

Hi, I love this library but I'm experiencing some very slow speeds of 2 MB/s encode and 0.05 MB/s decode. Am I doing something wrong? Here's my usage of infectious which operates on byte slices.

// Reed-Solomon encoder
func rsEncode(rs *infectious.FEC,data []byte) []byte{
	var res []byte
	rs.Encode(data,func(s infectious.Share){
		res = append(res,s.DeepCopy().Data[0])
	})
	return res
}

// Reed-Solomon decoder
func rsDecode(rs *infectious.FEC,data []byte) ([]byte,error){
	tmp := make([]infectious.Share,rs.Total())
	for i:=0;i<rs.Total();i++{
		tmp[i] = infectious.Share{
			Number:i,
			Data:[]byte{data[i]},
		}
	}
	res,err := rs.Decode(nil,tmp)
	if err!=nil{
		return data[:rs.Total()/3],err
	}
	return res,nil
}

Even a pure Python implementation I used is faster than this, so I must be doing something wrong. But I've read the docs multiple times and haven't been able to come up with a solution. Would you mind taking a quick look? Thank you very much!

Hi,

when using 1 parity share, I always get the error "not enough shares". That's because the following code uses int instead of float:

func (fc *FEC) berlekampWelch(shares []Share, index int) ([]byte, error) {
	k := fc.k        // required size
	r := len(shares) // required + redundancy size
	e := (r - k) / 2 // deg of E polynomial
	q := e + k       // def of Q polynomial

	fmt.Println(k, r, e, q, index)

	if e == 0 {
		return nil, Error.New("not enough shares")
	}

When using a configuration of e.g. 4 data and 1 parity share, we have a total of 5. In the equitation above, k = 4, r = 5, e = (5 - 4) / 2 = 0.5
But since you are using int, e = (5 - 4) / 2 = 0 which triggers "not enough shares".

Is it not intended to use only 1 parity share?

Thanks,
Marc

Hi.
Got these errors, while building your package:

$ go get -u github.com/vivint/infectious
go: github.com/vivint/infectious upgrade => v0.0.0-20200605153912-25a574ae18a3
go: downloading golang.org/x/sys v0.0.0-20200323222414-85ca7c5b95cd
go: golang.org/x/sys upgrade => v0.0.0-20200930185726-fdedc70b468f
go: downloading golang.org/x/sys v0.0.0-20200930185726-fdedc70b468f
-> github.com/vivint/infectious
../../go/pkg/mod/github.com/vivint/[email protected]/addmul_amd64.s: Assembler messages:
../../go/pkg/mod/github.com/vivint/[email protected]/addmul_amd64.s:72: Error: no such instruction: data nybble_mask<>+0x00(SB)/8,$0x0F0F0F0F0F0F0F0F' ../../go/pkg/mod/github.com/vivint/[email protected]/addmul_amd64.s:73: Error: no such instruction: data nybble_mask<>+0x08(SB)/8,$0x0F0F0F0F0F0F0F0F'
../../go/pkg/mod/github.com/vivint/[email protected]/addmul_amd64.s:74: Error: no such instruction: data nybble_mask<>+0x10(SB)/8,$0x0F0F0F0F0F0F0F0F' ../../go/pkg/mod/github.com/vivint/[email protected]/addmul_amd64.s:75: Error: no such instruction: data nybble_mask<>+0x18(SB)/8,$0x0F0F0F0F0F0F0F0F'
../../go/pkg/mod/github.com/vivint/[email protected]/addmul_amd64.s:76: Error: no such instruction: globl nybble_mask<>(SB),(NOPTR+RODATA),$32' ../../go/pkg/mod/github.com/vivint/[email protected]/addmul_amd64.s:92: Error: no such instruction: text ·addmulSSSE3(SB),7,$0'
../../go/pkg/mod/github.com/vivint/[email protected]/addmul_amd64.s:93: Error: junk (FP)' after expression ../../go/pkg/mod/github.com/vivint/[email protected]/addmul_amd64.s:93: Error: too many memory references for movq'
../../go/pkg/mod/github.com/vivint/[email protected]/addmul_amd64.s:94: Error: junk (FP)' after expression ../../go/pkg/mod/github.com/vivint/[email protected]/addmul_amd64.s:94: Error: too many memory references for movq'
../../go/pkg/mod/github.com/vivint/[email protected]/addmul_amd64.s:95: Error: junk (FP)' after expression ../../go/pkg/mod/github.com/vivint/[email protected]/addmul_amd64.s:95: Error: too many memory references for movq'
../../go/pkg/mod/github.com/vivint/[email protected]/addmul_amd64.s:97: Error: too many memory references for movq' ../../go/pkg/mod/github.com/vivint/[email protected]/addmul_amd64.s:100: Error: invalid character '=' in operand 1 ../../go/pkg/mod/github.com/vivint/[email protected]/addmul_amd64.s:102: Error: junk (FP)' after expression
../../go/pkg/mod/github.com/vivint/[email protected]/addmul_amd64.s:102: Error: too many memory references for movq' ../../go/pkg/mod/github.com/vivint/[email protected]/addmul_amd64.s:103: Error: no such instruction: movou (LOWHIGH),LOW'
../../go/pkg/mod/github.com/vivint/[email protected]/addmul_amd64.s:104: Error: no such instruction: movou 16(LOWHIGH),HIGH' ../../go/pkg/mod/github.com/vivint/[email protected]/addmul_amd64.s:106: Error: no such instruction: movou nybble_mask<>(SB),LOMASK'
../../go/pkg/mod/github.com/vivint/[email protected]/addmul_amd64.s:107: Error: invalid character '=' in operand 2
../../go/pkg/mod/github.com/vivint/[email protected]/addmul_amd64.s:110: Error: no such instruction: movou (IN)(INDEX*1),X0//X0=INPUT[INDEX]' ../../go/pkg/mod/github.com/vivint/[email protected]/addmul_amd64.s:111: Error: no such instruction: movou LOW,X4//X4=copy(LOW)'
../../go/pkg/mod/github.com/vivint/[email protected]/addmul_amd64.s:112: Error: no such instruction: movou (OUT)(INDEX*1),X2//X2=OUT[INDEX]' ../../go/pkg/mod/github.com/vivint/[email protected]/addmul_amd64.s:113: Error: no such instruction: movou X0,X1//X0=input[index]&15'
../../go/pkg/mod/github.com/vivint/[email protected]/addmul_amd64.s:114: Error: no such instruction: movou HIGH,X5//X5=copy(HIGH)' ../../go/pkg/mod/github.com/vivint/[email protected]/addmul_amd64.s:116: Error: too many memory references for pand'
../../go/pkg/mod/github.com/vivint/[email protected]/addmul_amd64.s:117: Error: invalid character '=' in operand 2
../../go/pkg/mod/github.com/vivint/[email protected]/addmul_amd64.s:118: Error: invalid character '=' in operand 2
../../go/pkg/mod/github.com/vivint/[email protected]/addmul_amd64.s:120: Error: invalid character '=' in operand 2
../../go/pkg/mod/github.com/vivint/[email protected]/addmul_amd64.s:121: Error: invalid character '=' in operand 2
../../go/pkg/mod/github.com/vivint/[email protected]/addmul_amd64.s:122: Error: invalid character '=' in operand 2
../../go/pkg/mod/github.com/vivint/[email protected]/addmul_amd64.s:123: Error: too many memory references for pxor' ../../go/pkg/mod/github.com/vivint/[email protected]/addmul_amd64.s:125: Error: no such instruction: movou X2,0(OUT)(INDEX1)'
../../go/pkg/mod/github.com/vivint/[email protected]/addmul_amd64.s:128: Error: too many memory references for cmp' ../../go/pkg/mod/github.com/vivint/[email protected]/addmul_amd64.s:132: Error: junk (FP)' after expression
../../go/pkg/mod/github.com/vivint/[email protected]/addmul_amd64.s:132: Error: too many memory references for movq' ../../go/pkg/mod/github.com/vivint/[email protected]/addmul_amd64.s:133: Error: too many memory references for movq'
../../go/pkg/mod/github.com/vivint/[email protected]/addmul_amd64.s:134: Error: too many memory references for cmp' ../../go/pkg/mod/github.com/vivint/[email protected]/addmul_amd64.s:138: Error: no such instruction: movbqzx (IN)(INDEX1),R9//R9:=in[index]'
../../go/pkg/mod/github.com/vivint/[email protected]/addmul_amd64.s:139: Error: no such instruction: `movbqzx (LOWHIGH)(R9*1),R10//R10:=multiply[R9]'