1 /* 2 * jchuff.c 3 * 4 * Copyright (C) 1991-1997, Thomas G. Lane. 5 * Modified 2006-2019 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 htbl = jpeg_std_huff_table((j_common_ptr) cinfo, isDC, tblno); 182 183 /* Allocate a workspace if we haven't already done so. */ 184 if (*pdtbl == NULL) 185 *pdtbl = (c_derived_tbl *) (*cinfo->mem->alloc_small) 186 ((j_common_ptr) cinfo, JPOOL_IMAGE, SIZEOF(c_derived_tbl)); 187 dtbl = *pdtbl; 188 189 /* Figure C.1: make table of Huffman code length for each symbol */ 190 191 p = 0; 192 for (l = 1; l <= 16; l++) { 193 i = (int) htbl->bits[l]; 194 if (i < 0 || p + i > 256) /* protect against table overrun */ 195 ERREXIT(cinfo, JERR_BAD_HUFF_TABLE); 196 while (i--) 197 huffsize[p++] = (char) l; 198 } 199 huffsize[p] = 0; 200 lastp = p; 201 202 /* Figure C.2: generate the codes themselves */ 203 /* We also validate that the counts represent a legal Huffman code tree. */ 204 205 code = 0; 206 si = huffsize[0]; 207 p = 0; 208 while (huffsize[p]) { 209 while (((int) huffsize[p]) == si) { 210 huffcode[p++] = code; 211 code++; 212 } 213 /* code is now 1 more than the last code used for codelength si; but 214 * it must still fit in si bits, since no code is allowed to be all ones. 215 */ 216 if (((INT32) code) >= (((INT32) 1) << si)) 217 ERREXIT(cinfo, JERR_BAD_HUFF_TABLE); 218 code <<= 1; 219 si++; 220 } 221 222 /* Figure C.3: generate encoding tables */ 223 /* These are code and size indexed by symbol value */ 224 225 /* Set all codeless symbols to have code length 0; 226 * this lets us detect duplicate VAL entries here, and later 227 * allows emit_bits to detect any attempt to emit such symbols. 228 */ 229 MEMZERO(dtbl->ehufsi, SIZEOF(dtbl->ehufsi)); 230 231 /* This is also a convenient place to check for out-of-range 232 * and duplicated VAL entries. We allow 0..255 for AC symbols 233 * but only 0..15 for DC. (We could constrain them further 234 * based on data depth and mode, but this seems enough.) 235 */ 236 maxsymbol = isDC ? 15 : 255; 237 238 for (p = 0; p < lastp; p++) { 239 i = htbl->huffval[p]; 240 if (i < 0 || i > maxsymbol || dtbl->ehufsi[i]) 241 ERREXIT(cinfo, JERR_BAD_HUFF_TABLE); 242 dtbl->ehufco[i] = huffcode[p]; 243 dtbl->ehufsi[i] = huffsize[p]; 244 } 245 } 246 247 248 /* Outputting bytes to the file. 249 * NB: these must be called only when actually outputting, 250 * that is, entropy->gather_statistics == FALSE. 251 */ 252 253 /* Emit a byte, taking 'action' if must suspend. */ 254 #define emit_byte_s(state,val,action) \ 255 { *(state)->next_output_byte++ = (JOCTET) (val); \ 256 if (--(state)->free_in_buffer == 0) \ 257 if (! dump_buffer_s(state)) \ 258 { action; } } 259 260 /* Emit a byte */ 261 #define emit_byte_e(entropy,val) \ 262 { *(entropy)->next_output_byte++ = (JOCTET) (val); \ 263 if (--(entropy)->free_in_buffer == 0) \ 264 dump_buffer_e(entropy); } 265 266 267 LOCAL(boolean) 268 dump_buffer_s (working_state * state) 269 /* Empty the output buffer; return TRUE if successful, FALSE if must suspend */ 270 { 271 struct jpeg_destination_mgr * dest = state->cinfo->dest; 272 273 if (! (*dest->empty_output_buffer) (state->cinfo)) 274 return FALSE; 275 /* After a successful buffer dump, must reset buffer pointers */ 276 state->next_output_byte = dest->next_output_byte; 277 state->free_in_buffer = dest->free_in_buffer; 278 return TRUE; 279 } 280 281 282 LOCAL(void) 283 dump_buffer_e (huff_entropy_ptr entropy) 284 /* Empty the output buffer; we do not support suspension in this case. */ 285 { 286 struct jpeg_destination_mgr * dest = entropy->cinfo->dest; 287 288 if (! (*dest->empty_output_buffer) (entropy->cinfo)) 289 ERREXIT(entropy->cinfo, JERR_CANT_SUSPEND); 290 /* After a successful buffer dump, must reset buffer pointers */ 291 entropy->next_output_byte = dest->next_output_byte; 292 entropy->free_in_buffer = dest->free_in_buffer; 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 304 INLINE 305 LOCAL(boolean) 306 emit_bits_s (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; 311 register int 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 /* mask off any extra bits in code */ 318 put_buffer = ((INT32) code) & ((((INT32) 1) << size) - 1); 319 320 /* new number of bits in buffer */ 321 put_bits = size + state->cur.put_bits; 322 323 put_buffer <<= 24 - put_bits; /* align incoming bits */ 324 325 /* and merge with old buffer contents */ 326 put_buffer |= state->cur.put_buffer; 327 328 while (put_bits >= 8) { 329 int c = (int) ((put_buffer >> 16) & 0xFF); 330 331 emit_byte_s(state, c, return FALSE); 332 if (c == 0xFF) { /* need to stuff a zero byte? */ 333 emit_byte_s(state, 0, return FALSE); 334 } 335 put_buffer <<= 8; 336 put_bits -= 8; 337 } 338 339 state->cur.put_buffer = put_buffer; /* update state variables */ 340 state->cur.put_bits = put_bits; 341 342 return TRUE; 343 } 344 345 346 INLINE 347 LOCAL(void) 348 emit_bits_e (huff_entropy_ptr entropy, unsigned int code, int size) 349 /* Emit some bits, unless we are in gather mode */ 350 { 351 /* This routine is heavily used, so it's worth coding tightly. */ 352 register INT32 put_buffer; 353 register int put_bits; 354 355 /* if size is 0, caller used an invalid Huffman table entry */ 356 if (size == 0) 357 ERREXIT(entropy->cinfo, JERR_HUFF_MISSING_CODE); 358 359 if (entropy->gather_statistics) 360 return; /* do nothing if we're only getting stats */ 361 362 /* mask off any extra bits in code */ 363 put_buffer = ((INT32) code) & ((((INT32) 1) << size) - 1); 364 365 /* new number of bits in buffer */ 366 put_bits = size + entropy->saved.put_bits; 367 368 put_buffer <<= 24 - put_bits; /* align incoming bits */ 369 370 /* and merge with old buffer contents */ 371 put_buffer |= entropy->saved.put_buffer; 372 373 while (put_bits >= 8) { 374 int c = (int) ((put_buffer >> 16) & 0xFF); 375 376 emit_byte_e(entropy, c); 377 if (c == 0xFF) { /* need to stuff a zero byte? */ 378 emit_byte_e(entropy, 0); 379 } 380 put_buffer <<= 8; 381 put_bits -= 8; 382 } 383 384 entropy->saved.put_buffer = put_buffer; /* update variables */ 385 entropy->saved.put_bits = put_bits; 386 } 387 388 389 LOCAL(boolean) 390 flush_bits_s (working_state * state) 391 { 392 if (! emit_bits_s(state, 0x7F, 7)) /* fill any partial byte with ones */ 393 return FALSE; 394 state->cur.put_buffer = 0; /* and reset bit-buffer to empty */ 395 state->cur.put_bits = 0; 396 return TRUE; 397 } 398 399 400 LOCAL(void) 401 flush_bits_e (huff_entropy_ptr entropy) 402 { 403 emit_bits_e(entropy, 0x7F, 7); /* fill any partial byte with ones */ 404 entropy->saved.put_buffer = 0; /* and reset bit-buffer to empty */ 405 entropy->saved.put_bits = 0; 406 } 407 408 409 /* 410 * Emit (or just count) a Huffman symbol. 411 */ 412 413 INLINE 414 LOCAL(void) 415 emit_dc_symbol (huff_entropy_ptr entropy, int tbl_no, int symbol) 416 { 417 if (entropy->gather_statistics) 418 entropy->dc_count_ptrs[tbl_no][symbol]++; 419 else { 420 c_derived_tbl * tbl = entropy->dc_derived_tbls[tbl_no]; 421 emit_bits_e(entropy, tbl->ehufco[symbol], tbl->ehufsi[symbol]); 422 } 423 } 424 425 426 INLINE 427 LOCAL(void) 428 emit_ac_symbol (huff_entropy_ptr entropy, int tbl_no, int symbol) 429 { 430 if (entropy->gather_statistics) 431 entropy->ac_count_ptrs[tbl_no][symbol]++; 432 else { 433 c_derived_tbl * tbl = entropy->ac_derived_tbls[tbl_no]; 434 emit_bits_e(entropy, tbl->ehufco[symbol], tbl->ehufsi[symbol]); 435 } 436 } 437 438 439 /* 440 * Emit bits from a correction bit buffer. 441 */ 442 443 LOCAL(void) 444 emit_buffered_bits (huff_entropy_ptr entropy, char * bufstart, 445 unsigned int nbits) 446 { 447 if (entropy->gather_statistics) 448 return; /* no real work */ 449 450 while (nbits > 0) { 451 emit_bits_e(entropy, (unsigned int) (*bufstart), 1); 452 bufstart++; 453 nbits--; 454 } 455 } 456 457 458 /* 459 * Emit any pending EOBRUN symbol. 460 */ 461 462 LOCAL(void) 463 emit_eobrun (huff_entropy_ptr entropy) 464 { 465 register int temp, nbits; 466 467 if (entropy->EOBRUN > 0) { /* if there is any pending EOBRUN */ 468 temp = entropy->EOBRUN; 469 nbits = 0; 470 while ((temp >>= 1)) 471 nbits++; 472 /* safety check: shouldn't happen given limited correction-bit buffer */ 473 if (nbits > 14) 474 ERREXIT(entropy->cinfo, JERR_HUFF_MISSING_CODE); 475 476 emit_ac_symbol(entropy, entropy->ac_tbl_no, nbits << 4); 477 if (nbits) 478 emit_bits_e(entropy, entropy->EOBRUN, nbits); 479 480 entropy->EOBRUN = 0; 481 482 /* Emit any buffered correction bits */ 483 emit_buffered_bits(entropy, entropy->bit_buffer, entropy->BE); 484 entropy->BE = 0; 485 } 486 } 487 488 489 /* 490 * Emit a restart marker & resynchronize predictions. 491 */ 492 493 LOCAL(boolean) 494 emit_restart_s (working_state * state, int restart_num) 495 { 496 int ci; 497 498 if (! flush_bits_s(state)) 499 return FALSE; 500 501 emit_byte_s(state, 0xFF, return FALSE); 502 emit_byte_s(state, JPEG_RST0 + restart_num, return FALSE); 503 504 /* Re-initialize DC predictions to 0 */ 505 for (ci = 0; ci < state->cinfo->comps_in_scan; ci++) 506 state->cur.last_dc_val[ci] = 0; 507 508 /* The restart counter is not updated until we successfully write the MCU. */ 509 510 return TRUE; 511 } 512 513 514 LOCAL(void) 515 emit_restart_e (huff_entropy_ptr entropy, int restart_num) 516 { 517 int ci; 518 519 emit_eobrun(entropy); 520 521 if (! entropy->gather_statistics) { 522 flush_bits_e(entropy); 523 emit_byte_e(entropy, 0xFF); 524 emit_byte_e(entropy, JPEG_RST0 + restart_num); 525 } 526 527 if (entropy->cinfo->Ss == 0) { 528 /* Re-initialize DC predictions to 0 */ 529 for (ci = 0; ci < entropy->cinfo->comps_in_scan; ci++) 530 entropy->saved.last_dc_val[ci] = 0; 531 } else { 532 /* Re-initialize all AC-related fields to 0 */ 533 entropy->EOBRUN = 0; 534 entropy->BE = 0; 535 } 536 } 537 538 539 /* 540 * MCU encoding for DC initial scan (either spectral selection, 541 * or first pass of successive approximation). 542 */ 543 544 METHODDEF(boolean) 545 encode_mcu_DC_first (j_compress_ptr cinfo, JBLOCKROW *MCU_data) 546 { 547 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy; 548 register int temp, temp2; 549 register int nbits; 550 int blkn, ci, tbl; 551 ISHIFT_TEMPS 552 553 entropy->next_output_byte = cinfo->dest->next_output_byte; 554 entropy->free_in_buffer = cinfo->dest->free_in_buffer; 555 556 /* Emit restart marker if needed */ 557 if (cinfo->restart_interval) 558 if (entropy->restarts_to_go == 0) 559 emit_restart_e(entropy, entropy->next_restart_num); 560 561 /* Encode the MCU data blocks */ 562 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) { 563 ci = cinfo->MCU_membership[blkn]; 564 tbl = cinfo->cur_comp_info[ci]->dc_tbl_no; 565 566 /* Compute the DC value after the required point transform by Al. 567 * This is simply an arithmetic right shift. 568 */ 569 temp = IRIGHT_SHIFT((int) (MCU_data[blkn][0][0]), cinfo->Al); 570 571 /* DC differences are figured on the point-transformed values. */ 572 temp2 = temp - entropy->saved.last_dc_val[ci]; 573 entropy->saved.last_dc_val[ci] = temp; 574 575 /* Encode the DC coefficient difference per section G.1.2.1 */ 576 temp = temp2; 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, tbl, 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 const int * natural_order; 632 JBLOCKROW block; 633 register int temp, temp2; 634 register int nbits; 635 register int r, k; 636 int Se, Al; 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, 735 * although the spec 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 int Al, blkn; 743 744 entropy->next_output_byte = cinfo->dest->next_output_byte; 745 entropy->free_in_buffer = cinfo->dest->free_in_buffer; 746 747 /* Emit restart marker if needed */ 748 if (cinfo->restart_interval) 749 if (entropy->restarts_to_go == 0) 750 emit_restart_e(entropy, entropy->next_restart_num); 751 752 Al = cinfo->Al; 753 754 /* Encode the MCU data blocks */ 755 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) { 756 /* We simply emit the Al'th bit of the DC coefficient value. */ 757 emit_bits_e(entropy, (unsigned int) (MCU_data[blkn][0][0] >> Al), 1); 758 } 759 760 cinfo->dest->next_output_byte = entropy->next_output_byte; 761 cinfo->dest->free_in_buffer = entropy->free_in_buffer; 762 763 /* Update restart-interval state too */ 764 if (cinfo->restart_interval) { 765 if (entropy->restarts_to_go == 0) { 766 entropy->restarts_to_go = cinfo->restart_interval; 767 entropy->next_restart_num++; 768 entropy->next_restart_num &= 7; 769 } 770 entropy->restarts_to_go--; 771 } 772 773 return TRUE; 774 } 775 776 777 /* 778 * MCU encoding for AC successive approximation refinement scan. 779 */ 780 781 METHODDEF(boolean) 782 encode_mcu_AC_refine (j_compress_ptr cinfo, JBLOCKROW *MCU_data) 783 { 784 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy; 785 const int * natural_order; 786 JBLOCKROW block; 787 register int temp; 788 register int r, k; 789 int Se, Al; 790 int EOB; 791 char *BR_buffer; 792 unsigned int BR; 793 int absvalues[DCTSIZE2]; 794 795 entropy->next_output_byte = cinfo->dest->next_output_byte; 796 entropy->free_in_buffer = cinfo->dest->free_in_buffer; 797 798 /* Emit restart marker if needed */ 799 if (cinfo->restart_interval) 800 if (entropy->restarts_to_go == 0) 801 emit_restart_e(entropy, entropy->next_restart_num); 802 803 Se = cinfo->Se; 804 Al = cinfo->Al; 805 natural_order = cinfo->natural_order; 806 807 /* Encode the MCU data block */ 808 block = MCU_data[0]; 809 810 /* It is convenient to make a pre-pass to determine the transformed 811 * coefficients' absolute values and the EOB position. 812 */ 813 EOB = 0; 814 for (k = cinfo->Ss; k <= Se; k++) { 815 temp = (*block)[natural_order[k]]; 816 /* We must apply the point transform by Al. For AC coefficients this 817 * is an integer division with rounding towards 0. To do this portably 818 * in C, we shift after obtaining the absolute value. 819 */ 820 if (temp < 0) 821 temp = -temp; /* temp is abs value of input */ 822 temp >>= Al; /* apply the point transform */ 823 absvalues[k] = temp; /* save abs value for main pass */ 824 if (temp == 1) 825 EOB = k; /* EOB = index of last newly-nonzero coef */ 826 } 827 828 /* Encode the AC coefficients per section G.1.2.3, fig. G.7 */ 829 830 r = 0; /* r = run length of zeros */ 831 BR = 0; /* BR = count of buffered bits added now */ 832 BR_buffer = entropy->bit_buffer + entropy->BE; /* Append bits to buffer */ 833 834 for (k = cinfo->Ss; k <= Se; k++) { 835 if ((temp = absvalues[k]) == 0) { 836 r++; 837 continue; 838 } 839 840 /* Emit any required ZRLs, but not if they can be folded into EOB */ 841 while (r > 15 && k <= EOB) { 842 /* emit any pending EOBRUN and the BE correction bits */ 843 emit_eobrun(entropy); 844 /* Emit ZRL */ 845 emit_ac_symbol(entropy, entropy->ac_tbl_no, 0xF0); 846 r -= 16; 847 /* Emit buffered correction bits that must be associated with ZRL */ 848 emit_buffered_bits(entropy, BR_buffer, BR); 849 BR_buffer = entropy->bit_buffer; /* BE bits are gone now */ 850 BR = 0; 851 } 852 853 /* If the coef was previously nonzero, it only needs a correction bit. 854 * NOTE: a straight translation of the spec's figure G.7 would suggest 855 * that we also need to test r > 15. But if r > 15, we can only get here 856 * if k > EOB, which implies that this coefficient is not 1. 857 */ 858 if (temp > 1) { 859 /* The correction bit is the next bit of the absolute value. */ 860 BR_buffer[BR++] = (char) (temp & 1); 861 continue; 862 } 863 864 /* Emit any pending EOBRUN and the BE correction bits */ 865 emit_eobrun(entropy); 866 867 /* Count/emit Huffman symbol for run length / number of bits */ 868 emit_ac_symbol(entropy, entropy->ac_tbl_no, (r << 4) + 1); 869 870 /* Emit output bit for newly-nonzero coef */ 871 temp = ((*block)[natural_order[k]] < 0) ? 0 : 1; 872 emit_bits_e(entropy, (unsigned int) temp, 1); 873 874 /* Emit buffered correction bits that must be associated with this code */ 875 emit_buffered_bits(entropy, BR_buffer, BR); 876 BR_buffer = entropy->bit_buffer; /* BE bits are gone now */ 877 BR = 0; 878 r = 0; /* reset zero run length */ 879 } 880 881 if (r > 0 || BR > 0) { /* If there are trailing zeroes, */ 882 entropy->EOBRUN++; /* count an EOB */ 883 entropy->BE += BR; /* concat my correction bits to older ones */ 884 /* We force out the EOB if we risk either: 885 * 1. overflow of the EOB counter; 886 * 2. overflow of the correction bit buffer during the next MCU. 887 */ 888 if (entropy->EOBRUN == 0x7FFF || entropy->BE > (MAX_CORR_BITS-DCTSIZE2+1)) 889 emit_eobrun(entropy); 890 } 891 892 cinfo->dest->next_output_byte = entropy->next_output_byte; 893 cinfo->dest->free_in_buffer = entropy->free_in_buffer; 894 895 /* Update restart-interval state too */ 896 if (cinfo->restart_interval) { 897 if (entropy->restarts_to_go == 0) { 898 entropy->restarts_to_go = cinfo->restart_interval; 899 entropy->next_restart_num++; 900 entropy->next_restart_num &= 7; 901 } 902 entropy->restarts_to_go--; 903 } 904 905 return TRUE; 906 } 907 908 909 /* Encode a single block's worth of coefficients */ 910 911 LOCAL(boolean) 912 encode_one_block (working_state * state, JCOEFPTR block, int last_dc_val, 913 c_derived_tbl *dctbl, c_derived_tbl *actbl) 914 { 915 register int temp, temp2; 916 register int nbits; 917 register int r, k; 918 int Se = state->cinfo->lim_Se; 919 const int * natural_order = state->cinfo->natural_order; 920 921 /* Encode the DC coefficient difference per section F.1.2.1 */ 922 923 temp = temp2 = block[0] - last_dc_val; 924 925 if (temp < 0) { 926 temp = -temp; /* temp is abs value of input */ 927 /* For a negative input, want temp2 = bitwise complement of abs(input) */ 928 /* This code assumes we are on a two's complement machine */ 929 temp2--; 930 } 931 932 /* Find the number of bits needed for the magnitude of the coefficient */ 933 nbits = 0; 934 while (temp) { 935 nbits++; 936 temp >>= 1; 937 } 938 /* Check for out-of-range coefficient values. 939 * Since we're encoding a difference, the range limit is twice as much. 940 */ 941 if (nbits > MAX_COEF_BITS+1) 942 ERREXIT(state->cinfo, JERR_BAD_DCT_COEF); 943 944 /* Emit the Huffman-coded symbol for the number of bits */ 945 if (! emit_bits_s(state, dctbl->ehufco[nbits], dctbl->ehufsi[nbits])) 946 return FALSE; 947 948 /* Emit that number of bits of the value, if positive, */ 949 /* or the complement of its magnitude, if negative. */ 950 if (nbits) /* emit_bits rejects calls with size 0 */ 951 if (! emit_bits_s(state, (unsigned int) temp2, nbits)) 952 return FALSE; 953 954 /* Encode the AC coefficients per section F.1.2.2 */ 955 956 r = 0; /* r = run length of zeros */ 957 958 for (k = 1; k <= Se; k++) { 959 if ((temp2 = block[natural_order[k]]) == 0) { 960 r++; 961 } else { 962 /* if run length > 15, must emit special run-length-16 codes (0xF0) */ 963 while (r > 15) { 964 if (! emit_bits_s(state, actbl->ehufco[0xF0], actbl->ehufsi[0xF0])) 965 return FALSE; 966 r -= 16; 967 } 968 969 temp = temp2; 970 if (temp < 0) { 971 temp = -temp; /* temp is abs value of input */ 972 /* This code assumes we are on a two's complement machine */ 973 temp2--; 974 } 975 976 /* Find the number of bits needed for the magnitude of the coefficient */ 977 nbits = 1; /* there must be at least one 1 bit */ 978 while ((temp >>= 1)) 979 nbits++; 980 /* Check for out-of-range coefficient values */ 981 if (nbits > MAX_COEF_BITS) 982 ERREXIT(state->cinfo, JERR_BAD_DCT_COEF); 983 984 /* Emit Huffman symbol for run length / number of bits */ 985 temp = (r << 4) + nbits; 986 if (! emit_bits_s(state, actbl->ehufco[temp], actbl->ehufsi[temp])) 987 return FALSE; 988 989 /* Emit that number of bits of the value, if positive, */ 990 /* or the complement of its magnitude, if negative. */ 991 if (! emit_bits_s(state, (unsigned int) temp2, nbits)) 992 return FALSE; 993 994 r = 0; 995 } 996 } 997 998 /* If the last coef(s) were zero, emit an end-of-block code */ 999 if (r > 0) 1000 if (! emit_bits_s(state, actbl->ehufco[0], actbl->ehufsi[0])) 1001 return FALSE; 1002 1003 return TRUE; 1004 } 1005 1006 1007 /* 1008 * Encode and output one MCU's worth of Huffman-compressed coefficients. 1009 */ 1010 1011 METHODDEF(boolean) 1012 encode_mcu_huff (j_compress_ptr cinfo, JBLOCKROW *MCU_data) 1013 { 1014 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy; 1015 working_state state; 1016 int blkn, ci; 1017 jpeg_component_info * compptr; 1018 1019 /* Load up working state */ 1020 state.next_output_byte = cinfo->dest->next_output_byte; 1021 state.free_in_buffer = cinfo->dest->free_in_buffer; 1022 ASSIGN_STATE(state.cur, entropy->saved); 1023 state.cinfo = cinfo; 1024 1025 /* Emit restart marker if needed */ 1026 if (cinfo->restart_interval) { 1027 if (entropy->restarts_to_go == 0) 1028 if (! emit_restart_s(&state, entropy->next_restart_num)) 1029 return FALSE; 1030 } 1031 1032 /* Encode the MCU data blocks */ 1033 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) { 1034 ci = cinfo->MCU_membership[blkn]; 1035 compptr = cinfo->cur_comp_info[ci]; 1036 if (! encode_one_block(&state, 1037 MCU_data[blkn][0], state.cur.last_dc_val[ci], 1038 entropy->dc_derived_tbls[compptr->dc_tbl_no], 1039 entropy->ac_derived_tbls[compptr->ac_tbl_no])) 1040 return FALSE; 1041 /* Update last_dc_val */ 1042 state.cur.last_dc_val[ci] = MCU_data[blkn][0][0]; 1043 } 1044 1045 /* Completed MCU, so update state */ 1046 cinfo->dest->next_output_byte = state.next_output_byte; 1047 cinfo->dest->free_in_buffer = state.free_in_buffer; 1048 ASSIGN_STATE(entropy->saved, state.cur); 1049 1050 /* Update restart-interval state too */ 1051 if (cinfo->restart_interval) { 1052 if (entropy->restarts_to_go == 0) { 1053 entropy->restarts_to_go = cinfo->restart_interval; 1054 entropy->next_restart_num++; 1055 entropy->next_restart_num &= 7; 1056 } 1057 entropy->restarts_to_go--; 1058 } 1059 1060 return TRUE; 1061 } 1062 1063 1064 /* 1065 * Finish up at the end of a Huffman-compressed scan. 1066 */ 1067 1068 METHODDEF(void) 1069 finish_pass_huff (j_compress_ptr cinfo) 1070 { 1071 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy; 1072 working_state state; 1073 1074 if (cinfo->progressive_mode) { 1075 entropy->next_output_byte = cinfo->dest->next_output_byte; 1076 entropy->free_in_buffer = cinfo->dest->free_in_buffer; 1077 1078 /* Flush out any buffered data */ 1079 emit_eobrun(entropy); 1080 flush_bits_e(entropy); 1081 1082 cinfo->dest->next_output_byte = entropy->next_output_byte; 1083 cinfo->dest->free_in_buffer = entropy->free_in_buffer; 1084 } else { 1085 /* Load up working state ... flush_bits needs it */ 1086 state.next_output_byte = cinfo->dest->next_output_byte; 1087 state.free_in_buffer = cinfo->dest->free_in_buffer; 1088 ASSIGN_STATE(state.cur, entropy->saved); 1089 state.cinfo = cinfo; 1090 1091 /* Flush out the last data */ 1092 if (! flush_bits_s(&state)) 1093 ERREXIT(cinfo, JERR_CANT_SUSPEND); 1094 1095 /* Update state */ 1096 cinfo->dest->next_output_byte = state.next_output_byte; 1097 cinfo->dest->free_in_buffer = state.free_in_buffer; 1098 ASSIGN_STATE(entropy->saved, state.cur); 1099 } 1100 } 1101 1102 1103 /* 1104 * Huffman coding optimization. 1105 * 1106 * We first scan the supplied data and count the number of uses of each symbol 1107 * that is to be Huffman-coded. (This process MUST agree with the code above.) 1108 * Then we build a Huffman coding tree for the observed counts. 1109 * Symbols which are not needed at all for the particular image are not 1110 * assigned any code, which saves space in the DHT marker as well as in 1111 * the compressed data. 1112 */ 1113 1114 1115 /* Process a single block's worth of coefficients */ 1116 1117 LOCAL(void) 1118 htest_one_block (j_compress_ptr cinfo, JCOEFPTR block, int last_dc_val, 1119 long dc_counts[], long ac_counts[]) 1120 { 1121 register int temp; 1122 register int nbits; 1123 register int r, k; 1124 int Se = cinfo->lim_Se; 1125 const int * natural_order = cinfo->natural_order; 1126 1127 /* Encode the DC coefficient difference per section F.1.2.1 */ 1128 1129 temp = block[0] - last_dc_val; 1130 if (temp < 0) 1131 temp = -temp; 1132 1133 /* Find the number of bits needed for the magnitude of the coefficient */ 1134 nbits = 0; 1135 while (temp) { 1136 nbits++; 1137 temp >>= 1; 1138 } 1139 /* Check for out-of-range coefficient values. 1140 * Since we're encoding a difference, the range limit is twice as much. 1141 */ 1142 if (nbits > MAX_COEF_BITS+1) 1143 ERREXIT(cinfo, JERR_BAD_DCT_COEF); 1144 1145 /* Count the Huffman symbol for the number of bits */ 1146 dc_counts[nbits]++; 1147 1148 /* Encode the AC coefficients per section F.1.2.2 */ 1149 1150 r = 0; /* r = run length of zeros */ 1151 1152 for (k = 1; k <= Se; k++) { 1153 if ((temp = block[natural_order[k]]) == 0) { 1154 r++; 1155 } else { 1156 /* if run length > 15, must emit special run-length-16 codes (0xF0) */ 1157 while (r > 15) { 1158 ac_counts[0xF0]++; 1159 r -= 16; 1160 } 1161 1162 /* Find the number of bits needed for the magnitude of the coefficient */ 1163 if (temp < 0) 1164 temp = -temp; 1165 1166 /* Find the number of bits needed for the magnitude of the coefficient */ 1167 nbits = 1; /* there must be at least one 1 bit */ 1168 while ((temp >>= 1)) 1169 nbits++; 1170 /* Check for out-of-range coefficient values */ 1171 if (nbits > MAX_COEF_BITS) 1172 ERREXIT(cinfo, JERR_BAD_DCT_COEF); 1173 1174 /* Count Huffman symbol for run length / number of bits */ 1175 ac_counts[(r << 4) + nbits]++; 1176 1177 r = 0; 1178 } 1179 } 1180 1181 /* If the last coef(s) were zero, emit an end-of-block code */ 1182 if (r > 0) 1183 ac_counts[0]++; 1184 } 1185 1186 1187 /* 1188 * Trial-encode one MCU's worth of Huffman-compressed coefficients. 1189 * No data is actually output, so no suspension return is possible. 1190 */ 1191 1192 METHODDEF(boolean) 1193 encode_mcu_gather (j_compress_ptr cinfo, JBLOCKROW *MCU_data) 1194 { 1195 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy; 1196 int blkn, ci; 1197 jpeg_component_info * compptr; 1198 1199 /* Take care of restart intervals if needed */ 1200 if (cinfo->restart_interval) { 1201 if (entropy->restarts_to_go == 0) { 1202 /* Re-initialize DC predictions to 0 */ 1203 for (ci = 0; ci < cinfo->comps_in_scan; ci++) 1204 entropy->saved.last_dc_val[ci] = 0; 1205 /* Update restart state */ 1206 entropy->restarts_to_go = cinfo->restart_interval; 1207 } 1208 entropy->restarts_to_go--; 1209 } 1210 1211 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) { 1212 ci = cinfo->MCU_membership[blkn]; 1213 compptr = cinfo->cur_comp_info[ci]; 1214 htest_one_block(cinfo, MCU_data[blkn][0], entropy->saved.last_dc_val[ci], 1215 entropy->dc_count_ptrs[compptr->dc_tbl_no], 1216 entropy->ac_count_ptrs[compptr->ac_tbl_no]); 1217 entropy->saved.last_dc_val[ci] = MCU_data[blkn][0][0]; 1218 } 1219 1220 return TRUE; 1221 } 1222 1223 1224 /* 1225 * Generate the best Huffman code table for the given counts, fill htbl. 1226 * 1227 * The JPEG standard requires that no symbol be assigned a codeword of all 1228 * one bits (so that padding bits added at the end of a compressed segment 1229 * can't look like a valid code). Because of the canonical ordering of 1230 * codewords, this just means that there must be an unused slot in the 1231 * longest codeword length category. Section K.2 of the JPEG spec suggests 1232 * reserving such a slot by pretending that symbol 256 is a valid symbol 1233 * with count 1. In theory that's not optimal; giving it count zero but 1234 * including it in the symbol set anyway should give a better Huffman code. 1235 * But the theoretically better code actually seems to come out worse in 1236 * practice, because it produces more all-ones bytes (which incur stuffed 1237 * zero bytes in the final file). In any case the difference is tiny. 1238 * 1239 * The JPEG standard requires Huffman codes to be no more than 16 bits long. 1240 * If some symbols have a very small but nonzero probability, the Huffman tree 1241 * must be adjusted to meet the code length restriction. We currently use 1242 * the adjustment method suggested in JPEG section K.2. This method is *not* 1243 * optimal; it may not choose the best possible limited-length code. But 1244 * typically only very-low-frequency symbols will be given less-than-optimal 1245 * lengths, so the code is almost optimal. Experimental comparisons against 1246 * an optimal limited-length-code algorithm indicate that the difference is 1247 * microscopic --- usually less than a hundredth of a percent of total size. 1248 * So the extra complexity of an optimal algorithm doesn't seem worthwhile. 1249 */ 1250 1251 LOCAL(void) 1252 jpeg_gen_optimal_table (j_compress_ptr cinfo, JHUFF_TBL * htbl, long freq[]) 1253 { 1254 #define MAX_CLEN 32 /* assumed maximum initial code length */ 1255 UINT8 bits[MAX_CLEN+1]; /* bits[k] = # of symbols with code length k */ 1256 int codesize[257]; /* codesize[k] = code length of symbol k */ 1257 int others[257]; /* next symbol in current branch of tree */ 1258 int c1, c2, i, j; 1259 UINT8 *p; 1260 long v; 1261 1262 freq[256] = 1; /* make sure 256 has a nonzero count */ 1263 /* Including the pseudo-symbol 256 in the Huffman procedure guarantees 1264 * that no real symbol is given code-value of all ones, because 256 1265 * will be placed last in the largest codeword category. 1266 * In the symbol list build procedure this element serves as sentinel 1267 * for the zero run loop. 1268 */ 1269 1270 #ifndef DONT_USE_FANCY_HUFF_OPT 1271 1272 /* Build list of symbols sorted in order of descending frequency */ 1273 /* This approach has several benefits (thank to John Korejwa for the idea): 1274 * 1. 1275 * If a codelength category is split during the length limiting procedure 1276 * below, the feature that more frequent symbols are assigned shorter 1277 * codewords remains valid for the adjusted code. 1278 * 2. 1279 * To reduce consecutive ones in a Huffman data stream (thus reducing the 1280 * number of stuff bytes in JPEG) it is preferable to follow 0 branches 1281 * (and avoid 1 branches) as much as possible. This is easily done by 1282 * assigning symbols to leaves of the Huffman tree in order of decreasing 1283 * frequency, with no secondary sort based on codelengths. 1284 * 3. 1285 * The symbol list can be built independently from the assignment of code 1286 * lengths by the Huffman procedure below. 1287 * Note: The symbol list build procedure must be performed first, because 1288 * the Huffman procedure assigning the codelengths clobbers the frequency 1289 * counts! 1290 */ 1291 1292 /* Here we use the others array as a linked list of nonzero frequencies 1293 * to be sorted. Already sorted elements are removed from the list. 1294 */ 1295 1296 /* Building list */ 1297 1298 /* This item does not correspond to a valid symbol frequency and is used 1299 * as starting index. 1300 */ 1301 j = 256; 1302 1303 for (i = 0;; i++) { 1304 if (freq[i] == 0) /* skip zero frequencies */ 1305 continue; 1306 if (i > 255) 1307 break; 1308 others[j] = i; /* this symbol value */ 1309 j = i; /* previous symbol value */ 1310 } 1311 others[j] = -1; /* mark end of list */ 1312 1313 /* Sorting list */ 1314 1315 p = htbl->huffval; 1316 while ((c1 = others[256]) >= 0) { 1317 v = freq[c1]; 1318 i = c1; /* first symbol value */ 1319 j = 256; /* pseudo symbol value for starting index */ 1320 while ((c2 = others[c1]) >= 0) { 1321 if (freq[c2] > v) { 1322 v = freq[c2]; 1323 i = c2; /* this symbol value */ 1324 j = c1; /* previous symbol value */ 1325 } 1326 c1 = c2; 1327 } 1328 others[j] = others[i]; /* remove this symbol i from list */ 1329 *p++ = (UINT8) i; 1330 } 1331 1332 #endif /* DONT_USE_FANCY_HUFF_OPT */ 1333 1334 /* This algorithm is explained in section K.2 of the JPEG standard */ 1335 1336 MEMZERO(bits, SIZEOF(bits)); 1337 MEMZERO(codesize, SIZEOF(codesize)); 1338 for (i = 0; i < 257; i++) 1339 others[i] = -1; /* init links to empty */ 1340 1341 /* Huffman's basic algorithm to assign optimal code lengths to symbols */ 1342 1343 for (;;) { 1344 /* Find the smallest nonzero frequency, set c1 = its symbol */ 1345 /* In case of ties, take the larger symbol number */ 1346 c1 = -1; 1347 v = 1000000000L; 1348 for (i = 0; i <= 256; i++) { 1349 if (freq[i] && freq[i] <= v) { 1350 v = freq[i]; 1351 c1 = i; 1352 } 1353 } 1354 1355 /* Find the next smallest nonzero frequency, set c2 = its symbol */ 1356 /* In case of ties, take the larger symbol number */ 1357 c2 = -1; 1358 v = 1000000000L; 1359 for (i = 0; i <= 256; i++) { 1360 if (freq[i] && freq[i] <= v && i != c1) { 1361 v = freq[i]; 1362 c2 = i; 1363 } 1364 } 1365 1366 /* Done if we've merged everything into one frequency */ 1367 if (c2 < 0) 1368 break; 1369 1370 /* Else merge the two counts/trees */ 1371 freq[c1] += freq[c2]; 1372 freq[c2] = 0; 1373 1374 /* Increment the codesize of everything in c1's tree branch */ 1375 codesize[c1]++; 1376 while (others[c1] >= 0) { 1377 c1 = others[c1]; 1378 codesize[c1]++; 1379 } 1380 1381 others[c1] = c2; /* chain c2 onto c1's tree branch */ 1382 1383 /* Increment the codesize of everything in c2's tree branch */ 1384 codesize[c2]++; 1385 while (others[c2] >= 0) { 1386 c2 = others[c2]; 1387 codesize[c2]++; 1388 } 1389 } 1390 1391 /* Now count the number of symbols of each code length */ 1392 for (i = 0; i <= 256; i++) { 1393 if (codesize[i]) { 1394 /* The JPEG standard seems to think that this can't happen, */ 1395 /* but I'm paranoid... */ 1396 if (codesize[i] > MAX_CLEN) 1397 ERREXIT(cinfo, JERR_HUFF_CLEN_OUTOFBOUNDS); 1398 1399 bits[codesize[i]]++; 1400 } 1401 } 1402 1403 /* JPEG doesn't allow symbols with code lengths over 16 bits, so if the pure 1404 * Huffman procedure assigned any such lengths, we must adjust the coding. 1405 * Here is what the JPEG spec says about how this next bit works: 1406 * Since symbols are paired for the longest Huffman code, the symbols are 1407 * removed from this length category two at a time. The prefix for the pair 1408 * (which is one bit shorter) is allocated to one of the pair; then, 1409 * skipping the BITS entry for that prefix length, a code word from the next 1410 * shortest nonzero BITS entry is converted into a prefix for two code words 1411 * one bit longer. 1412 */ 1413 1414 for (i = MAX_CLEN; i > 16; i--) { 1415 while (bits[i] > 0) { 1416 j = i - 2; /* find length of new prefix to be used */ 1417 while (bits[j] == 0) { 1418 if (j == 0) 1419 ERREXIT(cinfo, JERR_HUFF_CLEN_OUTOFBOUNDS); 1420 j--; 1421 } 1422 1423 bits[i] -= 2; /* remove two symbols */ 1424 bits[i-1]++; /* one goes in this length */ 1425 bits[j+1] += 2; /* two new symbols in this length */ 1426 bits[j]--; /* symbol of this length is now a prefix */ 1427 } 1428 } 1429 1430 /* Remove the count for the pseudo-symbol 256 from the largest codelength */ 1431 while (bits[i] == 0) /* find largest codelength still in use */ 1432 i--; 1433 bits[i]--; 1434 1435 /* Return final symbol counts (only for lengths 0..16) */ 1436 MEMCOPY(htbl->bits, bits, SIZEOF(htbl->bits)); 1437 1438 #ifdef DONT_USE_FANCY_HUFF_OPT 1439 1440 /* Return a list of the symbols sorted by code length */ 1441 /* Note: Due to the codelength changes made above, it can happen 1442 * that more frequent symbols are assigned longer codewords. 1443 */ 1444 p = htbl->huffval; 1445 for (i = 1; i <= MAX_CLEN; i++) { 1446 for (j = 0; j <= 255; j++) { 1447 if (codesize[j] == i) { 1448 *p++ = (UINT8) j; 1449 } 1450 } 1451 } 1452 1453 #endif /* DONT_USE_FANCY_HUFF_OPT */ 1454 1455 /* Set sent_table FALSE so updated table will be written to JPEG file. */ 1456 htbl->sent_table = FALSE; 1457 } 1458 1459 1460 /* 1461 * Finish up a statistics-gathering pass and create the new Huffman tables. 1462 */ 1463 1464 METHODDEF(void) 1465 finish_pass_gather (j_compress_ptr cinfo) 1466 { 1467 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy; 1468 int ci, tbl; 1469 jpeg_component_info * compptr; 1470 JHUFF_TBL **htblptr; 1471 boolean did_dc[NUM_HUFF_TBLS]; 1472 boolean did_ac[NUM_HUFF_TBLS]; 1473 1474 if (cinfo->progressive_mode) 1475 /* Flush out buffered data (all we care about is counting the EOB symbol) */ 1476 emit_eobrun(entropy); 1477 1478 /* It's important not to apply jpeg_gen_optimal_table more than once 1479 * per table, because it clobbers the input frequency counts! 1480 */ 1481 MEMZERO(did_dc, SIZEOF(did_dc)); 1482 MEMZERO(did_ac, SIZEOF(did_ac)); 1483 1484 for (ci = 0; ci < cinfo->comps_in_scan; ci++) { 1485 compptr = cinfo->cur_comp_info[ci]; 1486 /* DC needs no table for refinement scan */ 1487 if (cinfo->Ss == 0 && cinfo->Ah == 0) { 1488 tbl = compptr->dc_tbl_no; 1489 if (! did_dc[tbl]) { 1490 htblptr = & cinfo->dc_huff_tbl_ptrs[tbl]; 1491 if (*htblptr == NULL) 1492 *htblptr = jpeg_alloc_huff_table((j_common_ptr) cinfo); 1493 jpeg_gen_optimal_table(cinfo, *htblptr, entropy->dc_count_ptrs[tbl]); 1494 did_dc[tbl] = TRUE; 1495 } 1496 } 1497 /* AC needs no table when not present */ 1498 if (cinfo->Se) { 1499 tbl = compptr->ac_tbl_no; 1500 if (! did_ac[tbl]) { 1501 htblptr = & cinfo->ac_huff_tbl_ptrs[tbl]; 1502 if (*htblptr == NULL) 1503 *htblptr = jpeg_alloc_huff_table((j_common_ptr) cinfo); 1504 jpeg_gen_optimal_table(cinfo, *htblptr, entropy->ac_count_ptrs[tbl]); 1505 did_ac[tbl] = TRUE; 1506 } 1507 } 1508 } 1509 } 1510 1511 1512 /* 1513 * Initialize for a Huffman-compressed scan. 1514 * If gather_statistics is TRUE, we do not output anything during the scan, 1515 * just count the Huffman symbols used and generate Huffman code tables. 1516 */ 1517 1518 METHODDEF(void) 1519 start_pass_huff (j_compress_ptr cinfo, boolean gather_statistics) 1520 { 1521 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy; 1522 int ci, tbl; 1523 jpeg_component_info * compptr; 1524 1525 if (gather_statistics) 1526 entropy->pub.finish_pass = finish_pass_gather; 1527 else 1528 entropy->pub.finish_pass = finish_pass_huff; 1529 1530 if (cinfo->progressive_mode) { 1531 entropy->cinfo = cinfo; 1532 entropy->gather_statistics = gather_statistics; 1533 1534 /* We assume jcmaster.c already validated the scan parameters. */ 1535 1536 /* Select execution routine */ 1537 if (cinfo->Ah == 0) { 1538 if (cinfo->Ss == 0) 1539 entropy->pub.encode_mcu = encode_mcu_DC_first; 1540 else 1541 entropy->pub.encode_mcu = encode_mcu_AC_first; 1542 } else { 1543 if (cinfo->Ss == 0) 1544 entropy->pub.encode_mcu = encode_mcu_DC_refine; 1545 else { 1546 entropy->pub.encode_mcu = encode_mcu_AC_refine; 1547 /* AC refinement needs a correction bit buffer */ 1548 if (entropy->bit_buffer == NULL) 1549 entropy->bit_buffer = (char *) (*cinfo->mem->alloc_small) 1550 ((j_common_ptr) cinfo, JPOOL_IMAGE, MAX_CORR_BITS * SIZEOF(char)); 1551 } 1552 } 1553 1554 /* Initialize AC stuff */ 1555 entropy->ac_tbl_no = cinfo->cur_comp_info[0]->ac_tbl_no; 1556 entropy->EOBRUN = 0; 1557 entropy->BE = 0; 1558 } else { 1559 if (gather_statistics) 1560 entropy->pub.encode_mcu = encode_mcu_gather; 1561 else 1562 entropy->pub.encode_mcu = encode_mcu_huff; 1563 } 1564 1565 for (ci = 0; ci < cinfo->comps_in_scan; ci++) { 1566 compptr = cinfo->cur_comp_info[ci]; 1567 /* DC needs no table for refinement scan */ 1568 if (cinfo->Ss == 0 && cinfo->Ah == 0) { 1569 tbl = compptr->dc_tbl_no; 1570 if (gather_statistics) { 1571 /* Check for invalid table index */ 1572 /* (make_c_derived_tbl does this in the other path) */ 1573 if (tbl < 0 || tbl >= NUM_HUFF_TBLS) 1574 ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tbl); 1575 /* Allocate and zero the statistics tables */ 1576 /* Note that jpeg_gen_optimal_table expects 257 entries in each table! */ 1577 if (entropy->dc_count_ptrs[tbl] == NULL) 1578 entropy->dc_count_ptrs[tbl] = (long *) (*cinfo->mem->alloc_small) 1579 ((j_common_ptr) cinfo, JPOOL_IMAGE, 257 * SIZEOF(long)); 1580 MEMZERO(entropy->dc_count_ptrs[tbl], 257 * SIZEOF(long)); 1581 } else { 1582 /* Compute derived values for Huffman tables */ 1583 /* We may do this more than once for a table, but it's not expensive */ 1584 jpeg_make_c_derived_tbl(cinfo, TRUE, tbl, 1585 & entropy->dc_derived_tbls[tbl]); 1586 } 1587 /* Initialize DC predictions to 0 */ 1588 entropy->saved.last_dc_val[ci] = 0; 1589 } 1590 /* AC needs no table when not present */ 1591 if (cinfo->Se) { 1592 tbl = compptr->ac_tbl_no; 1593 if (gather_statistics) { 1594 if (tbl < 0 || tbl >= NUM_HUFF_TBLS) 1595 ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tbl); 1596 if (entropy->ac_count_ptrs[tbl] == NULL) 1597 entropy->ac_count_ptrs[tbl] = (long *) (*cinfo->mem->alloc_small) 1598 ((j_common_ptr) cinfo, JPOOL_IMAGE, 257 * SIZEOF(long)); 1599 MEMZERO(entropy->ac_count_ptrs[tbl], 257 * SIZEOF(long)); 1600 } else { 1601 jpeg_make_c_derived_tbl(cinfo, FALSE, tbl, 1602 & entropy->ac_derived_tbls[tbl]); 1603 } 1604 } 1605 } 1606 1607 /* Initialize bit buffer to empty */ 1608 entropy->saved.put_buffer = 0; 1609 entropy->saved.put_bits = 0; 1610 1611 /* Initialize restart stuff */ 1612 entropy->restarts_to_go = cinfo->restart_interval; 1613 entropy->next_restart_num = 0; 1614 } 1615 1616 1617 /* 1618 * Module initialization routine for Huffman entropy encoding. 1619 */ 1620 1621 GLOBAL(void) 1622 jinit_huff_encoder (j_compress_ptr cinfo) 1623 { 1624 huff_entropy_ptr entropy; 1625 int i; 1626 1627 entropy = (huff_entropy_ptr) (*cinfo->mem->alloc_small) 1628 ((j_common_ptr) cinfo, JPOOL_IMAGE, SIZEOF(huff_entropy_encoder)); 1629 cinfo->entropy = &entropy->pub; 1630 entropy->pub.start_pass = start_pass_huff; 1631 1632 /* Mark tables unallocated */ 1633 for (i = 0; i < NUM_HUFF_TBLS; i++) { 1634 entropy->dc_derived_tbls[i] = entropy->ac_derived_tbls[i] = NULL; 1635 entropy->dc_count_ptrs[i] = entropy->ac_count_ptrs[i] = NULL; 1636 } 1637 1638 if (cinfo->progressive_mode) 1639 entropy->bit_buffer = NULL; /* needed only in AC refinement scan */ 1640 } 1641