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, see
008 * <http://www.deic.uab.cat/~francesc/software/license/>.
009 */
010 package coders;
011
012 import streams.ByteStream;
013
014
015 /**
016 * This class implements the M coder defined in the HEVC standard. This class can perform both the
017 * operations of the encoder and the decoder. The sourcecode is translated from C++ to Java using
018 * the reference software of the HEVC project provided
019 * in https://hevc.hhi.fraunhofer.de/svn/svn_HEVCSoftware/trunk (revision 3517).<br>
020 *
021 * Usage: once the object is created, the functions to code/decode symbols are used to code the
022 * message. Instead of destroying the object and creating another one to encode a new message, it
023 * is more computationally efficient to reuse the same object. When encoding, the same object can be
024 * reused by calling the functions <code>terminate</code>, get the stream wherever is needed, and
025 * call <code>changeStream</code> and <code>restartEncoding</code> in this order. To reuse the
026 * decoder, call the functions <code>changeStream</code> and <code>restartDecoding</code> 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 each object.<br>
030 *
031 * @author Francesc Auli-Llinas
032 * @version 1.0
033 */
034 public final class ArithmeticCoderM{
035
036 //Variables needed to encode
037 private long m_uiLow;
038 private int m_bitsLeft;
039 private int m_numBufferedBytes;
040 private int m_bufferedByte;
041
042 //Variables needed to decode
043 private long m_uiValue;
044 private int m_bitsNeeded;
045
046 //Variables needed both to encode and to decode
047 private int L;
048 private ByteStream stream;
049 private long m_uiRange;
050 private int[] m_ucState = null;
051 final static private short[][] sm_aucLPSTable = {
052 { 128, 176, 208, 240},
053 { 128, 167, 197, 227},
054 { 128, 158, 187, 216},
055 { 123, 150, 178, 205},
056 { 116, 142, 169, 195},
057 { 111, 135, 160, 185},
058 { 105, 128, 152, 175},
059 { 100, 122, 144, 166},
060 { 95, 116, 137, 158},
061 { 90, 110, 130, 150},
062 { 85, 104, 123, 142},
063 { 81, 99, 117, 135},
064 { 77, 94, 111, 128},
065 { 73, 89, 105, 122},
066 { 69, 85, 100, 116},
067 { 66, 80, 95, 110},
068 { 62, 76, 90, 104},
069 { 59, 72, 86, 99},
070 { 56, 69, 81, 94},
071 { 53, 65, 77, 89},
072 { 51, 62, 73, 85},
073 { 48, 59, 69, 80},
074 { 46, 56, 66, 76},
075 { 43, 53, 63, 72},
076 { 41, 50, 59, 69},
077 { 39, 48, 56, 65},
078 { 37, 45, 54, 62},
079 { 35, 43, 51, 59},
080 { 33, 41, 48, 56},
081 { 32, 39, 46, 53},
082 { 30, 37, 43, 50},
083 { 29, 35, 41, 48},
084 { 27, 33, 39, 45},
085 { 26, 31, 37, 43},
086 { 24, 30, 35, 41},
087 { 23, 28, 33, 39},
088 { 22, 27, 32, 37},
089 { 21, 26, 30, 35},
090 { 20, 24, 29, 33},
091 { 19, 23, 27, 31},
092 { 18, 22, 26, 30},
093 { 17, 21, 25, 28},
094 { 16, 20, 23, 27},
095 { 15, 19, 22, 25},
096 { 14, 18, 21, 24},
097 { 14, 17, 20, 23},
098 { 13, 16, 19, 22},
099 { 12, 15, 18, 21},
100 { 12, 14, 17, 20},
101 { 11, 14, 16, 19},
102 { 11, 13, 15, 18},
103 { 10, 12, 15, 17},
104 { 10, 12, 14, 16},
105 { 9, 11, 13, 15},
106 { 9, 11, 12, 14},
107 { 8, 10, 12, 14},
108 { 8, 9, 11, 13},
109 { 7, 9, 11, 12},
110 { 7, 9, 10, 12},
111 { 7, 8, 10, 11},
112 { 6, 8, 9, 11},
113 { 6, 7, 9, 10},
114 { 6, 7, 8, 9},
115 { 2, 2, 2, 2}
116 };
117 final static private byte[] sm_aucRenormTable = {
118 6, 5, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1,
119 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
120 final static private byte[] m_aucNextStateMPS = {
121 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23,
122 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43,
123 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63,
124 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83,
125 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102,
126 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118,
127 119, 120, 121, 122, 123, 124, 125, 124, 125, 126, 127};
128 final static private byte[] m_aucNextStateLPS = {
129 1, 0, 0, 1, 2, 3, 4, 5, 4, 5, 8, 9, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
130 18, 19, 22, 23, 22, 23, 24, 25, 26, 27, 26, 27, 30, 31, 30, 31, 32, 33, 32, 33, 36,
131 37, 36, 37, 38, 39, 38, 39, 42, 43, 42, 43, 44, 45, 44, 45, 46, 47, 48, 49, 48, 49,
132 50, 51, 52, 53, 52, 53, 54, 55, 54, 55, 56, 57, 58, 59, 58, 59, 60, 61, 60, 61, 60,
133 61, 62, 63, 64, 65, 64, 65, 66, 67, 66, 67, 66, 67, 68, 69, 68, 69, 70, 71, 70, 71,
134 70, 71, 72, 73, 72, 73, 72, 73, 74, 75, 74, 75, 74, 75, 76, 77, 76, 77, 126, 127};
135
136
137 /**
138 * Constructor of the class. Initializes required variables.
139 *
140 * @param numContexts number of contexts that will be used
141 */
142 public ArithmeticCoderM(int numContexts){
143 assert(numContexts > 0);
144 m_ucState = new int[numContexts];
145 }
146
147 /**
148 * Restarts the coder leaving it ready to encode.
149 */
150 public void restartEncoding(){
151 m_uiLow = 0;
152 m_uiRange = 510;
153 m_bitsLeft = 23;
154 m_numBufferedBytes = 0;
155 m_bufferedByte = 0xff;
156 for(int c = 0; c < m_ucState.length; c++){
157 m_ucState[c] = 0;
158 }
159 L = 0;
160 }
161
162 /**
163 * Restarts the coder leaving it ready to decode.
164 *
165 * @throws Exception when some problem reading the stream occurs
166 */
167 public void restartDecoding() throws Exception{
168 m_uiRange = 510;
169 m_bitsNeeded = -8;
170 L = 0;
171 int Tr = 0x00;
172 if(L < stream.getLength()){
173 Tr = (0x000000FF & (int) stream.getByte(L));
174 L++;
175 }
176 m_uiValue = Tr << 8;
177 Tr = 0x00;
178 if(L < stream.getLength()){
179 Tr = (0x000000FF & (int) stream.getByte(L));
180 L++;
181 }
182 m_uiValue += Tr;
183 for(int c = 0; c < m_ucState.length; c++){
184 m_ucState[c] = 0;
185 }
186 }
187
188 /**
189 * Encodes a bit using equiprobable probabilities.
190 *
191 * @param binValue the bit to encode
192 */
193 public void encodeBit(boolean binValue){
194 m_uiLow <<= 1;
195 if(binValue){
196 m_uiLow += m_uiRange;
197 }
198 m_bitsLeft--;
199 testAndWriteOut();
200 }
201
202 /**
203 * Decodes a bit using equiprobable probabilities.
204 *
205 * @return the decoded bit
206 * @throws Exception when some problem reading the stream occurs
207 */
208 public boolean decodeBit() throws Exception{
209 boolean ruiBin;
210 m_uiValue += m_uiValue;
211 if(++m_bitsNeeded >= 0){
212 m_bitsNeeded = -8;
213 int Tr = 0x00;
214 if(L < stream.getLength()){
215 Tr = (0x000000FF & (int) stream.getByte(L));
216 L++;
217 }
218 m_uiValue += Tr;
219 }
220 ruiBin = false;
221 long scaledRange = m_uiRange << 7;
222 if(m_uiValue >= scaledRange){
223 ruiBin = true;
224 m_uiValue -= scaledRange;
225 }
226 return(ruiBin);
227 }
228
229 /**
230 * Encodes a bit employing context-adaptive mechanisms.
231 *
232 * @param binValue the bit to encode
233 * @param context the context employed to encode the bit
234 */
235 public void encodeBitContext(boolean binValue, int context){
236 int state = m_ucState[context] >> 1;
237 int uiLPS = sm_aucLPSTable[state][(int) ((m_uiRange >> 6) & 3)];
238 m_uiRange -= uiLPS;
239 boolean MPS = (m_ucState[context] & 1) == 1;
240
241 if(binValue != MPS){
242 int numBits = sm_aucRenormTable[uiLPS >> 3];
243 m_uiLow = (m_uiLow + m_uiRange) << numBits;
244 m_uiRange = uiLPS << numBits;
245 m_ucState[context] = m_aucNextStateLPS[m_ucState[context]];
246 m_bitsLeft -= numBits;
247 }else{
248 m_ucState[context] = m_aucNextStateMPS[m_ucState[context]];
249 if(m_uiRange >= 256){
250 return;
251 }
252 m_uiLow <<= 1;
253 m_uiRange <<= 1;
254 m_bitsLeft--;
255 }
256 testAndWriteOut();
257 }
258
259 /**
260 * Decodes a bit employing context-adaptive mechanisms.
261 *
262 * @param context the context employed to decode the bit
263 * @return the decoded bit
264 * @throws Exception when some problem reading the stream occurs
265 */
266 public boolean decodeBitContext(int context) throws Exception{
267 boolean ruiBin;
268 int state = m_ucState[context] >> 1;
269 int uiLPS = sm_aucLPSTable[state][(int) ((m_uiRange >> 6) - 4)];
270 m_uiRange -= uiLPS;
271 long scaledRange = m_uiRange << 7;
272 boolean MPS = (m_ucState[context] & 1) == 1;
273
274 if(m_uiValue < scaledRange){
275 ruiBin = MPS;
276 m_ucState[context] = m_aucNextStateMPS[m_ucState[context]];
277 if(scaledRange >= (256 << 7)){
278 return(ruiBin);
279 }
280 m_uiRange = scaledRange >> 6;
281 m_uiValue += m_uiValue;
282 if(++m_bitsNeeded == 0){
283 m_bitsNeeded = -8;
284 int Tr = 0x00;
285 if(L < stream.getLength()){
286 Tr = (0x000000FF & (int) stream.getByte(L));
287 L++;
288 }
289 m_uiValue += Tr;
290 }
291 }else{
292 int numBits = sm_aucRenormTable[uiLPS >> 3];
293 m_uiValue = (m_uiValue - scaledRange) << numBits;
294 m_uiRange = uiLPS << numBits;
295 ruiBin = !MPS;
296 m_ucState[context] = m_aucNextStateLPS[m_ucState[context]];
297 m_bitsNeeded += numBits;
298 if(m_bitsNeeded >= 0){
299 int Tr = 0x00;
300 if(L < stream.getLength()){
301 Tr = (0x000000FF & (int) stream.getByte(L));
302 L++;
303 }
304 m_uiValue += Tr << m_bitsNeeded;
305 m_bitsNeeded -= 8;
306 }
307 }
308 return(ruiBin);
309 }
310
311 /**
312 * Encodes a bit employing the probability of symbol 0.
313 *
314 * @param binValue the bit to encode
315 * @param prob0 probability of the symbol 0 computed through the function {@link #prob0ToM(float)}
316 */
317 public void encodeBitProb(boolean binValue, int prob0){
318 boolean MPS = prob0 < 0;
319 int uiLPS = sm_aucLPSTable[Math.abs(prob0)][(int) ((m_uiRange >> 6) & 3)];
320 m_uiRange -= uiLPS;
321
322 if(binValue != MPS){
323 int numBits = sm_aucRenormTable[uiLPS >> 3];
324 m_uiLow = (m_uiLow + m_uiRange) << numBits;
325 m_uiRange = uiLPS << numBits;
326 m_bitsLeft -= numBits;
327 }else{
328 if(m_uiRange >= 256){
329 return;
330 }
331 m_uiLow <<= 1;
332 m_uiRange <<= 1;
333 m_bitsLeft--;
334 }
335 testAndWriteOut();
336 }
337
338 /**
339 * Decodes a bit employing the probability of symbol 0.
340 *
341 * @param prob0 probability of the symbol 0 computed through the function {@link #prob0ToM(float)}
342 * @return the decoded bit
343 * @throws Exception when some problem reading the stream occurs
344 */
345 public boolean decodeBitProb(int prob0) throws Exception{
346 boolean MPS = prob0 < 0;
347 boolean ruiBin;
348 int uiLPS = sm_aucLPSTable[Math.abs(prob0)][(int) ((m_uiRange >> 6) - 4)];
349 m_uiRange -= uiLPS;
350 long scaledRange = m_uiRange << 7;
351
352 if(m_uiValue < scaledRange){
353 ruiBin = MPS;
354 if(scaledRange >= (256 << 7)){
355 return(ruiBin);
356 }
357 m_uiRange = scaledRange >> 6;
358 m_uiValue += m_uiValue;
359 if(++m_bitsNeeded == 0){
360 m_bitsNeeded = -8;
361 int Tr = 0x00;
362 if(L < stream.getLength()){
363 Tr = (0x000000FF & (int) stream.getByte(L));
364 L++;
365 }
366 m_uiValue += Tr;
367 }
368 }else{
369 int numBits = sm_aucRenormTable[uiLPS >> 3];
370 m_uiValue = (m_uiValue - scaledRange) << numBits;
371 m_uiRange = uiLPS << numBits;
372 ruiBin = !MPS;
373 m_bitsNeeded += numBits;
374 if(m_bitsNeeded >= 0){
375 int Tr = 0x00;
376 if(L < stream.getLength()){
377 Tr = (0x000000FF & (int) stream.getByte(L));
378 L++;
379 }
380 m_uiValue += Tr << m_bitsNeeded;
381 m_bitsNeeded -= 8;
382 }
383 }
384 return(ruiBin);
385 }
386
387 /**
388 * Transforms the probability of the symbol 0 (or false) in the range [0:1] into the integer
389 * required in the M coder to represent that probability.
390 *
391 * @param prob0 in the range [0:1]
392 * @return integer that can be feed to the M coder
393 */
394 public static int prob0ToM(float prob0){
395 boolean MPS;
396 if(prob0 >= 0.5f){
397 MPS = false;
398 }else{
399 MPS = true;
400 prob0 = 1 - prob0;
401 }
402 //determined through reverse engineering (it is the context with closest probability to prob0)
403 float base = 12f;
404 int prob0M = (int) (((Math.pow(base, (prob0 - 0.5f) * 2f) - 1f) / (base - 1f)) * 61f) + 2;
405 if(MPS){
406 prob0M = -prob0M;
407 }
408 return(prob0M);
409 }
410
411 /**
412 * Does nothing. Added for compatibility purposes.
413 */
414 public void reset(){}
415
416 /**
417 * Swaps the current stream. When encoding, before calling this function the stream should be
418 * terminated calling the <code>terminate</code> function, and after calling this function the
419 * function <code>restartEncoding</code> must be called. When decoding, after calling this
420 * function the function <code>restartDecoding</code> must be called.
421 *
422 * @param stream the new ByteStream
423 */
424 public void changeStream(ByteStream stream){
425 if(stream == null){
426 stream = new ByteStream();
427 }
428 this.stream = stream;
429 }
430
431 /**
432 * Terminates the encoding process dispatching all bits in the register to the stream.
433 */
434 public void terminate(){
435 encodeBinTrm(1);
436 if((m_uiLow >> (32 - m_bitsLeft)) != 0){
437 stream.putByte((byte) (m_bufferedByte + 1));
438 L++;
439 while(m_numBufferedBytes > 1){
440 stream.putByte((byte) 0x00);
441 L++;
442 m_numBufferedBytes--;
443 }
444 m_uiLow -= 1 << (32 - m_bitsLeft);
445 }else{
446 if(m_numBufferedBytes > 0){
447 stream.putByte((byte) m_bufferedByte);
448 L++;
449 }
450 while(m_numBufferedBytes > 1){
451 stream.putByte((byte) 0xFF);
452 L++;
453 m_numBufferedBytes--;
454 }
455 }
456 int bitsLeft = 24 - m_bitsLeft;
457 while(bitsLeft > 0){
458 stream.putByte((byte) (m_uiLow >> bitsLeft));
459 L++;
460 bitsLeft -= 8;
461 }
462 }
463
464 /**
465 * Gets the number of bytes read or written to the stream associated to the coder.
466 *
467 * @return the number of bytes
468 */
469 public int getReadBytes(){
470 return(L);
471 }
472
473 /**
474 * Computes the number of bytes belonging to the currently encoded data needed to flush the
475 * internal registers (for encoding purposes). This function is useful to determine potential
476 * truncation points of the stream.
477 *
478 * @return number of bytes
479 */
480 public int remainingBytes(){
481 return(4);
482 }
483
484 /**
485 * Tests whether the bits in the register have to be dispatched to the stream.
486 */
487 private void testAndWriteOut(){
488 if(m_bitsLeft < 12){
489 writeOut();
490 }
491 }
492
493 /**
494 * Writes some bits of the internal register to the stream.
495 */
496 private void writeOut(){
497 int leadByte = (int) (m_uiLow >> (24 - m_bitsLeft));
498 m_bitsLeft += 8;
499 m_uiLow &= (0xffffffffl) >> m_bitsLeft;
500
501 if(leadByte == 0xff){
502 m_numBufferedBytes++;
503 }else{
504 if(m_numBufferedBytes > 0){
505 int carry = leadByte >> 8;
506 int byteB = m_bufferedByte + carry;
507 m_bufferedByte = leadByte & 0xff;
508 stream.putByte((byte) byteB);
509 L++;
510
511 byteB = (0xff + carry) & 0xff;
512 while(m_numBufferedBytes > 1){
513 stream.putByte((byte) byteB);
514 L++;
515 m_numBufferedBytes--;
516 }
517 }else{
518 m_numBufferedBytes = 1;
519 m_bufferedByte = leadByte;
520 }
521 }
522 }
523
524 /**
525 * Encodes a terminating bit (needed when terminating the encoding process).
526 *
527 * @param binValue the bit encoded
528 */
529 public void encodeBinTrm(int binValue){
530 m_uiRange -= 2;
531 if(binValue != 0){
532 m_uiLow += m_uiRange;
533 m_uiLow <<= 7;
534 m_uiRange = 2 << 7;
535 m_bitsLeft -= 7;
536 }else if(m_uiRange >= 256){
537 return;
538 }else{
539 m_uiLow <<= 1;
540 m_uiRange <<= 1;
541 m_bitsLeft--;
542 }
543 testAndWriteOut();
544 }
545 }
|