bigregister.java

jpeg2000编解码

// $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 BigRegister
implements 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