1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/media/libjpeg/jchuff.c Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,1018 @@
1.4 +/*
1.5 + * jchuff.c
1.6 + *
1.7 + * This file was part of the Independent JPEG Group's software:
1.8 + * Copyright (C) 1991-1997, Thomas G. Lane.
1.9 + * libjpeg-turbo Modifications:
1.10 + * Copyright (C) 2009-2011, D. R. Commander.
1.11 + * For conditions of distribution and use, see the accompanying README file.
1.12 + *
1.13 + * This file contains Huffman entropy encoding routines.
1.14 + *
1.15 + * Much of the complexity here has to do with supporting output suspension.
1.16 + * If the data destination module demands suspension, we want to be able to
1.17 + * back up to the start of the current MCU. To do this, we copy state
1.18 + * variables into local working storage, and update them back to the
1.19 + * permanent JPEG objects only upon successful completion of an MCU.
1.20 + */
1.21 +
1.22 +#define JPEG_INTERNALS
1.23 +#include "jinclude.h"
1.24 +#include "jpeglib.h"
1.25 +#include "jchuff.h" /* Declarations shared with jcphuff.c */
1.26 +#include <limits.h>
1.27 +
1.28 +static const unsigned char jpeg_nbits_table[65536] = {
1.29 +/* Number i needs jpeg_nbits_table[i] bits to be represented. */
1.30 +#include "jpeg_nbits_table.h"
1.31 +};
1.32 +
1.33 +#ifndef min
1.34 + #define min(a,b) ((a)<(b)?(a):(b))
1.35 +#endif
1.36 +
1.37 +
1.38 +/* Expanded entropy encoder object for Huffman encoding.
1.39 + *
1.40 + * The savable_state subrecord contains fields that change within an MCU,
1.41 + * but must not be updated permanently until we complete the MCU.
1.42 + */
1.43 +
1.44 +typedef struct {
1.45 + size_t put_buffer; /* current bit-accumulation buffer */
1.46 + int put_bits; /* # of bits now in it */
1.47 + int last_dc_val[MAX_COMPS_IN_SCAN]; /* last DC coef for each component */
1.48 +} savable_state;
1.49 +
1.50 +/* This macro is to work around compilers with missing or broken
1.51 + * structure assignment. You'll need to fix this code if you have
1.52 + * such a compiler and you change MAX_COMPS_IN_SCAN.
1.53 + */
1.54 +
1.55 +#ifndef NO_STRUCT_ASSIGN
1.56 +#define ASSIGN_STATE(dest,src) ((dest) = (src))
1.57 +#else
1.58 +#if MAX_COMPS_IN_SCAN == 4
1.59 +#define ASSIGN_STATE(dest,src) \
1.60 + ((dest).put_buffer = (src).put_buffer, \
1.61 + (dest).put_bits = (src).put_bits, \
1.62 + (dest).last_dc_val[0] = (src).last_dc_val[0], \
1.63 + (dest).last_dc_val[1] = (src).last_dc_val[1], \
1.64 + (dest).last_dc_val[2] = (src).last_dc_val[2], \
1.65 + (dest).last_dc_val[3] = (src).last_dc_val[3])
1.66 +#endif
1.67 +#endif
1.68 +
1.69 +
1.70 +typedef struct {
1.71 + struct jpeg_entropy_encoder pub; /* public fields */
1.72 +
1.73 + savable_state saved; /* Bit buffer & DC state at start of MCU */
1.74 +
1.75 + /* These fields are NOT loaded into local working state. */
1.76 + unsigned int restarts_to_go; /* MCUs left in this restart interval */
1.77 + int next_restart_num; /* next restart number to write (0-7) */
1.78 +
1.79 + /* Pointers to derived tables (these workspaces have image lifespan) */
1.80 + c_derived_tbl * dc_derived_tbls[NUM_HUFF_TBLS];
1.81 + c_derived_tbl * ac_derived_tbls[NUM_HUFF_TBLS];
1.82 +
1.83 +#ifdef ENTROPY_OPT_SUPPORTED /* Statistics tables for optimization */
1.84 + long * dc_count_ptrs[NUM_HUFF_TBLS];
1.85 + long * ac_count_ptrs[NUM_HUFF_TBLS];
1.86 +#endif
1.87 +} huff_entropy_encoder;
1.88 +
1.89 +typedef huff_entropy_encoder * huff_entropy_ptr;
1.90 +
1.91 +/* Working state while writing an MCU.
1.92 + * This struct contains all the fields that are needed by subroutines.
1.93 + */
1.94 +
1.95 +typedef struct {
1.96 + JOCTET * next_output_byte; /* => next byte to write in buffer */
1.97 + size_t free_in_buffer; /* # of byte spaces remaining in buffer */
1.98 + savable_state cur; /* Current bit buffer & DC state */
1.99 + j_compress_ptr cinfo; /* dump_buffer needs access to this */
1.100 +} working_state;
1.101 +
1.102 +
1.103 +/* Forward declarations */
1.104 +METHODDEF(boolean) encode_mcu_huff JPP((j_compress_ptr cinfo,
1.105 + JBLOCKROW *MCU_data));
1.106 +METHODDEF(void) finish_pass_huff JPP((j_compress_ptr cinfo));
1.107 +#ifdef ENTROPY_OPT_SUPPORTED
1.108 +METHODDEF(boolean) encode_mcu_gather JPP((j_compress_ptr cinfo,
1.109 + JBLOCKROW *MCU_data));
1.110 +METHODDEF(void) finish_pass_gather JPP((j_compress_ptr cinfo));
1.111 +#endif
1.112 +
1.113 +
1.114 +/*
1.115 + * Initialize for a Huffman-compressed scan.
1.116 + * If gather_statistics is TRUE, we do not output anything during the scan,
1.117 + * just count the Huffman symbols used and generate Huffman code tables.
1.118 + */
1.119 +
1.120 +METHODDEF(void)
1.121 +start_pass_huff (j_compress_ptr cinfo, boolean gather_statistics)
1.122 +{
1.123 + huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
1.124 + int ci, dctbl, actbl;
1.125 + jpeg_component_info * compptr;
1.126 +
1.127 + if (gather_statistics) {
1.128 +#ifdef ENTROPY_OPT_SUPPORTED
1.129 + entropy->pub.encode_mcu = encode_mcu_gather;
1.130 + entropy->pub.finish_pass = finish_pass_gather;
1.131 +#else
1.132 + ERREXIT(cinfo, JERR_NOT_COMPILED);
1.133 +#endif
1.134 + } else {
1.135 + entropy->pub.encode_mcu = encode_mcu_huff;
1.136 + entropy->pub.finish_pass = finish_pass_huff;
1.137 + }
1.138 +
1.139 + for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
1.140 + compptr = cinfo->cur_comp_info[ci];
1.141 + dctbl = compptr->dc_tbl_no;
1.142 + actbl = compptr->ac_tbl_no;
1.143 + if (gather_statistics) {
1.144 +#ifdef ENTROPY_OPT_SUPPORTED
1.145 + /* Check for invalid table indexes */
1.146 + /* (make_c_derived_tbl does this in the other path) */
1.147 + if (dctbl < 0 || dctbl >= NUM_HUFF_TBLS)
1.148 + ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, dctbl);
1.149 + if (actbl < 0 || actbl >= NUM_HUFF_TBLS)
1.150 + ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, actbl);
1.151 + /* Allocate and zero the statistics tables */
1.152 + /* Note that jpeg_gen_optimal_table expects 257 entries in each table! */
1.153 + if (entropy->dc_count_ptrs[dctbl] == NULL)
1.154 + entropy->dc_count_ptrs[dctbl] = (long *)
1.155 + (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
1.156 + 257 * SIZEOF(long));
1.157 + MEMZERO(entropy->dc_count_ptrs[dctbl], 257 * SIZEOF(long));
1.158 + if (entropy->ac_count_ptrs[actbl] == NULL)
1.159 + entropy->ac_count_ptrs[actbl] = (long *)
1.160 + (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
1.161 + 257 * SIZEOF(long));
1.162 + MEMZERO(entropy->ac_count_ptrs[actbl], 257 * SIZEOF(long));
1.163 +#endif
1.164 + } else {
1.165 + /* Compute derived values for Huffman tables */
1.166 + /* We may do this more than once for a table, but it's not expensive */
1.167 + jpeg_make_c_derived_tbl(cinfo, TRUE, dctbl,
1.168 + & entropy->dc_derived_tbls[dctbl]);
1.169 + jpeg_make_c_derived_tbl(cinfo, FALSE, actbl,
1.170 + & entropy->ac_derived_tbls[actbl]);
1.171 + }
1.172 + /* Initialize DC predictions to 0 */
1.173 + entropy->saved.last_dc_val[ci] = 0;
1.174 + }
1.175 +
1.176 + /* Initialize bit buffer to empty */
1.177 + entropy->saved.put_buffer = 0;
1.178 + entropy->saved.put_bits = 0;
1.179 +
1.180 + /* Initialize restart stuff */
1.181 + entropy->restarts_to_go = cinfo->restart_interval;
1.182 + entropy->next_restart_num = 0;
1.183 +}
1.184 +
1.185 +
1.186 +/*
1.187 + * Compute the derived values for a Huffman table.
1.188 + * This routine also performs some validation checks on the table.
1.189 + *
1.190 + * Note this is also used by jcphuff.c.
1.191 + */
1.192 +
1.193 +GLOBAL(void)
1.194 +jpeg_make_c_derived_tbl (j_compress_ptr cinfo, boolean isDC, int tblno,
1.195 + c_derived_tbl ** pdtbl)
1.196 +{
1.197 + JHUFF_TBL *htbl;
1.198 + c_derived_tbl *dtbl;
1.199 + int p, i, l, lastp, si, maxsymbol;
1.200 + char huffsize[257];
1.201 + unsigned int huffcode[257];
1.202 + unsigned int code;
1.203 +
1.204 + /* Note that huffsize[] and huffcode[] are filled in code-length order,
1.205 + * paralleling the order of the symbols themselves in htbl->huffval[].
1.206 + */
1.207 +
1.208 + /* Find the input Huffman table */
1.209 + if (tblno < 0 || tblno >= NUM_HUFF_TBLS)
1.210 + ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tblno);
1.211 + htbl =
1.212 + isDC ? cinfo->dc_huff_tbl_ptrs[tblno] : cinfo->ac_huff_tbl_ptrs[tblno];
1.213 + if (htbl == NULL)
1.214 + ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tblno);
1.215 +
1.216 + /* Allocate a workspace if we haven't already done so. */
1.217 + if (*pdtbl == NULL)
1.218 + *pdtbl = (c_derived_tbl *)
1.219 + (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
1.220 + SIZEOF(c_derived_tbl));
1.221 + dtbl = *pdtbl;
1.222 +
1.223 + /* Figure C.1: make table of Huffman code length for each symbol */
1.224 +
1.225 + p = 0;
1.226 + for (l = 1; l <= 16; l++) {
1.227 + i = (int) htbl->bits[l];
1.228 + if (i < 0 || p + i > 256) /* protect against table overrun */
1.229 + ERREXIT(cinfo, JERR_BAD_HUFF_TABLE);
1.230 + while (i--)
1.231 + huffsize[p++] = (char) l;
1.232 + }
1.233 + huffsize[p] = 0;
1.234 + lastp = p;
1.235 +
1.236 + /* Figure C.2: generate the codes themselves */
1.237 + /* We also validate that the counts represent a legal Huffman code tree. */
1.238 +
1.239 + code = 0;
1.240 + si = huffsize[0];
1.241 + p = 0;
1.242 + while (huffsize[p]) {
1.243 + while (((int) huffsize[p]) == si) {
1.244 + huffcode[p++] = code;
1.245 + code++;
1.246 + }
1.247 + /* code is now 1 more than the last code used for codelength si; but
1.248 + * it must still fit in si bits, since no code is allowed to be all ones.
1.249 + */
1.250 + if (((INT32) code) >= (((INT32) 1) << si))
1.251 + ERREXIT(cinfo, JERR_BAD_HUFF_TABLE);
1.252 + code <<= 1;
1.253 + si++;
1.254 + }
1.255 +
1.256 + /* Figure C.3: generate encoding tables */
1.257 + /* These are code and size indexed by symbol value */
1.258 +
1.259 + /* Set all codeless symbols to have code length 0;
1.260 + * this lets us detect duplicate VAL entries here, and later
1.261 + * allows emit_bits to detect any attempt to emit such symbols.
1.262 + */
1.263 + MEMZERO(dtbl->ehufsi, SIZEOF(dtbl->ehufsi));
1.264 +
1.265 + /* This is also a convenient place to check for out-of-range
1.266 + * and duplicated VAL entries. We allow 0..255 for AC symbols
1.267 + * but only 0..15 for DC. (We could constrain them further
1.268 + * based on data depth and mode, but this seems enough.)
1.269 + */
1.270 + maxsymbol = isDC ? 15 : 255;
1.271 +
1.272 + for (p = 0; p < lastp; p++) {
1.273 + i = htbl->huffval[p];
1.274 + if (i < 0 || i > maxsymbol || dtbl->ehufsi[i])
1.275 + ERREXIT(cinfo, JERR_BAD_HUFF_TABLE);
1.276 + dtbl->ehufco[i] = huffcode[p];
1.277 + dtbl->ehufsi[i] = huffsize[p];
1.278 + }
1.279 +}
1.280 +
1.281 +
1.282 +/* Outputting bytes to the file */
1.283 +
1.284 +/* Emit a byte, taking 'action' if must suspend. */
1.285 +#define emit_byte(state,val,action) \
1.286 + { *(state)->next_output_byte++ = (JOCTET) (val); \
1.287 + if (--(state)->free_in_buffer == 0) \
1.288 + if (! dump_buffer(state)) \
1.289 + { action; } }
1.290 +
1.291 +
1.292 +LOCAL(boolean)
1.293 +dump_buffer (working_state * state)
1.294 +/* Empty the output buffer; return TRUE if successful, FALSE if must suspend */
1.295 +{
1.296 + struct jpeg_destination_mgr * dest = state->cinfo->dest;
1.297 +
1.298 + if (! (*dest->empty_output_buffer) (state->cinfo))
1.299 + return FALSE;
1.300 + /* After a successful buffer dump, must reset buffer pointers */
1.301 + state->next_output_byte = dest->next_output_byte;
1.302 + state->free_in_buffer = dest->free_in_buffer;
1.303 + return TRUE;
1.304 +}
1.305 +
1.306 +
1.307 +/* Outputting bits to the file */
1.308 +
1.309 +/* These macros perform the same task as the emit_bits() function in the
1.310 + * original libjpeg code. In addition to reducing overhead by explicitly
1.311 + * inlining the code, additional performance is achieved by taking into
1.312 + * account the size of the bit buffer and waiting until it is almost full
1.313 + * before emptying it. This mostly benefits 64-bit platforms, since 6
1.314 + * bytes can be stored in a 64-bit bit buffer before it has to be emptied.
1.315 + */
1.316 +
1.317 +#define EMIT_BYTE() { \
1.318 + JOCTET c; \
1.319 + put_bits -= 8; \
1.320 + c = (JOCTET)GETJOCTET(put_buffer >> put_bits); \
1.321 + *buffer++ = c; \
1.322 + if (c == 0xFF) /* need to stuff a zero byte? */ \
1.323 + *buffer++ = 0; \
1.324 + }
1.325 +
1.326 +#define PUT_BITS(code, size) { \
1.327 + put_bits += size; \
1.328 + put_buffer = (put_buffer << size) | code; \
1.329 +}
1.330 +
1.331 +#define CHECKBUF15() { \
1.332 + if (put_bits > 15) { \
1.333 + EMIT_BYTE() \
1.334 + EMIT_BYTE() \
1.335 + } \
1.336 +}
1.337 +
1.338 +#define CHECKBUF31() { \
1.339 + if (put_bits > 31) { \
1.340 + EMIT_BYTE() \
1.341 + EMIT_BYTE() \
1.342 + EMIT_BYTE() \
1.343 + EMIT_BYTE() \
1.344 + } \
1.345 +}
1.346 +
1.347 +#define CHECKBUF47() { \
1.348 + if (put_bits > 47) { \
1.349 + EMIT_BYTE() \
1.350 + EMIT_BYTE() \
1.351 + EMIT_BYTE() \
1.352 + EMIT_BYTE() \
1.353 + EMIT_BYTE() \
1.354 + EMIT_BYTE() \
1.355 + } \
1.356 +}
1.357 +
1.358 +#if __WORDSIZE==64 || defined(_WIN64)
1.359 +
1.360 +#define EMIT_BITS(code, size) { \
1.361 + CHECKBUF47() \
1.362 + PUT_BITS(code, size) \
1.363 +}
1.364 +
1.365 +#define EMIT_CODE(code, size) { \
1.366 + temp2 &= (((INT32) 1)<<nbits) - 1; \
1.367 + CHECKBUF31() \
1.368 + PUT_BITS(code, size) \
1.369 + PUT_BITS(temp2, nbits) \
1.370 + }
1.371 +
1.372 +#else
1.373 +
1.374 +#define EMIT_BITS(code, size) { \
1.375 + PUT_BITS(code, size) \
1.376 + CHECKBUF15() \
1.377 +}
1.378 +
1.379 +#define EMIT_CODE(code, size) { \
1.380 + temp2 &= (((INT32) 1)<<nbits) - 1; \
1.381 + PUT_BITS(code, size) \
1.382 + CHECKBUF15() \
1.383 + PUT_BITS(temp2, nbits) \
1.384 + CHECKBUF15() \
1.385 + }
1.386 +
1.387 +#endif
1.388 +
1.389 +
1.390 +#define BUFSIZE (DCTSIZE2 * 2)
1.391 +
1.392 +#define LOAD_BUFFER() { \
1.393 + if (state->free_in_buffer < BUFSIZE) { \
1.394 + localbuf = 1; \
1.395 + buffer = _buffer; \
1.396 + } \
1.397 + else buffer = state->next_output_byte; \
1.398 + }
1.399 +
1.400 +#define STORE_BUFFER() { \
1.401 + if (localbuf) { \
1.402 + bytes = buffer - _buffer; \
1.403 + buffer = _buffer; \
1.404 + while (bytes > 0) { \
1.405 + bytestocopy = min(bytes, state->free_in_buffer); \
1.406 + MEMCOPY(state->next_output_byte, buffer, bytestocopy); \
1.407 + state->next_output_byte += bytestocopy; \
1.408 + buffer += bytestocopy; \
1.409 + state->free_in_buffer -= bytestocopy; \
1.410 + if (state->free_in_buffer == 0) \
1.411 + if (! dump_buffer(state)) return FALSE; \
1.412 + bytes -= bytestocopy; \
1.413 + } \
1.414 + } \
1.415 + else { \
1.416 + state->free_in_buffer -= (buffer - state->next_output_byte); \
1.417 + state->next_output_byte = buffer; \
1.418 + } \
1.419 + }
1.420 +
1.421 +
1.422 +LOCAL(boolean)
1.423 +flush_bits (working_state * state)
1.424 +{
1.425 + JOCTET _buffer[BUFSIZE], *buffer;
1.426 + size_t put_buffer; int put_bits;
1.427 + size_t bytes, bytestocopy; int localbuf = 0;
1.428 +
1.429 + put_buffer = state->cur.put_buffer;
1.430 + put_bits = state->cur.put_bits;
1.431 + LOAD_BUFFER()
1.432 +
1.433 + /* fill any partial byte with ones */
1.434 + PUT_BITS(0x7F, 7)
1.435 + while (put_bits >= 8) EMIT_BYTE()
1.436 +
1.437 + state->cur.put_buffer = 0; /* and reset bit-buffer to empty */
1.438 + state->cur.put_bits = 0;
1.439 + STORE_BUFFER()
1.440 +
1.441 + return TRUE;
1.442 +}
1.443 +
1.444 +
1.445 +/* Encode a single block's worth of coefficients */
1.446 +
1.447 +LOCAL(boolean)
1.448 +encode_one_block (working_state * state, JCOEFPTR block, int last_dc_val,
1.449 + c_derived_tbl *dctbl, c_derived_tbl *actbl)
1.450 +{
1.451 + int temp, temp2, temp3;
1.452 + int nbits;
1.453 + int r, code, size;
1.454 + JOCTET _buffer[BUFSIZE], *buffer;
1.455 + size_t put_buffer; int put_bits;
1.456 + int code_0xf0 = actbl->ehufco[0xf0], size_0xf0 = actbl->ehufsi[0xf0];
1.457 + size_t bytes, bytestocopy; int localbuf = 0;
1.458 +
1.459 + put_buffer = state->cur.put_buffer;
1.460 + put_bits = state->cur.put_bits;
1.461 + LOAD_BUFFER()
1.462 +
1.463 + /* Encode the DC coefficient difference per section F.1.2.1 */
1.464 +
1.465 + temp = temp2 = block[0] - last_dc_val;
1.466 +
1.467 + /* This is a well-known technique for obtaining the absolute value without a
1.468 + * branch. It is derived from an assembly language technique presented in
1.469 + * "How to Optimize for the Pentium Processors", Copyright (c) 1996, 1997 by
1.470 + * Agner Fog.
1.471 + */
1.472 + temp3 = temp >> (CHAR_BIT * sizeof(int) - 1);
1.473 + temp ^= temp3;
1.474 + temp -= temp3;
1.475 +
1.476 + /* For a negative input, want temp2 = bitwise complement of abs(input) */
1.477 + /* This code assumes we are on a two's complement machine */
1.478 + temp2 += temp3;
1.479 +
1.480 + /* Find the number of bits needed for the magnitude of the coefficient */
1.481 + nbits = jpeg_nbits_table[temp];
1.482 +
1.483 + /* Emit the Huffman-coded symbol for the number of bits */
1.484 + code = dctbl->ehufco[nbits];
1.485 + size = dctbl->ehufsi[nbits];
1.486 + PUT_BITS(code, size)
1.487 + CHECKBUF15()
1.488 +
1.489 + /* Mask off any extra bits in code */
1.490 + temp2 &= (((INT32) 1)<<nbits) - 1;
1.491 +
1.492 + /* Emit that number of bits of the value, if positive, */
1.493 + /* or the complement of its magnitude, if negative. */
1.494 + PUT_BITS(temp2, nbits)
1.495 + CHECKBUF15()
1.496 +
1.497 + /* Encode the AC coefficients per section F.1.2.2 */
1.498 +
1.499 + r = 0; /* r = run length of zeros */
1.500 +
1.501 +/* Manually unroll the k loop to eliminate the counter variable. This
1.502 + * improves performance greatly on systems with a limited number of
1.503 + * registers (such as x86.)
1.504 + */
1.505 +#define kloop(jpeg_natural_order_of_k) { \
1.506 + if ((temp = block[jpeg_natural_order_of_k]) == 0) { \
1.507 + r++; \
1.508 + } else { \
1.509 + temp2 = temp; \
1.510 + /* Branch-less absolute value, bitwise complement, etc., same as above */ \
1.511 + temp3 = temp >> (CHAR_BIT * sizeof(int) - 1); \
1.512 + temp ^= temp3; \
1.513 + temp -= temp3; \
1.514 + temp2 += temp3; \
1.515 + nbits = jpeg_nbits_table[temp]; \
1.516 + /* if run length > 15, must emit special run-length-16 codes (0xF0) */ \
1.517 + while (r > 15) { \
1.518 + EMIT_BITS(code_0xf0, size_0xf0) \
1.519 + r -= 16; \
1.520 + } \
1.521 + /* Emit Huffman symbol for run length / number of bits */ \
1.522 + temp3 = (r << 4) + nbits; \
1.523 + code = actbl->ehufco[temp3]; \
1.524 + size = actbl->ehufsi[temp3]; \
1.525 + EMIT_CODE(code, size) \
1.526 + r = 0; \
1.527 + } \
1.528 +}
1.529 +
1.530 + /* One iteration for each value in jpeg_natural_order[] */
1.531 + kloop(1); kloop(8); kloop(16); kloop(9); kloop(2); kloop(3);
1.532 + kloop(10); kloop(17); kloop(24); kloop(32); kloop(25); kloop(18);
1.533 + kloop(11); kloop(4); kloop(5); kloop(12); kloop(19); kloop(26);
1.534 + kloop(33); kloop(40); kloop(48); kloop(41); kloop(34); kloop(27);
1.535 + kloop(20); kloop(13); kloop(6); kloop(7); kloop(14); kloop(21);
1.536 + kloop(28); kloop(35); kloop(42); kloop(49); kloop(56); kloop(57);
1.537 + kloop(50); kloop(43); kloop(36); kloop(29); kloop(22); kloop(15);
1.538 + kloop(23); kloop(30); kloop(37); kloop(44); kloop(51); kloop(58);
1.539 + kloop(59); kloop(52); kloop(45); kloop(38); kloop(31); kloop(39);
1.540 + kloop(46); kloop(53); kloop(60); kloop(61); kloop(54); kloop(47);
1.541 + kloop(55); kloop(62); kloop(63);
1.542 +
1.543 + /* If the last coef(s) were zero, emit an end-of-block code */
1.544 + if (r > 0) {
1.545 + code = actbl->ehufco[0];
1.546 + size = actbl->ehufsi[0];
1.547 + EMIT_BITS(code, size)
1.548 + }
1.549 +
1.550 + state->cur.put_buffer = put_buffer;
1.551 + state->cur.put_bits = put_bits;
1.552 + STORE_BUFFER()
1.553 +
1.554 + return TRUE;
1.555 +}
1.556 +
1.557 +
1.558 +/*
1.559 + * Emit a restart marker & resynchronize predictions.
1.560 + */
1.561 +
1.562 +LOCAL(boolean)
1.563 +emit_restart (working_state * state, int restart_num)
1.564 +{
1.565 + int ci;
1.566 +
1.567 + if (! flush_bits(state))
1.568 + return FALSE;
1.569 +
1.570 + emit_byte(state, 0xFF, return FALSE);
1.571 + emit_byte(state, JPEG_RST0 + restart_num, return FALSE);
1.572 +
1.573 + /* Re-initialize DC predictions to 0 */
1.574 + for (ci = 0; ci < state->cinfo->comps_in_scan; ci++)
1.575 + state->cur.last_dc_val[ci] = 0;
1.576 +
1.577 + /* The restart counter is not updated until we successfully write the MCU. */
1.578 +
1.579 + return TRUE;
1.580 +}
1.581 +
1.582 +
1.583 +/*
1.584 + * Encode and output one MCU's worth of Huffman-compressed coefficients.
1.585 + */
1.586 +
1.587 +METHODDEF(boolean)
1.588 +encode_mcu_huff (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
1.589 +{
1.590 + huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
1.591 + working_state state;
1.592 + int blkn, ci;
1.593 + jpeg_component_info * compptr;
1.594 +
1.595 + /* Load up working state */
1.596 + state.next_output_byte = cinfo->dest->next_output_byte;
1.597 + state.free_in_buffer = cinfo->dest->free_in_buffer;
1.598 + ASSIGN_STATE(state.cur, entropy->saved);
1.599 + state.cinfo = cinfo;
1.600 +
1.601 + /* Emit restart marker if needed */
1.602 + if (cinfo->restart_interval) {
1.603 + if (entropy->restarts_to_go == 0)
1.604 + if (! emit_restart(&state, entropy->next_restart_num))
1.605 + return FALSE;
1.606 + }
1.607 +
1.608 + /* Encode the MCU data blocks */
1.609 + for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
1.610 + ci = cinfo->MCU_membership[blkn];
1.611 + compptr = cinfo->cur_comp_info[ci];
1.612 + if (! encode_one_block(&state,
1.613 + MCU_data[blkn][0], state.cur.last_dc_val[ci],
1.614 + entropy->dc_derived_tbls[compptr->dc_tbl_no],
1.615 + entropy->ac_derived_tbls[compptr->ac_tbl_no]))
1.616 + return FALSE;
1.617 + /* Update last_dc_val */
1.618 + state.cur.last_dc_val[ci] = MCU_data[blkn][0][0];
1.619 + }
1.620 +
1.621 + /* Completed MCU, so update state */
1.622 + cinfo->dest->next_output_byte = state.next_output_byte;
1.623 + cinfo->dest->free_in_buffer = state.free_in_buffer;
1.624 + ASSIGN_STATE(entropy->saved, state.cur);
1.625 +
1.626 + /* Update restart-interval state too */
1.627 + if (cinfo->restart_interval) {
1.628 + if (entropy->restarts_to_go == 0) {
1.629 + entropy->restarts_to_go = cinfo->restart_interval;
1.630 + entropy->next_restart_num++;
1.631 + entropy->next_restart_num &= 7;
1.632 + }
1.633 + entropy->restarts_to_go--;
1.634 + }
1.635 +
1.636 + return TRUE;
1.637 +}
1.638 +
1.639 +
1.640 +/*
1.641 + * Finish up at the end of a Huffman-compressed scan.
1.642 + */
1.643 +
1.644 +METHODDEF(void)
1.645 +finish_pass_huff (j_compress_ptr cinfo)
1.646 +{
1.647 + huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
1.648 + working_state state;
1.649 +
1.650 + /* Load up working state ... flush_bits needs it */
1.651 + state.next_output_byte = cinfo->dest->next_output_byte;
1.652 + state.free_in_buffer = cinfo->dest->free_in_buffer;
1.653 + ASSIGN_STATE(state.cur, entropy->saved);
1.654 + state.cinfo = cinfo;
1.655 +
1.656 + /* Flush out the last data */
1.657 + if (! flush_bits(&state))
1.658 + ERREXIT(cinfo, JERR_CANT_SUSPEND);
1.659 +
1.660 + /* Update state */
1.661 + cinfo->dest->next_output_byte = state.next_output_byte;
1.662 + cinfo->dest->free_in_buffer = state.free_in_buffer;
1.663 + ASSIGN_STATE(entropy->saved, state.cur);
1.664 +}
1.665 +
1.666 +
1.667 +/*
1.668 + * Huffman coding optimization.
1.669 + *
1.670 + * We first scan the supplied data and count the number of uses of each symbol
1.671 + * that is to be Huffman-coded. (This process MUST agree with the code above.)
1.672 + * Then we build a Huffman coding tree for the observed counts.
1.673 + * Symbols which are not needed at all for the particular image are not
1.674 + * assigned any code, which saves space in the DHT marker as well as in
1.675 + * the compressed data.
1.676 + */
1.677 +
1.678 +#ifdef ENTROPY_OPT_SUPPORTED
1.679 +
1.680 +
1.681 +/* Process a single block's worth of coefficients */
1.682 +
1.683 +LOCAL(void)
1.684 +htest_one_block (j_compress_ptr cinfo, JCOEFPTR block, int last_dc_val,
1.685 + long dc_counts[], long ac_counts[])
1.686 +{
1.687 + register int temp;
1.688 + register int nbits;
1.689 + register int k, r;
1.690 +
1.691 + /* Encode the DC coefficient difference per section F.1.2.1 */
1.692 +
1.693 + temp = block[0] - last_dc_val;
1.694 + if (temp < 0)
1.695 + temp = -temp;
1.696 +
1.697 + /* Find the number of bits needed for the magnitude of the coefficient */
1.698 + nbits = 0;
1.699 + while (temp) {
1.700 + nbits++;
1.701 + temp >>= 1;
1.702 + }
1.703 + /* Check for out-of-range coefficient values.
1.704 + * Since we're encoding a difference, the range limit is twice as much.
1.705 + */
1.706 + if (nbits > MAX_COEF_BITS+1)
1.707 + ERREXIT(cinfo, JERR_BAD_DCT_COEF);
1.708 +
1.709 + /* Count the Huffman symbol for the number of bits */
1.710 + dc_counts[nbits]++;
1.711 +
1.712 + /* Encode the AC coefficients per section F.1.2.2 */
1.713 +
1.714 + r = 0; /* r = run length of zeros */
1.715 +
1.716 + for (k = 1; k < DCTSIZE2; k++) {
1.717 + if ((temp = block[jpeg_natural_order[k]]) == 0) {
1.718 + r++;
1.719 + } else {
1.720 + /* if run length > 15, must emit special run-length-16 codes (0xF0) */
1.721 + while (r > 15) {
1.722 + ac_counts[0xF0]++;
1.723 + r -= 16;
1.724 + }
1.725 +
1.726 + /* Find the number of bits needed for the magnitude of the coefficient */
1.727 + if (temp < 0)
1.728 + temp = -temp;
1.729 +
1.730 + /* Find the number of bits needed for the magnitude of the coefficient */
1.731 + nbits = 1; /* there must be at least one 1 bit */
1.732 + while ((temp >>= 1))
1.733 + nbits++;
1.734 + /* Check for out-of-range coefficient values */
1.735 + if (nbits > MAX_COEF_BITS)
1.736 + ERREXIT(cinfo, JERR_BAD_DCT_COEF);
1.737 +
1.738 + /* Count Huffman symbol for run length / number of bits */
1.739 + ac_counts[(r << 4) + nbits]++;
1.740 +
1.741 + r = 0;
1.742 + }
1.743 + }
1.744 +
1.745 + /* If the last coef(s) were zero, emit an end-of-block code */
1.746 + if (r > 0)
1.747 + ac_counts[0]++;
1.748 +}
1.749 +
1.750 +
1.751 +/*
1.752 + * Trial-encode one MCU's worth of Huffman-compressed coefficients.
1.753 + * No data is actually output, so no suspension return is possible.
1.754 + */
1.755 +
1.756 +METHODDEF(boolean)
1.757 +encode_mcu_gather (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
1.758 +{
1.759 + huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
1.760 + int blkn, ci;
1.761 + jpeg_component_info * compptr;
1.762 +
1.763 + /* Take care of restart intervals if needed */
1.764 + if (cinfo->restart_interval) {
1.765 + if (entropy->restarts_to_go == 0) {
1.766 + /* Re-initialize DC predictions to 0 */
1.767 + for (ci = 0; ci < cinfo->comps_in_scan; ci++)
1.768 + entropy->saved.last_dc_val[ci] = 0;
1.769 + /* Update restart state */
1.770 + entropy->restarts_to_go = cinfo->restart_interval;
1.771 + }
1.772 + entropy->restarts_to_go--;
1.773 + }
1.774 +
1.775 + for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
1.776 + ci = cinfo->MCU_membership[blkn];
1.777 + compptr = cinfo->cur_comp_info[ci];
1.778 + htest_one_block(cinfo, MCU_data[blkn][0], entropy->saved.last_dc_val[ci],
1.779 + entropy->dc_count_ptrs[compptr->dc_tbl_no],
1.780 + entropy->ac_count_ptrs[compptr->ac_tbl_no]);
1.781 + entropy->saved.last_dc_val[ci] = MCU_data[blkn][0][0];
1.782 + }
1.783 +
1.784 + return TRUE;
1.785 +}
1.786 +
1.787 +
1.788 +/*
1.789 + * Generate the best Huffman code table for the given counts, fill htbl.
1.790 + * Note this is also used by jcphuff.c.
1.791 + *
1.792 + * The JPEG standard requires that no symbol be assigned a codeword of all
1.793 + * one bits (so that padding bits added at the end of a compressed segment
1.794 + * can't look like a valid code). Because of the canonical ordering of
1.795 + * codewords, this just means that there must be an unused slot in the
1.796 + * longest codeword length category. Section K.2 of the JPEG spec suggests
1.797 + * reserving such a slot by pretending that symbol 256 is a valid symbol
1.798 + * with count 1. In theory that's not optimal; giving it count zero but
1.799 + * including it in the symbol set anyway should give a better Huffman code.
1.800 + * But the theoretically better code actually seems to come out worse in
1.801 + * practice, because it produces more all-ones bytes (which incur stuffed
1.802 + * zero bytes in the final file). In any case the difference is tiny.
1.803 + *
1.804 + * The JPEG standard requires Huffman codes to be no more than 16 bits long.
1.805 + * If some symbols have a very small but nonzero probability, the Huffman tree
1.806 + * must be adjusted to meet the code length restriction. We currently use
1.807 + * the adjustment method suggested in JPEG section K.2. This method is *not*
1.808 + * optimal; it may not choose the best possible limited-length code. But
1.809 + * typically only very-low-frequency symbols will be given less-than-optimal
1.810 + * lengths, so the code is almost optimal. Experimental comparisons against
1.811 + * an optimal limited-length-code algorithm indicate that the difference is
1.812 + * microscopic --- usually less than a hundredth of a percent of total size.
1.813 + * So the extra complexity of an optimal algorithm doesn't seem worthwhile.
1.814 + */
1.815 +
1.816 +GLOBAL(void)
1.817 +jpeg_gen_optimal_table (j_compress_ptr cinfo, JHUFF_TBL * htbl, long freq[])
1.818 +{
1.819 +#define MAX_CLEN 32 /* assumed maximum initial code length */
1.820 + UINT8 bits[MAX_CLEN+1]; /* bits[k] = # of symbols with code length k */
1.821 + int codesize[257]; /* codesize[k] = code length of symbol k */
1.822 + int others[257]; /* next symbol in current branch of tree */
1.823 + int c1, c2;
1.824 + int p, i, j;
1.825 + long v;
1.826 +
1.827 + /* This algorithm is explained in section K.2 of the JPEG standard */
1.828 +
1.829 + MEMZERO(bits, SIZEOF(bits));
1.830 + MEMZERO(codesize, SIZEOF(codesize));
1.831 + for (i = 0; i < 257; i++)
1.832 + others[i] = -1; /* init links to empty */
1.833 +
1.834 + freq[256] = 1; /* make sure 256 has a nonzero count */
1.835 + /* Including the pseudo-symbol 256 in the Huffman procedure guarantees
1.836 + * that no real symbol is given code-value of all ones, because 256
1.837 + * will be placed last in the largest codeword category.
1.838 + */
1.839 +
1.840 + /* Huffman's basic algorithm to assign optimal code lengths to symbols */
1.841 +
1.842 + for (;;) {
1.843 + /* Find the smallest nonzero frequency, set c1 = its symbol */
1.844 + /* In case of ties, take the larger symbol number */
1.845 + c1 = -1;
1.846 + v = 1000000000L;
1.847 + for (i = 0; i <= 256; i++) {
1.848 + if (freq[i] && freq[i] <= v) {
1.849 + v = freq[i];
1.850 + c1 = i;
1.851 + }
1.852 + }
1.853 +
1.854 + /* Find the next smallest nonzero frequency, set c2 = its symbol */
1.855 + /* In case of ties, take the larger symbol number */
1.856 + c2 = -1;
1.857 + v = 1000000000L;
1.858 + for (i = 0; i <= 256; i++) {
1.859 + if (freq[i] && freq[i] <= v && i != c1) {
1.860 + v = freq[i];
1.861 + c2 = i;
1.862 + }
1.863 + }
1.864 +
1.865 + /* Done if we've merged everything into one frequency */
1.866 + if (c2 < 0)
1.867 + break;
1.868 +
1.869 + /* Else merge the two counts/trees */
1.870 + freq[c1] += freq[c2];
1.871 + freq[c2] = 0;
1.872 +
1.873 + /* Increment the codesize of everything in c1's tree branch */
1.874 + codesize[c1]++;
1.875 + while (others[c1] >= 0) {
1.876 + c1 = others[c1];
1.877 + codesize[c1]++;
1.878 + }
1.879 +
1.880 + others[c1] = c2; /* chain c2 onto c1's tree branch */
1.881 +
1.882 + /* Increment the codesize of everything in c2's tree branch */
1.883 + codesize[c2]++;
1.884 + while (others[c2] >= 0) {
1.885 + c2 = others[c2];
1.886 + codesize[c2]++;
1.887 + }
1.888 + }
1.889 +
1.890 + /* Now count the number of symbols of each code length */
1.891 + for (i = 0; i <= 256; i++) {
1.892 + if (codesize[i]) {
1.893 + /* The JPEG standard seems to think that this can't happen, */
1.894 + /* but I'm paranoid... */
1.895 + if (codesize[i] > MAX_CLEN)
1.896 + ERREXIT(cinfo, JERR_HUFF_CLEN_OVERFLOW);
1.897 +
1.898 + bits[codesize[i]]++;
1.899 + }
1.900 + }
1.901 +
1.902 + /* JPEG doesn't allow symbols with code lengths over 16 bits, so if the pure
1.903 + * Huffman procedure assigned any such lengths, we must adjust the coding.
1.904 + * Here is what the JPEG spec says about how this next bit works:
1.905 + * Since symbols are paired for the longest Huffman code, the symbols are
1.906 + * removed from this length category two at a time. The prefix for the pair
1.907 + * (which is one bit shorter) is allocated to one of the pair; then,
1.908 + * skipping the BITS entry for that prefix length, a code word from the next
1.909 + * shortest nonzero BITS entry is converted into a prefix for two code words
1.910 + * one bit longer.
1.911 + */
1.912 +
1.913 + for (i = MAX_CLEN; i > 16; i--) {
1.914 + while (bits[i] > 0) {
1.915 + j = i - 2; /* find length of new prefix to be used */
1.916 + while (bits[j] == 0)
1.917 + j--;
1.918 +
1.919 + bits[i] -= 2; /* remove two symbols */
1.920 + bits[i-1]++; /* one goes in this length */
1.921 + bits[j+1] += 2; /* two new symbols in this length */
1.922 + bits[j]--; /* symbol of this length is now a prefix */
1.923 + }
1.924 + }
1.925 +
1.926 + /* Remove the count for the pseudo-symbol 256 from the largest codelength */
1.927 + while (bits[i] == 0) /* find largest codelength still in use */
1.928 + i--;
1.929 + bits[i]--;
1.930 +
1.931 + /* Return final symbol counts (only for lengths 0..16) */
1.932 + MEMCOPY(htbl->bits, bits, SIZEOF(htbl->bits));
1.933 +
1.934 + /* Return a list of the symbols sorted by code length */
1.935 + /* It's not real clear to me why we don't need to consider the codelength
1.936 + * changes made above, but the JPEG spec seems to think this works.
1.937 + */
1.938 + p = 0;
1.939 + for (i = 1; i <= MAX_CLEN; i++) {
1.940 + for (j = 0; j <= 255; j++) {
1.941 + if (codesize[j] == i) {
1.942 + htbl->huffval[p] = (UINT8) j;
1.943 + p++;
1.944 + }
1.945 + }
1.946 + }
1.947 +
1.948 + /* Set sent_table FALSE so updated table will be written to JPEG file. */
1.949 + htbl->sent_table = FALSE;
1.950 +}
1.951 +
1.952 +
1.953 +/*
1.954 + * Finish up a statistics-gathering pass and create the new Huffman tables.
1.955 + */
1.956 +
1.957 +METHODDEF(void)
1.958 +finish_pass_gather (j_compress_ptr cinfo)
1.959 +{
1.960 + huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
1.961 + int ci, dctbl, actbl;
1.962 + jpeg_component_info * compptr;
1.963 + JHUFF_TBL **htblptr;
1.964 + boolean did_dc[NUM_HUFF_TBLS];
1.965 + boolean did_ac[NUM_HUFF_TBLS];
1.966 +
1.967 + /* It's important not to apply jpeg_gen_optimal_table more than once
1.968 + * per table, because it clobbers the input frequency counts!
1.969 + */
1.970 + MEMZERO(did_dc, SIZEOF(did_dc));
1.971 + MEMZERO(did_ac, SIZEOF(did_ac));
1.972 +
1.973 + for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
1.974 + compptr = cinfo->cur_comp_info[ci];
1.975 + dctbl = compptr->dc_tbl_no;
1.976 + actbl = compptr->ac_tbl_no;
1.977 + if (! did_dc[dctbl]) {
1.978 + htblptr = & cinfo->dc_huff_tbl_ptrs[dctbl];
1.979 + if (*htblptr == NULL)
1.980 + *htblptr = jpeg_alloc_huff_table((j_common_ptr) cinfo);
1.981 + jpeg_gen_optimal_table(cinfo, *htblptr, entropy->dc_count_ptrs[dctbl]);
1.982 + did_dc[dctbl] = TRUE;
1.983 + }
1.984 + if (! did_ac[actbl]) {
1.985 + htblptr = & cinfo->ac_huff_tbl_ptrs[actbl];
1.986 + if (*htblptr == NULL)
1.987 + *htblptr = jpeg_alloc_huff_table((j_common_ptr) cinfo);
1.988 + jpeg_gen_optimal_table(cinfo, *htblptr, entropy->ac_count_ptrs[actbl]);
1.989 + did_ac[actbl] = TRUE;
1.990 + }
1.991 + }
1.992 +}
1.993 +
1.994 +
1.995 +#endif /* ENTROPY_OPT_SUPPORTED */
1.996 +
1.997 +
1.998 +/*
1.999 + * Module initialization routine for Huffman entropy encoding.
1.1000 + */
1.1001 +
1.1002 +GLOBAL(void)
1.1003 +jinit_huff_encoder (j_compress_ptr cinfo)
1.1004 +{
1.1005 + huff_entropy_ptr entropy;
1.1006 + int i;
1.1007 +
1.1008 + entropy = (huff_entropy_ptr)
1.1009 + (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
1.1010 + SIZEOF(huff_entropy_encoder));
1.1011 + cinfo->entropy = (struct jpeg_entropy_encoder *) entropy;
1.1012 + entropy->pub.start_pass = start_pass_huff;
1.1013 +
1.1014 + /* Mark tables unallocated */
1.1015 + for (i = 0; i < NUM_HUFF_TBLS; i++) {
1.1016 + entropy->dc_derived_tbls[i] = entropy->ac_derived_tbls[i] = NULL;
1.1017 +#ifdef ENTROPY_OPT_SUPPORTED
1.1018 + entropy->dc_count_ptrs[i] = entropy->ac_count_ptrs[i] = NULL;
1.1019 +#endif
1.1020 + }
1.1021 +}
