diff options
Diffstat (limited to 'Godeps/_workspace/src/github.com/mattermost/rsc/gf256')
4 files changed, 0 insertions, 528 deletions
diff --git a/Godeps/_workspace/src/github.com/mattermost/rsc/gf256/Makefile b/Godeps/_workspace/src/github.com/mattermost/rsc/gf256/Makefile deleted file mode 100644 index 518a034f3..000000000 --- a/Godeps/_workspace/src/github.com/mattermost/rsc/gf256/Makefile +++ /dev/null @@ -1,8 +0,0 @@ -# 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 deleted file mode 100644 index 12cc7deb0..000000000 --- a/Godeps/_workspace/src/github.com/mattermost/rsc/gf256/blog_test.go +++ /dev/null @@ -1,85 +0,0 @@ -// 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 deleted file mode 100644 index 34cc975a8..000000000 --- a/Godeps/_workspace/src/github.com/mattermost/rsc/gf256/gf256.go +++ /dev/null @@ -1,241 +0,0 @@ -// 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 deleted file mode 100644 index f77fa7d67..000000000 --- a/Godeps/_workspace/src/github.com/mattermost/rsc/gf256/gf256_test.go +++ /dev/null @@ -1,194 +0,0 @@ -// 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 -} |