1 /* 2 * jcarith.c 3 * 4 * This file was part of the Independent JPEG Group's software: 5 * Developed 1997-2009 by Guido Vollbeding. 6 * libjpeg-turbo Modifications: 7 * Copyright (C) 2015, D. R. Commander. 8 * For conditions of distribution and use, see the accompanying README.ijg 9 * file. 10 * 11 * This file contains portable arithmetic entropy encoding routines for JPEG 12 * (implementing the ISO/IEC IS 10918-1 and CCITT Recommendation ITU-T T.81). 13 * 14 * Both sequential and progressive modes are supported in this single module. 15 * 16 * Suspension is not currently supported in this module. 17 */ 18 19 #define JPEG_INTERNALS 20 #include "jinclude.h" 21 #include "jpeglib.h" 22 23 24 /* Expanded entropy encoder object for arithmetic encoding. */ 25 26 typedef struct { 27 struct jpeg_entropy_encoder pub; /* public fields */ 28 29 JLONG c; /* C register, base of coding interval, layout as in sec. D.1.3 */ 30 JLONG a; /* A register, normalized size of coding interval */ 31 JLONG sc; /* counter for stacked 0xFF values which might overflow */ 32 JLONG zc; /* counter for pending 0x00 output values which might * 33 * be discarded at the end ("Pacman" termination) */ 34 int ct; /* bit shift counter, determines when next byte will be written */ 35 int buffer; /* buffer for most recent output byte != 0xFF */ 36 37 int last_dc_val[MAX_COMPS_IN_SCAN]; /* last DC coef for each component */ 38 int dc_context[MAX_COMPS_IN_SCAN]; /* context index for DC conditioning */ 39 40 unsigned int restarts_to_go; /* MCUs left in this restart interval */ 41 int next_restart_num; /* next restart number to write (0-7) */ 42 43 /* Pointers to statistics areas (these workspaces have image lifespan) */ 44 unsigned char *dc_stats[NUM_ARITH_TBLS]; 45 unsigned char *ac_stats[NUM_ARITH_TBLS]; 46 47 /* Statistics bin for coding with fixed probability 0.5 */ 48 unsigned char fixed_bin[4]; 49 } arith_entropy_encoder; 50 51 typedef arith_entropy_encoder *arith_entropy_ptr; 52 53 /* The following two definitions specify the allocation chunk size 54 * for the statistics area. 55 * According to sections F.1.4.4.1.3 and F.1.4.4.2, we need at least 56 * 49 statistics bins for DC, and 245 statistics bins for AC coding. 57 * 58 * We use a compact representation with 1 byte per statistics bin, 59 * thus the numbers directly represent byte sizes. 60 * This 1 byte per statistics bin contains the meaning of the MPS 61 * (more probable symbol) in the highest bit (mask 0x80), and the 62 * index into the probability estimation state machine table 63 * in the lower bits (mask 0x7F). 64 */ 65 66 #define DC_STAT_BINS 64 67 #define AC_STAT_BINS 256 68 69 /* NOTE: Uncomment the following #define if you want to use the 70 * given formula for calculating the AC conditioning parameter Kx 71 * for spectral selection progressive coding in section G.1.3.2 72 * of the spec (Kx = Kmin + SRL (8 + Se - Kmin) 4). 73 * Although the spec and P&M authors claim that this "has proven 74 * to give good results for 8 bit precision samples", I'm not 75 * convinced yet that this is really beneficial. 76 * Early tests gave only very marginal compression enhancements 77 * (a few - around 5 or so - bytes even for very large files), 78 * which would turn out rather negative if we'd suppress the 79 * DAC (Define Arithmetic Conditioning) marker segments for 80 * the default parameters in the future. 81 * Note that currently the marker writing module emits 12-byte 82 * DAC segments for a full-component scan in a color image. 83 * This is not worth worrying about IMHO. However, since the 84 * spec defines the default values to be used if the tables 85 * are omitted (unlike Huffman tables, which are required 86 * anyway), one might optimize this behaviour in the future, 87 * and then it would be disadvantageous to use custom tables if 88 * they don't provide sufficient gain to exceed the DAC size. 89 * 90 * On the other hand, I'd consider it as a reasonable result 91 * that the conditioning has no significant influence on the 92 * compression performance. This means that the basic 93 * statistical model is already rather stable. 94 * 95 * Thus, at the moment, we use the default conditioning values 96 * anyway, and do not use the custom formula. 97 * 98 #define CALCULATE_SPECTRAL_CONDITIONING 99 */ 100 101 /* IRIGHT_SHIFT is like RIGHT_SHIFT, but works on int rather than JLONG. 102 * We assume that int right shift is unsigned if JLONG right shift is, 103 * which should be safe. 104 */ 105 106 #ifdef RIGHT_SHIFT_IS_UNSIGNED 107 #define ISHIFT_TEMPS int ishift_temp; 108 #define IRIGHT_SHIFT(x,shft) \ 109 ((ishift_temp = (x)) < 0 ? \ 110 (ishift_temp >> (shft)) | ((~0) << (16-(shft))) : \ 111 (ishift_temp >> (shft))) 112 #else 113 #define ISHIFT_TEMPS 114 #define IRIGHT_SHIFT(x,shft) ((x) >> (shft)) 115 #endif 116 117 118 LOCAL(void) 119 emit_byte (int val, j_compress_ptr cinfo) 120 /* Write next output byte; we do not support suspension in this module. */ 121 { 122 struct jpeg_destination_mgr *dest = cinfo->dest; 123 124 *dest->next_output_byte++ = (JOCTET) val; 125 if (--dest->free_in_buffer == 0) 126 if (! (*dest->empty_output_buffer) (cinfo)) 127 ERREXIT(cinfo, JERR_CANT_SUSPEND); 128 } 129 130 131 /* 132 * Finish up at the end of an arithmetic-compressed scan. 133 */ 134 135 METHODDEF(void) 136 finish_pass (j_compress_ptr cinfo) 137 { 138 arith_entropy_ptr e = (arith_entropy_ptr) cinfo->entropy; 139 JLONG temp; 140 141 /* Section D.1.8: Termination of encoding */ 142 143 /* Find the e->c in the coding interval with the largest 144 * number of trailing zero bits */ 145 if ((temp = (e->a - 1 + e->c) & 0xFFFF0000L) < e->c) 146 e->c = temp + 0x8000L; 147 else 148 e->c = temp; 149 /* Send remaining bytes to output */ 150 e->c <<= e->ct; 151 if (e->c & 0xF8000000L) { 152 /* One final overflow has to be handled */ 153 if (e->buffer >= 0) { 154 if (e->zc) 155 do emit_byte(0x00, cinfo); 156 while (--e->zc); 157 emit_byte(e->buffer + 1, cinfo); 158 if (e->buffer + 1 == 0xFF) 159 emit_byte(0x00, cinfo); 160 } 161 e->zc += e->sc; /* carry-over converts stacked 0xFF bytes to 0x00 */ 162 e->sc = 0; 163 } else { 164 if (e->buffer == 0) 165 ++e->zc; 166 else if (e->buffer >= 0) { 167 if (e->zc) 168 do emit_byte(0x00, cinfo); 169 while (--e->zc); 170 emit_byte(e->buffer, cinfo); 171 } 172 if (e->sc) { 173 if (e->zc) 174 do emit_byte(0x00, cinfo); 175 while (--e->zc); 176 do { 177 emit_byte(0xFF, cinfo); 178 emit_byte(0x00, cinfo); 179 } while (--e->sc); 180 } 181 } 182 /* Output final bytes only if they are not 0x00 */ 183 if (e->c & 0x7FFF800L) { 184 if (e->zc) /* output final pending zero bytes */ 185 do emit_byte(0x00, cinfo); 186 while (--e->zc); 187 emit_byte((e->c >> 19) & 0xFF, cinfo); 188 if (((e->c >> 19) & 0xFF) == 0xFF) 189 emit_byte(0x00, cinfo); 190 if (e->c & 0x7F800L) { 191 emit_byte((e->c >> 11) & 0xFF, cinfo); 192 if (((e->c >> 11) & 0xFF) == 0xFF) 193 emit_byte(0x00, cinfo); 194 } 195 } 196 } 197 198 199 /* 200 * The core arithmetic encoding routine (common in JPEG and JBIG). 201 * This needs to go as fast as possible. 202 * Machine-dependent optimization facilities 203 * are not utilized in this portable implementation. 204 * However, this code should be fairly efficient and 205 * may be a good base for further optimizations anyway. 206 * 207 * Parameter 'val' to be encoded may be 0 or 1 (binary decision). 208 * 209 * Note: I've added full "Pacman" termination support to the 210 * byte output routines, which is equivalent to the optional 211 * Discard_final_zeros procedure (Figure D.15) in the spec. 212 * Thus, we always produce the shortest possible output 213 * stream compliant to the spec (no trailing zero bytes, 214 * except for FF stuffing). 215 * 216 * I've also introduced a new scheme for accessing 217 * the probability estimation state machine table, 218 * derived from Markus Kuhn's JBIG implementation. 219 */ 220 221 LOCAL(void) 222 arith_encode (j_compress_ptr cinfo, unsigned char *st, int val) 223 { 224 register arith_entropy_ptr e = (arith_entropy_ptr) cinfo->entropy; 225 register unsigned char nl, nm; 226 register JLONG qe, temp; 227 register int sv; 228 229 /* Fetch values from our compact representation of Table D.2: 230 * Qe values and probability estimation state machine 231 */ 232 sv = *st; 233 qe = jpeg_aritab[sv & 0x7F]; /* => Qe_Value */ 234 nl = qe & 0xFF; qe >>= 8; /* Next_Index_LPS + Switch_MPS */ 235 nm = qe & 0xFF; qe >>= 8; /* Next_Index_MPS */ 236 237 /* Encode & estimation procedures per sections D.1.4 & D.1.5 */ 238 e->a -= qe; 239 if (val != (sv >> 7)) { 240 /* Encode the less probable symbol */ 241 if (e->a >= qe) { 242 /* If the interval size (qe) for the less probable symbol (LPS) 243 * is larger than the interval size for the MPS, then exchange 244 * the two symbols for coding efficiency, otherwise code the LPS 245 * as usual: */ 246 e->c += e->a; 247 e->a = qe; 248 } 249 *st = (sv & 0x80) ^ nl; /* Estimate_after_LPS */ 250 } else { 251 /* Encode the more probable symbol */ 252 if (e->a >= 0x8000L) 253 return; /* A >= 0x8000 -> ready, no renormalization required */ 254 if (e->a < qe) { 255 /* If the interval size (qe) for the less probable symbol (LPS) 256 * is larger than the interval size for the MPS, then exchange 257 * the two symbols for coding efficiency: */ 258 e->c += e->a; 259 e->a = qe; 260 } 261 *st = (sv & 0x80) ^ nm; /* Estimate_after_MPS */ 262 } 263 264 /* Renormalization & data output per section D.1.6 */ 265 do { 266 e->a <<= 1; 267 e->c <<= 1; 268 if (--e->ct == 0) { 269 /* Another byte is ready for output */ 270 temp = e->c >> 19; 271 if (temp > 0xFF) { 272 /* Handle overflow over all stacked 0xFF bytes */ 273 if (e->buffer >= 0) { 274 if (e->zc) 275 do emit_byte(0x00, cinfo); 276 while (--e->zc); 277 emit_byte(e->buffer + 1, cinfo); 278 if (e->buffer + 1 == 0xFF) 279 emit_byte(0x00, cinfo); 280 } 281 e->zc += e->sc; /* carry-over converts stacked 0xFF bytes to 0x00 */ 282 e->sc = 0; 283 /* Note: The 3 spacer bits in the C register guarantee 284 * that the new buffer byte can't be 0xFF here 285 * (see page 160 in the P&M JPEG book). */ 286 e->buffer = temp & 0xFF; /* new output byte, might overflow later */ 287 } else if (temp == 0xFF) { 288 ++e->sc; /* stack 0xFF byte (which might overflow later) */ 289 } else { 290 /* Output all stacked 0xFF bytes, they will not overflow any more */ 291 if (e->buffer == 0) 292 ++e->zc; 293 else if (e->buffer >= 0) { 294 if (e->zc) 295 do emit_byte(0x00, cinfo); 296 while (--e->zc); 297 emit_byte(e->buffer, cinfo); 298 } 299 if (e->sc) { 300 if (e->zc) 301 do emit_byte(0x00, cinfo); 302 while (--e->zc); 303 do { 304 emit_byte(0xFF, cinfo); 305 emit_byte(0x00, cinfo); 306 } while (--e->sc); 307 } 308 e->buffer = temp & 0xFF; /* new output byte (can still overflow) */ 309 } 310 e->c &= 0x7FFFFL; 311 e->ct += 8; 312 } 313 } while (e->a < 0x8000L); 314 } 315 316 317 /* 318 * Emit a restart marker & resynchronize predictions. 319 */ 320 321 LOCAL(void) 322 emit_restart (j_compress_ptr cinfo, int restart_num) 323 { 324 arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy; 325 int ci; 326 jpeg_component_info *compptr; 327 328 finish_pass(cinfo); 329 330 emit_byte(0xFF, cinfo); 331 emit_byte(JPEG_RST0 + restart_num, cinfo); 332 333 /* Re-initialize statistics areas */ 334 for (ci = 0; ci < cinfo->comps_in_scan; ci++) { 335 compptr = cinfo->cur_comp_info[ci]; 336 /* DC needs no table for refinement scan */ 337 if (cinfo->progressive_mode == 0 || (cinfo->Ss == 0 && cinfo->Ah == 0)) { 338 MEMZERO(entropy->dc_stats[compptr->dc_tbl_no], DC_STAT_BINS); 339 /* Reset DC predictions to 0 */ 340 entropy->last_dc_val[ci] = 0; 341 entropy->dc_context[ci] = 0; 342 } 343 /* AC needs no table when not present */ 344 if (cinfo->progressive_mode == 0 || cinfo->Se) { 345 MEMZERO(entropy->ac_stats[compptr->ac_tbl_no], AC_STAT_BINS); 346 } 347 } 348 349 /* Reset arithmetic encoding variables */ 350 entropy->c = 0; 351 entropy->a = 0x10000L; 352 entropy->sc = 0; 353 entropy->zc = 0; 354 entropy->ct = 11; 355 entropy->buffer = -1; /* empty */ 356 } 357 358 359 /* 360 * MCU encoding for DC initial scan (either spectral selection, 361 * or first pass of successive approximation). 362 */ 363 364 METHODDEF(boolean) 365 encode_mcu_DC_first (j_compress_ptr cinfo, JBLOCKROW *MCU_data) 366 { 367 arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy; 368 JBLOCKROW block; 369 unsigned char *st; 370 int blkn, ci, tbl; 371 int v, v2, m; 372 ISHIFT_TEMPS 373 374 /* Emit restart marker if needed */ 375 if (cinfo->restart_interval) { 376 if (entropy->restarts_to_go == 0) { 377 emit_restart(cinfo, entropy->next_restart_num); 378 entropy->restarts_to_go = cinfo->restart_interval; 379 entropy->next_restart_num++; 380 entropy->next_restart_num &= 7; 381 } 382 entropy->restarts_to_go--; 383 } 384 385 /* Encode the MCU data blocks */ 386 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) { 387 block = MCU_data[blkn]; 388 ci = cinfo->MCU_membership[blkn]; 389 tbl = cinfo->cur_comp_info[ci]->dc_tbl_no; 390 391 /* Compute the DC value after the required point transform by Al. 392 * This is simply an arithmetic right shift. 393 */ 394 m = IRIGHT_SHIFT((int) ((*block)[0]), cinfo->Al); 395 396 /* Sections F.1.4.1 & F.1.4.4.1: Encoding of DC coefficients */ 397 398 /* Table F.4: Point to statistics bin S0 for DC coefficient coding */ 399 st = entropy->dc_stats[tbl] + entropy->dc_context[ci]; 400 401 /* Figure F.4: Encode_DC_DIFF */ 402 if ((v = m - entropy->last_dc_val[ci]) == 0) { 403 arith_encode(cinfo, st, 0); 404 entropy->dc_context[ci] = 0; /* zero diff category */ 405 } else { 406 entropy->last_dc_val[ci] = m; 407 arith_encode(cinfo, st, 1); 408 /* Figure F.6: Encoding nonzero value v */ 409 /* Figure F.7: Encoding the sign of v */ 410 if (v > 0) { 411 arith_encode(cinfo, st + 1, 0); /* Table F.4: SS = S0 + 1 */ 412 st += 2; /* Table F.4: SP = S0 + 2 */ 413 entropy->dc_context[ci] = 4; /* small positive diff category */ 414 } else { 415 v = -v; 416 arith_encode(cinfo, st + 1, 1); /* Table F.4: SS = S0 + 1 */ 417 st += 3; /* Table F.4: SN = S0 + 3 */ 418 entropy->dc_context[ci] = 8; /* small negative diff category */ 419 } 420 /* Figure F.8: Encoding the magnitude category of v */ 421 m = 0; 422 if (v -= 1) { 423 arith_encode(cinfo, st, 1); 424 m = 1; 425 v2 = v; 426 st = entropy->dc_stats[tbl] + 20; /* Table F.4: X1 = 20 */ 427 while (v2 >>= 1) { 428 arith_encode(cinfo, st, 1); 429 m <<= 1; 430 st += 1; 431 } 432 } 433 arith_encode(cinfo, st, 0); 434 /* Section F.1.4.4.1.2: Establish dc_context conditioning category */ 435 if (m < (int) ((1L << cinfo->arith_dc_L[tbl]) >> 1)) 436 entropy->dc_context[ci] = 0; /* zero diff category */ 437 else if (m > (int) ((1L << cinfo->arith_dc_U[tbl]) >> 1)) 438 entropy->dc_context[ci] += 8; /* large diff category */ 439 /* Figure F.9: Encoding the magnitude bit pattern of v */ 440 st += 14; 441 while (m >>= 1) 442 arith_encode(cinfo, st, (m & v) ? 1 : 0); 443 } 444 } 445 446 return TRUE; 447 } 448 449 450 /* 451 * MCU encoding for AC initial scan (either spectral selection, 452 * or first pass of successive approximation). 453 */ 454 455 METHODDEF(boolean) 456 encode_mcu_AC_first (j_compress_ptr cinfo, JBLOCKROW *MCU_data) 457 { 458 arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy; 459 JBLOCKROW block; 460 unsigned char *st; 461 int tbl, k, ke; 462 int v, v2, m; 463 464 /* Emit restart marker if needed */ 465 if (cinfo->restart_interval) { 466 if (entropy->restarts_to_go == 0) { 467 emit_restart(cinfo, entropy->next_restart_num); 468 entropy->restarts_to_go = cinfo->restart_interval; 469 entropy->next_restart_num++; 470 entropy->next_restart_num &= 7; 471 } 472 entropy->restarts_to_go--; 473 } 474 475 /* Encode the MCU data block */ 476 block = MCU_data[0]; 477 tbl = cinfo->cur_comp_info[0]->ac_tbl_no; 478 479 /* Sections F.1.4.2 & F.1.4.4.2: Encoding of AC coefficients */ 480 481 /* Establish EOB (end-of-block) index */ 482 for (ke = cinfo->Se; ke > 0; ke--) 483 /* We must apply the point transform by Al. For AC coefficients this 484 * is an integer division with rounding towards 0. To do this portably 485 * in C, we shift after obtaining the absolute value. 486 */ 487 if ((v = (*block)[jpeg_natural_order[ke]]) >= 0) { 488 if (v >>= cinfo->Al) break; 489 } else { 490 v = -v; 491 if (v >>= cinfo->Al) break; 492 } 493 494 /* Figure F.5: Encode_AC_Coefficients */ 495 for (k = cinfo->Ss; k <= ke; k++) { 496 st = entropy->ac_stats[tbl] + 3 * (k - 1); 497 arith_encode(cinfo, st, 0); /* EOB decision */ 498 for (;;) { 499 if ((v = (*block)[jpeg_natural_order[k]]) >= 0) { 500 if (v >>= cinfo->Al) { 501 arith_encode(cinfo, st + 1, 1); 502 arith_encode(cinfo, entropy->fixed_bin, 0); 503 break; 504 } 505 } else { 506 v = -v; 507 if (v >>= cinfo->Al) { 508 arith_encode(cinfo, st + 1, 1); 509 arith_encode(cinfo, entropy->fixed_bin, 1); 510 break; 511 } 512 } 513 arith_encode(cinfo, st + 1, 0); st += 3; k++; 514 } 515 st += 2; 516 /* Figure F.8: Encoding the magnitude category of v */ 517 m = 0; 518 if (v -= 1) { 519 arith_encode(cinfo, st, 1); 520 m = 1; 521 v2 = v; 522 if (v2 >>= 1) { 523 arith_encode(cinfo, st, 1); 524 m <<= 1; 525 st = entropy->ac_stats[tbl] + 526 (k <= cinfo->arith_ac_K[tbl] ? 189 : 217); 527 while (v2 >>= 1) { 528 arith_encode(cinfo, st, 1); 529 m <<= 1; 530 st += 1; 531 } 532 } 533 } 534 arith_encode(cinfo, st, 0); 535 /* Figure F.9: Encoding the magnitude bit pattern of v */ 536 st += 14; 537 while (m >>= 1) 538 arith_encode(cinfo, st, (m & v) ? 1 : 0); 539 } 540 /* Encode EOB decision only if k <= cinfo->Se */ 541 if (k <= cinfo->Se) { 542 st = entropy->ac_stats[tbl] + 3 * (k - 1); 543 arith_encode(cinfo, st, 1); 544 } 545 546 return TRUE; 547 } 548 549 550 /* 551 * MCU encoding for DC successive approximation refinement scan. 552 */ 553 554 METHODDEF(boolean) 555 encode_mcu_DC_refine (j_compress_ptr cinfo, JBLOCKROW *MCU_data) 556 { 557 arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy; 558 unsigned char *st; 559 int Al, blkn; 560 561 /* Emit restart marker if needed */ 562 if (cinfo->restart_interval) { 563 if (entropy->restarts_to_go == 0) { 564 emit_restart(cinfo, entropy->next_restart_num); 565 entropy->restarts_to_go = cinfo->restart_interval; 566 entropy->next_restart_num++; 567 entropy->next_restart_num &= 7; 568 } 569 entropy->restarts_to_go--; 570 } 571 572 st = entropy->fixed_bin; /* use fixed probability estimation */ 573 Al = cinfo->Al; 574 575 /* Encode the MCU data blocks */ 576 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) { 577 /* We simply emit the Al'th bit of the DC coefficient value. */ 578 arith_encode(cinfo, st, (MCU_data[blkn][0][0] >> Al) & 1); 579 } 580 581 return TRUE; 582 } 583 584 585 /* 586 * MCU encoding for AC successive approximation refinement scan. 587 */ 588 589 METHODDEF(boolean) 590 encode_mcu_AC_refine (j_compress_ptr cinfo, JBLOCKROW *MCU_data) 591 { 592 arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy; 593 JBLOCKROW block; 594 unsigned char *st; 595 int tbl, k, ke, kex; 596 int v; 597 598 /* Emit restart marker if needed */ 599 if (cinfo->restart_interval) { 600 if (entropy->restarts_to_go == 0) { 601 emit_restart(cinfo, entropy->next_restart_num); 602 entropy->restarts_to_go = cinfo->restart_interval; 603 entropy->next_restart_num++; 604 entropy->next_restart_num &= 7; 605 } 606 entropy->restarts_to_go--; 607 } 608 609 /* Encode the MCU data block */ 610 block = MCU_data[0]; 611 tbl = cinfo->cur_comp_info[0]->ac_tbl_no; 612 613 /* Section G.1.3.3: Encoding of AC coefficients */ 614 615 /* Establish EOB (end-of-block) index */ 616 for (ke = cinfo->Se; ke > 0; ke--) 617 /* We must apply the point transform by Al. For AC coefficients this 618 * is an integer division with rounding towards 0. To do this portably 619 * in C, we shift after obtaining the absolute value. 620 */ 621 if ((v = (*block)[jpeg_natural_order[ke]]) >= 0) { 622 if (v >>= cinfo->Al) break; 623 } else { 624 v = -v; 625 if (v >>= cinfo->Al) break; 626 } 627 628 /* Establish EOBx (previous stage end-of-block) index */ 629 for (kex = ke; kex > 0; kex--) 630 if ((v = (*block)[jpeg_natural_order[kex]]) >= 0) { 631 if (v >>= cinfo->Ah) break; 632 } else { 633 v = -v; 634 if (v >>= cinfo->Ah) break; 635 } 636 637 /* Figure G.10: Encode_AC_Coefficients_SA */ 638 for (k = cinfo->Ss; k <= ke; k++) { 639 st = entropy->ac_stats[tbl] + 3 * (k - 1); 640 if (k > kex) 641 arith_encode(cinfo, st, 0); /* EOB decision */ 642 for (;;) { 643 if ((v = (*block)[jpeg_natural_order[k]]) >= 0) { 644 if (v >>= cinfo->Al) { 645 if (v >> 1) /* previously nonzero coef */ 646 arith_encode(cinfo, st + 2, (v & 1)); 647 else { /* newly nonzero coef */ 648 arith_encode(cinfo, st + 1, 1); 649 arith_encode(cinfo, entropy->fixed_bin, 0); 650 } 651 break; 652 } 653 } else { 654 v = -v; 655 if (v >>= cinfo->Al) { 656 if (v >> 1) /* previously nonzero coef */ 657 arith_encode(cinfo, st + 2, (v & 1)); 658 else { /* newly nonzero coef */ 659 arith_encode(cinfo, st + 1, 1); 660 arith_encode(cinfo, entropy->fixed_bin, 1); 661 } 662 break; 663 } 664 } 665 arith_encode(cinfo, st + 1, 0); st += 3; k++; 666 } 667 } 668 /* Encode EOB decision only if k <= cinfo->Se */ 669 if (k <= cinfo->Se) { 670 st = entropy->ac_stats[tbl] + 3 * (k - 1); 671 arith_encode(cinfo, st, 1); 672 } 673 674 return TRUE; 675 } 676 677 678 /* 679 * Encode and output one MCU's worth of arithmetic-compressed coefficients. 680 */ 681 682 METHODDEF(boolean) 683 encode_mcu (j_compress_ptr cinfo, JBLOCKROW *MCU_data) 684 { 685 arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy; 686 jpeg_component_info *compptr; 687 JBLOCKROW block; 688 unsigned char *st; 689 int blkn, ci, tbl, k, ke; 690 int v, v2, m; 691 692 /* Emit restart marker if needed */ 693 if (cinfo->restart_interval) { 694 if (entropy->restarts_to_go == 0) { 695 emit_restart(cinfo, entropy->next_restart_num); 696 entropy->restarts_to_go = cinfo->restart_interval; 697 entropy->next_restart_num++; 698 entropy->next_restart_num &= 7; 699 } 700 entropy->restarts_to_go--; 701 } 702 703 /* Encode the MCU data blocks */ 704 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) { 705 block = MCU_data[blkn]; 706 ci = cinfo->MCU_membership[blkn]; 707 compptr = cinfo->cur_comp_info[ci]; 708 709 /* Sections F.1.4.1 & F.1.4.4.1: Encoding of DC coefficients */ 710 711 tbl = compptr->dc_tbl_no; 712 713 /* Table F.4: Point to statistics bin S0 for DC coefficient coding */ 714 st = entropy->dc_stats[tbl] + entropy->dc_context[ci]; 715 716 /* Figure F.4: Encode_DC_DIFF */ 717 if ((v = (*block)[0] - entropy->last_dc_val[ci]) == 0) { 718 arith_encode(cinfo, st, 0); 719 entropy->dc_context[ci] = 0; /* zero diff category */ 720 } else { 721 entropy->last_dc_val[ci] = (*block)[0]; 722 arith_encode(cinfo, st, 1); 723 /* Figure F.6: Encoding nonzero value v */ 724 /* Figure F.7: Encoding the sign of v */ 725 if (v > 0) { 726 arith_encode(cinfo, st + 1, 0); /* Table F.4: SS = S0 + 1 */ 727 st += 2; /* Table F.4: SP = S0 + 2 */ 728 entropy->dc_context[ci] = 4; /* small positive diff category */ 729 } else { 730 v = -v; 731 arith_encode(cinfo, st + 1, 1); /* Table F.4: SS = S0 + 1 */ 732 st += 3; /* Table F.4: SN = S0 + 3 */ 733 entropy->dc_context[ci] = 8; /* small negative diff category */ 734 } 735 /* Figure F.8: Encoding the magnitude category of v */ 736 m = 0; 737 if (v -= 1) { 738 arith_encode(cinfo, st, 1); 739 m = 1; 740 v2 = v; 741 st = entropy->dc_stats[tbl] + 20; /* Table F.4: X1 = 20 */ 742 while (v2 >>= 1) { 743 arith_encode(cinfo, st, 1); 744 m <<= 1; 745 st += 1; 746 } 747 } 748 arith_encode(cinfo, st, 0); 749 /* Section F.1.4.4.1.2: Establish dc_context conditioning category */ 750 if (m < (int) ((1L << cinfo->arith_dc_L[tbl]) >> 1)) 751 entropy->dc_context[ci] = 0; /* zero diff category */ 752 else if (m > (int) ((1L << cinfo->arith_dc_U[tbl]) >> 1)) 753 entropy->dc_context[ci] += 8; /* large diff category */ 754 /* Figure F.9: Encoding the magnitude bit pattern of v */ 755 st += 14; 756 while (m >>= 1) 757 arith_encode(cinfo, st, (m & v) ? 1 : 0); 758 } 759 760 /* Sections F.1.4.2 & F.1.4.4.2: Encoding of AC coefficients */ 761 762 tbl = compptr->ac_tbl_no; 763 764 /* Establish EOB (end-of-block) index */ 765 for (ke = DCTSIZE2 - 1; ke > 0; ke--) 766 if ((*block)[jpeg_natural_order[ke]]) break; 767 768 /* Figure F.5: Encode_AC_Coefficients */ 769 for (k = 1; k <= ke; k++) { 770 st = entropy->ac_stats[tbl] + 3 * (k - 1); 771 arith_encode(cinfo, st, 0); /* EOB decision */ 772 while ((v = (*block)[jpeg_natural_order[k]]) == 0) { 773 arith_encode(cinfo, st + 1, 0); st += 3; k++; 774 } 775 arith_encode(cinfo, st + 1, 1); 776 /* Figure F.6: Encoding nonzero value v */ 777 /* Figure F.7: Encoding the sign of v */ 778 if (v > 0) { 779 arith_encode(cinfo, entropy->fixed_bin, 0); 780 } else { 781 v = -v; 782 arith_encode(cinfo, entropy->fixed_bin, 1); 783 } 784 st += 2; 785 /* Figure F.8: Encoding the magnitude category of v */ 786 m = 0; 787 if (v -= 1) { 788 arith_encode(cinfo, st, 1); 789 m = 1; 790 v2 = v; 791 if (v2 >>= 1) { 792 arith_encode(cinfo, st, 1); 793 m <<= 1; 794 st = entropy->ac_stats[tbl] + 795 (k <= cinfo->arith_ac_K[tbl] ? 189 : 217); 796 while (v2 >>= 1) { 797 arith_encode(cinfo, st, 1); 798 m <<= 1; 799 st += 1; 800 } 801 } 802 } 803 arith_encode(cinfo, st, 0); 804 /* Figure F.9: Encoding the magnitude bit pattern of v */ 805 st += 14; 806 while (m >>= 1) 807 arith_encode(cinfo, st, (m & v) ? 1 : 0); 808 } 809 /* Encode EOB decision only if k <= DCTSIZE2 - 1 */ 810 if (k <= DCTSIZE2 - 1) { 811 st = entropy->ac_stats[tbl] + 3 * (k - 1); 812 arith_encode(cinfo, st, 1); 813 } 814 } 815 816 return TRUE; 817 } 818 819 820 /* 821 * Initialize for an arithmetic-compressed scan. 822 */ 823 824 METHODDEF(void) 825 start_pass (j_compress_ptr cinfo, boolean gather_statistics) 826 { 827 arith_entropy_ptr entropy = (arith_entropy_ptr) cinfo->entropy; 828 int ci, tbl; 829 jpeg_component_info *compptr; 830 831 if (gather_statistics) 832 /* Make sure to avoid that in the master control logic! 833 * We are fully adaptive here and need no extra 834 * statistics gathering pass! 835 */ 836 ERREXIT(cinfo, JERR_NOT_COMPILED); 837 838 /* We assume jcmaster.c already validated the progressive scan parameters. */ 839 840 /* Select execution routines */ 841 if (cinfo->progressive_mode) { 842 if (cinfo->Ah == 0) { 843 if (cinfo->Ss == 0) 844 entropy->pub.encode_mcu = encode_mcu_DC_first; 845 else 846 entropy->pub.encode_mcu = encode_mcu_AC_first; 847 } else { 848 if (cinfo->Ss == 0) 849 entropy->pub.encode_mcu = encode_mcu_DC_refine; 850 else 851 entropy->pub.encode_mcu = encode_mcu_AC_refine; 852 } 853 } else 854 entropy->pub.encode_mcu = encode_mcu; 855 856 /* Allocate & initialize requested statistics areas */ 857 for (ci = 0; ci < cinfo->comps_in_scan; ci++) { 858 compptr = cinfo->cur_comp_info[ci]; 859 /* DC needs no table for refinement scan */ 860 if (cinfo->progressive_mode == 0 || (cinfo->Ss == 0 && cinfo->Ah == 0)) { 861 tbl = compptr->dc_tbl_no; 862 if (tbl < 0 || tbl >= NUM_ARITH_TBLS) 863 ERREXIT1(cinfo, JERR_NO_ARITH_TABLE, tbl); 864 if (entropy->dc_stats[tbl] == NULL) 865 entropy->dc_stats[tbl] = (unsigned char *) (*cinfo->mem->alloc_small) 866 ((j_common_ptr) cinfo, JPOOL_IMAGE, DC_STAT_BINS); 867 MEMZERO(entropy->dc_stats[tbl], DC_STAT_BINS); 868 /* Initialize DC predictions to 0 */ 869 entropy->last_dc_val[ci] = 0; 870 entropy->dc_context[ci] = 0; 871 } 872 /* AC needs no table when not present */ 873 if (cinfo->progressive_mode == 0 || cinfo->Se) { 874 tbl = compptr->ac_tbl_no; 875 if (tbl < 0 || tbl >= NUM_ARITH_TBLS) 876 ERREXIT1(cinfo, JERR_NO_ARITH_TABLE, tbl); 877 if (entropy->ac_stats[tbl] == NULL) 878 entropy->ac_stats[tbl] = (unsigned char *) (*cinfo->mem->alloc_small) 879 ((j_common_ptr) cinfo, JPOOL_IMAGE, AC_STAT_BINS); 880 MEMZERO(entropy->ac_stats[tbl], AC_STAT_BINS); 881 #ifdef CALCULATE_SPECTRAL_CONDITIONING 882 if (cinfo->progressive_mode) 883 /* Section G.1.3.2: Set appropriate arithmetic conditioning value Kx */ 884 cinfo->arith_ac_K[tbl] = cinfo->Ss + ((8 + cinfo->Se - cinfo->Ss) >> 4); 885 #endif 886 } 887 } 888 889 /* Initialize arithmetic encoding variables */ 890 entropy->c = 0; 891 entropy->a = 0x10000L; 892 entropy->sc = 0; 893 entropy->zc = 0; 894 entropy->ct = 11; 895 entropy->buffer = -1; /* empty */ 896 897 /* Initialize restart stuff */ 898 entropy->restarts_to_go = cinfo->restart_interval; 899 entropy->next_restart_num = 0; 900 } 901 902 903 /* 904 * Module initialization routine for arithmetic entropy encoding. 905 */ 906 907 GLOBAL(void) 908 jinit_arith_encoder (j_compress_ptr cinfo) 909 { 910 arith_entropy_ptr entropy; 911 int i; 912 913 entropy = (arith_entropy_ptr) 914 (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE, 915 sizeof(arith_entropy_encoder)); 916 cinfo->entropy = (struct jpeg_entropy_encoder *) entropy; 917 entropy->pub.start_pass = start_pass; 918 entropy->pub.finish_pass = finish_pass; 919 920 /* Mark tables unallocated */ 921 for (i = 0; i < NUM_ARITH_TBLS; i++) { 922 entropy->dc_stats[i] = NULL; 923 entropy->ac_stats[i] = NULL; 924 } 925 926 /* Initialize index for fixed probability estimation */ 927 entropy->fixed_bin[0] = 113; 928 } 929
