Repository: hadoop Updated Branches: refs/heads/HDFS-7285 2516efd8a -> e74644311
HADOOP-11542. Raw Reed-Solomon coder in pure Java. Contributed by Kai Zheng Project: http://git-wip-us.apache.org/repos/asf/hadoop/repo Commit: http://git-wip-us.apache.org/repos/asf/hadoop/commit/e7464431 Tree: http://git-wip-us.apache.org/repos/asf/hadoop/tree/e7464431 Diff: http://git-wip-us.apache.org/repos/asf/hadoop/diff/e7464431 Branch: refs/heads/HDFS-7285 Commit: e746443111b89690dbefd0595d8ab346e38cc101 Parents: 2516efd Author: drankye <dran...@gmail.com> Authored: Thu Feb 12 21:12:44 2015 +0800 Committer: drankye <dran...@gmail.com> Committed: Thu Feb 12 21:12:44 2015 +0800 ---------------------------------------------------------------------- .../hadoop-common/CHANGES-HDFS-EC-7285.txt | 4 + .../io/erasurecode/rawcoder/JRSRawDecoder.java | 69 +++ .../io/erasurecode/rawcoder/JRSRawEncoder.java | 78 +++ .../erasurecode/rawcoder/RawErasureCoder.java | 2 +- .../erasurecode/rawcoder/util/GaloisField.java | 497 +++++++++++++++++++ .../io/erasurecode/rawcoder/util/RSUtil.java | 22 + .../hadoop/io/erasurecode/TestCoderBase.java | 28 +- .../erasurecode/rawcoder/TestJRSRawCoder.java | 93 ++++ .../erasurecode/rawcoder/TestRawCoderBase.java | 5 +- .../erasurecode/rawcoder/TestXorRawCoder.java | 1 - 10 files changed, 786 insertions(+), 13 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/hadoop/blob/e7464431/hadoop-common-project/hadoop-common/CHANGES-HDFS-EC-7285.txt ---------------------------------------------------------------------- diff --git a/hadoop-common-project/hadoop-common/CHANGES-HDFS-EC-7285.txt b/hadoop-common-project/hadoop-common/CHANGES-HDFS-EC-7285.txt index 9728f97..7bbacf7 100644 --- a/hadoop-common-project/hadoop-common/CHANGES-HDFS-EC-7285.txt +++ b/hadoop-common-project/hadoop-common/CHANGES-HDFS-EC-7285.txt @@ -8,3 +8,7 @@ HADOOP-11541. Raw XOR coder ( Kai Zheng ) + + HADOOP-11542. Raw Reed-Solomon coder in pure Java. Contributed by Kai Zheng + ( Kai Zheng ) + http://git-wip-us.apache.org/repos/asf/hadoop/blob/e7464431/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/io/erasurecode/rawcoder/JRSRawDecoder.java ---------------------------------------------------------------------- diff --git a/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/io/erasurecode/rawcoder/JRSRawDecoder.java b/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/io/erasurecode/rawcoder/JRSRawDecoder.java new file mode 100644 index 0000000..dbb689e --- /dev/null +++ b/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/io/erasurecode/rawcoder/JRSRawDecoder.java @@ -0,0 +1,69 @@ +/** + * 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.io.erasurecode.rawcoder; + +import org.apache.hadoop.io.erasurecode.rawcoder.util.RSUtil; + +import java.nio.ByteBuffer; + +/** + * A raw erasure decoder in RS code scheme in pure Java in case native one + * isn't available in some environment. Please always use native implementations + * when possible. + */ +public class JRSRawDecoder extends AbstractRawErasureDecoder { + // To describe and calculate the needed Vandermonde matrix + private int[] errSignature; + private int[] primitivePower; + + @Override + public void initialize(int numDataUnits, int numParityUnits, int chunkSize) { + super.initialize(numDataUnits, numParityUnits, chunkSize); + assert (getNumDataUnits() + getNumParityUnits() < RSUtil.GF.getFieldSize()); + + this.errSignature = new int[getNumParityUnits()]; + this.primitivePower = RSUtil.getPrimitivePower(getNumDataUnits(), + getNumParityUnits()); + } + + @Override + protected void doDecode(ByteBuffer[] inputs, int[] erasedIndexes, + ByteBuffer[] outputs) { + for (int i = 0; i < erasedIndexes.length; i++) { + errSignature[i] = primitivePower[erasedIndexes[i]]; + RSUtil.GF.substitute(inputs, outputs[i], primitivePower[i]); + } + + int dataLen = inputs[0].remaining(); + RSUtil.GF.solveVandermondeSystem(errSignature, outputs, + erasedIndexes.length, dataLen); + } + + @Override + protected void doDecode(byte[][] inputs, int[] erasedIndexes, + byte[][] outputs) { + for (int i = 0; i < erasedIndexes.length; i++) { + errSignature[i] = primitivePower[erasedIndexes[i]]; + RSUtil.GF.substitute(inputs, outputs[i], primitivePower[i]); + } + + int dataLen = inputs[0].length; + RSUtil.GF.solveVandermondeSystem(errSignature, outputs, + erasedIndexes.length, dataLen); + } +} http://git-wip-us.apache.org/repos/asf/hadoop/blob/e7464431/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/io/erasurecode/rawcoder/JRSRawEncoder.java ---------------------------------------------------------------------- diff --git a/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/io/erasurecode/rawcoder/JRSRawEncoder.java b/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/io/erasurecode/rawcoder/JRSRawEncoder.java new file mode 100644 index 0000000..6ea7551 --- /dev/null +++ b/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/io/erasurecode/rawcoder/JRSRawEncoder.java @@ -0,0 +1,78 @@ +/** + * 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.io.erasurecode.rawcoder; + +import org.apache.hadoop.io.erasurecode.rawcoder.util.RSUtil; + +import java.nio.ByteBuffer; + +/** + * A raw erasure encoder in RS code scheme in pure Java in case native one + * isn't available in some environment. Please always use native implementations + * when possible. + */ +public class JRSRawEncoder extends AbstractRawErasureEncoder { + private int[] generatingPolynomial; + + @Override + public void initialize(int numDataUnits, int numParityUnits, int chunkSize) { + super.initialize(numDataUnits, numParityUnits, chunkSize); + assert (getNumDataUnits() + getNumParityUnits() < RSUtil.GF.getFieldSize()); + + int[] primitivePower = RSUtil.getPrimitivePower(getNumDataUnits(), + getNumParityUnits()); + // compute generating polynomial + int[] gen = {1}; + int[] poly = new int[2]; + for (int i = 0; i < getNumParityUnits(); i++) { + poly[0] = primitivePower[i]; + poly[1] = 1; + gen = RSUtil.GF.multiply(gen, poly); + } + // generating polynomial has all generating roots + generatingPolynomial = gen; + } + + @Override + protected void doEncode(ByteBuffer[] inputs, ByteBuffer[] outputs) { + ByteBuffer[] data = new ByteBuffer[getNumDataUnits() + getNumParityUnits()]; + for (int i = 0; i < getNumParityUnits(); i++) { + data[i] = outputs[i]; + } + for (int i = 0; i < getNumDataUnits(); i++) { + data[i + getNumParityUnits()] = inputs[i]; + } + + // Compute the remainder + RSUtil.GF.remainder(data, generatingPolynomial); + } + + @Override + protected void doEncode(byte[][] inputs, byte[][] outputs) { + byte[][] data = new byte[getNumDataUnits() + getNumParityUnits()][]; + for (int i = 0; i < getNumParityUnits(); i++) { + data[i] = outputs[i]; + } + for (int i = 0; i < getNumDataUnits(); i++) { + data[i + getNumParityUnits()] = inputs[i]; + } + + // Compute the remainder + RSUtil.GF.remainder(data, generatingPolynomial); + } +} http://git-wip-us.apache.org/repos/asf/hadoop/blob/e7464431/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/io/erasurecode/rawcoder/RawErasureCoder.java ---------------------------------------------------------------------- diff --git a/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/io/erasurecode/rawcoder/RawErasureCoder.java b/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/io/erasurecode/rawcoder/RawErasureCoder.java index 91a9abf..6e07cf1 100644 --- a/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/io/erasurecode/rawcoder/RawErasureCoder.java +++ b/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/io/erasurecode/rawcoder/RawErasureCoder.java @@ -71,7 +71,7 @@ public interface RawErasureCoder { public boolean preferNativeBuffer(); /** - * Should be called when release this coder. Good chance to release encoding + * Should be called when release this blockcoder. Good chance to release encoding * or decoding buffers */ public void release(); http://git-wip-us.apache.org/repos/asf/hadoop/blob/e7464431/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/io/erasurecode/rawcoder/util/GaloisField.java ---------------------------------------------------------------------- diff --git a/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/io/erasurecode/rawcoder/util/GaloisField.java b/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/io/erasurecode/rawcoder/util/GaloisField.java new file mode 100644 index 0000000..77544c6 --- /dev/null +++ b/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/io/erasurecode/rawcoder/util/GaloisField.java @@ -0,0 +1,497 @@ +/** + * 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.io.erasurecode.rawcoder.util; + +import java.nio.ByteBuffer; +import java.util.HashMap; +import java.util.Map; + +/** + * Implementation of Galois field arithmetic with 2^p elements. The input must + * be unsigned integers. It's ported from HDFS-RAID, slightly adapted. + */ +public class GaloisField { + + // Field size 256 is good for byte based system + private static final int DEFAULT_FIELD_SIZE = 256; + // primitive polynomial 1 + X^2 + X^3 + X^4 + X^8 (substitute 2) + private static final int DEFAULT_PRIMITIVE_POLYNOMIAL = 285; + static private final Map<Integer, GaloisField> instances = + new HashMap<Integer, GaloisField>(); + private final int[] logTable; + private final int[] powTable; + private final int[][] mulTable; + private final int[][] divTable; + private final int fieldSize; + private final int primitivePeriod; + private final int primitivePolynomial; + + private GaloisField(int fieldSize, int primitivePolynomial) { + assert fieldSize > 0; + assert primitivePolynomial > 0; + + this.fieldSize = fieldSize; + this.primitivePeriod = fieldSize - 1; + this.primitivePolynomial = primitivePolynomial; + logTable = new int[fieldSize]; + powTable = new int[fieldSize]; + mulTable = new int[fieldSize][fieldSize]; + divTable = new int[fieldSize][fieldSize]; + int value = 1; + for (int pow = 0; pow < fieldSize - 1; pow++) { + powTable[pow] = value; + logTable[value] = pow; + value = value * 2; + if (value >= fieldSize) { + value = value ^ primitivePolynomial; + } + } + // building multiplication table + for (int i = 0; i < fieldSize; i++) { + for (int j = 0; j < fieldSize; j++) { + if (i == 0 || j == 0) { + mulTable[i][j] = 0; + continue; + } + int z = logTable[i] + logTable[j]; + z = z >= primitivePeriod ? z - primitivePeriod : z; + z = powTable[z]; + mulTable[i][j] = z; + } + } + // building division table + for (int i = 0; i < fieldSize; i++) { + for (int j = 1; j < fieldSize; j++) { + if (i == 0) { + divTable[i][j] = 0; + continue; + } + int z = logTable[i] - logTable[j]; + z = z < 0 ? z + primitivePeriod : z; + z = powTable[z]; + divTable[i][j] = z; + } + } + } + + /** + * Get the object performs Galois field arithmetics + * + * @param fieldSize size of the field + * @param primitivePolynomial a primitive polynomial corresponds to the size + */ + public static GaloisField getInstance(int fieldSize, + int primitivePolynomial) { + int key = ((fieldSize << 16) & 0xFFFF0000) + + (primitivePolynomial & 0x0000FFFF); + GaloisField gf; + synchronized (instances) { + gf = instances.get(key); + if (gf == null) { + gf = new GaloisField(fieldSize, primitivePolynomial); + instances.put(key, gf); + } + } + return gf; + } + + /** + * Get the object performs Galois field arithmetic with default setting + */ + public static GaloisField getInstance() { + return getInstance(DEFAULT_FIELD_SIZE, DEFAULT_PRIMITIVE_POLYNOMIAL); + } + + /** + * Return number of elements in the field + * + * @return number of elements in the field + */ + public int getFieldSize() { + return fieldSize; + } + + /** + * Return the primitive polynomial in GF(2) + * + * @return primitive polynomial as a integer + */ + public int getPrimitivePolynomial() { + return primitivePolynomial; + } + + /** + * Compute the sum of two fields + * + * @param x input field + * @param y input field + * @return result of addition + */ + public int add(int x, int y) { + assert (x >= 0 && x < getFieldSize() && y >= 0 && y < getFieldSize()); + return x ^ y; + } + + /** + * Compute the multiplication of two fields + * + * @param x input field + * @param y input field + * @return result of multiplication + */ + public int multiply(int x, int y) { + assert (x >= 0 && x < getFieldSize() && y >= 0 && y < getFieldSize()); + return mulTable[x][y]; + } + + /** + * Compute the division of two fields + * + * @param x input field + * @param y input field + * @return x/y + */ + public int divide(int x, int y) { + assert (x >= 0 && x < getFieldSize() && y > 0 && y < getFieldSize()); + return divTable[x][y]; + } + + /** + * Compute power n of a field + * + * @param x input field + * @param n power + * @return x^n + */ + public int power(int x, int n) { + assert (x >= 0 && x < getFieldSize()); + if (n == 0) { + return 1; + } + if (x == 0) { + return 0; + } + x = logTable[x] * n; + if (x < primitivePeriod) { + return powTable[x]; + } + x = x % primitivePeriod; + return powTable[x]; + } + + /** + * 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. + * + * @param x the vector which describe the Vandermonde matrix + * @param y right-hand side of the Vandermonde system equation. will be + * replaced the output in this vector + */ + public void solveVandermondeSystem(int[] x, int[] y) { + solveVandermondeSystem(x, y, x.length); + } + + /** + * 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. + * + * @param x the vector which describe the Vandermonde matrix + * @param y right-hand side of the Vandermonde system equation. will be + * replaced the output in this vector + * @param len consider x and y only from 0...len-1 + */ + public void solveVandermondeSystem(int[] x, int[] y, int len) { + assert (x.length <= len && y.length <= len); + for (int i = 0; i < len - 1; i++) { + for (int j = len - 1; j > i; j--) { + y[j] = y[j] ^ mulTable[x[i]][y[j - 1]]; + } + } + for (int i = len - 1; i >= 0; i--) { + for (int j = i + 1; j < len; j++) { + y[j] = divTable[y[j]][x[j] ^ x[j - i - 1]]; + } + for (int j = i; j < len - 1; j++) { + y[j] = y[j] ^ y[j + 1]; + } + } + } + + /** + * A "bulk" version to the solving of Vandermonde System + */ + public void solveVandermondeSystem(int[] x, byte[][] y, + int len, int dataLen) { + for (int i = 0; i < len - 1; i++) { + for (int j = len - 1; j > i; j--) { + for (int k = 0; k < dataLen; k++) { + y[j][k] = (byte) (y[j][k] ^ mulTable[x[i]][y[j - 1][k] & + 0x000000FF]); + } + } + } + for (int i = len - 1; i >= 0; i--) { + for (int j = i + 1; j < len; j++) { + for (int k = 0; k < dataLen; k++) { + y[j][k] = (byte) (divTable[y[j][k] & 0x000000FF][x[j] ^ + x[j - i - 1]]); + } + } + for (int j = i; j < len - 1; j++) { + for (int k = 0; k < dataLen; k++) { + y[j][k] = (byte) (y[j][k] ^ y[j + 1][k]); + } + } + } + } + + /** + * A "bulk" version of the solveVandermondeSystem, using ByteBuffer. + */ + public void solveVandermondeSystem(int[] x, ByteBuffer[] y, + int len, int dataLen) { + for (int i = 0; i < len - 1; i++) { + for (int j = len - 1; j > i; j--) { + for (int k = 0; k < dataLen; k++) { + y[j].put(k, (byte) (y[j].get(k) ^ mulTable[x[i]][y[j - 1].get(k) & + 0x000000FF])); + } + } + } + for (int i = len - 1; i >= 0; i--) { + for (int j = i + 1; j < len; j++) { + for (int k = 0; k < dataLen; k++) { + y[j].put(k, (byte) (divTable[y[j].get(k) & 0x000000FF][x[j] ^ + x[j - i - 1]])); + } + } + for (int j = i; j < len - 1; j++) { + for (int k = 0; k < dataLen; k++) { + y[j].put(k, (byte) (y[j].get(k) ^ y[j + 1].get(k))); + } + } + } + } + + /** + * 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. + * + * @param p input polynomial + * @param q input polynomial + * @return polynomial represents p*q + */ + public int[] multiply(int[] p, int[] q) { + int len = p.length + q.length - 1; + int[] result = new int[len]; + for (int i = 0; i < len; i++) { + result[i] = 0; + } + for (int i = 0; i < p.length; i++) { + + for (int j = 0; j < q.length; j++) { + result[i + j] = add(result[i + j], multiply(p[i], q[j])); + } + } + return result; + } + + /** + * 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. + * + * @param dividend dividend polynomial, the remainder will be placed + * here when return + * @param divisor divisor polynomial + */ + public void remainder(int[] dividend, int[] divisor) { + for (int i = dividend.length - divisor.length; i >= 0; i--) { + int ratio = divTable[dividend[i + + divisor.length - 1]][divisor[divisor.length - 1]]; + for (int j = 0; j < divisor.length; j++) { + int k = j + i; + dividend[k] = dividend[k] ^ mulTable[ratio][divisor[j]]; + } + } + } + + /** + * 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. + * + * @param p input polynomial + * @param q input polynomial + * @return polynomial represents p+q + */ + public int[] add(int[] p, int[] q) { + int len = Math.max(p.length, q.length); + int[] result = new int[len]; + for (int i = 0; i < len; i++) { + if (i < p.length && i < q.length) { + result[i] = add(p[i], q[i]); + } else if (i < p.length) { + result[i] = p[i]; + } else { + result[i] = q[i]; + } + } + return result; + } + + /** + * Substitute x into polynomial p(x). + * + * @param p input polynomial + * @param x input field + * @return p(x) + */ + public int substitute(int[] p, int x) { + int result = 0; + int y = 1; + for (int i = 0; i < p.length; i++) { + result = result ^ mulTable[p[i]][y]; + y = mulTable[x][y]; + } + return result; + } + + /** + * A "bulk" version of the substitute. + * Tends to be 2X faster than the "int" substitute in a loop. + * + * @param p input polynomial + * @param q store the return result + * @param x input field + */ + public void substitute(byte[][] p, byte[] q, int x) { + int y = 1; + for (int i = 0; i < p.length; i++) { + byte[] pi = p[i]; + for (int j = 0; j < pi.length; j++) { + int pij = pi[j] & 0x000000FF; + q[j] = (byte) (q[j] ^ mulTable[pij][y]); + } + y = mulTable[x][y]; + } + } + + /** + * A "bulk" version of the substitute, using ByteBuffer. + * Tends to be 2X faster than the "int" substitute in a loop. + * + * @param p input polynomial + * @param q store the return result + * @param x input field + */ + public void substitute(ByteBuffer[] p, ByteBuffer q, int x) { + int y = 1; + for (int i = 0; i < p.length; i++) { + ByteBuffer pi = p[i]; + int len = pi.remaining(); + for (int j = 0; j < len; j++) { + int pij = pi.get(j) & 0x000000FF; + q.put(j, (byte) (q.get(j) ^ mulTable[pij][y])); + } + y = mulTable[x][y]; + } + } + + /** + * The "bulk" version of the remainder. + * Warning: This function will modify the "dividend" inputs. + */ + public void remainder(byte[][] dividend, int[] divisor) { + for (int i = dividend.length - divisor.length; i >= 0; i--) { + for (int j = 0; j < divisor.length; j++) { + for (int k = 0; k < dividend[i].length; k++) { + int ratio = divTable[dividend[i + divisor.length - 1][k] & + 0x00FF][divisor[divisor.length - 1]]; + dividend[j + i][k] = (byte) ((dividend[j + i][k] & 0x00FF) ^ + mulTable[ratio][divisor[j]]); + } + } + } + } + + /** + * The "bulk" version of the remainder, using ByteBuffer. + * Warning: This function will modify the "dividend" inputs. + */ + public void remainder(ByteBuffer[] dividend, int[] divisor) { + for (int i = dividend.length - divisor.length; i >= 0; i--) { + int width = dividend[i].remaining(); + for (int j = 0; j < divisor.length; j++) { + for (int k = 0; k < width; k++) { + int ratio = divTable[dividend[i + divisor.length - 1].get(k) & + 0x00FF][divisor[divisor.length - 1]]; + dividend[j + i].put(k, (byte) ((dividend[j + i].get(k) & 0x00FF) ^ + mulTable[ratio][divisor[j]])); + } + } + } + } + + /** + * Perform Gaussian elimination on the given matrix. This matrix has to be a + * fat matrix (number of rows > number of columns). + */ + public void gaussianElimination(int[][] matrix) { + assert(matrix != null && matrix.length > 0 && matrix[0].length > 0 + && matrix.length < matrix[0].length); + int height = matrix.length; + int width = matrix[0].length; + for (int i = 0; i < height; i++) { + boolean pivotFound = false; + // scan the column for a nonzero pivot and swap it to the diagonal + for (int j = i; j < height; j++) { + if (matrix[i][j] != 0) { + int[] tmp = matrix[i]; + matrix[i] = matrix[j]; + matrix[j] = tmp; + pivotFound = true; + break; + } + } + if (!pivotFound) { + continue; + } + int pivot = matrix[i][i]; + for (int j = i; j < width; j++) { + matrix[i][j] = divide(matrix[i][j], pivot); + } + for (int j = i + 1; j < height; j++) { + int lead = matrix[j][i]; + for (int k = i; k < width; k++) { + matrix[j][k] = add(matrix[j][k], multiply(lead, matrix[i][k])); + } + } + } + for (int i = height - 1; i >=0; i--) { + for (int j = 0; j < i; j++) { + int lead = matrix[j][i]; + for (int k = i; k < width; k++) { + matrix[j][k] = add(matrix[j][k], multiply(lead, matrix[i][k])); + } + } + } + } + +} http://git-wip-us.apache.org/repos/asf/hadoop/blob/e7464431/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/io/erasurecode/rawcoder/util/RSUtil.java ---------------------------------------------------------------------- diff --git a/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/io/erasurecode/rawcoder/util/RSUtil.java b/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/io/erasurecode/rawcoder/util/RSUtil.java new file mode 100644 index 0000000..33ba561 --- /dev/null +++ b/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/io/erasurecode/rawcoder/util/RSUtil.java @@ -0,0 +1,22 @@ +package org.apache.hadoop.io.erasurecode.rawcoder.util; + +/** + * Some utilities for Reed-Solomon coding. + */ +public class RSUtil { + + // We always use the byte system (with symbol size 8, field size 256, + // primitive polynomial 285, and primitive root 2). + public static GaloisField GF = GaloisField.getInstance(); + public static final int PRIMITIVE_ROOT = 2; + + public static int[] getPrimitivePower(int numDataUnits, int numParityUnits) { + int[] primitivePower = new int[numDataUnits + numParityUnits]; + // compute powers of the primitive root + for (int i = 0; i < numDataUnits + numParityUnits; i++) { + primitivePower[i] = GF.power(PRIMITIVE_ROOT, i); + } + return primitivePower; + } + +} http://git-wip-us.apache.org/repos/asf/hadoop/blob/e7464431/hadoop-common-project/hadoop-common/src/test/java/org/apache/hadoop/io/erasurecode/TestCoderBase.java ---------------------------------------------------------------------- diff --git a/hadoop-common-project/hadoop-common/src/test/java/org/apache/hadoop/io/erasurecode/TestCoderBase.java b/hadoop-common-project/hadoop-common/src/test/java/org/apache/hadoop/io/erasurecode/TestCoderBase.java index 9482b43..3c4288c 100644 --- a/hadoop-common-project/hadoop-common/src/test/java/org/apache/hadoop/io/erasurecode/TestCoderBase.java +++ b/hadoop-common-project/hadoop-common/src/test/java/org/apache/hadoop/io/erasurecode/TestCoderBase.java @@ -18,9 +18,11 @@ package org.apache.hadoop.io.erasurecode; import java.nio.ByteBuffer; +import java.util.Arrays; import java.util.Random; import static org.junit.Assert.assertArrayEquals; +import static org.junit.Assert.assertTrue; /** * Test base of common utilities for tests not only raw coders but also block @@ -41,6 +43,14 @@ public abstract class TestCoderBase { // may go to different coding implementations. protected boolean usingDirectBuffer = true; + protected void prepare(int numDataUnits, int numParityUnits, + int[] erasedIndexes) { + this.numDataUnits = numDataUnits; + this.numParityUnits = numParityUnits; + this.erasedDataIndexes = erasedIndexes != null ? + erasedIndexes : new int[] {0}; + } + /** * Compare and verify if erased chunks are equal to recovered chunks * @param erasedChunks @@ -50,10 +60,8 @@ public abstract class TestCoderBase { ECChunk[] recoveredChunks) { byte[][] erased = ECChunk.toArray(erasedChunks); byte[][] recovered = ECChunk.toArray(recoveredChunks); - for (int i = 0; i < erasedChunks.length; ++i) { - assertArrayEquals("Decoding and comparing failed.", erased[i], - recovered[i]); - } + boolean result = Arrays.deepEquals(erased, recovered); + assertTrue("Decoding and comparing failed.", result); } /** @@ -63,7 +71,7 @@ public abstract class TestCoderBase { */ protected int[] getErasedIndexesForDecoding() { int[] erasedIndexesForDecoding = new int[erasedDataIndexes.length]; - for (int i = 0; i < erasedDataIndexes.length; ++i) { + for (int i = 0; i < erasedDataIndexes.length; i++) { erasedIndexesForDecoding[i] = erasedDataIndexes[i] + numParityUnits; } return erasedIndexesForDecoding; @@ -100,7 +108,7 @@ public abstract class TestCoderBase { ECChunk[] copiedChunks = new ECChunk[erasedDataIndexes.length]; int j = 0; - for (int i = 0; i < erasedDataIndexes.length; ++i) { + for (int i = 0; i < erasedDataIndexes.length; i++) { copiedChunks[j ++] = cloneChunkWithData(dataChunks[erasedDataIndexes[i]]); } @@ -112,7 +120,7 @@ public abstract class TestCoderBase { * @param dataChunks */ protected void eraseSomeDataBlocks(ECChunk[] dataChunks) { - for (int i = 0; i < erasedDataIndexes.length; ++i) { + for (int i = 0; i < erasedDataIndexes.length; i++) { eraseDataFromChunk(dataChunks[erasedDataIndexes[i]]); } } @@ -122,7 +130,7 @@ public abstract class TestCoderBase { * @param chunks */ protected void eraseDataFromChunks(ECChunk[] chunks) { - for (int i = 0; i < chunks.length; ++i) { + for (int i = 0; i < chunks.length; i++) { eraseDataFromChunk(chunks[i]); } } @@ -135,7 +143,7 @@ public abstract class TestCoderBase { ByteBuffer chunkBuffer = chunk.getBuffer(); // erase the data chunkBuffer.position(0); - for (int i = 0; i < chunkSize; ++i) { + for (int i = 0; i < chunkSize; i++) { chunkBuffer.put((byte) 0); } chunkBuffer.flip(); @@ -150,7 +158,7 @@ public abstract class TestCoderBase { */ protected static ECChunk[] cloneChunksWithData(ECChunk[] chunks) { ECChunk[] results = new ECChunk[chunks.length]; - for (int i = 0; i < chunks.length; ++i) { + for (int i = 0; i < chunks.length; i++) { results[i] = cloneChunkWithData(chunks[i]); } http://git-wip-us.apache.org/repos/asf/hadoop/blob/e7464431/hadoop-common-project/hadoop-common/src/test/java/org/apache/hadoop/io/erasurecode/rawcoder/TestJRSRawCoder.java ---------------------------------------------------------------------- diff --git a/hadoop-common-project/hadoop-common/src/test/java/org/apache/hadoop/io/erasurecode/rawcoder/TestJRSRawCoder.java b/hadoop-common-project/hadoop-common/src/test/java/org/apache/hadoop/io/erasurecode/rawcoder/TestJRSRawCoder.java new file mode 100644 index 0000000..e54f647 --- /dev/null +++ b/hadoop-common-project/hadoop-common/src/test/java/org/apache/hadoop/io/erasurecode/rawcoder/TestJRSRawCoder.java @@ -0,0 +1,93 @@ +/** + * 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.io.erasurecode.rawcoder; + +import org.apache.hadoop.io.erasurecode.ECChunk; +import org.apache.hadoop.io.erasurecode.rawcoder.util.RSUtil; +import org.junit.Before; +import org.junit.Test; + +import java.nio.ByteBuffer; + +/** + * Test raw Reed-solomon encoding and decoding. + */ +public class TestJRSRawCoder extends TestRawCoderBase { + + private static int symbolSize = 0; + private static int symbolMax = 0; + + static { + symbolSize = (int) Math.round(Math.log( + RSUtil.GF.getFieldSize()) / Math.log(2)); + symbolMax = (int) Math.pow(2, symbolSize); + } + + @Before + public void setup() { + this.encoderClass = JRSRawEncoder.class; + this.decoderClass = JRSRawDecoder.class; + } + + @Test + public void testCodingNoDirectBuffer_10x4() { + prepare(10, 4, null); + testCoding(false); + } + + @Test + public void testCodingDirectBuffer_10x4() { + prepare(10, 4, null); + testCoding(true); + } + + @Test + public void testCodingDirectBuffer_10x4_erasure_of_2_4() { + prepare(10, 4, new int[] {2, 4}); + testCoding(true); + } + + @Test + public void testCodingDirectBuffer_10x4_erasing_all() { + prepare(10, 4, new int[] {0, 1, 2, 3}); + testCoding(true); + } + + @Test + public void testCodingNoDirectBuffer_3x3() { + prepare(3, 3, null); + testCoding(false); + } + + @Test + public void testCodingDirectBuffer_3x3() { + prepare(3, 3, null); + testCoding(true); + } + + @Override + protected ECChunk generateDataChunk() { + ByteBuffer buffer = allocateOutputBuffer(); + for (int i = 0; i < chunkSize; i++) { + buffer.put((byte) RAND.nextInt(symbolMax)); + } + buffer.flip(); + + return new ECChunk(buffer); + } +} http://git-wip-us.apache.org/repos/asf/hadoop/blob/e7464431/hadoop-common-project/hadoop-common/src/test/java/org/apache/hadoop/io/erasurecode/rawcoder/TestRawCoderBase.java ---------------------------------------------------------------------- diff --git a/hadoop-common-project/hadoop-common/src/test/java/org/apache/hadoop/io/erasurecode/rawcoder/TestRawCoderBase.java b/hadoop-common-project/hadoop-common/src/test/java/org/apache/hadoop/io/erasurecode/rawcoder/TestRawCoderBase.java index 9119211..5f6ccda 100644 --- a/hadoop-common-project/hadoop-common/src/test/java/org/apache/hadoop/io/erasurecode/rawcoder/TestRawCoderBase.java +++ b/hadoop-common-project/hadoop-common/src/test/java/org/apache/hadoop/io/erasurecode/rawcoder/TestRawCoderBase.java @@ -31,10 +31,13 @@ public abstract class TestRawCoderBase extends TestCoderBase { * Generating source data, encoding, recovering and then verifying. * RawErasureCoder mainly uses ECChunk to pass input and output data buffers, * it supports two kinds of ByteBuffers, one is array backed, the other is - * direct ByteBuffer. Have usingDirectBuffer to indicate which case to test. + * direct ByteBuffer. Use usingDirectBuffer indicate which case to test. + * * @param usingDirectBuffer */ protected void testCoding(boolean usingDirectBuffer) { + this.usingDirectBuffer = usingDirectBuffer; + // Generate data and encode ECChunk[] dataChunks = prepareDataChunksForEncoding(); ECChunk[] parityChunks = prepareParityChunksForEncoding(); http://git-wip-us.apache.org/repos/asf/hadoop/blob/e7464431/hadoop-common-project/hadoop-common/src/test/java/org/apache/hadoop/io/erasurecode/rawcoder/TestXorRawCoder.java ---------------------------------------------------------------------- diff --git a/hadoop-common-project/hadoop-common/src/test/java/org/apache/hadoop/io/erasurecode/rawcoder/TestXorRawCoder.java b/hadoop-common-project/hadoop-common/src/test/java/org/apache/hadoop/io/erasurecode/rawcoder/TestXorRawCoder.java index 8e59b8a..ff48586 100644 --- a/hadoop-common-project/hadoop-common/src/test/java/org/apache/hadoop/io/erasurecode/rawcoder/TestXorRawCoder.java +++ b/hadoop-common-project/hadoop-common/src/test/java/org/apache/hadoop/io/erasurecode/rawcoder/TestXorRawCoder.java @@ -26,7 +26,6 @@ import java.util.Random; * Test XOR encoding and decoding. */ public class TestXorRawCoder extends TestRawCoderBase { - private static Random RAND = new Random(); @Before public void setup() {