corrade-vassal – Blame information for rev 1

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 vero 1 /*
2 * CVS identifier:
3 *
4 * $Id: MQCoder.java,v 1.36 2002/01/10 10:31:28 grosbois Exp $
5 *
6 * Class: MQCoder
7 *
8 * Description: Class that encodes a number of bits using the
9 * MQ arithmetic coder
10 *
11 *
12 * Diego SANTA CRUZ, Jul-26-1999 (improved speed)
13 *
14 * COPYRIGHT:
15 *
16 * This software module was originally developed by Raphaël Grosbois and
17 * Diego Santa Cruz (Swiss Federal Institute of Technology-EPFL); Joel
18 * Askelöf (Ericsson Radio Systems AB); and Bertrand Berthelot, David
19 * Bouchard, Félix Henry, Gerard Mozelle and Patrice Onno (Canon Research
20 * Centre France S.A) in the course of development of the JPEG2000
21 * standard as specified by ISO/IEC 15444 (JPEG 2000 Standard). This
22 * software module is an implementation of a part of the JPEG 2000
23 * Standard. Swiss Federal Institute of Technology-EPFL, Ericsson Radio
24 * Systems AB and Canon Research Centre France S.A (collectively JJ2000
25 * Partners) agree not to assert against ISO/IEC and users of the JPEG
26 * 2000 Standard (Users) any of their rights under the copyright, not
27 * including other intellectual property rights, for this software module
28 * with respect to the usage by ISO/IEC and Users of this software module
29 * or modifications thereof for use in hardware or software products
30 * claiming conformance to the JPEG 2000 Standard. Those intending to use
31 * this software module in hardware or software products are advised that
32 * their use may infringe existing patents. The original developers of
33 * this software module, JJ2000 Partners and ISO/IEC assume no liability
34 * for use of this software module or modifications thereof. No license
35 * or right to this software module is granted for non JPEG 2000 Standard
36 * conforming products. JJ2000 Partners have full right to use this
37 * software module for his/her own purpose, assign or donate this
38 * software module to any third party and to inhibit third parties from
39 * using this software module for non JPEG 2000 Standard conforming
40 * products. This copyright notice must be included in all copies or
41 * derivative works of this software module.
42 *
43 * Copyright (c) 1999/2000 JJ2000 Partners.
44 * */
45 using System;
46 using CSJ2K.j2k.entropy.encoder;
47 using CSJ2K.j2k.entropy;
48 using CSJ2K.j2k.util;
49 using CSJ2K.j2k;
50 namespace CSJ2K.j2k.entropy.encoder
51 {
52  
53 /// <summary> This class implements the MQ arithmetic coder. When initialized a specific
54 /// state can be specified for each context, which may be adapted to the
55 /// probability distribution that is expected for that context.
56 ///
57 /// <p>The type of length calculation and termination can be chosen at
58 /// construction time.
59 ///
60 /// ---- Tricks that have been tried to improve speed ----
61 ///
62 /// <p>1) Merging Qe and mPS and doubling the lookup tables<br>
63 ///
64 /// Merge the mPS into Qe, as the sign bit (if Qe>=0 the sense of MPS is 0, if
65 /// Qe<0 the sense is 1), and double the lookup tables. The first half of the
66 /// lookup tables correspond to Qe>=0 (i.e. the sense of MPS is 0) and the
67 /// second half to Qe<0 (i.e. the sense of MPS is 1). The nLPS lookup table is
68 /// modified to incorporate the changes in the sense of MPS, by making it jump
69 /// from the first to the second half and vice-versa, when a change is
70 /// specified by the swicthLM lookup table. See JPEG book, section 13.2, page
71 /// 225. <br>
72 ///
73 /// There is NO speed improvement in doing this, actually there is a slight
74 /// decrease, probably due to the fact that often Q has to be negated. Also the
75 /// fact that a brach of the type "if (bit==mPS[li])" is replaced by two
76 /// simpler braches of the type "if (bit==0)" and "if (q<0)" may contribute to
77 /// that.</p>
78 ///
79 /// <p>2) Removing cT<br>
80 ///
81 /// It is possible to remove the cT counter by setting a flag bit in the high
82 /// bits of the C register. This bit will be automatically shifted left
83 /// whenever a renormalization shift occurs, which is equivalent to decreasing
84 /// cT. When the flag bit reaches the sign bit (leftmost bit), which is
85 /// equivalenet to cT==0, the byteOut() procedure is called. This test can be
86 /// done efficiently with "c<0" since C is a signed quantity. Care must be
87 /// taken in byteOut() to reset the bit in order to not interfere with other
88 /// bits in the C register. See JPEG book, page 228.<br>
89 ///
90 /// There is NO speed improvement in doing this. I don't really know why since
91 /// the number of operations whenever a renormalization occurs is
92 /// decreased. Maybe it is due to the number of extra operations in the
93 /// byteOut(), terminate() and getNumCodedBytes() procedures.</p>
94 ///
95 /// <p>3) Change the convention of MPS and LPS.<br>
96 ///
97 /// Making the LPS interval be above the MPS interval (MQ coder convention is
98 /// the opposite) can reduce the number of operations along the MPS path. In
99 /// order to generate the same bit stream as with the MQ convention the output
100 /// bytes need to be modified accordingly. The basic rule for this is that C =
101 /// (C'^0xFF...FF)-A, where C is the codestream for the MQ convention and C' is
102 /// the codestream generated by this other convention. Note that this affects
103 /// bit-stuffing as well.<br>
104 ///
105 /// This has not been tested yet.<br>
106 ///
107 /// <p>4) Removing normalization while loop on MPS path<br>
108 ///
109 /// Since in the MPS path Q is guaranteed to be always greater than 0x4000
110 /// (decimal 0.375) it is never necessary to do more than 1 renormalization
111 /// shift. Therefore the test of the while loop, and the loop itself, can be
112 /// removed.</p>
113 ///
114 /// <p>5) Simplifying test on A register<br>
115 ///
116 /// Since A is always less than or equal to 0xFFFF, the test "(a & 0x8000)==0"
117 /// can be replaced by the simplete test "a < 0x8000". This test is simpler in
118 /// Java since it involves only 1 operation (although the original test can be
119 /// converted to only one operation by smart Just-In-Time compilers)<br>
120 ///
121 /// This change has been integrated in the decoding procedures.</p>
122 ///
123 /// <p>6) Speedup mode<br>
124 ///
125 /// Implemented a method that uses the speedup mode of the MQ-coder if
126 /// possible. This should greately improve performance when coding long runs of
127 /// MPS symbols that have high probability. However, to take advantage of this,
128 /// the entropy coder implementation has to explicetely use it. The generated
129 /// bit stream is the same as if no speedup mode would have been used.<br>
130 ///
131 /// Implemented but performance not tested yet.</p>
132 ///
133 /// <p>7) Multiple-symbol coding<br>
134 ///
135 /// Since the time spent in a method call is non-negligable, coding several
136 /// symbols with one method call reduces the overhead per coded symbol. The
137 /// decodeSymbols() method implements this. However, to take advantage of it,
138 /// the implementation of the entropy coder has to explicitely use it.<br>
139 ///
140 /// Implemented but performance not tested yet.</p>
141 ///
142 /// </summary>
143 public class MQCoder
144 {
145 /// <summary> Set the length calculation type to the specified type.
146 ///
147 /// </summary>
148 /// <param name="ltype">The type of length calculation to use. One of
149 /// 'LENGTH_LAZY', 'LENGTH_LAZY_GOOD' or 'LENGTH_NEAR_OPT'.
150 ///
151 /// </param>
152 virtual public int LenCalcType
153 {
154 set
155 {
156 // Verify the ttype and ltype
157 if (value != LENGTH_LAZY && value != LENGTH_LAZY_GOOD && value != LENGTH_NEAR_OPT)
158 {
159 throw new System.ArgumentException("Unrecognized length " + "calculation type code: " + value);
160 }
161  
162 if (value == LENGTH_NEAR_OPT)
163 {
164 if (savedC == null)
165 savedC = new int[SAVED_LEN];
166 if (savedCT == null)
167 savedCT = new int[SAVED_LEN];
168 if (savedA == null)
169 savedA = new int[SAVED_LEN];
170 if (savedB == null)
171 savedB = new int[SAVED_LEN];
172 if (savedDelFF == null)
173 savedDelFF = new bool[SAVED_LEN];
174 }
175 this.ltype = value;
176 }
177  
178 }
179 /// <summary> Set termination type to the specified type.
180 ///
181 /// </summary>
182 /// <param name="ttype">The type of termination to use. One of 'TERM_FULL',
183 /// 'TERM_NEAR_OPT', 'TERM_EASY' or 'TERM_PRED_ER'.
184 ///
185 /// </param>
186 virtual public int TermType
187 {
188 set
189 {
190 if (value != TERM_FULL && value != TERM_NEAR_OPT && value != TERM_EASY && value != TERM_PRED_ER)
191 {
192 throw new System.ArgumentException("Unrecognized termination " + "type code: " + value);
193 }
194 this.ttype = value;
195 }
196  
197 }
198 /// <summary> Returns the number of contexts in the arithmetic coder.
199 ///
200 /// </summary>
201 /// <returns> The number of contexts
202 ///
203 /// </returns>
204 virtual public int NumCtxts
205 {
206 get
207 {
208 return I.Length;
209 }
210  
211 }
212 /// <summary> Returns the number of bytes that are necessary from the compressed
213 /// output stream to decode all the symbols that have been coded this
214 /// far. The number of returned bytes does not include anything coded
215 /// previous to the last time the 'terminate()' or 'reset()' methods where
216 /// called.
217 ///
218 /// <p>The values returned by this method are then to be used in finishing
219 /// the length calculation with the 'finishLengthCalculation()' method,
220 /// after compensation of the offset in the number of bytes due to previous
221 /// terminated segments.</p>
222 ///
223 /// <p>This method should not be called if the current coding pass is to be
224 /// terminated. The 'terminate()' method should be called instead.</p>
225 ///
226 /// <p>The calculation is done based on the type of length calculation
227 /// specified at the constructor.</p>
228 ///
229 /// </summary>
230 /// <returns> The number of bytes in the compressed output stream necessary
231 /// to decode all the information coded this far.
232 ///
233 /// </returns>
234 virtual public int NumCodedBytes
235 {
236 get
237 {
238 // NOTE: testing these algorithms for correctness is quite
239 // difficult. One way is to modify the rate allocator so that not all
240 // bit-planes are output if the distortion estimate for last passes is
241 // the same as for the previous ones.
242  
243 switch (ltype)
244 {
245  
246 case LENGTH_LAZY_GOOD:
247 // This one is a bit better than LENGTH_LAZY.
248 int bitsInN3Bytes; // The minimum amount of bits that can be
249 // stored in the 3 bytes following the current byte buffer 'b'.
250  
251 if (b >= 0xFE)
252 {
253 // The byte after b can have a bit stuffed so ther could be
254 // one less bit available
255 bitsInN3Bytes = 22; // 7 + 8 + 7
256 }
257 else
258 {
259 // We are sure that next byte after current byte buffer has no
260 // bit stuffing
261 bitsInN3Bytes = 23; // 8 + 7 + 8
262 }
263 if ((11 - cT + 16) <= bitsInN3Bytes)
264 {
265 return nrOfWrittenBytes + (delFF?1:0) + 1 + 3;
266 }
267 else
268 {
269 return nrOfWrittenBytes + (delFF?1:0) + 1 + 4;
270 }
271 //goto case LENGTH_LAZY;
272  
273 case LENGTH_LAZY:
274 // This is the very basic one that appears in the VM text
275 if ((27 - cT) <= 22)
276 {
277 return nrOfWrittenBytes + (delFF?1:0) + 1 + 3;
278 }
279 else
280 {
281 return nrOfWrittenBytes + (delFF?1:0) + 1 + 4;
282 }
283 //goto case LENGTH_NEAR_OPT;
284  
285 case LENGTH_NEAR_OPT:
286 // This is the best length calculation implemented in this class.
287 // It is almost always optimal. In order to calculate the length
288 // it is necessary to know which bytes will follow in the MQ
289 // bit stream, so we need to wait until termination to perform it.
290 // Save the state to perform the calculation later, in
291 // finishLengthCalculation()
292 saveState();
293 // Return current number of output bytes to use it later in
294 // finishLengthCalculation()
295 return nrOfWrittenBytes;
296  
297 default:
298 throw new System.ApplicationException("Illegal length calculation type code");
299  
300 }
301 }
302  
303 }
304  
305 /// <summary>Identifier for the lazy length calculation. The lazy length
306 /// calculation is not optimal but is extremely simple.
307 /// </summary>
308 public const int LENGTH_LAZY = 0;
309  
310 /// <summary>Identifier for a very simple length calculation. This provides better
311 /// results than the 'LENGTH_LAZY' computation. This is the old length
312 /// calculation that was implemented in this class.
313 /// </summary>
314 public const int LENGTH_LAZY_GOOD = 1;
315  
316 /// <summary>Identifier for the near optimal length calculation. This calculation
317 /// is more complex than the lazy one but provides an almost optimal length
318 /// calculation.
319 /// </summary>
320 public const int LENGTH_NEAR_OPT = 2;
321  
322 /// <summary>The identifier fort the termination that uses a full flush. This is
323 /// the less efficient termination.
324 /// </summary>
325 public const int TERM_FULL = 0;
326  
327 /// <summary>The identifier for the termination that uses the near optimal length
328 /// calculation to terminate the arithmetic codewrod
329 /// </summary>
330 public const int TERM_NEAR_OPT = 1;
331  
332 /// <summary>The identifier for the easy termination that is simpler than the
333 /// 'TERM_NEAR_OPT' one but slightly less efficient.
334 /// </summary>
335 public const int TERM_EASY = 2;
336  
337 /// <summary>The identifier for the predictable termination policy for error
338 /// resilience. This is the same as the 'TERM_EASY' one but an special
339 /// sequence of bits is embodied in the spare bits for error resilience
340 /// purposes.
341 /// </summary>
342 public const int TERM_PRED_ER = 3;
343  
344 /// <summary>The data structures containing the probabilities for the LPS </summary>
345 //UPGRADE_NOTE: Final was removed from the declaration of 'qe'. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1003'"
346 internal static readonly int[] qe = new int[]{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};
347  
348 /// <summary>The indexes of the next MPS </summary>
349 //UPGRADE_NOTE: Final was removed from the declaration of 'nMPS'. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1003'"
350 internal static readonly int[] nMPS = new int[]{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};
351  
352 /// <summary>The indexes of the next LPS </summary>
353 //UPGRADE_NOTE: Final was removed from the declaration of 'nLPS'. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1003'"
354 internal static readonly int[] nLPS = new int[]{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};
355  
356 /// <summary>Whether LPS and MPS should be switched </summary>
357 //UPGRADE_NOTE: Final was removed from the declaration of 'switchLM'. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1003'"
358 internal static readonly int[] switchLM = new int[]{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};
359 // Having ints proved to be more efficient than booleans
360  
361 /// <summary>The ByteOutputBuffer used to write the compressed bit stream. </summary>
362 internal ByteOutputBuffer out_Renamed;
363  
364 /// <summary>The current most probable signal for each context </summary>
365 internal int[] mPS;
366  
367 /// <summary>The current index of each context </summary>
368 internal int[] I;
369  
370 /// <summary>The current bit code </summary>
371 internal int c;
372  
373 /// <summary>The bit code counter </summary>
374 internal int cT;
375  
376 /// <summary>The current interval </summary>
377 internal int a;
378  
379 /// <summary>The last encoded byte of data </summary>
380 internal int b;
381  
382 /// <summary>If a 0xFF byte has been delayed and not yet been written to the output
383 /// (in the MQ we can never have more than 1 0xFF byte in a row).
384 /// </summary>
385 internal bool delFF;
386  
387 /// <summary>The number of written bytes so far, excluding any delayed 0xFF
388 /// bytes. Upon initialization it is -1 to indicated that the byte buffer
389 /// 'b' is empty as well.
390 /// </summary>
391 internal int nrOfWrittenBytes = - 1;
392  
393 /// <summary>The initial state of each context </summary>
394 internal int[] initStates;
395  
396 /// <summary>The termination type to use. One of 'TERM_FULL', 'TERM_NEAR_OPT',
397 /// 'TERM_EASY' or 'TERM_PRED_ER'.
398 /// </summary>
399 internal int ttype;
400  
401 /// <summary>The length calculation type to use. One of 'LENGTH_LAZY',
402 /// 'LENGTH_LAZY_GOOD', 'LENGTH_NEAR_OPT'.
403 /// </summary>
404 internal int ltype;
405  
406 /// <summary>Saved values of the C register. Used for the LENGTH_NEAR_OPT length
407 /// calculation.
408 /// </summary>
409 internal int[] savedC;
410  
411 /// <summary>Saved values of CT counter. Used for the LENGTH_NEAR_OPT length
412 /// calculation.
413 /// </summary>
414 internal int[] savedCT;
415  
416 /// <summary>Saved values of the A register. Used for the LENGTH_NEAR_OPT length
417 /// calculation.
418 /// </summary>
419 internal int[] savedA;
420  
421 /// <summary>Saved values of the B byte buffer. Used for the LENGTH_NEAR_OPT length
422 /// calculation.
423 /// </summary>
424 internal int[] savedB;
425  
426 /// <summary>Saved values of the delFF (i.e. delayed 0xFF) state. Used for the
427 /// LENGTH_NEAR_OPT length calculation.
428 /// </summary>
429 internal bool[] savedDelFF;
430  
431 /// <summary>Number of saved states. Used for the LENGTH_NEAR_OPT length
432 /// calculation.
433 /// </summary>
434 internal int nSaved;
435  
436 /// <summary>The initial length of the arrays to save sates </summary>
437 //UPGRADE_NOTE: Final was removed from the declaration of 'SAVED_LEN '. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1003'"
438 internal static readonly int SAVED_LEN = 32 * CSJ2K.j2k.entropy.StdEntropyCoderOptions.NUM_PASSES;
439  
440 /// <summary>The increase in length for the arrays to save states </summary>
441 //UPGRADE_NOTE: Final was removed from the declaration of 'SAVED_INC '. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1003'"
442 internal static readonly int SAVED_INC = 4 * CSJ2K.j2k.entropy.StdEntropyCoderOptions.NUM_PASSES;
443  
444 /// <summary> Instantiates a new MQ-coder, with the specified number of contexts and
445 /// initial states. The compressed bytestream is written to the 'oStream'
446 /// object.
447 ///
448 /// </summary>
449 /// <param name="oStream">where to output the compressed data.
450 ///
451 /// </param>
452 /// <param name="nrOfContexts">The number of contexts used by the MQ coder.
453 ///
454 /// </param>
455 /// <param name="init">The initial state for each context. A reference is kept to
456 /// this array to reinitialize the contexts whenever 'reset()' or
457 /// 'resetCtxts()' is called.
458 ///
459 /// </param>
460 public MQCoder(ByteOutputBuffer oStream, int nrOfContexts, int[] init)
461 {
462 out_Renamed = oStream;
463  
464 // --- INITENC
465  
466 // Default initialization of the statistics bins is MPS=0 and
467 // I=0
468 I = new int[nrOfContexts];
469 mPS = new int[nrOfContexts];
470 initStates = init;
471  
472 a = 0x8000;
473 c = 0;
474 if (b == 0xFF)
475 {
476 cT = 13;
477 }
478 else
479 {
480 cT = 12;
481 }
482  
483 resetCtxts();
484  
485 // End of INITENC ---
486 b = 0;
487 }
488  
489 /// <summary> This method performs the coding of the symbol 'bit', using context
490 /// 'ctxt', 'n' times, using the MQ-coder speedup mode if possible.
491 ///
492 /// <p>If the symbol 'bit' is the current more probable symbol (MPS) and
493 /// qe[ctxt]<=0x4000, and (A-0x8000)>=qe[ctxt], speedup mode will be
494 /// used. Otherwise the normal mode will be used. The speedup mode can
495 /// significantly improve the speed of arithmetic coding when several MPS
496 /// symbols, with a high probability distribution, must be coded with the
497 /// same context. The generated bit stream is the same as if the normal mode
498 /// was used.</p>
499 ///
500 /// <p>This method is also faster than the 'codeSymbols()' and
501 /// 'codeSymbol()' ones, for coding the same symbols with the same context
502 /// several times, when speedup mode can not be used, although not
503 /// significantly.</p>
504 ///
505 /// </summary>
506 /// <param name="bit">The symbol do code, 0 or 1.
507 ///
508 /// </param>
509 /// <param name="ctxt">The context to us in coding the symbol.
510 ///
511 /// </param>
512 /// <param name="n">The number of times that the symbol must be coded.
513 ///
514 /// </param>
515 public void fastCodeSymbols(int bit, int ctxt, int n)
516 {
517 int q; // cache for context's Qe
518 int la; // cache for A register
519 int nc; // counter for renormalization shifts
520 int ns; // the maximum length of a speedup mode run
521 int li; // cache for I[ctxt]
522  
523 li = I[ctxt]; // cache current index
524 q = qe[li]; // retrieve current LPS prob.
525  
526 if ((q <= 0x4000) && (bit == mPS[ctxt]) && ((ns = (a - 0x8000) / q + 1) > 1))
527 {
528 // Do speed up mode
529 // coding MPS, no conditional exchange can occur and
530 // speedup mode is possible for more than 1 symbol
531 do
532 {
533 // do as many speedup runs as necessary
534 if (n <= ns)
535 {
536 // All symbols in this run
537 // code 'n' symbols
538 la = n * q; // accumulated Q
539 a -= la;
540 c += la;
541 if (a >= 0x8000)
542 {
543 // no renormalization
544 I[ctxt] = li; // save the current state
545 return ; // done
546 }
547 I[ctxt] = nMPS[li]; // goto next state and save it
548 // -- Renormalization (MPS: no need for while loop)
549 a <<= 1; // a is doubled
550 c <<= 1; // c is doubled
551 cT--;
552 if (cT == 0)
553 {
554 byteOut();
555 }
556 // -- End of renormalization
557 return ; // done
558 }
559 else
560 {
561 // Not all symbols in this run
562 // code 'ns' symbols
563 la = ns * q; // accumulated Q
564 c += la;
565 a -= la;
566 // cache li and q for next iteration
567 li = nMPS[li];
568 q = qe[li]; // New q is always less than current one
569 // new I[ctxt] is stored in last run
570 // Renormalization always occurs since we exceed 'ns'
571 // -- Renormalization (MPS: no need for while loop)
572 a <<= 1; // a is doubled
573 c <<= 1; // c is doubled
574 cT--;
575 if (cT == 0)
576 {
577 byteOut();
578 }
579 // -- End of renormalization
580 n -= ns; // symbols left to code
581 ns = (a - 0x8000) / q + 1; // max length of next speedup run
582 continue; // goto next iteration
583 }
584 }
585 while (n > 0);
586 }
587 // end speed up mode
588 else
589 {
590 // No speedup mode
591 // Either speedup mode is not possible or not worth doing it
592 // because of probable conditional exchange
593 // Code everything as in normal mode
594 la = a; // cache A register in local variable
595 do
596 {
597 if (bit == mPS[ctxt])
598 {
599 // -- code MPS
600 la -= q; // Interval division associated with MPS coding
601 if (la >= 0x8000)
602 {
603 // Interval big enough
604 c += q;
605 }
606 else
607 {
608 // Interval too short
609 if (la < q)
610 {
611 // Probabilities are inverted
612 la = q;
613 }
614 else
615 {
616 c += q;
617 }
618 // cache new li and q for next iteration
619 li = nMPS[li];
620 q = qe[li];
621 // new I[ctxt] is stored after end of loop
622 // -- Renormalization (MPS: no need for while loop)
623 la <<= 1; // a is doubled
624 c <<= 1; // c is doubled
625 cT--;
626 if (cT == 0)
627 {
628 byteOut();
629 }
630 // -- End of renormalization
631 }
632 }
633 else
634 {
635 // -- code LPS
636 la -= q; // Interval division according to LPS coding
637 if (la < q)
638 {
639 c += q;
640 }
641 else
642 {
643 la = q;
644 }
645 if (switchLM[li] != 0)
646 {
647 mPS[ctxt] = 1 - mPS[ctxt];
648 }
649 // cache new li and q for next iteration
650 li = nLPS[li];
651 q = qe[li];
652 // new I[ctxt] is stored after end of loop
653 // -- Renormalization
654 // sligthly better than normal loop
655 nc = 0;
656 do
657 {
658 la <<= 1;
659 nc++; // count number of necessary shifts
660 }
661 while (la < 0x8000);
662 if (cT > nc)
663 {
664 c <<= nc;
665 cT -= nc;
666 }
667 else
668 {
669 do
670 {
671 c <<= cT;
672 nc -= cT;
673 // cT = 0; // not necessary
674 byteOut();
675 }
676 while (cT <= nc);
677 c <<= nc;
678 cT -= nc;
679 }
680 // -- End of renormalization
681 }
682 n--;
683 }
684 while (n > 0);
685 I[ctxt] = li; // store new I[ctxt]
686 a = la; // save cached A register
687 }
688 }
689  
690 /// <summary> This function performs the arithmetic encoding of several symbols
691 /// together. The function receives an array of symbols that are to be
692 /// encoded and an array containing the contexts with which to encode them.
693 ///
694 /// <p>The advantage of using this function is that the cost of the method
695 /// call is amortized by the number of coded symbols per method call.</p>
696 ///
697 /// <p>Each context has a current MPS and an index describing what the
698 /// current probability is for the LPS. Each bit is encoded and if the
699 /// probability of the LPS exceeds .5, the MPS and LPS are switched.</p>
700 ///
701 /// </summary>
702 /// <param name="bits">An array containing the symbols to be encoded. Valid
703 /// symbols are 0 and 1.
704 ///
705 /// </param>
706 /// <param name="cX">The context for each of the symbols to be encoded.
707 ///
708 /// </param>
709 /// <param name="n">The number of symbols to encode.
710 ///
711 /// </param>
712 public void codeSymbols(int[] bits, int[] cX, int n)
713 {
714 int q;
715 int li; // local cache of I[context]
716 int la;
717 int nc;
718 int ctxt; // context of current symbol
719 int i; // counter
720  
721 // NOTE: here we could use symbol aggregation to speed things up.
722 // It remains to be studied.
723  
724 la = a; // cache A register in local variable
725 for (i = 0; i < n; i++)
726 {
727 // NOTE: (a<0x8000) is equivalent to ((a&0x8000)==0)
728 // since 'a' is always less than or equal to 0xFFFF
729  
730 // NOTE: conditional exchange guarantees that A for MPS is
731 // always greater than 0x4000 (i.e. 0.375)
732 // => one renormalization shift is enough for MPS
733 // => no need to do a renormalization while loop for MPS
734  
735 ctxt = cX[i];
736 li = I[ctxt];
737 q = qe[li]; // Retrieve current LPS prob.
738  
739 if (bits[i] == mPS[ctxt])
740 {
741 // -- Code MPS
742  
743 la -= q; // Interval division associated with MPS coding
744  
745 if (la >= 0x8000)
746 {
747 // Interval big enough
748 c += q;
749 }
750 else
751 {
752 // Interval too short
753 if (la < q)
754 {
755 // Probabilities are inverted
756 la = q;
757 }
758 else
759 {
760 c += q;
761 }
762  
763 I[ctxt] = nMPS[li];
764  
765 // -- Renormalization (MPS: no need for while loop)
766 la <<= 1; // a is doubled
767 c <<= 1; // c is doubled
768 cT--;
769 if (cT == 0)
770 {
771 byteOut();
772 }
773 // -- End of renormalization
774 }
775 }
776 else
777 {
778 // -- Code LPS
779 la -= q; // Interval division according to LPS coding
780  
781 if (la < q)
782 {
783 c += q;
784 }
785 else
786 {
787 la = q;
788 }
789 if (switchLM[li] != 0)
790 {
791 mPS[ctxt] = 1 - mPS[ctxt];
792 }
793 I[ctxt] = nLPS[li];
794  
795 // -- Renormalization
796  
797 // sligthly better than normal loop
798 nc = 0;
799 do
800 {
801 la <<= 1;
802 nc++; // count number of necessary shifts
803 }
804 while (la < 0x8000);
805 if (cT > nc)
806 {
807 c <<= nc;
808 cT -= nc;
809 }
810 else
811 {
812 do
813 {
814 c <<= cT;
815 nc -= cT;
816 // cT = 0; // not necessary
817 byteOut();
818 }
819 while (cT <= nc);
820 c <<= nc;
821 cT -= nc;
822 }
823  
824 // -- End of renormalization
825 }
826 }
827 a = la; // save cached A register
828 }
829  
830  
831 /// <summary> This function performs the arithmetic encoding of one symbol. The
832 /// function receives a bit that is to be encoded and a context with which
833 /// to encode it.
834 ///
835 /// <p>Each context has a current MPS and an index describing what the
836 /// current probability is for the LPS. Each bit is encoded and if the
837 /// probability of the LPS exceeds .5, the MPS and LPS are switched.</p>
838 ///
839 /// </summary>
840 /// <param name="bit">The symbol to be encoded, must be 0 or 1.
841 ///
842 /// </param>
843 /// <param name="context">the context with which to encode the symbol.
844 ///
845 /// </param>
846 public void codeSymbol(int bit, int context)
847 {
848 int q;
849 int li; // local cache of I[context]
850 int la;
851 int n;
852  
853 // NOTE: (a < 0x8000) is equivalent to ((a & 0x8000)==0)
854 // since 'a' is always less than or equal to 0xFFFF
855  
856 // NOTE: conditional exchange guarantees that A for MPS is
857 // always greater than 0x4000 (i.e. 0.375)
858 // => one renormalization shift is enough for MPS
859 // => no need to do a renormalization while loop for MPS
860  
861 li = I[context];
862 q = qe[li]; // Retrieve current LPS prob.
863  
864 if (bit == mPS[context])
865 {
866 // -- Code MPS
867  
868 a -= q; // Interval division associated with MPS coding
869  
870 if (a >= 0x8000)
871 {
872 // Interval big enough
873 c += q;
874 }
875 else
876 {
877 // Interval too short
878 if (a < q)
879 {
880 // Probabilities are inverted
881 a = q;
882 }
883 else
884 {
885 c += q;
886 }
887  
888 I[context] = nMPS[li];
889  
890 // -- Renormalization (MPS: no need for while loop)
891 a <<= 1; // a is doubled
892 c <<= 1; // c is doubled
893 cT--;
894 if (cT == 0)
895 {
896 byteOut();
897 }
898 // -- End of renormalization
899 }
900 }
901 else
902 {
903 // -- Code LPS
904  
905 la = a; // cache A register in local variable
906 la -= q; // Interval division according to LPS coding
907  
908 if (la < q)
909 {
910 c += q;
911 }
912 else
913 {
914 la = q;
915 }
916 if (switchLM[li] != 0)
917 {
918 mPS[context] = 1 - mPS[context];
919 }
920 I[context] = nLPS[li];
921  
922 // -- Renormalization
923  
924 // sligthly better than normal loop
925 n = 0;
926 do
927 {
928 la <<= 1;
929 n++; // count number of necessary shifts
930 }
931 while (la < 0x8000);
932 if (cT > n)
933 {
934 c <<= n;
935 cT -= n;
936 }
937 else
938 {
939 do
940 {
941 c <<= cT;
942 n -= cT;
943 // cT = 0; // not necessary
944 byteOut();
945 }
946 while (cT <= n);
947 c <<= n;
948 cT -= n;
949 }
950  
951 // -- End of renormalization
952 a = la; // save cached A register
953 }
954 }
955  
956 /// <summary> This function puts one byte of compressed bits in the output stream.
957 /// The highest 8 bits of c are then put in b to be the next byte to
958 /// write. This method delays the output of any 0xFF bytes until a non 0xFF
959 /// byte has to be written to the output bit stream (the 'delFF' variable
960 /// signals if there is a delayed 0xff byte).
961 ///
962 /// </summary>
963 private void byteOut()
964 {
965 if (nrOfWrittenBytes >= 0)
966 {
967 if (b == 0xFF)
968 {
969 // Delay 0xFF byte
970 delFF = true;
971 b = SupportClass.URShift(c, 20);
972 c &= 0xFFFFF;
973 cT = 7;
974 }
975 else if (c < 0x8000000)
976 {
977 // Write delayed 0xFF bytes
978 if (delFF)
979 {
980 out_Renamed.write(0xFF);
981 delFF = false;
982 nrOfWrittenBytes++;
983 }
984 out_Renamed.write(b);
985 nrOfWrittenBytes++;
986 b = SupportClass.URShift(c, 19);
987 c &= 0x7FFFF;
988 cT = 8;
989 }
990 else
991 {
992 b++;
993 if (b == 0xFF)
994 {
995 // Delay 0xFF byte
996 delFF = true;
997 c &= 0x7FFFFFF;
998 b = SupportClass.URShift(c, 20);
999 c &= 0xFFFFF;
1000 cT = 7;
1001 }
1002 else
1003 {
1004 // Write delayed 0xFF bytes
1005 if (delFF)
1006 {
1007 out_Renamed.write(0xFF);
1008 delFF = false;
1009 nrOfWrittenBytes++;
1010 }
1011 out_Renamed.write(b);
1012 nrOfWrittenBytes++;
1013 b = ((SupportClass.URShift(c, 19)) & 0xFF);
1014 c &= 0x7FFFF;
1015 cT = 8;
1016 }
1017 }
1018 }
1019 else
1020 {
1021 // NOTE: carry bit can never be set if the byte buffer was empty
1022 b = (SupportClass.URShift(c, 19));
1023 c &= 0x7FFFF;
1024 cT = 8;
1025 nrOfWrittenBytes++;
1026 }
1027 }
1028  
1029 /// <summary> This function flushes the remaining encoded bits and makes sure that
1030 /// enough information is written to the bit stream to be able to finish
1031 /// decoding, and then it reinitializes the internal state of the MQ coder
1032 /// but without modifying the context states.
1033 ///
1034 /// <p>After calling this method the 'finishLengthCalculation()' method
1035 /// should be called, after compensating the returned length for the length
1036 /// of previous coded segments, so that the length calculation is
1037 /// finalized.</p>
1038 ///
1039 /// <p>The type of termination used depends on the one specified at the
1040 /// constructor.</p>
1041 ///
1042 /// </summary>
1043 /// <returns> The length of the arithmetic codeword after termination, in
1044 /// bytes.
1045 ///
1046 /// </returns>
1047 public virtual int terminate()
1048 {
1049 switch (ttype)
1050 {
1051  
1052 case TERM_FULL:
1053 //sets the remaining bits of the last byte of the coded bits.
1054 int tempc = c + a;
1055 c = c | 0xFFFF;
1056 if (c >= tempc)
1057 {
1058 c = c - 0x8000;
1059 }
1060  
1061 int remainingBits = 27 - cT;
1062  
1063 // Flushes remainingBits
1064 do
1065 {
1066 c <<= cT;
1067 if (b != 0xFF)
1068 {
1069 remainingBits -= 8;
1070 }
1071 else
1072 {
1073 remainingBits -= 7;
1074 }
1075 byteOut();
1076 }
1077 while (remainingBits > 0);
1078  
1079 b |= (1 << (- remainingBits)) - 1;
1080 if (b == 0xFF)
1081 {
1082 // Delay 0xFF bytes
1083 delFF = true;
1084 }
1085 else
1086 {
1087 // Write delayed 0xFF bytes
1088 if (delFF)
1089 {
1090 out_Renamed.write(0xFF);
1091 delFF = false;
1092 nrOfWrittenBytes++;
1093 }
1094 out_Renamed.write(b);
1095 nrOfWrittenBytes++;
1096 }
1097 break;
1098  
1099 case TERM_PRED_ER:
1100 case TERM_EASY:
1101 // The predictable error resilient and easy termination are the
1102 // same, except for the fact that the easy one can modify the
1103 // spare bits in the last byte to maximize the likelihood of
1104 // having a 0xFF, while the error resilient one can not touch
1105 // these bits.
1106  
1107 // In the predictable error resilient case the spare bits will be
1108 // recalculated by the decoder and it will check if they are the
1109 // same as as in the codestream and then deduce an error
1110 // probability from there.
1111  
1112 int k; // number of bits to push out
1113  
1114 k = (11 - cT) + 1;
1115  
1116 c <<= cT;
1117 for (; k > 0; k -= cT, c <<= cT)
1118 {
1119 byteOut();
1120 }
1121  
1122 // Make any spare bits 1s if in easy termination
1123 if (k < 0 && ttype == TERM_EASY)
1124 {
1125 // At this stage there is never a carry bit in C, so we can
1126 // freely modify the (-k) least significant bits.
1127 b |= (1 << (- k)) - 1;
1128 }
1129  
1130 byteOut(); // Push contents of byte buffer
1131 break;
1132  
1133 case TERM_NEAR_OPT:
1134  
1135 // This algorithm terminates in the shortest possible way, besides
1136 // the fact any previous 0xFF 0x7F sequences are not
1137 // eliminated. The probabalility of having those sequences is
1138 // extremely low.
1139  
1140 // The calculation of the length is based on the fact that the
1141 // decoder will pad the codestream with an endless string of
1142 // (binary) 1s. If the codestream, padded with 1s, is within the
1143 // bounds of the current interval then correct decoding is
1144 // guaranteed. The lower inclusive bound of the current interval
1145 // is the value of C (i.e. if only lower intervals would be coded
1146 // in the future). The upper exclusive bound of the current
1147 // interval is C+A (i.e. if only upper intervals would be coded in
1148 // the future). We therefore calculate the minimum length that
1149 // would be needed so that padding with 1s gives a codestream
1150 // within the interval.
1151  
1152 // In general, such a calculation needs the value of the next byte
1153 // that appears in the codestream. Here, since we are terminating,
1154 // the next value can be anything we want that lies within the
1155 // interval, we use the lower bound since this minimizes the
1156 // length. To calculate the necessary length at any other place
1157 // than the termination it is necessary to know the next bytes
1158 // that will appear in the codestream, which involves storing the
1159 // codestream and the sate of the MQCoder at various points (a
1160 // worst case approach can be used, but it is much more
1161 // complicated and the calculated length would be only marginally
1162 // better than much simple calculations, if not the same).
1163  
1164 int cLow;
1165 int cUp;
1166 int bLow;
1167 int bUp;
1168  
1169 // Initialize the upper (exclusive) and lower bound (inclusive) of
1170 // the valid interval (the actual interval is the concatenation of
1171 // bUp and cUp, and bLow and cLow).
1172 cLow = c;
1173 cUp = c + a;
1174 bLow = bUp = b;
1175  
1176 // We start by normalizing the C register to the sate cT = 0
1177 // (i.e., just before byteOut() is called)
1178 cLow <<= cT;
1179 cUp <<= cT;
1180 // Progate eventual carry bits and reset them in Clow, Cup NOTE:
1181 // carry bit can never be set if the byte buffer was empty so no
1182 // problem with propagating a carry into an empty byte buffer.
1183 if ((cLow & (1 << 27)) != 0)
1184 {
1185 // Carry bit in cLow
1186 if (bLow == 0xFF)
1187 {
1188 // We can not propagate carry bit, do bit stuffing
1189 delFF = true; // delay 0xFF
1190 // Get next byte buffer
1191 bLow = SupportClass.URShift(cLow, 20);
1192 bUp = SupportClass.URShift(cUp, 20);
1193 cLow &= 0xFFFFF;
1194 cUp &= 0xFFFFF;
1195 // Normalize to cT = 0
1196 cLow <<= 7;
1197 cUp <<= 7;
1198 }
1199 else
1200 {
1201 // we can propagate carry bit
1202 bLow++; // propagate
1203 cLow &= ~ (1 << 27); // reset carry in cLow
1204 }
1205 }
1206 if ((cUp & (1 << 27)) != 0)
1207 {
1208 bUp++; // propagate
1209 cUp &= ~ (1 << 27); // reset carry
1210 }
1211  
1212 // From now on there can never be a carry bit on cLow, since we
1213 // always output bLow.
1214  
1215 // Loop testing for the condition and doing byte output if they
1216 // are not met.
1217 while (true)
1218 {
1219 // If decoder's codestream is within interval stop
1220 // If preceding byte is 0xFF only values [0,127] are valid
1221 if (delFF)
1222 {
1223 // If delayed 0xFF
1224 if (bLow <= 127 && bUp > 127)
1225 break;
1226 // We will write more bytes so output delayed 0xFF now
1227 out_Renamed.write(0xFF);
1228 nrOfWrittenBytes++;
1229 delFF = false;
1230 }
1231 else
1232 {
1233 // No delayed 0xFF
1234 if (bLow <= 255 && bUp > 255)
1235 break;
1236 }
1237  
1238 // Output next byte
1239 // We could output anything within the interval, but using
1240 // bLow simplifies things a lot.
1241  
1242 // We should not have any carry bit here
1243  
1244 // Output bLow
1245 if (bLow < 255)
1246 {
1247 // Transfer byte bits from C to B
1248 // (if the byte buffer was empty output nothing)
1249 if (nrOfWrittenBytes >= 0)
1250 out_Renamed.write(bLow);
1251 nrOfWrittenBytes++;
1252 bUp -= bLow;
1253 bUp <<= 8;
1254 // Here bLow would be 0
1255 bUp |= (SupportClass.URShift(cUp, 19)) & 0xFF;
1256 bLow = (SupportClass.URShift(cLow, 19)) & 0xFF;
1257 // Clear upper bits (just pushed out) from cUp Clow.
1258 cLow &= 0x7FFFF;
1259 cUp &= 0x7FFFF;
1260 // Goto next state where CT is 0
1261 cLow <<= 8;
1262 cUp <<= 8;
1263 // Here there can be no carry on Cup, Clow
1264 }
1265 else
1266 {
1267 // bLow = 0xFF
1268 // Transfer byte bits from C to B
1269 // Since the byte to output is 0xFF we can delay it
1270 delFF = true;
1271 bUp -= bLow;
1272 bUp <<= 7;
1273 // Here bLow would be 0
1274 bUp |= (cUp >> 20) & 0x7F;
1275 bLow = (cLow >> 20) & 0x7F;
1276 // Clear upper bits (just pushed out) from cUp Clow.
1277 cLow &= 0xFFFFF;
1278 cUp &= 0xFFFFF;
1279 // Goto next state where CT is 0
1280 cLow <<= 7;
1281 cUp <<= 7;
1282 // Here there can be no carry on Cup, Clow
1283 }
1284 }
1285 break;
1286  
1287 default:
1288 throw new System.ApplicationException("Illegal termination type code");
1289  
1290 }
1291  
1292 // Reinitialize the state (without modifying the contexts)
1293 int len;
1294  
1295 len = nrOfWrittenBytes;
1296 a = 0x8000;
1297 c = 0;
1298 b = 0;
1299 cT = 12;
1300 delFF = false;
1301 nrOfWrittenBytes = - 1;
1302  
1303 // Return the terminated length
1304 return len;
1305 }
1306  
1307 /// <summary> Resets a context to the original probability distribution, and sets its
1308 /// more probable symbol to 0.
1309 ///
1310 /// </summary>
1311 /// <param name="c">The number of the context (it starts at 0).
1312 ///
1313 /// </param>
1314 public void resetCtxt(int c)
1315 {
1316 I[c] = initStates[c];
1317 mPS[c] = 0;
1318 }
1319  
1320 /// <summary> Resets all contexts to their original probability distribution and sets
1321 /// all more probable symbols to 0.
1322 ///
1323 /// </summary>
1324 public void resetCtxts()
1325 {
1326 Array.Copy(initStates, 0, I, 0, I.Length);
1327 ArrayUtil.intArraySet(mPS, 0);
1328 }
1329  
1330 /// <summary> Reinitializes the MQ coder and the underlying 'ByteOutputBuffer' buffer
1331 /// as if a new object was instantaited. All the data in the
1332 /// 'ByteOutputBuffer' buffer is erased and the state and contexts of the
1333 /// MQ coder are reinitialized). Additionally any saved MQ states are
1334 /// discarded.
1335 ///
1336 /// </summary>
1337 public void reset()
1338 {
1339  
1340 // Reset the output buffer
1341 out_Renamed.reset();
1342  
1343 a = 0x8000;
1344 c = 0;
1345 b = 0;
1346 if (b == 0xFF)
1347 cT = 13;
1348 else
1349 cT = 12;
1350 resetCtxts();
1351 nrOfWrittenBytes = - 1;
1352 delFF = false;
1353  
1354 nSaved = 0;
1355 }
1356  
1357 /// <summary> Saves the current state of the MQ coder (just the registers, not the
1358 /// contexts) so that a near optimal length calculation can be performed
1359 /// later.
1360 ///
1361 /// </summary>
1362 private void saveState()
1363 {
1364 // Increase capacity if necessary
1365 if (nSaved == savedC.Length)
1366 {
1367 System.Object tmp;
1368 tmp = savedC;
1369 savedC = new int[nSaved + SAVED_INC];
1370 // CONVERSION PROBLEM?
1371 Array.Copy((System.Array)tmp, 0, savedC, 0, nSaved);
1372 tmp = savedCT;
1373 savedCT = new int[nSaved + SAVED_INC];
1374 Array.Copy((System.Array)tmp, 0, savedCT, 0, nSaved);
1375 tmp = savedA;
1376 savedA = new int[nSaved + SAVED_INC];
1377 Array.Copy((System.Array)tmp, 0, savedA, 0, nSaved);
1378 tmp = savedB;
1379 savedB = new int[nSaved + SAVED_INC];
1380 Array.Copy((System.Array)tmp, 0, savedB, 0, nSaved);
1381 tmp = savedDelFF;
1382 savedDelFF = new bool[nSaved + SAVED_INC];
1383 Array.Copy((System.Array)tmp, 0, savedDelFF, 0, nSaved);
1384 }
1385 // Save the current sate
1386 savedC[nSaved] = c;
1387 savedCT[nSaved] = cT;
1388 savedA[nSaved] = a;
1389 savedB[nSaved] = b;
1390 savedDelFF[nSaved] = delFF;
1391 nSaved++;
1392 }
1393  
1394 /// <summary> Terminates the calculation of the required length for each coding
1395 /// pass. This method must be called just after the 'terminate()' one has
1396 /// been called for each terminated MQ segment.
1397 ///
1398 /// <p>The values in 'rates' must have been compensated for any offset due
1399 /// to previous terminated segments, so that the correct index to the
1400 /// stored coded data is used.</p>
1401 ///
1402 /// </summary>
1403 /// <param name="rates">The array containing the values returned by
1404 /// 'getNumCodedBytes()' for each coding pass.
1405 ///
1406 /// </param>
1407 /// <param name="n">The index in the 'rates' array of the last terminated length.
1408 ///
1409 /// </param>
1410 public virtual void finishLengthCalculation(int[] rates, int n)
1411 {
1412 if (ltype != LENGTH_NEAR_OPT)
1413 {
1414 // For the simple calculations the only thing we need to do is to
1415 // ensure that the calculated lengths are no greater than the
1416 // terminated one
1417 if (n > 0 && rates[n - 1] > rates[n])
1418 {
1419 // We need correction
1420 int tl = rates[n]; // The terminated length
1421 n--;
1422 do
1423 {
1424 rates[n--] = tl;
1425 }
1426 while (n >= 0 && rates[n] > tl);
1427 }
1428 }
1429 else
1430 {
1431 // We need to perform the more sophisticated near optimal
1432 // calculation.
1433  
1434 // The calculation of the length is based on the fact that the
1435 // decoder will pad the codestream with an endless string of
1436 // (binary) 1s after termination. If the codestream, padded with
1437 // 1s, is within the bounds of the current interval then correct
1438 // decoding is guaranteed. The lower inclusive bound of the
1439 // current interval is the value of C (i.e. if only lower
1440 // intervals would be coded in the future). The upper exclusive
1441 // bound of the current interval is C+A (i.e. if only upper
1442 // intervals would be coded in the future). We therefore calculate
1443 // the minimum length that would be needed so that padding with 1s
1444 // gives a codestream within the interval.
1445  
1446 // In order to know what will be appended to the current base of
1447 // the interval we need to know what is in the MQ bit stream after
1448 // the current last output byte until the termination. This is why
1449 // this calculation has to be performed after the MQ segment has
1450 // been entirely coded and terminated.
1451  
1452 int cLow; // lower bound on the C register for correct decoding
1453 int cUp; // upper bound on the C register for correct decoding
1454 int bLow; // lower bound on the byte buffer for correct decoding
1455 int bUp; // upper bound on the byte buffer for correct decoding
1456 int ridx; // index in the rates array of the pass we are
1457 // calculating
1458 int sidx; // index in the saved state array
1459 int clen; // current calculated length
1460 bool cdFF; // the current delayed FF state
1461 int nb; // the next byte of output
1462 int minlen; // minimum possible length
1463 int maxlen; // maximum possible length
1464  
1465 // Start on the first pass of this segment
1466 ridx = n - nSaved;
1467 // Minimum allowable length is length of previous termination
1468 minlen = (ridx - 1 >= 0)?rates[ridx - 1]:0;
1469 // Maximum possible length is the terminated length
1470 maxlen = rates[n];
1471 for (sidx = 0; ridx < n; ridx++, sidx++)
1472 {
1473 // Load the initial values of the bounds
1474 cLow = savedC[sidx];
1475 cUp = savedC[sidx] + savedA[sidx];
1476 bLow = savedB[sidx];
1477 bUp = savedB[sidx];
1478 // Normalize to cT=0 and propagate and reset any carry bits
1479 cLow <<= savedCT[sidx];
1480 if ((cLow & 0x8000000) != 0)
1481 {
1482 bLow++;
1483 cLow &= 0x7FFFFFF;
1484 }
1485 cUp <<= savedCT[sidx];
1486 if ((cUp & 0x8000000) != 0)
1487 {
1488 bUp++;
1489 cUp &= 0x7FFFFFF;
1490 }
1491 // Initialize current calculated length
1492 cdFF = savedDelFF[sidx];
1493 // rates[ridx] contains the number of bytes already output
1494 // when the state was saved, compensated for the offset in the
1495 // output stream.
1496 clen = rates[ridx] + (cdFF?1:0);
1497 while (true)
1498 {
1499 // If we are at end of coded data then this is the length
1500 if (clen >= maxlen)
1501 {
1502 clen = maxlen;
1503 break;
1504 }
1505 // Check for sufficiency of coded data
1506 if (cdFF)
1507 {
1508 if (bLow < 128 && bUp >= 128)
1509 {
1510 // We are done for this pass
1511 clen--; // Don't need delayed FF
1512 break;
1513 }
1514 }
1515 else
1516 {
1517 if (bLow < 256 && bUp >= 256)
1518 {
1519 // We are done for this pass
1520 break;
1521 }
1522 }
1523 // Update bounds with next byte of coded data and
1524 // normalize to cT = 0 again.
1525 nb = (clen >= minlen)?out_Renamed.getByte(clen):0;
1526 bLow -= nb;
1527 bUp -= nb;
1528 clen++;
1529 if (nb == 0xFF)
1530 {
1531 bLow <<= 7;
1532 bLow |= (cLow >> 20) & 0x7F;
1533 cLow &= 0xFFFFF;
1534 cLow <<= 7;
1535 bUp <<= 7;
1536 bUp |= (cUp >> 20) & 0x7F;
1537 cUp &= 0xFFFFF;
1538 cUp <<= 7;
1539 cdFF = true;
1540 }
1541 else
1542 {
1543 bLow <<= 8;
1544 bLow |= (cLow >> 19) & 0xFF;
1545 cLow &= 0x7FFFF;
1546 cLow <<= 8;
1547 bUp <<= 8;
1548 bUp |= (cUp >> 19) & 0xFF;
1549 cUp &= 0x7FFFF;
1550 cUp <<= 8;
1551 cdFF = false;
1552 }
1553 // Test again
1554 }
1555 // Store the rate found
1556 rates[ridx] = (clen >= minlen)?clen:minlen;
1557 }
1558 // Reset the saved states
1559 nSaved = 0;
1560 }
1561 }
1562 }
1563 }