source: golgotha/src/i4/loaders/jpg/jchuff.cc @ 80

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