diff options
Diffstat (limited to 'vendor/github.com/skip2/go-qrcode/reedsolomon/gf_poly.go')
-rw-r--r-- | vendor/github.com/skip2/go-qrcode/reedsolomon/gf_poly.go | 216 |
1 files changed, 0 insertions, 216 deletions
diff --git a/vendor/github.com/skip2/go-qrcode/reedsolomon/gf_poly.go b/vendor/github.com/skip2/go-qrcode/reedsolomon/gf_poly.go deleted file mode 100644 index 962f5454..00000000 --- a/vendor/github.com/skip2/go-qrcode/reedsolomon/gf_poly.go +++ /dev/null @@ -1,216 +0,0 @@ -// go-qrcode -// Copyright 2014 Tom Harwood - -package reedsolomon - -import ( - "fmt" - "log" - - bitset "github.com/skip2/go-qrcode/bitset" -) - -// gfPoly is a polynomial over GF(2^8). -type gfPoly struct { - // The ith value is the coefficient of the ith degree of x. - // term[0]*(x^0) + term[1]*(x^1) + term[2]*(x^2) ... - term []gfElement -} - -// newGFPolyFromData returns |data| as a polynomial over GF(2^8). -// -// Each data byte becomes the coefficient of an x term. -// -// For an n byte input the polynomial is: -// data[n-1]*(x^n-1) + data[n-2]*(x^n-2) ... + data[0]*(x^0). -func newGFPolyFromData(data *bitset.Bitset) gfPoly { - numTotalBytes := data.Len() / 8 - if data.Len()%8 != 0 { - numTotalBytes++ - } - - result := gfPoly{term: make([]gfElement, numTotalBytes)} - - i := numTotalBytes - 1 - for j := 0; j < data.Len(); j += 8 { - result.term[i] = gfElement(data.ByteAt(j)) - i-- - } - - return result -} - -// newGFPolyMonomial returns term*(x^degree). -func newGFPolyMonomial(term gfElement, degree int) gfPoly { - if term == gfZero { - return gfPoly{} - } - - result := gfPoly{term: make([]gfElement, degree+1)} - result.term[degree] = term - - return result -} - -func (e gfPoly) data(numTerms int) []byte { - result := make([]byte, numTerms) - - i := numTerms - len(e.term) - for j := len(e.term) - 1; j >= 0; j-- { - result[i] = byte(e.term[j]) - i++ - } - - return result -} - -// numTerms returns the number of -func (e gfPoly) numTerms() int { - return len(e.term) -} - -// gfPolyMultiply returns a * b. -func gfPolyMultiply(a, b gfPoly) gfPoly { - numATerms := a.numTerms() - numBTerms := b.numTerms() - - result := gfPoly{term: make([]gfElement, numATerms+numBTerms)} - - for i := 0; i < numATerms; i++ { - for j := 0; j < numBTerms; j++ { - if a.term[i] != 0 && b.term[j] != 0 { - monomial := gfPoly{term: make([]gfElement, i+j+1)} - monomial.term[i+j] = gfMultiply(a.term[i], b.term[j]) - - result = gfPolyAdd(result, monomial) - } - } - } - - return result.normalised() -} - -// gfPolyRemainder return the remainder of numerator / denominator. -func gfPolyRemainder(numerator, denominator gfPoly) gfPoly { - if denominator.equals(gfPoly{}) { - log.Panicln("Remainder by zero") - } - - remainder := numerator - - for remainder.numTerms() >= denominator.numTerms() { - degree := remainder.numTerms() - denominator.numTerms() - coefficient := gfDivide(remainder.term[remainder.numTerms()-1], - denominator.term[denominator.numTerms()-1]) - - divisor := gfPolyMultiply(denominator, - newGFPolyMonomial(coefficient, degree)) - - remainder = gfPolyAdd(remainder, divisor) - } - - return remainder.normalised() -} - -// gfPolyAdd returns a + b. -func gfPolyAdd(a, b gfPoly) gfPoly { - numATerms := a.numTerms() - numBTerms := b.numTerms() - - numTerms := numATerms - if numBTerms > numTerms { - numTerms = numBTerms - } - - result := gfPoly{term: make([]gfElement, numTerms)} - - for i := 0; i < numTerms; i++ { - switch { - case numATerms > i && numBTerms > i: - result.term[i] = gfAdd(a.term[i], b.term[i]) - case numATerms > i: - result.term[i] = a.term[i] - default: - result.term[i] = b.term[i] - } - } - - return result.normalised() -} - -func (e gfPoly) normalised() gfPoly { - numTerms := e.numTerms() - maxNonzeroTerm := numTerms - 1 - - for i := numTerms - 1; i >= 0; i-- { - if e.term[i] != 0 { - break - } - - maxNonzeroTerm = i - 1 - } - - if maxNonzeroTerm < 0 { - return gfPoly{} - } else if maxNonzeroTerm < numTerms-1 { - e.term = e.term[0 : maxNonzeroTerm+1] - } - - return e -} - -func (e gfPoly) string(useIndexForm bool) string { - var str string - numTerms := e.numTerms() - - for i := numTerms - 1; i >= 0; i-- { - if e.term[i] > 0 { - if len(str) > 0 { - str += " + " - } - - if !useIndexForm { - str += fmt.Sprintf("%dx^%d", e.term[i], i) - } else { - str += fmt.Sprintf("a^%dx^%d", gfLogTable[e.term[i]], i) - } - } - } - - if len(str) == 0 { - str = "0" - } - - return str -} - -// equals returns true if e == other. -func (e gfPoly) equals(other gfPoly) bool { - var minecPoly *gfPoly - var maxecPoly *gfPoly - - if e.numTerms() > other.numTerms() { - minecPoly = &other - maxecPoly = &e - } else { - minecPoly = &e - maxecPoly = &other - } - - numMinTerms := minecPoly.numTerms() - numMaxTerms := maxecPoly.numTerms() - - for i := 0; i < numMinTerms; i++ { - if e.term[i] != other.term[i] { - return false - } - } - - for i := numMinTerms; i < numMaxTerms; i++ { - if maxecPoly.term[i] != 0 { - return false - } - } - - return true -} |