diff options
Diffstat (limited to 'Godeps/_workspace/src/github.com/mattermost/rsc/gf256')
4 files changed, 528 insertions, 0 deletions
diff --git a/Godeps/_workspace/src/github.com/mattermost/rsc/gf256/Makefile b/Godeps/_workspace/src/github.com/mattermost/rsc/gf256/Makefile new file mode 100644 index 000000000..518a034f3 --- /dev/null +++ b/Godeps/_workspace/src/github.com/mattermost/rsc/gf256/Makefile @@ -0,0 +1,8 @@ +# Copyright 2010 The Go Authors. All rights reserved. +# Use of this source code is governed by a BSD-style +# license that can be found in the LICENSE file. + +include $(GOROOT)/src/Make.inc +TARG=rsc.googlecode.com/hg/gf256 +GOFILES=gf256.go #rs.go +include $(GOROOT)/src/Make.pkg diff --git a/Godeps/_workspace/src/github.com/mattermost/rsc/gf256/blog_test.go b/Godeps/_workspace/src/github.com/mattermost/rsc/gf256/blog_test.go new file mode 100644 index 000000000..12cc7deb0 --- /dev/null +++ b/Godeps/_workspace/src/github.com/mattermost/rsc/gf256/blog_test.go @@ -0,0 +1,85 @@ +// Copyright 2012 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +// This file contains a straightforward implementation of +// Reed-Solomon encoding, along with a benchmark. +// It goes with http://research.swtch.com/field. +// +// For an optimized implementation, see gf256.go. + +package gf256 + +import ( + "bytes" + "fmt" + "testing" +) + +// BlogECC writes to check the error correcting code bytes +// for data using the given Reed-Solomon parameters. +func BlogECC(rs *RSEncoder, m []byte, check []byte) { + if len(check) < rs.c { + panic("gf256: invalid check byte length") + } + if rs.c == 0 { + return + } + + // The check bytes are the remainder after dividing + // data padded with c zeros by the generator polynomial. + + // p = data padded with c zeros. + var p []byte + n := len(m) + rs.c + if len(rs.p) >= n { + p = rs.p + } else { + p = make([]byte, n) + } + copy(p, m) + for i := len(m); i < len(p); i++ { + p[i] = 0 + } + + gen := rs.gen + + // Divide p by gen, leaving the remainder in p[len(data):]. + // p[0] is the most significant term in p, and + // gen[0] is the most significant term in the generator. + for i := 0; i < len(m); i++ { + k := f.Mul(p[i], f.Inv(gen[0])) // k = pi / g0 + // p -= k·g + for j, g := range gen { + p[i+j] = f.Add(p[i+j], f.Mul(k, g)) + } + } + + copy(check, p[len(m):]) + rs.p = p +} + +func BenchmarkBlogECC(b *testing.B) { + data := []byte{0x10, 0x20, 0x0c, 0x56, 0x61, 0x80, 0xec, 0x11, 0xec, 0x11, 0xec, 0x11, 0xec, 0x11, 0xec, 0x11, 0x10, 0x20, 0x0c, 0x56, 0x61, 0x80, 0xec, 0x11, 0xec, 0x11, 0xec, 0x11, 0xec, 0x11, 0xec, 0x11} + check := []byte{0x29, 0x41, 0xb3, 0x93, 0x8, 0xe8, 0xa3, 0xe7, 0x63, 0x8f} + out := make([]byte, len(check)) + rs := NewRSEncoder(f, len(check)) + for i := 0; i < b.N; i++ { + BlogECC(rs, data, out) + } + b.SetBytes(int64(len(data))) + if !bytes.Equal(out, check) { + fmt.Printf("have %#v want %#v\n", out, check) + } +} + +func TestBlogECC(t *testing.T) { + data := []byte{0x10, 0x20, 0x0c, 0x56, 0x61, 0x80, 0xec, 0x11, 0xec, 0x11, 0xec, 0x11, 0xec, 0x11, 0xec, 0x11} + check := []byte{0xa5, 0x24, 0xd4, 0xc1, 0xed, 0x36, 0xc7, 0x87, 0x2c, 0x55} + out := make([]byte, len(check)) + rs := NewRSEncoder(f, len(check)) + BlogECC(rs, data, out) + if !bytes.Equal(out, check) { + t.Errorf("have %x want %x", out, check) + } +} diff --git a/Godeps/_workspace/src/github.com/mattermost/rsc/gf256/gf256.go b/Godeps/_workspace/src/github.com/mattermost/rsc/gf256/gf256.go new file mode 100644 index 000000000..34cc975a8 --- /dev/null +++ b/Godeps/_workspace/src/github.com/mattermost/rsc/gf256/gf256.go @@ -0,0 +1,241 @@ +// Copyright 2010 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +// Package gf256 implements arithmetic over the Galois Field GF(256). +package gf256 + +import "strconv" + +// A Field represents an instance of GF(256) defined by a specific polynomial. +type Field struct { + log [256]byte // log[0] is unused + exp [510]byte +} + +// NewField returns a new field corresponding to the polynomial poly +// and generator α. The Reed-Solomon encoding in QR codes uses +// polynomial 0x11d with generator 2. +// +// The choice of generator α only affects the Exp and Log operations. +func NewField(poly, α int) *Field { + if poly < 0x100 || poly >= 0x200 || reducible(poly) { + panic("gf256: invalid polynomial: " + strconv.Itoa(poly)) + } + + var f Field + x := 1 + for i := 0; i < 255; i++ { + if x == 1 && i != 0 { + panic("gf256: invalid generator " + strconv.Itoa(α) + + " for polynomial " + strconv.Itoa(poly)) + } + f.exp[i] = byte(x) + f.exp[i+255] = byte(x) + f.log[x] = byte(i) + x = mul(x, α, poly) + } + f.log[0] = 255 + for i := 0; i < 255; i++ { + if f.log[f.exp[i]] != byte(i) { + panic("bad log") + } + if f.log[f.exp[i+255]] != byte(i) { + panic("bad log") + } + } + for i := 1; i < 256; i++ { + if f.exp[f.log[i]] != byte(i) { + panic("bad log") + } + } + + return &f +} + +// nbit returns the number of significant in p. +func nbit(p int) uint { + n := uint(0) + for ; p > 0; p >>= 1 { + n++ + } + return n +} + +// polyDiv divides the polynomial p by q and returns the remainder. +func polyDiv(p, q int) int { + np := nbit(p) + nq := nbit(q) + for ; np >= nq; np-- { + if p&(1<<(np-1)) != 0 { + p ^= q << (np - nq) + } + } + return p +} + +// mul returns the product x*y mod poly, a GF(256) multiplication. +func mul(x, y, poly int) int { + z := 0 + for x > 0 { + if x&1 != 0 { + z ^= y + } + x >>= 1 + y <<= 1 + if y&0x100 != 0 { + y ^= poly + } + } + return z +} + +// reducible reports whether p is reducible. +func reducible(p int) bool { + // Multiplying n-bit * n-bit produces (2n-1)-bit, + // so if p is reducible, one of its factors must be + // of np/2+1 bits or fewer. + np := nbit(p) + for q := 2; q < 1<<(np/2+1); q++ { + if polyDiv(p, q) == 0 { + return true + } + } + return false +} + +// Add returns the sum of x and y in the field. +func (f *Field) Add(x, y byte) byte { + return x ^ y +} + +// Exp returns the the base-α exponential of e in the field. +// If e < 0, Exp returns 0. +func (f *Field) Exp(e int) byte { + if e < 0 { + return 0 + } + return f.exp[e%255] +} + +// Log returns the base-α logarithm of x in the field. +// If x == 0, Log returns -1. +func (f *Field) Log(x byte) int { + if x == 0 { + return -1 + } + return int(f.log[x]) +} + +// Inv returns the multiplicative inverse of x in the field. +// If x == 0, Inv returns 0. +func (f *Field) Inv(x byte) byte { + if x == 0 { + return 0 + } + return f.exp[255-f.log[x]] +} + +// Mul returns the product of x and y in the field. +func (f *Field) Mul(x, y byte) byte { + if x == 0 || y == 0 { + return 0 + } + return f.exp[int(f.log[x])+int(f.log[y])] +} + +// An RSEncoder implements Reed-Solomon encoding +// over a given field using a given number of error correction bytes. +type RSEncoder struct { + f *Field + c int + gen []byte + lgen []byte + p []byte +} + +func (f *Field) gen(e int) (gen, lgen []byte) { + // p = 1 + p := make([]byte, e+1) + p[e] = 1 + + for i := 0; i < e; i++ { + // p *= (x + Exp(i)) + // p[j] = p[j]*Exp(i) + p[j+1]. + c := f.Exp(i) + for j := 0; j < e; j++ { + p[j] = f.Mul(p[j], c) ^ p[j+1] + } + p[e] = f.Mul(p[e], c) + } + + // lp = log p. + lp := make([]byte, e+1) + for i, c := range p { + if c == 0 { + lp[i] = 255 + } else { + lp[i] = byte(f.Log(c)) + } + } + + return p, lp +} + +// NewRSEncoder returns a new Reed-Solomon encoder +// over the given field and number of error correction bytes. +func NewRSEncoder(f *Field, c int) *RSEncoder { + gen, lgen := f.gen(c) + return &RSEncoder{f: f, c: c, gen: gen, lgen: lgen} +} + +// ECC writes to check the error correcting code bytes +// for data using the given Reed-Solomon parameters. +func (rs *RSEncoder) ECC(data []byte, check []byte) { + if len(check) < rs.c { + panic("gf256: invalid check byte length") + } + if rs.c == 0 { + return + } + + // The check bytes are the remainder after dividing + // data padded with c zeros by the generator polynomial. + + // p = data padded with c zeros. + var p []byte + n := len(data) + rs.c + if len(rs.p) >= n { + p = rs.p + } else { + p = make([]byte, n) + } + copy(p, data) + for i := len(data); i < len(p); i++ { + p[i] = 0 + } + + // Divide p by gen, leaving the remainder in p[len(data):]. + // p[0] is the most significant term in p, and + // gen[0] is the most significant term in the generator, + // which is always 1. + // To avoid repeated work, we store various values as + // lv, not v, where lv = log[v]. + f := rs.f + lgen := rs.lgen[1:] + for i := 0; i < len(data); i++ { + c := p[i] + if c == 0 { + continue + } + q := p[i+1:] + exp := f.exp[f.log[c]:] + for j, lg := range lgen { + if lg != 255 { // lgen uses 255 for log 0 + q[j] ^= exp[lg] + } + } + } + copy(check, p[len(data):]) + rs.p = p +} diff --git a/Godeps/_workspace/src/github.com/mattermost/rsc/gf256/gf256_test.go b/Godeps/_workspace/src/github.com/mattermost/rsc/gf256/gf256_test.go new file mode 100644 index 000000000..f77fa7d67 --- /dev/null +++ b/Godeps/_workspace/src/github.com/mattermost/rsc/gf256/gf256_test.go @@ -0,0 +1,194 @@ +// Copyright 2010 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package gf256 + +import ( + "bytes" + "fmt" + "testing" +) + +var f = NewField(0x11d, 2) // x^8 + x^4 + x^3 + x^2 + 1 + +func TestBasic(t *testing.T) { + if f.Exp(0) != 1 || f.Exp(1) != 2 || f.Exp(255) != 1 { + panic("bad Exp") + } +} + +func TestECC(t *testing.T) { + data := []byte{0x10, 0x20, 0x0c, 0x56, 0x61, 0x80, 0xec, 0x11, 0xec, 0x11, 0xec, 0x11, 0xec, 0x11, 0xec, 0x11} + check := []byte{0xa5, 0x24, 0xd4, 0xc1, 0xed, 0x36, 0xc7, 0x87, 0x2c, 0x55} + out := make([]byte, len(check)) + rs := NewRSEncoder(f, len(check)) + rs.ECC(data, out) + if !bytes.Equal(out, check) { + t.Errorf("have %x want %x", out, check) + } +} + +func TestLinear(t *testing.T) { + d1 := []byte{0x00, 0x00} + c1 := []byte{0x00, 0x00} + out := make([]byte, len(c1)) + rs := NewRSEncoder(f, len(c1)) + if rs.ECC(d1, out); !bytes.Equal(out, c1) { + t.Errorf("ECBytes(%x, %d) = %x, want 0", d1, len(c1), out) + } + d2 := []byte{0x00, 0x01} + c2 := make([]byte, 2) + rs.ECC(d2, c2) + d3 := []byte{0x00, 0x02} + c3 := make([]byte, 2) + rs.ECC(d3, c3) + cx := make([]byte, 2) + for i := range cx { + cx[i] = c2[i] ^ c3[i] + } + d4 := []byte{0x00, 0x03} + c4 := make([]byte, 2) + rs.ECC(d4, c4) + if !bytes.Equal(cx, c4) { + t.Errorf("ECBytes(%x, 2) = %x\nECBytes(%x, 2) = %x\nxor = %x\nECBytes(%x, 2) = %x", + d2, c2, d3, c3, cx, d4, c4) + } +} + +func TestGaussJordan(t *testing.T) { + rs := NewRSEncoder(f, 2) + m := make([][]byte, 16) + for i := range m { + m[i] = make([]byte, 4) + m[i][i/8] = 1 << uint(i%8) + rs.ECC(m[i][:2], m[i][2:]) + } + if false { + fmt.Printf("---\n") + for _, row := range m { + fmt.Printf("%x\n", row) + } + } + b := []uint{0, 1, 2, 3, 12, 13, 14, 15, 20, 21, 22, 23, 24, 25, 26, 27} + for i := 0; i < 16; i++ { + bi := b[i] + if m[i][bi/8]&(1<<(7-bi%8)) == 0 { + for j := i + 1; ; j++ { + if j >= len(m) { + t.Errorf("lost track for %d", bi) + break + } + if m[j][bi/8]&(1<<(7-bi%8)) != 0 { + m[i], m[j] = m[j], m[i] + break + } + } + } + for j := i + 1; j < len(m); j++ { + if m[j][bi/8]&(1<<(7-bi%8)) != 0 { + for k := range m[j] { + m[j][k] ^= m[i][k] + } + } + } + } + if false { + fmt.Printf("---\n") + for _, row := range m { + fmt.Printf("%x\n", row) + } + } + for i := 15; i >= 0; i-- { + bi := b[i] + for j := i - 1; j >= 0; j-- { + if m[j][bi/8]&(1<<(7-bi%8)) != 0 { + for k := range m[j] { + m[j][k] ^= m[i][k] + } + } + } + } + if false { + fmt.Printf("---\n") + for _, row := range m { + fmt.Printf("%x", row) + out := make([]byte, 2) + if rs.ECC(row[:2], out); !bytes.Equal(out, row[2:]) { + fmt.Printf(" - want %x", out) + } + fmt.Printf("\n") + } + } +} + +func BenchmarkECC(b *testing.B) { + data := []byte{0x10, 0x20, 0x0c, 0x56, 0x61, 0x80, 0xec, 0x11, 0xec, 0x11, 0xec, 0x11, 0xec, 0x11, 0xec, 0x11, 0x10, 0x20, 0x0c, 0x56, 0x61, 0x80, 0xec, 0x11, 0xec, 0x11, 0xec, 0x11, 0xec, 0x11, 0xec, 0x11} + check := []byte{0x29, 0x41, 0xb3, 0x93, 0x8, 0xe8, 0xa3, 0xe7, 0x63, 0x8f} + out := make([]byte, len(check)) + rs := NewRSEncoder(f, len(check)) + for i := 0; i < b.N; i++ { + rs.ECC(data, out) + } + b.SetBytes(int64(len(data))) + if !bytes.Equal(out, check) { + fmt.Printf("have %#v want %#v\n", out, check) + } +} + +func TestGen(t *testing.T) { + for i := 0; i < 256; i++ { + _, lg := f.gen(i) + if lg[0] != 0 { + t.Errorf("#%d: %x", i, lg) + } + } +} + +func TestReducible(t *testing.T) { + var count = []int{1, 2, 3, 6, 9, 18, 30, 56, 99, 186} // oeis.org/A1037 + for i, want := range count { + n := 0 + for p := 1 << uint(i+2); p < 1<<uint(i+3); p++ { + if !reducible(p) { + n++ + } + } + if n != want { + t.Errorf("#reducible(%d-bit) = %d, want %d", i+2, n, want) + } + } +} + +func TestExhaustive(t *testing.T) { + for poly := 0x100; poly < 0x200; poly++ { + if reducible(poly) { + continue + } + α := 2 + for !generates(α, poly) { + α++ + } + f := NewField(poly, α) + for p := 0; p < 256; p++ { + for q := 0; q < 256; q++ { + fm := int(f.Mul(byte(p), byte(q))) + pm := mul(p, q, poly) + if fm != pm { + t.Errorf("NewField(%#x).Mul(%#x, %#x) = %#x, want %#x", poly, p, q, fm, pm) + } + } + } + } +} + +func generates(α, poly int) bool { + x := α + for i := 0; i < 254; i++ { + if x == 1 { + return false + } + x = mul(x, α, poly) + } + return true +} |