/* * CVS identifier: * * $Id: MQCoder.java,v 1.33 2001/02/14 10:45:50 grosbois Exp $ * * Class:                   MQCoder * * Description:             Class that encodes a number of bits using the *                          MQ arithmetic coder * * *                          Diego SANTA CRUZ, Jul-26-1999 (improved speed) * * COPYRIGHT: *  * This software module was originally developed by Rapha雔 Grosbois and * Diego Santa Cruz (Swiss Federal Institute of Technology-EPFL); Joel * Askel鰂 (Ericsson Radio Systems AB); and Bertrand Berthelot, David * Bouchard, F閘ix Henry, Gerard Mozelle and Patrice Onno (Canon Research * Centre France S.A) in the course of development of the JPEG2000 * standard as specified by ISO/IEC 15444 (JPEG 2000 Standard). This * software module is an implementation of a part of the JPEG 2000 * Standard. Swiss Federal Institute of Technology-EPFL, Ericsson Radio * Systems AB and Canon Research Centre France S.A (collectively JJ2000 * Partners) agree not to assert against ISO/IEC and users of the JPEG * 2000 Standard (Users) any of their rights under the copyright, not * including other intellectual property rights, for this software module * with respect to the usage by ISO/IEC and Users of this software module * or modifications thereof for use in hardware or software products * claiming conformance to the JPEG 2000 Standard. Those intending to use * this software module in hardware or software products are advised that * their use may infringe existing patents. The original developers of * this software module, JJ2000 Partners and ISO/IEC assume no liability * for use of this software module or modifications thereof. No license * or right to this software module is granted for non JPEG 2000 Standard * conforming products. JJ2000 Partners have full right to use this * software module for his/her own purpose, assign or donate this * software module to any third party and to inhibit third parties from * using this software module for non JPEG 2000 Standard conforming * products. This copyright notice must be included in all copies or * derivative works of this software module. *  * Copyright (c) 1999/2000 JJ2000 Partners. * */package jj2000.j2k.entropy.encoder;import jj2000.j2k.entropy.encoder.*;import jj2000.j2k.entropy.*;import jj2000.j2k.util.*;import jj2000.j2k.*;import java.io.*;/** * This class implements the MQ arithmetic coder. When initialized a specific * state can be specified for each context, which may be adapted to the * probability distribution that is expected for that context. * * <P>The type of length calculation and termination can be chosen at * construction time. *  * ---- Tricks that have been tried to improve speed ---- * * 1) Merging Qe and mPS and doubling the lookup tables * * Merge the mPS into Qe, as the sign bit (if Qe>=0 the sense of MPS is 0, if * Qe<0 the sense is 1), and double the lookup tables. The first half of the * lookup tables correspond to Qe>=0 (i.e. the sense of MPS is 0) and the * second half to Qe<0 (i.e. the sense of MPS is 1). The nLPS lookup table is * modified to incorporate the changes in the sense of MPS, by making it jump * from the first to the second half and vice-versa, when a change is * specified by the swicthLM lookup table. See JPEG book, section 13.2, page * 225.  * * There is NO speed improvement in doing this, actually there is a slight * decrease, probably due to the fact that often Q has to be negated. Also the * fact that a brach of the type "if (bit==mPS[li])" is replaced by two * simpler braches of the type "if (bit==0)" and "if (q<0)" may contribute to * that. * * 2) Removing cT * * It is possible to remove the cT counter by setting a flag bit in the high * bits of the C register. This bit will be automatically shifted left * whenever a renormalization shift occurs, which is equivalent to decreasing * cT. When the flag bit reaches the sign bit (leftmost bit), which is * equivalenet to cT==0, the byteOut() procedure is called. This test can be * done efficiently with "c<0" since C is a signed quantity. Care must be * taken in byteOut() to reset the bit in order to not interfere with other * bits in the C register. See JPEG book, page 228. * * There is NO speed improvement in doing this. I don't really know why since * the number of operations whenever a renormalization occurs is * decreased. Maybe it is due to the number of extra operations in the * byteOut(), terminate() and getNumCodedBytes() procedures. * * * 3) Change the convention of MPS and LPS. * * Making the LPS interval be above the MPS interval (MQ coder convention is * the opposite) can reduce the number of operations along the MPS path. In * order to generate the same bit stream as with the MQ convention the output * bytes need to be modified accordingly. The basic rule for this is that C = * (C'^0xFF...FF)-A, where C is the codestream for the MQ convention and C' is * the codestream generated by this other convention. Note that this affects * bit-stuffing as well. * * This has not been tested yet. * * 4) Removing normalization while loop on MPS path * * Since in the MPS path Q is guaranteed to be always greater than 0x4000 * (decimal 0.375) it is never necessary to do more than 1 renormalization * shift. Therefore the test of the while loop, and the loop itself, can be * removed. * * 5) Simplifying test on A register * * Since A is always less than or equal to 0xFFFF, the test "(a & 0x8000)==0" * can be replaced by the simplete test "a < 0x8000". This test is simpler in * Java since it involves only 1 operation (although the original test can be * converted to only one operation by  smart Just-In-Time compilers) * * This change has been integrated in the decoding procedures. * * 6) Speedup mode * * Implemented a method that uses the speedup mode of the MQ-coder if * possible. This should greately improve performance when coding long runs of  * MPS symbols that have high probability. However, to take advantage of this,  * the entropy coder implementation has to explicetely use it. The generated * bit stream is the same as if no speedup mode would have been used. * * Implemented but performance not tested yet. * * 7) Multiple-symbol coding * * Since the time spent in a method call is non-negligable, coding several * symbols with one method call reduces the overhead per coded symbol. The * decodeSymbols() method implements this. However, to take advantage of it, * the implementation of the entropy coder has to explicitely use it. * * Implemented but performance not tested yet. *  */public class MQCoder {    /** Identifier for the lazy length calculation. The lazy length     * calculation is not optimal but is extremely simple. */    public static final int LENGTH_LAZY = 0;    /** Identifier for a very simple length calculation. This provides better     * results than the 'LENGTH_LAZY' computation. This is the old length     * calculation that was implemented in this class. */    public static final int LENGTH_LAZY_GOOD = 1;    /** Identifier for the near optimal length calculation. This calculation     * is more complex than the lazy one but provides an almost optimal length      * calculation. */    public static final int LENGTH_NEAR_OPT = 2;    /** The identifier fort the termination that uses a full flush. This is     * the less efficient termination. */    public static final int TERM_FULL = 0;    /** The identifier for the termination that uses the near optimal length     * calculation to terminate the arithmetic codewrod */    public static final int TERM_NEAR_OPT = 1;    /** The identifier for the easy termination that is simpler than the     * 'TERM_NEAR_OPT' one but slightly less efficient. */    public static final int TERM_EASY = 2;    /** The identifier for the predictable termination policy for error     * resilience. This is the same as the 'TERM_EASY' one but an special     * sequence of bits is embodied in the spare bits for error resilience     * purposes. */    public static final int TERM_PRED_ER = 3;    /** The data structures containing the probabilities for the LPS */    final static        int qe[]={0x5601, 0x3401, 0x1801, 0x0ac1, 0x0521, 0x0221, 0x5601,                  0x5401, 0x4801, 0x3801, 0x3001, 0x2401, 0x1c01, 0x1601,                   0x5601, 0x5401, 0x5101, 0x4801, 0x3801, 0x3401, 0x3001,                  0x2801, 0x2401, 0x2201, 0x1c01, 0x1801, 0x1601, 0x1401,                  0x1201, 0x1101, 0x0ac1, 0x09c1, 0x08a1, 0x0521, 0x0441,                  0x02a1, 0x0221, 0x0141, 0x0111, 0x0085, 0x0049, 0x0025,                  0x0015, 0x0009, 0x0005, 0x0001, 0x5601 };        /** The indexes of the next MPS */    final static        int nMPS[]={ 1 , 2, 3, 4, 5,38, 7, 8, 9,10,11,12,13,29,15,16,17,                     18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,                     35,36,37,38,39,40,41,42,43,44,45,45,46 };    /** The indexes of the next LPS */    final static        int nLPS[]={ 1 , 6, 9,12,29,33, 6,14,14,14,17,18,20,21,14,14,15,                     16,17,18,19,19,20,21,22,23,24,25,26,27,28,29,30,31,                     32,33,34,35,36,37,38,39,40,41,42,43,46 };    /** Whether LPS and MPS should be switched */    final static        // at indices 0, 6, and 14 we switch        int switchLM[]={ 1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,                         0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 };    // Having ints proved to be more efficient than booleans    /** The ByteOutputBuffer used to write the compressed bit stream. */    ByteOutputBuffer out;    /** The current most probable signal for each context */    int[] mPS;    /** The current index of each context */    int[] I;    /** The current bit code */    int c;    /** The bit code counter */    int cT;    /** The current interval */    int a;    /** The last encoded byte of data */    int b;    /** If a 0xFF byte has been delayed and not yet been written to the output      * (in the MQ we can never have more than 1 0xFF byte in a row). */    boolean delFF;    /** The number of written bytes so far, excluding any delayed 0xFF     * bytes. Upon initialization it is -1 to indicated that the byte buffer     * 'b' is empty as well. */    int nrOfWrittenBytes = -1;    /** The initial state of each context */    int initStates[];    /** The termination type to use. One of 'TERM_FULL', 'TERM_NEAR_OPT',     * 'TERM_EASY' or 'TERM_PRED_ER'. */    int ttype;    /** The length calculation type to use. One of 'LENGTH_LAZY',     * 'LENGTH_LAZY_GOOD', 'LENGTH_NEAR_OPT'. */    int ltype;    /** Saved values of the C register. Used for the LENGTH_NEAR_OPT length     * calculation. */    int savedC[];    /** Saved values of CT counter. Used for the LENGTH_NEAR_OPT length     * calculation. */    int savedCT[];    /** Saved values of the A register. Used for the LENGTH_NEAR_OPT length     * calculation. */    int savedA[];    /** Saved values of the B byte buffer. Used for the LENGTH_NEAR_OPT length     * calculation. */    int savedB[];    /** Saved values of the delFF (i.e. delayed 0xFF) state. Used for the     * LENGTH_NEAR_OPT length calculation. */    boolean savedDelFF[];    /** Number of saved states. Used for the LENGTH_NEAR_OPT length     * calculation. */    int nSaved;    /** The initial length of the arrays to save sates */    final static int SAVED_LEN = 32*StdEntropyCoderOptions.NUM_PASSES;    /** The increase in length for the arrays to save states */    final static int SAVED_INC = 4*StdEntropyCoderOptions.NUM_PASSES;    /**      * Set the length calculation type to the specified type      *     * @param ltype The type of length calculation to use. One of     * 'LENGTH_LAZY', 'LENGTH_LAZY_GOOD' or 'LENGTH_NEAR_OPT'.     * */    public void setLenCalcType(int ltype){        // Verify the ttype and ltype        if (ltype != LENGTH_LAZY && ltype != LENGTH_LAZY_GOOD &&            ltype != LENGTH_NEAR_OPT) {            throw new IllegalArgumentException("Unrecognized length "+                                               "calculation type code: "+ltype);        }        if(ltype == LENGTH_NEAR_OPT){	    if(savedC==null)		savedC = new int[SAVED_LEN];	    if(savedCT==null)		savedCT = new int[SAVED_LEN];	    if(savedA==null)		savedA = new int[SAVED_LEN];	    if(savedB==null)	    		savedB = new int[SAVED_LEN];	    if(savedDelFF==null)		savedDelFF = new boolean[SAVED_LEN];        }        this.ltype = ltype;    }    /**      * Set termination type to the specified type      *     * @param ttype The type of termination to use. One of 'TERM_FULL',     * 'TERM_NEAR_OPT', 'TERM_EASY' or 'TERM_PRED_ER'.     * */    public void setTermType(int ttype){        if (ttype != TERM_FULL && ttype != TERM_NEAR_OPT &&            ttype != TERM_EASY && ttype != TERM_PRED_ER ) {            throw new IllegalArgumentException("Unrecognized termination type "+                                               "code: "+ttype);        }        this.ttype = ttype;    }    /**     * Instantiates a new MQ-coder, with the specified number of contexts and     * initial states. The compressed bytestream is written to the 'oStream'     * object.     *     * @param oStream where to output the compressed data     *     * @param nrOfContexts The number of contexts used     *     * @param init The initial state for each context. A reference is kept to     * this array to reinitialize the contexts whenever 'reset()' or     * 'resetCtxts()' is called.