• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * jcphuff.c
3  *
4  * Copyright (C) 1995-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 for progressive JPEG.
9  *
10  * We do not support output suspension in this module, since the library
11  * currently does not allow multiple-scan files to be written with output
12  * suspension.
13  */
14 
15 #define JPEG_INTERNALS
16 #include "jinclude.h"
17 #include "jpeglib.h"
18 #include "jchuff.h"		/* Declarations shared with jchuff.c */
19 
20 #ifdef C_PROGRESSIVE_SUPPORTED
21 
22 /* Expanded entropy encoder object for progressive Huffman encoding. */
23 
24 typedef struct {
25   struct jpeg_entropy_encoder pub; /* public fields */
26 
27   /* Mode flag: TRUE for optimization, FALSE for actual data output */
28   boolean gather_statistics;
29 
30   /* Bit-level coding status.
31    * next_output_byte/free_in_buffer are local copies of cinfo->dest fields.
32    */
33   JOCTET * next_output_byte;	/* => next byte to write in buffer */
34   size_t free_in_buffer;	/* # of byte spaces remaining in buffer */
35   INT32 put_buffer;		/* current bit-accumulation buffer */
36   int put_bits;			/* # of bits now in it */
37   j_compress_ptr cinfo;		/* link to cinfo (needed for dump_buffer) */
38 
39   /* Coding status for DC components */
40   int last_dc_val[MAX_COMPS_IN_SCAN]; /* last DC coef for each component */
41 
42   /* Coding status for AC components */
43   int ac_tbl_no;		/* the table number of the single component */
44   unsigned int EOBRUN;		/* run length of EOBs */
45   unsigned int BE;		/* # of buffered correction bits before MCU */
46   char * bit_buffer;		/* buffer for correction bits (1 per char) */
47   /* packing correction bits tightly would save some space but cost time... */
48 
49   unsigned int restarts_to_go;	/* MCUs left in this restart interval */
50   int next_restart_num;		/* next restart number to write (0-7) */
51 
52   /* Pointers to derived tables (these workspaces have image lifespan).
53    * Since any one scan codes only DC or only AC, we only need one set
54    * of tables, not one for DC and one for AC.
55    */
56   c_derived_tbl * derived_tbls[NUM_HUFF_TBLS];
57 
58   /* Statistics tables for optimization; again, one set is enough */
59   long * count_ptrs[NUM_HUFF_TBLS];
60 } phuff_entropy_encoder;
61 
62 typedef phuff_entropy_encoder * phuff_entropy_ptr;
63 
64 /* MAX_CORR_BITS is the number of bits the AC refinement correction-bit
65  * buffer can hold.  Larger sizes may slightly improve compression, but
66  * 1000 is already well into the realm of overkill.
67  * The minimum safe size is 64 bits.
68  */
69 
70 #define MAX_CORR_BITS  1000	/* Max # of correction bits I can buffer */
71 
72 /* IRIGHT_SHIFT is like RIGHT_SHIFT, but works on int rather than INT32.
73  * We assume that int right shift is unsigned if INT32 right shift is,
74  * which should be safe.
75  */
76 
77 #ifdef RIGHT_SHIFT_IS_UNSIGNED
78 #define ISHIFT_TEMPS	int ishift_temp;
79 #define IRIGHT_SHIFT(x,shft)  \
80 	((ishift_temp = (x)) < 0 ? \
81 	 (ishift_temp >> (shft)) | ((~0) << (16-(shft))) : \
82 	 (ishift_temp >> (shft)))
83 #else
84 #define ISHIFT_TEMPS
85 #define IRIGHT_SHIFT(x,shft)	((x) >> (shft))
86 #endif
87 
88 /* Forward declarations */
89 METHODDEF(boolean) encode_mcu_DC_first JPP((j_compress_ptr cinfo,
90 					    JBLOCKROW *MCU_data));
91 METHODDEF(boolean) encode_mcu_AC_first JPP((j_compress_ptr cinfo,
92 					    JBLOCKROW *MCU_data));
93 METHODDEF(boolean) encode_mcu_DC_refine JPP((j_compress_ptr cinfo,
94 					     JBLOCKROW *MCU_data));
95 METHODDEF(boolean) encode_mcu_AC_refine JPP((j_compress_ptr cinfo,
96 					     JBLOCKROW *MCU_data));
97 METHODDEF(void) finish_pass_phuff JPP((j_compress_ptr cinfo));
98 METHODDEF(void) finish_pass_gather_phuff JPP((j_compress_ptr cinfo));
99 
100 
101 /*
102  * Initialize for a Huffman-compressed scan using progressive JPEG.
103  */
104 
105 METHODDEF(void)
start_pass_phuff(j_compress_ptr cinfo,boolean gather_statistics)106 start_pass_phuff (j_compress_ptr cinfo, boolean gather_statistics)
107 {
108   phuff_entropy_ptr entropy = (phuff_entropy_ptr) cinfo->entropy;
109   boolean is_DC_band;
110   int ci, tbl;
111   jpeg_component_info * compptr;
112 
113   entropy->cinfo = cinfo;
114   entropy->gather_statistics = gather_statistics;
115 
116   is_DC_band = (cinfo->Ss == 0);
117 
118   /* We assume jcmaster.c already validated the scan parameters. */
119 
120   /* Select execution routines */
121   if (cinfo->Ah == 0) {
122     if (is_DC_band)
123       entropy->pub.encode_mcu = encode_mcu_DC_first;
124     else
125       entropy->pub.encode_mcu = encode_mcu_AC_first;
126   } else {
127     if (is_DC_band)
128       entropy->pub.encode_mcu = encode_mcu_DC_refine;
129     else {
130       entropy->pub.encode_mcu = encode_mcu_AC_refine;
131       /* AC refinement needs a correction bit buffer */
132       if (entropy->bit_buffer == NULL)
133 	entropy->bit_buffer = (char *)
134 	  (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
135 				      MAX_CORR_BITS * SIZEOF(char));
136     }
137   }
138   if (gather_statistics)
139     entropy->pub.finish_pass = finish_pass_gather_phuff;
140   else
141     entropy->pub.finish_pass = finish_pass_phuff;
142 
143   /* Only DC coefficients may be interleaved, so cinfo->comps_in_scan = 1
144    * for AC coefficients.
145    */
146   for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
147     compptr = cinfo->cur_comp_info[ci];
148     /* Initialize DC predictions to 0 */
149     entropy->last_dc_val[ci] = 0;
150     /* Get table index */
151     if (is_DC_band) {
152       if (cinfo->Ah != 0)	/* DC refinement needs no table */
153 	continue;
154       tbl = compptr->dc_tbl_no;
155     } else {
156       entropy->ac_tbl_no = tbl = compptr->ac_tbl_no;
157     }
158     if (gather_statistics) {
159       /* Check for invalid table index */
160       /* (make_c_derived_tbl does this in the other path) */
161       if (tbl < 0 || tbl >= NUM_HUFF_TBLS)
162         ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, tbl);
163       /* Allocate and zero the statistics tables */
164       /* Note that jpeg_gen_optimal_table expects 257 entries in each table! */
165       if (entropy->count_ptrs[tbl] == NULL)
166 	entropy->count_ptrs[tbl] = (long *)
167 	  (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
168 				      257 * SIZEOF(long));
169       MEMZERO(entropy->count_ptrs[tbl], 257 * SIZEOF(long));
170     } else {
171       /* Compute derived values for Huffman table */
172       /* We may do this more than once for a table, but it's not expensive */
173       jpeg_make_c_derived_tbl(cinfo, is_DC_band, tbl,
174 			      & entropy->derived_tbls[tbl]);
175     }
176   }
177 
178   /* Initialize AC stuff */
179   entropy->EOBRUN = 0;
180   entropy->BE = 0;
181 
182   /* Initialize bit buffer to empty */
183   entropy->put_buffer = 0;
184   entropy->put_bits = 0;
185 
186   /* Initialize restart stuff */
187   entropy->restarts_to_go = cinfo->restart_interval;
188   entropy->next_restart_num = 0;
189 }
190 
191 
192 /* Outputting bytes to the file.
193  * NB: these must be called only when actually outputting,
194  * that is, entropy->gather_statistics == FALSE.
195  */
196 
197 /* Emit a byte */
198 #define emit_byte(entropy,val)  \
199 	{ *(entropy)->next_output_byte++ = (JOCTET) (val);  \
200 	  if (--(entropy)->free_in_buffer == 0)  \
201 	    dump_buffer(entropy); }
202 
203 
204 LOCAL(void)
dump_buffer(phuff_entropy_ptr entropy)205 dump_buffer (phuff_entropy_ptr entropy)
206 /* Empty the output buffer; we do not support suspension in this module. */
207 {
208   struct jpeg_destination_mgr * dest = entropy->cinfo->dest;
209 
210   if (! (*dest->empty_output_buffer) (entropy->cinfo))
211     ERREXIT(entropy->cinfo, JERR_CANT_SUSPEND);
212   /* After a successful buffer dump, must reset buffer pointers */
213   entropy->next_output_byte = dest->next_output_byte;
214   entropy->free_in_buffer = dest->free_in_buffer;
215 }
216 
217 
218 /* Outputting bits to the file */
219 
220 /* Only the right 24 bits of put_buffer are used; the valid bits are
221  * left-justified in this part.  At most 16 bits can be passed to emit_bits
222  * in one call, and we never retain more than 7 bits in put_buffer
223  * between calls, so 24 bits are sufficient.
224  */
225 
226 LOCAL(void)
emit_bits(phuff_entropy_ptr entropy,unsigned int code,int size)227 emit_bits (phuff_entropy_ptr entropy, unsigned int code, int size)
228 /* Emit some bits, unless we are in gather mode */
229 {
230   /* This routine is heavily used, so it's worth coding tightly. */
231   register INT32 put_buffer = (INT32) code;
232   register int put_bits = entropy->put_bits;
233 
234   /* if size is 0, caller used an invalid Huffman table entry */
235   if (size == 0)
236     ERREXIT(entropy->cinfo, JERR_HUFF_MISSING_CODE);
237 
238   if (entropy->gather_statistics)
239     return;			/* do nothing if we're only getting stats */
240 
241   put_buffer &= (((INT32) 1)<<size) - 1; /* mask off any extra bits in code */
242 
243   put_bits += size;		/* new number of bits in buffer */
244 
245   put_buffer <<= 24 - put_bits; /* align incoming bits */
246 
247   put_buffer |= entropy->put_buffer; /* and merge with old buffer contents */
248 
249   while (put_bits >= 8) {
250     int c = (int) ((put_buffer >> 16) & 0xFF);
251 
252     emit_byte(entropy, c);
253     if (c == 0xFF) {		/* need to stuff a zero byte? */
254       emit_byte(entropy, 0);
255     }
256     put_buffer <<= 8;
257     put_bits -= 8;
258   }
259 
260   entropy->put_buffer = put_buffer; /* update variables */
261   entropy->put_bits = put_bits;
262 }
263 
264 
265 LOCAL(void)
flush_bits(phuff_entropy_ptr entropy)266 flush_bits (phuff_entropy_ptr entropy)
267 {
268   emit_bits(entropy, 0x7F, 7); /* fill any partial byte with ones */
269   entropy->put_buffer = 0;     /* and reset bit-buffer to empty */
270   entropy->put_bits = 0;
271 }
272 
273 
274 /*
275  * Emit (or just count) a Huffman symbol.
276  */
277 
278 LOCAL(void)
emit_symbol(phuff_entropy_ptr entropy,int tbl_no,int symbol)279 emit_symbol (phuff_entropy_ptr entropy, int tbl_no, int symbol)
280 {
281   if (entropy->gather_statistics)
282     entropy->count_ptrs[tbl_no][symbol]++;
283   else {
284     c_derived_tbl * tbl = entropy->derived_tbls[tbl_no];
285     emit_bits(entropy, tbl->ehufco[symbol], tbl->ehufsi[symbol]);
286   }
287 }
288 
289 
290 /*
291  * Emit bits from a correction bit buffer.
292  */
293 
294 LOCAL(void)
emit_buffered_bits(phuff_entropy_ptr entropy,char * bufstart,unsigned int nbits)295 emit_buffered_bits (phuff_entropy_ptr entropy, char * bufstart,
296 		    unsigned int nbits)
297 {
298   if (entropy->gather_statistics)
299     return;			/* no real work */
300 
301   while (nbits > 0) {
302     emit_bits(entropy, (unsigned int) (*bufstart), 1);
303     bufstart++;
304     nbits--;
305   }
306 }
307 
308 
309 /*
310  * Emit any pending EOBRUN symbol.
311  */
312 
313 LOCAL(void)
emit_eobrun(phuff_entropy_ptr entropy)314 emit_eobrun (phuff_entropy_ptr entropy)
315 {
316   register int temp, nbits;
317 
318   if (entropy->EOBRUN > 0) {	/* if there is any pending EOBRUN */
319     temp = entropy->EOBRUN;
320     nbits = 0;
321     while ((temp >>= 1))
322       nbits++;
323     /* safety check: shouldn't happen given limited correction-bit buffer */
324     if (nbits > 14)
325       ERREXIT(entropy->cinfo, JERR_HUFF_MISSING_CODE);
326 
327     emit_symbol(entropy, entropy->ac_tbl_no, nbits << 4);
328     if (nbits)
329       emit_bits(entropy, entropy->EOBRUN, nbits);
330 
331     entropy->EOBRUN = 0;
332 
333     /* Emit any buffered correction bits */
334     emit_buffered_bits(entropy, entropy->bit_buffer, entropy->BE);
335     entropy->BE = 0;
336   }
337 }
338 
339 
340 /*
341  * Emit a restart marker & resynchronize predictions.
342  */
343 
344 LOCAL(void)
emit_restart(phuff_entropy_ptr entropy,int restart_num)345 emit_restart (phuff_entropy_ptr entropy, int restart_num)
346 {
347   int ci;
348 
349   emit_eobrun(entropy);
350 
351   if (! entropy->gather_statistics) {
352     flush_bits(entropy);
353     emit_byte(entropy, 0xFF);
354     emit_byte(entropy, JPEG_RST0 + restart_num);
355   }
356 
357   if (entropy->cinfo->Ss == 0) {
358     /* Re-initialize DC predictions to 0 */
359     for (ci = 0; ci < entropy->cinfo->comps_in_scan; ci++)
360       entropy->last_dc_val[ci] = 0;
361   } else {
362     /* Re-initialize all AC-related fields to 0 */
363     entropy->EOBRUN = 0;
364     entropy->BE = 0;
365   }
366 }
367 
368 
369 /*
370  * MCU encoding for DC initial scan (either spectral selection,
371  * or first pass of successive approximation).
372  */
373 
374 METHODDEF(boolean)
encode_mcu_DC_first(j_compress_ptr cinfo,JBLOCKROW * MCU_data)375 encode_mcu_DC_first (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
376 {
377   phuff_entropy_ptr entropy = (phuff_entropy_ptr) cinfo->entropy;
378   register int temp, temp2;
379   register int nbits;
380   int blkn, ci;
381   int Al = cinfo->Al;
382   JBLOCKROW block;
383   jpeg_component_info * compptr;
384   ISHIFT_TEMPS
385 
386   entropy->next_output_byte = cinfo->dest->next_output_byte;
387   entropy->free_in_buffer = cinfo->dest->free_in_buffer;
388 
389   /* Emit restart marker if needed */
390   if (cinfo->restart_interval)
391     if (entropy->restarts_to_go == 0)
392       emit_restart(entropy, entropy->next_restart_num);
393 
394   /* Encode the MCU data blocks */
395   for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
396     block = MCU_data[blkn];
397     ci = cinfo->MCU_membership[blkn];
398     compptr = cinfo->cur_comp_info[ci];
399 
400     /* Compute the DC value after the required point transform by Al.
401      * This is simply an arithmetic right shift.
402      */
403     temp2 = IRIGHT_SHIFT((int) ((*block)[0]), Al);
404 
405     /* DC differences are figured on the point-transformed values. */
406     temp = temp2 - entropy->last_dc_val[ci];
407     entropy->last_dc_val[ci] = temp2;
408 
409     /* Encode the DC coefficient difference per section G.1.2.1 */
410     temp2 = temp;
411     if (temp < 0) {
412       temp = -temp;		/* temp is abs value of input */
413       /* For a negative input, want temp2 = bitwise complement of abs(input) */
414       /* This code assumes we are on a two's complement machine */
415       temp2--;
416     }
417 
418     /* Find the number of bits needed for the magnitude of the coefficient */
419     nbits = 0;
420     while (temp) {
421       nbits++;
422       temp >>= 1;
423     }
424     /* Check for out-of-range coefficient values.
425      * Since we're encoding a difference, the range limit is twice as much.
426      */
427     if (nbits > MAX_COEF_BITS+1)
428       ERREXIT(cinfo, JERR_BAD_DCT_COEF);
429 
430     /* Count/emit the Huffman-coded symbol for the number of bits */
431     emit_symbol(entropy, compptr->dc_tbl_no, nbits);
432 
433     /* Emit that number of bits of the value, if positive, */
434     /* or the complement of its magnitude, if negative. */
435     if (nbits)			/* emit_bits rejects calls with size 0 */
436       emit_bits(entropy, (unsigned int) temp2, nbits);
437   }
438 
439   cinfo->dest->next_output_byte = entropy->next_output_byte;
440   cinfo->dest->free_in_buffer = entropy->free_in_buffer;
441 
442   /* Update restart-interval state too */
443   if (cinfo->restart_interval) {
444     if (entropy->restarts_to_go == 0) {
445       entropy->restarts_to_go = cinfo->restart_interval;
446       entropy->next_restart_num++;
447       entropy->next_restart_num &= 7;
448     }
449     entropy->restarts_to_go--;
450   }
451 
452   return TRUE;
453 }
454 
455 
456 /*
457  * MCU encoding for AC initial scan (either spectral selection,
458  * or first pass of successive approximation).
459  */
460 
461 METHODDEF(boolean)
encode_mcu_AC_first(j_compress_ptr cinfo,JBLOCKROW * MCU_data)462 encode_mcu_AC_first (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
463 {
464   phuff_entropy_ptr entropy = (phuff_entropy_ptr) cinfo->entropy;
465   register int temp, temp2;
466   register int nbits;
467   register int r, k;
468   int Se = cinfo->Se;
469   int Al = cinfo->Al;
470   JBLOCKROW block;
471 
472   entropy->next_output_byte = cinfo->dest->next_output_byte;
473   entropy->free_in_buffer = cinfo->dest->free_in_buffer;
474 
475   /* Emit restart marker if needed */
476   if (cinfo->restart_interval)
477     if (entropy->restarts_to_go == 0)
478       emit_restart(entropy, entropy->next_restart_num);
479 
480   /* Encode the MCU data block */
481   block = MCU_data[0];
482 
483   /* Encode the AC coefficients per section G.1.2.2, fig. G.3 */
484 
485   r = 0;			/* r = run length of zeros */
486 
487   for (k = cinfo->Ss; k <= Se; k++) {
488     if ((temp = (*block)[jpeg_natural_order[k]]) == 0) {
489       r++;
490       continue;
491     }
492     /* We must apply the point transform by Al.  For AC coefficients this
493      * is an integer division with rounding towards 0.  To do this portably
494      * in C, we shift after obtaining the absolute value; so the code is
495      * interwoven with finding the abs value (temp) and output bits (temp2).
496      */
497     if (temp < 0) {
498       temp = -temp;		/* temp is abs value of input */
499       temp >>= Al;		/* apply the point transform */
500       /* For a negative coef, want temp2 = bitwise complement of abs(coef) */
501       temp2 = ~temp;
502     } else {
503       temp >>= Al;		/* apply the point transform */
504       temp2 = temp;
505     }
506     /* Watch out for case that nonzero coef is zero after point transform */
507     if (temp == 0) {
508       r++;
509       continue;
510     }
511 
512     /* Emit any pending EOBRUN */
513     if (entropy->EOBRUN > 0)
514       emit_eobrun(entropy);
515     /* if run length > 15, must emit special run-length-16 codes (0xF0) */
516     while (r > 15) {
517       emit_symbol(entropy, entropy->ac_tbl_no, 0xF0);
518       r -= 16;
519     }
520 
521     /* Find the number of bits needed for the magnitude of the coefficient */
522     nbits = 1;			/* there must be at least one 1 bit */
523     while ((temp >>= 1))
524       nbits++;
525     /* Check for out-of-range coefficient values */
526     if (nbits > MAX_COEF_BITS)
527       ERREXIT(cinfo, JERR_BAD_DCT_COEF);
528 
529     /* Count/emit Huffman symbol for run length / number of bits */
530     emit_symbol(entropy, entropy->ac_tbl_no, (r << 4) + nbits);
531 
532     /* Emit that number of bits of the value, if positive, */
533     /* or the complement of its magnitude, if negative. */
534     emit_bits(entropy, (unsigned int) temp2, nbits);
535 
536     r = 0;			/* reset zero run length */
537   }
538 
539   if (r > 0) {			/* If there are trailing zeroes, */
540     entropy->EOBRUN++;		/* count an EOB */
541     if (entropy->EOBRUN == 0x7FFF)
542       emit_eobrun(entropy);	/* force it out to avoid overflow */
543   }
544 
545   cinfo->dest->next_output_byte = entropy->next_output_byte;
546   cinfo->dest->free_in_buffer = entropy->free_in_buffer;
547 
548   /* Update restart-interval state too */
549   if (cinfo->restart_interval) {
550     if (entropy->restarts_to_go == 0) {
551       entropy->restarts_to_go = cinfo->restart_interval;
552       entropy->next_restart_num++;
553       entropy->next_restart_num &= 7;
554     }
555     entropy->restarts_to_go--;
556   }
557 
558   return TRUE;
559 }
560 
561 
562 /*
563  * MCU encoding for DC successive approximation refinement scan.
564  * Note: we assume such scans can be multi-component, although the spec
565  * is not very clear on the point.
566  */
567 
568 METHODDEF(boolean)
encode_mcu_DC_refine(j_compress_ptr cinfo,JBLOCKROW * MCU_data)569 encode_mcu_DC_refine (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
570 {
571   phuff_entropy_ptr entropy = (phuff_entropy_ptr) cinfo->entropy;
572   register int temp;
573   int blkn;
574   int Al = cinfo->Al;
575   JBLOCKROW block;
576 
577   entropy->next_output_byte = cinfo->dest->next_output_byte;
578   entropy->free_in_buffer = cinfo->dest->free_in_buffer;
579 
580   /* Emit restart marker if needed */
581   if (cinfo->restart_interval)
582     if (entropy->restarts_to_go == 0)
583       emit_restart(entropy, entropy->next_restart_num);
584 
585   /* Encode the MCU data blocks */
586   for (blkn = 0; blkn < cinfo->blocks_in_MCU; blkn++) {
587     block = MCU_data[blkn];
588 
589     /* We simply emit the Al'th bit of the DC coefficient value. */
590     temp = (*block)[0];
591     emit_bits(entropy, (unsigned int) (temp >> Al), 1);
592   }
593 
594   cinfo->dest->next_output_byte = entropy->next_output_byte;
595   cinfo->dest->free_in_buffer = entropy->free_in_buffer;
596 
597   /* Update restart-interval state too */
598   if (cinfo->restart_interval) {
599     if (entropy->restarts_to_go == 0) {
600       entropy->restarts_to_go = cinfo->restart_interval;
601       entropy->next_restart_num++;
602       entropy->next_restart_num &= 7;
603     }
604     entropy->restarts_to_go--;
605   }
606 
607   return TRUE;
608 }
609 
610 
611 /*
612  * MCU encoding for AC successive approximation refinement scan.
613  */
614 
615 METHODDEF(boolean)
encode_mcu_AC_refine(j_compress_ptr cinfo,JBLOCKROW * MCU_data)616 encode_mcu_AC_refine (j_compress_ptr cinfo, JBLOCKROW *MCU_data)
617 {
618   phuff_entropy_ptr entropy = (phuff_entropy_ptr) cinfo->entropy;
619   register int temp;
620   register int r, k;
621   int EOB;
622   char *BR_buffer;
623   unsigned int BR;
624   int Se = cinfo->Se;
625   int Al = cinfo->Al;
626   JBLOCKROW block;
627   int absvalues[DCTSIZE2];
628 
629   entropy->next_output_byte = cinfo->dest->next_output_byte;
630   entropy->free_in_buffer = cinfo->dest->free_in_buffer;
631 
632   /* Emit restart marker if needed */
633   if (cinfo->restart_interval)
634     if (entropy->restarts_to_go == 0)
635       emit_restart(entropy, entropy->next_restart_num);
636 
637   /* Encode the MCU data block */
638   block = MCU_data[0];
639 
640   /* It is convenient to make a pre-pass to determine the transformed
641    * coefficients' absolute values and the EOB position.
642    */
643   EOB = 0;
644   for (k = cinfo->Ss; k <= Se; k++) {
645     temp = (*block)[jpeg_natural_order[k]];
646     /* We must apply the point transform by Al.  For AC coefficients this
647      * is an integer division with rounding towards 0.  To do this portably
648      * in C, we shift after obtaining the absolute value.
649      */
650     if (temp < 0)
651       temp = -temp;		/* temp is abs value of input */
652     temp >>= Al;		/* apply the point transform */
653     absvalues[k] = temp;	/* save abs value for main pass */
654     if (temp == 1)
655       EOB = k;			/* EOB = index of last newly-nonzero coef */
656   }
657 
658   /* Encode the AC coefficients per section G.1.2.3, fig. G.7 */
659 
660   r = 0;			/* r = run length of zeros */
661   BR = 0;			/* BR = count of buffered bits added now */
662   BR_buffer = entropy->bit_buffer + entropy->BE; /* Append bits to buffer */
663 
664   for (k = cinfo->Ss; k <= Se; k++) {
665     if ((temp = absvalues[k]) == 0) {
666       r++;
667       continue;
668     }
669 
670     /* Emit any required ZRLs, but not if they can be folded into EOB */
671     while (r > 15 && k <= EOB) {
672       /* emit any pending EOBRUN and the BE correction bits */
673       emit_eobrun(entropy);
674       /* Emit ZRL */
675       emit_symbol(entropy, entropy->ac_tbl_no, 0xF0);
676       r -= 16;
677       /* Emit buffered correction bits that must be associated with ZRL */
678       emit_buffered_bits(entropy, BR_buffer, BR);
679       BR_buffer = entropy->bit_buffer; /* BE bits are gone now */
680       BR = 0;
681     }
682 
683     /* If the coef was previously nonzero, it only needs a correction bit.
684      * NOTE: a straight translation of the spec's figure G.7 would suggest
685      * that we also need to test r > 15.  But if r > 15, we can only get here
686      * if k > EOB, which implies that this coefficient is not 1.
687      */
688     if (temp > 1) {
689       /* The correction bit is the next bit of the absolute value. */
690       BR_buffer[BR++] = (char) (temp & 1);
691       continue;
692     }
693 
694     /* Emit any pending EOBRUN and the BE correction bits */
695     emit_eobrun(entropy);
696 
697     /* Count/emit Huffman symbol for run length / number of bits */
698     emit_symbol(entropy, entropy->ac_tbl_no, (r << 4) + 1);
699 
700     /* Emit output bit for newly-nonzero coef */
701     temp = ((*block)[jpeg_natural_order[k]] < 0) ? 0 : 1;
702     emit_bits(entropy, (unsigned int) temp, 1);
703 
704     /* Emit buffered correction bits that must be associated with this code */
705     emit_buffered_bits(entropy, BR_buffer, BR);
706     BR_buffer = entropy->bit_buffer; /* BE bits are gone now */
707     BR = 0;
708     r = 0;			/* reset zero run length */
709   }
710 
711   if (r > 0 || BR > 0) {	/* If there are trailing zeroes, */
712     entropy->EOBRUN++;		/* count an EOB */
713     entropy->BE += BR;		/* concat my correction bits to older ones */
714     /* We force out the EOB if we risk either:
715      * 1. overflow of the EOB counter;
716      * 2. overflow of the correction bit buffer during the next MCU.
717      */
718     if (entropy->EOBRUN == 0x7FFF || entropy->BE > (MAX_CORR_BITS-DCTSIZE2+1))
719       emit_eobrun(entropy);
720   }
721 
722   cinfo->dest->next_output_byte = entropy->next_output_byte;
723   cinfo->dest->free_in_buffer = entropy->free_in_buffer;
724 
725   /* Update restart-interval state too */
726   if (cinfo->restart_interval) {
727     if (entropy->restarts_to_go == 0) {
728       entropy->restarts_to_go = cinfo->restart_interval;
729       entropy->next_restart_num++;
730       entropy->next_restart_num &= 7;
731     }
732     entropy->restarts_to_go--;
733   }
734 
735   return TRUE;
736 }
737 
738 
739 /*
740  * Finish up at the end of a Huffman-compressed progressive scan.
741  */
742 
743 METHODDEF(void)
finish_pass_phuff(j_compress_ptr cinfo)744 finish_pass_phuff (j_compress_ptr cinfo)
745 {
746   phuff_entropy_ptr entropy = (phuff_entropy_ptr) cinfo->entropy;
747 
748   entropy->next_output_byte = cinfo->dest->next_output_byte;
749   entropy->free_in_buffer = cinfo->dest->free_in_buffer;
750 
751   /* Flush out any buffered data */
752   emit_eobrun(entropy);
753   flush_bits(entropy);
754 
755   cinfo->dest->next_output_byte = entropy->next_output_byte;
756   cinfo->dest->free_in_buffer = entropy->free_in_buffer;
757 }
758 
759 
760 /*
761  * Finish up a statistics-gathering pass and create the new Huffman tables.
762  */
763 
764 METHODDEF(void)
finish_pass_gather_phuff(j_compress_ptr cinfo)765 finish_pass_gather_phuff (j_compress_ptr cinfo)
766 {
767   phuff_entropy_ptr entropy = (phuff_entropy_ptr) cinfo->entropy;
768   boolean is_DC_band;
769   int ci, tbl;
770   jpeg_component_info * compptr;
771   JHUFF_TBL **htblptr;
772   boolean did[NUM_HUFF_TBLS];
773 
774   /* Flush out buffered data (all we care about is counting the EOB symbol) */
775   emit_eobrun(entropy);
776 
777   is_DC_band = (cinfo->Ss == 0);
778 
779   /* It's important not to apply jpeg_gen_optimal_table more than once
780    * per table, because it clobbers the input frequency counts!
781    */
782   MEMZERO(did, SIZEOF(did));
783 
784   for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
785     compptr = cinfo->cur_comp_info[ci];
786     if (is_DC_band) {
787       if (cinfo->Ah != 0)	/* DC refinement needs no table */
788 	continue;
789       tbl = compptr->dc_tbl_no;
790     } else {
791       tbl = compptr->ac_tbl_no;
792     }
793     if (! did[tbl]) {
794       if (is_DC_band)
795         htblptr = & cinfo->dc_huff_tbl_ptrs[tbl];
796       else
797         htblptr = & cinfo->ac_huff_tbl_ptrs[tbl];
798       if (*htblptr == NULL)
799         *htblptr = jpeg_alloc_huff_table((j_common_ptr) cinfo);
800       jpeg_gen_optimal_table(cinfo, *htblptr, entropy->count_ptrs[tbl]);
801       did[tbl] = TRUE;
802     }
803   }
804 }
805 
806 
807 /*
808  * Module initialization routine for progressive Huffman entropy encoding.
809  */
810 
811 GLOBAL(void)
jinit_phuff_encoder(j_compress_ptr cinfo)812 jinit_phuff_encoder (j_compress_ptr cinfo)
813 {
814   phuff_entropy_ptr entropy;
815   int i;
816 
817   entropy = (phuff_entropy_ptr)
818     (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
819 				SIZEOF(phuff_entropy_encoder));
820   cinfo->entropy = (struct jpeg_entropy_encoder *) entropy;
821   entropy->pub.start_pass = start_pass_phuff;
822 
823   /* Mark tables unallocated */
824   for (i = 0; i < NUM_HUFF_TBLS; i++) {
825     entropy->derived_tbls[i] = NULL;
826     entropy->count_ptrs[i] = NULL;
827   }
828   entropy->bit_buffer = NULL;	/* needed only in AC refinement scan */
829 }
830 
831 #endif /* C_PROGRESSIVE_SUPPORTED */
832