001: /*
002: * $RCSfile: MQDecoder.java,v $
003: * $Revision: 1.1 $
004: * $Date: 2005/02/11 05:02:06 $
005: * $State: Exp $
006: *
007: * Class: MQDecoder
008: *
009: * Description: Class that encodes a number of bits using the
010: * MQ arithmetic decoder
011: *
012: *
013: *
014: * COPYRIGHT:
015: *
016: * This software module was originally developed by Raphaël Grosbois and
017: * Diego Santa Cruz (Swiss Federal Institute of Technology-EPFL); Joel
018: * Askelöf (Ericsson Radio Systems AB); and Bertrand Berthelot, David
019: * Bouchard, Félix Henry, Gerard Mozelle and Patrice Onno (Canon Research
020: * Centre France S.A) in the course of development of the JPEG2000
021: * standard as specified by ISO/IEC 15444 (JPEG 2000 Standard). This
022: * software module is an implementation of a part of the JPEG 2000
023: * Standard. Swiss Federal Institute of Technology-EPFL, Ericsson Radio
024: * Systems AB and Canon Research Centre France S.A (collectively JJ2000
025: * Partners) agree not to assert against ISO/IEC and users of the JPEG
026: * 2000 Standard (Users) any of their rights under the copyright, not
027: * including other intellectual property rights, for this software module
028: * with respect to the usage by ISO/IEC and Users of this software module
029: * or modifications thereof for use in hardware or software products
030: * claiming conformance to the JPEG 2000 Standard. Those intending to use
031: * this software module in hardware or software products are advised that
032: * their use may infringe existing patents. The original developers of
033: * this software module, JJ2000 Partners and ISO/IEC assume no liability
034: * for use of this software module or modifications thereof. No license
035: * or right to this software module is granted for non JPEG 2000 Standard
036: * conforming products. JJ2000 Partners have full right to use this
037: * software module for his/her own purpose, assign or donate this
038: * software module to any third party and to inhibit third parties from
039: * using this software module for non JPEG 2000 Standard conforming
040: * products. This copyright notice must be included in all copies or
041: * derivative works of this software module.
042: *
043: * Copyright (c) 1999/2000 JJ2000 Partners.
044: *
045: *
046: *
047: */
048: package jj2000.j2k.entropy.decoder;
049:
050: import jj2000.j2k.entropy.decoder.*;
051: import jj2000.j2k.entropy.*;
052: import jj2000.j2k.io.*;
053: import jj2000.j2k.util.*;
054: import java.io.*;
055:
056: /**
057: * This class implements the MQ arithmetic decoder. It is implemented using
058: * the software conventions decoder for better performance (i.e. execution
059: * time performance). The initial states for each context of the MQ-coder are
060: * specified in the constructor.
061: *
062: */
063:
064: // A trick to test for increased speed: merge the Qe and mPS into 1 thing by
065: // using the sign bit of Qe to signal mPS (positive-or-0 is 0, negative is 1),
066: // and doubling the Qe, nMPS and nLPS tables. This gets rid of the swicthLM
067: // table since it can be integrated as special cases in the doubled nMPS and
068: // nLPS tables. See the JPEG book, chapter 13. The decoded decision can be
069: // calculated as (q>>>31).
070: public class MQDecoder {
071:
072: /** The data structures containing the probabilities for the LPS */
073: final static int qe[] = { 0x5601, 0x3401, 0x1801, 0x0ac1, 0x0521,
074: 0x0221, 0x5601, 0x5401, 0x4801, 0x3801, 0x3001, 0x2401,
075: 0x1c01, 0x1601, 0x5601, 0x5401, 0x5101, 0x4801, 0x3801,
076: 0x3401, 0x3001, 0x2801, 0x2401, 0x2201, 0x1c01, 0x1801,
077: 0x1601, 0x1401, 0x1201, 0x1101, 0x0ac1, 0x09c1, 0x08a1,
078: 0x0521, 0x0441, 0x02a1, 0x0221, 0x0141, 0x0111, 0x0085,
079: 0x0049, 0x0025, 0x0015, 0x0009, 0x0005, 0x0001, 0x5601 };
080:
081: /** The indexes of the next MPS */
082: final static int nMPS[] = { 1, 2, 3, 4, 5, 38, 7, 8, 9, 10, 11, 12,
083: 13, 29, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27,
084: 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42,
085: 43, 44, 45, 45, 46 };
086:
087: /** The indexes of the next LPS */
088: final static int nLPS[] = { 1, 6, 9, 12, 29, 33, 6, 14, 14, 14, 17,
089: 18, 20, 21, 14, 14, 15, 16, 17, 18, 19, 19, 20, 21, 22, 23,
090: 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38,
091: 39, 40, 41, 42, 43, 46 };
092:
093: /** Whether LPS and MPS should be switched */
094: final static int switchLM[] = { 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,
095: 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
096: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
097:
098: /** The ByteInputBuffer used to read the compressed bit stream. */
099: ByteInputBuffer in;
100:
101: /** The current most probable signal for each context */
102: int[] mPS;
103:
104: /** The current index of each context */
105: int[] I;
106:
107: /** The current bit code */
108: int c;
109:
110: /** The bit code counter */
111: int cT;
112:
113: /** The current interval */
114: int a;
115:
116: /** The last byte read */
117: int b;
118:
119: /** Flag indicating if a marker has been found */
120: boolean markerFound;
121:
122: /** The initial state of each context */
123: final int initStates[];
124:
125: /**
126: * Instantiates a new MQ-decoder, with the specified number of contexts and
127: * initial states. The compressed bytestream is read from the 'iStream'
128: * object.
129: *
130: * @param iStream the stream that contains the coded bits
131: *
132: * @param nrOfContexts The number of contexts used
133: *
134: * @param initStates The initial state for each context. A reference is
135: * kept to this array to reinitialize the contexts whenever 'reset()' or
136: * 'resetCtxts()' is called.
137: *
138: *
139: *
140: */
141: public MQDecoder(ByteInputBuffer iStream, int nrOfContexts,
142: int initStates[]) {
143: in = iStream;
144:
145: // Default initialization of the statistics bins is MPS=0 and
146: // I=0
147: I = new int[nrOfContexts];
148: mPS = new int[nrOfContexts];
149: // Save the initial states
150: this .initStates = initStates;
151:
152: // Initialize
153: init();
154:
155: // Set the contexts
156: resetCtxts();
157: }
158:
159: /**
160: * Decodes 'n' symbols from the bit stream using the same context
161: * 'ctxt'. If possible the MQ-coder speedup mode will be used to speed up
162: * decoding. The speedup mode is used if Q (the LPS probability for 'ctxt'
163: * is low enough) and the A and C registers permit decoding several MPS
164: * symbols without renormalization.
165: *
166: * <P>Speedup mode should be used when decoding long runs of MPS with high
167: * probability with the same context.
168: *
169: * <P>This methiod will return the decoded symbols differently if speedup
170: * mode was used or not. If true is returned, then speedup mode was used
171: * and the 'n' decoded symbols are all the same and it is returned ain
172: * bits[0] only. If false is returned then speedup mode was not used, the
173: * decoded symbols are probably not all the same and they are returned in
174: * bits[0], bits[1], ... bits[n-1].
175: *
176: * @param bits The array where to put the decoded symbols. Must be of
177: * length 'n' or more.
178: *
179: * @param ctxt The context to use in decoding the symbols.
180: *
181: * @param n The number of symbols to decode.
182: *
183: * @return True if speedup mode was used, false if not. If speedup mode
184: * was used then all the decoded symbols are the same and its value is
185: * returned in 'bits[0]' only (not in bits[1], bits[2], etc.).
186: *
187: *
188: * */
189: public final boolean fastDecodeSymbols(int[] bits, int ctxt, int n) {
190: int q; // LPS probability for context
191: int idx; // Index of current state
192: int la; // cache for A register
193: int i; // counter
194:
195: idx = I[ctxt];
196: q = qe[idx];
197:
198: // This is a first attempt to implement speedup mode, it is probably
199: // not the most efficient way of doing it.
200:
201: if ((q < 0x4000) && (n <= (a - (c >>> 16) - 1) / q)
202: && (n <= (a - 0x8000) / q + 1)) {
203: // Q is small enough. There will be no modification of C that
204: // affects decoding, and Q can be substracted from A several
205: // times. We will decode all MPS.
206: a -= n * q;
207: if (a >= 0x8000) { // No renormalization needed
208: bits[0] = mPS[ctxt];
209: return true; // Done, used speedup mode
210: } else { // renormalization needed
211: I[ctxt] = nMPS[idx];
212: // Renormalize (MPS: no need for while loop)
213: if (cT == 0)
214: byteIn();
215: a <<= 1;
216: c <<= 1;
217: cT--;
218: // End renormalization
219: bits[0] = mPS[ctxt];
220: return true; // Done, used speedup mode
221: }
222: } else { // Normal mode
223: la = a; // cache A register
224: for (i = 0; i < n; i++) {
225: la -= q;
226: if ((c >>> 16) < la) {
227: if (la >= 0x8000) {
228: bits[i] = mPS[ctxt];
229: } else {
230: // -- MPS Exchange
231: if (la >= q) {
232: bits[i] = mPS[ctxt];
233: idx = nMPS[idx];
234: q = qe[idx];
235: // I[ctxt] set at end of loop
236: // -- Renormalize (MPS: no need for while loop)
237: if (cT == 0)
238: byteIn();
239: la <<= 1;
240: c <<= 1;
241: cT--;
242: // -- End renormalization
243: } else {
244: bits[i] = 1 - mPS[ctxt];
245: if (switchLM[idx] == 1)
246: mPS[ctxt] = 1 - mPS[ctxt];
247: idx = nLPS[idx];
248: q = qe[idx];
249: // I[ctxt] set at end of loop
250: // -- Renormalize
251: do {
252: if (cT == 0)
253: byteIn();
254: la <<= 1;
255: c <<= 1;
256: cT--;
257: } while (la < 0x8000);
258: // -- End renormalization
259: }
260: // -- End MPS Exchange
261: }
262: } else {
263: c -= (la << 16);
264: // -- LPS Exchange
265: if (la < q) {
266: la = q;
267: bits[i] = mPS[ctxt];
268: idx = nMPS[idx];
269: q = qe[idx];
270: // I[ctxt] set at end of loop
271: // -- Renormalize (MPS: no need for while loop)
272: if (cT == 0)
273: byteIn();
274: la <<= 1;
275: c <<= 1;
276: cT--;
277: // -- End renormalization
278: } else {
279: la = q;
280: bits[i] = 1 - mPS[ctxt];
281: if (switchLM[idx] == 1)
282: mPS[ctxt] = 1 - mPS[ctxt];
283: idx = nLPS[idx];
284: q = qe[idx];
285: // I[ctxt] set at end of loop
286: // -- Renormalize
287: do {
288: if (cT == 0)
289: byteIn();
290: la <<= 1;
291: c <<= 1;
292: cT--;
293: } while (la < 0x8000);
294: // -- End renormalization
295: }
296: // -- End LPS Exchange
297: }
298: }
299: a = la; // save cached A register
300: I[ctxt] = idx; // save current index for context
301: return false; // done, did not use speedup mode
302: } // End normal mode
303: }
304:
305: /**
306: * This function performs the arithmetic decoding. The function receives
307: * an array in which to put the decoded symbols and an array of contexts
308: * with which to decode them.
309: *
310: * <P>Each context has a current MPS and an index describing what the
311: * current probability is for the LPS. Each bit is decoded and if the
312: * probability of the LPS exceeds .5, the MPS and LPS are switched.
313: *
314: * @param bits The array where to place the decoded symbols. It should be
315: * long enough to contain 'n' elements.
316: *
317: * @param cX The context to use in decoding each symbol.
318: *
319: * @param n The number of symbols to decode
320: *
321: *
322: */
323: public final void decodeSymbols(int[] bits, int[] cX, int n) {
324: int q;
325: int ctxt;
326: int la; // cache for A register value
327: int index;
328: int i;
329:
330: // NOTE: (a < 0x8000) is equivalent to ((a & 0x8000)==0)
331: // since 'a' is always less than or equal to 0xFFFF
332:
333: // NOTE: conditional exchange guarantees that A for MPS is
334: // always greater than 0x4000 (i.e. 0.375)
335: // => one renormalization shift is enough for MPS
336: // => no need to do a renormalization while loop for MPS
337:
338: for (i = 0; i < n; i++) {
339: ctxt = cX[i];
340:
341: index = I[ctxt];
342: q = qe[index];
343:
344: a -= q;
345: if ((c >>> 16) < a) {
346: if (a >= 0x8000) {
347: bits[i] = mPS[ctxt];
348: } else {
349: la = a;
350: // -- MPS Exchange
351: if (la >= q) {
352: bits[i] = mPS[ctxt];
353: I[ctxt] = nMPS[index];
354: // -- Renormalize (MPS: no need for while loop)
355: if (cT == 0)
356: byteIn();
357: la <<= 1;
358: c <<= 1;
359: cT--;
360: // -- End renormalization
361: } else {
362: bits[i] = 1 - mPS[ctxt];
363: if (switchLM[index] == 1)
364: mPS[ctxt] = 1 - mPS[ctxt];
365: I[ctxt] = nLPS[index];
366: // -- Renormalize
367: do {
368: if (cT == 0)
369: byteIn();
370: la <<= 1;
371: c <<= 1;
372: cT--;
373: } while (la < 0x8000);
374: // -- End renormalization
375: }
376: // -- End MPS Exchange
377: a = la;
378: }
379: } else {
380: la = a;
381: c -= (la << 16);
382: // -- LPS Exchange
383: if (la < q) {
384: la = q;
385: bits[i] = mPS[ctxt];
386: I[ctxt] = nMPS[index];
387: // -- Renormalize (MPS: no need for while loop)
388: if (cT == 0)
389: byteIn();
390: la <<= 1;
391: c <<= 1;
392: cT--;
393: // -- End renormalization
394: } else {
395: la = q;
396: bits[i] = 1 - mPS[ctxt];
397: if (switchLM[index] == 1)
398: mPS[ctxt] = 1 - mPS[ctxt];
399: I[ctxt] = nLPS[index];
400: // -- Renormalize
401: do {
402: if (cT == 0)
403: byteIn();
404: la <<= 1;
405: c <<= 1;
406: cT--;
407: } while (la < 0x8000);
408: // -- End renormalization
409: }
410: // -- End LPS Exchange
411:
412: a = la;
413: }
414: }
415: }
416:
417: /**
418: * Arithmetically decodes one symbol from the bit stream with the given
419: * context and returns its decoded value.
420: *
421: * <P>Each context has a current MPS and an index describing what the
422: * current probability is for the LPS. Each bit is encoded and if the
423: * probability of the LPS exceeds .5, the MPS and LPS are switched.
424: *
425: * @param context The context to use in decoding the symbol
426: *
427: * @return The decoded symbol, 0 or 1.
428: *
429: *
430: */
431: public final int decodeSymbol(int context) {
432: int q;
433: int la;
434: int index;
435: int decision;
436:
437: index = I[context];
438: q = qe[index];
439:
440: // NOTE: (a < 0x8000) is equivalent to ((a & 0x8000)==0)
441: // since 'a' is always less than or equal to 0xFFFF
442:
443: // NOTE: conditional exchange guarantees that A for MPS is
444: // always greater than 0x4000 (i.e. 0.375)
445: // => one renormalization shift is enough for MPS
446: // => no need to do a renormalization while loop for MPS
447:
448: a -= q;
449: if ((c >>> 16) < a) {
450: if (a >= 0x8000) {
451: decision = mPS[context];
452: } else {
453: la = a;
454: // -- MPS Exchange
455: if (la >= q) {
456: decision = mPS[context];
457: I[context] = nMPS[index];
458: // -- Renormalize (MPS: no need for while loop)
459: if (cT == 0)
460: byteIn();
461: la <<= 1;
462: c <<= 1;
463: cT--;
464: // -- End renormalization
465: } else {
466: decision = 1 - mPS[context];
467: if (switchLM[index] == 1)
468: mPS[context] = 1 - mPS[context];
469: I[context] = nLPS[index];
470: // -- Renormalize
471: do {
472: if (cT == 0)
473: byteIn();
474: la <<= 1;
475: c <<= 1;
476: cT--;
477: } while (la < 0x8000);
478: // -- End renormalization
479: }
480: // -- End MPS Exchange
481: a = la;
482: }
483: } else {
484: la = a;
485: c -= (la << 16);
486: // -- LPS Exchange
487: if (la < q) {
488: la = q;
489: decision = mPS[context];
490: I[context] = nMPS[index];
491: // -- Renormalize (MPS: no need for while loop)
492: if (cT == 0)
493: byteIn();
494: la <<= 1;
495: c <<= 1;
496: cT--;
497: // -- End renormalization
498: } else {
499: la = q;
500: decision = 1 - mPS[context];
501: if (switchLM[index] == 1)
502: mPS[context] = 1 - mPS[context];
503: I[context] = nLPS[index];
504: // -- Renormalize
505: do {
506: if (cT == 0)
507: byteIn();
508: la <<= 1;
509: c <<= 1;
510: cT--;
511: } while (la < 0x8000);
512: // -- End renormalization
513: }
514: // -- End LPS Exchange
515:
516: a = la;
517: }
518: return decision;
519: }
520:
521: /**
522: * Checks for past errors in the decoding process using the predictable
523: * error resilient termination. This works only if the encoder used the
524: * predictable error resilient MQ termination, otherwise it reports wrong
525: * results. If an error is detected it means that the MQ bit stream has
526: * been wrongly decoded or that the MQ terminated segment length is too
527: * long. If no errors are detected it does not necessarily mean that the
528: * MQ bit stream has been correctly decoded.
529: *
530: * @return True if errors are found, false otherwise.
531: * */
532: public boolean checkPredTerm() {
533: int k; // Number of bits that where added in the termination process
534: int q;
535:
536: // 1) if everything has been OK, 'b' must be 0xFF if a terminating
537: // marker has not yet been found
538: if (b != 0xFF && !markerFound)
539: return true;
540:
541: // 2) if cT is not 0, we must have already reached the terminating
542: // marker
543: if (cT != 0 && !markerFound)
544: return true;
545:
546: // 3) If cT is 1 there where no spare bits at the encoder, this is all
547: // that we can check
548: if (cT == 1)
549: return false;
550:
551: // 4) if cT is 0, then next byte must be the second byte of a
552: // terminating marker (i.e. larger than 0x8F) if the terminating
553: // marker has not been reached yet
554: if (cT == 0) {
555: if (!markerFound) {
556: // Get next byte and check
557: b = in.read() & 0xFF;
558: if (b <= 0x8F)
559: return true;
560: }
561: // Adjust cT for last byte
562: cT = 8;
563: }
564:
565: // 5) Now we can calculate the number 'k' of bits having error
566: // resilience information, which is the number of bits left to
567: // normalization in the C register, minus 1.
568: k = cT - 1;
569:
570: // 6) The predictable termination policy is as if an LPS interval was
571: // coded that caused a renormalization of 'k' bits, before the
572: // termination marker started
573:
574: // We first check if an LPS is decoded, that causes a renormalization
575: // of 'k' bits. Worst case is smallest LPS probability 'q' that causes
576: // a renormalization of 'k' bits.
577: q = 0x8000 >> k;
578:
579: // Check that we can decode an LPS interval of probability 'q'
580: a -= q;
581: if ((c >>> 16) < a) {
582: // Error: MPS interval decoded
583: return true;
584: }
585: // OK: LPS interval decoded
586: c -= (a << 16);
587: // -- LPS Exchange
588: // Here 'a' can not be smaller than 'q' because the minimum value
589: // for 'a' is 0x8000-0x4000=0x4000 and 'q' is set to a value equal
590: // to or smaller than that.
591: a = q;
592: // -- Renormalize
593: do {
594: if (cT == 0)
595: byteIn();
596: a <<= 1;
597: c <<= 1;
598: cT--;
599: } while (a < 0x8000);
600: // -- End renormalization
601: // -- End LPS Exchange
602:
603: // 7) Everything seems OK, we have checked the C register for the LPS
604: // symbols and ensured that it is followed by bits synthetized by the
605: // termination marker.
606: return false;
607: }
608:
609: /**
610: * This function gets one byte of compressed bits from the in-stream.
611: * the byte is added to c. If the byte is 0xFF and the next byte is greater
612: * than 0x8F, the byte after 0xFF is a marker.
613: *
614: *
615: *
616: */
617: private void byteIn() {
618: if (!markerFound) {
619: if (b == 0xFF) {
620: b = in.read() & 0xFF; // Convert EOFs (-1) to 0xFF
621:
622: if (b > 0x8F) {
623: markerFound = true;
624: // software-convention decoder: c unchanged
625: cT = 8;
626: } else {
627: c += 0xFE00 - (b << 9);
628: cT = 7;
629: }
630: } else {
631: b = in.read() & 0xFF; // Convert EOFs (-1) to 0xFF
632: c += 0xFF00 - (b << 8);
633: cT = 8;
634: }
635: } else {
636: // software-convention decoder: c unchanged
637: cT = 8;
638: }
639: }
640:
641: /**
642: * Returns the number of contexts in the arithmetic coder.
643: *
644: * @return The number of contexts
645: *
646: *
647: **/
648: public final int getNumCtxts() {
649: return I.length;
650: }
651:
652: /**
653: * Resets a context to the original probability distribution.
654: *
655: * @param c The number of the context (it starts at 0).
656: *
657: *
658: *
659: */
660: public final void resetCtxt(int c) {
661: I[c] = initStates[c];
662: mPS[c] = 0;
663: }
664:
665: /**
666: * Resets a context to the original probability distribution. The
667: * original probability distribution depends on the actual
668: * implementation of the arithmetic coder or decoder.
669: *
670: * @param c The index of the context (it starts at 0).
671: *
672: *
673: *
674: */
675: public final void resetCtxts() {
676: System.arraycopy(initStates, 0, I, 0, I.length);
677: ArrayUtil.intArraySet(mPS, 0);
678: }
679:
680: /**
681: * Resets the MQ decoder to start a new segment. This is like recreating a
682: * new MQDecoder object with new input data.
683: *
684: * @param buf The byte array containing the MQ encoded data. If null the
685: * current byte array is assumed.
686: *
687: * @param off The index of the first element in 'buf' to be decoded. If
688: * negative the byte just after the previous segment is assumed, only
689: * valid if 'buf' is null.
690: *
691: * @param len The number of bytes in 'buf' to be decoded. Any subsequent
692: * bytes are taken to be 0xFF.
693: *
694: *
695: * */
696: public final void nextSegment(byte buf[], int off, int len) {
697: // Set the new input
698: in.setByteArray(buf, off, len);
699: // Reinitialize MQ
700: init();
701: }
702:
703: /**
704: * Returns the underlying 'ByteInputBuffer' from where the MQ
705: * coded input bytes are read.
706: *
707: * @return The underlying ByteInputBuffer.
708: *
709: * */
710: public ByteInputBuffer getByteInputBuffer() {
711: return in;
712: }
713:
714: /**
715: * Initializes the state of the MQ coder, without modifying the current
716: * context states. It sets the registers (A,C,B) and the "marker found"
717: * state to the initial state, to start the decoding of a new segment.
718: *
719: * <P>To have a complete reset of the MQ (as if a new MQDecoder object was
720: * created) 'resetCtxts()' should be called after this method.
721: *
722: *
723: * */
724: private void init() {
725: // --- INITDEC
726: markerFound = false;
727:
728: // Read first byte
729: b = in.read() & 0xFF;
730:
731: // Software conventions decoder
732: c = (b ^ 0xFF) << 16;
733: byteIn();
734: c = c << 7;
735: cT = cT - 7;
736: a = 0x8000;
737:
738: // End of INITDEC ---
739: }
740: }
|