Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(421)

Side by Side Diff: jchuff.c

Issue 1939823002: Update to libjpeg_turbo 1.4.90 (Closed) Base URL: https://chromium.googlesource.com/chromium/deps/libjpeg_turbo.git@master
Patch Set: Response to comments Created 4 years, 7 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « jchuff.h ('k') | jcinit.c » ('j') | jconfig.h » ('J')
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 /* 1 /*
2 * jchuff.c 2 * jchuff.c
3 * 3 *
4 * This file was part of the Independent JPEG Group's software: 4 * This file was part of the Independent JPEG Group's software:
5 * Copyright (C) 1991-1997, Thomas G. Lane. 5 * Copyright (C) 1991-1997, Thomas G. Lane.
6 * libjpeg-turbo Modifications: 6 * libjpeg-turbo Modifications:
7 * Copyright (C) 2009-2011, D. R. Commander. 7 * Copyright (C) 2009-2011, 2014-2016 D. R. Commander.
8 * For conditions of distribution and use, see the accompanying README file. 8 * Copyright (C) 2015 Matthieu Darbois.
9 * For conditions of distribution and use, see the accompanying README.ijg
10 * file.
9 * 11 *
10 * This file contains Huffman entropy encoding routines. 12 * This file contains Huffman entropy encoding routines.
11 * 13 *
12 * Much of the complexity here has to do with supporting output suspension. 14 * Much of the complexity here has to do with supporting output suspension.
13 * If the data destination module demands suspension, we want to be able to 15 * If the data destination module demands suspension, we want to be able to
14 * back up to the start of the current MCU. To do this, we copy state 16 * back up to the start of the current MCU. To do this, we copy state
15 * variables into local working storage, and update them back to the 17 * variables into local working storage, and update them back to the
16 * permanent JPEG objects only upon successful completion of an MCU. 18 * permanent JPEG objects only upon successful completion of an MCU.
17 */ 19 */
18 20
19 #define JPEG_INTERNALS 21 #define JPEG_INTERNALS
20 #include "jinclude.h" 22 #include "jinclude.h"
21 #include "jpeglib.h" 23 #include "jpeglib.h"
22 #include "jchuff.h"» » /* Declarations shared with jcphuff.c */ 24 #include "jsimd.h"
25 #include "jconfigint.h"
23 #include <limits.h> 26 #include <limits.h>
24 27
25 /* 28 /*
26 * NOTE: If USE_CLZ_INTRINSIC is defined, then clz/bsr instructions will be 29 * NOTE: If USE_CLZ_INTRINSIC is defined, then clz/bsr instructions will be
27 * used for bit counting rather than the lookup table. This will reduce the 30 * used for bit counting rather than the lookup table. This will reduce the
28 * memory footprint by 64k, which is important for some mobile applications 31 * memory footprint by 64k, which is important for some mobile applications
29 * that create many isolated instances of libjpeg-turbo (web browsers, for 32 * that create many isolated instances of libjpeg-turbo (web browsers, for
30 * instance.) This may improve performance on some mobile platforms as well. 33 * instance.) This may improve performance on some mobile platforms as well.
31 * This feature is enabled by default only on ARM processors, because some x86 34 * This feature is enabled by default only on ARM processors, because some x86
32 * chips have a slow implementation of bsr, and the use of clz/bsr cannot be 35 * chips have a slow implementation of bsr, and the use of clz/bsr cannot be
33 * shown to have a significant performance impact even on the x86 chips that 36 * shown to have a significant performance impact even on the x86 chips that
34 * have a fast implementation of it. When building for ARMv6, you can 37 * have a fast implementation of it. When building for ARMv6, you can
35 * explicitly disable the use of clz/bsr by adding -mthumb to the compiler 38 * explicitly disable the use of clz/bsr by adding -mthumb to the compiler
36 * flags (this defines __thumb__). 39 * flags (this defines __thumb__).
37 */ 40 */
38 41
39 /* NOTE: Both GCC and Clang define __GNUC__ */ 42 /* NOTE: Both GCC and Clang define __GNUC__ */
40 #if defined __GNUC__ && defined __arm__ 43 #if defined __GNUC__ && (defined __arm__ || defined __aarch64__)
41 #if !defined __thumb__ || defined __thumb2__ 44 #if !defined __thumb__ || defined __thumb2__
42 #define USE_CLZ_INTRINSIC 45 #define USE_CLZ_INTRINSIC
43 #endif 46 #endif
44 #endif 47 #endif
45 48
46 #ifdef USE_CLZ_INTRINSIC 49 #ifdef USE_CLZ_INTRINSIC
47 #define JPEG_NBITS_NONZERO(x) (32 - __builtin_clz(x)) 50 #define JPEG_NBITS_NONZERO(x) (32 - __builtin_clz(x))
48 #define JPEG_NBITS(x) (x ? JPEG_NBITS_NONZERO(x) : 0) 51 #define JPEG_NBITS(x) (x ? JPEG_NBITS_NONZERO(x) : 0)
49 #else 52 #else
50 static unsigned char jpeg_nbits_table[65536]; 53 #include "jpeg_nbits_table.h"
51 static int jpeg_nbits_table_init = 0;
52 #define JPEG_NBITS(x) (jpeg_nbits_table[x]) 54 #define JPEG_NBITS(x) (jpeg_nbits_table[x])
53 #define JPEG_NBITS_NONZERO(x) JPEG_NBITS(x) 55 #define JPEG_NBITS_NONZERO(x) JPEG_NBITS(x)
54 #endif 56 #endif
55 57
56 #ifndef min 58 #ifndef min
57 #define min(a,b) ((a)<(b)?(a):(b)) 59 #define min(a,b) ((a)<(b)?(a):(b))
58 #endif 60 #endif
59 61
60 62
61 /* Expanded entropy encoder object for Huffman encoding. 63 /* Expanded entropy encoder object for Huffman encoding.
62 * 64 *
63 * The savable_state subrecord contains fields that change within an MCU, 65 * The savable_state subrecord contains fields that change within an MCU,
64 * but must not be updated permanently until we complete the MCU. 66 * but must not be updated permanently until we complete the MCU.
65 */ 67 */
66 68
67 typedef struct { 69 typedef struct {
68 size_t put_buffer;» » /* current bit-accumulation buffer */ 70 size_t put_buffer; /* current bit-accumulation buffer */
69 int put_bits;»» » /* # of bits now in it */ 71 int put_bits; /* # of bits now in it */
70 int last_dc_val[MAX_COMPS_IN_SCAN]; /* last DC coef for each component */ 72 int last_dc_val[MAX_COMPS_IN_SCAN]; /* last DC coef for each component */
71 } savable_state; 73 } savable_state;
72 74
73 /* This macro is to work around compilers with missing or broken 75 /* This macro is to work around compilers with missing or broken
74 * structure assignment. You'll need to fix this code if you have 76 * structure assignment. You'll need to fix this code if you have
75 * such a compiler and you change MAX_COMPS_IN_SCAN. 77 * such a compiler and you change MAX_COMPS_IN_SCAN.
76 */ 78 */
77 79
78 #ifndef NO_STRUCT_ASSIGN 80 #ifndef NO_STRUCT_ASSIGN
79 #define ASSIGN_STATE(dest,src) ((dest) = (src)) 81 #define ASSIGN_STATE(dest,src) ((dest) = (src))
80 #else 82 #else
81 #if MAX_COMPS_IN_SCAN == 4 83 #if MAX_COMPS_IN_SCAN == 4
82 #define ASSIGN_STATE(dest,src) \ 84 #define ASSIGN_STATE(dest,src) \
83 » ((dest).put_buffer = (src).put_buffer, \ 85 ((dest).put_buffer = (src).put_buffer, \
84 » (dest).put_bits = (src).put_bits, \ 86 (dest).put_bits = (src).put_bits, \
85 » (dest).last_dc_val[0] = (src).last_dc_val[0], \ 87 (dest).last_dc_val[0] = (src).last_dc_val[0], \
86 » (dest).last_dc_val[1] = (src).last_dc_val[1], \ 88 (dest).last_dc_val[1] = (src).last_dc_val[1], \
87 » (dest).last_dc_val[2] = (src).last_dc_val[2], \ 89 (dest).last_dc_val[2] = (src).last_dc_val[2], \
88 » (dest).last_dc_val[3] = (src).last_dc_val[3]) 90 (dest).last_dc_val[3] = (src).last_dc_val[3])
89 #endif 91 #endif
90 #endif 92 #endif
91 93
92 94
93 typedef struct { 95 typedef struct {
94 struct jpeg_entropy_encoder pub; /* public fields */ 96 struct jpeg_entropy_encoder pub; /* public fields */
95 97
96 savable_state saved;» » /* Bit buffer & DC state at start of MCU */ 98 savable_state saved; /* Bit buffer & DC state at start of MCU */
97 99
98 /* These fields are NOT loaded into local working state. */ 100 /* These fields are NOT loaded into local working state. */
99 unsigned int restarts_to_go;» /* MCUs left in this restart interval */ 101 unsigned int restarts_to_go; /* MCUs left in this restart interval */
100 int next_restart_num;»» /* next restart number to write (0-7) */ 102 int next_restart_num; /* next restart number to write (0-7) */
101 103
102 /* Pointers to derived tables (these workspaces have image lifespan) */ 104 /* Pointers to derived tables (these workspaces have image lifespan) */
103 c_derived_tbl * dc_derived_tbls[NUM_HUFF_TBLS]; 105 c_derived_tbl *dc_derived_tbls[NUM_HUFF_TBLS];
104 c_derived_tbl * ac_derived_tbls[NUM_HUFF_TBLS]; 106 c_derived_tbl *ac_derived_tbls[NUM_HUFF_TBLS];
105 107
106 #ifdef ENTROPY_OPT_SUPPORTED» /* Statistics tables for optimization */ 108 #ifdef ENTROPY_OPT_SUPPORTED /* Statistics tables for optimization */
107 long * dc_count_ptrs[NUM_HUFF_TBLS]; 109 long *dc_count_ptrs[NUM_HUFF_TBLS];
108 long * ac_count_ptrs[NUM_HUFF_TBLS]; 110 long *ac_count_ptrs[NUM_HUFF_TBLS];
109 #endif 111 #endif
112
113 int simd;
110 } huff_entropy_encoder; 114 } huff_entropy_encoder;
111 115
112 typedef huff_entropy_encoder * huff_entropy_ptr; 116 typedef huff_entropy_encoder *huff_entropy_ptr;
113 117
114 /* Working state while writing an MCU. 118 /* Working state while writing an MCU.
115 * This struct contains all the fields that are needed by subroutines. 119 * This struct contains all the fields that are needed by subroutines.
116 */ 120 */
117 121
118 typedef struct { 122 typedef struct {
119 JOCTET * next_output_byte;» /* => next byte to write in buffer */ 123 JOCTET *next_output_byte; /* => next byte to write in buffer */
120 size_t free_in_buffer;» /* # of byte spaces remaining in buffer */ 124 size_t free_in_buffer; /* # of byte spaces remaining in buffer */
121 savable_state cur;» » /* Current bit buffer & DC state */ 125 savable_state cur; /* Current bit buffer & DC state */
122 j_compress_ptr cinfo;»» /* dump_buffer needs access to this */ 126 j_compress_ptr cinfo; /* dump_buffer needs access to this */
123 } working_state; 127 } working_state;
124 128
125 129
126 /* Forward declarations */ 130 /* Forward declarations */
127 METHODDEF(boolean) encode_mcu_huff JPP((j_compress_ptr cinfo, 131 METHODDEF(boolean) encode_mcu_huff (j_compress_ptr cinfo, JBLOCKROW *MCU_data);
128 » » » » » JBLOCKROW *MCU_data)); 132 METHODDEF(void) finish_pass_huff (j_compress_ptr cinfo);
129 METHODDEF(void) finish_pass_huff JPP((j_compress_ptr cinfo));
130 #ifdef ENTROPY_OPT_SUPPORTED 133 #ifdef ENTROPY_OPT_SUPPORTED
131 METHODDEF(boolean) encode_mcu_gather JPP((j_compress_ptr cinfo, 134 METHODDEF(boolean) encode_mcu_gather (j_compress_ptr cinfo,
132 » » » » » JBLOCKROW *MCU_data)); 135 JBLOCKROW *MCU_data);
133 METHODDEF(void) finish_pass_gather JPP((j_compress_ptr cinfo)); 136 METHODDEF(void) finish_pass_gather (j_compress_ptr cinfo);
134 #endif 137 #endif
135 138
136 139
137 /* 140 /*
138 * Initialize for a Huffman-compressed scan. 141 * Initialize for a Huffman-compressed scan.
139 * If gather_statistics is TRUE, we do not output anything during the scan, 142 * If gather_statistics is TRUE, we do not output anything during the scan,
140 * just count the Huffman symbols used and generate Huffman code tables. 143 * just count the Huffman symbols used and generate Huffman code tables.
141 */ 144 */
142 145
143 METHODDEF(void) 146 METHODDEF(void)
144 start_pass_huff (j_compress_ptr cinfo, boolean gather_statistics) 147 start_pass_huff (j_compress_ptr cinfo, boolean gather_statistics)
145 { 148 {
146 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy; 149 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
147 int ci, dctbl, actbl; 150 int ci, dctbl, actbl;
148 jpeg_component_info * compptr; 151 jpeg_component_info *compptr;
149 152
150 if (gather_statistics) { 153 if (gather_statistics) {
151 #ifdef ENTROPY_OPT_SUPPORTED 154 #ifdef ENTROPY_OPT_SUPPORTED
152 entropy->pub.encode_mcu = encode_mcu_gather; 155 entropy->pub.encode_mcu = encode_mcu_gather;
153 entropy->pub.finish_pass = finish_pass_gather; 156 entropy->pub.finish_pass = finish_pass_gather;
154 #else 157 #else
155 ERREXIT(cinfo, JERR_NOT_COMPILED); 158 ERREXIT(cinfo, JERR_NOT_COMPILED);
156 #endif 159 #endif
157 } else { 160 } else {
158 entropy->pub.encode_mcu = encode_mcu_huff; 161 entropy->pub.encode_mcu = encode_mcu_huff;
159 entropy->pub.finish_pass = finish_pass_huff; 162 entropy->pub.finish_pass = finish_pass_huff;
160 } 163 }
161 164
165 entropy->simd = jsimd_can_huff_encode_one_block();
166
162 for (ci = 0; ci < cinfo->comps_in_scan; ci++) { 167 for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
163 compptr = cinfo->cur_comp_info[ci]; 168 compptr = cinfo->cur_comp_info[ci];
164 dctbl = compptr->dc_tbl_no; 169 dctbl = compptr->dc_tbl_no;
165 actbl = compptr->ac_tbl_no; 170 actbl = compptr->ac_tbl_no;
166 if (gather_statistics) { 171 if (gather_statistics) {
167 #ifdef ENTROPY_OPT_SUPPORTED 172 #ifdef ENTROPY_OPT_SUPPORTED
168 /* Check for invalid table indexes */ 173 /* Check for invalid table indexes */
169 /* (make_c_derived_tbl does this in the other path) */ 174 /* (make_c_derived_tbl does this in the other path) */
170 if (dctbl < 0 || dctbl >= NUM_HUFF_TBLS) 175 if (dctbl < 0 || dctbl >= NUM_HUFF_TBLS)
171 » ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, dctbl); 176 ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, dctbl);
172 if (actbl < 0 || actbl >= NUM_HUFF_TBLS) 177 if (actbl < 0 || actbl >= NUM_HUFF_TBLS)
173 » ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, actbl); 178 ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, actbl);
174 /* Allocate and zero the statistics tables */ 179 /* Allocate and zero the statistics tables */
175 /* Note that jpeg_gen_optimal_table expects 257 entries in each table! */ 180 /* Note that jpeg_gen_optimal_table expects 257 entries in each table! */
176 if (entropy->dc_count_ptrs[dctbl] == NULL) 181 if (entropy->dc_count_ptrs[dctbl] == NULL)
177 » entropy->dc_count_ptrs[dctbl] = (long *) 182 entropy->dc_count_ptrs[dctbl] = (long *)
178 » (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE, 183 (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
179 » » » » 257 * SIZEOF(long)); 184 257 * sizeof(long));
180 MEMZERO(entropy->dc_count_ptrs[dctbl], 257 * SIZEOF(long)); 185 MEMZERO(entropy->dc_count_ptrs[dctbl], 257 * sizeof(long));
181 if (entropy->ac_count_ptrs[actbl] == NULL) 186 if (entropy->ac_count_ptrs[actbl] == NULL)
182 » entropy->ac_count_ptrs[actbl] = (long *) 187 entropy->ac_count_ptrs[actbl] = (long *)
183 » (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE, 188 (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
184 » » » » 257 * SIZEOF(long)); 189 257 * sizeof(long));
185 MEMZERO(entropy->ac_count_ptrs[actbl], 257 * SIZEOF(long)); 190 MEMZERO(entropy->ac_count_ptrs[actbl], 257 * sizeof(long));
186 #endif 191 #endif
187 } else { 192 } else {
188 /* Compute derived values for Huffman tables */ 193 /* Compute derived values for Huffman tables */
189 /* We may do this more than once for a table, but it's not expensive */ 194 /* We may do this more than once for a table, but it's not expensive */
190 jpeg_make_c_derived_tbl(cinfo, TRUE, dctbl, 195 jpeg_make_c_derived_tbl(cinfo, TRUE, dctbl,
191 » » » & entropy->dc_derived_tbls[dctbl]); 196 & entropy->dc_derived_tbls[dctbl]);
192 jpeg_make_c_derived_tbl(cinfo, FALSE, actbl, 197 jpeg_make_c_derived_tbl(cinfo, FALSE, actbl,
193 » » » & entropy->ac_derived_tbls[actbl]); 198 & entropy->ac_derived_tbls[actbl]);
194 } 199 }
195 /* Initialize DC predictions to 0 */ 200 /* Initialize DC predictions to 0 */
196 entropy->saved.last_dc_val[ci] = 0; 201 entropy->saved.last_dc_val[ci] = 0;
197 } 202 }
198 203
199 /* Initialize bit buffer to empty */ 204 /* Initialize bit buffer to empty */
200 entropy->saved.put_buffer = 0; 205 entropy->saved.put_buffer = 0;
201 entropy->saved.put_bits = 0; 206 entropy->saved.put_bits = 0;
202 207
203 /* Initialize restart stuff */ 208 /* Initialize restart stuff */
204 entropy->restarts_to_go = cinfo->restart_interval; 209 entropy->restarts_to_go = cinfo->restart_interval;
205 entropy->next_restart_num = 0; 210 entropy->next_restart_num = 0;
206 } 211 }
207 212
208 213
209 /* 214 /*
210 * Compute the derived values for a Huffman table. 215 * Compute the derived values for a Huffman table.
211 * This routine also performs some validation checks on the table. 216 * This routine also performs some validation checks on the table.
212 * 217 *
213 * Note this is also used by jcphuff.c. 218 * Note this is also used by jcphuff.c.
214 */ 219 */
215 220
216 GLOBAL(void) 221 GLOBAL(void)
217 jpeg_make_c_derived_tbl (j_compress_ptr cinfo, boolean isDC, int tblno, 222 jpeg_make_c_derived_tbl (j_compress_ptr cinfo, boolean isDC, int tblno,
218 » » » c_derived_tbl ** pdtbl) 223 c_derived_tbl **pdtbl)
219 { 224 {
220 JHUFF_TBL *htbl; 225 JHUFF_TBL *htbl;
221 c_derived_tbl *dtbl; 226 c_derived_tbl *dtbl;
222 int p, i, l, lastp, si, maxsymbol; 227 int p, i, l, lastp, si, maxsymbol;
223 char huffsize[257]; 228 char huffsize[257];
224 unsigned int huffcode[257]; 229 unsigned int huffcode[257];
225 unsigned int code; 230 unsigned int code;
226 231
227 /* Note that huffsize[] and huffcode[] are filled in code-length order, 232 /* Note that huffsize[] and huffcode[] are filled in code-length order,
228 * paralleling the order of the symbols themselves in htbl->huffval[]. 233 * paralleling the order of the symbols themselves in htbl->huffval[].
229 */ 234 */
230 235
231 /* Find the input Huffman table */ 236 /* Find the input Huffman table */
232 if (tblno < 0 || tblno >= NUM_HUFF_TBLS) 237 if (tblno < 0 || tblno >= NUM_HUFF_TBLS)
233 ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tblno); 238 ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tblno);
234 htbl = 239 htbl =
235 isDC ? cinfo->dc_huff_tbl_ptrs[tblno] : cinfo->ac_huff_tbl_ptrs[tblno]; 240 isDC ? cinfo->dc_huff_tbl_ptrs[tblno] : cinfo->ac_huff_tbl_ptrs[tblno];
236 if (htbl == NULL) 241 if (htbl == NULL)
237 ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tblno); 242 ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tblno);
238 243
239 /* Allocate a workspace if we haven't already done so. */ 244 /* Allocate a workspace if we haven't already done so. */
240 if (*pdtbl == NULL) 245 if (*pdtbl == NULL)
241 *pdtbl = (c_derived_tbl *) 246 *pdtbl = (c_derived_tbl *)
242 (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE, 247 (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
243 » » » » SIZEOF(c_derived_tbl)); 248 sizeof(c_derived_tbl));
244 dtbl = *pdtbl; 249 dtbl = *pdtbl;
245 250
246 /* Figure C.1: make table of Huffman code length for each symbol */ 251 /* Figure C.1: make table of Huffman code length for each symbol */
247 252
248 p = 0; 253 p = 0;
249 for (l = 1; l <= 16; l++) { 254 for (l = 1; l <= 16; l++) {
250 i = (int) htbl->bits[l]; 255 i = (int) htbl->bits[l];
251 if (i < 0 || p + i > 256)» /* protect against table overrun */ 256 if (i < 0 || p + i > 256) /* protect against table overrun */
252 ERREXIT(cinfo, JERR_BAD_HUFF_TABLE); 257 ERREXIT(cinfo, JERR_BAD_HUFF_TABLE);
253 while (i--) 258 while (i--)
254 huffsize[p++] = (char) l; 259 huffsize[p++] = (char) l;
255 } 260 }
256 huffsize[p] = 0; 261 huffsize[p] = 0;
257 lastp = p; 262 lastp = p;
258 263
259 /* Figure C.2: generate the codes themselves */ 264 /* Figure C.2: generate the codes themselves */
260 /* We also validate that the counts represent a legal Huffman code tree. */ 265 /* We also validate that the counts represent a legal Huffman code tree. */
261 266
262 code = 0; 267 code = 0;
263 si = huffsize[0]; 268 si = huffsize[0];
264 p = 0; 269 p = 0;
265 while (huffsize[p]) { 270 while (huffsize[p]) {
266 while (((int) huffsize[p]) == si) { 271 while (((int) huffsize[p]) == si) {
267 huffcode[p++] = code; 272 huffcode[p++] = code;
268 code++; 273 code++;
269 } 274 }
270 /* code is now 1 more than the last code used for codelength si; but 275 /* code is now 1 more than the last code used for codelength si; but
271 * it must still fit in si bits, since no code is allowed to be all ones. 276 * it must still fit in si bits, since no code is allowed to be all ones.
272 */ 277 */
273 if (((INT32) code) >= (((INT32) 1) << si)) 278 if (((JLONG) code) >= (((JLONG) 1) << si))
274 ERREXIT(cinfo, JERR_BAD_HUFF_TABLE); 279 ERREXIT(cinfo, JERR_BAD_HUFF_TABLE);
275 code <<= 1; 280 code <<= 1;
276 si++; 281 si++;
277 } 282 }
278 283
279 /* Figure C.3: generate encoding tables */ 284 /* Figure C.3: generate encoding tables */
280 /* These are code and size indexed by symbol value */ 285 /* These are code and size indexed by symbol value */
281 286
282 /* Set all codeless symbols to have code length 0; 287 /* Set all codeless symbols to have code length 0;
283 * this lets us detect duplicate VAL entries here, and later 288 * this lets us detect duplicate VAL entries here, and later
284 * allows emit_bits to detect any attempt to emit such symbols. 289 * allows emit_bits to detect any attempt to emit such symbols.
285 */ 290 */
286 MEMZERO(dtbl->ehufsi, SIZEOF(dtbl->ehufsi)); 291 MEMZERO(dtbl->ehufsi, sizeof(dtbl->ehufsi));
287 292
288 /* This is also a convenient place to check for out-of-range 293 /* This is also a convenient place to check for out-of-range
289 * and duplicated VAL entries. We allow 0..255 for AC symbols 294 * and duplicated VAL entries. We allow 0..255 for AC symbols
290 * but only 0..15 for DC. (We could constrain them further 295 * but only 0..15 for DC. (We could constrain them further
291 * based on data depth and mode, but this seems enough.) 296 * based on data depth and mode, but this seems enough.)
292 */ 297 */
293 maxsymbol = isDC ? 15 : 255; 298 maxsymbol = isDC ? 15 : 255;
294 299
295 for (p = 0; p < lastp; p++) { 300 for (p = 0; p < lastp; p++) {
296 i = htbl->huffval[p]; 301 i = htbl->huffval[p];
297 if (i < 0 || i > maxsymbol || dtbl->ehufsi[i]) 302 if (i < 0 || i > maxsymbol || dtbl->ehufsi[i])
298 ERREXIT(cinfo, JERR_BAD_HUFF_TABLE); 303 ERREXIT(cinfo, JERR_BAD_HUFF_TABLE);
299 dtbl->ehufco[i] = huffcode[p]; 304 dtbl->ehufco[i] = huffcode[p];
300 dtbl->ehufsi[i] = huffsize[p]; 305 dtbl->ehufsi[i] = huffsize[p];
301 } 306 }
302
303 #ifndef USE_CLZ_INTRINSIC
304 if(!jpeg_nbits_table_init) {
305 for(i = 0; i < 65536; i++) {
306 int nbits = 0, temp = i;
307 while (temp) {temp >>= 1; nbits++;}
308 jpeg_nbits_table[i] = nbits;
309 }
310 jpeg_nbits_table_init = 1;
311 }
312 #endif
313 } 307 }
314 308
315 309
316 /* Outputting bytes to the file */ 310 /* Outputting bytes to the file */
317 311
318 /* Emit a byte, taking 'action' if must suspend. */ 312 /* Emit a byte, taking 'action' if must suspend. */
319 #define emit_byte(state,val,action) \ 313 #define emit_byte(state,val,action) \
320 » { *(state)->next_output_byte++ = (JOCTET) (val); \ 314 { *(state)->next_output_byte++ = (JOCTET) (val); \
321 » if (--(state)->free_in_buffer == 0) \ 315 if (--(state)->free_in_buffer == 0) \
322 » if (! dump_buffer(state)) \ 316 if (! dump_buffer(state)) \
323 » { action; } } 317 { action; } }
324 318
325 319
326 LOCAL(boolean) 320 LOCAL(boolean)
327 dump_buffer (working_state * state) 321 dump_buffer (working_state *state)
328 /* Empty the output buffer; return TRUE if successful, FALSE if must suspend */ 322 /* Empty the output buffer; return TRUE if successful, FALSE if must suspend */
329 { 323 {
330 struct jpeg_destination_mgr * dest = state->cinfo->dest; 324 struct jpeg_destination_mgr *dest = state->cinfo->dest;
331 325
332 if (! (*dest->empty_output_buffer) (state->cinfo)) 326 if (! (*dest->empty_output_buffer) (state->cinfo))
333 return FALSE; 327 return FALSE;
334 /* After a successful buffer dump, must reset buffer pointers */ 328 /* After a successful buffer dump, must reset buffer pointers */
335 state->next_output_byte = dest->next_output_byte; 329 state->next_output_byte = dest->next_output_byte;
336 state->free_in_buffer = dest->free_in_buffer; 330 state->free_in_buffer = dest->free_in_buffer;
337 return TRUE; 331 return TRUE;
338 } 332 }
339 333
340 334
(...skipping 41 matching lines...) Expand 10 before | Expand all | Expand 10 after
382 if (put_bits > 47) { \ 376 if (put_bits > 47) { \
383 EMIT_BYTE() \ 377 EMIT_BYTE() \
384 EMIT_BYTE() \ 378 EMIT_BYTE() \
385 EMIT_BYTE() \ 379 EMIT_BYTE() \
386 EMIT_BYTE() \ 380 EMIT_BYTE() \
387 EMIT_BYTE() \ 381 EMIT_BYTE() \
388 EMIT_BYTE() \ 382 EMIT_BYTE() \
389 } \ 383 } \
390 } 384 }
391 385
392 #if __WORDSIZE==64 || defined(_WIN64) 386 #if !defined(_WIN32) && !defined(SIZEOF_SIZE_T)
387 #error Cannot determine word size
388 #endif
389
390 #if SIZEOF_SIZE_T==8 || defined(_WIN64)
393 391
394 #define EMIT_BITS(code, size) { \ 392 #define EMIT_BITS(code, size) { \
395 CHECKBUF47() \ 393 CHECKBUF47() \
396 PUT_BITS(code, size) \ 394 PUT_BITS(code, size) \
397 } 395 }
398 396
399 #define EMIT_CODE(code, size) { \ 397 #define EMIT_CODE(code, size) { \
400 temp2 &= (((INT32) 1)<<nbits) - 1; \ 398 temp2 &= (((JLONG) 1)<<nbits) - 1; \
401 CHECKBUF31() \ 399 CHECKBUF31() \
402 PUT_BITS(code, size) \ 400 PUT_BITS(code, size) \
403 PUT_BITS(temp2, nbits) \ 401 PUT_BITS(temp2, nbits) \
404 } 402 }
405 403
406 #else 404 #else
407 405
408 #define EMIT_BITS(code, size) { \ 406 #define EMIT_BITS(code, size) { \
409 PUT_BITS(code, size) \ 407 PUT_BITS(code, size) \
410 CHECKBUF15() \ 408 CHECKBUF15() \
411 } 409 }
412 410
413 #define EMIT_CODE(code, size) { \ 411 #define EMIT_CODE(code, size) { \
414 temp2 &= (((INT32) 1)<<nbits) - 1; \ 412 temp2 &= (((JLONG) 1)<<nbits) - 1; \
415 PUT_BITS(code, size) \ 413 PUT_BITS(code, size) \
416 CHECKBUF15() \ 414 CHECKBUF15() \
417 PUT_BITS(temp2, nbits) \ 415 PUT_BITS(temp2, nbits) \
418 CHECKBUF15() \ 416 CHECKBUF15() \
419 } 417 }
420 418
421 #endif 419 #endif
422 420
423 421
424 #define BUFSIZE (DCTSIZE2 * 2) 422 /* Although it is exceedingly rare, it is possible for a Huffman-encoded
423 * coefficient block to be larger than the 128-byte unencoded block. For each
424 * of the 64 coefficients, PUT_BITS is invoked twice, and each invocation can
425 * theoretically store 16 bits (for a maximum of 2048 bits or 256 bytes per
426 * encoded block.) If, for instance, one artificially sets the AC
427 * coefficients to alternating values of 32767 and -32768 (using the JPEG
428 * scanning order-- 1, 8, 16, etc.), then this will produce an encoded block
429 * larger than 200 bytes.
430 */
431 #define BUFSIZE (DCTSIZE2 * 4)
425 432
426 #define LOAD_BUFFER() { \ 433 #define LOAD_BUFFER() { \
427 if (state->free_in_buffer < BUFSIZE) { \ 434 if (state->free_in_buffer < BUFSIZE) { \
428 localbuf = 1; \ 435 localbuf = 1; \
429 buffer = _buffer; \ 436 buffer = _buffer; \
430 } \ 437 } \
431 else buffer = state->next_output_byte; \ 438 else buffer = state->next_output_byte; \
432 } 439 }
433 440
434 #define STORE_BUFFER() { \ 441 #define STORE_BUFFER() { \
(...skipping 12 matching lines...) Expand all
447 } \ 454 } \
448 } \ 455 } \
449 else { \ 456 else { \
450 state->free_in_buffer -= (buffer - state->next_output_byte); \ 457 state->free_in_buffer -= (buffer - state->next_output_byte); \
451 state->next_output_byte = buffer; \ 458 state->next_output_byte = buffer; \
452 } \ 459 } \
453 } 460 }
454 461
455 462
456 LOCAL(boolean) 463 LOCAL(boolean)
457 flush_bits (working_state * state) 464 flush_bits (working_state *state)
458 { 465 {
459 JOCTET _buffer[BUFSIZE], *buffer; 466 JOCTET _buffer[BUFSIZE], *buffer;
460 size_t put_buffer; int put_bits; 467 size_t put_buffer; int put_bits;
461 size_t bytes, bytestocopy; int localbuf = 0; 468 size_t bytes, bytestocopy; int localbuf = 0;
462 469
463 put_buffer = state->cur.put_buffer; 470 put_buffer = state->cur.put_buffer;
464 put_bits = state->cur.put_bits; 471 put_bits = state->cur.put_bits;
465 LOAD_BUFFER() 472 LOAD_BUFFER()
466 473
467 /* fill any partial byte with ones */ 474 /* fill any partial byte with ones */
468 PUT_BITS(0x7F, 7) 475 PUT_BITS(0x7F, 7)
469 while (put_bits >= 8) EMIT_BYTE() 476 while (put_bits >= 8) EMIT_BYTE()
470 477
471 state->cur.put_buffer = 0;» /* and reset bit-buffer to empty */ 478 state->cur.put_buffer = 0; /* and reset bit-buffer to empty */
472 state->cur.put_bits = 0; 479 state->cur.put_bits = 0;
473 STORE_BUFFER() 480 STORE_BUFFER()
474 481
475 return TRUE; 482 return TRUE;
476 } 483 }
477 484
478 485
479 /* Encode a single block's worth of coefficients */ 486 /* Encode a single block's worth of coefficients */
480 487
481 LOCAL(boolean) 488 LOCAL(boolean)
482 encode_one_block (working_state * state, JCOEFPTR block, int last_dc_val, 489 encode_one_block_simd (working_state *state, JCOEFPTR block, int last_dc_val,
483 » » c_derived_tbl *dctbl, c_derived_tbl *actbl) 490 c_derived_tbl *dctbl, c_derived_tbl *actbl)
491 {
492 JOCTET _buffer[BUFSIZE], *buffer;
493 size_t bytes, bytestocopy; int localbuf = 0;
494
495 LOAD_BUFFER()
496
497 buffer = jsimd_huff_encode_one_block(state, buffer, block, last_dc_val,
498 dctbl, actbl);
499
500 STORE_BUFFER()
501
502 return TRUE;
503 }
504
505 LOCAL(boolean)
506 encode_one_block (working_state *state, JCOEFPTR block, int last_dc_val,
507 c_derived_tbl *dctbl, c_derived_tbl *actbl)
484 { 508 {
485 int temp, temp2, temp3; 509 int temp, temp2, temp3;
486 int nbits; 510 int nbits;
487 int r, code, size; 511 int r, code, size;
488 JOCTET _buffer[BUFSIZE], *buffer; 512 JOCTET _buffer[BUFSIZE], *buffer;
489 size_t put_buffer; int put_bits; 513 size_t put_buffer; int put_bits;
490 int code_0xf0 = actbl->ehufco[0xf0], size_0xf0 = actbl->ehufsi[0xf0]; 514 int code_0xf0 = actbl->ehufco[0xf0], size_0xf0 = actbl->ehufsi[0xf0];
491 size_t bytes, bytestocopy; int localbuf = 0; 515 size_t bytes, bytestocopy; int localbuf = 0;
492 516
493 put_buffer = state->cur.put_buffer; 517 put_buffer = state->cur.put_buffer;
494 put_bits = state->cur.put_bits; 518 put_bits = state->cur.put_bits;
495 LOAD_BUFFER() 519 LOAD_BUFFER()
496 520
497 /* Encode the DC coefficient difference per section F.1.2.1 */ 521 /* Encode the DC coefficient difference per section F.1.2.1 */
498 522
499 temp = temp2 = block[0] - last_dc_val; 523 temp = temp2 = block[0] - last_dc_val;
500 524
501 /* This is a well-known technique for obtaining the absolute value without a 525 /* This is a well-known technique for obtaining the absolute value without a
502 * branch. It is derived from an assembly language technique presented in 526 * branch. It is derived from an assembly language technique presented in
503 * "How to Optimize for the Pentium Processors", Copyright (c) 1996, 1997 by 527 * "How to Optimize for the Pentium Processors", Copyright (c) 1996, 1997 by
504 * Agner Fog. 528 * Agner Fog.
505 */ 529 */
506 temp3 = temp >> (CHAR_BIT * sizeof(int) - 1); 530 temp3 = temp >> (CHAR_BIT * sizeof(int) - 1);
507 temp ^= temp3; 531 temp ^= temp3;
508 temp -= temp3; 532 temp -= temp3;
509 533
510 /* For a negative input, want temp2 = bitwise complement of abs(input) */ 534 /* For a negative input, want temp2 = bitwise complement of abs(input) */
511 /* This code assumes we are on a two's complement machine */ 535 /* This code assumes we are on a two's complement machine */
512 temp2 += temp3; 536 temp2 += temp3;
513 537
514 /* Find the number of bits needed for the magnitude of the coefficient */ 538 /* Find the number of bits needed for the magnitude of the coefficient */
515 nbits = JPEG_NBITS(temp); 539 nbits = JPEG_NBITS(temp);
516 540
517 /* Emit the Huffman-coded symbol for the number of bits */ 541 /* Emit the Huffman-coded symbol for the number of bits */
518 code = dctbl->ehufco[nbits]; 542 code = dctbl->ehufco[nbits];
519 size = dctbl->ehufsi[nbits]; 543 size = dctbl->ehufsi[nbits];
520 PUT_BITS(code, size) 544 EMIT_BITS(code, size)
521 CHECKBUF15()
522 545
523 /* Mask off any extra bits in code */ 546 /* Mask off any extra bits in code */
524 temp2 &= (((INT32) 1)<<nbits) - 1; 547 temp2 &= (((JLONG) 1)<<nbits) - 1;
525 548
526 /* Emit that number of bits of the value, if positive, */ 549 /* Emit that number of bits of the value, if positive, */
527 /* or the complement of its magnitude, if negative. */ 550 /* or the complement of its magnitude, if negative. */
528 PUT_BITS(temp2, nbits) 551 EMIT_BITS(temp2, nbits)
529 CHECKBUF15()
530 552
531 /* Encode the AC coefficients per section F.1.2.2 */ 553 /* Encode the AC coefficients per section F.1.2.2 */
532 554
533 r = 0;» » » /* r = run length of zeros */ 555 r = 0; /* r = run length of zeros */
534 556
535 /* Manually unroll the k loop to eliminate the counter variable. This 557 /* Manually unroll the k loop to eliminate the counter variable. This
536 * improves performance greatly on systems with a limited number of 558 * improves performance greatly on systems with a limited number of
537 * registers (such as x86.) 559 * registers (such as x86.)
538 */ 560 */
539 #define kloop(jpeg_natural_order_of_k) { \ 561 #define kloop(jpeg_natural_order_of_k) { \
540 if ((temp = block[jpeg_natural_order_of_k]) == 0) { \ 562 if ((temp = block[jpeg_natural_order_of_k]) == 0) { \
541 r++; \ 563 r++; \
542 } else { \ 564 } else { \
543 temp2 = temp; \ 565 temp2 = temp; \
(...skipping 43 matching lines...) Expand 10 before | Expand all | Expand 10 after
587 609
588 return TRUE; 610 return TRUE;
589 } 611 }
590 612
591 613
592 /* 614 /*
593 * Emit a restart marker & resynchronize predictions. 615 * Emit a restart marker & resynchronize predictions.
594 */ 616 */
595 617
596 LOCAL(boolean) 618 LOCAL(boolean)
597 emit_restart (working_state * state, int restart_num) 619 emit_restart (working_state *state, int restart_num)
598 { 620 {
599 int ci; 621 int ci;
600 622
601 if (! flush_bits(state)) 623 if (! flush_bits(state))
602 return FALSE; 624 return FALSE;
603 625
604 emit_byte(state, 0xFF, return FALSE); 626 emit_byte(state, 0xFF, return FALSE);
605 emit_byte(state, JPEG_RST0 + restart_num, return FALSE); 627 emit_byte(state, JPEG_RST0 + restart_num, return FALSE);
606 628
607 /* Re-initialize DC predictions to 0 */ 629 /* Re-initialize DC predictions to 0 */
608 for (ci = 0; ci < state->cinfo->comps_in_scan; ci++) 630 for (ci = 0; ci < state->cinfo->comps_in_scan; ci++)
609 state->cur.last_dc_val[ci] = 0; 631 state->cur.last_dc_val[ci] = 0;
610 632
611 /* The restart counter is not updated until we successfully write the MCU. */ 633 /* The restart counter is not updated until we successfully write the MCU. */
612 634
613 return TRUE; 635 return TRUE;
614 } 636 }
615 637
616 638
617 /* 639 /*
618 * Encode and output one MCU's worth of Huffman-compressed coefficients. 640 * Encode and output one MCU's worth of Huffman-compressed coefficients.
619 */ 641 */
620 642
621 METHODDEF(boolean) 643 METHODDEF(boolean)
622 encode_mcu_huff (j_compress_ptr cinfo, JBLOCKROW *MCU_data) 644 encode_mcu_huff (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
623 { 645 {
624 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy; 646 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
625 working_state state; 647 working_state state;
626 int blkn, ci; 648 int blkn, ci;
627 jpeg_component_info * compptr; 649 jpeg_component_info *compptr;
628 650
629 /* Load up working state */ 651 /* Load up working state */
630 state.next_output_byte = cinfo->dest->next_output_byte; 652 state.next_output_byte = cinfo->dest->next_output_byte;
631 state.free_in_buffer = cinfo->dest->free_in_buffer; 653 state.free_in_buffer = cinfo->dest->free_in_buffer;
632 ASSIGN_STATE(state.cur, entropy->saved); 654 ASSIGN_STATE(state.cur, entropy->saved);
633 state.cinfo = cinfo; 655 state.cinfo = cinfo;
634 656
635 /* Emit restart marker if needed */ 657 /* Emit restart marker if needed */
636 if (cinfo->restart_interval) { 658 if (cinfo->restart_interval) {
637 if (entropy->restarts_to_go == 0) 659 if (entropy->restarts_to_go == 0)
638 if (! emit_restart(&state, entropy->next_restart_num)) 660 if (! emit_restart(&state, entropy->next_restart_num))
639 » return FALSE; 661 return FALSE;
640 } 662 }
641 663
642 /* Encode the MCU data blocks */ 664 /* Encode the MCU data blocks */
643 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) { 665 if (entropy->simd) {
644 ci = cinfo->MCU_membership[blkn]; 666 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
645 compptr = cinfo->cur_comp_info[ci]; 667 ci = cinfo->MCU_membership[blkn];
646 if (! encode_one_block(&state, 668 compptr = cinfo->cur_comp_info[ci];
647 » » » MCU_data[blkn][0], state.cur.last_dc_val[ci], 669 if (! encode_one_block_simd(&state,
648 » » » entropy->dc_derived_tbls[compptr->dc_tbl_no], 670 MCU_data[blkn][0], state.cur.last_dc_val[ci],
649 » » » entropy->ac_derived_tbls[compptr->ac_tbl_no])) 671 entropy->dc_derived_tbls[compptr->dc_tbl_no],
650 return FALSE; 672 entropy->ac_derived_tbls[compptr->ac_tbl_no]))
651 /* Update last_dc_val */ 673 return FALSE;
652 state.cur.last_dc_val[ci] = MCU_data[blkn][0][0]; 674 /* Update last_dc_val */
675 state.cur.last_dc_val[ci] = MCU_data[blkn][0][0];
676 }
677 } else {
678 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
679 ci = cinfo->MCU_membership[blkn];
680 compptr = cinfo->cur_comp_info[ci];
681 if (! encode_one_block(&state,
682 MCU_data[blkn][0], state.cur.last_dc_val[ci],
683 entropy->dc_derived_tbls[compptr->dc_tbl_no],
684 entropy->ac_derived_tbls[compptr->ac_tbl_no]))
685 return FALSE;
686 /* Update last_dc_val */
687 state.cur.last_dc_val[ci] = MCU_data[blkn][0][0];
688 }
653 } 689 }
654 690
655 /* Completed MCU, so update state */ 691 /* Completed MCU, so update state */
656 cinfo->dest->next_output_byte = state.next_output_byte; 692 cinfo->dest->next_output_byte = state.next_output_byte;
657 cinfo->dest->free_in_buffer = state.free_in_buffer; 693 cinfo->dest->free_in_buffer = state.free_in_buffer;
658 ASSIGN_STATE(entropy->saved, state.cur); 694 ASSIGN_STATE(entropy->saved, state.cur);
659 695
660 /* Update restart-interval state too */ 696 /* Update restart-interval state too */
661 if (cinfo->restart_interval) { 697 if (cinfo->restart_interval) {
662 if (entropy->restarts_to_go == 0) { 698 if (entropy->restarts_to_go == 0) {
(...skipping 46 matching lines...) Expand 10 before | Expand all | Expand 10 after
709 * the compressed data. 745 * the compressed data.
710 */ 746 */
711 747
712 #ifdef ENTROPY_OPT_SUPPORTED 748 #ifdef ENTROPY_OPT_SUPPORTED
713 749
714 750
715 /* Process a single block's worth of coefficients */ 751 /* Process a single block's worth of coefficients */
716 752
717 LOCAL(void) 753 LOCAL(void)
718 htest_one_block (j_compress_ptr cinfo, JCOEFPTR block, int last_dc_val, 754 htest_one_block (j_compress_ptr cinfo, JCOEFPTR block, int last_dc_val,
719 » » long dc_counts[], long ac_counts[]) 755 long dc_counts[], long ac_counts[])
720 { 756 {
721 register int temp; 757 register int temp;
722 register int nbits; 758 register int nbits;
723 register int k, r; 759 register int k, r;
724 760
725 /* Encode the DC coefficient difference per section F.1.2.1 */ 761 /* Encode the DC coefficient difference per section F.1.2.1 */
726 762
727 temp = block[0] - last_dc_val; 763 temp = block[0] - last_dc_val;
728 if (temp < 0) 764 if (temp < 0)
729 temp = -temp; 765 temp = -temp;
730 766
731 /* Find the number of bits needed for the magnitude of the coefficient */ 767 /* Find the number of bits needed for the magnitude of the coefficient */
732 nbits = 0; 768 nbits = 0;
733 while (temp) { 769 while (temp) {
734 nbits++; 770 nbits++;
735 temp >>= 1; 771 temp >>= 1;
736 } 772 }
737 /* Check for out-of-range coefficient values. 773 /* Check for out-of-range coefficient values.
738 * Since we're encoding a difference, the range limit is twice as much. 774 * Since we're encoding a difference, the range limit is twice as much.
739 */ 775 */
740 if (nbits > MAX_COEF_BITS+1) 776 if (nbits > MAX_COEF_BITS+1)
741 ERREXIT(cinfo, JERR_BAD_DCT_COEF); 777 ERREXIT(cinfo, JERR_BAD_DCT_COEF);
742 778
743 /* Count the Huffman symbol for the number of bits */ 779 /* Count the Huffman symbol for the number of bits */
744 dc_counts[nbits]++; 780 dc_counts[nbits]++;
745 781
746 /* Encode the AC coefficients per section F.1.2.2 */ 782 /* Encode the AC coefficients per section F.1.2.2 */
747 783
748 r = 0;» » » /* r = run length of zeros */ 784 r = 0; /* r = run length of zeros */
749 785
750 for (k = 1; k < DCTSIZE2; k++) { 786 for (k = 1; k < DCTSIZE2; k++) {
751 if ((temp = block[jpeg_natural_order[k]]) == 0) { 787 if ((temp = block[jpeg_natural_order[k]]) == 0) {
752 r++; 788 r++;
753 } else { 789 } else {
754 /* if run length > 15, must emit special run-length-16 codes (0xF0) */ 790 /* if run length > 15, must emit special run-length-16 codes (0xF0) */
755 while (r > 15) { 791 while (r > 15) {
756 » ac_counts[0xF0]++; 792 ac_counts[0xF0]++;
757 » r -= 16; 793 r -= 16;
758 } 794 }
759 795
760 /* Find the number of bits needed for the magnitude of the coefficient */ 796 /* Find the number of bits needed for the magnitude of the coefficient */
761 if (temp < 0) 797 if (temp < 0)
762 » temp = -temp; 798 temp = -temp;
763 799
764 /* Find the number of bits needed for the magnitude of the coefficient */ 800 /* Find the number of bits needed for the magnitude of the coefficient */
765 nbits = 1;» » /* there must be at least one 1 bit */ 801 nbits = 1; /* there must be at least one 1 bit */
766 while ((temp >>= 1)) 802 while ((temp >>= 1))
767 » nbits++; 803 nbits++;
768 /* Check for out-of-range coefficient values */ 804 /* Check for out-of-range coefficient values */
769 if (nbits > MAX_COEF_BITS) 805 if (nbits > MAX_COEF_BITS)
770 » ERREXIT(cinfo, JERR_BAD_DCT_COEF); 806 ERREXIT(cinfo, JERR_BAD_DCT_COEF);
771 807
772 /* Count Huffman symbol for run length / number of bits */ 808 /* Count Huffman symbol for run length / number of bits */
773 ac_counts[(r << 4) + nbits]++; 809 ac_counts[(r << 4) + nbits]++;
774 810
775 r = 0; 811 r = 0;
776 } 812 }
777 } 813 }
778 814
779 /* If the last coef(s) were zero, emit an end-of-block code */ 815 /* If the last coef(s) were zero, emit an end-of-block code */
780 if (r > 0) 816 if (r > 0)
781 ac_counts[0]++; 817 ac_counts[0]++;
782 } 818 }
783 819
784 820
785 /* 821 /*
786 * Trial-encode one MCU's worth of Huffman-compressed coefficients. 822 * Trial-encode one MCU's worth of Huffman-compressed coefficients.
787 * No data is actually output, so no suspension return is possible. 823 * No data is actually output, so no suspension return is possible.
788 */ 824 */
789 825
790 METHODDEF(boolean) 826 METHODDEF(boolean)
791 encode_mcu_gather (j_compress_ptr cinfo, JBLOCKROW *MCU_data) 827 encode_mcu_gather (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
792 { 828 {
793 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy; 829 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
794 int blkn, ci; 830 int blkn, ci;
795 jpeg_component_info * compptr; 831 jpeg_component_info *compptr;
796 832
797 /* Take care of restart intervals if needed */ 833 /* Take care of restart intervals if needed */
798 if (cinfo->restart_interval) { 834 if (cinfo->restart_interval) {
799 if (entropy->restarts_to_go == 0) { 835 if (entropy->restarts_to_go == 0) {
800 /* Re-initialize DC predictions to 0 */ 836 /* Re-initialize DC predictions to 0 */
801 for (ci = 0; ci < cinfo->comps_in_scan; ci++) 837 for (ci = 0; ci < cinfo->comps_in_scan; ci++)
802 » entropy->saved.last_dc_val[ci] = 0; 838 entropy->saved.last_dc_val[ci] = 0;
803 /* Update restart state */ 839 /* Update restart state */
804 entropy->restarts_to_go = cinfo->restart_interval; 840 entropy->restarts_to_go = cinfo->restart_interval;
805 } 841 }
806 entropy->restarts_to_go--; 842 entropy->restarts_to_go--;
807 } 843 }
808 844
809 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) { 845 for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
810 ci = cinfo->MCU_membership[blkn]; 846 ci = cinfo->MCU_membership[blkn];
811 compptr = cinfo->cur_comp_info[ci]; 847 compptr = cinfo->cur_comp_info[ci];
812 htest_one_block(cinfo, MCU_data[blkn][0], entropy->saved.last_dc_val[ci], 848 htest_one_block(cinfo, MCU_data[blkn][0], entropy->saved.last_dc_val[ci],
813 » » entropy->dc_count_ptrs[compptr->dc_tbl_no], 849 entropy->dc_count_ptrs[compptr->dc_tbl_no],
814 » » entropy->ac_count_ptrs[compptr->ac_tbl_no]); 850 entropy->ac_count_ptrs[compptr->ac_tbl_no]);
815 entropy->saved.last_dc_val[ci] = MCU_data[blkn][0][0]; 851 entropy->saved.last_dc_val[ci] = MCU_data[blkn][0][0];
816 } 852 }
817 853
818 return TRUE; 854 return TRUE;
819 } 855 }
820 856
821 857
822 /* 858 /*
823 * Generate the best Huffman code table for the given counts, fill htbl. 859 * Generate the best Huffman code table for the given counts, fill htbl.
824 * Note this is also used by jcphuff.c. 860 * Note this is also used by jcphuff.c.
(...skipping 16 matching lines...) Expand all
841 * the adjustment method suggested in JPEG section K.2. This method is *not* 877 * the adjustment method suggested in JPEG section K.2. This method is *not*
842 * optimal; it may not choose the best possible limited-length code. But 878 * optimal; it may not choose the best possible limited-length code. But
843 * typically only very-low-frequency symbols will be given less-than-optimal 879 * typically only very-low-frequency symbols will be given less-than-optimal
844 * lengths, so the code is almost optimal. Experimental comparisons against 880 * lengths, so the code is almost optimal. Experimental comparisons against
845 * an optimal limited-length-code algorithm indicate that the difference is 881 * an optimal limited-length-code algorithm indicate that the difference is
846 * microscopic --- usually less than a hundredth of a percent of total size. 882 * microscopic --- usually less than a hundredth of a percent of total size.
847 * So the extra complexity of an optimal algorithm doesn't seem worthwhile. 883 * So the extra complexity of an optimal algorithm doesn't seem worthwhile.
848 */ 884 */
849 885
850 GLOBAL(void) 886 GLOBAL(void)
851 jpeg_gen_optimal_table (j_compress_ptr cinfo, JHUFF_TBL * htbl, long freq[]) 887 jpeg_gen_optimal_table (j_compress_ptr cinfo, JHUFF_TBL *htbl, long freq[])
852 { 888 {
853 #define MAX_CLEN 32» » /* assumed maximum initial code length */ 889 #define MAX_CLEN 32 /* assumed maximum initial code length */
854 UINT8 bits[MAX_CLEN+1];» /* bits[k] = # of symbols with code length k */ 890 UINT8 bits[MAX_CLEN+1]; /* bits[k] = # of symbols with code length k */
855 int codesize[257];» » /* codesize[k] = code length of symbol k */ 891 int codesize[257]; /* codesize[k] = code length of symbol k */
856 int others[257];» » /* next symbol in current branch of tree */ 892 int others[257]; /* next symbol in current branch of tree */
857 int c1, c2; 893 int c1, c2;
858 int p, i, j; 894 int p, i, j;
859 long v; 895 long v;
860 896
861 /* This algorithm is explained in section K.2 of the JPEG standard */ 897 /* This algorithm is explained in section K.2 of the JPEG standard */
862 898
863 MEMZERO(bits, SIZEOF(bits)); 899 MEMZERO(bits, sizeof(bits));
864 MEMZERO(codesize, SIZEOF(codesize)); 900 MEMZERO(codesize, sizeof(codesize));
865 for (i = 0; i < 257; i++) 901 for (i = 0; i < 257; i++)
866 others[i] = -1;» » /* init links to empty */ 902 others[i] = -1; /* init links to empty */
867 903
868 freq[256] = 1;» » /* make sure 256 has a nonzero count */ 904 freq[256] = 1; /* make sure 256 has a nonzero count */
869 /* Including the pseudo-symbol 256 in the Huffman procedure guarantees 905 /* Including the pseudo-symbol 256 in the Huffman procedure guarantees
870 * that no real symbol is given code-value of all ones, because 256 906 * that no real symbol is given code-value of all ones, because 256
871 * will be placed last in the largest codeword category. 907 * will be placed last in the largest codeword category.
872 */ 908 */
873 909
874 /* Huffman's basic algorithm to assign optimal code lengths to symbols */ 910 /* Huffman's basic algorithm to assign optimal code lengths to symbols */
875 911
876 for (;;) { 912 for (;;) {
877 /* Find the smallest nonzero frequency, set c1 = its symbol */ 913 /* Find the smallest nonzero frequency, set c1 = its symbol */
878 /* In case of ties, take the larger symbol number */ 914 /* In case of ties, take the larger symbol number */
879 c1 = -1; 915 c1 = -1;
880 v = 1000000000L; 916 v = 1000000000L;
881 for (i = 0; i <= 256; i++) { 917 for (i = 0; i <= 256; i++) {
882 if (freq[i] && freq[i] <= v) { 918 if (freq[i] && freq[i] <= v) {
883 » v = freq[i]; 919 v = freq[i];
884 » c1 = i; 920 c1 = i;
885 } 921 }
886 } 922 }
887 923
888 /* Find the next smallest nonzero frequency, set c2 = its symbol */ 924 /* Find the next smallest nonzero frequency, set c2 = its symbol */
889 /* In case of ties, take the larger symbol number */ 925 /* In case of ties, take the larger symbol number */
890 c2 = -1; 926 c2 = -1;
891 v = 1000000000L; 927 v = 1000000000L;
892 for (i = 0; i <= 256; i++) { 928 for (i = 0; i <= 256; i++) {
893 if (freq[i] && freq[i] <= v && i != c1) { 929 if (freq[i] && freq[i] <= v && i != c1) {
894 » v = freq[i]; 930 v = freq[i];
895 » c2 = i; 931 c2 = i;
896 } 932 }
897 } 933 }
898 934
899 /* Done if we've merged everything into one frequency */ 935 /* Done if we've merged everything into one frequency */
900 if (c2 < 0) 936 if (c2 < 0)
901 break; 937 break;
902 938
903 /* Else merge the two counts/trees */ 939 /* Else merge the two counts/trees */
904 freq[c1] += freq[c2]; 940 freq[c1] += freq[c2];
905 freq[c2] = 0; 941 freq[c2] = 0;
906 942
907 /* Increment the codesize of everything in c1's tree branch */ 943 /* Increment the codesize of everything in c1's tree branch */
908 codesize[c1]++; 944 codesize[c1]++;
909 while (others[c1] >= 0) { 945 while (others[c1] >= 0) {
910 c1 = others[c1]; 946 c1 = others[c1];
911 codesize[c1]++; 947 codesize[c1]++;
912 } 948 }
913 949
914 others[c1] = c2;» » /* chain c2 onto c1's tree branch */ 950 others[c1] = c2; /* chain c2 onto c1's tree branch */
915 951
916 /* Increment the codesize of everything in c2's tree branch */ 952 /* Increment the codesize of everything in c2's tree branch */
917 codesize[c2]++; 953 codesize[c2]++;
918 while (others[c2] >= 0) { 954 while (others[c2] >= 0) {
919 c2 = others[c2]; 955 c2 = others[c2];
920 codesize[c2]++; 956 codesize[c2]++;
921 } 957 }
922 } 958 }
923 959
924 /* Now count the number of symbols of each code length */ 960 /* Now count the number of symbols of each code length */
925 for (i = 0; i <= 256; i++) { 961 for (i = 0; i <= 256; i++) {
926 if (codesize[i]) { 962 if (codesize[i]) {
927 /* The JPEG standard seems to think that this can't happen, */ 963 /* The JPEG standard seems to think that this can't happen, */
928 /* but I'm paranoid... */ 964 /* but I'm paranoid... */
929 if (codesize[i] > MAX_CLEN) 965 if (codesize[i] > MAX_CLEN)
930 » ERREXIT(cinfo, JERR_HUFF_CLEN_OVERFLOW); 966 ERREXIT(cinfo, JERR_HUFF_CLEN_OVERFLOW);
931 967
932 bits[codesize[i]]++; 968 bits[codesize[i]]++;
933 } 969 }
934 } 970 }
935 971
936 /* JPEG doesn't allow symbols with code lengths over 16 bits, so if the pure 972 /* JPEG doesn't allow symbols with code lengths over 16 bits, so if the pure
937 * Huffman procedure assigned any such lengths, we must adjust the coding. 973 * Huffman procedure assigned any such lengths, we must adjust the coding.
938 * Here is what the JPEG spec says about how this next bit works: 974 * Here is what the JPEG spec says about how this next bit works:
939 * Since symbols are paired for the longest Huffman code, the symbols are 975 * Since symbols are paired for the longest Huffman code, the symbols are
940 * removed from this length category two at a time. The prefix for the pair 976 * removed from this length category two at a time. The prefix for the pair
941 * (which is one bit shorter) is allocated to one of the pair; then, 977 * (which is one bit shorter) is allocated to one of the pair; then,
942 * skipping the BITS entry for that prefix length, a code word from the next 978 * skipping the BITS entry for that prefix length, a code word from the next
943 * shortest nonzero BITS entry is converted into a prefix for two code words 979 * shortest nonzero BITS entry is converted into a prefix for two code words
944 * one bit longer. 980 * one bit longer.
945 */ 981 */
946 982
947 for (i = MAX_CLEN; i > 16; i--) { 983 for (i = MAX_CLEN; i > 16; i--) {
948 while (bits[i] > 0) { 984 while (bits[i] > 0) {
949 j = i - 2;» » /* find length of new prefix to be used */ 985 j = i - 2; /* find length of new prefix to be used */
950 while (bits[j] == 0) 986 while (bits[j] == 0)
951 » j--; 987 j--;
952 988
953 bits[i] -= 2;» » /* remove two symbols */ 989 bits[i] -= 2; /* remove two symbols */
954 bits[i-1]++;» » /* one goes in this length */ 990 bits[i-1]++; /* one goes in this length */
955 bits[j+1] += 2;» » /* two new symbols in this length */ 991 bits[j+1] += 2; /* two new symbols in this length */
956 bits[j]--;» » /* symbol of this length is now a prefix */ 992 bits[j]--; /* symbol of this length is now a prefix */
957 } 993 }
958 } 994 }
959 995
960 /* Remove the count for the pseudo-symbol 256 from the largest codelength */ 996 /* Remove the count for the pseudo-symbol 256 from the largest codelength */
961 while (bits[i] == 0)» » /* find largest codelength still in use */ 997 while (bits[i] == 0) /* find largest codelength still in use */
962 i--; 998 i--;
963 bits[i]--; 999 bits[i]--;
964 1000
965 /* Return final symbol counts (only for lengths 0..16) */ 1001 /* Return final symbol counts (only for lengths 0..16) */
966 MEMCOPY(htbl->bits, bits, SIZEOF(htbl->bits)); 1002 MEMCOPY(htbl->bits, bits, sizeof(htbl->bits));
967 1003
968 /* Return a list of the symbols sorted by code length */ 1004 /* Return a list of the symbols sorted by code length */
969 /* It's not real clear to me why we don't need to consider the codelength 1005 /* It's not real clear to me why we don't need to consider the codelength
970 * changes made above, but the JPEG spec seems to think this works. 1006 * changes made above, but the JPEG spec seems to think this works.
971 */ 1007 */
972 p = 0; 1008 p = 0;
973 for (i = 1; i <= MAX_CLEN; i++) { 1009 for (i = 1; i <= MAX_CLEN; i++) {
974 for (j = 0; j <= 255; j++) { 1010 for (j = 0; j <= 255; j++) {
975 if (codesize[j] == i) { 1011 if (codesize[j] == i) {
976 » htbl->huffval[p] = (UINT8) j; 1012 htbl->huffval[p] = (UINT8) j;
977 » p++; 1013 p++;
978 } 1014 }
979 } 1015 }
980 } 1016 }
981 1017
982 /* Set sent_table FALSE so updated table will be written to JPEG file. */ 1018 /* Set sent_table FALSE so updated table will be written to JPEG file. */
983 htbl->sent_table = FALSE; 1019 htbl->sent_table = FALSE;
984 } 1020 }
985 1021
986 1022
987 /* 1023 /*
988 * Finish up a statistics-gathering pass and create the new Huffman tables. 1024 * Finish up a statistics-gathering pass and create the new Huffman tables.
989 */ 1025 */
990 1026
991 METHODDEF(void) 1027 METHODDEF(void)
992 finish_pass_gather (j_compress_ptr cinfo) 1028 finish_pass_gather (j_compress_ptr cinfo)
993 { 1029 {
994 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy; 1030 huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
995 int ci, dctbl, actbl; 1031 int ci, dctbl, actbl;
996 jpeg_component_info * compptr; 1032 jpeg_component_info *compptr;
997 JHUFF_TBL **htblptr; 1033 JHUFF_TBL **htblptr;
998 boolean did_dc[NUM_HUFF_TBLS]; 1034 boolean did_dc[NUM_HUFF_TBLS];
999 boolean did_ac[NUM_HUFF_TBLS]; 1035 boolean did_ac[NUM_HUFF_TBLS];
1000 1036
1001 /* It's important not to apply jpeg_gen_optimal_table more than once 1037 /* It's important not to apply jpeg_gen_optimal_table more than once
1002 * per table, because it clobbers the input frequency counts! 1038 * per table, because it clobbers the input frequency counts!
1003 */ 1039 */
1004 MEMZERO(did_dc, SIZEOF(did_dc)); 1040 MEMZERO(did_dc, sizeof(did_dc));
1005 MEMZERO(did_ac, SIZEOF(did_ac)); 1041 MEMZERO(did_ac, sizeof(did_ac));
1006 1042
1007 for (ci = 0; ci < cinfo->comps_in_scan; ci++) { 1043 for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
1008 compptr = cinfo->cur_comp_info[ci]; 1044 compptr = cinfo->cur_comp_info[ci];
1009 dctbl = compptr->dc_tbl_no; 1045 dctbl = compptr->dc_tbl_no;
1010 actbl = compptr->ac_tbl_no; 1046 actbl = compptr->ac_tbl_no;
1011 if (! did_dc[dctbl]) { 1047 if (! did_dc[dctbl]) {
1012 htblptr = & cinfo->dc_huff_tbl_ptrs[dctbl]; 1048 htblptr = & cinfo->dc_huff_tbl_ptrs[dctbl];
1013 if (*htblptr == NULL) 1049 if (*htblptr == NULL)
1014 » *htblptr = jpeg_alloc_huff_table((j_common_ptr) cinfo); 1050 *htblptr = jpeg_alloc_huff_table((j_common_ptr) cinfo);
1015 jpeg_gen_optimal_table(cinfo, *htblptr, entropy->dc_count_ptrs[dctbl]); 1051 jpeg_gen_optimal_table(cinfo, *htblptr, entropy->dc_count_ptrs[dctbl]);
1016 did_dc[dctbl] = TRUE; 1052 did_dc[dctbl] = TRUE;
1017 } 1053 }
1018 if (! did_ac[actbl]) { 1054 if (! did_ac[actbl]) {
1019 htblptr = & cinfo->ac_huff_tbl_ptrs[actbl]; 1055 htblptr = & cinfo->ac_huff_tbl_ptrs[actbl];
1020 if (*htblptr == NULL) 1056 if (*htblptr == NULL)
1021 » *htblptr = jpeg_alloc_huff_table((j_common_ptr) cinfo); 1057 *htblptr = jpeg_alloc_huff_table((j_common_ptr) cinfo);
1022 jpeg_gen_optimal_table(cinfo, *htblptr, entropy->ac_count_ptrs[actbl]); 1058 jpeg_gen_optimal_table(cinfo, *htblptr, entropy->ac_count_ptrs[actbl]);
1023 did_ac[actbl] = TRUE; 1059 did_ac[actbl] = TRUE;
1024 } 1060 }
1025 } 1061 }
1026 } 1062 }
1027 1063
1028 1064
1029 #endif /* ENTROPY_OPT_SUPPORTED */ 1065 #endif /* ENTROPY_OPT_SUPPORTED */
1030 1066
1031 1067
1032 /* 1068 /*
1033 * Module initialization routine for Huffman entropy encoding. 1069 * Module initialization routine for Huffman entropy encoding.
1034 */ 1070 */
1035 1071
1036 GLOBAL(void) 1072 GLOBAL(void)
1037 jinit_huff_encoder (j_compress_ptr cinfo) 1073 jinit_huff_encoder (j_compress_ptr cinfo)
1038 { 1074 {
1039 huff_entropy_ptr entropy; 1075 huff_entropy_ptr entropy;
1040 int i; 1076 int i;
1041 1077
1042 entropy = (huff_entropy_ptr) 1078 entropy = (huff_entropy_ptr)
1043 (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE, 1079 (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
1044 » » » » SIZEOF(huff_entropy_encoder)); 1080 sizeof(huff_entropy_encoder));
1045 cinfo->entropy = (struct jpeg_entropy_encoder *) entropy; 1081 cinfo->entropy = (struct jpeg_entropy_encoder *) entropy;
1046 entropy->pub.start_pass = start_pass_huff; 1082 entropy->pub.start_pass = start_pass_huff;
1047 1083
1048 /* Mark tables unallocated */ 1084 /* Mark tables unallocated */
1049 for (i = 0; i < NUM_HUFF_TBLS; i++) { 1085 for (i = 0; i < NUM_HUFF_TBLS; i++) {
1050 entropy->dc_derived_tbls[i] = entropy->ac_derived_tbls[i] = NULL; 1086 entropy->dc_derived_tbls[i] = entropy->ac_derived_tbls[i] = NULL;
1051 #ifdef ENTROPY_OPT_SUPPORTED 1087 #ifdef ENTROPY_OPT_SUPPORTED
1052 entropy->dc_count_ptrs[i] = entropy->ac_count_ptrs[i] = NULL; 1088 entropy->dc_count_ptrs[i] = entropy->ac_count_ptrs[i] = NULL;
1053 #endif 1089 #endif
1054 } 1090 }
1055 } 1091 }
OLDNEW
« no previous file with comments | « jchuff.h ('k') | jcinit.c » ('j') | jconfig.h » ('J')

Powered by Google App Engine
This is Rietveld 408576698