1#if !defined(_FX_JPEG_TURBO_) 2/* 3 * jchuff.c 4 * 5 * Copyright (C) 1991-1997, Thomas G. Lane. 6 * This file is part of the Independent JPEG Group's software. 7 * For conditions of distribution and use, see the accompanying README file. 8 * 9 * This file contains Huffman entropy encoding routines. 10 * 11 * Much of the complexity here has to do with supporting output suspension. 12 * If the data destination module demands suspension, we want to be able to 13 * back up to the start of the current MCU. To do this, we copy state 14 * variables into local working storage, and update them back to the 15 * permanent JPEG objects only upon successful completion of an MCU. 16 */ 17 18#define JPEG_INTERNALS 19#include "jinclude.h" 20#include "jpeglib.h" 21#include "jchuff.h" /* Declarations shared with jcphuff.c */ 22 23#ifdef _FX_MANAGED_CODE_ 24#define savable_state savable_state_c 25#endif 26 27/* Expanded entropy encoder object for Huffman encoding. 28 * 29 * The savable_state subrecord contains fields that change within an MCU, 30 * but must not be updated permanently until we complete the MCU. 31 */ 32 33typedef struct { 34 INT32 put_buffer; /* current bit-accumulation buffer */ 35 int put_bits; /* # of bits now in it */ 36 int last_dc_val[MAX_COMPS_IN_SCAN]; /* last DC coef for each component */ 37} savable_state; 38 39/* This macro is to work around compilers with missing or broken 40 * structure assignment. You'll need to fix this code if you have 41 * such a compiler and you change MAX_COMPS_IN_SCAN. 42 */ 43 44#ifndef NO_STRUCT_ASSIGN 45#define ASSIGN_STATE(dest,src) ((dest) = (src)) 46#else 47#if MAX_COMPS_IN_SCAN == 4 48#define ASSIGN_STATE(dest,src) \ 49 ((dest).put_buffer = (src).put_buffer, \ 50 (dest).put_bits = (src).put_bits, \ 51 (dest).last_dc_val[0] = (src).last_dc_val[0], \ 52 (dest).last_dc_val[1] = (src).last_dc_val[1], \ 53 (dest).last_dc_val[2] = (src).last_dc_val[2], \ 54 (dest).last_dc_val[3] = (src).last_dc_val[3]) 55#endif 56#endif 57 58 59typedef struct { 60 struct jpeg_entropy_encoder pub; /* public fields */ 61 62 savable_state saved; /* Bit buffer & DC state at start of MCU */ 63 64 /* These fields are NOT loaded into local working state. */ 65 unsigned int restarts_to_go; /* MCUs left in this restart interval */ 66 int next_restart_num; /* next restart number to write (0-7) */ 67 68 /* Pointers to derived tables (these workspaces have image lifespan) */ 69 c_derived_tbl * dc_derived_tbls[NUM_HUFF_TBLS]; 70 c_derived_tbl * ac_derived_tbls[NUM_HUFF_TBLS]; 71 72#ifdef ENTROPY_OPT_SUPPORTED /* Statistics tables for optimization */ 73 long * dc_count_ptrs[NUM_HUFF_TBLS]; 74 long * ac_count_ptrs[NUM_HUFF_TBLS]; 75#endif 76} huff_entropy_encoder; 77 78typedef huff_entropy_encoder * huff_entropy_ptr; 79 80/* Working state while writing an MCU. 81 * This struct contains all the fields that are needed by subroutines. 82 */ 83 84typedef struct { 85 JOCTET * next_output_byte; /* => next byte to write in buffer */ 86 size_t free_in_buffer; /* # of byte spaces remaining in buffer */ 87 savable_state cur; /* Current bit buffer & DC state */ 88 j_compress_ptr cinfo; /* dump_buffer needs access to this */ 89} working_state; 90 91 92/* Forward declarations */ 93METHODDEF(boolean) encode_mcu_huff JPP((j_compress_ptr cinfo, 94 JBLOCKROW *MCU_data)); 95METHODDEF(void) finish_pass_huff JPP((j_compress_ptr cinfo)); 96#ifdef ENTROPY_OPT_SUPPORTED 97METHODDEF(boolean) encode_mcu_gather JPP((j_compress_ptr cinfo, 98 JBLOCKROW *MCU_data)); 99METHODDEF(void) finish_pass_gather JPP((j_compress_ptr cinfo)); 100#endif 101 102 103/* 104 * Initialize for a Huffman-compressed scan. 105 * If gather_statistics is TRUE, we do not output anything during the scan, 106 * just count the Huffman symbols used and generate Huffman code tables. 107 */ 108 109METHODDEF(void) 110start_pass_huff (j_compress_ptr cinfo, boolean gather_statistics) 111{ 112 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy; 113 int ci, dctbl, actbl; 114 jpeg_component_info * compptr; 115 116 if (gather_statistics) { 117#ifdef ENTROPY_OPT_SUPPORTED 118 entropy->pub.encode_mcu = encode_mcu_gather; 119 entropy->pub.finish_pass = finish_pass_gather; 120#else 121 ERREXIT(cinfo, JERR_NOT_COMPILED); 122#endif 123 } else { 124 entropy->pub.encode_mcu = encode_mcu_huff; 125 entropy->pub.finish_pass = finish_pass_huff; 126 } 127 128 for (ci = 0; ci < cinfo->comps_in_scan; ci++) { 129 compptr = cinfo->cur_comp_info[ci]; 130 dctbl = compptr->dc_tbl_no; 131 actbl = compptr->ac_tbl_no; 132 if (gather_statistics) { 133#ifdef ENTROPY_OPT_SUPPORTED 134 /* Check for invalid table indexes */ 135 /* (make_c_derived_tbl does this in the other path) */ 136 if (dctbl < 0 || dctbl >= NUM_HUFF_TBLS) 137 ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, dctbl); 138 if (actbl < 0 || actbl >= NUM_HUFF_TBLS) 139 ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, actbl); 140 /* Allocate and zero the statistics tables */ 141 /* Note that jpeg_gen_optimal_table expects 257 entries in each table! */ 142 if (entropy->dc_count_ptrs[dctbl] == NULL) 143 entropy->dc_count_ptrs[dctbl] = (long *) 144 (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE, 145 257 * SIZEOF(long)); 146 MEMZERO(entropy->dc_count_ptrs[dctbl], 257 * SIZEOF(long)); 147 if (entropy->ac_count_ptrs[actbl] == NULL) 148 entropy->ac_count_ptrs[actbl] = (long *) 149 (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE, 150 257 * SIZEOF(long)); 151 MEMZERO(entropy->ac_count_ptrs[actbl], 257 * SIZEOF(long)); 152#endif 153 } else { 154 /* Compute derived values for Huffman tables */ 155 /* We may do this more than once for a table, but it's not expensive */ 156 jpeg_make_c_derived_tbl(cinfo, TRUE, dctbl, 157 & entropy->dc_derived_tbls[dctbl]); 158 jpeg_make_c_derived_tbl(cinfo, FALSE, actbl, 159 & entropy->ac_derived_tbls[actbl]); 160 } 161 /* Initialize DC predictions to 0 */ 162 entropy->saved.last_dc_val[ci] = 0; 163 } 164 165 /* Initialize bit buffer to empty */ 166 entropy->saved.put_buffer = 0; 167 entropy->saved.put_bits = 0; 168 169 /* Initialize restart stuff */ 170 entropy->restarts_to_go = cinfo->restart_interval; 171 entropy->next_restart_num = 0; 172} 173 174 175/* 176 * Compute the derived values for a Huffman table. 177 * This routine also performs some validation checks on the table. 178 * 179 * Note this is also used by jcphuff.c. 180 */ 181 182GLOBAL(void) 183jpeg_make_c_derived_tbl (j_compress_ptr cinfo, boolean isDC, int tblno, 184 c_derived_tbl ** pdtbl) 185{ 186 JHUFF_TBL *htbl; 187 c_derived_tbl *dtbl; 188 int p, i, l, lastp, _si, maxsymbol; 189 char huffsize[257]; 190 unsigned int huffcode[257]; 191 unsigned int code; 192 193 /* Note that huffsize[] and huffcode[] are filled in code-length order, 194 * paralleling the order of the symbols themselves in htbl->huffval[]. 195 */ 196 197 /* Find the input Huffman table */ 198 if (tblno < 0 || tblno >= NUM_HUFF_TBLS) 199 ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tblno); 200 htbl = 201 isDC ? cinfo->dc_huff_tbl_ptrs[tblno] : cinfo->ac_huff_tbl_ptrs[tblno]; 202 if (htbl == NULL) 203 ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tblno); 204 205 /* Allocate a workspace if we haven't already done so. */ 206 if (*pdtbl == NULL) 207 *pdtbl = (c_derived_tbl *) 208 (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE, 209 SIZEOF(c_derived_tbl)); 210 dtbl = *pdtbl; 211 212 /* Figure C.1: make table of Huffman code length for each symbol */ 213 214 p = 0; 215 for (l = 1; l <= 16; l++) { 216 i = (int) htbl->bits[l]; 217 if (i < 0 || p + i > 256) /* protect against table overrun */ 218 ERREXIT(cinfo, JERR_BAD_HUFF_TABLE); 219 while (i--) 220 huffsize[p++] = (char) l; 221 } 222 huffsize[p] = 0; 223 lastp = p; 224 225 /* Figure C.2: generate the codes themselves */ 226 /* We also validate that the counts represent a legal Huffman code tree. */ 227 228 code = 0; 229 _si = huffsize[0]; 230 p = 0; 231 while (huffsize[p]) { 232 while (((int) huffsize[p]) == _si) { 233 huffcode[p++] = code; 234 code++; 235 } 236 /* code is now 1 more than the last code used for codelength si; but 237 * it must still fit in si bits, since no code is allowed to be all ones. 238 */ 239 if (((INT32) code) >= (((INT32) 1) << _si)) 240 ERREXIT(cinfo, JERR_BAD_HUFF_TABLE); 241 code <<= 1; 242 _si++; 243 } 244 245 /* Figure C.3: generate encoding tables */ 246 /* These are code and size indexed by symbol value */ 247 248 /* Set all codeless symbols to have code length 0; 249 * this lets us detect duplicate VAL entries here, and later 250 * allows emit_bits to detect any attempt to emit such symbols. 251 */ 252 MEMZERO(dtbl->ehufsi, SIZEOF(dtbl->ehufsi)); 253 254 /* This is also a convenient place to check for out-of-range 255 * and duplicated VAL entries. We allow 0..255 for AC symbols 256 * but only 0..15 for DC. (We could constrain them further 257 * based on data depth and mode, but this seems enough.) 258 */ 259 maxsymbol = isDC ? 15 : 255; 260 261 for (p = 0; p < lastp; p++) { 262 i = htbl->huffval[p]; 263 if (i < 0 || i > maxsymbol || dtbl->ehufsi[i]) 264 ERREXIT(cinfo, JERR_BAD_HUFF_TABLE); 265 dtbl->ehufco[i] = huffcode[p]; 266 dtbl->ehufsi[i] = huffsize[p]; 267 } 268} 269 270 271/* Outputting bytes to the file */ 272 273/* Emit a byte, taking 'action' if must suspend. */ 274#define emit_byte(state,val,action) \ 275 { *(state)->next_output_byte++ = (JOCTET) (val); \ 276 if (--(state)->free_in_buffer == 0) \ 277 if (! dump_buffer(state)) \ 278 { action; } } 279 280 281LOCAL(boolean) 282dump_buffer (working_state * state) 283/* Empty the output buffer; return TRUE if successful, FALSE if must suspend */ 284{ 285 struct jpeg_destination_mgr * dest = state->cinfo->dest; 286 287 if (! (*dest->empty_output_buffer) (state->cinfo)) 288 return FALSE; 289 /* After a successful buffer dump, must reset buffer pointers */ 290 state->next_output_byte = dest->next_output_byte; 291 state->free_in_buffer = dest->free_in_buffer; 292 return TRUE; 293} 294 295 296/* Outputting bits to the file */ 297 298/* Only the right 24 bits of put_buffer are used; the valid bits are 299 * left-justified in this part. At most 16 bits can be passed to emit_bits 300 * in one call, and we never retain more than 7 bits in put_buffer 301 * between calls, so 24 bits are sufficient. 302 */ 303 304INLINE 305LOCAL(boolean) 306emit_bits (working_state * state, unsigned int code, int size) 307/* Emit some bits; return TRUE if successful, FALSE if must suspend */ 308{ 309 /* This routine is heavily used, so it's worth coding tightly. */ 310 register INT32 put_buffer = (INT32) code; 311 register int put_bits = state->cur.put_bits; 312 313 /* if size is 0, caller used an invalid Huffman table entry */ 314 if (size == 0) 315 ERREXIT(state->cinfo, JERR_HUFF_MISSING_CODE); 316 317 put_buffer &= (((INT32) 1)<<size) - 1; /* mask off any extra bits in code */ 318 319 put_bits += size; /* new number of bits in buffer */ 320 321 put_buffer <<= 24 - put_bits; /* align incoming bits */ 322 323 put_buffer |= state->cur.put_buffer; /* and merge with old buffer contents */ 324 325 while (put_bits >= 8) { 326 int c = (int) ((put_buffer >> 16) & 0xFF); 327 328 emit_byte(state, c, return FALSE); 329 if (c == 0xFF) { /* need to stuff a zero byte? */ 330 emit_byte(state, 0, return FALSE); 331 } 332 put_buffer <<= 8; 333 put_bits -= 8; 334 } 335 336 state->cur.put_buffer = put_buffer; /* update state variables */ 337 state->cur.put_bits = put_bits; 338 339 return TRUE; 340} 341 342 343LOCAL(boolean) 344flush_bits (working_state * state) 345{ 346 if (! emit_bits(state, 0x7F, 7)) /* fill any partial byte with ones */ 347 return FALSE; 348 state->cur.put_buffer = 0; /* and reset bit-buffer to empty */ 349 state->cur.put_bits = 0; 350 return TRUE; 351} 352 353 354/* Encode a single block's worth of coefficients */ 355 356LOCAL(boolean) 357encode_one_block (working_state * state, JCOEFPTR block, int last_dc_val, 358 c_derived_tbl *dctbl, c_derived_tbl *actbl) 359{ 360 register int temp, temp2; 361 register int nbits; 362 register int k, r, i; 363 364 /* Encode the DC coefficient difference per section F.1.2.1 */ 365 366 temp = temp2 = block[0] - last_dc_val; 367 368 if (temp < 0) { 369 temp = -temp; /* temp is abs value of input */ 370 /* For a negative input, want temp2 = bitwise complement of abs(input) */ 371 /* This code assumes we are on a two's complement machine */ 372 temp2--; 373 } 374 375 /* Find the number of bits needed for the magnitude of the coefficient */ 376 nbits = 0; 377 while (temp) { 378 nbits++; 379 temp >>= 1; 380 } 381 /* Check for out-of-range coefficient values. 382 * Since we're encoding a difference, the range limit is twice as much. 383 */ 384 if (nbits > MAX_COEF_BITS+1) 385 ERREXIT(state->cinfo, JERR_BAD_DCT_COEF); 386 387 /* Emit the Huffman-coded symbol for the number of bits */ 388 if (! emit_bits(state, dctbl->ehufco[nbits], dctbl->ehufsi[nbits])) 389 return FALSE; 390 391 /* Emit that number of bits of the value, if positive, */ 392 /* or the complement of its magnitude, if negative. */ 393 if (nbits) /* emit_bits rejects calls with size 0 */ 394 if (! emit_bits(state, (unsigned int) temp2, nbits)) 395 return FALSE; 396 397 /* Encode the AC coefficients per section F.1.2.2 */ 398 399 r = 0; /* r = run length of zeros */ 400 401 for (k = 1; k < DCTSIZE2; k++) { 402 if ((temp = block[jpeg_natural_order[k]]) == 0) { 403 r++; 404 } else { 405 /* if run length > 15, must emit special run-length-16 codes (0xF0) */ 406 while (r > 15) { 407 if (! emit_bits(state, actbl->ehufco[0xF0], actbl->ehufsi[0xF0])) 408 return FALSE; 409 r -= 16; 410 } 411 412 temp2 = temp; 413 if (temp < 0) { 414 temp = -temp; /* temp is abs value of input */ 415 /* This code assumes we are on a two's complement machine */ 416 temp2--; 417 } 418 419 /* Find the number of bits needed for the magnitude of the coefficient */ 420 nbits = 1; /* there must be at least one 1 bit */ 421 while ((temp >>= 1)) 422 nbits++; 423 /* Check for out-of-range coefficient values */ 424 if (nbits > MAX_COEF_BITS) 425 ERREXIT(state->cinfo, JERR_BAD_DCT_COEF); 426 427 /* Emit Huffman symbol for run length / number of bits */ 428 i = (r << 4) + nbits; 429 if (! emit_bits(state, actbl->ehufco[i], actbl->ehufsi[i])) 430 return FALSE; 431 432 /* Emit that number of bits of the value, if positive, */ 433 /* or the complement of its magnitude, if negative. */ 434 if (! emit_bits(state, (unsigned int) temp2, nbits)) 435 return FALSE; 436 437 r = 0; 438 } 439 } 440 441 /* If the last coef(s) were zero, emit an end-of-block code */ 442 if (r > 0) 443 if (! emit_bits(state, actbl->ehufco[0], actbl->ehufsi[0])) 444 return FALSE; 445 446 return TRUE; 447} 448 449 450/* 451 * Emit a restart marker & resynchronize predictions. 452 */ 453 454LOCAL(boolean) 455emit_restart (working_state * state, int restart_num) 456{ 457 int ci; 458 459 if (! flush_bits(state)) 460 return FALSE; 461 462 emit_byte(state, 0xFF, return FALSE); 463 emit_byte(state, JPEG_RST0 + restart_num, return FALSE); 464 465 /* Re-initialize DC predictions to 0 */ 466 for (ci = 0; ci < state->cinfo->comps_in_scan; ci++) 467 state->cur.last_dc_val[ci] = 0; 468 469 /* The restart counter is not updated until we successfully write the MCU. */ 470 471 return TRUE; 472} 473 474 475/* 476 * Encode and output one MCU's worth of Huffman-compressed coefficients. 477 */ 478 479METHODDEF(boolean) 480encode_mcu_huff (j_compress_ptr cinfo, JBLOCKROW *MCU_data) 481{ 482 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy; 483 working_state state; 484 int blkn, ci; 485 jpeg_component_info * compptr; 486 487 /* Load up working state */ 488 state.next_output_byte = cinfo->dest->next_output_byte; 489 state.free_in_buffer = cinfo->dest->free_in_buffer; 490 ASSIGN_STATE(state.cur, entropy->saved); 491 state.cinfo = cinfo; 492 493 /* Emit restart marker if needed */ 494 if (cinfo->restart_interval) { 495 if (entropy->restarts_to_go == 0) 496 if (! emit_restart(&state, entropy->next_restart_num)) 497 return FALSE; 498 } 499 500 /* Encode the MCU data blocks */ 501 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) { 502 ci = cinfo->MCU_membership[blkn]; 503 compptr = cinfo->cur_comp_info[ci]; 504 if (! encode_one_block(&state, 505 MCU_data[blkn][0], state.cur.last_dc_val[ci], 506 entropy->dc_derived_tbls[compptr->dc_tbl_no], 507 entropy->ac_derived_tbls[compptr->ac_tbl_no])) 508 return FALSE; 509 /* Update last_dc_val */ 510 state.cur.last_dc_val[ci] = MCU_data[blkn][0][0]; 511 } 512 513 /* Completed MCU, so update state */ 514 cinfo->dest->next_output_byte = state.next_output_byte; 515 cinfo->dest->free_in_buffer = state.free_in_buffer; 516 ASSIGN_STATE(entropy->saved, state.cur); 517 518 /* Update restart-interval state too */ 519 if (cinfo->restart_interval) { 520 if (entropy->restarts_to_go == 0) { 521 entropy->restarts_to_go = cinfo->restart_interval; 522 entropy->next_restart_num++; 523 entropy->next_restart_num &= 7; 524 } 525 entropy->restarts_to_go--; 526 } 527 528 return TRUE; 529} 530 531 532/* 533 * Finish up at the end of a Huffman-compressed scan. 534 */ 535 536METHODDEF(void) 537finish_pass_huff (j_compress_ptr cinfo) 538{ 539 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy; 540 working_state state; 541 542 /* Load up working state ... flush_bits needs it */ 543 state.next_output_byte = cinfo->dest->next_output_byte; 544 state.free_in_buffer = cinfo->dest->free_in_buffer; 545 ASSIGN_STATE(state.cur, entropy->saved); 546 state.cinfo = cinfo; 547 548 /* Flush out the last data */ 549 if (! flush_bits(&state)) 550 ERREXIT(cinfo, JERR_CANT_SUSPEND); 551 552 /* Update state */ 553 cinfo->dest->next_output_byte = state.next_output_byte; 554 cinfo->dest->free_in_buffer = state.free_in_buffer; 555 ASSIGN_STATE(entropy->saved, state.cur); 556} 557 558 559/* 560 * Huffman coding optimization. 561 * 562 * We first scan the supplied data and count the number of uses of each symbol 563 * that is to be Huffman-coded. (This process MUST agree with the code above.) 564 * Then we build a Huffman coding tree for the observed counts. 565 * Symbols which are not needed at all for the particular image are not 566 * assigned any code, which saves space in the DHT marker as well as in 567 * the compressed data. 568 */ 569 570#ifdef ENTROPY_OPT_SUPPORTED 571 572 573/* Process a single block's worth of coefficients */ 574 575LOCAL(void) 576htest_one_block (j_compress_ptr cinfo, JCOEFPTR block, int last_dc_val, 577 long dc_counts[], long ac_counts[]) 578{ 579 register int temp; 580 register int nbits; 581 register int k, r; 582 583 /* Encode the DC coefficient difference per section F.1.2.1 */ 584 585 temp = block[0] - last_dc_val; 586 if (temp < 0) 587 temp = -temp; 588 589 /* Find the number of bits needed for the magnitude of the coefficient */ 590 nbits = 0; 591 while (temp) { 592 nbits++; 593 temp >>= 1; 594 } 595 /* Check for out-of-range coefficient values. 596 * Since we're encoding a difference, the range limit is twice as much. 597 */ 598 if (nbits > MAX_COEF_BITS+1) 599 ERREXIT(cinfo, JERR_BAD_DCT_COEF); 600 601 /* Count the Huffman symbol for the number of bits */ 602 dc_counts[nbits]++; 603 604 /* Encode the AC coefficients per section F.1.2.2 */ 605 606 r = 0; /* r = run length of zeros */ 607 608 for (k = 1; k < DCTSIZE2; k++) { 609 if ((temp = block[jpeg_natural_order[k]]) == 0) { 610 r++; 611 } else { 612 /* if run length > 15, must emit special run-length-16 codes (0xF0) */ 613 while (r > 15) { 614 ac_counts[0xF0]++; 615 r -= 16; 616 } 617 618 /* Find the number of bits needed for the magnitude of the coefficient */ 619 if (temp < 0) 620 temp = -temp; 621 622 /* Find the number of bits needed for the magnitude of the coefficient */ 623 nbits = 1; /* there must be at least one 1 bit */ 624 while ((temp >>= 1)) 625 nbits++; 626 /* Check for out-of-range coefficient values */ 627 if (nbits > MAX_COEF_BITS) 628 ERREXIT(cinfo, JERR_BAD_DCT_COEF); 629 630 /* Count Huffman symbol for run length / number of bits */ 631 ac_counts[(r << 4) + nbits]++; 632 633 r = 0; 634 } 635 } 636 637 /* If the last coef(s) were zero, emit an end-of-block code */ 638 if (r > 0) 639 ac_counts[0]++; 640} 641 642 643/* 644 * Trial-encode one MCU's worth of Huffman-compressed coefficients. 645 * No data is actually output, so no suspension return is possible. 646 */ 647 648METHODDEF(boolean) 649encode_mcu_gather (j_compress_ptr cinfo, JBLOCKROW *MCU_data) 650{ 651 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy; 652 int blkn, ci; 653 jpeg_component_info * compptr; 654 655 /* Take care of restart intervals if needed */ 656 if (cinfo->restart_interval) { 657 if (entropy->restarts_to_go == 0) { 658 /* Re-initialize DC predictions to 0 */ 659 for (ci = 0; ci < cinfo->comps_in_scan; ci++) 660 entropy->saved.last_dc_val[ci] = 0; 661 /* Update restart state */ 662 entropy->restarts_to_go = cinfo->restart_interval; 663 } 664 entropy->restarts_to_go--; 665 } 666 667 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) { 668 ci = cinfo->MCU_membership[blkn]; 669 compptr = cinfo->cur_comp_info[ci]; 670 htest_one_block(cinfo, MCU_data[blkn][0], entropy->saved.last_dc_val[ci], 671 entropy->dc_count_ptrs[compptr->dc_tbl_no], 672 entropy->ac_count_ptrs[compptr->ac_tbl_no]); 673 entropy->saved.last_dc_val[ci] = MCU_data[blkn][0][0]; 674 } 675 676 return TRUE; 677} 678 679 680/* 681 * Generate the best Huffman code table for the given counts, fill htbl. 682 * Note this is also used by jcphuff.c. 683 * 684 * The JPEG standard requires that no symbol be assigned a codeword of all 685 * one bits (so that padding bits added at the end of a compressed segment 686 * can't look like a valid code). Because of the canonical ordering of 687 * codewords, this just means that there must be an unused slot in the 688 * longest codeword length category. Section K.2 of the JPEG spec suggests 689 * reserving such a slot by pretending that symbol 256 is a valid symbol 690 * with count 1. In theory that's not optimal; giving it count zero but 691 * including it in the symbol set anyway should give a better Huffman code. 692 * But the theoretically better code actually seems to come out worse in 693 * practice, because it produces more all-ones bytes (which incur stuffed 694 * zero bytes in the final file). In any case the difference is tiny. 695 * 696 * The JPEG standard requires Huffman codes to be no more than 16 bits long. 697 * If some symbols have a very small but nonzero probability, the Huffman tree 698 * must be adjusted to meet the code length restriction. We currently use 699 * the adjustment method suggested in JPEG section K.2. This method is *not* 700 * optimal; it may not choose the best possible limited-length code. But 701 * typically only very-low-frequency symbols will be given less-than-optimal 702 * lengths, so the code is almost optimal. Experimental comparisons against 703 * an optimal limited-length-code algorithm indicate that the difference is 704 * microscopic --- usually less than a hundredth of a percent of total size. 705 * So the extra complexity of an optimal algorithm doesn't seem worthwhile. 706 */ 707 708GLOBAL(void) 709jpeg_gen_optimal_table (j_compress_ptr cinfo, JHUFF_TBL * htbl, long freq[]) 710{ 711#define MAX_CLEN 32 /* assumed maximum initial code length */ 712 UINT8 bits[MAX_CLEN+1]; /* bits[k] = # of symbols with code length k */ 713 int codesize[257]; /* codesize[k] = code length of symbol k */ 714 int others[257]; /* next symbol in current branch of tree */ 715 int c1, c2; 716 int p, i, j; 717 long v; 718 719 /* This algorithm is explained in section K.2 of the JPEG standard */ 720 721 MEMZERO(bits, SIZEOF(bits)); 722 MEMZERO(codesize, SIZEOF(codesize)); 723 for (i = 0; i < 257; i++) 724 others[i] = -1; /* init links to empty */ 725 726 freq[256] = 1; /* make sure 256 has a nonzero count */ 727 /* Including the pseudo-symbol 256 in the Huffman procedure guarantees 728 * that no real symbol is given code-value of all ones, because 256 729 * will be placed last in the largest codeword category. 730 */ 731 732 /* Huffman's basic algorithm to assign optimal code lengths to symbols */ 733 734 for (;;) { 735 /* Find the smallest nonzero frequency, set c1 = its symbol */ 736 /* In case of ties, take the larger symbol number */ 737 c1 = -1; 738 v = 1000000000L; 739 for (i = 0; i <= 256; i++) { 740 if (freq[i] && freq[i] <= v) { 741 v = freq[i]; 742 c1 = i; 743 } 744 } 745 746 /* Find the next smallest nonzero frequency, set c2 = its symbol */ 747 /* In case of ties, take the larger symbol number */ 748 c2 = -1; 749 v = 1000000000L; 750 for (i = 0; i <= 256; i++) { 751 if (freq[i] && freq[i] <= v && i != c1) { 752 v = freq[i]; 753 c2 = i; 754 } 755 } 756 757 /* Done if we've merged everything into one frequency */ 758 if (c2 < 0) 759 break; 760 761 /* Else merge the two counts/trees */ 762 freq[c1] += freq[c2]; 763 freq[c2] = 0; 764 765 /* Increment the codesize of everything in c1's tree branch */ 766 codesize[c1]++; 767 while (others[c1] >= 0) { 768 c1 = others[c1]; 769 codesize[c1]++; 770 } 771 772 others[c1] = c2; /* chain c2 onto c1's tree branch */ 773 774 /* Increment the codesize of everything in c2's tree branch */ 775 codesize[c2]++; 776 while (others[c2] >= 0) { 777 c2 = others[c2]; 778 codesize[c2]++; 779 } 780 } 781 782 /* Now count the number of symbols of each code length */ 783 for (i = 0; i <= 256; i++) { 784 if (codesize[i]) { 785 /* The JPEG standard seems to think that this can't happen, */ 786 /* but I'm paranoid... */ 787 if (codesize[i] > MAX_CLEN) 788 ERREXIT(cinfo, JERR_HUFF_CLEN_OVERFLOW); 789 790 bits[codesize[i]]++; 791 } 792 } 793 794 /* JPEG doesn't allow symbols with code lengths over 16 bits, so if the pure 795 * Huffman procedure assigned any such lengths, we must adjust the coding. 796 * Here is what the JPEG spec says about how this next bit works: 797 * Since symbols are paired for the longest Huffman code, the symbols are 798 * removed from this length category two at a time. The prefix for the pair 799 * (which is one bit shorter) is allocated to one of the pair; then, 800 * skipping the BITS entry for that prefix length, a code word from the next 801 * shortest nonzero BITS entry is converted into a prefix for two code words 802 * one bit longer. 803 */ 804 805 for (i = MAX_CLEN; i > 16; i--) { 806 while (bits[i] > 0) { 807 j = i - 2; /* find length of new prefix to be used */ 808 while (bits[j] == 0) 809 j--; 810 811 bits[i] -= 2; /* remove two symbols */ 812 bits[i-1]++; /* one goes in this length */ 813 bits[j+1] += 2; /* two new symbols in this length */ 814 bits[j]--; /* symbol of this length is now a prefix */ 815 } 816 } 817 818 /* Remove the count for the pseudo-symbol 256 from the largest codelength */ 819 while (bits[i] == 0) /* find largest codelength still in use */ 820 i--; 821 bits[i]--; 822 823 /* Return final symbol counts (only for lengths 0..16) */ 824 MEMCOPY(htbl->bits, bits, SIZEOF(htbl->bits)); 825 826 /* Return a list of the symbols sorted by code length */ 827 /* It's not real clear to me why we don't need to consider the codelength 828 * changes made above, but the JPEG spec seems to think this works. 829 */ 830 p = 0; 831 for (i = 1; i <= MAX_CLEN; i++) { 832 for (j = 0; j <= 255; j++) { 833 if (codesize[j] == i) { 834 htbl->huffval[p] = (UINT8) j; 835 p++; 836 } 837 } 838 } 839 840 /* Set sent_table FALSE so updated table will be written to JPEG file. */ 841 htbl->sent_table = FALSE; 842} 843 844 845/* 846 * Finish up a statistics-gathering pass and create the new Huffman tables. 847 */ 848 849METHODDEF(void) 850finish_pass_gather (j_compress_ptr cinfo) 851{ 852 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy; 853 int ci, dctbl, actbl; 854 jpeg_component_info * compptr; 855 JHUFF_TBL **htblptr; 856 boolean did_dc[NUM_HUFF_TBLS]; 857 boolean did_ac[NUM_HUFF_TBLS]; 858 859 /* It's important not to apply jpeg_gen_optimal_table more than once 860 * per table, because it clobbers the input frequency counts! 861 */ 862 MEMZERO(did_dc, SIZEOF(did_dc)); 863 MEMZERO(did_ac, SIZEOF(did_ac)); 864 865 for (ci = 0; ci < cinfo->comps_in_scan; ci++) { 866 compptr = cinfo->cur_comp_info[ci]; 867 dctbl = compptr->dc_tbl_no; 868 actbl = compptr->ac_tbl_no; 869 if (! did_dc[dctbl]) { 870 htblptr = & cinfo->dc_huff_tbl_ptrs[dctbl]; 871 if (*htblptr == NULL) 872 *htblptr = jpeg_alloc_huff_table((j_common_ptr) cinfo); 873 jpeg_gen_optimal_table(cinfo, *htblptr, entropy->dc_count_ptrs[dctbl]); 874 did_dc[dctbl] = TRUE; 875 } 876 if (! did_ac[actbl]) { 877 htblptr = & cinfo->ac_huff_tbl_ptrs[actbl]; 878 if (*htblptr == NULL) 879 *htblptr = jpeg_alloc_huff_table((j_common_ptr) cinfo); 880 jpeg_gen_optimal_table(cinfo, *htblptr, entropy->ac_count_ptrs[actbl]); 881 did_ac[actbl] = TRUE; 882 } 883 } 884} 885 886 887#endif /* ENTROPY_OPT_SUPPORTED */ 888 889 890/* 891 * Module initialization routine for Huffman entropy encoding. 892 */ 893 894GLOBAL(void) 895jinit_huff_encoder (j_compress_ptr cinfo) 896{ 897 huff_entropy_ptr entropy; 898 int i; 899 900 entropy = (huff_entropy_ptr) 901 (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE, 902 SIZEOF(huff_entropy_encoder)); 903 cinfo->entropy = (struct jpeg_entropy_encoder *) entropy; 904 entropy->pub.start_pass = start_pass_huff; 905 906 /* Mark tables unallocated */ 907 for (i = 0; i < NUM_HUFF_TBLS; i++) { 908 entropy->dc_derived_tbls[i] = entropy->ac_derived_tbls[i] = NULL; 909#ifdef ENTROPY_OPT_SUPPORTED 910 entropy->dc_count_ptrs[i] = entropy->ac_count_ptrs[i] = NULL; 911#endif 912 } 913} 914 915#endif //_FX_JPEG_TURBO_ 916