0001: /*
0002: * $RCSfile: MQCoder.java,v $
0003: * $Revision: 1.1 $
0004: * $Date: 2005/02/11 05:02:09 $
0005: * $State: Exp $
0006: *
0007: * Class: MQCoder
0008: *
0009: * Description: Class that encodes a number of bits using the
0010: * MQ arithmetic coder
0011: *
0012: *
0013: * Diego SANTA CRUZ, Jul-26-1999 (improved speed)
0014: *
0015: * COPYRIGHT:
0016: *
0017: * This software module was originally developed by Raphaël Grosbois and
0018: * Diego Santa Cruz (Swiss Federal Institute of Technology-EPFL); Joel
0019: * Askelöf (Ericsson Radio Systems AB); and Bertrand Berthelot, David
0020: * Bouchard, Félix Henry, Gerard Mozelle and Patrice Onno (Canon Research
0021: * Centre France S.A) in the course of development of the JPEG2000
0022: * standard as specified by ISO/IEC 15444 (JPEG 2000 Standard). This
0023: * software module is an implementation of a part of the JPEG 2000
0024: * Standard. Swiss Federal Institute of Technology-EPFL, Ericsson Radio
0025: * Systems AB and Canon Research Centre France S.A (collectively JJ2000
0026: * Partners) agree not to assert against ISO/IEC and users of the JPEG
0027: * 2000 Standard (Users) any of their rights under the copyright, not
0028: * including other intellectual property rights, for this software module
0029: * with respect to the usage by ISO/IEC and Users of this software module
0030: * or modifications thereof for use in hardware or software products
0031: * claiming conformance to the JPEG 2000 Standard. Those intending to use
0032: * this software module in hardware or software products are advised that
0033: * their use may infringe existing patents. The original developers of
0034: * this software module, JJ2000 Partners and ISO/IEC assume no liability
0035: * for use of this software module or modifications thereof. No license
0036: * or right to this software module is granted for non JPEG 2000 Standard
0037: * conforming products. JJ2000 Partners have full right to use this
0038: * software module for his/her own purpose, assign or donate this
0039: * software module to any third party and to inhibit third parties from
0040: * using this software module for non JPEG 2000 Standard conforming
0041: * products. This copyright notice must be included in all copies or
0042: * derivative works of this software module.
0043: *
0044: * Copyright (c) 1999/2000 JJ2000 Partners.
0045: * */
0046: package jj2000.j2k.entropy.encoder;
0047:
0048: import jj2000.j2k.entropy.encoder.*;
0049: import jj2000.j2k.entropy.*;
0050: import jj2000.j2k.util.*;
0051: import jj2000.j2k.*;
0052:
0053: import java.io.*;
0054:
0055: /**
0056: * This class implements the MQ arithmetic coder. When initialized a specific
0057: * state can be specified for each context, which may be adapted to the
0058: * probability distribution that is expected for that context.
0059: *
0060: * <P>The type of length calculation and termination can be chosen at
0061: * construction time.
0062: *
0063: * ---- Tricks that have been tried to improve speed ----
0064: *
0065: * 1) Merging Qe and mPS and doubling the lookup tables
0066: *
0067: * Merge the mPS into Qe, as the sign bit (if Qe>=0 the sense of MPS is 0, if
0068: * Qe<0 the sense is 1), and double the lookup tables. The first half of the
0069: * lookup tables correspond to Qe>=0 (i.e. the sense of MPS is 0) and the
0070: * second half to Qe<0 (i.e. the sense of MPS is 1). The nLPS lookup table is
0071: * modified to incorporate the changes in the sense of MPS, by making it jump
0072: * from the first to the second half and vice-versa, when a change is
0073: * specified by the swicthLM lookup table. See JPEG book, section 13.2, page
0074: * 225.
0075: *
0076: * There is NO speed improvement in doing this, actually there is a slight
0077: * decrease, probably due to the fact that often Q has to be negated. Also the
0078: * fact that a brach of the type "if (bit==mPS[li])" is replaced by two
0079: * simpler braches of the type "if (bit==0)" and "if (q<0)" may contribute to
0080: * that.
0081: *
0082: * 2) Removing cT
0083: *
0084: * It is possible to remove the cT counter by setting a flag bit in the high
0085: * bits of the C register. This bit will be automatically shifted left
0086: * whenever a renormalization shift occurs, which is equivalent to decreasing
0087: * cT. When the flag bit reaches the sign bit (leftmost bit), which is
0088: * equivalenet to cT==0, the byteOut() procedure is called. This test can be
0089: * done efficiently with "c<0" since C is a signed quantity. Care must be
0090: * taken in byteOut() to reset the bit in order to not interfere with other
0091: * bits in the C register. See JPEG book, page 228.
0092: *
0093: * There is NO speed improvement in doing this. I don't really know why since
0094: * the number of operations whenever a renormalization occurs is
0095: * decreased. Maybe it is due to the number of extra operations in the
0096: * byteOut(), terminate() and getNumCodedBytes() procedures.
0097: *
0098: *
0099: * 3) Change the convention of MPS and LPS.
0100: *
0101: * Making the LPS interval be above the MPS interval (MQ coder convention is
0102: * the opposite) can reduce the number of operations along the MPS path. In
0103: * order to generate the same bit stream as with the MQ convention the output
0104: * bytes need to be modified accordingly. The basic rule for this is that C =
0105: * (C'^0xFF...FF)-A, where C is the codestream for the MQ convention and C' is
0106: * the codestream generated by this other convention. Note that this affects
0107: * bit-stuffing as well.
0108: *
0109: * This has not been tested yet.
0110: *
0111: * 4) Removing normalization while loop on MPS path
0112: *
0113: * Since in the MPS path Q is guaranteed to be always greater than 0x4000
0114: * (decimal 0.375) it is never necessary to do more than 1 renormalization
0115: * shift. Therefore the test of the while loop, and the loop itself, can be
0116: * removed.
0117: *
0118: * 5) Simplifying test on A register
0119: *
0120: * Since A is always less than or equal to 0xFFFF, the test "(a & 0x8000)==0"
0121: * can be replaced by the simplete test "a < 0x8000". This test is simpler in
0122: * Java since it involves only 1 operation (although the original test can be
0123: * converted to only one operation by smart Just-In-Time compilers)
0124: *
0125: * This change has been integrated in the decoding procedures.
0126: *
0127: * 6) Speedup mode
0128: *
0129: * Implemented a method that uses the speedup mode of the MQ-coder if
0130: * possible. This should greately improve performance when coding long runs of
0131: * MPS symbols that have high probability. However, to take advantage of this,
0132: * the entropy coder implementation has to explicetely use it. The generated
0133: * bit stream is the same as if no speedup mode would have been used.
0134: *
0135: * Implemented but performance not tested yet.
0136: *
0137: * 7) Multiple-symbol coding
0138: *
0139: * Since the time spent in a method call is non-negligable, coding several
0140: * symbols with one method call reduces the overhead per coded symbol. The
0141: * decodeSymbols() method implements this. However, to take advantage of it,
0142: * the implementation of the entropy coder has to explicitely use it.
0143: *
0144: * Implemented but performance not tested yet.
0145: * */
0146: public class MQCoder {
0147:
0148: /** Identifier for the lazy length calculation. The lazy length
0149: * calculation is not optimal but is extremely simple. */
0150: public static final int LENGTH_LAZY = 0;
0151:
0152: /** Identifier for a very simple length calculation. This provides better
0153: * results than the 'LENGTH_LAZY' computation. This is the old length
0154: * calculation that was implemented in this class. */
0155: public static final int LENGTH_LAZY_GOOD = 1;
0156:
0157: /** Identifier for the near optimal length calculation. This calculation
0158: * is more complex than the lazy one but provides an almost optimal length
0159: * calculation. */
0160: public static final int LENGTH_NEAR_OPT = 2;
0161:
0162: /** The identifier fort the termination that uses a full flush. This is
0163: * the less efficient termination. */
0164: public static final int TERM_FULL = 0;
0165:
0166: /** The identifier for the termination that uses the near optimal length
0167: * calculation to terminate the arithmetic codewrod */
0168: public static final int TERM_NEAR_OPT = 1;
0169:
0170: /** The identifier for the easy termination that is simpler than the
0171: * 'TERM_NEAR_OPT' one but slightly less efficient. */
0172: public static final int TERM_EASY = 2;
0173:
0174: /** The identifier for the predictable termination policy for error
0175: * resilience. This is the same as the 'TERM_EASY' one but an special
0176: * sequence of bits is embodied in the spare bits for error resilience
0177: * purposes. */
0178: public static final int TERM_PRED_ER = 3;
0179:
0180: /** The data structures containing the probabilities for the LPS */
0181: final static int qe[] = { 0x5601, 0x3401, 0x1801, 0x0ac1, 0x0521,
0182: 0x0221, 0x5601, 0x5401, 0x4801, 0x3801, 0x3001, 0x2401,
0183: 0x1c01, 0x1601, 0x5601, 0x5401, 0x5101, 0x4801, 0x3801,
0184: 0x3401, 0x3001, 0x2801, 0x2401, 0x2201, 0x1c01, 0x1801,
0185: 0x1601, 0x1401, 0x1201, 0x1101, 0x0ac1, 0x09c1, 0x08a1,
0186: 0x0521, 0x0441, 0x02a1, 0x0221, 0x0141, 0x0111, 0x0085,
0187: 0x0049, 0x0025, 0x0015, 0x0009, 0x0005, 0x0001, 0x5601 };
0188:
0189: /** The indexes of the next MPS */
0190: final static int nMPS[] = { 1, 2, 3, 4, 5, 38, 7, 8, 9, 10, 11, 12,
0191: 13, 29, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27,
0192: 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42,
0193: 43, 44, 45, 45, 46 };
0194:
0195: /** The indexes of the next LPS */
0196: final static int nLPS[] = { 1, 6, 9, 12, 29, 33, 6, 14, 14, 14, 17,
0197: 18, 20, 21, 14, 14, 15, 16, 17, 18, 19, 19, 20, 21, 22, 23,
0198: 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38,
0199: 39, 40, 41, 42, 43, 46 };
0200:
0201: /** Whether LPS and MPS should be switched */
0202: final static// at indices 0, 6, and 14 we switch
0203: int switchLM[] = { 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0,
0204: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0205: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
0206: // Having ints proved to be more efficient than booleans
0207:
0208: /** The ByteOutputBuffer used to write the compressed bit stream. */
0209: ByteOutputBuffer out;
0210:
0211: /** The current most probable signal for each context */
0212: int[] mPS;
0213:
0214: /** The current index of each context */
0215: int[] I;
0216:
0217: /** The current bit code */
0218: int c;
0219:
0220: /** The bit code counter */
0221: int cT;
0222:
0223: /** The current interval */
0224: int a;
0225:
0226: /** The last encoded byte of data */
0227: int b;
0228:
0229: /** If a 0xFF byte has been delayed and not yet been written to the output
0230: * (in the MQ we can never have more than 1 0xFF byte in a row). */
0231: boolean delFF;
0232:
0233: /** The number of written bytes so far, excluding any delayed 0xFF
0234: * bytes. Upon initialization it is -1 to indicated that the byte buffer
0235: * 'b' is empty as well. */
0236: int nrOfWrittenBytes = -1;
0237:
0238: /** The initial state of each context */
0239: int initStates[];
0240:
0241: /** The termination type to use. One of 'TERM_FULL', 'TERM_NEAR_OPT',
0242: * 'TERM_EASY' or 'TERM_PRED_ER'. */
0243: int ttype;
0244:
0245: /** The length calculation type to use. One of 'LENGTH_LAZY',
0246: * 'LENGTH_LAZY_GOOD', 'LENGTH_NEAR_OPT'. */
0247: int ltype;
0248:
0249: /** Saved values of the C register. Used for the LENGTH_NEAR_OPT length
0250: * calculation. */
0251: int savedC[];
0252:
0253: /** Saved values of CT counter. Used for the LENGTH_NEAR_OPT length
0254: * calculation. */
0255: int savedCT[];
0256:
0257: /** Saved values of the A register. Used for the LENGTH_NEAR_OPT length
0258: * calculation. */
0259: int savedA[];
0260:
0261: /** Saved values of the B byte buffer. Used for the LENGTH_NEAR_OPT length
0262: * calculation. */
0263: int savedB[];
0264:
0265: /** Saved values of the delFF (i.e. delayed 0xFF) state. Used for the
0266: * LENGTH_NEAR_OPT length calculation. */
0267: boolean savedDelFF[];
0268:
0269: /** Number of saved states. Used for the LENGTH_NEAR_OPT length
0270: * calculation. */
0271: int nSaved;
0272:
0273: /** The initial length of the arrays to save sates */
0274: final static int SAVED_LEN = 32 * StdEntropyCoderOptions.NUM_PASSES;
0275:
0276: /** The increase in length for the arrays to save states */
0277: final static int SAVED_INC = 4 * StdEntropyCoderOptions.NUM_PASSES;
0278:
0279: /**
0280: * Set the length calculation type to the specified type
0281: *
0282: * @param ltype The type of length calculation to use. One of
0283: * 'LENGTH_LAZY', 'LENGTH_LAZY_GOOD' or 'LENGTH_NEAR_OPT'.
0284: * */
0285: public void setLenCalcType(int ltype) {
0286: // Verify the ttype and ltype
0287: if (ltype != LENGTH_LAZY && ltype != LENGTH_LAZY_GOOD
0288: && ltype != LENGTH_NEAR_OPT) {
0289: throw new IllegalArgumentException("Unrecognized length "
0290: + "calculation type code: " + ltype);
0291: }
0292:
0293: if (ltype == LENGTH_NEAR_OPT) {
0294: if (savedC == null)
0295: savedC = new int[SAVED_LEN];
0296: if (savedCT == null)
0297: savedCT = new int[SAVED_LEN];
0298: if (savedA == null)
0299: savedA = new int[SAVED_LEN];
0300: if (savedB == null)
0301: savedB = new int[SAVED_LEN];
0302: if (savedDelFF == null)
0303: savedDelFF = new boolean[SAVED_LEN];
0304: }
0305:
0306: this .ltype = ltype;
0307: }
0308:
0309: /**
0310: * Set termination type to the specified type
0311: *
0312: * @param ttype The type of termination to use. One of 'TERM_FULL',
0313: * 'TERM_NEAR_OPT', 'TERM_EASY' or 'TERM_PRED_ER'.
0314: * */
0315: public void setTermType(int ttype) {
0316: if (ttype != TERM_FULL && ttype != TERM_NEAR_OPT
0317: && ttype != TERM_EASY && ttype != TERM_PRED_ER) {
0318: throw new IllegalArgumentException(
0319: "Unrecognized termination type " + "code: " + ttype);
0320: }
0321:
0322: this .ttype = ttype;
0323: }
0324:
0325: /**
0326: * Instantiates a new MQ-coder, with the specified number of contexts and
0327: * initial states. The compressed bytestream is written to the 'oStream'
0328: * object.
0329: *
0330: * @param oStream where to output the compressed data
0331: *
0332: * @param nrOfContexts The number of contexts used
0333: *
0334: * @param init The initial state for each context. A reference is kept to
0335: * this array to reinitialize the contexts whenever 'reset()' or
0336: * 'resetCtxts()' is called.
0337: * */
0338: public MQCoder(ByteOutputBuffer oStream, int nrOfContexts,
0339: int init[]) {
0340: out = oStream;
0341:
0342: // --- INITENC
0343:
0344: // Default initialization of the statistics bins is MPS=0 and
0345: // I=0
0346: I = new int[nrOfContexts];
0347: mPS = new int[nrOfContexts];
0348: initStates = init;
0349:
0350: a = 0x8000;
0351: c = 0;
0352: if (b == 0xFF)
0353: cT = 13;
0354: else
0355: cT = 12;
0356:
0357: resetCtxts();
0358:
0359: // End of INITENC ---
0360:
0361: b = 0;
0362: }
0363:
0364: /**
0365: * This method performs the coding of the symbol 'bit', using context
0366: * 'ctxt', 'n' times, using the MQ-coder speedup mode if possible.
0367: *
0368: * <P>If the symbol 'bit' is the current more probable symbol (MPS) and
0369: * qe[ctxt]<=0x4000, and (A-0x8000)>=qe[ctxt], speedup mode will be
0370: * used. Otherwise the normal mode will be used. The speedup mode can
0371: * significantly improve the speed of arithmetic coding when several MPS
0372: * symbols, with a high probability distribution, must be coded with the
0373: * same context. The generated bit stream is the same as if the normal mode
0374: * was used.
0375: *
0376: * <P>This method is also faster than the 'codeSymbols()' and
0377: * 'codeSymbol()' ones, for coding the same symbols with the same context
0378: * several times, when speedup mode can not be used, although not
0379: * significantly.
0380: *
0381: * @param bit The symbol do code, 0 or 1.
0382: *
0383: * @param ctxt The context to us in coding the symbol
0384: *
0385: * @param n The number of times that the symbol must be coded.
0386: * */
0387: public final void fastCodeSymbols(int bit, int ctxt, int n) {
0388: int q; // cache for context's Qe
0389: int la; // cache for A register
0390: int nc; // counter for renormalization shifts
0391: int ns; // the maximum length of a speedup mode run
0392: int li; // cache for I[ctxt]
0393:
0394: li = I[ctxt]; // cache current index
0395: q = qe[li]; // retrieve current LPS prob.
0396:
0397: if ((q <= 0x4000) && (bit == mPS[ctxt])
0398: && ((ns = (a - 0x8000) / q + 1) > 1)) { // Do speed up mode
0399: // coding MPS, no conditional exchange can occur and
0400: // speedup mode is possible for more than 1 symbol
0401: do { // do as many speedup runs as necessary
0402: if (n <= ns) { // All symbols in this run
0403: // code 'n' symbols
0404: la = n * q; // accumulated Q
0405: a -= la;
0406: c += la;
0407: if (a >= 0x8000) { // no renormalization
0408: I[ctxt] = li; // save the current state
0409: return; // done
0410: }
0411: I[ctxt] = nMPS[li]; // goto next state and save it
0412: // -- Renormalization (MPS: no need for while loop)
0413: a <<= 1; // a is doubled
0414: c <<= 1; // c is doubled
0415: cT--;
0416: if (cT == 0) {
0417: byteOut();
0418: }
0419: // -- End of renormalization
0420: return; // done
0421: } else { // Not all symbols in this run
0422: // code 'ns' symbols
0423: la = ns * q; // accumulated Q
0424: c += la;
0425: a -= la;
0426: // cache li and q for next iteration
0427: li = nMPS[li];
0428: q = qe[li]; // New q is always less than current one
0429: // new I[ctxt] is stored in last run
0430: // Renormalization always occurs since we exceed 'ns'
0431: // -- Renormalization (MPS: no need for while loop)
0432: a <<= 1; // a is doubled
0433: c <<= 1; // c is doubled
0434: cT--;
0435: if (cT == 0) {
0436: byteOut();
0437: }
0438: // -- End of renormalization
0439: n -= ns; // symbols left to code
0440: ns = (a - 0x8000) / q + 1; // max length of next speedup run
0441: continue; // goto next iteration
0442: }
0443: } while (n > 0);
0444: } // end speed up mode
0445: else { // No speedup mode
0446: // Either speedup mode is not possible or not worth doing it
0447: // because of probable conditional exchange
0448: // Code everything as in normal mode
0449: la = a; // cache A register in local variable
0450: do {
0451: if (bit == mPS[ctxt]) { // -- code MPS
0452: la -= q; // Interval division associated with MPS coding
0453: if (la >= 0x8000) { // Interval big enough
0454: c += q;
0455: } else { // Interval too short
0456: if (la < q) // Probabilities are inverted
0457: la = q;
0458: else
0459: c += q;
0460: // cache new li and q for next iteration
0461: li = nMPS[li];
0462: q = qe[li];
0463: // new I[ctxt] is stored after end of loop
0464: // -- Renormalization (MPS: no need for while loop)
0465: la <<= 1; // a is doubled
0466: c <<= 1; // c is doubled
0467: cT--;
0468: if (cT == 0) {
0469: byteOut();
0470: }
0471: // -- End of renormalization
0472: }
0473: } else { // -- code LPS
0474: la -= q; // Interval division according to LPS coding
0475: if (la < q)
0476: c += q;
0477: else
0478: la = q;
0479: if (switchLM[li] != 0) {
0480: mPS[ctxt] = 1 - mPS[ctxt];
0481: }
0482: // cache new li and q for next iteration
0483: li = nLPS[li];
0484: q = qe[li];
0485: // new I[ctxt] is stored after end of loop
0486: // -- Renormalization
0487: // sligthly better than normal loop
0488: nc = 0;
0489: do {
0490: la <<= 1;
0491: nc++; // count number of necessary shifts
0492: } while (la < 0x8000);
0493: if (cT > nc) {
0494: c <<= nc;
0495: cT -= nc;
0496: } else {
0497: do {
0498: c <<= cT;
0499: nc -= cT;
0500: // cT = 0; // not necessary
0501: byteOut();
0502: } while (cT <= nc);
0503: c <<= nc;
0504: cT -= nc;
0505: }
0506: // -- End of renormalization
0507: }
0508: n--;
0509: } while (n > 0);
0510: I[ctxt] = li; // store new I[ctxt]
0511: a = la; // save cached A register
0512: }
0513: }
0514:
0515: /**
0516: * This function performs the arithmetic encoding of several symbols
0517: * together. The function receives an array of symbols that are to be
0518: * encoded and an array containing the contexts with which to encode them.
0519: *
0520: * <P>The advantage of using this function is that the cost of the method
0521: * call is amortized by the number of coded symbols per method call.
0522: *
0523: * <P>Each context has a current MPS and an index describing what the
0524: * current probability is for the LPS. Each bit is encoded and if the
0525: * probability of the LPS exceeds .5, the MPS and LPS are switched.
0526: *
0527: * @param bits An array containing the symbols to be encoded. Valid
0528: * symbols are 0 and 1.
0529: *
0530: * @param cX The context for each of the symbols to be encoded
0531: *
0532: * @param n The number of symbols to encode.
0533: * */
0534: public final void codeSymbols(int[] bits, int[] cX, int n) {
0535: int q;
0536: int li; // local cache of I[context]
0537: int la;
0538: int nc;
0539: int ctxt; // context of current symbol
0540: int i; // counter
0541:
0542: // NOTE: here we could use symbol aggregation to speed things up.
0543: // It remains to be studied.
0544:
0545: la = a; // cache A register in local variable
0546: for (i = 0; i < n; i++) {
0547: // NOTE: (a < 0x8000) is equivalent to ((a & 0x8000)==0)
0548: // since 'a' is always less than or equal to 0xFFFF
0549:
0550: // NOTE: conditional exchange guarantees that A for MPS is
0551: // always greater than 0x4000 (i.e. 0.375)
0552: // => one renormalization shift is enough for MPS
0553: // => no need to do a renormalization while loop for MPS
0554:
0555: ctxt = cX[i];
0556: li = I[ctxt];
0557: q = qe[li]; // Retrieve current LPS prob.
0558:
0559: if (bits[i] == mPS[ctxt]) { // -- Code MPS
0560:
0561: la -= q; // Interval division associated with MPS coding
0562:
0563: if (la >= 0x8000) { // Interval big enough
0564: c += q;
0565: } else { // Interval too short
0566: if (la < q) // Probabilities are inverted
0567: la = q;
0568: else
0569: c += q;
0570:
0571: I[ctxt] = nMPS[li];
0572:
0573: // -- Renormalization (MPS: no need for while loop)
0574: la <<= 1; // a is doubled
0575: c <<= 1; // c is doubled
0576: cT--;
0577: if (cT == 0) {
0578: byteOut();
0579: }
0580: // -- End of renormalization
0581: }
0582: }// End Code MPS --
0583: else { // -- Code LPS
0584: la -= q; // Interval division according to LPS coding
0585:
0586: if (la < q)
0587: c += q;
0588: else
0589: la = q;
0590: if (switchLM[li] != 0) {
0591: mPS[ctxt] = 1 - mPS[ctxt];
0592: }
0593: I[ctxt] = nLPS[li];
0594:
0595: // -- Renormalization
0596:
0597: // sligthly better than normal loop
0598: nc = 0;
0599: do {
0600: la <<= 1;
0601: nc++; // count number of necessary shifts
0602: } while (la < 0x8000);
0603: if (cT > nc) {
0604: c <<= nc;
0605: cT -= nc;
0606: } else {
0607: do {
0608: c <<= cT;
0609: nc -= cT;
0610: // cT = 0; // not necessary
0611: byteOut();
0612: } while (cT <= nc);
0613: c <<= nc;
0614: cT -= nc;
0615: }
0616:
0617: // -- End of renormalization
0618: }
0619: }
0620: a = la; // save cached A register
0621: }
0622:
0623: /**
0624: * This function performs the arithmetic encoding of one symbol. The
0625: * function receives a bit that is to be encoded and a context with which
0626: * to encode it.
0627: *
0628: * <P>Each context has a current MPS and an index describing what the
0629: * current probability is for the LPS. Each bit is encoded and if the
0630: * probability of the LPS exceeds .5, the MPS and LPS are switched.
0631: *
0632: * @param bit The symbol to be encoded, must be 0 or 1.
0633: *
0634: * @param context the context with which to encode the symbol.
0635: * */
0636: public final void codeSymbol(int bit, int context) {
0637: int q;
0638: int li; // local cache of I[context]
0639: int la;
0640: int n;
0641:
0642: // NOTE: (a < 0x8000) is equivalent to ((a & 0x8000)==0)
0643: // since 'a' is always less than or equal to 0xFFFF
0644:
0645: // NOTE: conditional exchange guarantees that A for MPS is
0646: // always greater than 0x4000 (i.e. 0.375)
0647: // => one renormalization shift is enough for MPS
0648: // => no need to do a renormalization while loop for MPS
0649:
0650: li = I[context];
0651: q = qe[li]; // Retrieve current LPS prob.
0652:
0653: if (bit == mPS[context]) {// -- Code MPS
0654:
0655: a -= q; // Interval division associated with MPS coding
0656:
0657: if (a >= 0x8000) { // Interval big enough
0658: c += q;
0659: } else { // Interval too short
0660: if (a < q) // Probabilities are inverted
0661: a = q;
0662: else
0663: c += q;
0664:
0665: I[context] = nMPS[li];
0666:
0667: // -- Renormalization (MPS: no need for while loop)
0668: a <<= 1; // a is doubled
0669: c <<= 1; // c is doubled
0670: cT--;
0671: if (cT == 0) {
0672: byteOut();
0673: }
0674: // -- End of renormalization
0675: }
0676: }// End Code MPS --
0677: else { // -- Code LPS
0678:
0679: la = a; // cache A register in local variable
0680: la -= q; // Interval division according to LPS coding
0681:
0682: if (la < q)
0683: c += q;
0684: else
0685: la = q;
0686: if (switchLM[li] != 0) {
0687: mPS[context] = 1 - mPS[context];
0688: }
0689: I[context] = nLPS[li];
0690:
0691: // -- Renormalization
0692:
0693: // sligthly better than normal loop
0694: n = 0;
0695: do {
0696: la <<= 1;
0697: n++; // count number of necessary shifts
0698: } while (la < 0x8000);
0699: if (cT > n) {
0700: c <<= n;
0701: cT -= n;
0702: } else {
0703: do {
0704: c <<= cT;
0705: n -= cT;
0706: // cT = 0; // not necessary
0707: byteOut();
0708: } while (cT <= n);
0709: c <<= n;
0710: cT -= n;
0711: }
0712:
0713: // -- End of renormalization
0714: a = la; // save cached A register
0715: }
0716: }
0717:
0718: /**
0719: * This function puts one byte of compressed bits in the out out stream.
0720: * the highest 8 bits of c are then put in b to be the next byte to
0721: * write. This method delays the output of any 0xFF bytes until a non 0xFF
0722: * byte has to be written to the output bit stream (the 'delFF' variable
0723: * signals if there is a delayed 0xff byte).
0724: * */
0725: private void byteOut() {
0726: if (nrOfWrittenBytes >= 0) {
0727: if (b == 0xFF) {
0728: // Delay 0xFF byte
0729: delFF = true;
0730: b = c >>> 20;
0731: c &= 0xFFFFF;
0732: cT = 7;
0733: } else if (c < 0x8000000) {
0734: // Write delayed 0xFF bytes
0735: if (delFF) {
0736: out.write(0xFF);
0737: delFF = false;
0738: nrOfWrittenBytes++;
0739: }
0740: out.write(b);
0741: nrOfWrittenBytes++;
0742: b = c >>> 19;
0743: c &= 0x7FFFF;
0744: cT = 8;
0745: } else {
0746: b++;
0747: if (b == 0xFF) {
0748: // Delay 0xFF byte
0749: delFF = true;
0750: c &= 0x7FFFFFF;
0751: b = c >>> 20;
0752: c &= 0xFFFFF;
0753: cT = 7;
0754: } else {
0755: // Write delayed 0xFF bytes
0756: if (delFF) {
0757: out.write(0xFF);
0758: delFF = false;
0759: nrOfWrittenBytes++;
0760: }
0761: out.write(b);
0762: nrOfWrittenBytes++;
0763: b = ((c >>> 19) & 0xFF);
0764: c &= 0x7FFFF;
0765: cT = 8;
0766: }
0767: }
0768: } else {
0769: // NOTE: carry bit can never be set if the byte buffer was empty
0770: b = (c >>> 19);
0771: c &= 0x7FFFF;
0772: cT = 8;
0773: nrOfWrittenBytes++;
0774: }
0775: }
0776:
0777: /**
0778: * This function flushes the remaining encoded bits and makes sure that
0779: * enough information is written to the bit stream to be able to finish
0780: * decoding, and then it reinitializes the internal state of the MQ coder
0781: * but without modifying the context states.
0782: *
0783: * <P>After calling this method the 'finishLengthCalculation()' method
0784: * should be called, after cmopensating the returned length for the length
0785: * of previous coded segments, so that the length calculation is finalized.
0786: *
0787: * <P>The type of termination used depends on the one specified at the
0788: * constructor.
0789: *
0790: * @return The length of the arithmetic codeword after termination, in
0791: * bytes.
0792: * */
0793: public int terminate() {
0794: switch (ttype) {
0795: case TERM_FULL:
0796: //sets the remaining bits of the last byte of the coded bits.
0797: int tempc = c + a;
0798: c = c | 0xFFFF;
0799: if (c >= tempc)
0800: c = c - 0x8000;
0801:
0802: int remainingBits = 27 - cT;
0803:
0804: // Flushes remainingBits
0805: do {
0806: c <<= cT;
0807: if (b != 0xFF)
0808: remainingBits -= 8;
0809: else
0810: remainingBits -= 7;
0811: byteOut();
0812: } while (remainingBits > 0);
0813:
0814: b |= (1 << (-remainingBits)) - 1;
0815: if (b == 0xFF) { // Delay 0xFF bytes
0816: delFF = true;
0817: } else {
0818: // Write delayed 0xFF bytes
0819: if (delFF) {
0820: out.write(0xFF);
0821: delFF = false;
0822: nrOfWrittenBytes++;
0823: }
0824: out.write(b);
0825: nrOfWrittenBytes++;
0826: }
0827: break;
0828: case TERM_PRED_ER:
0829: case TERM_EASY:
0830: // The predictable error resilient and easy termination are the
0831: // same, except for the fact that the easy one can modify the
0832: // spare bits in the last byte to maximize the likelihood of
0833: // having a 0xFF, while the error resilient one can not touch
0834: // these bits.
0835:
0836: // In the predictable error resilient case the spare bits will be
0837: // recalculated by the decoder and it will check if they are the
0838: // same as as in the codestream and then deduce an error
0839: // probability from there.
0840:
0841: int k; // number of bits to push out
0842:
0843: k = (11 - cT) + 1;
0844:
0845: c <<= cT;
0846: for (; k > 0; k -= cT, c <<= cT) {
0847: byteOut();
0848: }
0849:
0850: // Make any spare bits 1s if in easy termination
0851: if (k < 0 && ttype == TERM_EASY) {
0852: // At this stage there is never a carry bit in C, so we can
0853: // freely modify the (-k) least significant bits.
0854: b |= (1 << (-k)) - 1;
0855: }
0856:
0857: byteOut(); // Push contents of byte buffer
0858: break;
0859: case TERM_NEAR_OPT:
0860:
0861: // This algorithm terminates in the shortest possible way, besides
0862: // the fact any previous 0xFF 0x7F sequences are not
0863: // eliminated. The probabalility of having those sequences is
0864: // extremely low.
0865:
0866: // The calculation of the length is based on the fact that the
0867: // decoder will pad the codestream with an endless string of
0868: // (binary) 1s. If the codestream, padded with 1s, is within the
0869: // bounds of the current interval then correct decoding is
0870: // guaranteed. The lower inclusive bound of the current interval
0871: // is the value of C (i.e. if only lower intervals would be coded
0872: // in the future). The upper exclusive bound of the current
0873: // interval is C+A (i.e. if only upper intervals would be coded in
0874: // the future). We therefore calculate the minimum length that
0875: // would be needed so that padding with 1s gives a codestream
0876: // within the interval.
0877:
0878: // In general, such a calculation needs the value of the next byte
0879: // that appears in the codestream. Here, since we are terminating,
0880: // the next value can be anything we want that lies within the
0881: // interval, we use the lower bound since this minimizes the
0882: // length. To calculate the necessary length at any other place
0883: // than the termination it is necessary to know the next bytes
0884: // that will appear in the codestream, which involves storing the
0885: // codestream and the sate of the MQCoder at various points (a
0886: // worst case approach can be used, but it is much more
0887: // complicated and the calculated length would be only marginally
0888: // better than much simple calculations, if not the same).
0889:
0890: int cLow;
0891: int cUp;
0892: int bLow;
0893: int bUp;
0894:
0895: // Initialize the upper (exclusive) and lower bound (inclusive) of
0896: // the valid interval (the actual interval is the concatenation of
0897: // bUp and cUp, and bLow and cLow).
0898: cLow = c;
0899: cUp = c + a;
0900: bLow = bUp = b;
0901:
0902: // We start by normalizing the C register to the sate cT = 0
0903: // (i.e., just before byteOut() is called)
0904: cLow <<= cT;
0905: cUp <<= cT;
0906: // Progate eventual carry bits and reset them in Clow, Cup NOTE:
0907: // carry bit can never be set if the byte buffer was empty so no
0908: // problem with propagating a carry into an empty byte buffer.
0909: if ((cLow & (1 << 27)) != 0) { // Carry bit in cLow
0910: if (bLow == 0xFF) {
0911: // We can not propagate carry bit, do bit stuffing
0912: delFF = true; // delay 0xFF
0913: // Get next byte buffer
0914: bLow = cLow >>> 20;
0915: bUp = cUp >>> 20;
0916: cLow &= 0xFFFFF;
0917: cUp &= 0xFFFFF;
0918: // Normalize to cT = 0
0919: cLow <<= 7;
0920: cUp <<= 7;
0921: } else { // we can propagate carry bit
0922: bLow++; // propagate
0923: cLow &= ~(1 << 27); // reset carry in cLow
0924: }
0925: }
0926: if ((cUp & (1 << 27)) != 0) {
0927: bUp++; // propagate
0928: cUp &= ~(1 << 27); // reset carry
0929: }
0930:
0931: // From now on there can never be a carry bit on cLow, since we
0932: // always output bLow.
0933:
0934: // Loop testing for the condition and doing byte output if they
0935: // are not met.
0936: while (true) {
0937: // If decoder's codestream is within interval stop
0938: // If preceding byte is 0xFF only values [0,127] are valid
0939: if (delFF) { // If delayed 0xFF
0940: if (bLow <= 127 && bUp > 127)
0941: break;
0942: // We will write more bytes so output delayed 0xFF now
0943: out.write(0xFF);
0944: nrOfWrittenBytes++;
0945: delFF = false;
0946: } else { // No delayed 0xFF
0947: if (bLow <= 255 && bUp > 255)
0948: break;
0949: }
0950:
0951: // Output next byte
0952: // We could output anything within the interval, but using
0953: // bLow simplifies things a lot.
0954:
0955: // We should not have any carry bit here
0956:
0957: // Output bLow
0958: if (bLow < 255) {
0959: // Transfer byte bits from C to B
0960: // (if the byte buffer was empty output nothing)
0961: if (nrOfWrittenBytes >= 0)
0962: out.write(bLow);
0963: nrOfWrittenBytes++;
0964: bUp -= bLow;
0965: bUp <<= 8;
0966: // Here bLow would be 0
0967: bUp |= (cUp >>> 19) & 0xFF;
0968: bLow = (cLow >>> 19) & 0xFF;
0969: // Clear upper bits (just pushed out) from cUp Clow.
0970: cLow &= 0x7FFFF;
0971: cUp &= 0x7FFFF;
0972: // Goto next state where CT is 0
0973: cLow <<= 8;
0974: cUp <<= 8;
0975: // Here there can be no carry on Cup, Clow
0976: } else { // bLow = 0xFF
0977: // Transfer byte bits from C to B
0978: // Since the byte to output is 0xFF we can delay it
0979: delFF = true;
0980: bUp -= bLow;
0981: bUp <<= 7;
0982: // Here bLow would be 0
0983: bUp |= (cUp >> 20) & 0x7F;
0984: bLow = (cLow >> 20) & 0x7F;
0985: // Clear upper bits (just pushed out) from cUp Clow.
0986: cLow &= 0xFFFFF;
0987: cUp &= 0xFFFFF;
0988: // Goto next state where CT is 0
0989: cLow <<= 7;
0990: cUp <<= 7;
0991: // Here there can be no carry on Cup, Clow
0992: }
0993: }
0994: break;
0995: default:
0996: throw new Error("Illegal termination type code");
0997: }
0998:
0999: // Reinitialize the state (without modifying the contexts)
1000: int len;
1001:
1002: len = nrOfWrittenBytes;
1003: a = 0x8000;
1004: c = 0;
1005: b = 0;
1006: cT = 12;
1007: delFF = false;
1008: nrOfWrittenBytes = -1;
1009:
1010: // Return the terminated length
1011: return len;
1012: }
1013:
1014: /**
1015: * Returns the number of contexts in the arithmetic coder.
1016: *
1017: * @return The number of contexts
1018: * */
1019: public final int getNumCtxts() {
1020: return I.length;
1021: }
1022:
1023: /**
1024: * Resets a context to the original probability distribution, and sets its
1025: * more probable symbol to 0.
1026: *
1027: * @param c The number of the context (it starts at 0).
1028: * */
1029: public final void resetCtxt(int c) {
1030: I[c] = initStates[c];
1031: mPS[c] = 0;
1032: }
1033:
1034: /**
1035: * Resets all contexts to their original probability distribution and sets
1036: * all more probable symbols to 0.
1037: * */
1038: public final void resetCtxts() {
1039: System.arraycopy(initStates, 0, I, 0, I.length);
1040: ArrayUtil.intArraySet(mPS, 0);
1041: }
1042:
1043: /**
1044: * Returns the number of bytes that are necessary from the compressed
1045: * output stream to decode all the symbols that have been coded this
1046: * far. The number of returned bytes does not include anything coded
1047: * previous to the last time the 'terminate()' or 'reset()' methods where
1048: * called.
1049: *
1050: * <P>The values returned by this method are then to be used in finishing
1051: * the length calculation with the 'finishLengthCalculation()' method,
1052: * after compensation of the offset in the number of bytes due to previous
1053: * terminated segments.
1054: *
1055: * <P>This method should not be called if the current coding pass is to be
1056: * terminated. The 'terminate()' method should be called instead.
1057: *
1058: * <P>The calculation is done based on the type of length calculation
1059: * specified at the constructor.
1060: *
1061: * @return The number of bytes in the compressed output stream necessary
1062: * to decode all the information coded this far.
1063: * */
1064: public final int getNumCodedBytes() {
1065: // NOTE: testing these algorithms for correctness is quite
1066: // difficult. One way is to modify the rate allocator so that not all
1067: // bit-planes are output if the distortion estimate for last passes is
1068: // the same as for the previous ones.
1069:
1070: switch (ltype) {
1071: case LENGTH_LAZY_GOOD:
1072: // This one is a bit better than LENGTH_LAZY.
1073: int bitsInN3Bytes; // The minimum amount of bits that can be stored
1074: // in the 3 bytes following the current byte
1075: // buffer 'b'.
1076: if (b >= 0xFE) {
1077: // The byte after b can have a bit stuffed so ther could be
1078: // one less bit available
1079: bitsInN3Bytes = 22; // 7 + 8 + 7
1080: } else {
1081: // We are sure that next byte after current byte buffer has no
1082: // bit stuffing
1083: bitsInN3Bytes = 23; // 8 + 7 + 8
1084: }
1085: if ((11 - cT + 16) <= bitsInN3Bytes) {
1086: return nrOfWrittenBytes + (delFF ? 1 : 0) + 1 + 3;
1087: } else {
1088: return nrOfWrittenBytes + (delFF ? 1 : 0) + 1 + 4;
1089: }
1090: case LENGTH_LAZY:
1091: // This is the very basic one that appears in the VM text
1092: if ((27 - cT) <= 22) {
1093: return nrOfWrittenBytes + (delFF ? 1 : 0) + 1 + 3;
1094: } else {
1095: return nrOfWrittenBytes + (delFF ? 1 : 0) + 1 + 4;
1096: }
1097: case LENGTH_NEAR_OPT:
1098: // This is the best length calculation implemented in this class.
1099: // It is almost always optimal. In order to calculate the length
1100: // it is necessary to know which bytes will follow in the MQ
1101: // bit stream, so we need to wait until termination to perform it.
1102: // Save the state to perform the calculation later, in
1103: // finishLengthCalculation()
1104: saveState();
1105: // Return current number of output bytes to use it later in
1106: // finishLengthCalculation()
1107: return nrOfWrittenBytes;
1108: default:
1109: throw new Error("Illegal length calculation type code");
1110: }
1111: }
1112:
1113: /**
1114: * Reinitializes the MQ coder and the underlying 'ByteOutputBuffer' buffer
1115: * as if a new object was instantaited. All the data in the
1116: * 'ByteOutputBuffer' buffer is erased and the state and contexts of the
1117: * MQ coder are reinitialized). Additionally any saved MQ states are
1118: * discarded.
1119: * */
1120: public final void reset() {
1121:
1122: // Reset the output buffer
1123: out.reset();
1124:
1125: a = 0x8000;
1126: c = 0;
1127: b = 0;
1128: if (b == 0xFF)
1129: cT = 13;
1130: else
1131: cT = 12;
1132: resetCtxts();
1133: nrOfWrittenBytes = -1;
1134: delFF = false;
1135:
1136: nSaved = 0;
1137: }
1138:
1139: /**
1140: * Saves the current state of the MQ coder (just the registers, not the
1141: * contexts) so that a near optimal length calculation can be performed
1142: * later.
1143: * */
1144: private void saveState() {
1145: // Increase capacity if necessary
1146: if (nSaved == savedC.length) {
1147: Object tmp;
1148: tmp = savedC;
1149: savedC = new int[nSaved + SAVED_INC];
1150: System.arraycopy(tmp, 0, savedC, 0, nSaved);
1151: tmp = savedCT;
1152: savedCT = new int[nSaved + SAVED_INC];
1153: System.arraycopy(tmp, 0, savedCT, 0, nSaved);
1154: tmp = savedA;
1155: savedA = new int[nSaved + SAVED_INC];
1156: System.arraycopy(tmp, 0, savedA, 0, nSaved);
1157: tmp = savedB;
1158: savedB = new int[nSaved + SAVED_INC];
1159: System.arraycopy(tmp, 0, savedB, 0, nSaved);
1160: tmp = savedDelFF;
1161: savedDelFF = new boolean[nSaved + SAVED_INC];
1162: System.arraycopy(tmp, 0, savedDelFF, 0, nSaved);
1163: }
1164: // Save the current sate
1165: savedC[nSaved] = c;
1166: savedCT[nSaved] = cT;
1167: savedA[nSaved] = a;
1168: savedB[nSaved] = b;
1169: savedDelFF[nSaved] = delFF;
1170: nSaved++;
1171: }
1172:
1173: /**
1174: * Terminates the calculation of the required length for each coding
1175: * pass. This method must be called just after the 'terminate()' one has
1176: * been called for each terminated MQ segment.
1177: *
1178: * <P>The values in 'rates' must have been compensated for any offset due
1179: * to previous terminated segments, so that the correct index to the
1180: * stored coded data is used.
1181: *
1182: * @param rates The array containing the values returned by
1183: * 'getNumCodedBytes()' for each coding pass.
1184: *
1185: * @param n The index in the 'rates' array of the last terminated length.
1186: * */
1187: public void finishLengthCalculation(int rates[], int n) {
1188: if (ltype != LENGTH_NEAR_OPT) {
1189: // For the simple calculations the only thing we need to do is to
1190: // ensure that the calculated lengths are no greater than the
1191: // terminated one
1192: if (n > 0 && rates[n - 1] > rates[n]) {
1193: // We need correction
1194: int tl = rates[n]; // The terminated length
1195: n--;
1196: do {
1197: rates[n--] = tl;
1198: } while (n >= 0 && rates[n] > tl);
1199: }
1200: } else {
1201: // We need to perform the more sophisticated near optimal
1202: // calculation.
1203:
1204: // The calculation of the length is based on the fact that the
1205: // decoder will pad the codestream with an endless string of
1206: // (binary) 1s after termination. If the codestream, padded with
1207: // 1s, is within the bounds of the current interval then correct
1208: // decoding is guaranteed. The lower inclusive bound of the
1209: // current interval is the value of C (i.e. if only lower
1210: // intervals would be coded in the future). The upper exclusive
1211: // bound of the current interval is C+A (i.e. if only upper
1212: // intervals would be coded in the future). We therefore calculate
1213: // the minimum length that would be needed so that padding with 1s
1214: // gives a codestream within the interval.
1215:
1216: // In order to know what will be appended to the current base of
1217: // the interval we need to know what is in the MQ bit stream after
1218: // the current last output byte until the termination. This is why
1219: // this calculation has to be performed after the MQ segment has
1220: // been entirely coded and terminated.
1221:
1222: int cLow; // lower bound on the C register for correct decoding
1223: int cUp; // upper bound on the C register for correct decoding
1224: int bLow; // lower bound on the byte buffer for correct decoding
1225: int bUp; // upper bound on the byte buffer for correct decoding
1226: int ridx; // index in the rates array of the pass we are
1227: // calculating
1228: int sidx; // index in the saved state array
1229: int clen; // current calculated length
1230: boolean cdFF; // the current delayed FF state
1231: int nb; // the next byte of output
1232: int minlen; // minimum possible length
1233: int maxlen; // maximum possible length
1234:
1235: // Start on the first pass of this segment
1236: ridx = n - nSaved;
1237: // Minimum allowable length is length of previous termination
1238: minlen = (ridx - 1 >= 0) ? rates[ridx - 1] : 0;
1239: // Maximum possible length is the terminated length
1240: maxlen = rates[n];
1241: for (sidx = 0; ridx < n; ridx++, sidx++) {
1242: // Load the initial values of the bounds
1243: cLow = savedC[sidx];
1244: cUp = savedC[sidx] + savedA[sidx];
1245: bLow = savedB[sidx];
1246: bUp = savedB[sidx];
1247: // Normalize to CT = 0 and propagate and reset any carry bits
1248: cLow <<= savedCT[sidx];
1249: if ((cLow & 0x8000000) != 0) {
1250: bLow++;
1251: cLow &= 0x7FFFFFF;
1252: }
1253: cUp <<= savedCT[sidx];
1254: if ((cUp & 0x8000000) != 0) {
1255: bUp++;
1256: cUp &= 0x7FFFFFF;
1257: }
1258: // Initialize current calculated length
1259: cdFF = savedDelFF[sidx];
1260: // rates[ridx] contains the number of bytes already output
1261: // when the state was saved, compensated for the offset in the
1262: // output stream.
1263: clen = rates[ridx] + (cdFF ? 1 : 0);
1264: while (true) {
1265: // If we are at end of coded data then this is the length
1266: if (clen >= maxlen) {
1267: clen = maxlen;
1268: break;
1269: }
1270: // Check for sufficiency of coded data
1271: if (cdFF) {
1272: if (bLow < 128 && bUp >= 128) {
1273: // We are done for this pass
1274: clen--; // Don't need delayed FF
1275: break;
1276: }
1277: } else {
1278: if (bLow < 256 && bUp >= 256) {
1279: // We are done for this pass
1280: break;
1281: }
1282: }
1283: // Update bounds with next byte of coded data and
1284: // normalize to CT = 0 again.
1285: nb = (clen >= minlen) ? out.getByte(clen) : 0;
1286: bLow -= nb;
1287: bUp -= nb;
1288: clen++;
1289: if (nb == 0xFF) {
1290: bLow <<= 7;
1291: bLow |= (cLow >> 20) & 0x7F;
1292: cLow &= 0xFFFFF;
1293: cLow <<= 7;
1294: bUp <<= 7;
1295: bUp |= (cUp >> 20) & 0x7F;
1296: cUp &= 0xFFFFF;
1297: cUp <<= 7;
1298: cdFF = true;
1299: } else {
1300: bLow <<= 8;
1301: bLow |= (cLow >> 19) & 0xFF;
1302: cLow &= 0x7FFFF;
1303: cLow <<= 8;
1304: bUp <<= 8;
1305: bUp |= (cUp >> 19) & 0xFF;
1306: cUp &= 0x7FFFF;
1307: cUp <<= 8;
1308: cdFF = false;
1309: }
1310: // Test again
1311: }
1312: // Store the rate found
1313: rates[ridx] = (clen >= minlen) ? clen : minlen;
1314: }
1315: // Reset the saved states
1316: nSaved = 0;
1317: }
1318: }
1319: }
|