trinomiallfsr.java

jpeg2000编解码

// $Id: TrinomialLFSR.java,v 1.1.1.1 2002/08/27 12:32:15 grosbois Exp $
//
// $Log: TrinomialLFSR.java,v $
// Revision 1.1.1.1  2002/08/27 12:32:15  grosbois
// Add cryptix 3.2
//
// Revision 1.2  1997/11/22 07:05:41  raif
// *** empty log message ***
//
// + added handling of case param is null in isSame* methods.
// + optimised the pow method by pre-computing 2*n powers
//   of the base polynomial (the Z factors in Knuth Algorithm
//   A). This option comes into effect by setting the
//   PRE_COMPUTE_POWERS boolean constant to true (default)
//   and recompiling. Coded with 2 alternatives: Hashtable
//   and object array; object array is faster.
//
// 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, and sameGroup to isSameGroup.
// + 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 java.io.Serializable;
// import java.util.Hashtable;

/**
 * A class that implements a special category of Linear Feedback Shift
 * Register (LFSR). Formally speaking, it implements a <i>Fibonacci</i>
 * LFSR --LFSR(II)-- with a Monic, Non-Singular, Trinomial Connection
 * (Characteristic) function of the form <i>f(x) = x<font size="-1">
 * <sup>L</sup></font> + x<font size="-1"><sup>K</sup></font> + 1</i>.
 * <p>
 * <a href="#HAC"><cite>Menezes et al.</cite></a> define a generalised
 * LFSR --with an L-degree connection polynomial-- as follows:
 * <p>
 * An LFSR of length L consists of L <i>stages</i> (or <i>delay
 * elements</i>) numbered 0, 1, ..., L-1, each capable of storing one
 * bit and having one input and one output; and a <i>clock</i> which
 * controls the movement of data. During each unit of time the following
 * operations are performed:
 * <ul>
 *     <li>the contents of <i>stage</i> 0 is output and forms part
 *     of the <i>output sequence</i>;
 *     <li>the contents of <i>stage i</i> is moved to <i>stage i-1</i>
 *     for each <i>i, 1 <= i <= L-1</i>; and
 *     <li>the new contents of <i>stage L-1</i> is the <i>feedback bit
 *     s<font size="-1"><sub>j</sub></font></i> which is calculated by
 *     adding together modulo 2 the previous contents of a fixed subset
 *     of <i>stages 0, 1, ..., L-1</i> also called <i>taps</i>.
 * </ul><p>
 * Such an LFSR, referred to as a <i>Fibonacci LFSR</i>, <i>Type II LFSR
 * </i>, or simply <i>LFSR(II)</i>, is denoted by <i>&lt;L, C(D)&gt</i>,
 * where <i>C(D)</i> is called the <i>connection</i> or <i>characteristic
 * polynomial</i> and is defined as:<br>
 * <blockquote>
 *     C(D) = 1 + c<sub><font size="-1">1</font></sub>D + c<sub>
 *     <font size="-1">2</font></sub>D<sup><font size="-1">2</font></sup>
 *     + ... + c<sub><font size="-1">L</font></sub>D<sup><font size="-1">L
 *     </font></sup> <font face="Symbol">&Icirc;</FONT> Z<sub><font size=
 *     "-1">2</font></sub>[D]<br>
 * </blockquote>
 * A Linear Feedback Shift Register (LFSR) with a trinomial function of
 * the form <i>1 + x<font size="-1"><sup>K</sup></font> + x<font size=
 * "-1"><sup>L</sup></font></i> as its <i>connection polynomial</i> can
 * be schematised as follows:
 * <blockquote><pre>
 *  +--------------------XOR<-------------------------------+
 *  |                     ^                                 |
 *  |                     |                                 |
 *  |   +-----+-----+-----+-----+-----+-----+-----+-----+   |
 *  |   |stage|     |stage|stage|     |stage|stage|stage|   |
 *  +---| L-1 | ... | L-K |L-K-1| ... |  2  |  1  |  0  |---+--> output
 *      +-----+-----+-----+-----+-----+-----+-----+-----+
 *        K+1         L-1    0          K-3   K-2   K-1
 *      <------- Powers of the polynomial terms -------->
 
 * </pre></blockquote>
 * The following, collected from the references, are properties and
 * <i>curiosities</i> inherent to such objects:
 * <ul>
 *     <li>Choosing a primitive trinomial over <i>Z<font size="-1">
 *     <sub>2</sub></font></i>, ensures that each of the LFSR's <i>2<font
 *     size="-1"><sup>L</sup></font> - 1</i> initial states produces an
 *     output sequence with maximum possible period <i>2<font size="-1">
 *     <sup>L</sup></font> - 1</i>.
 *     <li>If <i>2<font size="-1"><sup>L</sup></font> - 1</i> is a prime
 *     (a <i>Mersenne prime</i>), then every irreducible polynomial of
 *     degree <i>L</i> in <i>Z<font size="-1"><sub>2</sub></font>[x]</i>
 *     is also primitive.
 *     <li>Irreducible trinomials, <i>f(x)</i>, of degree <i>L</i> can
 *     be used to represent the elements of the finite field <i>F<font
 *     size="-1"><sub>2</sub>L</font> = Z<font size="-1"><sub>2</sub></font>
 *     [x]/(f(x))</i>, the set of all polynomials in <i>Z<font size="-1">
 *     <sub>2</sub></font>[x]</i> of degree less than <i>L</i> where the
 *     addition and multiplication of polynomials is performed modulo
 *     <i>f(x)</i>.
 *     <li>If <i>f(x)</i> is a primitive polynomial of degree <i>L</i>,
 *     then <i>x<font size="-1"><sup>L</sup></font> f(x<font size="-1">
 *     <sup>-1</sup></font>) = f'(x)</i> is also a primitive polynomial.
 *     This is easily shown using the definition of a primitive polynomial,
 *     and the properties of modulo-2 arithmetic. A little thought shows
 *     that the register taps of <i>f'(x)</i> are the mirror image of those
 *     of <i>f(x)</i>. And the sequence produced by the tap-reversed
 *     generator is the time reversal of the original.
 * </ul><p>
 * Some terms and conventions associated with LFSRs, and used in this
 * implementation, are:
 * <ul>
 *     <li><b>tap-sequence</b>: the powers of the terms of the
 *     polynomial. In a monic (starts with <i>1 + ...</i>), non-
 *     singular (the term <i>x<sup><font size="-1">L</font></sup></i>
 *     for an <i>L</i>-long register is part of the polynomial function)
 *     trinomial, the sequence consists of 3 elements: 0, K, and L.
 *
 *     <li><b>mid-tap</b>: the second/middle value of the tap sequence
 *     of a monic, non-singular trinomial.
 *
 *     <li><b>state</b>: the value of the LFSR's contents. Also used
 *     to represent the coefficients of a polynomial in the field
 *     <i>F<font size="-1"><sub>2</sub>L</font></i>.
 *
 *     <li><b>terms of a polynomial</b>: the correspondence between
 *     the LFSR <i>stages</i> and the powers of <i>x</i> (the polynomial
 *     invariate) in the <i>GF[<font size="-1"><sub>2</sub>L</font>]</i>
 *     with <i>f(x) = x<font size="-1"><sup>L</sup></font> + x<font size=
 *     "-1"><sup>K</sup></font> + 1</i> is such that the term with degree
 *     0 is at <i>stage L - K - 1</i>; the term with degree 1 is at <i>
 *     stage L - K - 2</i>, etc... After <i>stage</i> 0, the relationship
 *     restarts from <code>stage</code> <i>L - 1</i>. The reason for this
 *     gymnastic is to facilitate computing the successive powers of <i>x
 *     </i> --based on the mathematical fact that <i>g(x) = x</i> is a
 *     generator of the monic primitive <i>f(x)</i>-- which in turn are
 *     used in the computation of polynomial multiplication modulo <i>f(x)
 *     </i>. When so ordered, multiplying a polynomial <i>p(x)</i> by <i>x
 *     <font size="-1"><sup>t</sup></font></i> modulo <i>f(x)</i> is as
 *     simple as loading the LFSR's register with the terms of the
 *     polynomial, and clocking it by <i>t</i> cycles.
 * </ul>
 * Finally, <a href="#HAC"><cite>Menezes et al.</cite></a> lists (Table 4.9,
 * p.162) some primitive polynomials of degree <i>m</i> over <i>Z<font size=
 * "-1"><sub>2</sub></font>, 2<font size="-1"><sup>m</sup></font> - 1</i> a
 * <i>Mersenne prime</i>. The following is an excerpt from this table for
 * values of <i>m, m <= 4096</i> and <i>k, 1 <= k <= m/2</i>, for which the
 * monic, non-singular trinomial <i>x<font size="-1"><sup>m</sup></font>
 * + x<font size="-1"><sup>k</sup></font> + 1</i> is irreducible over <i>
 * Z<font size="-1"><sub>2</sub></font></i>.
 * <blockquote><pre>
 *    m  |  k
 * ------+------------------------------
 *    2  |    1
 *    3  |    1
 *    5  |    2
 *    7  |    1,    3
 *   17  |    3,    5,     6
 *   31  |    3,    6,     7,   13
 *   89  |   38
 *  127  |    1,    7,    15,   30,  63
 *  521  |   32,   48,   158,  168
 *  607  |  105,  147,   273
 * 1279  |  216,  418
 * 2281  |  715,  915,  1029
 * 3217  |   67,  576
 * </pre></blockquote>
 * <b>Implementation Notes:</b>
 * <p>
 * In order to increase performance of this class, and since it's extending
 * <code>BigRegister</code>, which assumes a bit numbering using bit index
 * 0 as the rightmost one, our LFSR will actually look like so:
 * <blockquote><pre>
 *     +------------------->XOR--------------------------------+
 *     |                     ^                                 |
 *     |                     |                                 |
 *     |   +-----+-----+-----+-----+-----+-----+-----+-----+   |
 *     |   | bit |     | bit | bit |     | bit | bit | bit |   |
 *  <--+---| L-1 | ... | L-K |L-K-1| ... |  2  |  1  |  0  |<--+
 *         +-----+-----+-----+-----+-----+-----+-----+-----+
 *           K-1          0    L-1         K+2   K+1    K
 *         <------- Powers of the polynomial terms -------->
 * </pre></blockquote>
 * Obtaining a normal representation of the powers of the polynomial
 * is done by left rotating the LFSR's contents by <i>K</i> positions.
 * <p>
 * Clocking the LFSR consists of executing the following pseudo-code:
 * <pre>
 *     out = getBit(L-1);
 *     in = out ^ getBit(L-K-1);
 *     shiftLeft(1);
 *     if (in == 1) setBit(0);
 * </pre>
 * <p>
 * <b>References:</b>
 * <ol>
 *   <li> <a name="HAC">[HAC]</a>
 *        A. J. Menezes, P. C. van Oorschot, S. A. Vanstone,
 *        <cite>Handbook of Applied Cryptography</cite>
 *        CRC Press 1997, pp 195-212.
 *        <p>
 *   <li> <a name="AC2">[AC2]</a>
 *        Bruce Schneier,
 *        <cite>Applied Cryptography, 2nd edition</cite>,
 *        John Wiley &amp; Sons, Inc. 1996, pp 372-428.
 *        <p>
 *   <li> <a name="LFSR">[LFSR]</a>
 *        Arthur H. M. Ross,
 *        <cite>Linear Feedback Shift Registers</cite>,
 *        WWW page <a href="http://www.cdg.org/a_ross/LFSR.html">
 *        www.cdg.org/a_ross/LFSR.html</a>
 * </ol>
 * <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
 * @since   Cryptix 2.2.2
 */
public class TrinomialLFSR
extends BigRegister
implements Cloneable, Serializable
{
// Variables and constants
//...........................................................................

    /**
     * Number of stages/delay elements in this LFSR which is also
     * the <i>degree</i> of the <i>connection trinomial</i>.
     */
    private int L;

    /** Degree (power) of the <i>mid-tap</i> connection. */
    private int K;

    /**
     * Clocking is the process of computing the new feedback bit from
     * the output one and feeding it back to the end of the register.
     * On a bit by bit basis, this looks like so:
     * <pre>
     *     out = getBit(L-1);
     *     in = out ^ getBit(L-K-1);
     *     shiftLeft(1);
     *     if (in == 1) setBit(0);
     * </pre>
     * It is clear from the above that better efficiency and speed
     * can be achieved if we can process a larger chunck of bits at
     * a time than just one bit.
     * <p>
     * This variable is here for exactly this purpose. It tells us
     * how many bits we can alter with maximum efficiency. It is
     * computed at instantiation time as the min(64, K, L-K).
     */
    private int slice;
    private int warpFactor;

    private static final long serialVersionUID = -8054549768481919515L;

    /** Make this false and recompile if space is rare. */