boofcv.alg.fiducial.qrcode

Class GaliosFieldTableOps

java.lang.Object

boofcv.alg.fiducial.qrcode.GaliosFieldTableOps

public class GaliosFieldTableOps
extends java.lang.Object

Precomputed look up table for performing operations on GF polynomials of the specified degree.

Code and code comments based on the tutorial at [1].

[1] Reed-Solomon Codes for Coders Viewed on September 28, 2017

Constructor Summary

Constructors

Constructor and Description
GaliosFieldTableOps(int numBits, int primitive) Specifies the GF polynomial

Method Summary

Modifier and Type	Method and Description
int	divide(int x, int y) Computes the following the value of output such that:
int	inverse(int x) Computes the following 2**(max-x) mod primitive
int	multiply(int x, int y) Computes the following (x*y) mod primitive.
void	polyAdd_S(org.ddogleg.struct.GrowQueue_I8 polyA, org.ddogleg.struct.GrowQueue_I8 polyB, org.ddogleg.struct.GrowQueue_I8 output) Adds two polynomials together.
void	polyAdd(org.ddogleg.struct.GrowQueue_I8 polyA, org.ddogleg.struct.GrowQueue_I8 polyB, org.ddogleg.struct.GrowQueue_I8 output) Adds two polynomials together.
void	polyAddScaleB(org.ddogleg.struct.GrowQueue_I8 polyA, org.ddogleg.struct.GrowQueue_I8 polyB, int scaleB, org.ddogleg.struct.GrowQueue_I8 output) Adds two polynomials together while scaling the second.
void	polyDivide_S(org.ddogleg.struct.GrowQueue_I8 dividend, org.ddogleg.struct.GrowQueue_I8 divisor, org.ddogleg.struct.GrowQueue_I8 quotient, org.ddogleg.struct.GrowQueue_I8 remainder) Performs polynomial division using a synthetic division algorithm.
void	polyDivide(org.ddogleg.struct.GrowQueue_I8 dividend, org.ddogleg.struct.GrowQueue_I8 divisor, org.ddogleg.struct.GrowQueue_I8 quotient, org.ddogleg.struct.GrowQueue_I8 remainder) Performs polynomial division using a synthetic division algorithm.
int	polyEval_S(org.ddogleg.struct.GrowQueue_I8 input, int x) Evaluate the polynomial using Horner's method.
int	polyEval(org.ddogleg.struct.GrowQueue_I8 input, int x) Evaluate the polynomial using Horner's method.
int	polyEvalContinue(int previousOutput, org.ddogleg.struct.GrowQueue_I8 part, int x) Continue evaluating a polynomial which has been broken up into multiple arrays.
void	polyMult_flipA(org.ddogleg.struct.GrowQueue_I8 polyA, org.ddogleg.struct.GrowQueue_I8 polyB, org.ddogleg.struct.GrowQueue_I8 output)
void	polyMult_S(org.ddogleg.struct.GrowQueue_I8 polyA, org.ddogleg.struct.GrowQueue_I8 polyB, org.ddogleg.struct.GrowQueue_I8 output) Identical to polyMult(GrowQueue_I8, GrowQueue_I8, GrowQueue_I8)
void	polyMult(org.ddogleg.struct.GrowQueue_I8 polyA, org.ddogleg.struct.GrowQueue_I8 polyB, org.ddogleg.struct.GrowQueue_I8 output) Coefficients for largest powers are first, e.g.
void	polyScale(org.ddogleg.struct.GrowQueue_I8 input, int scale, org.ddogleg.struct.GrowQueue_I8 output) Scales the polynomial.
int	power_n(int x, int power)
int	power(int x, int power) Computes the following x**power mod primitive

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

GaliosFieldTableOps

public GaliosFieldTableOps(int numBits,
                           int primitive)

Specifies the GF polynomial

Parameters:

numBits - Number of bits needed to describe the polynomial. GF(2**8) = 8 bits

primitive - The primitive polynomial

Method Detail

multiply

public int multiply(int x,
                    int y)

Computes the following (x*y) mod primitive. This is done by

divide

public int divide(int x,
                  int y)

Computes the following the value of output such that:

divide(multiply(x,y),y)==x for any x and any nonzero y.

power

public int power(int x,
                 int power)

Computes the following x**power mod primitive

power_n

public int power_n(int x,
                   int power)

inverse

public int inverse(int x)

Computes the following 2**(max-x) mod primitive

polyScale

public void polyScale(org.ddogleg.struct.GrowQueue_I8 input,
                      int scale,
                      org.ddogleg.struct.GrowQueue_I8 output)

Scales the polynomial.

Coefficients for largest powers are first, e.g. 2*x**3 + 8*x**2+1 = [2,8,0,1]

Parameters:

input - Input polynomial.

scale - scale

output - Output polynomial.

polyAdd

public void polyAdd(org.ddogleg.struct.GrowQueue_I8 polyA,
                    org.ddogleg.struct.GrowQueue_I8 polyB,
                    org.ddogleg.struct.GrowQueue_I8 output)

Adds two polynomials together. output = polyA + polyB

Coefficients for largest powers are first, e.g. 2*x**3 + 8*x**2+1 = [2,8,0,1]

Parameters:

polyA - (Input) First polynomial

polyB - (Input) Second polynomial

output - (Output) Results of addition

polyAdd_S

public void polyAdd_S(org.ddogleg.struct.GrowQueue_I8 polyA,
                      org.ddogleg.struct.GrowQueue_I8 polyB,
                      org.ddogleg.struct.GrowQueue_I8 output)

Adds two polynomials together.

Coefficients for smallest powers are first, e.g. 2*x**3 + 8*x**2+1 = [1,0,2,8]

Parameters:

polyA - (Input) First polynomial

polyB - (Input) Second polynomial

output - (Output) Results of addition

polyAddScaleB

public void polyAddScaleB(org.ddogleg.struct.GrowQueue_I8 polyA,
                          org.ddogleg.struct.GrowQueue_I8 polyB,
                          int scaleB,
                          org.ddogleg.struct.GrowQueue_I8 output)

Adds two polynomials together while scaling the second.

Coefficients for largest powers are first, e.g. 2*x**3 + 8*x**2+1 = [2,8,0,1]

Parameters:

polyA - (Input) First polynomial

polyB - (Input) Second polynomial

scaleB - (Input) Scale factor applied to polyB

output - (Output) Results of addition

polyMult

public void polyMult(org.ddogleg.struct.GrowQueue_I8 polyA,
                     org.ddogleg.struct.GrowQueue_I8 polyB,
                     org.ddogleg.struct.GrowQueue_I8 output)

Coefficients for largest powers are first, e.g. 2*x**3 + 8*x**2+1 = [2,8,0,1]

Parameters:

polyA -

polyB -

output -

polyMult_flipA

public void polyMult_flipA(org.ddogleg.struct.GrowQueue_I8 polyA,
                           org.ddogleg.struct.GrowQueue_I8 polyB,
                           org.ddogleg.struct.GrowQueue_I8 output)

polyMult_S

public void polyMult_S(org.ddogleg.struct.GrowQueue_I8 polyA,
                       org.ddogleg.struct.GrowQueue_I8 polyB,
                       org.ddogleg.struct.GrowQueue_I8 output)

Identical to polyMult(GrowQueue_I8, GrowQueue_I8, GrowQueue_I8)

Coefficients for smallest powers are first, e.g. 2*x**3 + 8*x**2+1 = [1,0,2,8]

Parameters:

polyA -

polyB -

output -

polyEval

public int polyEval(org.ddogleg.struct.GrowQueue_I8 input,
                    int x)

Evaluate the polynomial using Horner's method. Avoids explicit calculating the powers of x.

01x**4 + 0fx**3 + 36x**2 + 78x + 40 = (((01 x + 0f) x + 36) x + 78) x + 40

Coefficients for largest powers are first, e.g. 2*x**3 + 8*x**2+1 = [2,8,0,1]

Parameters:

input - Polynomial being evaluated

x - Value of x

Returns:

Output of function

polyEval_S

public int polyEval_S(org.ddogleg.struct.GrowQueue_I8 input,
                      int x)

Evaluate the polynomial using Horner's method. Avoids explicit calculating the powers of x.

01x**4 + 0fx**3 + 36x**2 + 78x + 40 = (((01 x + 0f) x + 36) x + 78) x + 40

Coefficients for smallest powers are first, e.g. 2*x**3 + 8*x**2+1 = [1,0,2,8]

Parameters:

input - Polynomial being evaluated

x - Value of x

Returns:

Output of function

polyEvalContinue

public int polyEvalContinue(int previousOutput,
                            org.ddogleg.struct.GrowQueue_I8 part,
                            int x)

Continue evaluating a polynomial which has been broken up into multiple arrays.

Parameters:

previousOutput - Output from the evaluation of the prior part of the polynomial

part - Additional segment of the polynomial

x - Point it's being evaluated at

Returns:

results

polyDivide

public void polyDivide(org.ddogleg.struct.GrowQueue_I8 dividend,
                       org.ddogleg.struct.GrowQueue_I8 divisor,
                       org.ddogleg.struct.GrowQueue_I8 quotient,
                       org.ddogleg.struct.GrowQueue_I8 remainder)

Performs polynomial division using a synthetic division algorithm.

Coefficients for largest powers are first, e.g. 2*x**3 + 8*x**2+1 = [2,8,0,1]

Parameters:

dividend - (Input) Polynomial dividend

divisor - (Input) Polynomial divisor

quotient - (Output) Division's quotient

remainder - (Output) Divisions's remainder

polyDivide_S

public void polyDivide_S(org.ddogleg.struct.GrowQueue_I8 dividend,
                         org.ddogleg.struct.GrowQueue_I8 divisor,
                         org.ddogleg.struct.GrowQueue_I8 quotient,
                         org.ddogleg.struct.GrowQueue_I8 remainder)

Performs polynomial division using a synthetic division algorithm.

Coefficients for smallest powers are first, e.g. 2*x**3 + 8*x**2+1 = [1,0,2,8]

Parameters:

dividend - (Input) Polynomial dividend

divisor - (Input) Polynomial divisor

quotient - (Output) Division's quotient

remainder - (Output) Divisions's remainder