BinaryField.java

/* 
 * Reed-Solomon error-correcting code decoder (Java)
 * 
 * Copyright (c) 2019 Project Nayuki
 * All rights reserved. Contact Nayuki for licensing.
 * https://www.nayuki.io/page/reed-solomon-error-correcting-code-decoder
 */

import java.util.Objects;


/**
 * A Galois field of the form GF(2<sup><var>n</var></sup>/<var>mod</var>). Each element of this kind of
 * field is a polynomial of degree less than <var>n</var> where each monomial coefficient is either 0 or 1.
 * Both the field and the elements are immutable and thread-safe.
 */
public final class BinaryField extends Field<Integer> {
	
	/*---- Fields ----*/
	
	/**
	 * The modulus of this field represented as a string of bits in natural order.
	 * For example, the modulus <var>x</var>^5 + <var>x</var>^1 + <var>x</var>^0
	 * is represented by the integer value 0b100011 (binary) or 35 (decimal).
	 */
	public final int modulus;
	
	
	/**
	 * The number of (unique) elements in this field. It is a positive power of 2, e.g. 2, 4, 8, 16, etc.
	 * The size of the field is equal to 2 to the power of the degree of the modulus.
	 */
	public final int size;
	
	
	
	/*---- Constructor ----*/
	
	/**
	 * Constructs a binary field with the specified modulus. The modulus must have degree
	 * between 1 and 30, inclusive. Also the modulus must be irreducible (not factorable)
	 * in Z<sub>2</sub>, but this critical property is not checked by the constructor.
	 * @param mod the modulus polynomial
	 * @throws IllegalArgumentException if the modulus has degree less than 1
	 */
	public BinaryField(int mod) {
		if (mod <= 1)
			throw new IllegalArgumentException("Invalid modulus");
		modulus = mod;
		size = Integer.highestOneBit(mod);
	}
	
	
	
	/*---- Methods ----*/
	
	public Integer zero() {
		return 0;
	}
	
	public Integer one() {
		return 1;
	}
	
	
	public boolean equals(Integer x, Integer y) {
		return check(x) == check(y);
	}
	
	public Integer negate(Integer x) {
		return check(x);
	}
	
	public Integer add(Integer x, Integer y) {
		return check(x) ^ check(y);
	}
	
	public Integer subtract(Integer x, Integer y) {
		return add(x, y);
	}
	
	public Integer multiply(Integer x, Integer y) {
		return multiply(check(x), check(y));
	}
	
	
	private int multiply(int x, int y) {
		int result = 0;
		for (; y != 0; y >>>= 1) {
			result ^= (y & 1) * x;
			x <<= 1;
			if ((x & size) != 0)
				x ^= modulus;
		}
		return result;
	}
	
	
	public Integer reciprocal(Integer w) {
		// Extended Euclidean GCD algorithm
		int x = modulus;
		int y = check(w);
		if (y == 0)
			throw new ArithmeticException("Division by zero");
		int a = 0;
		int b = 1;
		while (y != 0) {
			int[] quotrem = divideAndRemainder(x, y);
			int c = a ^ multiply(quotrem[0], b);
			x = y;
			y = quotrem[1];
			a = b;
			b = c;
		}
		if (x == 1)
			return a;
		else  // All non-zero values must have a reciprocal
			throw new IllegalStateException("Field modulus is not irreducible");
	}
	
	
	// Returns a new array containing the pair of values (x div y, x mod y).
	private static int[] divideAndRemainder(int x, int y) {
		int quotient = 0;
		int topY = Integer.highestOneBit(y);
		for (int i = Integer.numberOfLeadingZeros(y) - Integer.numberOfLeadingZeros(x); i >= 0; i--) {
			if (((topY << i) & x) != 0) {
				x ^= y << i;
				quotient |= 1 << i;
			}
		}
		return new int[]{quotient, x};
	}
	
	
	// Checks if the given object is non-null and within the range
	// of valid values, and returns the unboxed primitive value.
	private int check(Integer x) {
		Objects.requireNonNull(x);
		int y = x.intValue();
		if (y < 0 || y >= size)
			throw new IllegalArgumentException("Not an element of this field: " + y);
		return y;
	}
	
}