Package org.apache.hadoop.io.erasurecode.rawcoder.util

Class GaloisField

java.lang.Object
org.apache.hadoop.io.erasurecode.rawcoder.util.GaloisField
@Private public class GaloisField extends Object
Implementation of Galois field arithmetic with 2^p elements. The input must be unsigned integers. It's ported from HDFS-RAID, slightly adapted.

  • Method Summary

    Modifier and Type
    Method
    Description
    int[]
    add(int[] p, int[] q)
    Compute the sum of two polynomials.
    int
    add(int x, int y)
    Compute the sum of two fields
    int
    divide(int x, int y)
    Compute the division of two fields
    void
    gaussianElimination(int[][] matrix)
    Perform Gaussian elimination on the given matrix.
    int
    getFieldSize()
    Return number of elements in the field
    static GaloisField
    getInstance()
    Get the object performs Galois field arithmetic with default setting.
    static GaloisField
    getInstance(int fieldSize, int primitivePolynomial)
    Get the object performs Galois field arithmetics.
    int
    getPrimitivePolynomial()
    Return the primitive polynomial in GF(2)
    int[]
    multiply(int[] p, int[] q)
    Compute the multiplication of two polynomials.
    int
    multiply(int x, int y)
    Compute the multiplication of two fields
    int
    power(int x, int n)
    Compute power n of a field
    void
    remainder(byte[][] dividend, int[] divisor)
    The "bulk" version of the remainder.
    void
    remainder(byte[][] dividend, int[] offsets, int len, int[] divisor)
    The "bulk" version of the remainder.
    void
    remainder(int[] dividend, int[] divisor)
    Compute the remainder of a dividend and divisor pair.
    void
    remainder(ByteBuffer[] dividend, int[] divisor)
    The "bulk" version of the remainder, using ByteBuffer.
    void
    solveVandermondeSystem(int[] x, byte[][] y, int[] outputOffsets, int len, int dataLen)
    A "bulk" version to the solving of Vandermonde System.
    void
    solveVandermondeSystem(int[] x, int[] y)
    Given a Vandermonde matrix V[i][j]=x[j]^i and vector y, solve for z such that Vz=y.
    void
    solveVandermondeSystem(int[] x, int[] y, int len)
    Given a Vandermonde matrix V[i][j]=x[j]^i and vector y, solve for z such that Vz=y.
    void
    solveVandermondeSystem(int[] x, ByteBuffer[] y, int len)
    A "bulk" version of the solveVandermondeSystem, using ByteBuffer.
    void
    substitute(byte[][] p, byte[] q, int x)
    A "bulk" version of the substitute.
    void
    substitute(byte[][] p, int[] offsets, int len, byte[] q, int offset, int x)
    A "bulk" version of the substitute.
    int
    substitute(int[] p, int x)
    Substitute x into polynomial p(x).
    void
    substitute(ByteBuffer[] p, int len, ByteBuffer q, int x)
    A "bulk" version of the substitute, using ByteBuffer.

    Methods inherited from class java.lang.Object

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

  • Method Details

    • getInstance

      public static GaloisField getInstance(int fieldSize, int primitivePolynomial)
      Get the object performs Galois field arithmetics.
      Parameters:
      fieldSize - size of the field
      primitivePolynomial - a primitive polynomial corresponds to the size
      Returns:
      GaloisField.

    • getInstance

      public static GaloisField getInstance()
      Get the object performs Galois field arithmetic with default setting.
      Returns:
      GaloisField.

    • getFieldSize

      public int getFieldSize()
      Return number of elements in the field
      Returns:
      number of elements in the field

    • getPrimitivePolynomial

      public int getPrimitivePolynomial()
      Return the primitive polynomial in GF(2)
      Returns:
      primitive polynomial as a integer

    • add

      public int add(int x, int y)
      Compute the sum of two fields
      Parameters:
      x - input field
      y - input field
      Returns:
      result of addition

    • multiply

      public int multiply(int x, int y)
      Compute the multiplication of two fields
      Parameters:
      x - input field
      y - input field
      Returns:
      result of multiplication

    • divide

      public int divide(int x, int y)
      Compute the division of two fields
      Parameters:
      x - input field
      y - input field
      Returns:
      x/y

    • power

      public int power(int x, int n)
      Compute power n of a field
      Parameters:
      x - input field
      n - power
      Returns:
      x^n

    • solveVandermondeSystem

      public void solveVandermondeSystem(int[] x, int[] y)
      Given a Vandermonde matrix V[i][j]=x[j]^i and vector y, solve for z such that Vz=y. The output z will be placed in y.
      Parameters:
      x - the vector which describe the Vandermonde matrix
      y - right-hand side of the Vandermonde system equation. will be replaced the output in this vector

    • solveVandermondeSystem

      public void solveVandermondeSystem(int[] x, int[] y, int len)
      Given a Vandermonde matrix V[i][j]=x[j]^i and vector y, solve for z such that Vz=y. The output z will be placed in y.
      Parameters:
      x - the vector which describe the Vandermonde matrix
      y - right-hand side of the Vandermonde system equation. will be replaced the output in this vector
      len - consider x and y only from 0...len-1

    • solveVandermondeSystem

      public void solveVandermondeSystem(int[] x, byte[][] y, int[] outputOffsets, int len, int dataLen)
      A "bulk" version to the solving of Vandermonde System.
      Parameters:
      x - input x.
      y - input y.
      outputOffsets - input outputOffsets.
      len - input len.
      dataLen - input dataLen.

    • solveVandermondeSystem

      public void solveVandermondeSystem(int[] x, ByteBuffer[] y, int len)
      A "bulk" version of the solveVandermondeSystem, using ByteBuffer.
      Parameters:
      x - input x.
      y - input y.
      len - input len.

    • multiply

      public int[] multiply(int[] p, int[] q)
      Compute the multiplication of two polynomials. The index in the array corresponds to the power of the entry. For example p[0] is the constant term of the polynomial p.
      Parameters:
      p - input polynomial
      q - input polynomial
      Returns:
      polynomial represents p*q

    • remainder

      public void remainder(int[] dividend, int[] divisor)
      Compute the remainder of a dividend and divisor pair. The index in the array corresponds to the power of the entry. For example p[0] is the constant term of the polynomial p.
      Parameters:
      dividend - dividend polynomial, the remainder will be placed here when return
      divisor - divisor polynomial

    • add

      public int[] add(int[] p, int[] q)
      Compute the sum of two polynomials. The index in the array corresponds to the power of the entry. For example p[0] is the constant term of the polynomial p.
      Parameters:
      p - input polynomial
      q - input polynomial
      Returns:
      polynomial represents p+q

    • substitute

      public int substitute(int[] p, int x)
      Substitute x into polynomial p(x).
      Parameters:
      p - input polynomial
      x - input field
      Returns:
      p(x)

    • substitute

      public void substitute(byte[][] p, byte[] q, int x)
      A "bulk" version of the substitute. Tends to be 2X faster than the "int" substitute in a loop.
      Parameters:
      p - input polynomial
      q - store the return result
      x - input field

    • substitute

      public void substitute(byte[][] p, int[] offsets, int len, byte[] q, int offset, int x)
      A "bulk" version of the substitute. Tends to be 2X faster than the "int" substitute in a loop.
      Parameters:
      p - input polynomial
      offsets - input offset.
      len - input len.
      q - store the return result
      offset - input offset.
      x - input field

    • substitute

      public void substitute(ByteBuffer[] p, int len, ByteBuffer q, int x)
      A "bulk" version of the substitute, using ByteBuffer. Tends to be 2X faster than the "int" substitute in a loop.
      Parameters:
      p - input polynomial
      q - store the return result
      x - input field
      len - input len.

    • remainder

      public void remainder(byte[][] dividend, int[] divisor)
      The "bulk" version of the remainder. Warning: This function will modify the "dividend" inputs.
      Parameters:
      divisor - divisor.
      dividend - dividend.

    • remainder

      public void remainder(byte[][] dividend, int[] offsets, int len, int[] divisor)
      The "bulk" version of the remainder. Warning: This function will modify the "dividend" inputs.
      Parameters:
      dividend - dividend.
      offsets - offsets.
      len - len.
      divisor - divisor.

    • remainder

      public void remainder(ByteBuffer[] dividend, int[] divisor)
      The "bulk" version of the remainder, using ByteBuffer. Warning: This function will modify the "dividend" inputs.
      Parameters:
      dividend - dividend.
      divisor - divisor.

    • gaussianElimination

      public void gaussianElimination(int[][] matrix)
      Perform Gaussian elimination on the given matrix. This matrix has to be a fat matrix (number of rows > number of columns).
      Parameters:
      matrix - matrix.