1/* 2 * reserved comment block 3 * DO NOT REMOVE OR ALTER! 4 */ 5/* 6 * jcphuff.c 7 * 8 * Copyright (C) 1995-1997, Thomas G. Lane. 9 * This file is part of the Independent JPEG Group's software. 10 * For conditions of distribution and use, see the accompanying README file. 11 * 12 * This file contains Huffman entropy encoding routines for progressive JPEG. 13 * 14 * We do not support output suspension in this module, since the library 15 * currently does not allow multiple-scan files to be written with output 16 * suspension. 17 */ 18 19#define JPEG_INTERNALS 20#include "jinclude.h" 21#include "jpeglib.h" 22#include "jchuff.h" /* Declarations shared with jchuff.c */ 23 24#ifdef C_PROGRESSIVE_SUPPORTED 25 26/* Expanded entropy encoder object for progressive Huffman encoding. */ 27 28typedef struct { 29 struct jpeg_entropy_encoder pub; /* public fields */ 30 31 /* Mode flag: TRUE for optimization, FALSE for actual data output */ 32 boolean gather_statistics; 33 34 /* Bit-level coding status. 35 * next_output_byte/free_in_buffer are local copies of cinfo->dest fields. 36 */ 37 JOCTET * next_output_byte; /* => next byte to write in buffer */ 38 size_t free_in_buffer; /* # of byte spaces remaining in buffer */ 39 INT32 put_buffer; /* current bit-accumulation buffer */ 40 int put_bits; /* # of bits now in it */ 41 j_compress_ptr cinfo; /* link to cinfo (needed for dump_buffer) */ 42 43 /* Coding status for DC components */ 44 int last_dc_val[MAX_COMPS_IN_SCAN]; /* last DC coef for each component */ 45 46 /* Coding status for AC components */ 47 int ac_tbl_no; /* the table number of the single component */ 48 unsigned int EOBRUN; /* run length of EOBs */ 49 unsigned int BE; /* # of buffered correction bits before MCU */ 50 char * bit_buffer; /* buffer for correction bits (1 per char) */ 51 /* packing correction bits tightly would save some space but cost time... */ 52 53 unsigned int restarts_to_go; /* MCUs left in this restart interval */ 54 int next_restart_num; /* next restart number to write (0-7) */ 55 56 /* Pointers to derived tables (these workspaces have image lifespan). 57 * Since any one scan codes only DC or only AC, we only need one set 58 * of tables, not one for DC and one for AC. 59 */ 60 c_derived_tbl * derived_tbls[NUM_HUFF_TBLS]; 61 62 /* Statistics tables for optimization; again, one set is enough */ 63 long * count_ptrs[NUM_HUFF_TBLS]; 64} phuff_entropy_encoder; 65 66typedef phuff_entropy_encoder * phuff_entropy_ptr; 67 68/* MAX_CORR_BITS is the number of bits the AC refinement correction-bit 69 * buffer can hold. Larger sizes may slightly improve compression, but 70 * 1000 is already well into the realm of overkill. 71 * The minimum safe size is 64 bits. 72 */ 73 74#define MAX_CORR_BITS 1000 /* Max # of correction bits I can buffer */ 75 76/* IRIGHT_SHIFT is like RIGHT_SHIFT, but works on int rather than INT32. 77 * We assume that int right shift is unsigned if INT32 right shift is, 78 * which should be safe. 79 */ 80 81#ifdef RIGHT_SHIFT_IS_UNSIGNED 82#define ISHIFT_TEMPS int ishift_temp; 83#define IRIGHT_SHIFT(x,shft) \ 84 ((ishift_temp = (x)) < 0 ? \ 85 (ishift_temp >> (shft)) | ((~0) << (16-(shft))) : \ 86 (ishift_temp >> (shft))) 87#else 88#define ISHIFT_TEMPS 89#define IRIGHT_SHIFT(x,shft) ((x) >> (shft)) 90#endif 91 92/* Forward declarations */ 93METHODDEF(boolean) encode_mcu_DC_first JPP((j_compress_ptr cinfo, 94 JBLOCKROW *MCU_data)); 95METHODDEF(boolean) encode_mcu_AC_first JPP((j_compress_ptr cinfo, 96 JBLOCKROW *MCU_data)); 97METHODDEF(boolean) encode_mcu_DC_refine JPP((j_compress_ptr cinfo, 98 JBLOCKROW *MCU_data)); 99METHODDEF(boolean) encode_mcu_AC_refine JPP((j_compress_ptr cinfo, 100 JBLOCKROW *MCU_data)); 101METHODDEF(void) finish_pass_phuff JPP((j_compress_ptr cinfo)); 102METHODDEF(void) finish_pass_gather_phuff JPP((j_compress_ptr cinfo)); 103 104 105/* 106 * Initialize for a Huffman-compressed scan using progressive JPEG. 107 */ 108 109METHODDEF(void) 110start_pass_phuff (j_compress_ptr cinfo, boolean gather_statistics) 111{ 112 phuff_entropy_ptr entropy = (phuff_entropy_ptr) cinfo->entropy; 113 boolean is_DC_band; 114 int ci, tbl; 115 jpeg_component_info * compptr; 116 117 entropy->cinfo = cinfo; 118 entropy->gather_statistics = gather_statistics; 119 120 is_DC_band = (cinfo->Ss == 0); 121 122 /* We assume jcmaster.c already validated the scan parameters. */ 123 124 /* Select execution routines */ 125 if (cinfo->Ah == 0) { 126 if (is_DC_band) 127 entropy->pub.encode_mcu = encode_mcu_DC_first; 128 else 129 entropy->pub.encode_mcu = encode_mcu_AC_first; 130 } else { 131 if (is_DC_band) 132 entropy->pub.encode_mcu = encode_mcu_DC_refine; 133 else { 134 entropy->pub.encode_mcu = encode_mcu_AC_refine; 135 /* AC refinement needs a correction bit buffer */ 136 if (entropy->bit_buffer == NULL) 137 entropy->bit_buffer = (char *) 138 (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE, 139 MAX_CORR_BITS * SIZEOF(char)); 140 } 141 } 142 if (gather_statistics) 143 entropy->pub.finish_pass = finish_pass_gather_phuff; 144 else 145 entropy->pub.finish_pass = finish_pass_phuff; 146 147 /* Only DC coefficients may be interleaved, so cinfo->comps_in_scan = 1 148 * for AC coefficients. 149 */ 150 for (ci = 0; ci < cinfo->comps_in_scan; ci++) { 151 compptr = cinfo->cur_comp_info[ci]; 152 /* Initialize DC predictions to 0 */ 153 entropy->last_dc_val[ci] = 0; 154 /* Get table index */ 155 if (is_DC_band) { 156 if (cinfo->Ah != 0) /* DC refinement needs no table */ 157 continue; 158 tbl = compptr->dc_tbl_no; 159 } else { 160 entropy->ac_tbl_no = tbl = compptr->ac_tbl_no; 161 } 162 if (gather_statistics) { 163 /* Check for invalid table index */ 164 /* (make_c_derived_tbl does this in the other path) */ 165 if (tbl < 0 || tbl >= NUM_HUFF_TBLS) 166 ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tbl); 167 /* Allocate and zero the statistics tables */ 168 /* Note that jpeg_gen_optimal_table expects 257 entries in each table! */ 169 if (entropy->count_ptrs[tbl] == NULL) 170 entropy->count_ptrs[tbl] = (long *) 171 (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE, 172 257 * SIZEOF(long)); 173 MEMZERO(entropy->count_ptrs[tbl], 257 * SIZEOF(long)); 174 } else { 175 /* Compute derived values for Huffman table */ 176 /* We may do this more than once for a table, but it's not expensive */ 177 jpeg_make_c_derived_tbl(cinfo, is_DC_band, tbl, 178 & entropy->derived_tbls[tbl]); 179 } 180 } 181 182 /* Initialize AC stuff */ 183 entropy->EOBRUN = 0; 184 entropy->BE = 0; 185 186 /* Initialize bit buffer to empty */ 187 entropy->put_buffer = 0; 188 entropy->put_bits = 0; 189 190 /* Initialize restart stuff */ 191 entropy->restarts_to_go = cinfo->restart_interval; 192 entropy->next_restart_num = 0; 193} 194 195 196/* Outputting bytes to the file. 197 * NB: these must be called only when actually outputting, 198 * that is, entropy->gather_statistics == FALSE. 199 */ 200 201/* Emit a byte */ 202#define emit_byte(entropy,val) \ 203 { *(entropy)->next_output_byte++ = (JOCTET) (val); \ 204 if (--(entropy)->free_in_buffer == 0) \ 205 dump_buffer(entropy); } 206 207 208LOCAL(void) 209dump_buffer (phuff_entropy_ptr entropy) 210/* Empty the output buffer; we do not support suspension in this module. */ 211{ 212 struct jpeg_destination_mgr * dest = entropy->cinfo->dest; 213 214 if (! (*dest->empty_output_buffer) (entropy->cinfo)) 215 ERREXIT(entropy->cinfo, JERR_CANT_SUSPEND); 216 /* After a successful buffer dump, must reset buffer pointers */ 217 entropy->next_output_byte = dest->next_output_byte; 218 entropy->free_in_buffer = dest->free_in_buffer; 219} 220 221 222/* Outputting bits to the file */ 223 224/* Only the right 24 bits of put_buffer are used; the valid bits are 225 * left-justified in this part. At most 16 bits can be passed to emit_bits 226 * in one call, and we never retain more than 7 bits in put_buffer 227 * between calls, so 24 bits are sufficient. 228 */ 229 230INLINE 231LOCAL(void) 232emit_bits (phuff_entropy_ptr entropy, unsigned int code, int size) 233/* Emit some bits, unless we are in gather mode */ 234{ 235 /* This routine is heavily used, so it's worth coding tightly. */ 236 register INT32 put_buffer = (INT32) code; 237 register int put_bits = entropy->put_bits; 238 239 /* if size is 0, caller used an invalid Huffman table entry */ 240 if (size == 0) 241 ERREXIT(entropy->cinfo, JERR_HUFF_MISSING_CODE); 242 243 if (entropy->gather_statistics) 244 return; /* do nothing if we're only getting stats */ 245 246 put_buffer &= (((INT32) 1)<<size) - 1; /* mask off any extra bits in code */ 247 248 put_bits += size; /* new number of bits in buffer */ 249 250 put_buffer <<= 24 - put_bits; /* align incoming bits */ 251 252 put_buffer |= entropy->put_buffer; /* and merge with old buffer contents */ 253 254 while (put_bits >= 8) { 255 int c = (int) ((put_buffer >> 16) & 0xFF); 256 257 emit_byte(entropy, c); 258 if (c == 0xFF) { /* need to stuff a zero byte? */ 259 emit_byte(entropy, 0); 260 } 261 put_buffer <<= 8; 262 put_bits -= 8; 263 } 264 265 entropy->put_buffer = put_buffer; /* update variables */ 266 entropy->put_bits = put_bits; 267} 268 269 270LOCAL(void) 271flush_bits (phuff_entropy_ptr entropy) 272{ 273 emit_bits(entropy, 0x7F, 7); /* fill any partial byte with ones */ 274 entropy->put_buffer = 0; /* and reset bit-buffer to empty */ 275 entropy->put_bits = 0; 276} 277 278 279/* 280 * Emit (or just count) a Huffman symbol. 281 */ 282 283INLINE 284LOCAL(void) 285emit_symbol (phuff_entropy_ptr entropy, int tbl_no, int symbol) 286{ 287 if (entropy->gather_statistics) 288 entropy->count_ptrs[tbl_no][symbol]++; 289 else { 290 c_derived_tbl * tbl = entropy->derived_tbls[tbl_no]; 291 emit_bits(entropy, tbl->ehufco[symbol], tbl->ehufsi[symbol]); 292 } 293} 294 295 296/* 297 * Emit bits from a correction bit buffer. 298 */ 299 300LOCAL(void) 301emit_buffered_bits (phuff_entropy_ptr entropy, char * bufstart, 302 unsigned int nbits) 303{ 304 if (entropy->gather_statistics) 305 return; /* no real work */ 306 307 while (nbits > 0) { 308 emit_bits(entropy, (unsigned int) (*bufstart), 1); 309 bufstart++; 310 nbits--; 311 } 312} 313 314 315/* 316 * Emit any pending EOBRUN symbol. 317 */ 318 319LOCAL(void) 320emit_eobrun (phuff_entropy_ptr entropy) 321{ 322 register int temp, nbits; 323 324 if (entropy->EOBRUN > 0) { /* if there is any pending EOBRUN */ 325 temp = entropy->EOBRUN; 326 nbits = 0; 327 while ((temp >>= 1)) 328 nbits++; 329 /* safety check: shouldn't happen given limited correction-bit buffer */ 330 if (nbits > 14) 331 ERREXIT(entropy->cinfo, JERR_HUFF_MISSING_CODE); 332 333 emit_symbol(entropy, entropy->ac_tbl_no, nbits << 4); 334 if (nbits) 335 emit_bits(entropy, entropy->EOBRUN, nbits); 336 337 entropy->EOBRUN = 0; 338 339 /* Emit any buffered correction bits */ 340 emit_buffered_bits(entropy, entropy->bit_buffer, entropy->BE); 341 entropy->BE = 0; 342 } 343} 344 345 346/* 347 * Emit a restart marker & resynchronize predictions. 348 */ 349 350LOCAL(void) 351emit_restart (phuff_entropy_ptr entropy, int restart_num) 352{ 353 int ci; 354 355 emit_eobrun(entropy); 356 357 if (! entropy->gather_statistics) { 358 flush_bits(entropy); 359 emit_byte(entropy, 0xFF); 360 emit_byte(entropy, JPEG_RST0 + restart_num); 361 } 362 363 if (entropy->cinfo->Ss == 0) { 364 /* Re-initialize DC predictions to 0 */ 365 for (ci = 0; ci < entropy->cinfo->comps_in_scan; ci++) 366 entropy->last_dc_val[ci] = 0; 367 } else { 368 /* Re-initialize all AC-related fields to 0 */ 369 entropy->EOBRUN = 0; 370 entropy->BE = 0; 371 } 372} 373 374 375/* 376 * MCU encoding for DC initial scan (either spectral selection, 377 * or first pass of successive approximation). 378 */ 379 380METHODDEF(boolean) 381encode_mcu_DC_first (j_compress_ptr cinfo, JBLOCKROW *MCU_data) 382{ 383 phuff_entropy_ptr entropy = (phuff_entropy_ptr) cinfo->entropy; 384 register int temp, temp2; 385 register int nbits; 386 int blkn, ci; 387 int Al = cinfo->Al; 388 JBLOCKROW block; 389 jpeg_component_info * compptr; 390 ISHIFT_TEMPS 391 392 entropy->next_output_byte = cinfo->dest->next_output_byte; 393 entropy->free_in_buffer = cinfo->dest->free_in_buffer; 394 395 /* Emit restart marker if needed */ 396 if (cinfo->restart_interval) 397 if (entropy->restarts_to_go == 0) 398 emit_restart(entropy, entropy->next_restart_num); 399 400 /* Encode the MCU data blocks */ 401 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) { 402 block = MCU_data[blkn]; 403 ci = cinfo->MCU_membership[blkn]; 404 compptr = cinfo->cur_comp_info[ci]; 405 406 /* Compute the DC value after the required point transform by Al. 407 * This is simply an arithmetic right shift. 408 */ 409 temp2 = IRIGHT_SHIFT((int) ((*block)[0]), Al); 410 411 /* DC differences are figured on the point-transformed values. */ 412 temp = temp2 - entropy->last_dc_val[ci]; 413 entropy->last_dc_val[ci] = temp2; 414 415 /* Encode the DC coefficient difference per section G.1.2.1 */ 416 temp2 = temp; 417 if (temp < 0) { 418 temp = -temp; /* temp is abs value of input */ 419 /* For a negative input, want temp2 = bitwise complement of abs(input) */ 420 /* This code assumes we are on a two's complement machine */ 421 temp2--; 422 } 423 424 /* Find the number of bits needed for the magnitude of the coefficient */ 425 nbits = 0; 426 while (temp) { 427 nbits++; 428 temp >>= 1; 429 } 430 /* Check for out-of-range coefficient values. 431 * Since we're encoding a difference, the range limit is twice as much. 432 */ 433 if (nbits > MAX_COEF_BITS+1) 434 ERREXIT(cinfo, JERR_BAD_DCT_COEF); 435 436 /* Count/emit the Huffman-coded symbol for the number of bits */ 437 emit_symbol(entropy, compptr->dc_tbl_no, nbits); 438 439 /* Emit that number of bits of the value, if positive, */ 440 /* or the complement of its magnitude, if negative. */ 441 if (nbits) /* emit_bits rejects calls with size 0 */ 442 emit_bits(entropy, (unsigned int) temp2, nbits); 443 } 444 445 cinfo->dest->next_output_byte = entropy->next_output_byte; 446 cinfo->dest->free_in_buffer = entropy->free_in_buffer; 447 448 /* Update restart-interval state too */ 449 if (cinfo->restart_interval) { 450 if (entropy->restarts_to_go == 0) { 451 entropy->restarts_to_go = cinfo->restart_interval; 452 entropy->next_restart_num++; 453 entropy->next_restart_num &= 7; 454 } 455 entropy->restarts_to_go--; 456 } 457 458 return TRUE; 459} 460 461 462/* 463 * MCU encoding for AC initial scan (either spectral selection, 464 * or first pass of successive approximation). 465 */ 466 467METHODDEF(boolean) 468encode_mcu_AC_first (j_compress_ptr cinfo, JBLOCKROW *MCU_data) 469{ 470 phuff_entropy_ptr entropy = (phuff_entropy_ptr) cinfo->entropy; 471 register int temp, temp2; 472 register int nbits; 473 register int r, k; 474 int Se = cinfo->Se; 475 int Al = cinfo->Al; 476 JBLOCKROW block; 477 478 entropy->next_output_byte = cinfo->dest->next_output_byte; 479 entropy->free_in_buffer = cinfo->dest->free_in_buffer; 480 481 /* Emit restart marker if needed */ 482 if (cinfo->restart_interval) 483 if (entropy->restarts_to_go == 0) 484 emit_restart(entropy, entropy->next_restart_num); 485 486 /* Encode the MCU data block */ 487 block = MCU_data[0]; 488 489 /* Encode the AC coefficients per section G.1.2.2, fig. G.3 */ 490 491 r = 0; /* r = run length of zeros */ 492 493 for (k = cinfo->Ss; k <= Se; k++) { 494 if ((temp = (*block)[jpeg_natural_order[k]]) == 0) { 495 r++; 496 continue; 497 } 498 /* We must apply the point transform by Al. For AC coefficients this 499 * is an integer division with rounding towards 0. To do this portably 500 * in C, we shift after obtaining the absolute value; so the code is 501 * interwoven with finding the abs value (temp) and output bits (temp2). 502 */ 503 if (temp < 0) { 504 temp = -temp; /* temp is abs value of input */ 505 temp >>= Al; /* apply the point transform */ 506 /* For a negative coef, want temp2 = bitwise complement of abs(coef) */ 507 temp2 = ~temp; 508 } else { 509 temp >>= Al; /* apply the point transform */ 510 temp2 = temp; 511 } 512 /* Watch out for case that nonzero coef is zero after point transform */ 513 if (temp == 0) { 514 r++; 515 continue; 516 } 517 518 /* Emit any pending EOBRUN */ 519 if (entropy->EOBRUN > 0) 520 emit_eobrun(entropy); 521 /* if run length > 15, must emit special run-length-16 codes (0xF0) */ 522 while (r > 15) { 523 emit_symbol(entropy, entropy->ac_tbl_no, 0xF0); 524 r -= 16; 525 } 526 527 /* Find the number of bits needed for the magnitude of the coefficient */ 528 nbits = 1; /* there must be at least one 1 bit */ 529 while ((temp >>= 1)) 530 nbits++; 531 /* Check for out-of-range coefficient values */ 532 if (nbits > MAX_COEF_BITS) 533 ERREXIT(cinfo, JERR_BAD_DCT_COEF); 534 535 /* Count/emit Huffman symbol for run length / number of bits */ 536 emit_symbol(entropy, entropy->ac_tbl_no, (r << 4) + nbits); 537 538 /* Emit that number of bits of the value, if positive, */ 539 /* or the complement of its magnitude, if negative. */ 540 emit_bits(entropy, (unsigned int) temp2, nbits); 541 542 r = 0; /* reset zero run length */ 543 } 544 545 if (r > 0) { /* If there are trailing zeroes, */ 546 entropy->EOBRUN++; /* count an EOB */ 547 if (entropy->EOBRUN == 0x7FFF) 548 emit_eobrun(entropy); /* force it out to avoid overflow */ 549 } 550 551 cinfo->dest->next_output_byte = entropy->next_output_byte; 552 cinfo->dest->free_in_buffer = entropy->free_in_buffer; 553 554 /* Update restart-interval state too */ 555 if (cinfo->restart_interval) { 556 if (entropy->restarts_to_go == 0) { 557 entropy->restarts_to_go = cinfo->restart_interval; 558 entropy->next_restart_num++; 559 entropy->next_restart_num &= 7; 560 } 561 entropy->restarts_to_go--; 562 } 563 564 return TRUE; 565} 566 567 568/* 569 * MCU encoding for DC successive approximation refinement scan. 570 * Note: we assume such scans can be multi-component, although the spec 571 * is not very clear on the point. 572 */ 573 574METHODDEF(boolean) 575encode_mcu_DC_refine (j_compress_ptr cinfo, JBLOCKROW *MCU_data) 576{ 577 phuff_entropy_ptr entropy = (phuff_entropy_ptr) cinfo->entropy; 578 register int temp; 579 int blkn; 580 int Al = cinfo->Al; 581 JBLOCKROW block; 582 583 entropy->next_output_byte = cinfo->dest->next_output_byte; 584 entropy->free_in_buffer = cinfo->dest->free_in_buffer; 585 586 /* Emit restart marker if needed */ 587 if (cinfo->restart_interval) 588 if (entropy->restarts_to_go == 0) 589 emit_restart(entropy, entropy->next_restart_num); 590 591 /* Encode the MCU data blocks */ 592 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) { 593 block = MCU_data[blkn]; 594 595 /* We simply emit the Al'th bit of the DC coefficient value. */ 596 temp = (*block)[0]; 597 emit_bits(entropy, (unsigned int) (temp >> Al), 1); 598 } 599 600 cinfo->dest->next_output_byte = entropy->next_output_byte; 601 cinfo->dest->free_in_buffer = entropy->free_in_buffer; 602 603 /* Update restart-interval state too */ 604 if (cinfo->restart_interval) { 605 if (entropy->restarts_to_go == 0) { 606 entropy->restarts_to_go = cinfo->restart_interval; 607 entropy->next_restart_num++; 608 entropy->next_restart_num &= 7; 609 } 610 entropy->restarts_to_go--; 611 } 612 613 return TRUE; 614} 615 616 617/* 618 * MCU encoding for AC successive approximation refinement scan. 619 */ 620 621METHODDEF(boolean) 622encode_mcu_AC_refine (j_compress_ptr cinfo, JBLOCKROW *MCU_data) 623{ 624 phuff_entropy_ptr entropy = (phuff_entropy_ptr) cinfo->entropy; 625 register int temp; 626 register int r, k; 627 int EOB; 628 char *BR_buffer; 629 unsigned int BR; 630 int Se = cinfo->Se; 631 int Al = cinfo->Al; 632 JBLOCKROW block; 633 int absvalues[DCTSIZE2]; 634 635 entropy->next_output_byte = cinfo->dest->next_output_byte; 636 entropy->free_in_buffer = cinfo->dest->free_in_buffer; 637 638 /* Emit restart marker if needed */ 639 if (cinfo->restart_interval) 640 if (entropy->restarts_to_go == 0) 641 emit_restart(entropy, entropy->next_restart_num); 642 643 /* Encode the MCU data block */ 644 block = MCU_data[0]; 645 646 /* It is convenient to make a pre-pass to determine the transformed 647 * coefficients' absolute values and the EOB position. 648 */ 649 EOB = 0; 650 for (k = cinfo->Ss; k <= Se; k++) { 651 temp = (*block)[jpeg_natural_order[k]]; 652 /* We must apply the point transform by Al. For AC coefficients this 653 * is an integer division with rounding towards 0. To do this portably 654 * in C, we shift after obtaining the absolute value. 655 */ 656 if (temp < 0) 657 temp = -temp; /* temp is abs value of input */ 658 temp >>= Al; /* apply the point transform */ 659 absvalues[k] = temp; /* save abs value for main pass */ 660 if (temp == 1) 661 EOB = k; /* EOB = index of last newly-nonzero coef */ 662 } 663 664 /* Encode the AC coefficients per section G.1.2.3, fig. G.7 */ 665 666 r = 0; /* r = run length of zeros */ 667 BR = 0; /* BR = count of buffered bits added now */ 668 BR_buffer = entropy->bit_buffer + entropy->BE; /* Append bits to buffer */ 669 670 for (k = cinfo->Ss; k <= Se; k++) { 671 if ((temp = absvalues[k]) == 0) { 672 r++; 673 continue; 674 } 675 676 /* Emit any required ZRLs, but not if they can be folded into EOB */ 677 while (r > 15 && k <= EOB) { 678 /* emit any pending EOBRUN and the BE correction bits */ 679 emit_eobrun(entropy); 680 /* Emit ZRL */ 681 emit_symbol(entropy, entropy->ac_tbl_no, 0xF0); 682 r -= 16; 683 /* Emit buffered correction bits that must be associated with ZRL */ 684 emit_buffered_bits(entropy, BR_buffer, BR); 685 BR_buffer = entropy->bit_buffer; /* BE bits are gone now */ 686 BR = 0; 687 } 688 689 /* If the coef was previously nonzero, it only needs a correction bit. 690 * NOTE: a straight translation of the spec's figure G.7 would suggest 691 * that we also need to test r > 15. But if r > 15, we can only get here 692 * if k > EOB, which implies that this coefficient is not 1. 693 */ 694 if (temp > 1) { 695 /* The correction bit is the next bit of the absolute value. */ 696 BR_buffer[BR++] = (char) (temp & 1); 697 continue; 698 } 699 700 /* Emit any pending EOBRUN and the BE correction bits */ 701 emit_eobrun(entropy); 702 703 /* Count/emit Huffman symbol for run length / number of bits */ 704 emit_symbol(entropy, entropy->ac_tbl_no, (r << 4) + 1); 705 706 /* Emit output bit for newly-nonzero coef */ 707 temp = ((*block)[jpeg_natural_order[k]] < 0) ? 0 : 1; 708 emit_bits(entropy, (unsigned int) temp, 1); 709 710 /* Emit buffered correction bits that must be associated with this code */ 711 emit_buffered_bits(entropy, BR_buffer, BR); 712 BR_buffer = entropy->bit_buffer; /* BE bits are gone now */ 713 BR = 0; 714 r = 0; /* reset zero run length */ 715 } 716 717 if (r > 0 || BR > 0) { /* If there are trailing zeroes, */ 718 entropy->EOBRUN++; /* count an EOB */ 719 entropy->BE += BR; /* concat my correction bits to older ones */ 720 /* We force out the EOB if we risk either: 721 * 1. overflow of the EOB counter; 722 * 2. overflow of the correction bit buffer during the next MCU. 723 */ 724 if (entropy->EOBRUN == 0x7FFF || entropy->BE > (MAX_CORR_BITS-DCTSIZE2+1)) 725 emit_eobrun(entropy); 726 } 727 728 cinfo->dest->next_output_byte = entropy->next_output_byte; 729 cinfo->dest->free_in_buffer = entropy->free_in_buffer; 730 731 /* Update restart-interval state too */ 732 if (cinfo->restart_interval) { 733 if (entropy->restarts_to_go == 0) { 734 entropy->restarts_to_go = cinfo->restart_interval; 735 entropy->next_restart_num++; 736 entropy->next_restart_num &= 7; 737 } 738 entropy->restarts_to_go--; 739 } 740 741 return TRUE; 742} 743 744 745/* 746 * Finish up at the end of a Huffman-compressed progressive scan. 747 */ 748 749METHODDEF(void) 750finish_pass_phuff (j_compress_ptr cinfo) 751{ 752 phuff_entropy_ptr entropy = (phuff_entropy_ptr) cinfo->entropy; 753 754 entropy->next_output_byte = cinfo->dest->next_output_byte; 755 entropy->free_in_buffer = cinfo->dest->free_in_buffer; 756 757 /* Flush out any buffered data */ 758 emit_eobrun(entropy); 759 flush_bits(entropy); 760 761 cinfo->dest->next_output_byte = entropy->next_output_byte; 762 cinfo->dest->free_in_buffer = entropy->free_in_buffer; 763} 764 765 766/* 767 * Finish up a statistics-gathering pass and create the new Huffman tables. 768 */ 769 770METHODDEF(void) 771finish_pass_gather_phuff (j_compress_ptr cinfo) 772{ 773 phuff_entropy_ptr entropy = (phuff_entropy_ptr) cinfo->entropy; 774 boolean is_DC_band; 775 int ci, tbl; 776 jpeg_component_info * compptr; 777 JHUFF_TBL **htblptr; 778 boolean did[NUM_HUFF_TBLS]; 779 780 /* Flush out buffered data (all we care about is counting the EOB symbol) */ 781 emit_eobrun(entropy); 782 783 is_DC_band = (cinfo->Ss == 0); 784 785 /* It's important not to apply jpeg_gen_optimal_table more than once 786 * per table, because it clobbers the input frequency counts! 787 */ 788 MEMZERO(did, SIZEOF(did)); 789 790 for (ci = 0; ci < cinfo->comps_in_scan; ci++) { 791 compptr = cinfo->cur_comp_info[ci]; 792 if (is_DC_band) { 793 if (cinfo->Ah != 0) /* DC refinement needs no table */ 794 continue; 795 tbl = compptr->dc_tbl_no; 796 } else { 797 tbl = compptr->ac_tbl_no; 798 } 799 if (! did[tbl]) { 800 if (is_DC_band) 801 htblptr = & cinfo->dc_huff_tbl_ptrs[tbl]; 802 else 803 htblptr = & cinfo->ac_huff_tbl_ptrs[tbl]; 804 if (*htblptr == NULL) 805 *htblptr = jpeg_alloc_huff_table((j_common_ptr) cinfo); 806 jpeg_gen_optimal_table(cinfo, *htblptr, entropy->count_ptrs[tbl]); 807 did[tbl] = TRUE; 808 } 809 } 810} 811 812 813/* 814 * Module initialization routine for progressive Huffman entropy encoding. 815 */ 816 817GLOBAL(void) 818jinit_phuff_encoder (j_compress_ptr cinfo) 819{ 820 phuff_entropy_ptr entropy; 821 int i; 822 823 entropy = (phuff_entropy_ptr) 824 (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE, 825 SIZEOF(phuff_entropy_encoder)); 826 cinfo->entropy = (struct jpeg_entropy_encoder *) entropy; 827 entropy->pub.start_pass = start_pass_phuff; 828 829 /* Mark tables unallocated */ 830 for (i = 0; i < NUM_HUFF_TBLS; i++) { 831 entropy->derived_tbls[i] = NULL; 832 entropy->count_ptrs[i] = NULL; 833 } 834 entropy->bit_buffer = NULL; /* needed only in AC refinement scan */ 835} 836 837#endif /* C_PROGRESSIVE_SUPPORTED */ 838