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