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