Issue 3295042: Reed-Solomon {En,De}Coding for the masses. (Closed)
|
Created:
13 years, 11 months ago by lvd Modified:
13 years, 5 months ago Reviewers:
Visibility:
Public. |
Descriptionpkg/encoding/rs: Reed-Solomon {En,De}Coding for the masses.
Patch Set 1 #
Total comments: 25
Patch Set 2 : code review 3295042: Reed-Solomon {En,De}Coding for the masses. #Patch Set 3 : code review 3295042: Reed-Solomon {En,De}Coding for the masses. #
MessagesTotal messages: 9
Does anything pending depend on this? I'm wondering if it's sufficiently widely useful to have it merged without a common-place user of it right now.
Sign in to reply to this message.
On Mon, Nov 29, 2010 at 11:10, <cw@f00f.org> wrote: > Does anything pending depend on this? > > I'm wondering if it's sufficiently widely useful to have it merged > without a common-place user of it right now. Probably not. It seems likely that it will end up somewhere else. This is more for a critique of a new-to-Go programmer's first real Go code than for adding a new package. Russ
Sign in to reply to this message.
it's just a toy. i'll very likely not submit in this form. On Mon, Nov 29, 2010 at 20:10, <cw@f00f.org> wrote: > Does anything pending depend on this? > > I'm wondering if it's sufficiently widely useful to have it merged > without a common-place user of it right now. > > > http://codereview.appspot.com/3295042/ >
Sign in to reply to this message.
seems fine; i am suprirsed how little code it takes. main comments are about comments and using range when possible to improve readability. http://codereview.appspot.com/3295042/diff/1/src/cmd/rsc/Makefile File src/cmd/rsc/Makefile (right): http://codereview.appspot.com/3295042/diff/1/src/cmd/rsc/Makefile#newcode3 src/cmd/rsc/Makefile:3: TARG=rsc haha http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go File src/pkg/encoding/rs/rs.go (right): http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcode11 src/pkg/encoding/rs/rs.go:11: if you delete the blank line then this becomes a doc comment (try godoc encoding/rs) http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcode21 src/pkg/encoding/rs/rs.go:21: cp_84320 = 1<<8 | 1<<4 | 1<<3 | 1<<2 | 1<<0 go style is not to use underscores. also cryptic abbreviations are typically out. poly84320 galoisMultiply inX outX http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcode26 src/pkg/encoding/rs/rs.go:26: a uint16 = uint16(aa) not much point to uint16 math here. uint is likely to be more efficient and just as good http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcode62 src/pkg/encoding/rs/rs.go:62: a = galois_multiply(a, 2) If that's all you need it for, it'd be better to use if a&0x80 != 0 { a = a<<1 ^ poly84320 } else { a <<= 1 } http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcode69 src/pkg/encoding/rs/rs.go:69: inv[i] = exp[idx] inv[i] = exp[255 - log[i]] http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcode73 src/pkg/encoding/rs/rs.go:73: // Go's % on signed types preserves sign, do it by hand. weird comment for mult. maybe it should be inside the function somewhere. but i don't see any negative numbers http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcode98 src/pkg/encoding/rs/rs.go:98: // Construct an empty X x Y matrix out of slices. see effective go for comment style // makeMatrix constructs an empty X x Y matrix out of slices. it's a little confusing that you use out to mean "destination" but also the name of an index. for a function like this it's easier to drop the named parameter: func makeMatrix(x, y int) [][]uint8 { m := make([][]uint8, x) ... return m } http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcod... src/pkg/encoding/rs/rs.go:123: func NewErasureCoder(in_x, out_x []uint8) (p *ErasureCoder) { convention in go is uniformly dst, src. but i don't really understand why dst is specified so early. http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcod... src/pkg/encoding/rs/rs.go:127: for j := range out_x { for j, v := range out_x { p.interp[i][j] = lagrange(in_x, v) } http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcod... src/pkg/encoding/rs/rs.go:154: panic(Error(fmt.Sprintf( functions with likely errors typically return os.Error instead of panicking. panics are for truly unexpected things like dereferencing a nil pointer or internal use. this may qualify; if so it should say which package is complaining: "encoding/rs: invalid input length %d (wanted %d)" http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcod... src/pkg/encoding/rs/rs.go:168: for i := 0; i < len(in); i++ { Let go do the indexing for you. for i, row := range in { for j, jv := range row { for k, kv := range p.interp[i] { out[k][j] ^= mult(jv, kv) } } } http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcod... src/pkg/encoding/rs/rs.go:180: // the update. the lenght of in_delta and the lenghts of the elements ,s/lenght/length/ http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcod... src/pkg/encoding/rs/rs.go:209: for k := 0; k < len(p.interp[idx]); k++ { for j, in := range inDelta { for k, v := range p.interp[idx] { out[k][j] = mult(in, v) } }
Sign in to reply to this message.
On Tue, Dec 7, 2010 at 20:51, <rsc@golang.org> wrote: > seems fine; i am suprirsed how little code it takes. > main comments are about comments and using range > when possible to improve readability. > > thanks! i was pleasantly surprised too. and half of it is for checking you feed it nice rectangular matrices. if it was just for the demo app i'd all stick it into 1 source file. i think i'll make the arguments-are-rectangular testing a separate method, that way you can call it for debugging, but not bother with it if you know what you're doing. > > > http://codereview.appspot.com/3295042/diff/1/src/cmd/rsc/Makefile > File src/cmd/rsc/Makefile (right): > > http://codereview.appspot.com/3295042/diff/1/src/cmd/rsc/Makefile#newcode3 > src/cmd/rsc/Makefile:3: TARG=rsc > haha > > http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go > File src/pkg/encoding/rs/rs.go (right): > > > http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcode11 > src/pkg/encoding/rs/rs.go:11: > if you delete the blank line then this becomes a doc comment > (try godoc encoding/rs) > > > http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcode21 > src/pkg/encoding/rs/rs.go:21: cp_84320 = 1<<8 | 1<<4 | 1<<3 | 1<<2 | > 1<<0 > go style is not to use underscores. > also cryptic abbreviations are typically out. > > poly84320 > galoisMultiply > inX > outX > > > http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcode26 > src/pkg/encoding/rs/rs.go:26: a uint16 = uint16(aa) > not much point to uint16 math here. > uint is likely to be more efficient and just as good > > > http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcode62 > src/pkg/encoding/rs/rs.go:62: a = galois_multiply(a, 2) > If that's all you need it for, it'd be better to use > > if a&0x80 != 0 { > a = a<<1 ^ poly84320 > } else { > a <<= 1 > } > yes, but i kept the original full blown multiplication around for testing. i'll clean this up. > > > http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcode69 > src/pkg/encoding/rs/rs.go:69: inv[i] = exp[idx] > inv[i] = exp[255 - log[i]] > > > http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcode73 > src/pkg/encoding/rs/rs.go:73: // Go's % on signed types preserves sign, > do it by hand. > weird comment for mult. > maybe it should be inside the function somewhere. > but i don't see any negative numbers > > > http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcode98 > src/pkg/encoding/rs/rs.go:98: // Construct an empty X x Y matrix out of > slices. > see effective go for comment style > > // makeMatrix constructs an empty X x Y matrix out of slices. > > it's a little confusing that you use out to mean > "destination" but also the name of an index. > for a function like this it's easier to drop the named parameter: > > func makeMatrix(x, y int) [][]uint8 { > m := make([][]uint8, x) > ... > return m > } > > > http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcod... > src/pkg/encoding/rs/rs.go:123: func NewErasureCoder(in_x, out_x []uint8) > (p *ErasureCoder) { > convention in go is uniformly dst, src. > but i don't really understand why dst is specified so early. > because you need them to set up the interpolation factors. > > > http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcod... > src/pkg/encoding/rs/rs.go:127: for j := range out_x { > for j, v := range out_x { > p.interp[i][j] = lagrange(in_x, v) > } > > > http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcod... > src/pkg/encoding/rs/rs.go:154: panic(Error(fmt.Sprintf( > functions with likely errors typically return os.Error instead of > panicking. > panics are for truly unexpected things like dereferencing a nil pointer > or internal use. > > this may qualify; if so it should say which package is complaining: > > "encoding/rs: invalid input length %d (wanted %d)" > > > http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcod... > src/pkg/encoding/rs/rs.go:168: for i := 0; i < len(in); i++ { > Let go do the indexing for you. > > for i, row := range in { > for j, jv := range row { > for k, kv := range p.interp[i] { > out[k][j] ^= mult(jv, kv) > } > } > } > > > http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcod... > src/pkg/encoding/rs/rs.go:180: // the update. the lenght of in_delta > and the lenghts of the elements > ,s/lenght/length/ > > > http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcod... > src/pkg/encoding/rs/rs.go:209: for k := 0; k < len(p.interp[idx]); k++ { > for j, in := range inDelta { > for k, v := range p.interp[idx] { > out[k][j] = mult(in, v) > } > } > > http://codereview.appspot.com/3295042/ >
Sign in to reply to this message.
I still have to rename the underscores away and swap the in/output params, although i'm not convinced that makes sense here. I got rid of all the panicking and moved all that logic to ValidForCode and ValidForInput that the user can quickly check the preconditions with. Now there's almost nothing left :-) i think i'll make the Galois Field its own structure, so you can build erasure coders with different polynomials, and perhaps larger integers than uint8. i'll let you know when its worth another look. On 2010/12/08 01:31:29, lvd wrote: > On Tue, Dec 7, 2010 at 20:51, <mailto:rsc@golang.org> wrote: > > > seems fine; i am suprirsed how little code it takes. > > main comments are about comments and using range > > when possible to improve readability. > > > > > thanks! i was pleasantly surprised too. and half of it is for checking you > feed it nice rectangular matrices. if it was just for the demo app i'd all > stick it into 1 source file. > > i think i'll make the arguments-are-rectangular testing a separate method, > that way you can call it for debugging, but not bother with it if you know > what you're doing. > > > > > > > > http://codereview.appspot.com/3295042/diff/1/src/cmd/rsc/Makefile > > File src/cmd/rsc/Makefile (right): > > > > http://codereview.appspot.com/3295042/diff/1/src/cmd/rsc/Makefile#newcode3 > > src/cmd/rsc/Makefile:3: TARG=rsc > > haha > > > > http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go > > File src/pkg/encoding/rs/rs.go (right): > > > > > > > http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcode11 > > src/pkg/encoding/rs/rs.go:11: > > if you delete the blank line then this becomes a doc comment > > (try godoc encoding/rs) > > > > > > > http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcode21 > > src/pkg/encoding/rs/rs.go:21: cp_84320 = 1<<8 | 1<<4 | 1<<3 | 1<<2 | > > 1<<0 > > go style is not to use underscores. > > also cryptic abbreviations are typically out. > > > > poly84320 > > galoisMultiply > > inX > > outX > > > > > > > http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcode26 > > src/pkg/encoding/rs/rs.go:26: a uint16 = uint16(aa) > > not much point to uint16 math here. > > uint is likely to be more efficient and just as good > > > > > > > http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcode62 > > src/pkg/encoding/rs/rs.go:62: a = galois_multiply(a, 2) > > If that's all you need it for, it'd be better to use > > > > if a&0x80 != 0 { > > a = a<<1 ^ poly84320 > > } else { > > a <<= 1 > > } > > > > yes, but i kept the original full blown multiplication around for testing. > i'll clean this up. > > > > > > > > > http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcode69 > > src/pkg/encoding/rs/rs.go:69: inv[i] = exp[idx] > > inv[i] = exp[255 - log[i]] > > > > > > > http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcode73 > > src/pkg/encoding/rs/rs.go:73: // Go's % on signed types preserves sign, > > do it by hand. > > weird comment for mult. > > maybe it should be inside the function somewhere. > > but i don't see any negative numbers > > > > > > > http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcode98 > > src/pkg/encoding/rs/rs.go:98: // Construct an empty X x Y matrix out of > > slices. > > see effective go for comment style > > > > // makeMatrix constructs an empty X x Y matrix out of slices. > > > > it's a little confusing that you use out to mean > > "destination" but also the name of an index. > > for a function like this it's easier to drop the named parameter: > > > > func makeMatrix(x, y int) [][]uint8 { > > m := make([][]uint8, x) > > ... > > return m > > } > > > > > > > http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcod... > > src/pkg/encoding/rs/rs.go:123: func NewErasureCoder(in_x, out_x []uint8) > > (p *ErasureCoder) { > > convention in go is uniformly dst, src. > > but i don't really understand why dst is specified so early. > > > > because you need them to set up the interpolation factors. > > > > > > > > > http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcod... > > src/pkg/encoding/rs/rs.go:127: for j := range out_x { > > for j, v := range out_x { > > p.interp[i][j] = lagrange(in_x, v) > > } > > > > > > > http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcod... > > src/pkg/encoding/rs/rs.go:154: panic(Error(fmt.Sprintf( > > functions with likely errors typically return os.Error instead of > > panicking. > > panics are for truly unexpected things like dereferencing a nil pointer > > or internal use. > > > > this may qualify; if so it should say which package is complaining: > > > > "encoding/rs: invalid input length %d (wanted %d)" > > > > > > > http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcod... > > src/pkg/encoding/rs/rs.go:168: for i := 0; i < len(in); i++ { > > Let go do the indexing for you. > > > > for i, row := range in { > > for j, jv := range row { > > for k, kv := range p.interp[i] { > > out[k][j] ^= mult(jv, kv) > > } > > } > > } > > > > > > > http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcod... > > src/pkg/encoding/rs/rs.go:180: // the update. the lenght of in_delta > > and the lenghts of the elements > > ,s/lenght/length/ > > > > > > > http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcod... > > src/pkg/encoding/rs/rs.go:209: for k := 0; k < len(p.interp[idx]); k++ { > > for j, in := range inDelta { > > for k, v := range p.interp[idx] { > > out[k][j] = mult(in, v) > > } > > } > > > > http://codereview.appspot.com/3295042/ > >
Sign in to reply to this message.
http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go File src/pkg/encoding/rs/rs.go (right): http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcode11 src/pkg/encoding/rs/rs.go:11: On 2010/12/07 19:51:08, rsc wrote: > if you delete the blank line then this becomes a doc comment > (try godoc encoding/rs) Done. http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcode62 src/pkg/encoding/rs/rs.go:62: a = galois_multiply(a, 2) On 2010/12/07 19:51:08, rsc wrote: > If that's all you need it for, it'd be better to use > > if a&0x80 != 0 { > a = a<<1 ^ poly84320 > } else { > a <<= 1 > } Done. http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcode62 src/pkg/encoding/rs/rs.go:62: a = galois_multiply(a, 2) On 2010/12/07 19:51:08, rsc wrote: > If that's all you need it for, it'd be better to use > > if a&0x80 != 0 { > a = a<<1 ^ poly84320 > } else { > a <<= 1 > } Done. http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcode69 src/pkg/encoding/rs/rs.go:69: inv[i] = exp[idx] On 2010/12/07 19:51:08, rsc wrote: > inv[i] = exp[255 - log[i]] Done. http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcode73 src/pkg/encoding/rs/rs.go:73: // Go's % on signed types preserves sign, do it by hand. On 2010/12/07 19:51:08, rsc wrote: > weird comment for mult. > maybe it should be inside the function somewhere. > but i don't see any negative numbers Done. http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcode98 src/pkg/encoding/rs/rs.go:98: // Construct an empty X x Y matrix out of slices. On 2010/12/07 19:51:08, rsc wrote: > see effective go for comment style > > // makeMatrix constructs an empty X x Y matrix out of slices. > > it's a little confusing that you use out to mean > "destination" but also the name of an index. > for a function like this it's easier to drop the named parameter: > > func makeMatrix(x, y int) [][]uint8 { > m := make([][]uint8, x) > ... > return m > } > Done. http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcode98 src/pkg/encoding/rs/rs.go:98: // Construct an empty X x Y matrix out of slices. On 2010/12/07 19:51:08, rsc wrote: > see effective go for comment style > > // makeMatrix constructs an empty X x Y matrix out of slices. > > it's a little confusing that you use out to mean > "destination" but also the name of an index. > for a function like this it's easier to drop the named parameter: > > func makeMatrix(x, y int) [][]uint8 { > m := make([][]uint8, x) > ... > return m > } > Done. http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcod... src/pkg/encoding/rs/rs.go:127: for j := range out_x { On 2010/12/07 19:51:08, rsc wrote: > for j, v := range out_x { > p.interp[i][j] = lagrange(in_x, v) > } Done. http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcod... src/pkg/encoding/rs/rs.go:168: for i := 0; i < len(in); i++ { On 2010/12/07 19:51:08, rsc wrote: > Let go do the indexing for you. > > for i, row := range in { > for j, jv := range row { > for k, kv := range p.interp[i] { > out[k][j] ^= mult(jv, kv) > } > } > } Done. http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcod... src/pkg/encoding/rs/rs.go:180: // the update. the lenght of in_delta and the lenghts of the elements On 2010/12/07 19:51:08, rsc wrote: > ,s/lenght/length/ Done. http://codereview.appspot.com/3295042/diff/1/src/pkg/encoding/rs/rs.go#newcod... src/pkg/encoding/rs/rs.go:209: for k := 0; k < len(p.interp[idx]); k++ { On 2010/12/07 19:51:08, rsc wrote: > for j, in := range inDelta { > for k, v := range p.interp[idx] { > out[k][j] = mult(in, v) > } > } Done.
Sign in to reply to this message.
you might also be interested in http://code.google.com/p/rsc/source/browse/gf256/gf256.go
Sign in to reply to this message.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
