hadoop-mapreduce/src/contrib/raid/src/test/org/apache/hadoop/raid/TestGaloisField.java

/**
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.hadoop.raid;

import java.util.Random;
import java.util.Set;
import java.util.HashSet;

import junit.framework.TestCase;

public class TestGaloisField extends TestCase {

  final int TEST_TIMES = 10000;
  final Random RAND = new Random();
  final static GaloisField GF = GaloisField.getInstance();

  private int randGF() {
    return 0x000000FF & RAND.nextInt(GF.getFieldSize());
  }
  private int[] randGFPoly(int len) {
    int[] result = new int[len];
    for (int i = 0; i < len; i++) {
      result[i] = randGF();
    }
    return result;
  }

  public void testGetInstance() {
    GaloisField gf1 = GaloisField.getInstance(256, 285);
    GaloisField gf2 = GaloisField.getInstance();
    GaloisField gf3 = GaloisField.getInstance(128, 137);
    GaloisField gf4 = GaloisField.getInstance(128, 137);
    GaloisField gf5 = GaloisField.getInstance(512, 529);
    GaloisField gf6 = GaloisField.getInstance(512, 529);
    assertTrue(gf1 == gf2);
    assertTrue(gf3 == gf4);
    assertTrue(gf5 == gf6);
  }

  public void testDistributivity() {
    for (int i = 0; i < TEST_TIMES; i++) {
      int a = RAND.nextInt(GF.getFieldSize());
      int b = RAND.nextInt(GF.getFieldSize());
      int c = RAND.nextInt(GF.getFieldSize());
      int result1 = GF.multiply(a, GF.add(b, c));
      int result2 = GF.add(GF.multiply(a, b), GF.multiply(a, c));
      assertTrue("Distributivity test #" + i + " failed: " + a + ", " + b + ", "
                 + c, result1 == result2);
    }
  }

  public void testDevision() {
    for (int i = 0; i < TEST_TIMES; i++) {
      int a = RAND.nextInt(GF.getFieldSize());
      int b = RAND.nextInt(GF.getFieldSize());
      if (b == 0) {
        continue;
      }
      int c = GF.divide(a, b);
      assertTrue("Division test #" + i + " failed: " + a + "/" + b + " = " + c,
                 a == GF.multiply(c, b));
    }
  }

  public void testPower() {
    for (int i = 0; i < TEST_TIMES; i++) {
      int a = randGF();
      int n = RAND.nextInt(10);
      int result1 = GF.power(a, n);
      int result2 = 1;
      for (int j = 0; j < n; j++) {
        result2 = GF.multiply(result2, a);
      }
      assert(result1 == result2);
    }
  }

  public void testPolynomialDistributivity() {
    final int TEST_LEN = 15;
    for (int i = 0; i < TEST_TIMES; i++) {
      int[] a = randGFPoly(RAND.nextInt(TEST_LEN - 1) + 1);
      int[] b = randGFPoly(RAND.nextInt(TEST_LEN - 1) + 1);
      int[] c = randGFPoly(RAND.nextInt(TEST_LEN - 1) + 1);
      int[] result1 = GF.multiply(a, GF.add(b, c));
      int[] result2 = GF.add(GF.multiply(a, b), GF.multiply(a, c));
      assertTrue("Distributivity test on polynomials failed",
                 java.util.Arrays.equals(result1, result2));
    }
  }

  public void testSubstitute() {
    final int TEST_LEN = 15;
    for (int i = 0; i < TEST_TIMES; i++) {
      int[] a = randGFPoly(RAND.nextInt(TEST_LEN - 1) + 1);
      int[] b = randGFPoly(RAND.nextInt(TEST_LEN - 1) + 1);
      int[] c = randGFPoly(RAND.nextInt(TEST_LEN - 1) + 1);
      int x = randGF();
      // (a * b * c)(x)
      int result1 = GF.substitute(GF.multiply(GF.multiply(a, b), c), x);
      // a(x) * b(x) * c(x)
      int result2 =
        GF.multiply(GF.multiply(GF.substitute(a, x), GF.substitute(b, x)),
                    GF.substitute(c, x));
      assertTrue("Substitute test on polynomial failed",
                 result1 == result2);
    }
  }

  public void testSolveVandermondeSystem() {
    final int TEST_LEN = 15;
    for (int i = 0; i < TEST_TIMES; i++) {
      int[] z = randGFPoly(RAND.nextInt(TEST_LEN - 1) + 1);
      // generate distinct values for x
      int[] x = new int[z.length];
      Set<Integer> s = new HashSet<Integer>();
      while (s.size() != z.length) {
        s.add(randGF());
      }
      int t = 0;
      for (int v : s) {
        x[t++] = v;
      }
      // compute the output for the Vandermonde system
      int[] y = new int[x.length];
      for (int j = 0; j < x.length; j++) {
        y[j] = 0;
        for (int k = 0; k < x.length; k++) {
          //y[j] = y[j] + z[k] * pow(x[k], j);
          y[j] = GF.add(y[j], GF.multiply(GF.power(x[k], j), z[k]));
        }
      }

      GF.solveVandermondeSystem(x, y);
      assertTrue("Solving Vandermonde system failed",
                 java.util.Arrays.equals(y, z));
    }
  }

  public void testRemainder() {
    final int TEST_LEN = 15;
    for (int i = 0; i < TEST_TIMES; i++) {
      int[] quotient = null;
      int[] divisor = null;
      int[] remainder = null;
      int[] dividend = null;
      while (true) {
        quotient = randGFPoly(RAND.nextInt(TEST_LEN - 3) + 3);
        divisor = randGFPoly(RAND.nextInt(quotient.length - 2) + 2);
        remainder = randGFPoly(RAND.nextInt(divisor.length - 1) + 1);
        dividend = GF.add(remainder, GF.multiply(quotient, divisor));
        if (quotient[quotient.length - 1] != 0 &&
            divisor[divisor.length - 1] != 0 &&
            remainder[remainder.length - 1] != 0) {
          // make sure all the leading terms are not zero
          break;
        }
      }
      GF.remainder(dividend, divisor);
      for (int j = 0; j < remainder.length; j++) {
        assertTrue("Distributivity test on polynomials failed",
                   dividend[j] == remainder[j]);
      }
    }
  }
}