source: trunk/libjpeg/jchuff.c @ 15

Last change on this file since 15 was 15, checked in by Eugene Romanenko, 16 years ago

needed libs update

File size: 28.4 KB
Line 
1/*
2 * jchuff.c
3 *
4 * Copyright (C) 1991-1997, Thomas G. Lane.
5 * This file is part of the Independent JPEG Group's software.
6 * For conditions of distribution and use, see the accompanying README file.
7 *
8 * This file contains Huffman entropy encoding routines.
9 *
10 * Much of the complexity here has to do with supporting output suspension.
11 * If the data destination module demands suspension, we want to be able to
12 * back up to the start of the current MCU.  To do this, we copy state
13 * variables into local working storage, and update them back to the
14 * permanent JPEG objects only upon successful completion of an MCU.
15 */
16
17#define JPEG_INTERNALS
18#include "jinclude.h"
19#include "jpeglib.h"
20#include "jchuff.h"             /* Declarations shared with jcphuff.c */
21
22
23/* Expanded entropy encoder object for Huffman encoding.
24 *
25 * The savable_state subrecord contains fields that change within an MCU,
26 * but must not be updated permanently until we complete the MCU.
27 */
28
29typedef struct {
30  INT32 put_buffer;             /* current bit-accumulation buffer */
31  int put_bits;                 /* # of bits now in it */
32  int last_dc_val[MAX_COMPS_IN_SCAN]; /* last DC coef for each component */
33} savable_state;
34
35/* This macro is to work around compilers with missing or broken
36 * structure assignment.  You'll need to fix this code if you have
37 * such a compiler and you change MAX_COMPS_IN_SCAN.
38 */
39
40#ifndef NO_STRUCT_ASSIGN
41#define ASSIGN_STATE(dest,src)  ((dest) = (src))
42#else
43#if MAX_COMPS_IN_SCAN == 4
44#define ASSIGN_STATE(dest,src)  \
45        ((dest).put_buffer = (src).put_buffer, \
46         (dest).put_bits = (src).put_bits, \
47         (dest).last_dc_val[0] = (src).last_dc_val[0], \
48         (dest).last_dc_val[1] = (src).last_dc_val[1], \
49         (dest).last_dc_val[2] = (src).last_dc_val[2], \
50         (dest).last_dc_val[3] = (src).last_dc_val[3])
51#endif
52#endif
53
54
55typedef struct {
56  struct jpeg_entropy_encoder pub; /* public fields */
57
58  savable_state saved;          /* Bit buffer & DC state at start of MCU */
59
60  /* These fields are NOT loaded into local working state. */
61  unsigned int restarts_to_go;  /* MCUs left in this restart interval */
62  int next_restart_num;         /* next restart number to write (0-7) */
63
64  /* Pointers to derived tables (these workspaces have image lifespan) */
65  c_derived_tbl * dc_derived_tbls[NUM_HUFF_TBLS];
66  c_derived_tbl * ac_derived_tbls[NUM_HUFF_TBLS];
67
68#ifdef ENTROPY_OPT_SUPPORTED    /* Statistics tables for optimization */
69  long * dc_count_ptrs[NUM_HUFF_TBLS];
70  long * ac_count_ptrs[NUM_HUFF_TBLS];
71#endif
72} huff_entropy_encoder;
73
74typedef huff_entropy_encoder * huff_entropy_ptr;
75
76/* Working state while writing an MCU.
77 * This struct contains all the fields that are needed by subroutines.
78 */
79
80typedef struct {
81  JOCTET * next_output_byte;    /* => next byte to write in buffer */
82  size_t free_in_buffer;        /* # of byte spaces remaining in buffer */
83  savable_state cur;            /* Current bit buffer & DC state */
84  j_compress_ptr cinfo;         /* dump_buffer needs access to this */
85} working_state;
86
87
88/* Forward declarations */
89METHODDEF(boolean) encode_mcu_huff JPP((j_compress_ptr cinfo,
90                                        JBLOCKROW *MCU_data));
91METHODDEF(void) finish_pass_huff JPP((j_compress_ptr cinfo));
92#ifdef ENTROPY_OPT_SUPPORTED
93METHODDEF(boolean) encode_mcu_gather JPP((j_compress_ptr cinfo,
94                                          JBLOCKROW *MCU_data));
95METHODDEF(void) finish_pass_gather JPP((j_compress_ptr cinfo));
96#endif
97
98
99/*
100 * Initialize for a Huffman-compressed scan.
101 * If gather_statistics is TRUE, we do not output anything during the scan,
102 * just count the Huffman symbols used and generate Huffman code tables.
103 */
104
105METHODDEF(void)
106start_pass_huff (j_compress_ptr cinfo, boolean gather_statistics)
107{
108  huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
109  int ci, dctbl, actbl;
110  jpeg_component_info * compptr;
111
112  if (gather_statistics) {
113#ifdef ENTROPY_OPT_SUPPORTED
114    entropy->pub.encode_mcu = encode_mcu_gather;
115    entropy->pub.finish_pass = finish_pass_gather;
116#else
117    ERREXIT(cinfo, JERR_NOT_COMPILED);
118#endif
119  } else {
120    entropy->pub.encode_mcu = encode_mcu_huff;
121    entropy->pub.finish_pass = finish_pass_huff;
122  }
123
124  for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
125    compptr = cinfo->cur_comp_info[ci];
126    dctbl = compptr->dc_tbl_no;
127    actbl = compptr->ac_tbl_no;
128    if (gather_statistics) {
129#ifdef ENTROPY_OPT_SUPPORTED
130      /* Check for invalid table indexes */
131      /* (make_c_derived_tbl does this in the other path) */
132      if (dctbl < 0 || dctbl >= NUM_HUFF_TBLS)
133        ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, dctbl);
134      if (actbl < 0 || actbl >= NUM_HUFF_TBLS)
135        ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, actbl);
136      /* Allocate and zero the statistics tables */
137      /* Note that jpeg_gen_optimal_table expects 257 entries in each table! */
138      if (entropy->dc_count_ptrs[dctbl] == NULL)
139        entropy->dc_count_ptrs[dctbl] = (long *)
140          (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
141                                      257 * SIZEOF(long));
142      MEMZERO(entropy->dc_count_ptrs[dctbl], 257 * SIZEOF(long));
143      if (entropy->ac_count_ptrs[actbl] == NULL)
144        entropy->ac_count_ptrs[actbl] = (long *)
145          (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
146                                      257 * SIZEOF(long));
147      MEMZERO(entropy->ac_count_ptrs[actbl], 257 * SIZEOF(long));
148#endif
149    } else {
150      /* Compute derived values for Huffman tables */
151      /* We may do this more than once for a table, but it's not expensive */
152      jpeg_make_c_derived_tbl(cinfo, TRUE, dctbl,
153                              & entropy->dc_derived_tbls[dctbl]);
154      jpeg_make_c_derived_tbl(cinfo, FALSE, actbl,
155                              & entropy->ac_derived_tbls[actbl]);
156    }
157    /* Initialize DC predictions to 0 */
158    entropy->saved.last_dc_val[ci] = 0;
159  }
160
161  /* Initialize bit buffer to empty */
162  entropy->saved.put_buffer = 0;
163  entropy->saved.put_bits = 0;
164
165  /* Initialize restart stuff */
166  entropy->restarts_to_go = cinfo->restart_interval;
167  entropy->next_restart_num = 0;
168}
169
170
171/*
172 * Compute the derived values for a Huffman table.
173 * This routine also performs some validation checks on the table.
174 *
175 * Note this is also used by jcphuff.c.
176 */
177
178GLOBAL(void)
179jpeg_make_c_derived_tbl (j_compress_ptr cinfo, boolean isDC, int tblno,
180                         c_derived_tbl ** pdtbl)
181{
182  JHUFF_TBL *htbl;
183  c_derived_tbl *dtbl;
184  int p, i, l, lastp, si, maxsymbol;
185  char huffsize[257];
186  unsigned int huffcode[257];
187  unsigned int code;
188
189  /* Note that huffsize[] and huffcode[] are filled in code-length order,
190   * paralleling the order of the symbols themselves in htbl->huffval[].
191   */
192
193  /* Find the input Huffman table */
194  if (tblno < 0 || tblno >= NUM_HUFF_TBLS)
195    ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tblno);
196  htbl =
197    isDC ? cinfo->dc_huff_tbl_ptrs[tblno] : cinfo->ac_huff_tbl_ptrs[tblno];
198  if (htbl == NULL)
199    ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tblno);
200
201  /* Allocate a workspace if we haven't already done so. */
202  if (*pdtbl == NULL)
203    *pdtbl = (c_derived_tbl *)
204      (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
205                                  SIZEOF(c_derived_tbl));
206  dtbl = *pdtbl;
207 
208  /* Figure C.1: make table of Huffman code length for each symbol */
209
210  p = 0;
211  for (l = 1; l <= 16; l++) {
212    i = (int) htbl->bits[l];
213    if (i < 0 || p + i > 256)   /* protect against table overrun */
214      ERREXIT(cinfo, JERR_BAD_HUFF_TABLE);
215    while (i--)
216      huffsize[p++] = (char) l;
217  }
218  huffsize[p] = 0;
219  lastp = p;
220 
221  /* Figure C.2: generate the codes themselves */
222  /* We also validate that the counts represent a legal Huffman code tree. */
223
224  code = 0;
225  si = huffsize[0];
226  p = 0;
227  while (huffsize[p]) {
228    while (((int) huffsize[p]) == si) {
229      huffcode[p++] = code;
230      code++;
231    }
232    /* code is now 1 more than the last code used for codelength si; but
233     * it must still fit in si bits, since no code is allowed to be all ones.
234     */
235    if (((INT32) code) >= (((INT32) 1) << si))
236      ERREXIT(cinfo, JERR_BAD_HUFF_TABLE);
237    code <<= 1;
238    si++;
239  }
240 
241  /* Figure C.3: generate encoding tables */
242  /* These are code and size indexed by symbol value */
243
244  /* Set all codeless symbols to have code length 0;
245   * this lets us detect duplicate VAL entries here, and later
246   * allows emit_bits to detect any attempt to emit such symbols.
247   */
248  MEMZERO(dtbl->ehufsi, SIZEOF(dtbl->ehufsi));
249
250  /* This is also a convenient place to check for out-of-range
251   * and duplicated VAL entries.  We allow 0..255 for AC symbols
252   * but only 0..15 for DC.  (We could constrain them further
253   * based on data depth and mode, but this seems enough.)
254   */
255  maxsymbol = isDC ? 15 : 255;
256
257  for (p = 0; p < lastp; p++) {
258    i = htbl->huffval[p];
259    if (i < 0 || i > maxsymbol || dtbl->ehufsi[i])
260      ERREXIT(cinfo, JERR_BAD_HUFF_TABLE);
261    dtbl->ehufco[i] = huffcode[p];
262    dtbl->ehufsi[i] = huffsize[p];
263  }
264}
265
266
267/* Outputting bytes to the file */
268
269/* Emit a byte, taking 'action' if must suspend. */
270#define emit_byte(state,val,action)  \
271        { *(state)->next_output_byte++ = (JOCTET) (val);  \
272          if (--(state)->free_in_buffer == 0)  \
273            if (! dump_buffer(state))  \
274              { action; } }
275
276
277LOCAL(boolean)
278dump_buffer (working_state * state)
279/* Empty the output buffer; return TRUE if successful, FALSE if must suspend */
280{
281  struct jpeg_destination_mgr * dest = state->cinfo->dest;
282
283  if (! (*dest->empty_output_buffer) (state->cinfo))
284    return FALSE;
285  /* After a successful buffer dump, must reset buffer pointers */
286  state->next_output_byte = dest->next_output_byte;
287  state->free_in_buffer = dest->free_in_buffer;
288  return TRUE;
289}
290
291
292/* Outputting bits to the file */
293
294/* Only the right 24 bits of put_buffer are used; the valid bits are
295 * left-justified in this part.  At most 16 bits can be passed to emit_bits
296 * in one call, and we never retain more than 7 bits in put_buffer
297 * between calls, so 24 bits are sufficient.
298 */
299
300INLINE
301LOCAL(boolean)
302emit_bits (working_state * state, unsigned int code, int size)
303/* Emit some bits; return TRUE if successful, FALSE if must suspend */
304{
305  /* This routine is heavily used, so it's worth coding tightly. */
306  register INT32 put_buffer = (INT32) code;
307  register int put_bits = state->cur.put_bits;
308
309  /* if size is 0, caller used an invalid Huffman table entry */
310  if (size == 0)
311    ERREXIT(state->cinfo, JERR_HUFF_MISSING_CODE);
312
313  put_buffer &= (((INT32) 1)<<size) - 1; /* mask off any extra bits in code */
314 
315  put_bits += size;             /* new number of bits in buffer */
316 
317  put_buffer <<= 24 - put_bits; /* align incoming bits */
318
319  put_buffer |= state->cur.put_buffer; /* and merge with old buffer contents */
320 
321  while (put_bits >= 8) {
322    int c = (int) ((put_buffer >> 16) & 0xFF);
323   
324    emit_byte(state, c, return FALSE);
325    if (c == 0xFF) {            /* need to stuff a zero byte? */
326      emit_byte(state, 0, return FALSE);
327    }
328    put_buffer <<= 8;
329    put_bits -= 8;
330  }
331
332  state->cur.put_buffer = put_buffer; /* update state variables */
333  state->cur.put_bits = put_bits;
334
335  return TRUE;
336}
337
338
339LOCAL(boolean)
340flush_bits (working_state * state)
341{
342  if (! emit_bits(state, 0x7F, 7)) /* fill any partial byte with ones */
343    return FALSE;
344  state->cur.put_buffer = 0;    /* and reset bit-buffer to empty */
345  state->cur.put_bits = 0;
346  return TRUE;
347}
348
349
350/* Encode a single block's worth of coefficients */
351
352LOCAL(boolean)
353encode_one_block (working_state * state, JCOEFPTR block, int last_dc_val,
354                  c_derived_tbl *dctbl, c_derived_tbl *actbl)
355{
356  register int temp, temp2;
357  register int nbits;
358  register int k, r, i;
359 
360  /* Encode the DC coefficient difference per section F.1.2.1 */
361 
362  temp = temp2 = block[0] - last_dc_val;
363
364  if (temp < 0) {
365    temp = -temp;               /* temp is abs value of input */
366    /* For a negative input, want temp2 = bitwise complement of abs(input) */
367    /* This code assumes we are on a two's complement machine */
368    temp2--;
369  }
370 
371  /* Find the number of bits needed for the magnitude of the coefficient */
372  nbits = 0;
373  while (temp) {
374    nbits++;
375    temp >>= 1;
376  }
377  /* Check for out-of-range coefficient values.
378   * Since we're encoding a difference, the range limit is twice as much.
379   */
380  if (nbits > MAX_COEF_BITS+1)
381    ERREXIT(state->cinfo, JERR_BAD_DCT_COEF);
382 
383  /* Emit the Huffman-coded symbol for the number of bits */
384  if (! emit_bits(state, dctbl->ehufco[nbits], dctbl->ehufsi[nbits]))
385    return FALSE;
386
387  /* Emit that number of bits of the value, if positive, */
388  /* or the complement of its magnitude, if negative. */
389  if (nbits)                    /* emit_bits rejects calls with size 0 */
390    if (! emit_bits(state, (unsigned int) temp2, nbits))
391      return FALSE;
392
393  /* Encode the AC coefficients per section F.1.2.2 */
394 
395  r = 0;                        /* r = run length of zeros */
396 
397  for (k = 1; k < DCTSIZE2; k++) {
398    if ((temp = block[jpeg_natural_order[k]]) == 0) {
399      r++;
400    } else {
401      /* if run length > 15, must emit special run-length-16 codes (0xF0) */
402      while (r > 15) {
403        if (! emit_bits(state, actbl->ehufco[0xF0], actbl->ehufsi[0xF0]))
404          return FALSE;
405        r -= 16;
406      }
407
408      temp2 = temp;
409      if (temp < 0) {
410        temp = -temp;           /* temp is abs value of input */
411        /* This code assumes we are on a two's complement machine */
412        temp2--;
413      }
414     
415      /* Find the number of bits needed for the magnitude of the coefficient */
416      nbits = 1;                /* there must be at least one 1 bit */
417      while ((temp >>= 1))
418        nbits++;
419      /* Check for out-of-range coefficient values */
420      if (nbits > MAX_COEF_BITS)
421        ERREXIT(state->cinfo, JERR_BAD_DCT_COEF);
422     
423      /* Emit Huffman symbol for run length / number of bits */
424      i = (r << 4) + nbits;
425      if (! emit_bits(state, actbl->ehufco[i], actbl->ehufsi[i]))
426        return FALSE;
427
428      /* Emit that number of bits of the value, if positive, */
429      /* or the complement of its magnitude, if negative. */
430      if (! emit_bits(state, (unsigned int) temp2, nbits))
431        return FALSE;
432     
433      r = 0;
434    }
435  }
436
437  /* If the last coef(s) were zero, emit an end-of-block code */
438  if (r > 0)
439    if (! emit_bits(state, actbl->ehufco[0], actbl->ehufsi[0]))
440      return FALSE;
441
442  return TRUE;
443}
444
445
446/*
447 * Emit a restart marker & resynchronize predictions.
448 */
449
450LOCAL(boolean)
451emit_restart (working_state * state, int restart_num)
452{
453  int ci;
454
455  if (! flush_bits(state))
456    return FALSE;
457
458  emit_byte(state, 0xFF, return FALSE);
459  emit_byte(state, JPEG_RST0 + restart_num, return FALSE);
460
461  /* Re-initialize DC predictions to 0 */
462  for (ci = 0; ci < state->cinfo->comps_in_scan; ci++)
463    state->cur.last_dc_val[ci] = 0;
464
465  /* The restart counter is not updated until we successfully write the MCU. */
466
467  return TRUE;
468}
469
470
471/*
472 * Encode and output one MCU's worth of Huffman-compressed coefficients.
473 */
474
475METHODDEF(boolean)
476encode_mcu_huff (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
477{
478  huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
479  working_state state;
480  int blkn, ci;
481  jpeg_component_info * compptr;
482
483  /* Load up working state */
484  state.next_output_byte = cinfo->dest->next_output_byte;
485  state.free_in_buffer = cinfo->dest->free_in_buffer;
486  ASSIGN_STATE(state.cur, entropy->saved);
487  state.cinfo = cinfo;
488
489  /* Emit restart marker if needed */
490  if (cinfo->restart_interval) {
491    if (entropy->restarts_to_go == 0)
492      if (! emit_restart(&state, entropy->next_restart_num))
493        return FALSE;
494  }
495
496  /* Encode the MCU data blocks */
497  for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
498    ci = cinfo->MCU_membership[blkn];
499    compptr = cinfo->cur_comp_info[ci];
500    if (! encode_one_block(&state,
501                           MCU_data[blkn][0], state.cur.last_dc_val[ci],
502                           entropy->dc_derived_tbls[compptr->dc_tbl_no],
503                           entropy->ac_derived_tbls[compptr->ac_tbl_no]))
504      return FALSE;
505    /* Update last_dc_val */
506    state.cur.last_dc_val[ci] = MCU_data[blkn][0][0];
507  }
508
509  /* Completed MCU, so update state */
510  cinfo->dest->next_output_byte = state.next_output_byte;
511  cinfo->dest->free_in_buffer = state.free_in_buffer;
512  ASSIGN_STATE(entropy->saved, state.cur);
513
514  /* Update restart-interval state too */
515  if (cinfo->restart_interval) {
516    if (entropy->restarts_to_go == 0) {
517      entropy->restarts_to_go = cinfo->restart_interval;
518      entropy->next_restart_num++;
519      entropy->next_restart_num &= 7;
520    }
521    entropy->restarts_to_go--;
522  }
523
524  return TRUE;
525}
526
527
528/*
529 * Finish up at the end of a Huffman-compressed scan.
530 */
531
532METHODDEF(void)
533finish_pass_huff (j_compress_ptr cinfo)
534{
535  huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
536  working_state state;
537
538  /* Load up working state ... flush_bits needs it */
539  state.next_output_byte = cinfo->dest->next_output_byte;
540  state.free_in_buffer = cinfo->dest->free_in_buffer;
541  ASSIGN_STATE(state.cur, entropy->saved);
542  state.cinfo = cinfo;
543
544  /* Flush out the last data */
545  if (! flush_bits(&state))
546    ERREXIT(cinfo, JERR_CANT_SUSPEND);
547
548  /* Update state */
549  cinfo->dest->next_output_byte = state.next_output_byte;
550  cinfo->dest->free_in_buffer = state.free_in_buffer;
551  ASSIGN_STATE(entropy->saved, state.cur);
552}
553
554
555/*
556 * Huffman coding optimization.
557 *
558 * We first scan the supplied data and count the number of uses of each symbol
559 * that is to be Huffman-coded. (This process MUST agree with the code above.)
560 * Then we build a Huffman coding tree for the observed counts.
561 * Symbols which are not needed at all for the particular image are not
562 * assigned any code, which saves space in the DHT marker as well as in
563 * the compressed data.
564 */
565
566#ifdef ENTROPY_OPT_SUPPORTED
567
568
569/* Process a single block's worth of coefficients */
570
571LOCAL(void)
572htest_one_block (j_compress_ptr cinfo, JCOEFPTR block, int last_dc_val,
573                 long dc_counts[], long ac_counts[])
574{
575  register int temp;
576  register int nbits;
577  register int k, r;
578 
579  /* Encode the DC coefficient difference per section F.1.2.1 */
580 
581  temp = block[0] - last_dc_val;
582  if (temp < 0)
583    temp = -temp;
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 the Huffman symbol for the number of bits */
598  dc_counts[nbits]++;
599 
600  /* Encode the AC coefficients per section F.1.2.2 */
601 
602  r = 0;                        /* r = run length of zeros */
603 
604  for (k = 1; k < DCTSIZE2; k++) {
605    if ((temp = block[jpeg_natural_order[k]]) == 0) {
606      r++;
607    } else {
608      /* if run length > 15, must emit special run-length-16 codes (0xF0) */
609      while (r > 15) {
610        ac_counts[0xF0]++;
611        r -= 16;
612      }
613     
614      /* Find the number of bits needed for the magnitude of the coefficient */
615      if (temp < 0)
616        temp = -temp;
617     
618      /* Find the number of bits needed for the magnitude of the coefficient */
619      nbits = 1;                /* there must be at least one 1 bit */
620      while ((temp >>= 1))
621        nbits++;
622      /* Check for out-of-range coefficient values */
623      if (nbits > MAX_COEF_BITS)
624        ERREXIT(cinfo, JERR_BAD_DCT_COEF);
625     
626      /* Count Huffman symbol for run length / number of bits */
627      ac_counts[(r << 4) + nbits]++;
628     
629      r = 0;
630    }
631  }
632
633  /* If the last coef(s) were zero, emit an end-of-block code */
634  if (r > 0)
635    ac_counts[0]++;
636}
637
638
639/*
640 * Trial-encode one MCU's worth of Huffman-compressed coefficients.
641 * No data is actually output, so no suspension return is possible.
642 */
643
644METHODDEF(boolean)
645encode_mcu_gather (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
646{
647  huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
648  int blkn, ci;
649  jpeg_component_info * compptr;
650
651  /* Take care of restart intervals if needed */
652  if (cinfo->restart_interval) {
653    if (entropy->restarts_to_go == 0) {
654      /* Re-initialize DC predictions to 0 */
655      for (ci = 0; ci < cinfo->comps_in_scan; ci++)
656        entropy->saved.last_dc_val[ci] = 0;
657      /* Update restart state */
658      entropy->restarts_to_go = cinfo->restart_interval;
659    }
660    entropy->restarts_to_go--;
661  }
662
663  for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
664    ci = cinfo->MCU_membership[blkn];
665    compptr = cinfo->cur_comp_info[ci];
666    htest_one_block(cinfo, MCU_data[blkn][0], entropy->saved.last_dc_val[ci],
667                    entropy->dc_count_ptrs[compptr->dc_tbl_no],
668                    entropy->ac_count_ptrs[compptr->ac_tbl_no]);
669    entropy->saved.last_dc_val[ci] = MCU_data[blkn][0][0];
670  }
671
672  return TRUE;
673}
674
675
676/*
677 * Generate the best Huffman code table for the given counts, fill htbl.
678 * Note this is also used by jcphuff.c.
679 *
680 * The JPEG standard requires that no symbol be assigned a codeword of all
681 * one bits (so that padding bits added at the end of a compressed segment
682 * can't look like a valid code).  Because of the canonical ordering of
683 * codewords, this just means that there must be an unused slot in the
684 * longest codeword length category.  Section K.2 of the JPEG spec suggests
685 * reserving such a slot by pretending that symbol 256 is a valid symbol
686 * with count 1.  In theory that's not optimal; giving it count zero but
687 * including it in the symbol set anyway should give a better Huffman code.
688 * But the theoretically better code actually seems to come out worse in
689 * practice, because it produces more all-ones bytes (which incur stuffed
690 * zero bytes in the final file).  In any case the difference is tiny.
691 *
692 * The JPEG standard requires Huffman codes to be no more than 16 bits long.
693 * If some symbols have a very small but nonzero probability, the Huffman tree
694 * must be adjusted to meet the code length restriction.  We currently use
695 * the adjustment method suggested in JPEG section K.2.  This method is *not*
696 * optimal; it may not choose the best possible limited-length code.  But
697 * typically only very-low-frequency symbols will be given less-than-optimal
698 * lengths, so the code is almost optimal.  Experimental comparisons against
699 * an optimal limited-length-code algorithm indicate that the difference is
700 * microscopic --- usually less than a hundredth of a percent of total size.
701 * So the extra complexity of an optimal algorithm doesn't seem worthwhile.
702 */
703
704GLOBAL(void)
705jpeg_gen_optimal_table (j_compress_ptr cinfo, JHUFF_TBL * htbl, long freq[])
706{
707#define MAX_CLEN 32             /* assumed maximum initial code length */
708  UINT8 bits[MAX_CLEN+1];       /* bits[k] = # of symbols with code length k */
709  int codesize[257];            /* codesize[k] = code length of symbol k */
710  int others[257];              /* next symbol in current branch of tree */
711  int c1, c2;
712  int p, i, j;
713  long v;
714
715  /* This algorithm is explained in section K.2 of the JPEG standard */
716
717  MEMZERO(bits, SIZEOF(bits));
718  MEMZERO(codesize, SIZEOF(codesize));
719  for (i = 0; i < 257; i++)
720    others[i] = -1;             /* init links to empty */
721 
722  freq[256] = 1;                /* make sure 256 has a nonzero count */
723  /* Including the pseudo-symbol 256 in the Huffman procedure guarantees
724   * that no real symbol is given code-value of all ones, because 256
725   * will be placed last in the largest codeword category.
726   */
727
728  /* Huffman's basic algorithm to assign optimal code lengths to symbols */
729
730  for (;;) {
731    /* Find the smallest nonzero frequency, set c1 = its symbol */
732    /* In case of ties, take the larger symbol number */
733    c1 = -1;
734    v = 1000000000L;
735    for (i = 0; i <= 256; i++) {
736      if (freq[i] && freq[i] <= v) {
737        v = freq[i];
738        c1 = i;
739      }
740    }
741
742    /* Find the next smallest nonzero frequency, set c2 = its symbol */
743    /* In case of ties, take the larger symbol number */
744    c2 = -1;
745    v = 1000000000L;
746    for (i = 0; i <= 256; i++) {
747      if (freq[i] && freq[i] <= v && i != c1) {
748        v = freq[i];
749        c2 = i;
750      }
751    }
752
753    /* Done if we've merged everything into one frequency */
754    if (c2 < 0)
755      break;
756   
757    /* Else merge the two counts/trees */
758    freq[c1] += freq[c2];
759    freq[c2] = 0;
760
761    /* Increment the codesize of everything in c1's tree branch */
762    codesize[c1]++;
763    while (others[c1] >= 0) {
764      c1 = others[c1];
765      codesize[c1]++;
766    }
767   
768    others[c1] = c2;            /* chain c2 onto c1's tree branch */
769   
770    /* Increment the codesize of everything in c2's tree branch */
771    codesize[c2]++;
772    while (others[c2] >= 0) {
773      c2 = others[c2];
774      codesize[c2]++;
775    }
776  }
777
778  /* Now count the number of symbols of each code length */
779  for (i = 0; i <= 256; i++) {
780    if (codesize[i]) {
781      /* The JPEG standard seems to think that this can't happen, */
782      /* but I'm paranoid... */
783      if (codesize[i] > MAX_CLEN)
784        ERREXIT(cinfo, JERR_HUFF_CLEN_OVERFLOW);
785
786      bits[codesize[i]]++;
787    }
788  }
789
790  /* JPEG doesn't allow symbols with code lengths over 16 bits, so if the pure
791   * Huffman procedure assigned any such lengths, we must adjust the coding.
792   * Here is what the JPEG spec says about how this next bit works:
793   * Since symbols are paired for the longest Huffman code, the symbols are
794   * removed from this length category two at a time.  The prefix for the pair
795   * (which is one bit shorter) is allocated to one of the pair; then,
796   * skipping the BITS entry for that prefix length, a code word from the next
797   * shortest nonzero BITS entry is converted into a prefix for two code words
798   * one bit longer.
799   */
800 
801  for (i = MAX_CLEN; i > 16; i--) {
802    while (bits[i] > 0) {
803      j = i - 2;                /* find length of new prefix to be used */
804      while (bits[j] == 0)
805        j--;
806     
807      bits[i] -= 2;             /* remove two symbols */
808      bits[i-1]++;              /* one goes in this length */
809      bits[j+1] += 2;           /* two new symbols in this length */
810      bits[j]--;                /* symbol of this length is now a prefix */
811    }
812  }
813
814  /* Remove the count for the pseudo-symbol 256 from the largest codelength */
815  while (bits[i] == 0)          /* find largest codelength still in use */
816    i--;
817  bits[i]--;
818 
819  /* Return final symbol counts (only for lengths 0..16) */
820  MEMCOPY(htbl->bits, bits, SIZEOF(htbl->bits));
821 
822  /* Return a list of the symbols sorted by code length */
823  /* It's not real clear to me why we don't need to consider the codelength
824   * changes made above, but the JPEG spec seems to think this works.
825   */
826  p = 0;
827  for (i = 1; i <= MAX_CLEN; i++) {
828    for (j = 0; j <= 255; j++) {
829      if (codesize[j] == i) {
830        htbl->huffval[p] = (UINT8) j;
831        p++;
832      }
833    }
834  }
835
836  /* Set sent_table FALSE so updated table will be written to JPEG file. */
837  htbl->sent_table = FALSE;
838}
839
840
841/*
842 * Finish up a statistics-gathering pass and create the new Huffman tables.
843 */
844
845METHODDEF(void)
846finish_pass_gather (j_compress_ptr cinfo)
847{
848  huff_entropy_ptr entropy = (huff_entropy_ptr) cinfo->entropy;
849  int ci, dctbl, actbl;
850  jpeg_component_info * compptr;
851  JHUFF_TBL **htblptr;
852  boolean did_dc[NUM_HUFF_TBLS];
853  boolean did_ac[NUM_HUFF_TBLS];
854
855  /* It's important not to apply jpeg_gen_optimal_table more than once
856   * per table, because it clobbers the input frequency counts!
857   */
858  MEMZERO(did_dc, SIZEOF(did_dc));
859  MEMZERO(did_ac, SIZEOF(did_ac));
860
861  for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
862    compptr = cinfo->cur_comp_info[ci];
863    dctbl = compptr->dc_tbl_no;
864    actbl = compptr->ac_tbl_no;
865    if (! did_dc[dctbl]) {
866      htblptr = & cinfo->dc_huff_tbl_ptrs[dctbl];
867      if (*htblptr == NULL)
868        *htblptr = jpeg_alloc_huff_table((j_common_ptr) cinfo);
869      jpeg_gen_optimal_table(cinfo, *htblptr, entropy->dc_count_ptrs[dctbl]);
870      did_dc[dctbl] = TRUE;
871    }
872    if (! did_ac[actbl]) {
873      htblptr = & cinfo->ac_huff_tbl_ptrs[actbl];
874      if (*htblptr == NULL)
875        *htblptr = jpeg_alloc_huff_table((j_common_ptr) cinfo);
876      jpeg_gen_optimal_table(cinfo, *htblptr, entropy->ac_count_ptrs[actbl]);
877      did_ac[actbl] = TRUE;
878    }
879  }
880}
881
882
883#endif /* ENTROPY_OPT_SUPPORTED */
884
885
886/*
887 * Module initialization routine for Huffman entropy encoding.
888 */
889
890GLOBAL(void)
891jinit_huff_encoder (j_compress_ptr cinfo)
892{
893  huff_entropy_ptr entropy;
894  int i;
895
896  entropy = (huff_entropy_ptr)
897    (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
898                                SIZEOF(huff_entropy_encoder));
899  cinfo->entropy = (struct jpeg_entropy_encoder *) entropy;
900  entropy->pub.start_pass = start_pass_huff;
901
902  /* Mark tables unallocated */
903  for (i = 0; i < NUM_HUFF_TBLS; i++) {
904    entropy->dc_derived_tbls[i] = entropy->ac_derived_tbls[i] = NULL;
905#ifdef ENTROPY_OPT_SUPPORTED
906    entropy->dc_count_ptrs[i] = entropy->ac_count_ptrs[i] = NULL;
907#endif
908  }
909}
Note: See TracBrowser for help on using the repository browser.