corrade-vassal – Blame information for rev 1
?pathlinks?
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 | } |