1 /* 2 * jchuff.c 3 * 4 * Copyright (C) 1991-1997, Thomas G. Lane. 5 * Modified 2006-2009 by Guido Vollbeding. 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 * Both sequential and progressive modes are supported in this single module. 11 * 12 * Much of the complexity here has to do with supporting output suspension. 13 * If the data destination module demands suspension, we want to be able to 14 * back up to the start of the current MCU. To do this, we copy state 15 * variables into local working storage, and update them back to the 16 * permanent JPEG objects only upon successful completion of an MCU. 17 * 18 * We do not support output suspension for the progressive JPEG mode, since 19 * the library currently does not allow multiple-scan files to be written 20 * with output suspension. 21 */ 22 23 #define JPEG_INTERNALS 24 #include "jinclude.h" 25 #include "jpeglib.h" 26 27 28 /* The legal range of a DCT coefficient is 29 * -1024 .. +1023 for 8-bit data; 30 * -16384 .. +16383 for 12-bit data. 31 * Hence the magnitude should always fit in 10 or 14 bits respectively. 32 */ 33 34 #if BITS_IN_JSAMPLE == 8 35 #define MAX_COEF_BITS 10 36 #else 37 #define MAX_COEF_BITS 14 38 #endif 39 40 /* Derived data constructed for each Huffman table */ 41 42 typedef struct { 43 unsigned int ehufco[256]; /* code for each symbol */ 44 char ehufsi[256]; /* length of code for each symbol */ 45 /* If no code has been allocated for a symbol S, ehufsi[S] contains 0 */ 46 } c_derived_tbl; 47 48 49 /* Expanded entropy encoder object for Huffman encoding. 50 * 51 * The savable_state subrecord contains fields that change within an MCU, 52 * but must not be updated permanently until we complete the MCU. 53 */ 54 55 typedef struct { 56 INT32 put_buffer; /* current bit-accumulation buffer */ 57 int put_bits; /* # of bits now in it */ 58 int last_dc_val[MAX_COMPS_IN_SCAN]; /* last DC coef for each component */ 59 } savable_state; 60 61 /* This macro is to work around compilers with missing or broken 62 * structure assignment. You'll need to fix this code if you have 63 * such a compiler and you change MAX_COMPS_IN_SCAN. 64 */ 65 66 #ifndef NO_STRUCT_ASSIGN 67 #define ASSIGN_STATE(dest,src) ((dest) = (src)) 68 #else 69 #if MAX_COMPS_IN_SCAN == 4 70 #define ASSIGN_STATE(dest,src) \ 71 ((dest).put_buffer = (src).put_buffer, \ 72 (dest).put_bits = (src).put_bits, \ 73 (dest).last_dc_val[0] = (src).last_dc_val[0], \ 74 (dest).last_dc_val[1] = (src).last_dc_val[1], \ 75 (dest).last_dc_val[2] = (src).last_dc_val[2], \ 76 (dest).last_dc_val[3] = (src).last_dc_val[3]) 77 #endif 78 #endif 79 80 81 typedef struct { 82 struct jpeg_entropy_encoder pub; /* public fields */ 83 84 savable_state saved; /* Bit buffer & DC state at start of MCU */ 85 86 /* These fields are NOT loaded into local working state. */ 87 unsigned int restarts_to_go; /* MCUs left in this restart interval */ 88 int next_restart_num; /* next restart number to write (0-7) */ 89 90 /* Pointers to derived tables (these workspaces have image lifespan) */ 91 c_derived_tbl * dc_derived_tbls[NUM_HUFF_TBLS]; 92 c_derived_tbl * ac_derived_tbls[NUM_HUFF_TBLS]; 93 94 /* Statistics tables for optimization */ 95 long * dc_count_ptrs[NUM_HUFF_TBLS]; 96 long * ac_count_ptrs[NUM_HUFF_TBLS]; 97 98 /* Following fields used only in progressive mode */ 99 100 /* Mode flag: TRUE for optimization, FALSE for actual data output */ 101 boolean gather_statistics; 102 103 /* next_output_byte/free_in_buffer are local copies of cinfo->dest fields. 104 */ 105 JOCTET * next_output_byte; /* => next byte to write in buffer */ 106 size_t free_in_buffer; /* # of byte spaces remaining in buffer */ 107 j_compress_ptr cinfo; /* link to cinfo (needed for dump_buffer) */ 108 109 /* Coding status for AC components */ 110 int ac_tbl_no; /* the table number of the single component */ 111 unsigned int EOBRUN; /* run length of EOBs */ 112 unsigned int BE; /* # of buffered correction bits before MCU */ 113 char * bit_buffer; /* buffer for correction bits (1 per char) */ 114 /* packing correction bits tightly would save some space but cost time... */ 115 } huff_entropy_encoder; 116 117 typedef huff_entropy_encoder * huff_entropy_ptr; 118 119 /* Working state while writing an MCU (sequential mode). 120 * This struct contains all the fields that are needed by subroutines. 121 */ 122 123 typedef struct { 124 JOCTET * next_output_byte; /* => next byte to write in buffer */ 125 size_t free_in_buffer; /* # of byte spaces remaining in buffer */ 126 savable_state cur; /* Current bit buffer & DC state */ 127 j_compress_ptr cinfo; /* dump_buffer needs access to this */ 128 } working_state; 129 130 /* MAX_CORR_BITS is the number of bits the AC refinement correction-bit 131 * buffer can hold. Larger sizes may slightly improve compression, but 132 * 1000 is already well into the realm of overkill. 133 * The minimum safe size is 64 bits. 134 */ 135 136 #define MAX_CORR_BITS 1000 /* Max # of correction bits I can buffer */ 137 138 /* IRIGHT_SHIFT is like RIGHT_SHIFT, but works on int rather than INT32. 139 * We assume that int right shift is unsigned if INT32 right shift is, 140 * which should be safe. 141 */ 142 143 #ifdef RIGHT_SHIFT_IS_UNSIGNED 144 #define ISHIFT_TEMPS int ishift_temp; 145 #define IRIGHT_SHIFT(x,shft) \ 146 ((ishift_temp = (x)) < 0 ? \ 147 (ishift_temp >> (shft)) | ((~0) << (16-(shft))) : \ 148 (ishift_temp >> (shft))) 149 #else 150 #define ISHIFT_TEMPS 151 #define IRIGHT_SHIFT(x,shft) ((x) >> (shft)) 152 #endif 153 154 155 /* 156 * Compute the derived values for a Huffman table. 157 * This routine also performs some validation checks on the table. 158 */ 159 160 LOCAL(void) 161 jpeg_make_c_derived_tbl (j_compress_ptr cinfo, boolean isDC, int tblno, 162 c_derived_tbl ** pdtbl) 163 { 164 JHUFF_TBL *htbl; 165 c_derived_tbl *dtbl; 166 int p, i, l, lastp, si, maxsymbol; 167 char huffsize[257]; 168 unsigned int huffcode[257]; 169 unsigned int code; 170 171 /* Note that huffsize[] and huffcode[] are filled in code-length order, 172 * paralleling the order of the symbols themselves in htbl->huffval[]. 173 */ 174 175 /* Find the input Huffman table */ 176 if (tblno < 0 || tblno >= NUM_HUFF_TBLS) 177 ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tblno); 178 htbl = 179 isDC ? cinfo->dc_huff_tbl_ptrs[tblno] : cinfo->ac_huff_tbl_ptrs[tblno]; 180 if (htbl == NULL) 181 ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tblno); 182 183 /* Allocate a workspace if we haven't already done so. */ 184 if (*pdtbl == NULL) 185 *pdtbl = (c_derived_tbl *) 186 (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE, 187 SIZEOF(c_derived_tbl)); 188 dtbl = *pdtbl; 189 190 /* Figure C.1: make table of Huffman code length for each symbol */ 191 192 p = 0; 193 for (l = 1; l <= 16; l++) { 194 i = (int) htbl->bits[l]; 195 if (i < 0 || p + i > 256) /* protect against table overrun */ 196 ERREXIT(cinfo, JERR_BAD_HUFF_TABLE); 197 while (i--) 198 huffsize[p++] = (char) l; 199 } 200 huffsize[p] = 0; 201 lastp = p; 202 203 /* Figure C.2: generate the codes themselves */ 204 /* We also validate that the counts represent a legal Huffman code tree. */ 205 206 code = 0; 207 si = huffsize[0]; 208 p = 0; 209 while (huffsize[p]) { 210 while (((int) huffsize[p]) == si) { 211 huffcode[p++] = code; 212 code++; 213 } 214 /* code is now 1 more than the last code used for codelength si; but 215 * it must still fit in si bits, since no code is allowed to be all ones. 216 */ 217 if (((INT32) code) >= (((INT32) 1) << si)) 218 ERREXIT(cinfo, JERR_BAD_HUFF_TABLE); 219 code <<= 1; 220 si++; 221 } 222 223 /* Figure C.3: generate encoding tables */ 224 /* These are code and size indexed by symbol value */ 225 226 /* Set all codeless symbols to have code length 0; 227 * this lets us detect duplicate VAL entries here, and later 228 * allows emit_bits to detect any attempt to emit such symbols. 229 */ 230 MEMZERO(dtbl->ehufsi, SIZEOF(dtbl->ehufsi)); 231 232 /* This is also a convenient place to check for out-of-range 233 * and duplicated VAL entries. We allow 0..255 for AC symbols 234 * but only 0..15 for DC. (We could constrain them further 235 * based on data depth and mode, but this seems enough.) 236 */ 237 maxsymbol = isDC ? 15 : 255; 238 239 for (p = 0; p < lastp; p++) { 240 i = htbl->huffval[p]; 241 if (i < 0 || i > maxsymbol || dtbl->ehufsi[i]) 242 ERREXIT(cinfo, JERR_BAD_HUFF_TABLE); 243 dtbl->ehufco[i] = huffcode[p]; 244 dtbl->ehufsi[i] = huffsize[p]; 245 } 246 } 247 248 249 /* Outputting bytes to the file. 250 * NB: these must be called only when actually outputting, 251 * that is, entropy->gather_statistics == FALSE. 252 */ 253 254 /* Emit a byte, taking 'action' if must suspend. */ 255 #define emit_byte_s(state,val,action) \ 256 { *(state)->next_output_byte++ = (JOCTET) (val); \ 257 if (--(state)->free_in_buffer == 0) \ 258 if (! dump_buffer_s(state)) \ 259 { action; } } 260 261 /* Emit a byte */ 262 #define emit_byte_e(entropy,val) \ 263 { *(entropy)->next_output_byte++ = (JOCTET) (val); \ 264 if (--(entropy)->free_in_buffer == 0) \ 265 dump_buffer_e(entropy); } 266 267 268 LOCAL(boolean) 269 dump_buffer_s (working_state * state) 270 /* Empty the output buffer; return TRUE if successful, FALSE if must suspend */ 271 { 272 struct jpeg_destination_mgr * dest = state->cinfo->dest; 273 274 if (! (*dest->empty_output_buffer) (state->cinfo)) 275 return FALSE; 276 /* After a successful buffer dump, must reset buffer pointers */ 277 state->next_output_byte = dest->next_output_byte; 278 state->free_in_buffer = dest->free_in_buffer; 279 return TRUE; 280 } 281 282 283 LOCAL(void) 284 dump_buffer_e (huff_entropy_ptr entropy) 285 /* Empty the output buffer; we do not support suspension in this case. */ 286 { 287 struct jpeg_destination_mgr * dest = entropy->cinfo->dest; 288 289 if (! (*dest->empty_output_buffer) (entropy->cinfo)) 290 ERREXIT(entropy->cinfo, JERR_CANT_SUSPEND); 291 /* After a successful buffer dump, must reset buffer pointers */ 292 entropy->next_output_byte = dest->next_output_byte; 293 entropy->free_in_buffer = dest->free_in_buffer; 294 } 295 296 297 /* Outputting bits to the file */ 298 299 /* Only the right 24 bits of put_buffer are used; the valid bits are 300 * left-justified in this part. At most 16 bits can be passed to emit_bits 301 * in one call, and we never retain more than 7 bits in put_buffer 302 * between calls, so 24 bits are sufficient. 303 */ 304 305 INLINE 306 LOCAL(boolean) 307 emit_bits_s (working_state * state, unsigned int code, int size) 308 /* Emit some bits; return TRUE if successful, FALSE if must suspend */ 309 { 310 /* This routine is heavily used, so it's worth coding tightly. */ 311 register INT32 put_buffer = (INT32) code; 312 register int put_bits = state->cur.put_bits; 313 314 /* if size is 0, caller used an invalid Huffman table entry */ 315 if (size == 0) 316 ERREXIT(state->cinfo, JERR_HUFF_MISSING_CODE); 317 318 put_buffer &= (((INT32) 1)<<size) - 1; /* mask off any extra bits in code */ 319 320 put_bits += size; /* new number of bits in buffer */ 321 322 put_buffer <<= 24 - put_bits; /* align incoming bits */ 323 324 put_buffer |= state->cur.put_buffer; /* and merge with old buffer contents */ 325 326 while (put_bits >= 8) { 327 int c = (int) ((put_buffer >> 16) & 0xFF); 328 329 emit_byte_s(state, c, return FALSE); 330 if (c == 0xFF) { /* need to stuff a zero byte? */ 331 emit_byte_s(state, 0, return FALSE); 332 } 333 put_buffer <<= 8; 334 put_bits -= 8; 335 } 336 337 state->cur.put_buffer = put_buffer; /* update state variables */ 338 state->cur.put_bits = put_bits; 339 340 return TRUE; 341 } 342 343 344 INLINE 345 LOCAL(void) 346 emit_bits_e (huff_entropy_ptr entropy, unsigned int code, int size) 347 /* Emit some bits, unless we are in gather mode */ 348 { 349 /* This routine is heavily used, so it's worth coding tightly. */ 350 register INT32 put_buffer = (INT32) code; 351 register int put_bits = entropy->saved.put_bits; 352 353 /* if size is 0, caller used an invalid Huffman table entry */ 354 if (size == 0) 355 ERREXIT(entropy->cinfo, JERR_HUFF_MISSING_CODE); 356 357 if (entropy->gather_statistics) 358 return; /* do nothing if we're only getting stats */ 359 360 put_buffer &= (((INT32) 1)<<size) - 1; /* mask off any extra bits in code */ 361 362 put_bits += size; /* new number of bits in buffer */ 363 364 put_buffer <<= 24 - put_bits; /* align incoming bits */ 365 366 /* and merge with old buffer contents */ 367 put_buffer |= entropy->saved.put_buffer; 368 369 while (put_bits >= 8) { 370 int c = (int) ((put_buffer >> 16) & 0xFF); 371 372 emit_byte_e(entropy, c); 373 if (c == 0xFF) { /* need to stuff a zero byte? */ 374 emit_byte_e(entropy, 0); 375 } 376 put_buffer <<= 8; 377 put_bits -= 8; 378 } 379 380 entropy->saved.put_buffer = put_buffer; /* update variables */ 381 entropy->saved.put_bits = put_bits; 382 } 383 384 385 LOCAL(boolean) 386 flush_bits_s (working_state * state) 387 { 388 if (! emit_bits_s(state, 0x7F, 7)) /* fill any partial byte with ones */ 389 return FALSE; 390 state->cur.put_buffer = 0; /* and reset bit-buffer to empty */ 391 state->cur.put_bits = 0; 392 return TRUE; 393 } 394 395 396 LOCAL(void) 397 flush_bits_e (huff_entropy_ptr entropy) 398 { 399 emit_bits_e(entropy, 0x7F, 7); /* fill any partial byte with ones */ 400 entropy->saved.put_buffer = 0; /* and reset bit-buffer to empty */ 401 entropy->saved.put_bits = 0; 402 } 403 404 405 /* 406 * Emit (or just count) a Huffman symbol. 407 */ 408 409 INLINE 410 LOCAL(void) 411 emit_dc_symbol (huff_entropy_ptr entropy, int tbl_no, int symbol) 412 { 413 if (entropy->gather_statistics) 414 entropy->dc_count_ptrs[tbl_no][symbol]++; 415 else { 416 c_derived_tbl * tbl = entropy->dc_derived_tbls[tbl_no]; 417 emit_bits_e(entropy, tbl->ehufco[symbol], tbl->ehufsi[symbol]); 418 } 419 } 420 421 422 INLINE 423 LOCAL(void) 424 emit_ac_symbol (huff_entropy_ptr entropy, int tbl_no, int symbol) 425 { 426 if (entropy->gather_statistics) 427 entropy->ac_count_ptrs[tbl_no][symbol]++; 428 else { 429 c_derived_tbl * tbl = entropy->ac_derived_tbls[tbl_no]; 430 emit_bits_e(entropy, tbl->ehufco[symbol], tbl->ehufsi[symbol]); 431 } 432 } 433 434 435 /* 436 * Emit bits from a correction bit buffer. 437 */ 438 439 LOCAL(void) 440 emit_buffered_bits (huff_entropy_ptr entropy, char * bufstart, 441 unsigned int nbits) 442 { 443 if (entropy->gather_statistics) 444 return; /* no real work */ 445 446 while (nbits > 0) { 447 emit_bits_e(entropy, (unsigned int) (*bufstart), 1); 448 bufstart++; 449 nbits--; 450 } 451 } 452 453 454 /* 455 * Emit any pending EOBRUN symbol. 456 */ 457 458 LOCAL(void) 459 emit_eobrun (huff_entropy_ptr entropy) 460 { 461 register int temp, nbits; 462 463 if (entropy->EOBRUN > 0) { /* if there is any pending EOBRUN */ 464 temp = entropy->EOBRUN; 465 nbits = 0; 466 while ((temp >>= 1)) 467 nbits++; 468 /* safety check: shouldn't happen given limited correction-bit buffer */ 469 if (nbits > 14) 470 ERREXIT(entropy->cinfo, JERR_HUFF_MISSING_CODE); 471 472 emit_ac_symbol(entropy, entropy->ac_tbl_no, nbits << 4); 473 if (nbits) 474 emit_bits_e(entropy, entropy->EOBRUN, nbits); 475 476 entropy->EOBRUN = 0; 477 478 /* Emit any buffered correction bits */ 479 emit_buffered_bits(entropy, entropy->bit_buffer, entropy->BE); 480 entropy->BE = 0; 481 } 482 } 483 484 485 /* 486 * Emit a restart marker & resynchronize predictions. 487 */ 488 489 LOCAL(boolean) 490 emit_restart_s (working_state * state, int restart_num) 491 { 492 int ci; 493 494 if (! flush_bits_s(state)) 495 return FALSE; 496 497 emit_byte_s(state, 0xFF, return FALSE); 498 emit_byte_s(state, JPEG_RST0 + restart_num, return FALSE); 499 500 /* Re-initialize DC predictions to 0 */ 501 for (ci = 0; ci < state->cinfo->comps_in_scan; ci++) 502 state->cur.last_dc_val[ci] = 0; 503 504 /* The restart counter is not updated until we successfully write the MCU. */ 505 506 return TRUE; 507 } 508 509 510 LOCAL(void) 511 emit_restart_e (huff_entropy_ptr entropy, int restart_num) 512 { 513 int ci; 514 515 emit_eobrun(entropy); 516 517 if (! entropy->gather_statistics) { 518 flush_bits_e(entropy); 519 emit_byte_e(entropy, 0xFF); 520 emit_byte_e(entropy, JPEG_RST0 + restart_num); 521 } 522 523 if (entropy->cinfo->Ss == 0) { 524 /* Re-initialize DC predictions to 0 */ 525 for (ci = 0; ci < entropy->cinfo->comps_in_scan; ci++) 526 entropy->saved.last_dc_val[ci] = 0; 527 } else { 528 /* Re-initialize all AC-related fields to 0 */ 529 entropy->EOBRUN = 0; 530 entropy->BE = 0; 531 } 532 } 533 534 535 /* 536 * MCU encoding for DC initial scan (either spectral selection, 537 * or first pass of successive approximation). 538 */ 539 540 METHODDEF(boolean) 541 encode_mcu_DC_first (j_compress_ptr cinfo, JBLOCKROW *MCU_data) 542 { 543 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy; 544 register int temp, temp2; 545 register int nbits; 546 int blkn, ci; 547 int Al = cinfo->Al; 548 JBLOCKROW block; 549 jpeg_component_info * compptr; 550 ISHIFT_TEMPS 551 552 entropy->next_output_byte = cinfo->dest->next_output_byte; 553 entropy->free_in_buffer = cinfo->dest->free_in_buffer; 554 555 /* Emit restart marker if needed */ 556 if (cinfo->restart_interval) 557 if (entropy->restarts_to_go == 0) 558 emit_restart_e(entropy, entropy->next_restart_num); 559 560 /* Encode the MCU data blocks */ 561 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) { 562 block = MCU_data[blkn]; 563 ci = cinfo->MCU_membership[blkn]; 564 compptr = cinfo->cur_comp_info[ci]; 565 566 /* Compute the DC value after the required point transform by Al. 567 * This is simply an arithmetic right shift. 568 */ 569 temp2 = IRIGHT_SHIFT((int) ((*block)[0]), Al); 570 571 /* DC differences are figured on the point-transformed values. */ 572 temp = temp2 - entropy->saved.last_dc_val[ci]; 573 entropy->saved.last_dc_val[ci] = temp2; 574 575 /* Encode the DC coefficient difference per section G.1.2.1 */ 576 temp2 = temp; 577 if (temp < 0) { 578 temp = -temp; /* temp is abs value of input */ 579 /* For a negative input, want temp2 = bitwise complement of abs(input) */ 580 /* This code assumes we are on a two's complement machine */ 581 temp2--; 582 } 583 584 /* Find the number of bits needed for the magnitude of the coefficient */ 585 nbits = 0; 586 while (temp) { 587 nbits++; 588 temp >>= 1; 589 } 590 /* Check for out-of-range coefficient values. 591 * Since we're encoding a difference, the range limit is twice as much. 592 */ 593 if (nbits > MAX_COEF_BITS+1) 594 ERREXIT(cinfo, JERR_BAD_DCT_COEF); 595 596 /* Count/emit the Huffman-coded symbol for the number of bits */ 597 emit_dc_symbol(entropy, compptr->dc_tbl_no, nbits); 598 599 /* Emit that number of bits of the value, if positive, */ 600 /* or the complement of its magnitude, if negative. */ 601 if (nbits) /* emit_bits rejects calls with size 0 */ 602 emit_bits_e(entropy, (unsigned int) temp2, nbits); 603 } 604 605 cinfo->dest->next_output_byte = entropy->next_output_byte; 606 cinfo->dest->free_in_buffer = entropy->free_in_buffer; 607 608 /* Update restart-interval state too */ 609 if (cinfo->restart_interval) { 610 if (entropy->restarts_to_go == 0) { 611 entropy->restarts_to_go = cinfo->restart_interval; 612 entropy->next_restart_num++; 613 entropy->next_restart_num &= 7; 614 } 615 entropy->restarts_to_go--; 616 } 617 618 return TRUE; 619 } 620 621 622 /* 623 * MCU encoding for AC initial scan (either spectral selection, 624 * or first pass of successive approximation). 625 */ 626 627 METHODDEF(boolean) 628 encode_mcu_AC_first (j_compress_ptr cinfo, JBLOCKROW *MCU_data) 629 { 630 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy; 631 register int temp, temp2; 632 register int nbits; 633 register int r, k; 634 int Se, Al; 635 const int * natural_order; 636 JBLOCKROW block; 637 638 entropy->next_output_byte = cinfo->dest->next_output_byte; 639 entropy->free_in_buffer = cinfo->dest->free_in_buffer; 640 641 /* Emit restart marker if needed */ 642 if (cinfo->restart_interval) 643 if (entropy->restarts_to_go == 0) 644 emit_restart_e(entropy, entropy->next_restart_num); 645 646 Se = cinfo->Se; 647 Al = cinfo->Al; 648 natural_order = cinfo->natural_order; 649 650 /* Encode the MCU data block */ 651 block = MCU_data[0]; 652 653 /* Encode the AC coefficients per section G.1.2.2, fig. G.3 */ 654 655 r = 0; /* r = run length of zeros */ 656 657 for (k = cinfo->Ss; k <= Se; k++) { 658 if ((temp = (*block)[natural_order[k]]) == 0) { 659 r++; 660 continue; 661 } 662 /* We must apply the point transform by Al. For AC coefficients this 663 * is an integer division with rounding towards 0. To do this portably 664 * in C, we shift after obtaining the absolute value; so the code is 665 * interwoven with finding the abs value (temp) and output bits (temp2). 666 */ 667 if (temp < 0) { 668 temp = -temp; /* temp is abs value of input */ 669 temp >>= Al; /* apply the point transform */ 670 /* For a negative coef, want temp2 = bitwise complement of abs(coef) */ 671 temp2 = ~temp; 672 } else { 673 temp >>= Al; /* apply the point transform */ 674 temp2 = temp; 675 } 676 /* Watch out for case that nonzero coef is zero after point transform */ 677 if (temp == 0) { 678 r++; 679 continue; 680 } 681 682 /* Emit any pending EOBRUN */ 683 if (entropy->EOBRUN > 0) 684 emit_eobrun(entropy); 685 /* if run length > 15, must emit special run-length-16 codes (0xF0) */ 686 while (r > 15) { 687 emit_ac_symbol(entropy, entropy->ac_tbl_no, 0xF0); 688 r -= 16; 689 } 690 691 /* Find the number of bits needed for the magnitude of the coefficient */ 692 nbits = 1; /* there must be at least one 1 bit */ 693 while ((temp >>= 1)) 694 nbits++; 695 /* Check for out-of-range coefficient values */ 696 if (nbits > MAX_COEF_BITS) 697 ERREXIT(cinfo, JERR_BAD_DCT_COEF); 698 699 /* Count/emit Huffman symbol for run length / number of bits */ 700 emit_ac_symbol(entropy, entropy->ac_tbl_no, (r << 4) + nbits); 701 702 /* Emit that number of bits of the value, if positive, */ 703 /* or the complement of its magnitude, if negative. */ 704 emit_bits_e(entropy, (unsigned int) temp2, nbits); 705 706 r = 0; /* reset zero run length */ 707 } 708 709 if (r > 0) { /* If there are trailing zeroes, */ 710 entropy->EOBRUN++; /* count an EOB */ 711 if (entropy->EOBRUN == 0x7FFF) 712 emit_eobrun(entropy); /* force it out to avoid overflow */ 713 } 714 715 cinfo->dest->next_output_byte = entropy->next_output_byte; 716 cinfo->dest->free_in_buffer = entropy->free_in_buffer; 717 718 /* Update restart-interval state too */ 719 if (cinfo->restart_interval) { 720 if (entropy->restarts_to_go == 0) { 721 entropy->restarts_to_go = cinfo->restart_interval; 722 entropy->next_restart_num++; 723 entropy->next_restart_num &= 7; 724 } 725 entropy->restarts_to_go--; 726 } 727 728 return TRUE; 729 } 730 731 732 /* 733 * MCU encoding for DC successive approximation refinement scan. 734 * Note: we assume such scans can be multi-component, although the spec 735 * is not very clear on the point. 736 */ 737 738 METHODDEF(boolean) 739 encode_mcu_DC_refine (j_compress_ptr cinfo, JBLOCKROW *MCU_data) 740 { 741 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy; 742 register int temp; 743 int blkn; 744 int Al = cinfo->Al; 745 JBLOCKROW block; 746 747 entropy->next_output_byte = cinfo->dest->next_output_byte; 748 entropy->free_in_buffer = cinfo->dest->free_in_buffer; 749 750 /* Emit restart marker if needed */ 751 if (cinfo->restart_interval) 752 if (entropy->restarts_to_go == 0) 753 emit_restart_e(entropy, entropy->next_restart_num); 754 755 /* Encode the MCU data blocks */ 756 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) { 757 block = MCU_data[blkn]; 758 759 /* We simply emit the Al'th bit of the DC coefficient value. */ 760 temp = (*block)[0]; 761 emit_bits_e(entropy, (unsigned int) (temp >> Al), 1); 762 } 763 764 cinfo->dest->next_output_byte = entropy->next_output_byte; 765 cinfo->dest->free_in_buffer = entropy->free_in_buffer; 766 767 /* Update restart-interval state too */ 768 if (cinfo->restart_interval) { 769 if (entropy->restarts_to_go == 0) { 770 entropy->restarts_to_go = cinfo->restart_interval; 771 entropy->next_restart_num++; 772 entropy->next_restart_num &= 7; 773 } 774 entropy->restarts_to_go--; 775 } 776 777 return TRUE; 778 } 779 780 781 /* 782 * MCU encoding for AC successive approximation refinement scan. 783 */ 784 785 METHODDEF(boolean) 786 encode_mcu_AC_refine (j_compress_ptr cinfo, JBLOCKROW *MCU_data) 787 { 788 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy; 789 register int temp; 790 register int r, k; 791 int EOB; 792 char *BR_buffer; 793 unsigned int BR; 794 int Se, Al; 795 const int * natural_order; 796 JBLOCKROW block; 797 int absvalues[DCTSIZE2]; 798 799 entropy->next_output_byte = cinfo->dest->next_output_byte; 800 entropy->free_in_buffer = cinfo->dest->free_in_buffer; 801 802 /* Emit restart marker if needed */ 803 if (cinfo->restart_interval) 804 if (entropy->restarts_to_go == 0) 805 emit_restart_e(entropy, entropy->next_restart_num); 806 807 Se = cinfo->Se; 808 Al = cinfo->Al; 809 natural_order = cinfo->natural_order; 810 811 /* Encode the MCU data block */ 812 block = MCU_data[0]; 813 814 /* It is convenient to make a pre-pass to determine the transformed 815 * coefficients' absolute values and the EOB position. 816 */ 817 EOB = 0; 818 for (k = cinfo->Ss; k <= Se; k++) { 819 temp = (*block)[natural_order[k]]; 820 /* We must apply the point transform by Al. For AC coefficients this 821 * is an integer division with rounding towards 0. To do this portably 822 * in C, we shift after obtaining the absolute value. 823 */ 824 if (temp < 0) 825 temp = -temp; /* temp is abs value of input */ 826 temp >>= Al; /* apply the point transform */ 827 absvalues[k] = temp; /* save abs value for main pass */ 828 if (temp == 1) 829 EOB = k; /* EOB = index of last newly-nonzero coef */ 830 } 831 832 /* Encode the AC coefficients per section G.1.2.3, fig. G.7 */ 833 834 r = 0; /* r = run length of zeros */ 835 BR = 0; /* BR = count of buffered bits added now */ 836 BR_buffer = entropy->bit_buffer + entropy->BE; /* Append bits to buffer */ 837 838 for (k = cinfo->Ss; k <= Se; k++) { 839 if ((temp = absvalues[k]) == 0) { 840 r++; 841 continue; 842 } 843 844 /* Emit any required ZRLs, but not if they can be folded into EOB */ 845 while (r > 15 && k <= EOB) { 846 /* emit any pending EOBRUN and the BE correction bits */ 847 emit_eobrun(entropy); 848 /* Emit ZRL */ 849 emit_ac_symbol(entropy, entropy->ac_tbl_no, 0xF0); 850 r -= 16; 851 /* Emit buffered correction bits that must be associated with ZRL */ 852 emit_buffered_bits(entropy, BR_buffer, BR); 853 BR_buffer = entropy->bit_buffer; /* BE bits are gone now */ 854 BR = 0; 855 } 856 857 /* If the coef was previously nonzero, it only needs a correction bit. 858 * NOTE: a straight translation of the spec's figure G.7 would suggest 859 * that we also need to test r > 15. But if r > 15, we can only get here 860 * if k > EOB, which implies that this coefficient is not 1. 861 */ 862 if (temp > 1) { 863 /* The correction bit is the next bit of the absolute value. */ 864 BR_buffer[BR++] = (char) (temp & 1); 865 continue; 866 } 867 868 /* Emit any pending EOBRUN and the BE correction bits */ 869 emit_eobrun(entropy); 870 871 /* Count/emit Huffman symbol for run length / number of bits */ 872 emit_ac_symbol(entropy, entropy->ac_tbl_no, (r << 4) + 1); 873 874 /* Emit output bit for newly-nonzero coef */ 875 temp = ((*block)[natural_order[k]] < 0) ? 0 : 1; 876 emit_bits_e(entropy, (unsigned int) temp, 1); 877 878 /* Emit buffered correction bits that must be associated with this code */ 879 emit_buffered_bits(entropy, BR_buffer, BR); 880 BR_buffer = entropy->bit_buffer; /* BE bits are gone now */ 881 BR = 0; 882 r = 0; /* reset zero run length */ 883 } 884 885 if (r > 0 || BR > 0) { /* If there are trailing zeroes, */ 886 entropy->EOBRUN++; /* count an EOB */ 887 entropy->BE += BR; /* concat my correction bits to older ones */ 888 /* We force out the EOB if we risk either: 889 * 1. overflow of the EOB counter; 890 * 2. overflow of the correction bit buffer during the next MCU. 891 */ 892 if (entropy->EOBRUN == 0x7FFF || entropy->BE > (MAX_CORR_BITS-DCTSIZE2+1)) 893 emit_eobrun(entropy); 894 } 895 896 cinfo->dest->next_output_byte = entropy->next_output_byte; 897 cinfo->dest->free_in_buffer = entropy->free_in_buffer; 898 899 /* Update restart-interval state too */ 900 if (cinfo->restart_interval) { 901 if (entropy->restarts_to_go == 0) { 902 entropy->restarts_to_go = cinfo->restart_interval; 903 entropy->next_restart_num++; 904 entropy->next_restart_num &= 7; 905 } 906 entropy->restarts_to_go--; 907 } 908 909 return TRUE; 910 } 911 912 913 /* Encode a single block's worth of coefficients */ 914 915 LOCAL(boolean) 916 encode_one_block (working_state * state, JCOEFPTR block, int last_dc_val, 917 c_derived_tbl *dctbl, c_derived_tbl *actbl) 918 { 919 register int temp, temp2; 920 register int nbits; 921 register int k, r, i; 922 int Se = state->cinfo->lim_Se; 923 const int * natural_order = state->cinfo->natural_order; 924 925 /* Encode the DC coefficient difference per section F.1.2.1 */ 926 927 temp = temp2 = block[0] - last_dc_val; 928 929 if (temp < 0) { 930 temp = -temp; /* temp is abs value of input */ 931 /* For a negative input, want temp2 = bitwise complement of abs(input) */ 932 /* This code assumes we are on a two's complement machine */ 933 temp2--; 934 } 935 936 /* Find the number of bits needed for the magnitude of the coefficient */ 937 nbits = 0; 938 while (temp) { 939 nbits++; 940 temp >>= 1; 941 } 942 /* Check for out-of-range coefficient values. 943 * Since we're encoding a difference, the range limit is twice as much. 944 */ 945 if (nbits > MAX_COEF_BITS+1) 946 ERREXIT(state->cinfo, JERR_BAD_DCT_COEF); 947 948 /* Emit the Huffman-coded symbol for the number of bits */ 949 if (! emit_bits_s(state, dctbl->ehufco[nbits], dctbl->ehufsi[nbits])) 950 return FALSE; 951 952 /* Emit that number of bits of the value, if positive, */ 953 /* or the complement of its magnitude, if negative. */ 954 if (nbits) /* emit_bits rejects calls with size 0 */ 955 if (! emit_bits_s(state, (unsigned int) temp2, nbits)) 956 return FALSE; 957 958 /* Encode the AC coefficients per section F.1.2.2 */ 959 960 r = 0; /* r = run length of zeros */ 961 962 for (k = 1; k <= Se; k++) { 963 if ((temp = block[natural_order[k]]) == 0) { 964 r++; 965 } else { 966 /* if run length > 15, must emit special run-length-16 codes (0xF0) */ 967 while (r > 15) { 968 if (! emit_bits_s(state, actbl->ehufco[0xF0], actbl->ehufsi[0xF0])) 969 return FALSE; 970 r -= 16; 971 } 972 973 temp2 = temp; 974 if (temp < 0) { 975 temp = -temp; /* temp is abs value of input */ 976 /* This code assumes we are on a two's complement machine */ 977 temp2--; 978 } 979 980 /* Find the number of bits needed for the magnitude of the coefficient */ 981 nbits = 1; /* there must be at least one 1 bit */ 982 while ((temp >>= 1)) 983 nbits++; 984 /* Check for out-of-range coefficient values */ 985 if (nbits > MAX_COEF_BITS) 986 ERREXIT(state->cinfo, JERR_BAD_DCT_COEF); 987 988 /* Emit Huffman symbol for run length / number of bits */ 989 i = (r << 4) + nbits; 990 if (! emit_bits_s(state, actbl->ehufco[i], actbl->ehufsi[i])) 991 return FALSE; 992 993 /* Emit that number of bits of the value, if positive, */ 994 /* or the complement of its magnitude, if negative. */ 995 if (! emit_bits_s(state, (unsigned int) temp2, nbits)) 996 return FALSE; 997 998 r = 0; 999 } 1000 } 1001 1002 /* If the last coef(s) were zero, emit an end-of-block code */ 1003 if (r > 0) 1004 if (! emit_bits_s(state, actbl->ehufco[0], actbl->ehufsi[0])) 1005 return FALSE; 1006 1007 return TRUE; 1008 } 1009 1010 1011 /* 1012 * Encode and output one MCU's worth of Huffman-compressed coefficients. 1013 */ 1014 1015 METHODDEF(boolean) 1016 encode_mcu_huff (j_compress_ptr cinfo, JBLOCKROW *MCU_data) 1017 { 1018 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy; 1019 working_state state; 1020 int blkn, ci; 1021 jpeg_component_info * compptr; 1022 1023 /* Load up working state */ 1024 state.next_output_byte = cinfo->dest->next_output_byte; 1025 state.free_in_buffer = cinfo->dest->free_in_buffer; 1026 ASSIGN_STATE(state.cur, entropy->saved); 1027 state.cinfo = cinfo; 1028 1029 /* Emit restart marker if needed */ 1030 if (cinfo->restart_interval) { 1031 if (entropy->restarts_to_go == 0) 1032 if (! emit_restart_s(&state, entropy->next_restart_num)) 1033 return FALSE; 1034 } 1035 1036 /* Encode the MCU data blocks */ 1037 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) { 1038 ci = cinfo->MCU_membership[blkn]; 1039 compptr = cinfo->cur_comp_info[ci]; 1040 if (! encode_one_block(&state, 1041 MCU_data[blkn][0], state.cur.last_dc_val[ci], 1042 entropy->dc_derived_tbls[compptr->dc_tbl_no], 1043 entropy->ac_derived_tbls[compptr->ac_tbl_no])) 1044 return FALSE; 1045 /* Update last_dc_val */ 1046 state.cur.last_dc_val[ci] = MCU_data[blkn][0][0]; 1047 } 1048 1049 /* Completed MCU, so update state */ 1050 cinfo->dest->next_output_byte = state.next_output_byte; 1051 cinfo->dest->free_in_buffer = state.free_in_buffer; 1052 ASSIGN_STATE(entropy->saved, state.cur); 1053 1054 /* Update restart-interval state too */ 1055 if (cinfo->restart_interval) { 1056 if (entropy->restarts_to_go == 0) { 1057 entropy->restarts_to_go = cinfo->restart_interval; 1058 entropy->next_restart_num++; 1059 entropy->next_restart_num &= 7; 1060 } 1061 entropy->restarts_to_go--; 1062 } 1063 1064 return TRUE; 1065 } 1066 1067 1068 /* 1069 * Finish up at the end of a Huffman-compressed scan. 1070 */ 1071 1072 METHODDEF(void) 1073 finish_pass_huff (j_compress_ptr cinfo) 1074 { 1075 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy; 1076 working_state state; 1077 1078 if (cinfo->progressive_mode) { 1079 entropy->next_output_byte = cinfo->dest->next_output_byte; 1080 entropy->free_in_buffer = cinfo->dest->free_in_buffer; 1081 1082 /* Flush out any buffered data */ 1083 emit_eobrun(entropy); 1084 flush_bits_e(entropy); 1085 1086 cinfo->dest->next_output_byte = entropy->next_output_byte; 1087 cinfo->dest->free_in_buffer = entropy->free_in_buffer; 1088 } else { 1089 /* Load up working state ... flush_bits needs it */ 1090 state.next_output_byte = cinfo->dest->next_output_byte; 1091 state.free_in_buffer = cinfo->dest->free_in_buffer; 1092 ASSIGN_STATE(state.cur, entropy->saved); 1093 state.cinfo = cinfo; 1094 1095 /* Flush out the last data */ 1096 if (! flush_bits_s(&state)) 1097 ERREXIT(cinfo, JERR_CANT_SUSPEND); 1098 1099 /* Update state */ 1100 cinfo->dest->next_output_byte = state.next_output_byte; 1101 cinfo->dest->free_in_buffer = state.free_in_buffer; 1102 ASSIGN_STATE(entropy->saved, state.cur); 1103 } 1104 } 1105 1106 1107 /* 1108 * Huffman coding optimization. 1109 * 1110 * We first scan the supplied data and count the number of uses of each symbol 1111 * that is to be Huffman-coded. (This process MUST agree with the code above.) 1112 * Then we build a Huffman coding tree for the observed counts. 1113 * Symbols which are not needed at all for the particular image are not 1114 * assigned any code, which saves space in the DHT marker as well as in 1115 * the compressed data. 1116 */ 1117 1118 1119 /* Process a single block's worth of coefficients */ 1120 1121 LOCAL(void) 1122 htest_one_block (j_compress_ptr cinfo, JCOEFPTR block, int last_dc_val, 1123 long dc_counts[], long ac_counts[]) 1124 { 1125 register int temp; 1126 register int nbits; 1127 register int k, r; 1128 int Se = cinfo->lim_Se; 1129 const int * natural_order = cinfo->natural_order; 1130 1131 /* Encode the DC coefficient difference per section F.1.2.1 */ 1132 1133 temp = block[0] - last_dc_val; 1134 if (temp < 0) 1135 temp = -temp; 1136 1137 /* Find the number of bits needed for the magnitude of the coefficient */ 1138 nbits = 0; 1139 while (temp) { 1140 nbits++; 1141 temp >>= 1; 1142 } 1143 /* Check for out-of-range coefficient values. 1144 * Since we're encoding a difference, the range limit is twice as much. 1145 */ 1146 if (nbits > MAX_COEF_BITS+1) 1147 ERREXIT(cinfo, JERR_BAD_DCT_COEF); 1148 1149 /* Count the Huffman symbol for the number of bits */ 1150 dc_counts[nbits]++; 1151 1152 /* Encode the AC coefficients per section F.1.2.2 */ 1153 1154 r = 0; /* r = run length of zeros */ 1155 1156 for (k = 1; k <= Se; k++) { 1157 if ((temp = block[natural_order[k]]) == 0) { 1158 r++; 1159 } else { 1160 /* if run length > 15, must emit special run-length-16 codes (0xF0) */ 1161 while (r > 15) { 1162 ac_counts[0xF0]++; 1163 r -= 16; 1164 } 1165 1166 /* Find the number of bits needed for the magnitude of the coefficient */ 1167 if (temp < 0) 1168 temp = -temp; 1169 1170 /* Find the number of bits needed for the magnitude of the coefficient */ 1171 nbits = 1; /* there must be at least one 1 bit */ 1172 while ((temp >>= 1)) 1173 nbits++; 1174 /* Check for out-of-range coefficient values */ 1175 if (nbits > MAX_COEF_BITS) 1176 ERREXIT(cinfo, JERR_BAD_DCT_COEF); 1177 1178 /* Count Huffman symbol for run length / number of bits */ 1179 ac_counts[(r << 4) + nbits]++; 1180 1181 r = 0; 1182 } 1183 } 1184 1185 /* If the last coef(s) were zero, emit an end-of-block code */ 1186 if (r > 0) 1187 ac_counts[0]++; 1188 } 1189 1190 1191 /* 1192 * Trial-encode one MCU's worth of Huffman-compressed coefficients. 1193 * No data is actually output, so no suspension return is possible. 1194 */ 1195 1196 METHODDEF(boolean) 1197 encode_mcu_gather (j_compress_ptr cinfo, JBLOCKROW *MCU_data) 1198 { 1199 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy; 1200 int blkn, ci; 1201 jpeg_component_info * compptr; 1202 1203 /* Take care of restart intervals if needed */ 1204 if (cinfo->restart_interval) { 1205 if (entropy->restarts_to_go == 0) { 1206 /* Re-initialize DC predictions to 0 */ 1207 for (ci = 0; ci < cinfo->comps_in_scan; ci++) 1208 entropy->saved.last_dc_val[ci] = 0; 1209 /* Update restart state */ 1210 entropy->restarts_to_go = cinfo->restart_interval; 1211 } 1212 entropy->restarts_to_go--; 1213 } 1214 1215 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) { 1216 ci = cinfo->MCU_membership[blkn]; 1217 compptr = cinfo->cur_comp_info[ci]; 1218 htest_one_block(cinfo, MCU_data[blkn][0], entropy->saved.last_dc_val[ci], 1219 entropy->dc_count_ptrs[compptr->dc_tbl_no], 1220 entropy->ac_count_ptrs[compptr->ac_tbl_no]); 1221 entropy->saved.last_dc_val[ci] = MCU_data[blkn][0][0]; 1222 } 1223 1224 return TRUE; 1225 } 1226 1227 1228 /* 1229 * Generate the best Huffman code table for the given counts, fill htbl. 1230 * 1231 * The JPEG standard requires that no symbol be assigned a codeword of all 1232 * one bits (so that padding bits added at the end of a compressed segment 1233 * can't look like a valid code). Because of the canonical ordering of 1234 * codewords, this just means that there must be an unused slot in the 1235 * longest codeword length category. Section K.2 of the JPEG spec suggests 1236 * reserving such a slot by pretending that symbol 256 is a valid symbol 1237 * with count 1. In theory that's not optimal; giving it count zero but 1238 * including it in the symbol set anyway should give a better Huffman code. 1239 * But the theoretically better code actually seems to come out worse in 1240 * practice, because it produces more all-ones bytes (which incur stuffed 1241 * zero bytes in the final file). In any case the difference is tiny. 1242 * 1243 * The JPEG standard requires Huffman codes to be no more than 16 bits long. 1244 * If some symbols have a very small but nonzero probability, the Huffman tree 1245 * must be adjusted to meet the code length restriction. We currently use 1246 * the adjustment method suggested in JPEG section K.2. This method is *not* 1247 * optimal; it may not choose the best possible limited-length code. But 1248 * typically only very-low-frequency symbols will be given less-than-optimal 1249 * lengths, so the code is almost optimal. Experimental comparisons against 1250 * an optimal limited-length-code algorithm indicate that the difference is 1251 * microscopic --- usually less than a hundredth of a percent of total size. 1252 * So the extra complexity of an optimal algorithm doesn't seem worthwhile. 1253 */ 1254 1255 LOCAL(void) 1256 jpeg_gen_optimal_table (j_compress_ptr cinfo, JHUFF_TBL * htbl, long freq[]) 1257 { 1258 #define MAX_CLEN 32 /* assumed maximum initial code length */ 1259 UINT8 bits[MAX_CLEN+1]; /* bits[k] = # of symbols with code length k */ 1260 int codesize[257]; /* codesize[k] = code length of symbol k */ 1261 int others[257]; /* next symbol in current branch of tree */ 1262 int c1, c2; 1263 int p, i, j; 1264 long v; 1265 1266 /* This algorithm is explained in section K.2 of the JPEG standard */ 1267 1268 MEMZERO(bits, SIZEOF(bits)); 1269 MEMZERO(codesize, SIZEOF(codesize)); 1270 for (i = 0; i < 257; i++) 1271 others[i] = -1; /* init links to empty */ 1272 1273 freq[256] = 1; /* make sure 256 has a nonzero count */ 1274 /* Including the pseudo-symbol 256 in the Huffman procedure guarantees 1275 * that no real symbol is given code-value of all ones, because 256 1276 * will be placed last in the largest codeword category. 1277 */ 1278 1279 /* Huffman's basic algorithm to assign optimal code lengths to symbols */ 1280 1281 for (;;) { 1282 /* Find the smallest nonzero frequency, set c1 = its symbol */ 1283 /* In case of ties, take the larger symbol number */ 1284 c1 = -1; 1285 v = 1000000000L; 1286 for (i = 0; i <= 256; i++) { 1287 if (freq[i] && freq[i] <= v) { 1288 v = freq[i]; 1289 c1 = i; 1290 } 1291 } 1292 1293 /* Find the next smallest nonzero frequency, set c2 = its symbol */ 1294 /* In case of ties, take the larger symbol number */ 1295 c2 = -1; 1296 v = 1000000000L; 1297 for (i = 0; i <= 256; i++) { 1298 if (freq[i] && freq[i] <= v && i != c1) { 1299 v = freq[i]; 1300 c2 = i; 1301 } 1302 } 1303 1304 /* Done if we've merged everything into one frequency */ 1305 if (c2 < 0) 1306 break; 1307 1308 /* Else merge the two counts/trees */ 1309 freq[c1] += freq[c2]; 1310 freq[c2] = 0; 1311 1312 /* Increment the codesize of everything in c1's tree branch */ 1313 codesize[c1]++; 1314 while (others[c1] >= 0) { 1315 c1 = others[c1]; 1316 codesize[c1]++; 1317 } 1318 1319 others[c1] = c2; /* chain c2 onto c1's tree branch */ 1320 1321 /* Increment the codesize of everything in c2's tree branch */ 1322 codesize[c2]++; 1323 while (others[c2] >= 0) { 1324 c2 = others[c2]; 1325 codesize[c2]++; 1326 } 1327 } 1328 1329 /* Now count the number of symbols of each code length */ 1330 for (i = 0; i <= 256; i++) { 1331 if (codesize[i]) { 1332 /* The JPEG standard seems to think that this can't happen, */ 1333 /* but I'm paranoid... */ 1334 if (codesize[i] > MAX_CLEN) 1335 ERREXIT(cinfo, JERR_HUFF_CLEN_OVERFLOW); 1336 1337 bits[codesize[i]]++; 1338 } 1339 } 1340 1341 /* JPEG doesn't allow symbols with code lengths over 16 bits, so if the pure 1342 * Huffman procedure assigned any such lengths, we must adjust the coding. 1343 * Here is what the JPEG spec says about how this next bit works: 1344 * Since symbols are paired for the longest Huffman code, the symbols are 1345 * removed from this length category two at a time. The prefix for the pair 1346 * (which is one bit shorter) is allocated to one of the pair; then, 1347 * skipping the BITS entry for that prefix length, a code word from the next 1348 * shortest nonzero BITS entry is converted into a prefix for two code words 1349 * one bit longer. 1350 */ 1351 1352 for (i = MAX_CLEN; i > 16; i--) { 1353 while (bits[i] > 0) { 1354 j = i - 2; /* find length of new prefix to be used */ 1355 while (bits[j] == 0) 1356 j--; 1357 1358 bits[i] -= 2; /* remove two symbols */ 1359 bits[i-1]++; /* one goes in this length */ 1360 bits[j+1] += 2; /* two new symbols in this length */ 1361 bits[j]--; /* symbol of this length is now a prefix */ 1362 } 1363 } 1364 1365 /* Remove the count for the pseudo-symbol 256 from the largest codelength */ 1366 while (bits[i] == 0) /* find largest codelength still in use */ 1367 i--; 1368 bits[i]--; 1369 1370 /* Return final symbol counts (only for lengths 0..16) */ 1371 MEMCOPY(htbl->bits, bits, SIZEOF(htbl->bits)); 1372 1373 /* Return a list of the symbols sorted by code length */ 1374 /* It's not real clear to me why we don't need to consider the codelength 1375 * changes made above, but the JPEG spec seems to think this works. 1376 */ 1377 p = 0; 1378 for (i = 1; i <= MAX_CLEN; i++) { 1379 for (j = 0; j <= 255; j++) { 1380 if (codesize[j] == i) { 1381 htbl->huffval[p] = (UINT8) j; 1382 p++; 1383 } 1384 } 1385 } 1386 1387 /* Set sent_table FALSE so updated table will be written to JPEG file. */ 1388 htbl->sent_table = FALSE; 1389 } 1390 1391 1392 /* 1393 * Finish up a statistics-gathering pass and create the new Huffman tables. 1394 */ 1395 1396 METHODDEF(void) 1397 finish_pass_gather (j_compress_ptr cinfo) 1398 { 1399 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy; 1400 int ci, tbl; 1401 jpeg_component_info * compptr; 1402 JHUFF_TBL **htblptr; 1403 boolean did_dc[NUM_HUFF_TBLS]; 1404 boolean did_ac[NUM_HUFF_TBLS]; 1405 1406 /* It's important not to apply jpeg_gen_optimal_table more than once 1407 * per table, because it clobbers the input frequency counts! 1408 */ 1409 if (cinfo->progressive_mode) 1410 /* Flush out buffered data (all we care about is counting the EOB symbol) */ 1411 emit_eobrun(entropy); 1412 1413 MEMZERO(did_dc, SIZEOF(did_dc)); 1414 MEMZERO(did_ac, SIZEOF(did_ac)); 1415 1416 for (ci = 0; ci < cinfo->comps_in_scan; ci++) { 1417 compptr = cinfo->cur_comp_info[ci]; 1418 /* DC needs no table for refinement scan */ 1419 if (cinfo->Ss == 0 && cinfo->Ah == 0) { 1420 tbl = compptr->dc_tbl_no; 1421 if (! did_dc[tbl]) { 1422 htblptr = & cinfo->dc_huff_tbl_ptrs[tbl]; 1423 if (*htblptr == NULL) 1424 *htblptr = jpeg_alloc_huff_table((j_common_ptr) cinfo); 1425 jpeg_gen_optimal_table(cinfo, *htblptr, entropy->dc_count_ptrs[tbl]); 1426 did_dc[tbl] = TRUE; 1427 } 1428 } 1429 /* AC needs no table when not present */ 1430 if (cinfo->Se) { 1431 tbl = compptr->ac_tbl_no; 1432 if (! did_ac[tbl]) { 1433 htblptr = & cinfo->ac_huff_tbl_ptrs[tbl]; 1434 if (*htblptr == NULL) 1435 *htblptr = jpeg_alloc_huff_table((j_common_ptr) cinfo); 1436 jpeg_gen_optimal_table(cinfo, *htblptr, entropy->ac_count_ptrs[tbl]); 1437 did_ac[tbl] = TRUE; 1438 } 1439 } 1440 } 1441 } 1442 1443 1444 /* 1445 * Initialize for a Huffman-compressed scan. 1446 * If gather_statistics is TRUE, we do not output anything during the scan, 1447 * just count the Huffman symbols used and generate Huffman code tables. 1448 */ 1449 1450 METHODDEF(void) 1451 start_pass_huff (j_compress_ptr cinfo, boolean gather_statistics) 1452 { 1453 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy; 1454 int ci, tbl; 1455 jpeg_component_info * compptr; 1456 1457 if (gather_statistics) 1458 entropy->pub.finish_pass = finish_pass_gather; 1459 else 1460 entropy->pub.finish_pass = finish_pass_huff; 1461 1462 if (cinfo->progressive_mode) { 1463 entropy->cinfo = cinfo; 1464 entropy->gather_statistics = gather_statistics; 1465 1466 /* We assume jcmaster.c already validated the scan parameters. */ 1467 1468 /* Select execution routine */ 1469 if (cinfo->Ah == 0) { 1470 if (cinfo->Ss == 0) 1471 entropy->pub.encode_mcu = encode_mcu_DC_first; 1472 else 1473 entropy->pub.encode_mcu = encode_mcu_AC_first; 1474 } else { 1475 if (cinfo->Ss == 0) 1476 entropy->pub.encode_mcu = encode_mcu_DC_refine; 1477 else { 1478 entropy->pub.encode_mcu = encode_mcu_AC_refine; 1479 /* AC refinement needs a correction bit buffer */ 1480 if (entropy->bit_buffer == NULL) 1481 entropy->bit_buffer = (char *) 1482 (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE, 1483 MAX_CORR_BITS * SIZEOF(char)); 1484 } 1485 } 1486 1487 /* Initialize AC stuff */ 1488 entropy->ac_tbl_no = cinfo->cur_comp_info[0]->ac_tbl_no; 1489 entropy->EOBRUN = 0; 1490 entropy->BE = 0; 1491 } else { 1492 if (gather_statistics) 1493 entropy->pub.encode_mcu = encode_mcu_gather; 1494 else 1495 entropy->pub.encode_mcu = encode_mcu_huff; 1496 } 1497 1498 for (ci = 0; ci < cinfo->comps_in_scan; ci++) { 1499 compptr = cinfo->cur_comp_info[ci]; 1500 /* DC needs no table for refinement scan */ 1501 if (cinfo->Ss == 0 && cinfo->Ah == 0) { 1502 tbl = compptr->dc_tbl_no; 1503 if (gather_statistics) { 1504 /* Check for invalid table index */ 1505 /* (make_c_derived_tbl does this in the other path) */ 1506 if (tbl < 0 || tbl >= NUM_HUFF_TBLS) 1507 ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tbl); 1508 /* Allocate and zero the statistics tables */ 1509 /* Note that jpeg_gen_optimal_table expects 257 entries in each table! */ 1510 if (entropy->dc_count_ptrs[tbl] == NULL) 1511 entropy->dc_count_ptrs[tbl] = (long *) 1512 (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE, 1513 257 * SIZEOF(long)); 1514 MEMZERO(entropy->dc_count_ptrs[tbl], 257 * SIZEOF(long)); 1515 } else { 1516 /* Compute derived values for Huffman tables */ 1517 /* We may do this more than once for a table, but it's not expensive */ 1518 jpeg_make_c_derived_tbl(cinfo, TRUE, tbl, 1519 & entropy->dc_derived_tbls[tbl]); 1520 } 1521 /* Initialize DC predictions to 0 */ 1522 entropy->saved.last_dc_val[ci] = 0; 1523 } 1524 /* AC needs no table when not present */ 1525 if (cinfo->Se) { 1526 tbl = compptr->ac_tbl_no; 1527 if (gather_statistics) { 1528 if (tbl < 0 || tbl >= NUM_HUFF_TBLS) 1529 ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tbl); 1530 if (entropy->ac_count_ptrs[tbl] == NULL) 1531 entropy->ac_count_ptrs[tbl] = (long *) 1532 (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE, 1533 257 * SIZEOF(long)); 1534 MEMZERO(entropy->ac_count_ptrs[tbl], 257 * SIZEOF(long)); 1535 } else { 1536 jpeg_make_c_derived_tbl(cinfo, FALSE, tbl, 1537 & entropy->ac_derived_tbls[tbl]); 1538 } 1539 } 1540 } 1541 1542 /* Initialize bit buffer to empty */ 1543 entropy->saved.put_buffer = 0; 1544 entropy->saved.put_bits = 0; 1545 1546 /* Initialize restart stuff */ 1547 entropy->restarts_to_go = cinfo->restart_interval; 1548 entropy->next_restart_num = 0; 1549 } 1550 1551 1552 /* 1553 * Module initialization routine for Huffman entropy encoding. 1554 */ 1555 1556 GLOBAL(void) 1557 jinit_huff_encoder (j_compress_ptr cinfo) 1558 { 1559 huff_entropy_ptr entropy; 1560 int i; 1561 1562 entropy = (huff_entropy_ptr) 1563 (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE, 1564 SIZEOF(huff_entropy_encoder)); 1565 cinfo->entropy = (struct jpeg_entropy_encoder *) entropy; 1566 entropy->pub.start_pass = start_pass_huff; 1567 1568 /* Mark tables unallocated */ 1569 for (i = 0; i < NUM_HUFF_TBLS; i++) { 1570 entropy->dc_derived_tbls[i] = entropy->ac_derived_tbls[i] = NULL; 1571 entropy->dc_count_ptrs[i] = entropy->ac_count_ptrs[i] = NULL; 1572 } 1573 1574 if (cinfo->progressive_mode) 1575 entropy->bit_buffer = NULL; /* needed only in AC refinement scan */ 1576 } 1577
