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