trinomiallfsr.java

jpeg2000编解码

    private static final boolean PRE_COMPUTE_POWERS = true;
//    private static final boolean PRE_COMPUTE_POWERS = false;
    
    /**
     * Table of pre-computed 2n powers (n = 0, 2, 4, 8, 16, ..., 2*(L-1))
     * of the current polynomial. The value for the 0 power, instead
     * of storing the unity polynomial, will consist of the base
     * polynomial itself. This is necessary since the TrinomialLFSR
     * object is mutable and we need to assert if the current contents
     * of the hashtable are the powers of the current state/value of
     * this object.
     * <p>
     * Declared as transient so it doen't get serialised.
     */
    // [] is faster and more straightforward -- RSN.
//    private transient Hashtable powers;
    private transient TrinomialLFSR[] powers;


// Constructor
//...........................................................................

    /**
     * Define an LFSR with <code>L</code> stages and with a connection
     * trinomial of the form: <i>x<font size="-1"><sup>L</sup></font> +
     * x<font size="-1"><sup>K</sup></font> + 1.</i>
     *
     * @param  l  Size of the register; ie. number of levels/stages
     *         of this LFSR. Is also the <i>degree</i> of the <i>
     *         connection trinomial</i>.
     * @param  k  Degree/power of the <i>mid-tap</i> within the LFSR.
     * @exception  IllegalArgumentException  If k <= 0 or k >= l.
     */
    public TrinomialLFSR (int l, int k) {
        super(l);
        if (k < 1 || k > l - 1) throw new IllegalArgumentException();
        L = l;
        K = k;
        warpFactor = Math.min(K, L - K);
        slice = Math.min(64, warpFactor);
    }


// Cloneable method implementation
//...........................................................................

    public Object clone() {
        TrinomialLFSR result = new TrinomialLFSR(L, K);
        result.load(this);
        return result;
    }


// FSR methods
//...........................................................................
    
    /**
     * Repeatedly invoke the <code>engineClock()</code> method until
     * the LFSR has been clocked <code>ticks</code> times.
     *
     * @param  ticks  Number of steps to clock the FSR by. If it is
     *         &lt;= 0 nothing happens.
     */
    public void clock (int ticks) {
        if (ticks < 1) return;
        int morcel = ticks % slice;
        if (morcel != 0) {
            engineClock(morcel);
            ticks -= morcel;
        }
        while (ticks > 0) {
            engineClock(slice);
            ticks -= slice;
        }
    }

    /**
     * Clock the register <i>ticks</i> steps.
     *
     * @param  ticks  Number of steps to clock the register. It is the
     *         responsibility of the caller to ensure that this value
     *         never exceeds that of <code>slice</code>.
     */
    protected void engineClock (int ticks) {
        long io = getBits(L-ticks, ticks) ^ getBits(L-K-ticks, ticks);
        shiftLeft(ticks);
        if (io != 0) setBits(0, ticks, io);
    }

    private void jump (int ticks) {
        if (ticks < 1) return;
        int morcel = ticks % warpFactor;
        if (morcel != 0) {
            clock(morcel);
            ticks -= morcel;
        }
        BigRegister b1, b2;
        while (ticks > 0) {
            b1 = (BigRegister) clone();
            b2 = (BigRegister) clone();
            b2.shiftLeft(warpFactor);
            b2.xor(b1);
            b2.shiftRight(L-warpFactor);
            shiftLeft(warpFactor);
            or(b2);
            ticks -= warpFactor;
        }
    }
    
    /**
     * Return the value of the leftmost <code>count</code> bits of
     * this LFSR and clock it by as many ticks. Note however that
     * only the minimum of <code>count</code> and <code>slice</code>
     * bits, among those returned, are meaningful.
     *
     * @param  count  Number of leftmost bits to consider. If this
     *         value is zero then return 0.
     * @return The value of the leftmost <code>count</code> bits
     *         right justified in a <code>long</code>.
     */
    public long next (int count) {
        if (count < 1) return 0L;
        long result = getBits(L-count, count);
        clock(count);
        return result;
    }


// Arithmetical methods in GF(2**L) over (f(x) = x**L + x**K + 1)
//...........................................................................

    /**
     * Compute <code>this += gx (mod f(x))</code>. Note that this
     * operation is only meaningful, when the monic trinomial is primitive.
     *
     * @param  gx  A representation of the terms of a polynomial to add
     *         to <code>this</code>.
     * @exception  IllegalArgumentException  If the argument is not in
     *         the same group as <code>this</code>.
     */
    public void add (TrinomialLFSR gx) {
        if (! isSameGroup(gx)) throw new IllegalArgumentException();
        xor(gx);
    }

    /**
     * Compute <code>this -= gx (mod f(x))</code>. Note that this
     * operation is only meaningful, when the monic trinomial is
     * primitive. When such is the case the result is the same as
     * that obtained by the <code>add()</code> method since in <i>
     * F<font size="-1"><sub>2</sub>n</font></i> every polynomial is
     * its own additive inverse.
     *
     * @param  gx  A representation of the terms of a polynomial to
     *         subtract from <code>this</code>.
     * @exception  IllegalArgumentException  If the argument is not
     *         in the same group as <code>this</code>.
     */
    public void subtract (TrinomialLFSR gx) { add(gx); }

    /**
     * Compute <code>this *= gx (mod f(x))</code>. Note that this
     * operation is only meaningful, when the monic trinomial is primitive.
     *
     * @param  gx  A representation of the terms of a polynomial to
     *         multiply by <code>this</code>.
     * @exception  IllegalArgumentException  If the argument is not in
     *         the same group as <code>this</code>.
     */
    public void multiply (TrinomialLFSR gx) {
        if (! isSameGroup(gx)) throw new IllegalArgumentException();
        if (gx.countSetBits() == 0) {                        // x * 0 = 0
            reset();
            return;
        }
        TrinomialLFSR X = new TrinomialLFSR(L, K);    // 1st multiplicand
        TrinomialLFSR result = null;
        int t;
        for (int i = 0; i < L; i++) {
            if (gx.testBit(i)) {       // term #i in 2nd multiplicand set
                X.load(this);
                t = degreeAt(i);        // translate index to power/ticks
                if (t != 0) X.jump(t);                // multiply by x**t
                if (result == null)
                    result = (TrinomialLFSR) X.clone();
                else
                    result.add(X);
            }
        }
        load(result);
    }

    /**
     * Return the product of the two arguments modulo <i>f(x))</i>, where
     * both arguments are members of the same polynomial group with the
     * same monic trinomial <i>f(x)</i>. Note that this operation is only
     * meaningful, when the monic trinomial is primitive.
     *
     * @param  p  A representation of the terms of the first polynomial
     *         multiplicand.
     * @param  q  A representation of the terms of the second polynomial
     *         multiplicand.
     * @return The product of the two arguments modulo <i>f(x))</i>.
     * @exception  IllegalArgumentException  If the arguments are not
     *         from the same group.
     */
    public static TrinomialLFSR multiply (TrinomialLFSR p, TrinomialLFSR q) {
        if (! p.isSameGroup(q)) throw new IllegalArgumentException();
        // optimise performance by choosing the second operand to be the
        // one with fewer bits set
        TrinomialLFSR result;
        if (p.countSetBits() > q.countSetBits()) {
            result = (TrinomialLFSR) p.clone();
            result.multiply(q);
        } else {
            result = (TrinomialLFSR) q.clone();
            result.multiply(p);
        }
        return result;
    }

    /**
     * Raise <code>this</code> to the <code>n</code>th power modulo
     * <i>f(x))</i>. Note that this operation is only meaningful,
     * when the monic trinomial is primitive.
     *
     * @param  n  Bit representation of the power to raise this
     *         polynomial representation to.
     * @exception  IllegalArgumentException  If the argument's <code>
     *         size</code> is greater than that of <code>this</code>.
     */
    public void pow (BigRegister n) {
        if (n.getSize() > L) throw new IllegalArgumentException();
        //
        // Algorithm A (adapted from)
        // The Art of Computer Programming, Vol. 2. Donald E. Knuth; p.442.
        //
        int limit = n.highestSetBit();
        if (limit == 0) return;                       // (any)**1 = (any)
        if (limit == -1) {                              // (any)**0 = (1)
            resetX(0);
            return;
        }
        TrinomialLFSR Y = trinomialOne();
        TrinomialLFSR Z = (TrinomialLFSR) clone();
        if (PRE_COMPUTE_POWERS) {
/*
// Hashtable ................................................................
//
            if (powers == null) powers = new Hashtable(L);          // exist?
            boolean ok = powers.size() != 0;
            if (ok) {                                   // table is not empty
                // see if we haven't pre-computed the contents in an earlier
                // invocation. do so by checking if value at #0 is == this.
                TrinomialLFSR x = (TrinomialLFSR) powers.get(new Integer(0));
                ok = this.isSameValue(x);
            }
            if (! ok) {                              // pre-compute the table
                powers.clear();
                powers.put(new Integer(0), (TrinomialLFSR) Z.clone()); // hash #0 is this
                for (int i = 1, j = 2; i < L; i++, j <<= 1) {
                    Z.multiply(Z);
                    powers.put(new Integer(j), (TrinomialLFSR) Z.clone());
                }
            }
            // use it
            Y = n.testBit(0) ? (TrinomialLFSR) clone() : trinomialOne();
            int j = 2;
            for (int i = 1; i < limit; i++, j <<= 1)
                if (n.testBit(i)) {
                    Z = (TrinomialLFSR) powers.get(new Integer(j));
                    Y = multiply(Z, Y);
                }
            Z = (TrinomialLFSR) powers.get(new Integer(j));
*/
// Array ....................................................................