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