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