taldir

gf_poly.go (4361B)

---

 // 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
 }