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 warranty; without
006 * 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 with 2 codewords of fixed length to increase
017 * efficiency. This class can perform both the operations of the encoder and the decoder.
018 * The constructor of the class permits the use of codewords with different lengths, and
019 * the use of probabilities with different precision. It also permits the use of
020 * context-adaptive coding. As the MQ coder, this coder stuffs one 0 bit after a byte
021 * equal to 0xFF.<br>
022 *
023 * Usage: once the object is created, the functions to code/decode symbols are used to code
024 * the message. Instead of destroying the object and creating another one to encode a new
025 * message, it is more computationally efficient to reuse the same object. When encoding,
026 * the same object can be reused by calling the functions <code>terminate</code>, get the stream
027 * wherever is needed, <code>changeStream</code>, <code>restartEncoding</code> and <code>reset</code>
028 * in this order. To reuse the decoder, the functions <code>changeStream</code>,
029 * <code>restartDecoding</code>, and <code>reset</code> have to be called in this order.<br>
030 *
031 * Multithreading support: the object must be created and manipulated by a single thread.
032 * There can be many objects of this class running simultaneously as long as a single thread
033 * manipulates each object.<br>
034 *
035 * @author Francesc Auli-Llinas
036 * @version 1.1
037 */
038 public final class ArithmeticCoderFL2W{
039
040 /**
041 * Minimum size of the interval at which the percentage of TOLERANCE begins to apply.
042 * <p>
043 * Must be greater than 2 and smaller than 2^codewordLength - 1.
044 */
045 private static final int MIN_SIZE = 16;
046
047 /**
048 * Percentage of tolerance between the real probability of the symbol coded and the
049 * probability given by the current interval.
050 * <p>
051 * Must be greater than 0 and smaller than 0.5.
052 */
053 private static final float TOLERANCE = 0.05f;
054
055 /**
056 * Indicates the number of symbols coded before updating the context probability.
057 * <p>
058 * Must be 2^X - 1.
059 */
060 private static final int UPDATE_PROB0 = 7;
061
062 /**
063 * Indicates the number of symbols appeared more recently that are taken into account to
064 * compute the probability of the context.
065 * <p>
066 * Must be 2^X - 1.
067 */
068 private static final int WINDOW_PROB = 127;
069
070 /**
071 * ByteStream employed by the coder to write/read the output/input bytes.
072 * <p>
073 * The stream may contain zero bytes.
074 */
075 private ByteStream stream;
076
077 /**
078 * Length of the codeword encoded. It can be changed by the constructor.
079 * <p>
080 * If must be greater than 0 and shorter than 60.
081 */
082 private int codewordLength = 32;
083
084 /**
085 * Number of bits to represent the probability employed to code the symbols. Note that to
086 * use fewer bits than the codewordLength may decrease compression efficiency for very
087 * high/low probabilities (to use more bits is inconsequential). It can be changed by the
088 * constructor.
089 * <p>
090 * If must be greater than 0 and smaller than 64. Be aware that codewordLength + precisionBits < 64.
091 */
092 private int precisionBits = 15;
093
094 /**
095 * Maximum allowed value of the codeword.
096 * <p>
097 * It is 2^codewordLength - 1, and is computed by the constructor of the class.
098 */
099 private long codewordMax = -1;
100
101 /**
102 * Number of complete bytes of the codeword.
103 * <p>
104 * It is ceil(codewordLength / 8), and is computed by the constructor of the class.
105 */
106 private int codeword2Bytes = -1;
107
108 /**
109 * Probability 0.5 using the precision bits of the class.
110 * <p>
111 * It is 2^(precisionBits - 1), and is computed by the constructor of the class.
112 */
113 private int precisionMid = -1;
114
115 /**
116 * Tolerance stored in the internal representation of the probabilities.
117 * <p>
118 * It is prob0ToFL2W(TOLERANCE, precisionBits), and is computed by the constructor of the class.
119 */
120 private long tolerance = -1;
121
122 /**
123 * Minimum value of the intervals.
124 * <p>
125 * Must be greater than 0 and smaller than 2^codewordLength - 1. Each index of the array
126 * correspond to one of the codewords being coded.
127 */
128 private long[] intervalMin = {-1, -1};
129
130 /**
131 * Size of the interval - 1.
132 * <p>
133 * Must be greater than 0 and equal or smaller than 2^codewordLength - 1. Each index of the
134 * array correspond to one of the codewords being coded.
135 */
136 private long[] intervalSize = {-1, -1};
137
138 /**
139 * Number within the interval stored in the codeword.
140 * <p>
141 * Must be equal or greater than intervalMin and equal or smaller than
142 * intervalMin + intervalSize. Each index of the array correspond to one of the codewords
143 * being coded.
144 */
145 private long[] interval = {-1, -1};
146
147 /**
148 * Byte to flush out/read.
149 * <p>
150 * Flushed byte to the stream.
151 */
152 private int Tr = -1;
153
154 /**
155 * Number of bits to transfer.
156 * <p>
157 * It is useful when the codewordLength does not correspond to a fixed number of bytes.
158 */
159 private int t = -1;
160
161 /**
162 * Current byte read/write.
163 * <p>
164 * Current position in the stream.
165 */
166 private int L;
167
168 /**
169 * Forcing one codeword to finish.
170 * <p>
171 * -1 indicates that no codeword is forced to finish, 0 and 1 indicate the index of the
172 * codeword that is forced to finish
173 */
174 private int forcingWord = -1;
175
176 /**
177 * Number of contexts.
178 * <p>
179 * Set when the class is instantiated.
180 */
181 private int numContexts = -1;
182
183 /**
184 * Current probability of each context.
185 * <p>
186 * Each index corresponds to one context. The probability is computed via {@link #prob0ToFLW}.
187 */
188 private int[] contextProb0FL2W = null;
189
190 /**
191 * Number of 0s coded in this context.
192 * <p>
193 * It is initialized to 0 in the <code>reset</code> function.
194 */
195 private int[] context0s = null;
196
197 /**
198 * Number of 0s coded in the last WINDOW_PROB symbols coded.
199 * <p>
200 * It is initialized to 0 in the <code>reset</code> function.
201 */
202 private int[] context0sWindow = null;
203
204 /**
205 * Total number of symbols coded in this context.
206 * <p>
207 * It is initialized to 0 in the <code>reset</code> function.
208 */
209 private int[] contextTotal = null;
210
211 /**
212 * Indicates whether the function <code>fillInterval</code> fills the interval with
213 * zeroes when no more bytes are in the stream.
214 * <p>
215 * True indicates that replenishment with 0s is activated.
216 */
217 private boolean replenishment = true;
218
219 /**
220 * Masks employed when transferring the bits of the interval to the stream.
221 * <p>
222 * The position in the array indicates the number of least significant bits for which
223 * the mask is computed.
224 */
225 private static final long[] BIT_MASKS = {0x0, 0x01, 0x03, 0x07, 0x0F, 0x1F, 0x3F, 0x7F, 0xFF};
226
227
228 /**
229 * Initializes internal registers. Before using the coder, a stream has to be
230 * set through <code>changeStream</code>.
231 */
232 public ArithmeticCoderFL2W(){
233 assert(codewordLength > 0);
234 assert(precisionBits > 0);
235 assert(codewordLength + precisionBits < 64);
236
237 codewordMax = ((long) 1 << codewordLength) - 1;
238 codeword2Bytes = (int) Math.ceil((float) codewordLength / 8f) * 2;
239 precisionMid = 1 << (precisionBits - 1);
240 tolerance = prob0ToFL2W(TOLERANCE, precisionBits);
241 restartEncoding();
242 }
243
244 /**
245 * Initializes internal registers. Before using the coder, a stream has to be
246 * set through <code>changeStream</code>.
247 *
248 * @param codewordLength number of bits of the codeword
249 */
250 public ArithmeticCoderFL2W(int codewordLength){
251 this.codewordLength = codewordLength;
252
253 assert(codewordLength > 0);
254 assert(precisionBits > 0);
255 assert(codewordLength + precisionBits < 64);
256
257 codewordMax = ((long) 1 << codewordLength) - 1;
258 codeword2Bytes = (int) Math.ceil((float) codewordLength / 8f) * 2;
259 precisionMid = 1 << (precisionBits - 1);
260 tolerance = prob0ToFL2W(TOLERANCE, precisionBits);
261 restartEncoding();
262 }
263
264 /**
265 * Initializes internal registers. Before using the coder, a stream has to be
266 * set through <code>changeStream</code>.
267 *
268 * @param codewordLength number of bits of the codeword
269 * @param precisionBits number of bits employed in the probabilities
270 */
271 public ArithmeticCoderFL2W(int codewordLength, int precisionBits){
272 this.codewordLength = codewordLength;
273 this.precisionBits = precisionBits;
274
275 assert(codewordLength > 0);
276 assert(precisionBits > 0);
277 assert(codewordLength + precisionBits < 64);
278
279 codewordMax = ((long) 1 << codewordLength) - 1;
280 codeword2Bytes = (int) Math.ceil((float) codewordLength / 8f) * 2;
281 precisionMid = 1 << (precisionBits - 1);
282 tolerance = prob0ToFL2W(TOLERANCE, precisionBits);
283 restartEncoding();
284 }
285
286 /**
287 * Initializes internal registers. Before using the coder, a stream has to be
288 * set through <code>changeStream</code>.
289 *
290 * @param codewordLength number of bits of the codeword
291 * @param precisionBits number of bits employed in the probabilities
292 * @param numContexts number of contexts available for this object
293 */
294 public ArithmeticCoderFL2W(int codewordLength, int precisionBits, int numContexts){
295 this.codewordLength = codewordLength;
296 this.precisionBits = precisionBits;
297 this.numContexts = numContexts;
298
299 assert(codewordLength > 0);
300 assert(precisionBits > 0);
301 assert(numContexts > 0);
302 assert(codewordLength + precisionBits < 64);
303
304 codewordMax = ((long) 1 << codewordLength) - 1;
305 codeword2Bytes = (int) Math.ceil((float) codewordLength / 8f) * 2;
306 precisionMid = 1 << (precisionBits - 1);
307 tolerance = prob0ToFL2W(TOLERANCE, precisionBits);
308 contextProb0FL2W = new int[numContexts];
309 context0s = new int[numContexts];
310 context0sWindow = new int[numContexts];
311 contextTotal = new int[numContexts];
312 reset();
313 restartEncoding();
314 }
315
316 /**
317 * Transforms the probability of the symbol 0 (or false) in the range (0,1) into the
318 * integer required in the FL2W coder to represent that probability.
319 *
320 * @param prob0 in the range [0:1]. If 0 or 1, the closest probability to 0/1 given the
321 * precision bits employed will be used --but it will not be 0 or 1.
322 * @param precisionBits number of bits employed to represent the probability in the returned
323 * integer
324 * @return integer that can be fed to the FL2W coder. It is computed as (2^precisionBits) * prob0.
325 */
326 public static int prob0ToFL2W(float prob0, int precisionBits){
327 assert((prob0 >= 0f) && (prob0 <= 1f));
328
329 int prob0FL2W = (int) ((float) (1 << precisionBits) * prob0);
330 if(prob0FL2W == 0){
331 prob0FL2W = 1;
332 }else if(prob0FL2W == (1 << precisionBits)){
333 prob0FL2W = (1 << precisionBits) - 1;
334 }
335 assert((prob0FL2W > 0) && (prob0FL2W < (1 << precisionBits)));
336 return(prob0FL2W);
337 }
338
339 /**
340 * Transforms the FL2W integer to the probability of the symbol 0 (or false) in the range (0,1).
341 *
342 * @param prob0FL2W integer fed to the FL2W coder. It is (2^precisionBits) * prob0.
343 * @param precisionBits number of bits employed to represent the probability in prob0FL2W.
344 * It is recommended to be, at least, equal to the codewordLength. To use fewer bits than the
345 * codewordLength may decrease compression efficiency for very high/low probabilities, and to
346 * use more is inconsequential. Also, be aware that codewordLength + precisionBits <= 64.
347 * @return prob0 in the range (0:1)
348 */
349 public static float FL2WToProb0(int prob0FL2W, int precisionBits){
350 assert((prob0FL2W > 0) && (prob0FL2W < (1 << precisionBits)));
351
352 float prob0 = (float) prob0FL2W / (float) (1 << precisionBits);
353 assert((prob0 > 0f) && (prob0 < 1f));
354 return(prob0);
355 }
356
357 /**
358 * Encodes a bit without using any probability model.
359 *
360 * @param bit input
361 */
362 public void encodeBit(boolean bit){
363 encodeBitProb(bit, precisionMid);
364 }
365
366 /**
367 * Decodes a bit without using any probability model.
368 *
369 * @return bit output
370 * @throws Exception when some problem manipulating the stream occurs
371 */
372 public boolean decodeBit() throws Exception{
373 return(decodeBitProb(precisionMid));
374 }
375
376 /**
377 * Encodes a bit using a context so that the probabilities are adaptively adjusted depending
378 * on the incoming symbols.
379 *
380 * @param bit input
381 * @param context context of the symbol
382 */
383 public void encodeBitContext(boolean bit, int context){
384 //Updates the probability of this context, when necessary
385 if((contextTotal[context] & UPDATE_PROB0) == UPDATE_PROB0){
386 if(context0s[context] == 0){
387 contextProb0FL2W[context] = 1;
388 }else if(context0s[context] == contextTotal[context]){
389 contextProb0FL2W[context] = (1 << precisionBits) - 1;
390 }else{
391 contextProb0FL2W[context] = (context0s[context] << precisionBits) / contextTotal[context];
392 }
393 assert((contextProb0FL2W[context] > 0) && (contextProb0FL2W[context] < (1 << precisionBits)));
394 if((contextTotal[context] & WINDOW_PROB) == WINDOW_PROB){
395 if(context0sWindow[context] != -1){
396 contextTotal[context] -= WINDOW_PROB;
397 context0s[context] -= context0sWindow[context];
398 }
399 context0sWindow[context] = context0s[context];
400 }
401 }
402
403 //Encodes the bit
404 encodeBitProb(bit, contextProb0FL2W[context]);
405
406 //Updates the number of symbols coded for this context
407 if(bit == false){
408 context0s[context]++;
409 }
410 contextTotal[context]++;
411 }
412
413 /**
414 * Decodes a bit using a context so that the probabilities are adaptively adjusted depending
415 * on the outcoming symbols.
416 *
417 * @param context context of the symbols
418 * @return output bit
419 * @throws Exception when some problem manipulating the stream occurs
420 */
421 public boolean decodeBitContext(int context) throws Exception{
422 //Updates the probability of this context, when necessary
423 if((contextTotal[context] & UPDATE_PROB0) == UPDATE_PROB0){
424 if(context0s[context] == 0){
425 contextProb0FL2W[context] = 1;
426 }else if(context0s[context] == contextTotal[context]){
427 contextProb0FL2W[context] = (1 << precisionBits) - 1;
428 }else{
429 contextProb0FL2W[context] = (context0s[context] << precisionBits) / contextTotal[context];
430 }
431 assert((contextProb0FL2W[context] > 0) && (contextProb0FL2W[context] < (1 << precisionBits)));
432 if((contextTotal[context] & WINDOW_PROB) == WINDOW_PROB){
433 if(context0sWindow[context] != -1){
434 contextTotal[context] -= WINDOW_PROB;
435 context0s[context] -= context0sWindow[context];
436 }
437 context0sWindow[context] = context0s[context];
438 }
439 }
440
441 //Decodes the bit
442 boolean bit = decodeBitProb(contextProb0FL2W[context]);
443
444 //Updates the number of symbols coded for this context
445 if(bit == false){
446 context0s[context]++;
447 }
448 contextTotal[context]++;
449 return(bit);
450 }
451
452 /**
453 * Encodes a bit using a specified probability.
454 *
455 * @param bit input
456 * @param prob0FL2W probability of bit == false.
457 */
458 public void encodeBitProb(boolean bit, int prob0FL2W){
459 assert(codewordLength + precisionBits < 64);
460 assert((prob0FL2W > 0) && (prob0FL2W < (1 << precisionBits)));
461
462 int selectedWord;
463 if((forcingWord != 0) && (intervalSize[0] <= MIN_SIZE)){
464 if(intervalSize[1] <= MIN_SIZE){
465 long[] intervalMid = new long[2];
466 intervalMid[0] = ((long) prob0FL2W * intervalSize[0]) >> precisionBits;
467 intervalMid[1] = ((long) prob0FL2W * intervalSize[1]) >> precisionBits;
468 long[] intervalMidFL2W = new long[2];
469 intervalMidFL2W[0] = (intervalMid[0] + 1) << precisionBits;
470 intervalMidFL2W[1] = (intervalMid[1] + 1) << precisionBits;
471 long[] effectiveProb0FL2W = new long[2];
472 effectiveProb0FL2W[0] = intervalMidFL2W[0] / (intervalSize[0] + 1);
473 effectiveProb0FL2W[1] = intervalMidFL2W[1] / (intervalSize[1] + 1);
474 long[] diff = new long[2];
475 diff[0] = Math.abs(prob0FL2W - effectiveProb0FL2W[0]);
476 diff[1] = Math.abs(prob0FL2W - effectiveProb0FL2W[1]);
477
478 if(diff[0] <= diff[1]){
479 selectedWord = 0;
480 }else{
481 selectedWord = 1;
482 }
483 if(bit == false){
484 intervalSize[selectedWord] = intervalMid[selectedWord];
485 }else{
486 long tmp = intervalMid[selectedWord] + 1;
487 intervalMin[selectedWord] += tmp;
488 intervalSize[selectedWord] -= tmp;
489 }
490
491 }else{
492 long intervalMid = ((long) prob0FL2W * intervalSize[0]) >> precisionBits;
493 long intervalMidFL2W = (intervalMid + 1) << precisionBits;
494 long effectiveProb0FL2W = intervalMidFL2W / (intervalSize[0] + 1);
495 long diff = Math.abs(prob0FL2W - effectiveProb0FL2W);
496
497 if(diff <= tolerance){
498 selectedWord = 0;
499 if(bit == false){
500 intervalSize[0] = intervalMid;
501 }else{
502 long tmp = intervalMid + 1;
503 intervalMin[0] += tmp;
504 intervalSize[0] -= tmp;
505 }
506 }else{
507 selectedWord = 1;
508 if(bit == false){
509 intervalSize[1] = ((long) prob0FL2W * intervalSize[1]) >> precisionBits;
510 }else{
511 long tmp = (((long) prob0FL2W * intervalSize[1]) >> precisionBits) + 1;
512 intervalMin[1] += tmp;
513 intervalSize[1] -= tmp;
514 }
515 }
516 }
517
518 }else{
519 selectedWord = 0;
520 if(bit == false){
521 intervalSize[0] = ((long) prob0FL2W * intervalSize[0]) >> precisionBits;
522 }else{
523 long tmp = (((long) prob0FL2W * intervalSize[0]) >> precisionBits) + 1;
524 intervalMin[0] += tmp;
525 intervalSize[0] -= tmp;
526 }
527 }
528
529 if(intervalSize[selectedWord] == 0){
530 if(selectedWord == 0){
531 interval[0] = intervalMin[0];
532 transferInterval(codewordLength);
533 if(intervalSize[1] == 0){
534 interval[0] = intervalMin[1];
535 transferInterval(codewordLength);
536 intervalMin[0] = 0;
537 intervalSize[0] = codewordMax;
538 }else{
539 intervalMin[0] = intervalMin[1];
540 intervalSize[0] = intervalSize[1];
541 }
542 intervalMin[1] = 0;
543 intervalSize[1] = codewordMax;
544 forcingWord = -1;
545 }else{
546 forcingWord = 0;
547 }
548 }
549 }
550
551 /**
552 * Decodes a bit using a specified probability.
553 *
554 * @param prob0FL2W probability of bit == false.
555 * @return bit decoded bit
556 * @throws Exception when some problem manipulating the stream occurs
557 */
558 public boolean decodeBitProb(int prob0FL2W) throws Exception{
559 assert(codewordLength + precisionBits < 64);
560 assert((prob0FL2W > 0) && (prob0FL2W < (1 << precisionBits)));
561
562 if(intervalSize[0] == 0){
563 if(intervalSize[1] == 0){
564 fillInterval();
565 intervalMin[0] = 0;
566 intervalSize[0] = codewordMax;
567 interval[0] = interval[1];
568 fillInterval();
569 intervalMin[1] = 0;
570 intervalSize[1] = codewordMax;
571 }else{
572 intervalMin[0] = intervalMin[1];
573 intervalSize[0] = intervalSize[1];
574 interval[0] = interval[1];
575 fillInterval();
576 intervalMin[1] = 0;
577 intervalSize[1] = codewordMax;
578 }
579 forcingWord = -1;
580 }else if(intervalSize[1] == 0){
581 forcingWord = 0;
582 }
583
584 boolean bit;
585 if((forcingWord != 0) && (intervalSize[0] <= MIN_SIZE)){
586 if(intervalSize[1] <= MIN_SIZE){
587 long[] intervalMid = new long[2];
588 intervalMid[0] = ((long) prob0FL2W * intervalSize[0]) >> precisionBits;
589 intervalMid[1] = ((long) prob0FL2W * intervalSize[1]) >> precisionBits;
590 long[] intervalMidFL2W = new long[2];
591 intervalMidFL2W[0] = (intervalMid[0] + 1) << precisionBits;
592 intervalMidFL2W[1] = (intervalMid[1] + 1) << precisionBits;
593 long[] effectiveProb0FL2W = new long[2];
594 effectiveProb0FL2W[0] = intervalMidFL2W[0] / (intervalSize[0] + 1);
595 effectiveProb0FL2W[1] = intervalMidFL2W[1] / (intervalSize[1] + 1);
596 long[] diff = new long[2];
597 diff[0] = Math.abs(prob0FL2W - effectiveProb0FL2W[0]);
598 diff[1] = Math.abs(prob0FL2W - effectiveProb0FL2W[1]);
599
600 int selectedWord;
601 if(diff[0] <= diff[1]){
602 selectedWord = 0;
603 }else{
604 selectedWord = 1;
605 }
606 long tmp = intervalMid[selectedWord] + 1;
607 long mid = intervalMin[selectedWord] + tmp;
608 if(interval[selectedWord] >= mid){
609 bit = true;
610 intervalMin[selectedWord] = mid;
611 intervalSize[selectedWord] -= tmp;
612 }else{
613 bit = false;
614 intervalSize[selectedWord] = tmp - 1;
615 }
616
617 }else{
618 long intervalMid = ((long) prob0FL2W * intervalSize[0]) >> precisionBits;
619 long intervalMidFL2W = (intervalMid + 1) << precisionBits;
620 long effectiveProb0FL2W = intervalMidFL2W / (intervalSize[0] + 1);
621 long diff = Math.abs(prob0FL2W - effectiveProb0FL2W);
622
623 if(diff <= tolerance){
624 long tmp = intervalMid + 1;
625 long mid = intervalMin[0] + tmp;
626 if(interval[0] >= mid){
627 bit = true;
628 intervalMin[0] = mid;
629 intervalSize[0] -= tmp;
630 }else{
631 bit = false;
632 intervalSize[0] = tmp - 1;
633 }
634 }else{
635 long tmp = (((long) prob0FL2W * intervalSize[1]) >> precisionBits) + 1;
636 long mid = intervalMin[1] + tmp;
637 if(interval[1] >= mid){
638 bit = true;
639 intervalMin[1] = mid;
640 intervalSize[1] -= tmp;
641 }else{
642 bit = false;
643 intervalSize[1] = tmp - 1;
644 }
645 }
646 }
647
648 }else{
649 long tmp = (((long) prob0FL2W * intervalSize[0]) >> precisionBits) + 1;
650 long mid = intervalMin[0] + tmp;
651 if(interval[0] >= mid){
652 bit = true;
653 intervalMin[0] = mid;
654 intervalSize[0] -= tmp;
655 }else{
656 bit = false;
657 intervalSize[0] = tmp - 1;
658 }
659 }
660 return(bit);
661 }
662
663 /**
664 * Transfers the interval of the first codeword to the stream (for encoding only).
665 *
666 * @param length number of bits of the interval to be transferred
667 */
668 private void transferInterval(int length){
669 int transferredBits = 0;
670 while(transferredBits < length){
671 int remainingBits = codewordLength - transferredBits;
672 int transfer = remainingBits <= t? remainingBits: t;
673
674 if((remainingBits - t) >= 0){
675 Tr |= (interval[0] >> (remainingBits - t)) & BIT_MASKS[transfer];
676 }else{
677 Tr |= (interval[0] & BIT_MASKS[transfer]) << (t - remainingBits);
678 }
679
680 t -= transfer;
681 if(t == 0){
682 stream.putByte((byte) Tr);
683 if(Tr == 0xFF){
684 t = 7;
685 }else{
686 t = 8;
687 }
688 Tr = 0;
689 L++;
690 }
691 assert(t >= 0 && t <= 8);
692
693 transferredBits += transfer;
694 }
695 }
696
697 /**
698 * Reads the interval of the second codeword from the stream (for decoding only). If at the
699 * middle of reading the interval, the stream runs out of bytes, this function fills the least
700 * significant bits of the codeword with 0s.
701 */
702 private void fillInterval() throws Exception{
703 if(!replenishment && (L >= stream.getLength())){
704 //This placed here to throw the exception only when trying to fill a new interval
705 throw new Exception("No more data in the stream to fill the interval.");
706 }
707
708 int readBits = 0;
709 interval[1] = 0;
710 do{
711 if(t == 0){
712 if(L < stream.getLength()){
713 if(Tr == 0xFF){
714 t = 7;
715 }else{
716 t = 8;
717 }
718 Tr = (0x000000FF & stream.getByte(L));
719 L++;
720 }else{
721 //Fills with 0s
722 Tr = 0;
723 t = 8;
724 }
725 }
726
727 int remainingBits = codewordLength - readBits;
728 int read = remainingBits <= t? remainingBits: t;
729
730 if((remainingBits - t) >= 0){
731 interval[1] |= ((long) Tr & BIT_MASKS[read]) << (remainingBits - t);
732 }else{
733 interval[1] |= ((long) Tr >> (t - remainingBits)) & BIT_MASKS[read];
734 }
735 assert((interval[1] >= 0) && (interval[1] <= codewordMax));
736
737 t -= read;
738 assert(t >= 0 && t <= 8);
739
740 readBits += read;
741 }while(readBits < codewordLength);
742 }
743
744 /**
745 * Changes the current stream. When encoding, before calling this function the stream
746 * should be terminated calling the <code>terminate</code> function, and after calling this
747 * function the function <code>restartEncoding</code> must be called. When decoding, after calling
748 * this function the function <code>restartDecoding</code> must be called.
749 *
750 * @param stream the new ByteStream
751 */
752 public void changeStream(ByteStream stream){
753 if(stream == null){
754 stream = new ByteStream();
755 }
756 this.stream = stream;
757 }
758
759 /**
760 * Resets the state of all contexts.
761 */
762 public void reset(){
763 for(int c = 0; c < numContexts; c++){
764 contextProb0FL2W[c] = prob0ToFL2W(0.66f, precisionBits); //Slightly biased towards 0
765 context0s[c] = 2;
766 context0sWindow[c] = -1;
767 contextTotal[c] = 3;
768 }
769 }
770
771 /**
772 * Restarts the internal registers of the coder for encoding.
773 */
774 public void restartEncoding(){
775 intervalMin[0] = 0;
776 intervalSize[0] = codewordMax;
777 intervalMin[1] = 0;
778 intervalSize[1] = codewordMax;
779 Tr = 0;
780 t = 8;
781 L = -1;
782 forcingWord = -1;
783 }
784
785 /**
786 * Restarts the internal registers of the coder for decoding.
787 *
788 * @throws Exception when some problem manipulating the stream occurs
789 */
790 public void restartDecoding() throws Exception{
791 intervalMin[0] = 0;
792 intervalSize[0] = 0;
793 intervalMin[1] = 0;
794 intervalSize[1] = 0;
795 Tr = 0;
796 t = 0;
797 L = 0;
798 forcingWord = -1;
799 }
800
801 /**
802 * Terminates the current stream using an optimal termination (for encoding purposes).
803 *
804 * @throws Exception when some problem manipulating the stream occurs
805 */
806 public void terminate() throws Exception{
807 //Stores all bits of the first codeword
808 interval[0] = intervalMin[0];
809 transferInterval(codewordLength);
810
811 //The second codeword can be terminated discarding some of the least significant bits
812 long interval1 = 0;
813 long interval2 = 0;
814 int bits = codewordLength;
815 long intervalMax = intervalMin[1] + intervalSize[1];
816 while(((interval1 < intervalMin[1]) || (interval1 > intervalMax))
817 && ((interval2 < intervalMin[1]) || (interval2 > intervalMax))){
818 bits--;
819 interval1 |= ((long) 1 << bits) & intervalMin[1];
820 interval2 |= ((long) 1 << bits) & intervalMax;
821 }
822
823 if((interval1 >= intervalMin[1]) && (interval1 <= intervalMax)){
824 interval[0] = interval1;
825 }else{
826 assert((interval2 >= intervalMin[1]) && (interval2 <= intervalMax));
827 interval[0] = interval2;
828 }
829 assert(bits >= 0);
830
831 transferInterval(codewordLength - bits);
832 if(t != 8){
833 stream.putByte((byte) Tr);
834 Tr = 0;
835 t = 8;
836 }
837 }
838
839 /**
840 * Computes the number of bytes belonging to the currently encoded data needed to flush
841 * the internal registers (for encoding purposes). This function is useful to determine
842 * potential truncation points of the stream.
843 *
844 * @return number of bytes
845 */
846 public int remainingBytes(){
847 if(t == 8){
848 return(codeword2Bytes );
849 }else{
850 return(codeword2Bytes + 1);
851 }
852 }
853
854 /**
855 * Gets the number of bytes read or written to the stream associated to the coder.
856 *
857 * @return number of bytes
858 */
859 public int getReadBytes(){
860 return(L);
861 }
862
863 /**
864 * Sets the {@link #replenishment} parameter.
865 *
866 * @param replenishment the new value for the parameter
867 */
868 public void setReplenishment(boolean replenishment){
869 this.replenishment = replenishment;
870 }
871 }
|