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