diff options
Diffstat (limited to 'src/3rdparty/libjpeg/src/jchuff.c')
| -rw-r--r-- | src/3rdparty/libjpeg/src/jchuff.c | 585 |
1 files changed, 330 insertions, 255 deletions
diff --git a/src/3rdparty/libjpeg/src/jchuff.c b/src/3rdparty/libjpeg/src/jchuff.c index cb05055d99..488c9b5c3a 100644 --- a/src/3rdparty/libjpeg/src/jchuff.c +++ b/src/3rdparty/libjpeg/src/jchuff.c @@ -3,9 +3,14 @@ * * This file was part of the Independent JPEG Group's software: * Copyright (C) 1991-1997, Thomas G. Lane. + * Lossless JPEG Modifications: + * Copyright (C) 1999, Ken Murchison. * libjpeg-turbo Modifications: - * Copyright (C) 2009-2011, 2014-2016, 2018-2019, D. R. Commander. + * Copyright (C) 2009-2011, 2014-2016, 2018-2024, D. R. Commander. * Copyright (C) 2015, Matthieu Darbois. + * Copyright (C) 2018, Matthias Räncker. + * Copyright (C) 2020, Arm Limited. + * Copyright (C) 2022, Felix Hanau. * For conditions of distribution and use, see the accompanying README.ijg * file. * @@ -24,39 +29,13 @@ #define JPEG_INTERNALS #include "jinclude.h" #include "jpeglib.h" +#ifdef WITH_SIMD #include "jsimd.h" -#include "jconfigint.h" -#include <limits.h> - -/* - * NOTE: If USE_CLZ_INTRINSIC is defined, then clz/bsr instructions will be - * used for bit counting rather than the lookup table. This will reduce the - * memory footprint by 64k, which is important for some mobile applications - * that create many isolated instances of libjpeg-turbo (web browsers, for - * instance.) This may improve performance on some mobile platforms as well. - * This feature is enabled by default only on ARM processors, because some x86 - * chips have a slow implementation of bsr, and the use of clz/bsr cannot be - * shown to have a significant performance impact even on the x86 chips that - * have a fast implementation of it. When building for ARMv6, you can - * explicitly disable the use of clz/bsr by adding -mthumb to the compiler - * flags (this defines __thumb__). - */ - -/* NOTE: Both GCC and Clang define __GNUC__ */ -#if defined(__GNUC__) && (defined(__arm__) || defined(__aarch64__)) -#if !defined(__thumb__) || defined(__thumb2__) -#define USE_CLZ_INTRINSIC -#endif -#endif - -#ifdef USE_CLZ_INTRINSIC -#define JPEG_NBITS_NONZERO(x) (32 - __builtin_clz(x)) -#define JPEG_NBITS(x) (x ? JPEG_NBITS_NONZERO(x) : 0) #else -#include "jpeg_nbits_table.h" -#define JPEG_NBITS(x) (jpeg_nbits_table[x]) -#define JPEG_NBITS_NONZERO(x) JPEG_NBITS(x) +#include "jchuff.h" /* Declarations shared with jc*huff.c */ #endif +#include <limits.h> +#include "jpeg_nbits.h" /* Expanded entropy encoder object for Huffman encoding. @@ -65,31 +44,44 @@ * but must not be updated permanently until we complete the MCU. */ -typedef struct { - size_t put_buffer; /* current bit-accumulation buffer */ - int put_bits; /* # of bits now in it */ - int last_dc_val[MAX_COMPS_IN_SCAN]; /* last DC coef for each component */ -} savable_state; +#if defined(__x86_64__) && defined(__ILP32__) +typedef unsigned long long bit_buf_type; +#else +typedef size_t bit_buf_type; +#endif -/* This macro is to work around compilers with missing or broken - * structure assignment. You'll need to fix this code if you have - * such a compiler and you change MAX_COMPS_IN_SCAN. +/* NOTE: The more optimal Huffman encoding algorithm is only used by the + * intrinsics implementation of the Arm Neon SIMD extensions, which is why we + * retain the old Huffman encoder behavior when using the GAS implementation. */ - -#ifndef NO_STRUCT_ASSIGN -#define ASSIGN_STATE(dest, src) ((dest) = (src)) +#if defined(WITH_SIMD) && !(defined(__arm__) || defined(__aarch64__) || \ + defined(_M_ARM) || defined(_M_ARM64)) +typedef unsigned long long simd_bit_buf_type; #else -#if MAX_COMPS_IN_SCAN == 4 -#define ASSIGN_STATE(dest, src) \ - ((dest).put_buffer = (src).put_buffer, \ - (dest).put_bits = (src).put_bits, \ - (dest).last_dc_val[0] = (src).last_dc_val[0], \ - (dest).last_dc_val[1] = (src).last_dc_val[1], \ - (dest).last_dc_val[2] = (src).last_dc_val[2], \ - (dest).last_dc_val[3] = (src).last_dc_val[3]) +typedef bit_buf_type simd_bit_buf_type; #endif + +#if (defined(SIZEOF_SIZE_T) && SIZEOF_SIZE_T == 8) || defined(_WIN64) || \ + (defined(__x86_64__) && defined(__ILP32__)) +#define BIT_BUF_SIZE 64 +#elif (defined(SIZEOF_SIZE_T) && SIZEOF_SIZE_T == 4) || defined(_WIN32) +#define BIT_BUF_SIZE 32 +#else +#error Cannot determine word size #endif +#define SIMD_BIT_BUF_SIZE (sizeof(simd_bit_buf_type) * 8) +typedef struct { + union { + bit_buf_type c; +#ifdef WITH_SIMD + simd_bit_buf_type simd; +#endif + } put_buffer; /* current bit accumulation buffer */ + int free_bits; /* # of bits available in it */ + /* (Neon GAS: # of bits now in it) */ + int last_dc_val[MAX_COMPS_IN_SCAN]; /* last DC coef for each component */ +} savable_state; typedef struct { struct jpeg_entropy_encoder pub; /* public fields */ @@ -109,7 +101,9 @@ typedef struct { long *ac_count_ptrs[NUM_HUFF_TBLS]; #endif +#ifdef WITH_SIMD int simd; +#endif } huff_entropy_encoder; typedef huff_entropy_encoder *huff_entropy_ptr; @@ -123,6 +117,9 @@ typedef struct { size_t free_in_buffer; /* # of byte spaces remaining in buffer */ savable_state cur; /* Current bit buffer & DC state */ j_compress_ptr cinfo; /* dump_buffer needs access to this */ +#ifdef WITH_SIMD + int simd; +#endif } working_state; @@ -161,7 +158,9 @@ start_pass_huff(j_compress_ptr cinfo, boolean gather_statistics) entropy->pub.finish_pass = finish_pass_huff; } +#ifdef WITH_SIMD entropy->simd = jsimd_can_huff_encode_one_block(); +#endif for (ci = 0; ci < cinfo->comps_in_scan; ci++) { compptr = cinfo->cur_comp_info[ci]; @@ -181,12 +180,12 @@ start_pass_huff(j_compress_ptr cinfo, boolean gather_statistics) entropy->dc_count_ptrs[dctbl] = (long *) (*cinfo->mem->alloc_small) ((j_common_ptr)cinfo, JPOOL_IMAGE, 257 * sizeof(long)); - MEMZERO(entropy->dc_count_ptrs[dctbl], 257 * sizeof(long)); + memset(entropy->dc_count_ptrs[dctbl], 0, 257 * sizeof(long)); if (entropy->ac_count_ptrs[actbl] == NULL) entropy->ac_count_ptrs[actbl] = (long *) (*cinfo->mem->alloc_small) ((j_common_ptr)cinfo, JPOOL_IMAGE, 257 * sizeof(long)); - MEMZERO(entropy->ac_count_ptrs[actbl], 257 * sizeof(long)); + memset(entropy->ac_count_ptrs[actbl], 0, 257 * sizeof(long)); #endif } else { /* Compute derived values for Huffman tables */ @@ -201,8 +200,20 @@ start_pass_huff(j_compress_ptr cinfo, boolean gather_statistics) } /* Initialize bit buffer to empty */ - entropy->saved.put_buffer = 0; - entropy->saved.put_bits = 0; +#ifdef WITH_SIMD + if (entropy->simd) { + entropy->saved.put_buffer.simd = 0; +#if defined(__aarch64__) && !defined(NEON_INTRINSICS) + entropy->saved.free_bits = 0; +#else + entropy->saved.free_bits = SIMD_BIT_BUF_SIZE; +#endif + } else +#endif + { + entropy->saved.put_buffer.c = 0; + entropy->saved.free_bits = BIT_BUF_SIZE; + } /* Initialize restart stuff */ entropy->restarts_to_go = cinfo->restart_interval; @@ -214,7 +225,7 @@ start_pass_huff(j_compress_ptr cinfo, boolean gather_statistics) * Compute the derived values for a Huffman table. * This routine also performs some validation checks on the table. * - * Note this is also used by jcphuff.c. + * Note this is also used by jcphuff.c and jclhuff.c. */ GLOBAL(void) @@ -287,14 +298,15 @@ jpeg_make_c_derived_tbl(j_compress_ptr cinfo, boolean isDC, int tblno, * this lets us detect duplicate VAL entries here, and later * allows emit_bits to detect any attempt to emit such symbols. */ - MEMZERO(dtbl->ehufsi, sizeof(dtbl->ehufsi)); + memset(dtbl->ehufco, 0, sizeof(dtbl->ehufco)); + memset(dtbl->ehufsi, 0, sizeof(dtbl->ehufsi)); - /* This is also a convenient place to check for out-of-range - * and duplicated VAL entries. We allow 0..255 for AC symbols - * but only 0..15 for DC. (We could constrain them further - * based on data depth and mode, but this seems enough.) + /* This is also a convenient place to check for out-of-range and duplicated + * VAL entries. We allow 0..255 for AC symbols but only 0..15 for DC in + * lossy mode and 0..16 for DC in lossless mode. (We could constrain them + * further based on data depth and mode, but this seems enough.) */ - maxsymbol = isDC ? 15 : 255; + maxsymbol = isDC ? (cinfo->master->lossless ? 16 : 15) : 255; for (p = 0; p < lastp; p++) { i = htbl->huffval[p]; @@ -334,94 +346,94 @@ dump_buffer(working_state *state) /* Outputting bits to the file */ -/* These macros perform the same task as the emit_bits() function in the - * original libjpeg code. In addition to reducing overhead by explicitly - * inlining the code, additional performance is achieved by taking into - * account the size of the bit buffer and waiting until it is almost full - * before emptying it. This mostly benefits 64-bit platforms, since 6 - * bytes can be stored in a 64-bit bit buffer before it has to be emptied. +/* Output byte b and, speculatively, an additional 0 byte. 0xFF must be + * encoded as 0xFF 0x00, so the output buffer pointer is advanced by 2 if the + * byte is 0xFF. Otherwise, the output buffer pointer is advanced by 1, and + * the speculative 0 byte will be overwritten by the next byte. */ - -#define EMIT_BYTE() { \ - JOCTET c; \ - put_bits -= 8; \ - c = (JOCTET)GETJOCTET(put_buffer >> put_bits); \ - *buffer++ = c; \ - if (c == 0xFF) /* need to stuff a zero byte? */ \ - *buffer++ = 0; \ +#define EMIT_BYTE(b) { \ + buffer[0] = (JOCTET)(b); \ + buffer[1] = 0; \ + buffer -= -2 + ((JOCTET)(b) < 0xFF); \ } -#define PUT_BITS(code, size) { \ - put_bits += size; \ - put_buffer = (put_buffer << size) | code; \ -} - -#if SIZEOF_SIZE_T != 8 && !defined(_WIN64) - -#define CHECKBUF15() { \ - if (put_bits > 15) { \ - EMIT_BYTE() \ - EMIT_BYTE() \ +/* Output the entire bit buffer. If there are no 0xFF bytes in it, then write + * directly to the output buffer. Otherwise, use the EMIT_BYTE() macro to + * encode 0xFF as 0xFF 0x00. + */ +#if BIT_BUF_SIZE == 64 + +#define FLUSH() { \ + if (put_buffer & 0x8080808080808080 & ~(put_buffer + 0x0101010101010101)) { \ + EMIT_BYTE(put_buffer >> 56) \ + EMIT_BYTE(put_buffer >> 48) \ + EMIT_BYTE(put_buffer >> 40) \ + EMIT_BYTE(put_buffer >> 32) \ + EMIT_BYTE(put_buffer >> 24) \ + EMIT_BYTE(put_buffer >> 16) \ + EMIT_BYTE(put_buffer >> 8) \ + EMIT_BYTE(put_buffer ) \ + } else { \ + buffer[0] = (JOCTET)(put_buffer >> 56); \ + buffer[1] = (JOCTET)(put_buffer >> 48); \ + buffer[2] = (JOCTET)(put_buffer >> 40); \ + buffer[3] = (JOCTET)(put_buffer >> 32); \ + buffer[4] = (JOCTET)(put_buffer >> 24); \ + buffer[5] = (JOCTET)(put_buffer >> 16); \ + buffer[6] = (JOCTET)(put_buffer >> 8); \ + buffer[7] = (JOCTET)(put_buffer); \ + buffer += 8; \ } \ } -#endif - -#define CHECKBUF31() { \ - if (put_bits > 31) { \ - EMIT_BYTE() \ - EMIT_BYTE() \ - EMIT_BYTE() \ - EMIT_BYTE() \ - } \ -} +#else -#define CHECKBUF47() { \ - if (put_bits > 47) { \ - EMIT_BYTE() \ - EMIT_BYTE() \ - EMIT_BYTE() \ - EMIT_BYTE() \ - EMIT_BYTE() \ - EMIT_BYTE() \ +#define FLUSH() { \ + if (put_buffer & 0x80808080 & ~(put_buffer + 0x01010101)) { \ + EMIT_BYTE(put_buffer >> 24) \ + EMIT_BYTE(put_buffer >> 16) \ + EMIT_BYTE(put_buffer >> 8) \ + EMIT_BYTE(put_buffer ) \ + } else { \ + buffer[0] = (JOCTET)(put_buffer >> 24); \ + buffer[1] = (JOCTET)(put_buffer >> 16); \ + buffer[2] = (JOCTET)(put_buffer >> 8); \ + buffer[3] = (JOCTET)(put_buffer); \ + buffer += 4; \ } \ } -#if !defined(_WIN32) && !defined(SIZEOF_SIZE_T) -#error Cannot determine word size #endif -#if SIZEOF_SIZE_T == 8 || defined(_WIN64) - -#define EMIT_BITS(code, size) { \ - CHECKBUF47() \ - PUT_BITS(code, size) \ -} - -#define EMIT_CODE(code, size) { \ - temp2 &= (((JLONG)1) << nbits) - 1; \ - CHECKBUF31() \ - PUT_BITS(code, size) \ - PUT_BITS(temp2, nbits) \ +/* Fill the bit buffer to capacity with the leading bits from code, then output + * the bit buffer and put the remaining bits from code into the bit buffer. + */ +#define PUT_AND_FLUSH(code, size) { \ + put_buffer = (put_buffer << (size + free_bits)) | (code >> -free_bits); \ + FLUSH() \ + free_bits += BIT_BUF_SIZE; \ + put_buffer = code; \ } -#else - -#define EMIT_BITS(code, size) { \ - PUT_BITS(code, size) \ - CHECKBUF15() \ +/* Insert code into the bit buffer and output the bit buffer if needed. + * NOTE: We can't flush with free_bits == 0, since the left shift in + * PUT_AND_FLUSH() would have undefined behavior. + */ +#define PUT_BITS(code, size) { \ + free_bits -= size; \ + if (free_bits < 0) \ + PUT_AND_FLUSH(code, size) \ + else \ + put_buffer = (put_buffer << size) | code; \ } -#define EMIT_CODE(code, size) { \ - temp2 &= (((JLONG)1) << nbits) - 1; \ - PUT_BITS(code, size) \ - CHECKBUF15() \ - PUT_BITS(temp2, nbits) \ - CHECKBUF15() \ +#define PUT_CODE(code, size) { \ + temp &= (((JLONG)1) << nbits) - 1; \ + temp |= code << nbits; \ + nbits += size; \ + PUT_BITS(temp, nbits) \ } -#endif - /* Although it is exceedingly rare, it is possible for a Huffman-encoded * coefficient block to be larger than the 128-byte unencoded block. For each @@ -444,11 +456,12 @@ dump_buffer(working_state *state) #define STORE_BUFFER() { \ if (localbuf) { \ + size_t bytes, bytestocopy; \ bytes = buffer - _buffer; \ buffer = _buffer; \ while (bytes > 0) { \ bytestocopy = MIN(bytes, state->free_in_buffer); \ - MEMCOPY(state->next_output_byte, buffer, bytestocopy); \ + memcpy(state->next_output_byte, buffer, bytestocopy); \ state->next_output_byte += bytestocopy; \ buffer += bytestocopy; \ state->free_in_buffer -= bytestocopy; \ @@ -466,26 +479,60 @@ dump_buffer(working_state *state) LOCAL(boolean) flush_bits(working_state *state) { - JOCTET _buffer[BUFSIZE], *buffer; - size_t put_buffer; int put_bits; - size_t bytes, bytestocopy; int localbuf = 0; + JOCTET _buffer[BUFSIZE], *buffer, temp; + simd_bit_buf_type put_buffer; int put_bits; + int localbuf = 0; + +#ifdef WITH_SIMD + if (state->simd) { +#if defined(__aarch64__) && !defined(NEON_INTRINSICS) + put_bits = state->cur.free_bits; +#else + put_bits = SIMD_BIT_BUF_SIZE - state->cur.free_bits; +#endif + put_buffer = state->cur.put_buffer.simd; + } else +#endif + { + put_bits = BIT_BUF_SIZE - state->cur.free_bits; + put_buffer = state->cur.put_buffer.c; + } - put_buffer = state->cur.put_buffer; - put_bits = state->cur.put_bits; LOAD_BUFFER() - /* fill any partial byte with ones */ - PUT_BITS(0x7F, 7) - while (put_bits >= 8) EMIT_BYTE() + while (put_bits >= 8) { + put_bits -= 8; + temp = (JOCTET)(put_buffer >> put_bits); + EMIT_BYTE(temp) + } + if (put_bits) { + /* fill partial byte with ones */ + temp = (JOCTET)((put_buffer << (8 - put_bits)) | (0xFF >> put_bits)); + EMIT_BYTE(temp) + } - state->cur.put_buffer = 0; /* and reset bit-buffer to empty */ - state->cur.put_bits = 0; +#ifdef WITH_SIMD + if (state->simd) { /* and reset bit buffer to empty */ + state->cur.put_buffer.simd = 0; +#if defined(__aarch64__) && !defined(NEON_INTRINSICS) + state->cur.free_bits = 0; +#else + state->cur.free_bits = SIMD_BIT_BUF_SIZE; +#endif + } else +#endif + { + state->cur.put_buffer.c = 0; + state->cur.free_bits = BIT_BUF_SIZE; + } STORE_BUFFER() return TRUE; } +#ifdef WITH_SIMD + /* Encode a single block's worth of coefficients */ LOCAL(boolean) @@ -493,7 +540,7 @@ encode_one_block_simd(working_state *state, JCOEFPTR block, int last_dc_val, c_derived_tbl *dctbl, c_derived_tbl *actbl) { JOCTET _buffer[BUFSIZE], *buffer; - size_t bytes, bytestocopy; int localbuf = 0; + int localbuf = 0; LOAD_BUFFER() @@ -505,57 +552,53 @@ encode_one_block_simd(working_state *state, JCOEFPTR block, int last_dc_val, return TRUE; } +#endif + LOCAL(boolean) encode_one_block(working_state *state, JCOEFPTR block, int last_dc_val, c_derived_tbl *dctbl, c_derived_tbl *actbl) { - int temp, temp2, temp3; - int nbits; - int r, code, size; + int temp, nbits, free_bits; + bit_buf_type put_buffer; JOCTET _buffer[BUFSIZE], *buffer; - size_t put_buffer; int put_bits; - int code_0xf0 = actbl->ehufco[0xf0], size_0xf0 = actbl->ehufsi[0xf0]; - size_t bytes, bytestocopy; int localbuf = 0; + int localbuf = 0; + int max_coef_bits = state->cinfo->data_precision + 2; - put_buffer = state->cur.put_buffer; - put_bits = state->cur.put_bits; + free_bits = state->cur.free_bits; + put_buffer = state->cur.put_buffer.c; LOAD_BUFFER() /* Encode the DC coefficient difference per section F.1.2.1 */ - temp = temp2 = block[0] - last_dc_val; + temp = block[0] - last_dc_val; /* This is a well-known technique for obtaining the absolute value without a * branch. It is derived from an assembly language technique presented in * "How to Optimize for the Pentium Processors", Copyright (c) 1996, 1997 by - * Agner Fog. + * Agner Fog. This code assumes we are on a two's complement machine. */ - temp3 = temp >> (CHAR_BIT * sizeof(int) - 1); - temp ^= temp3; - temp -= temp3; - - /* For a negative input, want temp2 = bitwise complement of abs(input) */ - /* This code assumes we are on a two's complement machine */ - temp2 += temp3; + nbits = temp >> (CHAR_BIT * sizeof(int) - 1); + temp += nbits; + nbits ^= temp; /* Find the number of bits needed for the magnitude of the coefficient */ - nbits = JPEG_NBITS(temp); - - /* Emit the Huffman-coded symbol for the number of bits */ - code = dctbl->ehufco[nbits]; - size = dctbl->ehufsi[nbits]; - EMIT_BITS(code, size) - - /* Mask off any extra bits in code */ - temp2 &= (((JLONG)1) << nbits) - 1; + nbits = JPEG_NBITS(nbits); + /* Check for out-of-range coefficient values. + * Since we're encoding a difference, the range limit is twice as much. + */ + if (nbits > max_coef_bits + 1) + ERREXIT(state->cinfo, JERR_BAD_DCT_COEF); - /* Emit that number of bits of the value, if positive, */ - /* or the complement of its magnitude, if negative. */ - EMIT_BITS(temp2, nbits) + /* Emit the Huffman-coded symbol for the number of bits. + * Emit that number of bits of the value, if positive, + * or the complement of its magnitude, if negative. + */ + PUT_CODE(dctbl->ehufco[nbits], dctbl->ehufsi[nbits]) /* Encode the AC coefficients per section F.1.2.2 */ - r = 0; /* r = run length of zeros */ + { + int r = 0; /* r = run length of zeros */ /* Manually unroll the k loop to eliminate the counter variable. This * improves performance greatly on systems with a limited number of @@ -563,51 +606,49 @@ encode_one_block(working_state *state, JCOEFPTR block, int last_dc_val, */ #define kloop(jpeg_natural_order_of_k) { \ if ((temp = block[jpeg_natural_order_of_k]) == 0) { \ - r++; \ + r += 16; \ } else { \ - temp2 = temp; \ /* Branch-less absolute value, bitwise complement, etc., same as above */ \ - temp3 = temp >> (CHAR_BIT * sizeof(int) - 1); \ - temp ^= temp3; \ - temp -= temp3; \ - temp2 += temp3; \ - nbits = JPEG_NBITS_NONZERO(temp); \ + nbits = temp >> (CHAR_BIT * sizeof(int) - 1); \ + temp += nbits; \ + nbits ^= temp; \ + nbits = JPEG_NBITS_NONZERO(nbits); \ + /* Check for out-of-range coefficient values */ \ + if (nbits > max_coef_bits) \ + ERREXIT(state->cinfo, JERR_BAD_DCT_COEF); \ /* if run length > 15, must emit special run-length-16 codes (0xF0) */ \ - while (r > 15) { \ - EMIT_BITS(code_0xf0, size_0xf0) \ - r -= 16; \ + while (r >= 16 * 16) { \ + r -= 16 * 16; \ + PUT_BITS(actbl->ehufco[0xf0], actbl->ehufsi[0xf0]) \ } \ /* Emit Huffman symbol for run length / number of bits */ \ - temp3 = (r << 4) + nbits; \ - code = actbl->ehufco[temp3]; \ - size = actbl->ehufsi[temp3]; \ - EMIT_CODE(code, size) \ + r += nbits; \ + PUT_CODE(actbl->ehufco[r], actbl->ehufsi[r]) \ r = 0; \ } \ } - /* One iteration for each value in jpeg_natural_order[] */ - kloop(1); kloop(8); kloop(16); kloop(9); kloop(2); kloop(3); - kloop(10); kloop(17); kloop(24); kloop(32); kloop(25); kloop(18); - kloop(11); kloop(4); kloop(5); kloop(12); kloop(19); kloop(26); - kloop(33); kloop(40); kloop(48); kloop(41); kloop(34); kloop(27); - kloop(20); kloop(13); kloop(6); kloop(7); kloop(14); kloop(21); - kloop(28); kloop(35); kloop(42); kloop(49); kloop(56); kloop(57); - kloop(50); kloop(43); kloop(36); kloop(29); kloop(22); kloop(15); - kloop(23); kloop(30); kloop(37); kloop(44); kloop(51); kloop(58); - kloop(59); kloop(52); kloop(45); kloop(38); kloop(31); kloop(39); - kloop(46); kloop(53); kloop(60); kloop(61); kloop(54); kloop(47); - kloop(55); kloop(62); kloop(63); - - /* If the last coef(s) were zero, emit an end-of-block code */ - if (r > 0) { - code = actbl->ehufco[0]; - size = actbl->ehufsi[0]; - EMIT_BITS(code, size) + /* One iteration for each value in jpeg_natural_order[] */ + kloop(1); kloop(8); kloop(16); kloop(9); kloop(2); kloop(3); + kloop(10); kloop(17); kloop(24); kloop(32); kloop(25); kloop(18); + kloop(11); kloop(4); kloop(5); kloop(12); kloop(19); kloop(26); + kloop(33); kloop(40); kloop(48); kloop(41); kloop(34); kloop(27); + kloop(20); kloop(13); kloop(6); kloop(7); kloop(14); kloop(21); + kloop(28); kloop(35); kloop(42); kloop(49); kloop(56); kloop(57); + kloop(50); kloop(43); kloop(36); kloop(29); kloop(22); kloop(15); + kloop(23); kloop(30); kloop(37); kloop(44); kloop(51); kloop(58); + kloop(59); kloop(52); kloop(45); kloop(38); kloop(31); kloop(39); + kloop(46); kloop(53); kloop(60); kloop(61); kloop(54); kloop(47); + kloop(55); kloop(62); kloop(63); + + /* If the last coef(s) were zero, emit an end-of-block code */ + if (r > 0) { + PUT_BITS(actbl->ehufco[0], actbl->ehufsi[0]) + } } - state->cur.put_buffer = put_buffer; - state->cur.put_bits = put_bits; + state->cur.put_buffer.c = put_buffer; + state->cur.free_bits = free_bits; STORE_BUFFER() return TRUE; @@ -654,8 +695,11 @@ encode_mcu_huff(j_compress_ptr cinfo, JBLOCKROW *MCU_data) /* Load up working state */ state.next_output_byte = cinfo->dest->next_output_byte; state.free_in_buffer = cinfo->dest->free_in_buffer; - ASSIGN_STATE(state.cur, entropy->saved); + state.cur = entropy->saved; state.cinfo = cinfo; +#ifdef WITH_SIMD + state.simd = entropy->simd; +#endif /* Emit restart marker if needed */ if (cinfo->restart_interval) { @@ -665,6 +709,7 @@ encode_mcu_huff(j_compress_ptr cinfo, JBLOCKROW *MCU_data) } /* Encode the MCU data blocks */ +#ifdef WITH_SIMD if (entropy->simd) { for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) { ci = cinfo->MCU_membership[blkn]; @@ -677,7 +722,9 @@ encode_mcu_huff(j_compress_ptr cinfo, JBLOCKROW *MCU_data) /* Update last_dc_val */ state.cur.last_dc_val[ci] = MCU_data[blkn][0][0]; } - } else { + } else +#endif + { for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) { ci = cinfo->MCU_membership[blkn]; compptr = cinfo->cur_comp_info[ci]; @@ -694,7 +741,7 @@ encode_mcu_huff(j_compress_ptr cinfo, JBLOCKROW *MCU_data) /* Completed MCU, so update state */ cinfo->dest->next_output_byte = state.next_output_byte; cinfo->dest->free_in_buffer = state.free_in_buffer; - ASSIGN_STATE(entropy->saved, state.cur); + entropy->saved = state.cur; /* Update restart-interval state too */ if (cinfo->restart_interval) { @@ -723,8 +770,11 @@ finish_pass_huff(j_compress_ptr cinfo) /* Load up working state ... flush_bits needs it */ state.next_output_byte = cinfo->dest->next_output_byte; state.free_in_buffer = cinfo->dest->free_in_buffer; - ASSIGN_STATE(state.cur, entropy->saved); + state.cur = entropy->saved; state.cinfo = cinfo; +#ifdef WITH_SIMD + state.simd = entropy->simd; +#endif /* Flush out the last data */ if (!flush_bits(&state)) @@ -733,7 +783,7 @@ finish_pass_huff(j_compress_ptr cinfo) /* Update state */ cinfo->dest->next_output_byte = state.next_output_byte; cinfo->dest->free_in_buffer = state.free_in_buffer; - ASSIGN_STATE(entropy->saved, state.cur); + entropy->saved = state.cur; } @@ -760,6 +810,7 @@ htest_one_block(j_compress_ptr cinfo, JCOEFPTR block, int last_dc_val, register int temp; register int nbits; register int k, r; + int max_coef_bits = cinfo->data_precision + 2; /* Encode the DC coefficient difference per section F.1.2.1 */ @@ -776,7 +827,7 @@ htest_one_block(j_compress_ptr cinfo, JCOEFPTR block, int last_dc_val, /* Check for out-of-range coefficient values. * Since we're encoding a difference, the range limit is twice as much. */ - if (nbits > MAX_COEF_BITS + 1) + if (nbits > max_coef_bits + 1) ERREXIT(cinfo, JERR_BAD_DCT_COEF); /* Count the Huffman symbol for the number of bits */ @@ -805,7 +856,7 @@ htest_one_block(j_compress_ptr cinfo, JCOEFPTR block, int last_dc_val, while ((temp >>= 1)) nbits++; /* Check for out-of-range coefficient values */ - if (nbits > MAX_COEF_BITS) + if (nbits > max_coef_bits) ERREXIT(cinfo, JERR_BAD_DCT_COEF); /* Count Huffman symbol for run length / number of bits */ @@ -860,7 +911,7 @@ encode_mcu_gather(j_compress_ptr cinfo, JBLOCKROW *MCU_data) /* * Generate the best Huffman code table for the given counts, fill htbl. - * Note this is also used by jcphuff.c. + * Note this is also used by jcphuff.c and jclhuff.c. * * The JPEG standard requires that no symbol be assigned a codeword of all * one bits (so that padding bits added at the end of a compressed segment @@ -892,16 +943,20 @@ jpeg_gen_optimal_table(j_compress_ptr cinfo, JHUFF_TBL *htbl, long freq[]) { #define MAX_CLEN 32 /* assumed maximum initial code length */ UINT8 bits[MAX_CLEN + 1]; /* bits[k] = # of symbols with code length k */ + int bit_pos[MAX_CLEN + 1]; /* # of symbols with smaller code length */ int codesize[257]; /* codesize[k] = code length of symbol k */ + int nz_index[257]; /* index of nonzero symbol in the original freq + array */ int others[257]; /* next symbol in current branch of tree */ int c1, c2; int p, i, j; - long v; + int num_nz_symbols; + long v, v2; /* This algorithm is explained in section K.2 of the JPEG standard */ - MEMZERO(bits, sizeof(bits)); - MEMZERO(codesize, sizeof(codesize)); + memset(bits, 0, sizeof(bits)); + memset(codesize, 0, sizeof(codesize)); for (i = 0; i < 257; i++) others[i] = -1; /* init links to empty */ @@ -911,28 +966,41 @@ jpeg_gen_optimal_table(j_compress_ptr cinfo, JHUFF_TBL *htbl, long freq[]) * will be placed last in the largest codeword category. */ + /* Group nonzero frequencies together so we can more easily find the + * smallest. + */ + num_nz_symbols = 0; + for (i = 0; i < 257; i++) { + if (freq[i]) { + nz_index[num_nz_symbols] = i; + freq[num_nz_symbols] = freq[i]; + num_nz_symbols++; + } + } + /* Huffman's basic algorithm to assign optimal code lengths to symbols */ for (;;) { - /* Find the smallest nonzero frequency, set c1 = its symbol */ - /* In case of ties, take the larger symbol number */ + /* Find the two smallest nonzero frequencies; set c1, c2 = their symbols */ + /* In case of ties, take the larger symbol number. Since we have grouped + * the nonzero symbols together, checking for zero symbols is not + * necessary. + */ c1 = -1; - v = 1000000000L; - for (i = 0; i <= 256; i++) { - if (freq[i] && freq[i] <= v) { - v = freq[i]; - c1 = i; - } - } - - /* Find the next smallest nonzero frequency, set c2 = its symbol */ - /* In case of ties, take the larger symbol number */ c2 = -1; v = 1000000000L; - for (i = 0; i <= 256; i++) { - if (freq[i] && freq[i] <= v && i != c1) { - v = freq[i]; - c2 = i; + v2 = 1000000000L; + for (i = 0; i < num_nz_symbols; i++) { + if (freq[i] <= v2) { + if (freq[i] <= v) { + c2 = c1; + v2 = v; + v = freq[i]; + c1 = i; + } else { + v2 = freq[i]; + c2 = i; + } } } @@ -942,7 +1010,10 @@ jpeg_gen_optimal_table(j_compress_ptr cinfo, JHUFF_TBL *htbl, long freq[]) /* Else merge the two counts/trees */ freq[c1] += freq[c2]; - freq[c2] = 0; + /* Set the frequency to a very high value instead of zero, so we don't have + * to check for zero values. + */ + freq[c2] = 1000000001L; /* Increment the codesize of everything in c1's tree branch */ codesize[c1]++; @@ -962,15 +1033,24 @@ jpeg_gen_optimal_table(j_compress_ptr cinfo, JHUFF_TBL *htbl, long freq[]) } /* Now count the number of symbols of each code length */ - for (i = 0; i <= 256; i++) { - if (codesize[i]) { - /* The JPEG standard seems to think that this can't happen, */ - /* but I'm paranoid... */ - if (codesize[i] > MAX_CLEN) - ERREXIT(cinfo, JERR_HUFF_CLEN_OVERFLOW); - - bits[codesize[i]]++; - } + for (i = 0; i < num_nz_symbols; i++) { + /* The JPEG standard seems to think that this can't happen, */ + /* but I'm paranoid... */ + if (codesize[i] > MAX_CLEN) + ERREXIT(cinfo, JERR_HUFF_CLEN_OVERFLOW); + + bits[codesize[i]]++; + } + + /* Count the number of symbols with a length smaller than i bits, so we can + * construct the symbol table more efficiently. Note that this includes the + * pseudo-symbol 256, but since it is the last symbol, it will not affect the + * table. + */ + p = 0; + for (i = 1; i <= MAX_CLEN; i++) { + bit_pos[i] = p; + p += bits[i]; } /* JPEG doesn't allow symbols with code lengths over 16 bits, so if the pure @@ -1003,21 +1083,16 @@ jpeg_gen_optimal_table(j_compress_ptr cinfo, JHUFF_TBL *htbl, long freq[]) bits[i]--; /* Return final symbol counts (only for lengths 0..16) */ - MEMCOPY(htbl->bits, bits, sizeof(htbl->bits)); + memcpy(htbl->bits, bits, sizeof(htbl->bits)); /* Return a list of the symbols sorted by code length */ /* It's not real clear to me why we don't need to consider the codelength * changes made above, but Rec. ITU-T T.81 | ISO/IEC 10918-1 seems to think * this works. */ - p = 0; - for (i = 1; i <= MAX_CLEN; i++) { - for (j = 0; j <= 255; j++) { - if (codesize[j] == i) { - htbl->huffval[p] = (UINT8)j; - p++; - } - } + for (i = 0; i < num_nz_symbols - 1; i++) { + htbl->huffval[bit_pos[codesize[i]]] = (UINT8)nz_index[i]; + bit_pos[codesize[i]]++; } /* Set sent_table FALSE so updated table will be written to JPEG file. */ @@ -1042,8 +1117,8 @@ finish_pass_gather(j_compress_ptr cinfo) /* It's important not to apply jpeg_gen_optimal_table more than once * per table, because it clobbers the input frequency counts! */ - MEMZERO(did_dc, sizeof(did_dc)); - MEMZERO(did_ac, sizeof(did_ac)); + memset(did_dc, 0, sizeof(did_dc)); + memset(did_ac, 0, sizeof(did_ac)); for (ci = 0; ci < cinfo->comps_in_scan; ci++) { compptr = cinfo->cur_comp_info[ci]; |