// $Id: BigRegister.java,v 1.1.1.1 2002/08/27 12:32:15 grosbois Exp $//// $Log: BigRegister.java,v $// Revision 1.1.1.1  2002/08/27 12:32:15  grosbois// Add cryptix 3.2//// Revision 1.2  1999/06/30 22:44:36  edwin// synchronized classes are evil//// Revision 1.1.1.1  1997/11/20 22:05:46  hopwood// + Moved BigRegister and TrinomialLFSR here from the cryptix.util package.//// Revision 1.1.1  1997/11/20  David Hopwood// + Renamed equals to isSameValue.// + Moved to cryptix.util.math package.//// Revision 1.1  1997/11/07 05:53:26  raif// *** empty log message ***//// Revision 0.1.3  1997/10/01 09:04:24  raif// *** empty log message ***//// Revision 0.1.1  1997/09/25  R. Naffah// + Original version.//// $Endlog$/* * Copyright (c) 1997 Systemics Ltd * on behalf of the Cryptix Development Team. All rights reserved. */package cryptix.util.math;import cryptix.util.core.ArrayUtil;import java.io.Serializable;import java.security.SecureRandom;/** * Utility class to manage a large bit-register of a given size as a * <b>mutable</b> object. * <p> * The bits are indexed from <i>0</i> (rightmost) to <i><code>size</code> * - 1</i>, (leftmost) where <code>size</code> is this register's * designated (at instantiation time) bit capacity. * <p> * <b>Copyright</b> &copy; 1995-1997 * <a href="http://www.systemics.com/">Systemics Ltd</a> on behalf of the * <a href="http://www.systemics.com/docs/cryptix/">Cryptix Development Team</a>. * <br>All rights reserved. * <p> * <b>$Revision: 1.1.1.1 $</b> * @author  Raif S. Naffah */public class BigRegisterimplements Cloneable, Serializable{// Constants and variables//.....................................................................    /** Maximum allowed number of bits in a <code>BigRegister</code> object. */    public static final int MAXIMUM_SIZE = 4096;    // Number of bits in the binary representaion of x, 0 <= x <= 127    private static final byte[] log2x = {        0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,        5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,        6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,        6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,        7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,        7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,        7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,        7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7};    // index of highest set bit in a 4-bit value    private static final byte[] high = {        0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3};    // index of lowest set bit in a 4-bit value    private static final byte[] low = {        0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0};    private static final String[] binaryDigits = {        "0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111",        "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"};    private static final String m_1 = "size < 2";    private static final String m_2 = "size > MAXIMUM_SIZE";    private static final SecureRandom prng = new SecureRandom();    private byte[] bits;    private int size;    private static final long serialVersionUID = 2535877383275048954L;// Constructors//.....................................................................    /**     * Instantiate a <code>BigRegister</code> of a given <code>size</code>     * with all its bits set to zeroes.     *     * @param  size  Number of meaningful bits in <code>this</code> object.     * @exception  IllegalArgumentException  If the argument is less than     *         2 or greater than the maximum allowed value.     * @see    #MAXIMUM_SIZE     */    public BigRegister (int size) {        if (size < 2) throw new IllegalArgumentException(m_1);        if (size > MAXIMUM_SIZE) throw new IllegalArgumentException(m_2);        this.size = size;        bits = new byte[(size + 7) / 8];    // multiple of 8    }    // Constructor to implement cloneability    private BigRegister (BigRegister r) {        this.size = r.size;        this.bits = (byte[]) (r.bits.clone());    }// Cloneable method implementation//...........................................................................    /** Return a reference to a duplicate of <code>this</code>. */    public synchronized Object clone() { return new BigRegister(this); }// Bit logical operators//.....................................................................    /**     * Compute <code>this &amp;= source</code>.     *     * @exception  IllegalArgumentException  If the argument is of     *     different <code>size</code> than <code>this</code>.     */    public synchronized void and (BigRegister source) {        if (size != source.size) throw new IllegalArgumentException();        for (int i = 0; i < bits.length; i++)            bits[i] &= source.bits[i];    }    /**     * Compute <code>this &amp;= ~source</code>.     *     * @exception  IllegalArgumentException  If the argument is of     *     different <code>size</code> than <code>this</code>.     */    public synchronized void andNot (BigRegister source) {        if (size != source.size) throw new IllegalArgumentException();        for (int i = 0; i < bits.length; i++)            bits[i] &= ~source.bits[i];    }    /**     * Compute <code>this |= source</code>.     *     * @exception  IllegalArgumentException  If the argument is of     *     different <code>size</code> than <code>this</code>.     */    public synchronized void or (BigRegister source) {        if (size != source.size) throw new IllegalArgumentException();        for (int i = 0; i < bits.length; i++)            bits[i] |= source.bits[i];        pad();    }    /**     * Compute <code>this = ~this</code>.     */    public synchronized void not () {        for (int i = 0; i < bits.length; i++)            bits[i] = (byte) ~bits[i];        pad();    }    /**     * Compute <code>this ^= source</code>.     *     * @exception  IllegalArgumentException  If the argument is of     *     different <code>size</code> than <code>this</code>.     */    public synchronized void xor (BigRegister source) {        if (size != source.size) throw new IllegalArgumentException();        for (int i = 0; i < bits.length; i++)            bits[i] ^= source.bits[i];        pad();    }// Shift operators//.....................................................................    /**     * Execute a left shift of <code>this BigRegister</code>'s contents     * by a given number of bit positions. If the number is negative, a     * right shift is executed.     *     * @param  n  Number of bit positions to shift by. If this value     *         is negative then a shift in the opposite direction is     *         executed.     */    public synchronized void shiftLeft (int n) {        if (n == 0) return;        if (n < 0) {            shiftRight(-n);            return;        }        if (n >= size) {            reset();            return;        }        int start = lowestSetBit();        if (start == -1) return;                // all zeroes        if (start >= size - n) {                // all 1s will disappear            reset();            return;        }        start = n / 8;        int offset = n % 8;        int length = bits.length;        byte[] result = new byte[length];        if (offset == 0)            System.arraycopy(bits, 0, result, start, length - start);        else {            int offsetBar = 8 - offset;            for (int i = start, j = 0; i < length; i++, j++)                result[i] = (byte) (                    bits[j] << offset |                    (j == 0 ? 0 : (bits[j - 1] & 0xFF) >>> offsetBar)                );        }        bits = result;        pad();    }    /**     * Execute a right shift of <code>this BigRegister</code>'s contents     * by a given number of bit positions. If the number is negative, a     * left shift is executed.     *     * @param  n  Number of bit positions to shift by. If this value     *         is negative then a shift in the opposite direction is     *         executed.     */    public synchronized void shiftRight (int n) {        if (n == 0) return;        if (n < 0) {            shiftLeft(-n);            return;        }        if (n >= size) {            reset();            return;        }        int start = highestSetBit();            // index of last bit to move        if (start < 0) return;                    // all zeroes anyway        if (start < n) {                        // all 1s will go            reset();            return;        }        start = n / 8;        int offset = n % 8;        int length = bits.length;        byte[] result = new byte[length];        if (offset == 0)            System.arraycopy(bits, start, result, 0, length - start);        else            for (int i = 0, j = start; i < length && j < length; i++, j++)                result[i] = (byte) (                    ((j == length - 1 ? 0 : bits[j + 1] << 8) | (bits[j] & 0xFF)) >>> offset                );        bits = result;        pad();    }// Rotation operators//.....................................................................    /**     * Circular left shift over the <code>size</code> of <code>this</code>     * register.     * <p>     * Effectively compute <code>this = this << n | this >> (size - n)</code>.     * <p>     * If the number of positions to rotate by is negative, then a     * right instead of left rotation is executed.     */    public synchronized void rotateLeft (int n) {        n = n % size;        if (n == 0) return;        if (n < 0)            rotateRight(-n);        else {            BigRegister same = (BigRegister) clone();            same.shiftRight(size - n);            shiftLeft(n);            or(same);        }    }    /**     * Circular right shift over the <code>size</code> of <code>this</code>     * register.     * <p>     * Effectively compute <code>this = this >> n | this << (size - n)</code>.     * <p>     * If the number of positions to rotate by is negative, then a     * left instead of right rotation is executed.     */    public synchronized void rotateRight (int n) {        n = n % size;        if (n == 0) return;        if (n < 0)            rotateLeft(-n);        else {            BigRegister same = (BigRegister) clone();            same.shiftLeft(size - n);            shiftRight(n);            or(same);        }    }    /** Invert the bit order of the current contents of <code>this</code>. */    public synchronized void invertOrder () {        byte[] result = new byte[bits.length];        for (int i = 0, j = size - 1; i < size; i++, j--)            if (testBit(i)) result[j / 8] |= 1 << (j % 8);        bits = result;    }// Test and comparison operators//.....................................................................    /**     * Return true if the designated bit is set or false otherwise.     *     * @param  n  Index of the bit to test.     * @return true if the designated bit is set or false otherwise.     */    public synchronized boolean testBit (int n) {        if (n < 0 || n > size) throw new IllegalArgumentException();        return (bits[n / 8] & (1 << (n % 8))) != 0;    }    /**     * Return true if the parameters of the BigRegister <i>x</i>     * (<code>size</code> and <code>bits</code>) are equal to this one;     * false otherwise.     * <p>     * NOTE: the <code>equals</code> method is not used, because this is     * a mutable object (see the requirements for equals in the Java Language     * Spec).     *     * @param  x  BigRegister to test for equality.     * @return true iff x has equal <code>size</code> and contents.     */    public synchronized boolean isSameValue (BigRegister x) {        if (x.size != size) return false;        return ArrayUtil.areEqual(bits, x.bits);    }    /**     * Compare <code>this BigRegister</code>'s contents to that of the