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