stdentropycoder.java

jpeg2000算法实现

/* 
 * CVS identifier:
 * 
 * $Id: StdEntropyCoder.java,v 1.34 2001/02/14 17:35:20 grosbois Exp $
 * 
 * Class:                   StdEntropyCoder
 * 
 * Description:             Entropy coding engine of stripes in code-blocks
 * 
 * 
 * 
 * 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.quantization.quantizer.*;
import jj2000.j2k.wavelet.analysis.*;
import jj2000.j2k.codestream.*;
import jj2000.j2k.wavelet.*;
import jj2000.j2k.encoder.*;
import jj2000.j2k.entropy.*;
import jj2000.j2k.image.*;
import jj2000.j2k.util.*;
import jj2000.j2k.io.*;
import jj2000.j2k.*;

import java.util.*;

/**
 * This class implements the JPEG 2000 entropy coder, which codes stripes in
 * code-blocks. This entropy coding engine can function in a single-threaded
 * mode where one code-block is encoded at a time, or in a multi-threaded mode
 * where multiple code-blocks are entropy coded in parallel. The interface
 * presented by this class is the same in both modes.
 *
 * <p>The number of threads used by this entropy coder is specified by the
 * "jj2000.j2k.entropy.encoder.StdEntropyCoder.nthreads" Java system
 * property. If set to "0" the single threaded implementation is used. If set
 * to 'n' ('n' larger than 0) then 'n' extra threads are started by this class
 * which are used to encode the code-blocks in parallel (i.e. ideally 'n'
 * code-blocks will be encoded in parallel at a time). On multiprocessor
 * machines under a "native threads" Java Virtual Machine implementation each
 * one of these threads can run on a separate processor speeding up the
 * encoding time. By default the single-threaded implementation is used. The
 * multi-threaded implementation currently assumes that the vast majority of
 * consecutive calls to 'getNextCodeBlock()' will be done on the same
 * component. If this is not the case, the speed-up that can be expected on
 * multiprocessor machines might be significantly decreased.
 *
 * <p>The code-blocks are rectangular, with dimensions which must be powers of
 * 2. Each dimension has to be no smaller than 4 and no larger than 256. The
 * product of the two dimensions (i.e. area of the code-block) may not exceed
 * 4096.
 *
 * <p>Context 0 of the MQ-coder is used as the uniform one (uniform,
 * non-adaptive probability distribution). Context 1 is used for RLC
 * coding. Contexts 2-10 are used for zero-coding (ZC), contexts 11-15 are
 * used for sign-coding (SC) and contexts 16-18 are used for
 * magnitude-refinement (MR).
 *
 * <p>This implementation buffers the symbols and calls the MQ coder only once 
 * per stripe and per coding pass, to reduce the method call overhead.
 *
 * <p>This implementation also provides some timing features. They can be
 * enabled by setting the 'DO_TIMING' constant of this class to true and
 * recompiling. The timing uses the 'System.currentTimeMillis()' Java API
 * call, which returns wall clock time, not the actual CPU time used. The
 * timing results will be printed on the message output. Since the times
 * reported are wall clock times and not CPU usage times they can not be added
 * to find the total used time (i.e. some time might be counted in several
 * places). When timing is disabled ('DO_TIMING' is false) there is no penalty
 * if the compiler performs some basic optimizations. Even if not the penalty
 * should be negligeable.
 *
 * <p>The source module must implement the CBlkQuantDataSrcEnc interface and
 * code-block's data is received in a CBlkWTData instance. This modules sends
 * code-block's information in a CBlkRateDistStats instance.
 *
 * @see CBlkQuantDataSrcEnc
 * @see CBlkWTData
 * @see CBlkRateDistStats
 * */
public class StdEntropyCoder extends EntropyCoder 
    implements StdEntropyCoderOptions {

    /** Whether to collect timing information or not: false. Used as a compile 
     * time directive. */
    private final static boolean DO_TIMING = false;

    /** The cumulative wall time for the entropy coding engine, for each
     * component. In the single-threaded implementation it is the total time,
     * in the multi-threaded implementation it is the time spent managing the
     * compressor threads only. */
    private long time[];

    /** The Java system property name for the number of threads to use:
     jj2000.j2k.entropy.encoder.StdEntropyCoder.nthreads */
    public static final String THREADS_PROP_NAME =
        "jj2000.j2k.entropy.encoder.StdEntropyCoder.nthreads";

    /** The default value for the property in THREADS_PROP_NAME: 0 */
    public static final String DEF_THREADS_NUM = "0";

    /** The increase in priority for the compressor threads, currently 3. The
     * compressor threads will have a priority of THREADS_PRIORITY_INC more
     * than the priority of the thread calling this class constructor. Used
     * only in the multi-threaded implementation. */
    public static final int THREADS_PRIORITY_INC = 0;

    /** The pool of threads, for the threaded implementation. It is null, if
     * non threaded implementation is used */
    private ThreadPool tPool;

    /** The queue of idle compressors. Used in multithreaded
        implementation only */
    private Stack idleComps;

    /** The queue of completed compressors, for each component. Used
        in multithreaded implementation only. */
    private Stack completedComps[];

    /** The number of busy compressors, for each component. Used in
        multithreaded implementation only. */
    private int nBusyComps[];

    /** A flag indicating for each component if all the code-blocks of the *
        current tile have been returned. Used in multithreaded implementation
        only. */
    private boolean finishedTileComponent[];

    /** The MQ coder used, for each thread */
    private MQCoder mqT[];

    /** The raw bit output used, for each thread */
    private BitToByteOutput boutT[];

    /** The output stream used, for each thread */
    private ByteOutputBuffer outT[];

    /** The encoder specifications */
    private EncoderSpecs encSpec;

    /** The options that are turned on, as flag bits. One element for
     * each tile-component. The options are 'OPT_REG_TERM',
     * 'OPT_RESET_MQ', 'OPT_VERT_STR_CAUSAL', 'OPT_BYPASS' and
     * 'OPT_SEG_MARKERS' as defined in the StdEntropyCoderOptions
     * interface
     *
     * @see StdEntropyCoderOptions
     * */
    private int[][] opts = null;

    /** The length calculation type for each tile-component */
    private int[][] lenCalc = null;

    /** The termination type for each tile-component */
    private int[][] tType = null;

    /** Number of bits used for the Zero Coding lookup table */
    private static final int ZC_LUT_BITS = 8;

    /** Zero Coding context lookup tables for the LH global orientation */
    private static final int ZC_LUT_LH[] = new int[1<<ZC_LUT_BITS];

    /** Zero Coding context lookup tables for the HL global orientation */
    private static final int ZC_LUT_HL[] = new int[1<<ZC_LUT_BITS];

    /** Zero Coding context lookup tables for the HH global orientation */
    private static final int ZC_LUT_HH[] = new int[1<<ZC_LUT_BITS];

    /** Number of bits used for the Sign Coding lookup table */
    private static final int SC_LUT_BITS = 9;

    /** Sign Coding context lookup table. The index into the table is a 9 bit
     * index, which correspond the the value in the 'state' array shifted by
     * 'SC_SHIFT'. Bits 8-5 are the signs of the horizontal-left,
     * horizontal-right, vertical-up and vertical-down neighbors,
     * respectively. Bit 4 is not used (0 or 1 makes no difference). Bits 3-0
     * are the significance of the horizontal-left, horizontal-right,
     * vertical-up and vertical-down neighbors, respectively. The least 4 bits
     * of the value in the lookup table define the context number and the sign
     * bit defines the "sign predictor". */
    private static final int SC_LUT[] = new int[1<<SC_LUT_BITS];

    /** The mask to obtain the context index from the 'SC_LUT' */
    private static final int SC_LUT_MASK = (1<<4)-1;

    /** The shift to obtain the sign predictor from the 'SC_LUT'. It must be
     * an unsigned shift. */
    private static final int SC_SPRED_SHIFT = 31;

    /** The sign bit for int data */
    private static final int INT_SIGN_BIT = 1<<31;

    /** The number of bits used for the Magnitude Refinement lookup table */
    private static final int MR_LUT_BITS = 9;

    /** Magnitude Refinement context lookup table */
    private static final int MR_LUT[] = new int[1<<MR_LUT_BITS];

    /** The number of contexts used */
    private static final int NUM_CTXTS = 19;

    /** The RLC context */
    private static final int RLC_CTXT = 1;

    /** The UNIFORM context (with a uniform probability distribution which
     * does not adapt) */
    private static final int UNIF_CTXT = 0;

    /** The initial states for the MQ coder */
    private static final int MQ_INIT[] = {46, 3, 4, 0, 0, 0, 0, 0, 0, 0, 0,
                                          0, 0, 0, 0, 0, 0, 0, 0};

    /** The 4 symbol segmentation marker (1010) */
    private static final int SEG_MARKERS[] = {1,0,1,0};

    /** The 4 contexts for the segmentation marker (always the UNIFORM context,
     * UNIF_CTXT) */
    private static final int SEG_MARK_CTXTS[] = {UNIF_CTXT, UNIF_CTXT,
                                                 UNIF_CTXT, UNIF_CTXT};

    /**
     * The state array for each thread. Each element of the state array stores
     * the state of two coefficients. The lower 16 bits store the state of a
     * coefficient in row 'i' and column 'j', while the upper 16 bits store
     * the state of a coefficient in row 'i+1' and column 'j'. The 'i' row is
     * either the first or the third row of a stripe. This packing of the
     * states into 32 bit words allows a faster scan of all coefficients on
     * each coding pass and diminished the amount of data transferred. The
     * size of the state array is increased by 1 on each side (top, bottom,
     * left, right) to handle boundary conditions without any special logic.
     *
     * <P>The state of a coefficient is stored in the following way in the
     * lower 16 bits, where bit 0 is the least significant bit. Bit 15 is the
     * significance of a coefficient (0 if non-significant, 1 otherwise). Bit
     * 14 is the visited state (i.e. if a coefficient has been coded in the
     * significance propagation pass of the current bit-plane). Bit 13 is the
     * "non zero-context" state (i.e. if one of the eight immediate neighbors
     * is significant it is 1, otherwise is 0). Bits 12 to 9 store the sign of
     * the already significant left, right, up and down neighbors (1 for
     * negative, 0 for positive or not yet significant). Bit 8 indicates if
     * the magnitude refinement has already been applied to the
     * coefficient. Bits 7 to 4 store the significance of the left, right, up
     * and down neighbors (1 for significant, 0 for non significant). Bits 3
     * to 0 store the significance of the diagonal coefficients (up-left,
     * up-right, down-left and down-right; 1 for significant, 0 for non
     * significant).
     *
     * <P>The upper 16 bits the state is stored as in the lower 16 bits,
     * but with the bits shifted up by 16.
     *
     * <P>The lower 16 bits are referred to as "row 1" ("R1") while the upper
     * 16 bits are referred to as "row 2" ("R2").
     * */
    private int stateT[][];

    /* The separation between the upper and lower bits in the state array: 16
     * */ 
    private static final int STATE_SEP = 16;

    /** The flag bit for the significance in the state array, for row 1. */
    private static final int STATE_SIG_R1 = 1<<15;

    /** The flag bit for the "visited" bit in the state array, for row 1. */ 
    private static final int STATE_VISITED_R1 = 1<<14;

    /** The flag bit for the "not zero context" bit in the state array, for
     * row 1. This bit is always the OR of bits STATE_H_L_R1, STATE_H_R_R1,
     * STATE_V_U_R1, STATE_V_D_R1, STATE_D_UL_R1, STATE_D_UR_R1, STATE_D_DL_R1
     * and STATE_D_DR_R1. */
    private static final int STATE_NZ_CTXT_R1 = 1<<13;

    /** The flag bit for the horizontal-left sign in the state array, for row
     * 1. This bit can only be set if the STATE_H_L_R1 is also set. */
    private static final int STATE_H_L_SIGN_R1 = 1<<12;

    /** The flag bit for the horizontal-right sign in the state array, for
     * row 1. This bit can only be set if the STATE_H_R_R1 is also set. */
    private static final int STATE_H_R_SIGN_R1 = 1<<11;

    /** The flag bit for the vertical-up sign in the state array, for row
     * 1. This bit can only be set if the STATE_V_U_R1 is also set. */