001 /**
002 * Copyright (C) 2013 - Francesc Auli-Llinas
003 *
004 * This program is distributed under the BOI License.
005 * This program is distributed in the hope that it will be useful, but without any
006 * warranty; without even the implied warranty of merchantability or fitness for a particular purpose.
007 * You should have received a copy of the BOI License along with this program. If not,
008 * see <http://www.deic.uab.cat/~francesc/software/license/>.
009 */
010 package coders;
011
012 import streams.ByteStream;
013
014
015 /**
016 * This class implements an arithmetic coder. The underlying coding scheme is based on the
017 * arithmetic coder MQ defined in the JPEG2000 standard (see the <code>ArithmeticCoderMQ</code> class
018 * for more details). This class can perform both the operations of the encoder and the decoder.<br>
019 *
020 * Usage: once the object is created, the functions to code/decode symbols are used to code the
021 * message. Instead of destroying the object and creating another one to encode a new message, it
022 * is more computationally efficient to reuse the same object. When encoding, the same object can be
023 * reused by calling the functions <code>terminate</code>, get the stream wherever is needed,
024 * <code>changeStream</code>, <code>restartEncoding</code> and <code>reset</code> in this order.
025 * To reuse the decoder, the functions <code>changeStream</code>, <code>restartDecoding</code>, and
026 * <code>reset</code> have to be called in this order.<br>
027 *
028 * Multithreading support: the object must be created and manipulated by a single thread. There
029 * can be many objects of this class running simultaneously as long as a single thread manipulates
030 * each object.<br>
031 *
032 * @author Francesc Auli-Llinas
033 * @version 1.0
034 */
035 public final class ArithmeticCoder{
036
037 /**
038 * ByteStream employed by the coder to write/read the output/input bytes.
039 * <p>
040 * The stream may contain zero bytes.
041 */
042 private ByteStream stream;
043
044 /**
045 * Interval range.
046 * <p>
047 * From right to left: 8 register bits, 3 spacer bits, 8 partial code bits, and 1 carry bit.
048 */
049 private int A;
050
051 /**
052 * Lower down interval.
053 * <p>
054 * From right to left: 8 register bits, 3 spacer bits, 8 partial code bits, and 1 carry bit.
055 */
056 private int C;
057
058 /**
059 * Number of bits to transfer.
060 * <p>
061 * It is set to 8 except when carry situations occur, in which is set to 7.
062 */
063 private int t;
064
065 /**
066 * Byte to flush out/read.
067 * <p>
068 * Flushed byte to the stream.
069 */
070 private int Tr;
071
072 /**
073 * Current byte read/write.
074 * <p>
075 * Current position in the stream.
076 */
077 private int L;
078
079 /**
080 * Number of contexts.
081 * <p>
082 * Set when the class is instantiated.
083 */
084 private int numContexts = -1;
085
086 /**
087 * Current state of the context.
088 * <p>
089 * Must in the range [0, STATE_TRANSITIONS_MPS.length - 1]
090 */
091 private int[] contextState = null;
092
093 /**
094 * Most probable symbol of the Context.
095 * <p>
096 * Either 0 or 1.
097 */
098 private int[] contextMPS = null;
099
100 /**
101 * Transition to the next state when coding the most probable symbol.
102 * <p>
103 * Each index must in the range [0, STATE_TRANSITIONS_MPS.length - 1]
104 */
105 private static final int[] STATE_TRANSITIONS_MPS = {1, 2, 3, 4, 5, 38, 7, 8, 9, 10,
106 11, 12, 13, 29, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
107 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 45, 46};
108
109 /**
110 * Transition to the next state when coding the least probable symbol.
111 * <p>
112 * Each index must in the range [0, STATE_TRANSITIONS_MPS.length - 1]
113 */
114 private static final int[] STATE_TRANSITIONS_LPS = {1, 6, 9, 12, 29, 33, 6, 14, 14,
115 14, 17, 18, 20, 21, 14, 14, 15, 16, 17, 18, 19, 19, 20, 21, 22, 23, 24, 25, 26,
116 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 46};
117
118 /**
119 * Most probable symbol change.
120 * <p>
121 * 1 indicates a change of the MPS.
122 */
123 private static final int[] STATE_CHANGE = {1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0,
124 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,
125 0, 0, 0, 0, 0, 0, 0, 0};
126
127 /**
128 * Probability of the context.
129 * <p>
130 * The real probability can be computed as the coded probability expressed in this array 0xXXXX / (2^16 * \alpha), with \alpha = 0.708.
131 */
132 private static final int[] STATE_PROB = {0x5601, 0x3401, 0x1801, 0x0AC1, 0x0521,
133 0x0221, 0x5601, 0x5401, 0x4801, 0x3801, 0x3001, 0x2401, 0x1C01, 0x1601, 0x5601,
134 0x5401, 0x5101, 0x4801, 0x3801, 0x3401, 0x3001, 0x2801, 0x2401, 0x2201, 0x1C01,
135 0x1801, 0x1601, 0x1401, 0x1201, 0x1101, 0x0AC1, 0x09C1, 0x08A1, 0x0521, 0x0441,
136 0x02A1, 0x0221, 0x0141, 0x0111, 0x0085, 0x0049, 0x0025, 0x0015, 0x0009, 0x0005,
137 0x0001, 0x5601};
138
139 /**
140 * Bit masks (employed when coding integers).
141 * <p>
142 * The position in the array indicates the bit for which the mask is computed.
143 */
144 protected static final int[] BIT_MASKS = {1, 1 << 1, 1 << 2, 1 << 3, 1 << 4, 1 << 5,
145 1 << 6, 1 << 7, 1 << 8, 1 << 9, 1 << 10, 1 << 11, 1 << 12, 1 << 13, 1 << 14, 1 << 15,
146 1 << 16, 1 << 17, 1 << 18, 1 << 19, 1 << 20, 1 << 21, 1 << 22, 1 << 23, 1 << 24,
147 1 << 25, 1 << 26, 1 << 27, 1 << 28, 1 << 29, 1 << 30};
148
149
150 /**
151 * Initializes internal registers. Before using the coder, a stream has to be set
152 * through <code>changeStream</code>.
153 */
154 public ArithmeticCoder(){
155 reset();
156 restartEncoding();
157 }
158
159 /**
160 * Initializes internal registers and creates the number of contexts specified. Before
161 * using the coder, a stream has to be set through <code>changeStream</code>.
162 *
163 * @param numContexts number of contexts available for this object
164 */
165 public ArithmeticCoder(int numContexts){
166 this.numContexts = numContexts;
167 contextState = new int[numContexts];
168 contextMPS = new int[numContexts];
169 reset();
170 restartEncoding();
171 }
172
173 /**
174 * Encodes a bit using a context so that the probabilities are adaptively adjusted
175 * depending on the incoming symbols.
176 *
177 * @param bit input
178 * @param context context of the symbol
179 */
180 public void encodeBitContext(boolean bit, int context){
181 int x = bit ? 1 : 0;
182 int s = contextMPS[context];
183 int p = STATE_PROB[contextState[context]];
184
185 A -= p;
186 if(x == s){ //Codes the most probable symbol
187 if(A >= (1 << 15)){
188 C += p;
189 }else{
190 if(A < p){
191 A = p;
192 }else{
193 C += p;
194 }
195 contextState[context] = STATE_TRANSITIONS_MPS[contextState[context]];
196 while(A < (1 << 15)){
197 A <<= 1;
198 C <<= 1;
199 t--;
200 if(t == 0){
201 transferByte();
202 }
203 }
204 }
205 }else{ //Codes the least probable symbol
206 if(A < p){
207 C += p;
208 }else{
209 A = p;
210 }
211 if(STATE_CHANGE[contextState[context]] == 1){
212 contextMPS[context] = contextMPS[context] == 0 ? 1: 0; //Switches MPS/LPS if necessary
213 }
214 contextState[context] = STATE_TRANSITIONS_LPS[contextState[context]];
215 while(A < (1 << 15)){
216 A <<= 1;
217 C <<= 1;
218 t--;
219 if(t == 0){
220 transferByte();
221 }
222 }
223 }
224 }
225
226 /**
227 * Decodes a bit using a context so that the probabilities are adaptively adjusted
228 * depending on the outcoming symbols.
229 *
230 * @param context context of the symbols
231 * @return output bit
232 * @throws Exception when some problem manipulating the stream occurs
233 */
234 public boolean decodeBitContext(int context) throws Exception{
235 int p = STATE_PROB[contextState[context]];
236 int s = contextMPS[context];
237 int x = s;
238
239 A -= p;
240 if((C & 0x00FFFF00) >= (p << 8)){
241 C = ((C & ~0xFFFFFF00) | ((C & 0x00FFFF00) - (p << 8)));
242 if(A < (1 << 15)){
243 if(A < p){
244 x = 1 - s;
245 if(STATE_CHANGE[contextState[context]] == 1){
246 contextMPS[context] = contextMPS[context] == 0 ? 1: 0; //Switches MPS/LPS if necessary
247 }
248 contextState[context] = STATE_TRANSITIONS_LPS[contextState[context]];
249 }else{
250 contextState[context] = STATE_TRANSITIONS_MPS[contextState[context]];
251 }
252 while(A < (1 << 15)){
253 if(t == 0){
254 fillLSB();
255 }
256 A <<= 1;
257 C <<= 1;
258 t--;
259 }
260 }
261 }else{
262 if(A < p){
263 contextState[context] = STATE_TRANSITIONS_MPS[contextState[context]];
264 }else{
265 x = 1 - s;
266 if(STATE_CHANGE[contextState[context]] == 1){
267 contextMPS[context] = contextMPS[context] == 0 ? 1: 0; //Switches MPS/LPS if necessary
268 }
269 contextState[context] = STATE_TRANSITIONS_LPS[contextState[context]];
270 }
271 A = p;
272 while(A < (1 << 15)){
273 if(t == 0){
274 fillLSB();
275 }
276 A <<= 1;
277 C <<= 1;
278 t--;
279 }
280 }
281 return(x == 1);
282 }
283
284 /**
285 * Encodes a bit using a specified probability.
286 *
287 * @param bit input
288 * @param prob0 through this parameter, the probability of the symbol to be 0 can be set.
289 * Let the real probability of the symbol to be 0 be denoted as P. Then, if P >= 0.5, prob0 is
290 * computed as prob0 = ((1f - P) * ((4f / 3f) * (float) 0x8000)), otherwise
291 * prob0 = - (P * ((4f / 3f) * (float) 0x8000)). Make sure that P = [0.0001f ,0.9999f].
292 * This operation is not carried out in the function to alleviate computational costs. See
293 * the function {@link #prob0ToMQ} and {@link #MQToProb0}.
294 */
295 public void encodeBitProb(boolean bit, int prob0){
296 int x = bit ? 1 : 0;
297 int p;
298 int s = 0;
299 if(prob0 >= 0){
300 p = prob0;
301 }else{
302 p = -prob0;
303 s = 1;
304 }
305
306 A -= p;
307 if(x == s){ //Codes the most probable symbol
308 if(A >= (1 << 15)){
309 C += p;
310 }else{
311 if(A < p){
312 A = p;
313 }else{
314 C += p;
315 }
316 while(A < (1 << 15)){
317 A <<= 1;
318 C <<= 1;
319 t--;
320 if(t == 0){
321 transferByte();
322 }
323 }
324 }
325 }else{ //Codes the least probable symbol
326 if(A < p){
327 C += p;
328 }else{
329 A = p;
330 }
331 while(A < (1 << 15)){
332 A <<= 1;
333 C <<= 1;
334 t--;
335 if(t == 0){
336 transferByte();
337 }
338 }
339 }
340 }
341
342 /**
343 * Decodes a bit using a specified probability.
344 *
345 * @param prob0 through this parameter, the probability of the symbol to be 0 can be
346 * set. Let the real probability of the symbol to be 0 be denoted as P. Then, if
347 * P >= 0.5, prob0 is computed as prob0 = ((1f - P) * ((4f / 3f) * (float) 0x8000)),
348 * otherwise prob0 = - (P * ((4f / 3f) * (float) 0x8000)). Make sure that P = [0.0001f ,0.9999f].
349 * This operation is not carried out in the function to alleviate computational costs. See the
350 * function {@link #prob0ToMQ} and {@link #MQToProb0}.
351 *
352 * @return output bit
353 * @throws Exception when some problem manipulating the stream occurs
354 */
355 public boolean decodeBitProb(int prob0) throws Exception{
356 int p;
357 int s = 0;
358 if(prob0 >= 0){
359 p = prob0;
360 }else{
361 p = -prob0;
362 s = 1;
363 }
364 int x = s;
365
366 A -= p;
367 if((C & 0x00FFFF00) >= (p << 8)){
368 C = ((C & ~0xFFFFFF00) | ((C & 0x00FFFF00) - (p << 8)));
369 if(A < (1 << 15)){
370 if(A < p){
371 x = 1 - s;
372 }
373 while(A < (1 << 15)){
374 if(t == 0){
375 fillLSB();
376 }
377 A <<= 1;
378 C <<= 1;
379 t--;
380 }
381 }
382 }else{
383 if(A >= p){
384 x = 1 - s;
385 }
386 A = p;
387 while(A < (1 << 15)){
388 if(t == 0){
389 fillLSB();
390 }
391 A <<= 1;
392 C <<= 1;
393 t--;
394 }
395 }
396 return(x == 1);
397 }
398
399 /**
400 * Transforms the probability of the symbol 0 (or false) in the range [0:1] into
401 * the integer required in the MQ coder to represent that probability.
402 *
403 * @param prob0 in the range [0:1]
404 * @return integer that can be feed to the MQ coder
405 */
406 public static int prob0ToMQ(float prob0){
407 int prob0MQ;
408 if(prob0 >= 0.5f){
409 prob0 = prob0 > 0.9999f ? 0.9999f: prob0;
410 prob0MQ = (int) ((1f - prob0) * ((4f / 3f) * (float) 0x8000));
411 }else{
412 prob0 = prob0 < 0.0001f ? 0.0001f: prob0;
413 prob0MQ = (int) -(prob0 * ((4f / 3f) * (float) 0x8000));
414 }
415 return(prob0MQ);
416 }
417
418 /**
419 * Transforms the MQ integer to the probability of the symbol 0 (or false) in
420 * the range [0:1].
421 *
422 * @param probMQ integer feed to the MQ coder
423 * @return prob0 in the range [0:1]
424 */
425 public static float MQToProb0(int probMQ){
426 float prob0 = (3f * (float) probMQ) / (4f * (float) 0x8000);
427 if(probMQ > 0){
428 prob0 = 1 - prob0;
429 }else{
430 prob0 = -prob0;
431 }
432 return(prob0);
433 }
434
435 /**
436 * Transfers a byte to the stream (for encoding purposes).
437 */
438 private void transferByte(){
439 if(Tr == 0xFF){ //Bit stuff
440 stream.putByte((byte) Tr);
441 L++;
442 Tr = (C >>> 20); //Puts C_msbs to Tr
443 C &= (~0xFFF00000); //Puts 0 to C_msbs
444 t = 7;
445 }else{
446 if(C >= 0x08000000){
447 //Propagates any carry bit from C into Tr
448 Tr += 0x01;
449 C &= (~0xF8000000); //Resets the carry bit
450 }
451 if(L >= 0){
452 stream.putByte((byte) Tr);
453 }
454 L++;
455 if(Tr == 0xFF){ //Bit stuff
456 //Although it may not be a bit carry
457 Tr = (C >>> 20); //Puts C_msbs to Tr
458 C &= (~0xFFF00000); //Puts 0 to C_msbs
459 t = 7;
460 }else{
461 Tr = (C >>> 19); //Puts C_partial to Tr
462 C &= (~0xFFF80000); //Puts 0 to C_partial
463 t = 8;
464 }
465 }
466 }
467
468 /**
469 * Fills the C register with a byte from the stream or with 0xFF when the end of
470 * the stream is reached (for decoding purposes).
471 *
472 * @throws Exception when some problem manipulating the stream occurs
473 */
474 private void fillLSB() throws Exception{
475 byte BL = 0;
476 t = 8;
477 if(L < stream.getLength()){
478 BL = stream.getByte(L);
479 }
480 //Reached the end of the stream
481 if((L == stream.getLength()) || ((Tr == 0xFF) && (BL > 0x8F))){
482 C += 0xFF;
483 if(L != stream.getLength()){
484 throw new Exception("Read marker 0xFF in the stream.");
485 }
486 }else{
487 if(Tr == 0xFF){
488 t = 7;
489 }
490 Tr = (0x000000FF & (int) BL);
491 L++;
492 C += (Tr << (8 - t));
493 }
494 }
495
496 /**
497 * Changes the current stream. When encoding, before calling this function the stream
498 * should be terminated calling the <code>terminate</code> function, and after calling
499 * this function the functions <code>restartEncoding</code> and <code>reset</code> must
500 * be called. When decoding, after calling this function the functions <code>restartDecoding</code>
501 * and <code>reset</code> must be called.
502 *
503 * @param stream the new ByteStream
504 */
505 public void changeStream(ByteStream stream){
506 if(stream == null){
507 stream = new ByteStream();
508 }
509 this.stream = stream;
510 }
511
512 /**
513 * Resets the state of all contexts.
514 */
515 public void reset(){
516 for(int c = 0; c < numContexts; c++){
517 contextState[c] = 0;
518 contextMPS[c] = 0;
519 }
520 }
521
522 /**
523 * Restarts the internal registers of the coder for encoding.
524 */
525 public void restartEncoding(){
526 A = 0x8000;
527 C = 0;
528 t = 12;
529 Tr = 0;
530 L = -1;
531 }
532
533 /**
534 * Restarts the internal registers of the coder for decoding.
535 *
536 * @throws Exception when some problem manipulating the stream occurs
537 */
538 public void restartDecoding() throws Exception{
539 Tr = 0;
540 L = 0;
541 C = 0;
542 fillLSB();
543 C <<= t;
544 fillLSB();
545 C <<= 7;
546 t -= 7;
547 A = 0x8000;
548 }
549
550 /**
551 * Computes the number of bytes belonging to the currently encoded data needed to flush
552 * the internal registers (for encoding purposes). This function is useful to determine
553 * potential truncation points of the stream.
554 *
555 * @return number of bytes
556 */
557 public int remainingBytes(){
558 if(27 - t <= 22){
559 return(4);
560 }else{
561 return(5);
562 }
563 }
564
565 /**
566 * Terminates the current stream using the optimal termination (for encoding purposes).
567 *
568 * @throws Exception when some problem manipulating the stream occurs
569 */
570 public void terminate() throws Exception{
571 terminateOptimal();
572 }
573
574 /**
575 * Gets the number of bytes read or written to the stream associated to the coder.
576 *
577 * @return the number of bytes
578 */
579 public int getReadBytes(){
580 return(L);
581 }
582
583 /**
584 * Terminates the current stream using the easy termination (for encoding purposes).
585 */
586 public void terminateEasy(){
587 int nBits = 27 - 15 - t;
588 C <<= t;
589 while(nBits > 0){
590 transferByte();
591 nBits -= t;
592 C <<= t;
593 }
594 transferByte();
595 if(t == 7){
596 stream.removeByte();
597 }
598 }
599
600 /**
601 * Terminates the current stream using the optimal termination (for encoding purposes).
602 *
603 * @throws Exception when some problem manipulating the stream occurs
604 */
605 public void terminateOptimal() throws Exception{
606 int NZTr = Tr;
607 int NZt = t;
608 int NZC = C;
609 int NZA = A;
610 int NZL = L;
611
612 int lengthEmptyTermination = (int) stream.getLength();
613 terminateEasy();
614 int necessaryBytes = minFlush(NZTr, NZt, NZC, NZA, NZL, lengthEmptyTermination);
615 int lengthOptimalTermination = lengthEmptyTermination + necessaryBytes;
616
617 if((lengthOptimalTermination >= 1) && ((stream.getByte(lengthOptimalTermination - 1) == 0xFF))){
618 lengthOptimalTermination--;
619 }
620 boolean elimination;
621 do{
622 elimination = false;
623 if((lengthOptimalTermination >= 2) &&
624 ((stream.getByte(lengthOptimalTermination - 2) == 0xFF) &&
625 (stream.getByte(lengthOptimalTermination - 1) == 0x7F))){
626 lengthOptimalTermination -= 2;
627 elimination = true;
628 }
629 }while(elimination);
630 stream.removeBytes((int) stream.getLength() - lengthOptimalTermination);
631 }
632
633 /**
634 * Determines the minimum number of bytes needed to terminate the stream while assuring a
635 * complete recovering.
636 *
637 * @param NZTr Tr register for the normalization
638 * @param NZt t register for the normalization
639 * @param NZC C register for the normalization
640 * @param NZA A register for the normalization
641 * @param NZL number of flushed bytes
642 * @param lengthEmptyTermination length bytes used by the easy termination
643 * @return the number of bytes that should be flushed to terminate the ByteStream optimally
644 *
645 * @throws Exception when some problem manipulating the stream occurs
646 */
647 private int minFlush(int NZTr, int NZt, int NZC, int NZA, int NZL, int lengthEmptyTermination) throws Exception{
648 long Cr = ((long) NZTr << 27) + ((long) NZC << NZt);
649 long Ar = (long) NZA << NZt;
650 long Rf = 0;
651 int s = 8;
652 int Sf = 35;
653
654 int necessaryBytes = 0;
655 int maxNecessaryBytes = 5;
656 int cutZone = (int) stream.getLength() - lengthEmptyTermination;
657 if(maxNecessaryBytes > cutZone){
658 maxNecessaryBytes = cutZone;
659 }
660 if((lengthEmptyTermination == 0) && (((Cr >> 32) & 0xFF) == 0x00) && (NZL == -1)){
661 Cr <<= 8;
662 Ar <<= 8;
663 }
664 while((necessaryBytes < maxNecessaryBytes)
665 && ((Rf + ((long) 1 << Sf) - 1 < Cr)
666 || (Rf + ((long) 1 << Sf) - 1 >= Cr + Ar))){
667 necessaryBytes++;
668 if(necessaryBytes <= 4){
669 Sf -= s;
670 long b = stream.getByte(lengthEmptyTermination + necessaryBytes - 1);
671 if(b < 0){
672 b += 256;
673 }
674 Rf += b << Sf;
675 if(b == 0xFF){
676 s = 7;
677 }else{
678 s = 8;
679 }
680 }
681 }
682 return(necessaryBytes);
683 }
684 }
|