jchuff.c (37246B)
1 /* 2 * jchuff.c 3 * 4 * This file was part of the Independent JPEG Group's software: 5 * Copyright (C) 1991-1997, Thomas G. Lane. 6 * Lossless JPEG Modifications: 7 * Copyright (C) 1999, Ken Murchison. 8 * libjpeg-turbo Modifications: 9 * Copyright (C) 2009-2011, 2014-2016, 2018-2024, D. R. Commander. 10 * Copyright (C) 2015, Matthieu Darbois. 11 * Copyright (C) 2018, Matthias Räncker. 12 * Copyright (C) 2020, Arm Limited. 13 * Copyright (C) 2022, Felix Hanau. 14 * For conditions of distribution and use, see the accompanying README.ijg 15 * file. 16 * 17 * This file contains Huffman entropy encoding routines. 18 * 19 * Much of the complexity here has to do with supporting output suspension. 20 * If the data destination module demands suspension, we want to be able to 21 * back up to the start of the current MCU. To do this, we copy state 22 * variables into local working storage, and update them back to the 23 * permanent JPEG objects only upon successful completion of an MCU. 24 * 25 * NOTE: All referenced figures are from 26 * Recommendation ITU-T T.81 (1992) | ISO/IEC 10918-1:1994. 27 */ 28 29 #define JPEG_INTERNALS 30 #include "jinclude.h" 31 #include "jpeglib.h" 32 #ifdef WITH_SIMD 33 #include "jsimd.h" 34 #else 35 #include "jchuff.h" /* Declarations shared with jc*huff.c */ 36 #endif 37 #include <limits.h> 38 #include "jpeg_nbits.h" 39 40 41 /* Expanded entropy encoder object for Huffman encoding. 42 * 43 * The savable_state subrecord contains fields that change within an MCU, 44 * but must not be updated permanently until we complete the MCU. 45 */ 46 47 #if defined(__x86_64__) && defined(__ILP32__) 48 typedef unsigned long long bit_buf_type; 49 #else 50 typedef size_t bit_buf_type; 51 #endif 52 53 /* NOTE: The more optimal Huffman encoding algorithm is only used by the 54 * intrinsics implementation of the Arm Neon SIMD extensions, which is why we 55 * retain the old Huffman encoder behavior when using the GAS implementation. 56 */ 57 #if defined(WITH_SIMD) && !(defined(__arm__) || defined(__aarch64__) || \ 58 defined(_M_ARM) || defined(_M_ARM64)) 59 typedef unsigned long long simd_bit_buf_type; 60 #else 61 typedef bit_buf_type simd_bit_buf_type; 62 #endif 63 64 #if (defined(SIZEOF_SIZE_T) && SIZEOF_SIZE_T == 8) || defined(_WIN64) || \ 65 (defined(__x86_64__) && defined(__ILP32__)) 66 #define BIT_BUF_SIZE 64 67 #elif (defined(SIZEOF_SIZE_T) && SIZEOF_SIZE_T == 4) || defined(_WIN32) 68 #define BIT_BUF_SIZE 32 69 #else 70 #error Cannot determine word size 71 #endif 72 #define SIMD_BIT_BUF_SIZE (sizeof(simd_bit_buf_type) * 8) 73 74 typedef struct { 75 union { 76 bit_buf_type c; 77 #ifdef WITH_SIMD 78 simd_bit_buf_type simd; 79 #endif 80 } put_buffer; /* current bit accumulation buffer */ 81 int free_bits; /* # of bits available in it */ 82 /* (Neon GAS: # of bits now in it) */ 83 int last_dc_val[MAX_COMPS_IN_SCAN]; /* last DC coef for each component */ 84 } savable_state; 85 86 typedef struct { 87 struct jpeg_entropy_encoder pub; /* public fields */ 88 89 savable_state saved; /* Bit buffer & DC state at start of MCU */ 90 91 /* These fields are NOT loaded into local working state. */ 92 unsigned int restarts_to_go; /* MCUs left in this restart interval */ 93 int next_restart_num; /* next restart number to write (0-7) */ 94 95 /* Pointers to derived tables (these workspaces have image lifespan) */ 96 c_derived_tbl *dc_derived_tbls[NUM_HUFF_TBLS]; 97 c_derived_tbl *ac_derived_tbls[NUM_HUFF_TBLS]; 98 99 #ifdef ENTROPY_OPT_SUPPORTED /* Statistics tables for optimization */ 100 long *dc_count_ptrs[NUM_HUFF_TBLS]; 101 long *ac_count_ptrs[NUM_HUFF_TBLS]; 102 #endif 103 104 #ifdef WITH_SIMD 105 int simd; 106 #endif 107 } huff_entropy_encoder; 108 109 typedef huff_entropy_encoder *huff_entropy_ptr; 110 111 /* Working state while writing an MCU. 112 * This struct contains all the fields that are needed by subroutines. 113 */ 114 115 typedef struct { 116 JOCTET *next_output_byte; /* => next byte to write in buffer */ 117 size_t free_in_buffer; /* # of byte spaces remaining in buffer */ 118 savable_state cur; /* Current bit buffer & DC state */ 119 j_compress_ptr cinfo; /* dump_buffer needs access to this */ 120 #ifdef WITH_SIMD 121 int simd; 122 #endif 123 } working_state; 124 125 126 /* Forward declarations */ 127 METHODDEF(boolean) encode_mcu_huff(j_compress_ptr cinfo, JBLOCKROW *MCU_data); 128 METHODDEF(void) finish_pass_huff(j_compress_ptr cinfo); 129 #ifdef ENTROPY_OPT_SUPPORTED 130 METHODDEF(boolean) encode_mcu_gather(j_compress_ptr cinfo, 131 JBLOCKROW *MCU_data); 132 METHODDEF(void) finish_pass_gather(j_compress_ptr cinfo); 133 #endif 134 135 136 /* 137 * Initialize for a Huffman-compressed scan. 138 * If gather_statistics is TRUE, we do not output anything during the scan, 139 * just count the Huffman symbols used and generate Huffman code tables. 140 */ 141 142 METHODDEF(void) 143 start_pass_huff(j_compress_ptr cinfo, boolean gather_statistics) 144 { 145 huff_entropy_ptr entropy = (huff_entropy_ptr)cinfo->entropy; 146 int ci, dctbl, actbl; 147 jpeg_component_info *compptr; 148 149 if (gather_statistics) { 150 #ifdef ENTROPY_OPT_SUPPORTED 151 entropy->pub.encode_mcu = encode_mcu_gather; 152 entropy->pub.finish_pass = finish_pass_gather; 153 #else 154 ERREXIT(cinfo, JERR_NOT_COMPILED); 155 #endif 156 } else { 157 entropy->pub.encode_mcu = encode_mcu_huff; 158 entropy->pub.finish_pass = finish_pass_huff; 159 } 160 161 #ifdef WITH_SIMD 162 entropy->simd = jsimd_can_huff_encode_one_block(); 163 #endif 164 165 for (ci = 0; ci < cinfo->comps_in_scan; ci++) { 166 compptr = cinfo->cur_comp_info[ci]; 167 dctbl = compptr->dc_tbl_no; 168 actbl = compptr->ac_tbl_no; 169 if (gather_statistics) { 170 #ifdef ENTROPY_OPT_SUPPORTED 171 /* Check for invalid table indexes */ 172 /* (make_c_derived_tbl does this in the other path) */ 173 if (dctbl < 0 || dctbl >= NUM_HUFF_TBLS) 174 ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, dctbl); 175 if (actbl < 0 || actbl >= NUM_HUFF_TBLS) 176 ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, actbl); 177 /* Allocate and zero the statistics tables */ 178 /* Note that jpeg_gen_optimal_table expects 257 entries in each table! */ 179 if (entropy->dc_count_ptrs[dctbl] == NULL) 180 entropy->dc_count_ptrs[dctbl] = (long *) 181 (*cinfo->mem->alloc_small) ((j_common_ptr)cinfo, JPOOL_IMAGE, 182 257 * sizeof(long)); 183 memset(entropy->dc_count_ptrs[dctbl], 0, 257 * sizeof(long)); 184 if (entropy->ac_count_ptrs[actbl] == NULL) 185 entropy->ac_count_ptrs[actbl] = (long *) 186 (*cinfo->mem->alloc_small) ((j_common_ptr)cinfo, JPOOL_IMAGE, 187 257 * sizeof(long)); 188 memset(entropy->ac_count_ptrs[actbl], 0, 257 * sizeof(long)); 189 #endif 190 } else { 191 /* Compute derived values for Huffman tables */ 192 /* We may do this more than once for a table, but it's not expensive */ 193 jpeg_make_c_derived_tbl(cinfo, TRUE, dctbl, 194 &entropy->dc_derived_tbls[dctbl]); 195 jpeg_make_c_derived_tbl(cinfo, FALSE, actbl, 196 &entropy->ac_derived_tbls[actbl]); 197 } 198 /* Initialize DC predictions to 0 */ 199 entropy->saved.last_dc_val[ci] = 0; 200 } 201 202 /* Initialize bit buffer to empty */ 203 #ifdef WITH_SIMD 204 if (entropy->simd) { 205 entropy->saved.put_buffer.simd = 0; 206 #if defined(__aarch64__) && !defined(NEON_INTRINSICS) 207 entropy->saved.free_bits = 0; 208 #else 209 entropy->saved.free_bits = SIMD_BIT_BUF_SIZE; 210 #endif 211 } else 212 #endif 213 { 214 entropy->saved.put_buffer.c = 0; 215 entropy->saved.free_bits = BIT_BUF_SIZE; 216 } 217 218 /* Initialize restart stuff */ 219 entropy->restarts_to_go = cinfo->restart_interval; 220 entropy->next_restart_num = 0; 221 } 222 223 224 /* 225 * Compute the derived values for a Huffman table. 226 * This routine also performs some validation checks on the table. 227 * 228 * Note this is also used by jcphuff.c and jclhuff.c. 229 */ 230 231 GLOBAL(void) 232 jpeg_make_c_derived_tbl(j_compress_ptr cinfo, boolean isDC, int tblno, 233 c_derived_tbl **pdtbl) 234 { 235 JHUFF_TBL *htbl; 236 c_derived_tbl *dtbl; 237 int p, i, l, lastp, si, maxsymbol; 238 char huffsize[257]; 239 unsigned int huffcode[257]; 240 unsigned int code; 241 242 /* Note that huffsize[] and huffcode[] are filled in code-length order, 243 * paralleling the order of the symbols themselves in htbl->huffval[]. 244 */ 245 246 /* Find the input Huffman table */ 247 if (tblno < 0 || tblno >= NUM_HUFF_TBLS) 248 ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tblno); 249 htbl = 250 isDC ? cinfo->dc_huff_tbl_ptrs[tblno] : cinfo->ac_huff_tbl_ptrs[tblno]; 251 if (htbl == NULL) 252 ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tblno); 253 254 /* Allocate a workspace if we haven't already done so. */ 255 if (*pdtbl == NULL) 256 *pdtbl = (c_derived_tbl *) 257 (*cinfo->mem->alloc_small) ((j_common_ptr)cinfo, JPOOL_IMAGE, 258 sizeof(c_derived_tbl)); 259 dtbl = *pdtbl; 260 261 /* Figure C.1: make table of Huffman code length for each symbol */ 262 263 p = 0; 264 for (l = 1; l <= 16; l++) { 265 i = (int)htbl->bits[l]; 266 if (i < 0 || p + i > 256) /* protect against table overrun */ 267 ERREXIT(cinfo, JERR_BAD_HUFF_TABLE); 268 while (i--) 269 huffsize[p++] = (char)l; 270 } 271 huffsize[p] = 0; 272 lastp = p; 273 274 /* Figure C.2: generate the codes themselves */ 275 /* We also validate that the counts represent a legal Huffman code tree. */ 276 277 code = 0; 278 si = huffsize[0]; 279 p = 0; 280 while (huffsize[p]) { 281 while (((int)huffsize[p]) == si) { 282 huffcode[p++] = code; 283 code++; 284 } 285 /* code is now 1 more than the last code used for codelength si; but 286 * it must still fit in si bits, since no code is allowed to be all ones. 287 */ 288 if (((JLONG)code) >= (((JLONG)1) << si)) 289 ERREXIT(cinfo, JERR_BAD_HUFF_TABLE); 290 code <<= 1; 291 si++; 292 } 293 294 /* Figure C.3: generate encoding tables */ 295 /* These are code and size indexed by symbol value */ 296 297 /* Set all codeless symbols to have code length 0; 298 * this lets us detect duplicate VAL entries here, and later 299 * allows emit_bits to detect any attempt to emit such symbols. 300 */ 301 memset(dtbl->ehufco, 0, sizeof(dtbl->ehufco)); 302 memset(dtbl->ehufsi, 0, sizeof(dtbl->ehufsi)); 303 304 /* This is also a convenient place to check for out-of-range and duplicated 305 * VAL entries. We allow 0..255 for AC symbols but only 0..15 for DC in 306 * lossy mode and 0..16 for DC in lossless mode. (We could constrain them 307 * further based on data depth and mode, but this seems enough.) 308 */ 309 maxsymbol = isDC ? (cinfo->master->lossless ? 16 : 15) : 255; 310 311 for (p = 0; p < lastp; p++) { 312 i = htbl->huffval[p]; 313 if (i < 0 || i > maxsymbol || dtbl->ehufsi[i]) 314 ERREXIT(cinfo, JERR_BAD_HUFF_TABLE); 315 dtbl->ehufco[i] = huffcode[p]; 316 dtbl->ehufsi[i] = huffsize[p]; 317 } 318 } 319 320 321 /* Outputting bytes to the file */ 322 323 /* Emit a byte, taking 'action' if must suspend. */ 324 #define emit_byte(state, val, action) { \ 325 *(state)->next_output_byte++ = (JOCTET)(val); \ 326 if (--(state)->free_in_buffer == 0) \ 327 if (!dump_buffer(state)) \ 328 { action; } \ 329 } 330 331 332 LOCAL(boolean) 333 dump_buffer(working_state *state) 334 /* Empty the output buffer; return TRUE if successful, FALSE if must suspend */ 335 { 336 struct jpeg_destination_mgr *dest = state->cinfo->dest; 337 338 if (!(*dest->empty_output_buffer) (state->cinfo)) 339 return FALSE; 340 /* After a successful buffer dump, must reset buffer pointers */ 341 state->next_output_byte = dest->next_output_byte; 342 state->free_in_buffer = dest->free_in_buffer; 343 return TRUE; 344 } 345 346 347 /* Outputting bits to the file */ 348 349 /* Output byte b and, speculatively, an additional 0 byte. 0xFF must be 350 * encoded as 0xFF 0x00, so the output buffer pointer is advanced by 2 if the 351 * byte is 0xFF. Otherwise, the output buffer pointer is advanced by 1, and 352 * the speculative 0 byte will be overwritten by the next byte. 353 */ 354 #define EMIT_BYTE(b) { \ 355 buffer[0] = (JOCTET)(b); \ 356 buffer[1] = 0; \ 357 buffer -= -2 + ((JOCTET)(b) < 0xFF); \ 358 } 359 360 /* Output the entire bit buffer. If there are no 0xFF bytes in it, then write 361 * directly to the output buffer. Otherwise, use the EMIT_BYTE() macro to 362 * encode 0xFF as 0xFF 0x00. 363 */ 364 #if BIT_BUF_SIZE == 64 365 366 #define FLUSH() { \ 367 if (put_buffer & 0x8080808080808080 & ~(put_buffer + 0x0101010101010101)) { \ 368 EMIT_BYTE(put_buffer >> 56) \ 369 EMIT_BYTE(put_buffer >> 48) \ 370 EMIT_BYTE(put_buffer >> 40) \ 371 EMIT_BYTE(put_buffer >> 32) \ 372 EMIT_BYTE(put_buffer >> 24) \ 373 EMIT_BYTE(put_buffer >> 16) \ 374 EMIT_BYTE(put_buffer >> 8) \ 375 EMIT_BYTE(put_buffer ) \ 376 } else { \ 377 buffer[0] = (JOCTET)(put_buffer >> 56); \ 378 buffer[1] = (JOCTET)(put_buffer >> 48); \ 379 buffer[2] = (JOCTET)(put_buffer >> 40); \ 380 buffer[3] = (JOCTET)(put_buffer >> 32); \ 381 buffer[4] = (JOCTET)(put_buffer >> 24); \ 382 buffer[5] = (JOCTET)(put_buffer >> 16); \ 383 buffer[6] = (JOCTET)(put_buffer >> 8); \ 384 buffer[7] = (JOCTET)(put_buffer); \ 385 buffer += 8; \ 386 } \ 387 } 388 389 #else 390 391 #define FLUSH() { \ 392 if (put_buffer & 0x80808080 & ~(put_buffer + 0x01010101)) { \ 393 EMIT_BYTE(put_buffer >> 24) \ 394 EMIT_BYTE(put_buffer >> 16) \ 395 EMIT_BYTE(put_buffer >> 8) \ 396 EMIT_BYTE(put_buffer ) \ 397 } else { \ 398 buffer[0] = (JOCTET)(put_buffer >> 24); \ 399 buffer[1] = (JOCTET)(put_buffer >> 16); \ 400 buffer[2] = (JOCTET)(put_buffer >> 8); \ 401 buffer[3] = (JOCTET)(put_buffer); \ 402 buffer += 4; \ 403 } \ 404 } 405 406 #endif 407 408 /* Fill the bit buffer to capacity with the leading bits from code, then output 409 * the bit buffer and put the remaining bits from code into the bit buffer. 410 */ 411 #define PUT_AND_FLUSH(code, size) { \ 412 put_buffer = (put_buffer << (size + free_bits)) | (code >> -free_bits); \ 413 FLUSH() \ 414 free_bits += BIT_BUF_SIZE; \ 415 put_buffer = code; \ 416 } 417 418 /* Insert code into the bit buffer and output the bit buffer if needed. 419 * NOTE: We can't flush with free_bits == 0, since the left shift in 420 * PUT_AND_FLUSH() would have undefined behavior. 421 */ 422 #define PUT_BITS(code, size) { \ 423 free_bits -= size; \ 424 if (free_bits < 0) \ 425 PUT_AND_FLUSH(code, size) \ 426 else \ 427 put_buffer = (put_buffer << size) | code; \ 428 } 429 430 #define PUT_CODE(code, size) { \ 431 temp &= (((JLONG)1) << nbits) - 1; \ 432 temp |= code << nbits; \ 433 nbits += size; \ 434 PUT_BITS(temp, nbits) \ 435 } 436 437 438 /* Although it is exceedingly rare, it is possible for a Huffman-encoded 439 * coefficient block to be larger than the 128-byte unencoded block. For each 440 * of the 64 coefficients, PUT_BITS is invoked twice, and each invocation can 441 * theoretically store 16 bits (for a maximum of 2048 bits or 256 bytes per 442 * encoded block.) If, for instance, one artificially sets the AC 443 * coefficients to alternating values of 32767 and -32768 (using the JPEG 444 * scanning order-- 1, 8, 16, etc.), then this will produce an encoded block 445 * larger than 200 bytes. 446 */ 447 #define BUFSIZE (DCTSIZE2 * 8) 448 449 #define LOAD_BUFFER() { \ 450 if (state->free_in_buffer < BUFSIZE) { \ 451 localbuf = 1; \ 452 buffer = _buffer; \ 453 } else \ 454 buffer = state->next_output_byte; \ 455 } 456 457 #define STORE_BUFFER() { \ 458 if (localbuf) { \ 459 size_t bytes, bytestocopy; \ 460 bytes = buffer - _buffer; \ 461 buffer = _buffer; \ 462 while (bytes > 0) { \ 463 bytestocopy = MIN(bytes, state->free_in_buffer); \ 464 memcpy(state->next_output_byte, buffer, bytestocopy); \ 465 state->next_output_byte += bytestocopy; \ 466 buffer += bytestocopy; \ 467 state->free_in_buffer -= bytestocopy; \ 468 if (state->free_in_buffer == 0) \ 469 if (!dump_buffer(state)) return FALSE; \ 470 bytes -= bytestocopy; \ 471 } \ 472 } else { \ 473 state->free_in_buffer -= (buffer - state->next_output_byte); \ 474 state->next_output_byte = buffer; \ 475 } \ 476 } 477 478 479 LOCAL(boolean) 480 flush_bits(working_state *state) 481 { 482 JOCTET _buffer[BUFSIZE], *buffer, temp; 483 simd_bit_buf_type put_buffer; int put_bits; 484 int localbuf = 0; 485 486 #ifdef WITH_SIMD 487 if (state->simd) { 488 #if defined(__aarch64__) && !defined(NEON_INTRINSICS) 489 put_bits = state->cur.free_bits; 490 #else 491 put_bits = SIMD_BIT_BUF_SIZE - state->cur.free_bits; 492 #endif 493 put_buffer = state->cur.put_buffer.simd; 494 } else 495 #endif 496 { 497 put_bits = BIT_BUF_SIZE - state->cur.free_bits; 498 put_buffer = state->cur.put_buffer.c; 499 } 500 501 LOAD_BUFFER() 502 503 while (put_bits >= 8) { 504 put_bits -= 8; 505 temp = (JOCTET)(put_buffer >> put_bits); 506 EMIT_BYTE(temp) 507 } 508 if (put_bits) { 509 /* fill partial byte with ones */ 510 temp = (JOCTET)((put_buffer << (8 - put_bits)) | (0xFF >> put_bits)); 511 EMIT_BYTE(temp) 512 } 513 514 #ifdef WITH_SIMD 515 if (state->simd) { /* and reset bit buffer to empty */ 516 state->cur.put_buffer.simd = 0; 517 #if defined(__aarch64__) && !defined(NEON_INTRINSICS) 518 state->cur.free_bits = 0; 519 #else 520 state->cur.free_bits = SIMD_BIT_BUF_SIZE; 521 #endif 522 } else 523 #endif 524 { 525 state->cur.put_buffer.c = 0; 526 state->cur.free_bits = BIT_BUF_SIZE; 527 } 528 STORE_BUFFER() 529 530 return TRUE; 531 } 532 533 534 #ifdef WITH_SIMD 535 536 /* Encode a single block's worth of coefficients */ 537 538 LOCAL(boolean) 539 encode_one_block_simd(working_state *state, JCOEFPTR block, int last_dc_val, 540 c_derived_tbl *dctbl, c_derived_tbl *actbl) 541 { 542 JOCTET _buffer[BUFSIZE], *buffer; 543 int localbuf = 0; 544 545 #ifdef ZERO_BUFFERS 546 memset(_buffer, 0, sizeof(_buffer)); 547 #endif 548 549 LOAD_BUFFER() 550 551 buffer = jsimd_huff_encode_one_block(state, buffer, block, last_dc_val, 552 dctbl, actbl); 553 554 STORE_BUFFER() 555 556 return TRUE; 557 } 558 559 #endif 560 561 LOCAL(boolean) 562 encode_one_block(working_state *state, JCOEFPTR block, int last_dc_val, 563 c_derived_tbl *dctbl, c_derived_tbl *actbl) 564 { 565 int temp, nbits, free_bits; 566 bit_buf_type put_buffer; 567 JOCTET _buffer[BUFSIZE], *buffer; 568 int localbuf = 0; 569 int max_coef_bits = state->cinfo->data_precision + 2; 570 571 free_bits = state->cur.free_bits; 572 put_buffer = state->cur.put_buffer.c; 573 LOAD_BUFFER() 574 575 /* Encode the DC coefficient difference per section F.1.2.1 */ 576 577 temp = block[0] - last_dc_val; 578 579 /* This is a well-known technique for obtaining the absolute value without a 580 * branch. It is derived from an assembly language technique presented in 581 * "How to Optimize for the Pentium Processors", Copyright (c) 1996, 1997 by 582 * Agner Fog. This code assumes we are on a two's complement machine. 583 */ 584 nbits = temp >> (CHAR_BIT * sizeof(int) - 1); 585 temp += nbits; 586 nbits ^= temp; 587 588 /* Find the number of bits needed for the magnitude of the coefficient */ 589 nbits = JPEG_NBITS(nbits); 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(state->cinfo, JERR_BAD_DCT_COEF); 595 596 /* Emit the Huffman-coded symbol for the number of bits. 597 * Emit that number of bits of the value, if positive, 598 * or the complement of its magnitude, if negative. 599 */ 600 PUT_CODE(dctbl->ehufco[nbits], dctbl->ehufsi[nbits]) 601 602 /* Encode the AC coefficients per section F.1.2.2 */ 603 604 { 605 int r = 0; /* r = run length of zeros */ 606 607 /* Manually unroll the k loop to eliminate the counter variable. This 608 * improves performance greatly on systems with a limited number of 609 * registers (such as x86.) 610 */ 611 #define kloop(jpeg_natural_order_of_k) { \ 612 if ((temp = block[jpeg_natural_order_of_k]) == 0) { \ 613 r += 16; \ 614 } else { \ 615 /* Branch-less absolute value, bitwise complement, etc., same as above */ \ 616 nbits = temp >> (CHAR_BIT * sizeof(int) - 1); \ 617 temp += nbits; \ 618 nbits ^= temp; \ 619 nbits = JPEG_NBITS_NONZERO(nbits); \ 620 /* Check for out-of-range coefficient values */ \ 621 if (nbits > max_coef_bits) \ 622 ERREXIT(state->cinfo, JERR_BAD_DCT_COEF); \ 623 /* if run length > 15, must emit special run-length-16 codes (0xF0) */ \ 624 while (r >= 16 * 16) { \ 625 r -= 16 * 16; \ 626 PUT_BITS(actbl->ehufco[0xf0], actbl->ehufsi[0xf0]) \ 627 } \ 628 /* Emit Huffman symbol for run length / number of bits */ \ 629 r += nbits; \ 630 PUT_CODE(actbl->ehufco[r], actbl->ehufsi[r]) \ 631 r = 0; \ 632 } \ 633 } 634 635 /* One iteration for each value in jpeg_natural_order[] */ 636 kloop(1); kloop(8); kloop(16); kloop(9); kloop(2); kloop(3); 637 kloop(10); kloop(17); kloop(24); kloop(32); kloop(25); kloop(18); 638 kloop(11); kloop(4); kloop(5); kloop(12); kloop(19); kloop(26); 639 kloop(33); kloop(40); kloop(48); kloop(41); kloop(34); kloop(27); 640 kloop(20); kloop(13); kloop(6); kloop(7); kloop(14); kloop(21); 641 kloop(28); kloop(35); kloop(42); kloop(49); kloop(56); kloop(57); 642 kloop(50); kloop(43); kloop(36); kloop(29); kloop(22); kloop(15); 643 kloop(23); kloop(30); kloop(37); kloop(44); kloop(51); kloop(58); 644 kloop(59); kloop(52); kloop(45); kloop(38); kloop(31); kloop(39); 645 kloop(46); kloop(53); kloop(60); kloop(61); kloop(54); kloop(47); 646 kloop(55); kloop(62); kloop(63); 647 648 /* If the last coef(s) were zero, emit an end-of-block code */ 649 if (r > 0) { 650 PUT_BITS(actbl->ehufco[0], actbl->ehufsi[0]) 651 } 652 } 653 654 state->cur.put_buffer.c = put_buffer; 655 state->cur.free_bits = free_bits; 656 STORE_BUFFER() 657 658 return TRUE; 659 } 660 661 662 /* 663 * Emit a restart marker & resynchronize predictions. 664 */ 665 666 LOCAL(boolean) 667 emit_restart(working_state *state, int restart_num) 668 { 669 int ci; 670 671 if (!flush_bits(state)) 672 return FALSE; 673 674 emit_byte(state, 0xFF, return FALSE); 675 emit_byte(state, JPEG_RST0 + restart_num, return FALSE); 676 677 /* Re-initialize DC predictions to 0 */ 678 for (ci = 0; ci < state->cinfo->comps_in_scan; ci++) 679 state->cur.last_dc_val[ci] = 0; 680 681 /* The restart counter is not updated until we successfully write the MCU. */ 682 683 return TRUE; 684 } 685 686 687 /* 688 * Encode and output one MCU's worth of Huffman-compressed coefficients. 689 */ 690 691 METHODDEF(boolean) 692 encode_mcu_huff(j_compress_ptr cinfo, JBLOCKROW *MCU_data) 693 { 694 huff_entropy_ptr entropy = (huff_entropy_ptr)cinfo->entropy; 695 working_state state; 696 int blkn, ci; 697 jpeg_component_info *compptr; 698 699 /* Load up working state */ 700 state.next_output_byte = cinfo->dest->next_output_byte; 701 state.free_in_buffer = cinfo->dest->free_in_buffer; 702 state.cur = entropy->saved; 703 state.cinfo = cinfo; 704 #ifdef WITH_SIMD 705 state.simd = entropy->simd; 706 #endif 707 708 /* Emit restart marker if needed */ 709 if (cinfo->restart_interval) { 710 if (entropy->restarts_to_go == 0) 711 if (!emit_restart(&state, entropy->next_restart_num)) 712 return FALSE; 713 } 714 715 /* Encode the MCU data blocks */ 716 #ifdef WITH_SIMD 717 if (entropy->simd) { 718 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) { 719 ci = cinfo->MCU_membership[blkn]; 720 compptr = cinfo->cur_comp_info[ci]; 721 if (!encode_one_block_simd(&state, 722 MCU_data[blkn][0], state.cur.last_dc_val[ci], 723 entropy->dc_derived_tbls[compptr->dc_tbl_no], 724 entropy->ac_derived_tbls[compptr->ac_tbl_no])) 725 return FALSE; 726 /* Update last_dc_val */ 727 state.cur.last_dc_val[ci] = MCU_data[blkn][0][0]; 728 } 729 } else 730 #endif 731 { 732 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) { 733 ci = cinfo->MCU_membership[blkn]; 734 compptr = cinfo->cur_comp_info[ci]; 735 if (!encode_one_block(&state, 736 MCU_data[blkn][0], state.cur.last_dc_val[ci], 737 entropy->dc_derived_tbls[compptr->dc_tbl_no], 738 entropy->ac_derived_tbls[compptr->ac_tbl_no])) 739 return FALSE; 740 /* Update last_dc_val */ 741 state.cur.last_dc_val[ci] = MCU_data[blkn][0][0]; 742 } 743 } 744 745 /* Completed MCU, so update state */ 746 cinfo->dest->next_output_byte = state.next_output_byte; 747 cinfo->dest->free_in_buffer = state.free_in_buffer; 748 entropy->saved = state.cur; 749 750 /* Update restart-interval state too */ 751 if (cinfo->restart_interval) { 752 if (entropy->restarts_to_go == 0) { 753 entropy->restarts_to_go = cinfo->restart_interval; 754 entropy->next_restart_num++; 755 entropy->next_restart_num &= 7; 756 } 757 entropy->restarts_to_go--; 758 } 759 760 return TRUE; 761 } 762 763 764 /* 765 * Finish up at the end of a Huffman-compressed scan. 766 */ 767 768 METHODDEF(void) 769 finish_pass_huff(j_compress_ptr cinfo) 770 { 771 huff_entropy_ptr entropy = (huff_entropy_ptr)cinfo->entropy; 772 working_state state; 773 774 /* Load up working state ... flush_bits needs it */ 775 state.next_output_byte = cinfo->dest->next_output_byte; 776 state.free_in_buffer = cinfo->dest->free_in_buffer; 777 state.cur = entropy->saved; 778 state.cinfo = cinfo; 779 #ifdef WITH_SIMD 780 state.simd = entropy->simd; 781 #endif 782 783 /* Flush out the last data */ 784 if (!flush_bits(&state)) 785 ERREXIT(cinfo, JERR_CANT_SUSPEND); 786 787 /* Update state */ 788 cinfo->dest->next_output_byte = state.next_output_byte; 789 cinfo->dest->free_in_buffer = state.free_in_buffer; 790 entropy->saved = state.cur; 791 } 792 793 794 /* 795 * Huffman coding optimization. 796 * 797 * We first scan the supplied data and count the number of uses of each symbol 798 * that is to be Huffman-coded. (This process MUST agree with the code above.) 799 * Then we build a Huffman coding tree for the observed counts. 800 * Symbols which are not needed at all for the particular image are not 801 * assigned any code, which saves space in the DHT marker as well as in 802 * the compressed data. 803 */ 804 805 #ifdef ENTROPY_OPT_SUPPORTED 806 807 808 /* Process a single block's worth of coefficients */ 809 810 LOCAL(void) 811 htest_one_block(j_compress_ptr cinfo, JCOEFPTR block, int last_dc_val, 812 long dc_counts[], long ac_counts[]) 813 { 814 register int temp; 815 register int nbits; 816 register int k, r; 817 int max_coef_bits = cinfo->data_precision + 2; 818 819 /* Encode the DC coefficient difference per section F.1.2.1 */ 820 821 temp = block[0] - last_dc_val; 822 if (temp < 0) 823 temp = -temp; 824 825 /* Find the number of bits needed for the magnitude of the coefficient */ 826 nbits = 0; 827 while (temp) { 828 nbits++; 829 temp >>= 1; 830 } 831 /* Check for out-of-range coefficient values. 832 * Since we're encoding a difference, the range limit is twice as much. 833 */ 834 if (nbits > max_coef_bits + 1) 835 ERREXIT(cinfo, JERR_BAD_DCT_COEF); 836 837 /* Count the Huffman symbol for the number of bits */ 838 dc_counts[nbits]++; 839 840 /* Encode the AC coefficients per section F.1.2.2 */ 841 842 r = 0; /* r = run length of zeros */ 843 844 for (k = 1; k < DCTSIZE2; k++) { 845 if ((temp = block[jpeg_natural_order[k]]) == 0) { 846 r++; 847 } else { 848 /* if run length > 15, must emit special run-length-16 codes (0xF0) */ 849 while (r > 15) { 850 ac_counts[0xF0]++; 851 r -= 16; 852 } 853 854 /* Find the number of bits needed for the magnitude of the coefficient */ 855 if (temp < 0) 856 temp = -temp; 857 858 /* Find the number of bits needed for the magnitude of the coefficient */ 859 nbits = 1; /* there must be at least one 1 bit */ 860 while ((temp >>= 1)) 861 nbits++; 862 /* Check for out-of-range coefficient values */ 863 if (nbits > max_coef_bits) 864 ERREXIT(cinfo, JERR_BAD_DCT_COEF); 865 866 /* Count Huffman symbol for run length / number of bits */ 867 ac_counts[(r << 4) + nbits]++; 868 869 r = 0; 870 } 871 } 872 873 /* If the last coef(s) were zero, emit an end-of-block code */ 874 if (r > 0) 875 ac_counts[0]++; 876 } 877 878 879 /* 880 * Trial-encode one MCU's worth of Huffman-compressed coefficients. 881 * No data is actually output, so no suspension return is possible. 882 */ 883 884 METHODDEF(boolean) 885 encode_mcu_gather(j_compress_ptr cinfo, JBLOCKROW *MCU_data) 886 { 887 huff_entropy_ptr entropy = (huff_entropy_ptr)cinfo->entropy; 888 int blkn, ci; 889 jpeg_component_info *compptr; 890 891 /* Take care of restart intervals if needed */ 892 if (cinfo->restart_interval) { 893 if (entropy->restarts_to_go == 0) { 894 /* Re-initialize DC predictions to 0 */ 895 for (ci = 0; ci < cinfo->comps_in_scan; ci++) 896 entropy->saved.last_dc_val[ci] = 0; 897 /* Update restart state */ 898 entropy->restarts_to_go = cinfo->restart_interval; 899 } 900 entropy->restarts_to_go--; 901 } 902 903 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) { 904 ci = cinfo->MCU_membership[blkn]; 905 compptr = cinfo->cur_comp_info[ci]; 906 htest_one_block(cinfo, MCU_data[blkn][0], entropy->saved.last_dc_val[ci], 907 entropy->dc_count_ptrs[compptr->dc_tbl_no], 908 entropy->ac_count_ptrs[compptr->ac_tbl_no]); 909 entropy->saved.last_dc_val[ci] = MCU_data[blkn][0][0]; 910 } 911 912 return TRUE; 913 } 914 915 916 /* 917 * Generate the best Huffman code table for the given counts, fill htbl. 918 * Note this is also used by jcphuff.c and jclhuff.c. 919 * 920 * The JPEG standard requires that no symbol be assigned a codeword of all 921 * one bits (so that padding bits added at the end of a compressed segment 922 * can't look like a valid code). Because of the canonical ordering of 923 * codewords, this just means that there must be an unused slot in the 924 * longest codeword length category. Annex K (Clause K.2) of 925 * Rec. ITU-T T.81 (1992) | ISO/IEC 10918-1:1994 suggests reserving such a slot 926 * by pretending that symbol 256 is a valid symbol with count 1. In theory 927 * that's not optimal; giving it count zero but including it in the symbol set 928 * anyway should give a better Huffman code. But the theoretically better code 929 * actually seems to come out worse in practice, because it produces more 930 * all-ones bytes (which incur stuffed zero bytes in the final file). In any 931 * case the difference is tiny. 932 * 933 * The JPEG standard requires Huffman codes to be no more than 16 bits long. 934 * If some symbols have a very small but nonzero probability, the Huffman tree 935 * must be adjusted to meet the code length restriction. We currently use 936 * the adjustment method suggested in JPEG section K.2. This method is *not* 937 * optimal; it may not choose the best possible limited-length code. But 938 * typically only very-low-frequency symbols will be given less-than-optimal 939 * lengths, so the code is almost optimal. Experimental comparisons against 940 * an optimal limited-length-code algorithm indicate that the difference is 941 * microscopic --- usually less than a hundredth of a percent of total size. 942 * So the extra complexity of an optimal algorithm doesn't seem worthwhile. 943 */ 944 945 GLOBAL(void) 946 jpeg_gen_optimal_table(j_compress_ptr cinfo, JHUFF_TBL *htbl, long freq[]) 947 { 948 #define MAX_CLEN 32 /* assumed maximum initial code length */ 949 UINT8 bits[MAX_CLEN + 1]; /* bits[k] = # of symbols with code length k */ 950 int bit_pos[MAX_CLEN + 1]; /* # of symbols with smaller code length */ 951 int codesize[257]; /* codesize[k] = code length of symbol k */ 952 int nz_index[257]; /* index of nonzero symbol in the original freq 953 array */ 954 int others[257]; /* next symbol in current branch of tree */ 955 int c1, c2; 956 int p, i, j; 957 int num_nz_symbols; 958 long v, v2; 959 960 /* This algorithm is explained in section K.2 of the JPEG standard */ 961 962 memset(bits, 0, sizeof(bits)); 963 memset(codesize, 0, sizeof(codesize)); 964 for (i = 0; i < 257; i++) 965 others[i] = -1; /* init links to empty */ 966 967 freq[256] = 1; /* make sure 256 has a nonzero count */ 968 /* Including the pseudo-symbol 256 in the Huffman procedure guarantees 969 * that no real symbol is given code-value of all ones, because 256 970 * will be placed last in the largest codeword category. 971 */ 972 973 /* Group nonzero frequencies together so we can more easily find the 974 * smallest. 975 */ 976 num_nz_symbols = 0; 977 for (i = 0; i < 257; i++) { 978 if (freq[i]) { 979 nz_index[num_nz_symbols] = i; 980 freq[num_nz_symbols] = freq[i]; 981 num_nz_symbols++; 982 } 983 } 984 985 /* Huffman's basic algorithm to assign optimal code lengths to symbols */ 986 987 for (;;) { 988 /* Find the two smallest nonzero frequencies; set c1, c2 = their symbols */ 989 /* In case of ties, take the larger symbol number. Since we have grouped 990 * the nonzero symbols together, checking for zero symbols is not 991 * necessary. 992 */ 993 c1 = -1; 994 c2 = -1; 995 v = 1000000000L; 996 v2 = 1000000000L; 997 for (i = 0; i < num_nz_symbols; i++) { 998 if (freq[i] <= v2) { 999 if (freq[i] <= v) { 1000 c2 = c1; 1001 v2 = v; 1002 v = freq[i]; 1003 c1 = i; 1004 } else { 1005 v2 = freq[i]; 1006 c2 = i; 1007 } 1008 } 1009 } 1010 1011 /* Done if we've merged everything into one frequency */ 1012 if (c2 < 0) 1013 break; 1014 1015 /* Else merge the two counts/trees */ 1016 freq[c1] += freq[c2]; 1017 /* Set the frequency to a very high value instead of zero, so we don't have 1018 * to check for zero values. 1019 */ 1020 freq[c2] = 1000000001L; 1021 1022 /* Increment the codesize of everything in c1's tree branch */ 1023 codesize[c1]++; 1024 while (others[c1] >= 0) { 1025 c1 = others[c1]; 1026 codesize[c1]++; 1027 } 1028 1029 others[c1] = c2; /* chain c2 onto c1's tree branch */ 1030 1031 /* Increment the codesize of everything in c2's tree branch */ 1032 codesize[c2]++; 1033 while (others[c2] >= 0) { 1034 c2 = others[c2]; 1035 codesize[c2]++; 1036 } 1037 } 1038 1039 /* Now count the number of symbols of each code length */ 1040 for (i = 0; i < num_nz_symbols; i++) { 1041 /* The JPEG standard seems to think that this can't happen, */ 1042 /* but I'm paranoid... */ 1043 if (codesize[i] > MAX_CLEN) 1044 ERREXIT(cinfo, JERR_HUFF_CLEN_OVERFLOW); 1045 1046 bits[codesize[i]]++; 1047 } 1048 1049 /* Count the number of symbols with a length smaller than i bits, so we can 1050 * construct the symbol table more efficiently. Note that this includes the 1051 * pseudo-symbol 256, but since it is the last symbol, it will not affect the 1052 * table. 1053 */ 1054 p = 0; 1055 for (i = 1; i <= MAX_CLEN; i++) { 1056 bit_pos[i] = p; 1057 p += bits[i]; 1058 } 1059 1060 /* JPEG doesn't allow symbols with code lengths over 16 bits, so if the pure 1061 * Huffman procedure assigned any such lengths, we must adjust the coding. 1062 * Here is what Rec. ITU-T T.81 | ISO/IEC 10918-1 says about how this next 1063 * bit works: Since symbols are paired for the longest Huffman code, the 1064 * symbols are removed from this length category two at a time. The prefix 1065 * for the pair (which is one bit shorter) is allocated to one of the pair; 1066 * then, skipping the BITS entry for that prefix length, a code word from the 1067 * next shortest nonzero BITS entry is converted into a prefix for two code 1068 * words one bit longer. 1069 */ 1070 1071 for (i = MAX_CLEN; i > 16; i--) { 1072 while (bits[i] > 0) { 1073 j = i - 2; /* find length of new prefix to be used */ 1074 while (bits[j] == 0) 1075 j--; 1076 1077 bits[i] -= 2; /* remove two symbols */ 1078 bits[i - 1]++; /* one goes in this length */ 1079 bits[j + 1] += 2; /* two new symbols in this length */ 1080 bits[j]--; /* symbol of this length is now a prefix */ 1081 } 1082 } 1083 1084 /* Remove the count for the pseudo-symbol 256 from the largest codelength */ 1085 while (bits[i] == 0) /* find largest codelength still in use */ 1086 i--; 1087 bits[i]--; 1088 1089 /* Return final symbol counts (only for lengths 0..16) */ 1090 memcpy(htbl->bits, bits, sizeof(htbl->bits)); 1091 1092 /* Return a list of the symbols sorted by code length */ 1093 /* It's not real clear to me why we don't need to consider the codelength 1094 * changes made above, but Rec. ITU-T T.81 | ISO/IEC 10918-1 seems to think 1095 * this works. 1096 */ 1097 for (i = 0; i < num_nz_symbols - 1; i++) { 1098 htbl->huffval[bit_pos[codesize[i]]] = (UINT8)nz_index[i]; 1099 bit_pos[codesize[i]]++; 1100 } 1101 1102 /* Set sent_table FALSE so updated table will be written to JPEG file. */ 1103 htbl->sent_table = FALSE; 1104 } 1105 1106 1107 /* 1108 * Finish up a statistics-gathering pass and create the new Huffman tables. 1109 */ 1110 1111 METHODDEF(void) 1112 finish_pass_gather(j_compress_ptr cinfo) 1113 { 1114 huff_entropy_ptr entropy = (huff_entropy_ptr)cinfo->entropy; 1115 int ci, dctbl, actbl; 1116 jpeg_component_info *compptr; 1117 JHUFF_TBL **htblptr; 1118 boolean did_dc[NUM_HUFF_TBLS]; 1119 boolean did_ac[NUM_HUFF_TBLS]; 1120 1121 /* It's important not to apply jpeg_gen_optimal_table more than once 1122 * per table, because it clobbers the input frequency counts! 1123 */ 1124 memset(did_dc, 0, sizeof(did_dc)); 1125 memset(did_ac, 0, sizeof(did_ac)); 1126 1127 for (ci = 0; ci < cinfo->comps_in_scan; ci++) { 1128 compptr = cinfo->cur_comp_info[ci]; 1129 dctbl = compptr->dc_tbl_no; 1130 actbl = compptr->ac_tbl_no; 1131 if (!did_dc[dctbl]) { 1132 htblptr = &cinfo->dc_huff_tbl_ptrs[dctbl]; 1133 if (*htblptr == NULL) 1134 *htblptr = jpeg_alloc_huff_table((j_common_ptr)cinfo); 1135 jpeg_gen_optimal_table(cinfo, *htblptr, entropy->dc_count_ptrs[dctbl]); 1136 did_dc[dctbl] = TRUE; 1137 } 1138 if (!did_ac[actbl]) { 1139 htblptr = &cinfo->ac_huff_tbl_ptrs[actbl]; 1140 if (*htblptr == NULL) 1141 *htblptr = jpeg_alloc_huff_table((j_common_ptr)cinfo); 1142 jpeg_gen_optimal_table(cinfo, *htblptr, entropy->ac_count_ptrs[actbl]); 1143 did_ac[actbl] = TRUE; 1144 } 1145 } 1146 } 1147 1148 1149 #endif /* ENTROPY_OPT_SUPPORTED */ 1150 1151 1152 /* 1153 * Module initialization routine for Huffman entropy encoding. 1154 */ 1155 1156 GLOBAL(void) 1157 jinit_huff_encoder(j_compress_ptr cinfo) 1158 { 1159 huff_entropy_ptr entropy; 1160 int i; 1161 1162 entropy = (huff_entropy_ptr) 1163 (*cinfo->mem->alloc_small) ((j_common_ptr)cinfo, JPOOL_IMAGE, 1164 sizeof(huff_entropy_encoder)); 1165 cinfo->entropy = (struct jpeg_entropy_encoder *)entropy; 1166 entropy->pub.start_pass = start_pass_huff; 1167 1168 /* Mark tables unallocated */ 1169 for (i = 0; i < NUM_HUFF_TBLS; i++) { 1170 entropy->dc_derived_tbls[i] = entropy->ac_derived_tbls[i] = NULL; 1171 #ifdef ENTROPY_OPT_SUPPORTED 1172 entropy->dc_count_ptrs[i] = entropy->ac_count_ptrs[i] = NULL; 1173 #endif 1174 } 1175 }