]> Creatis software - gdcm.git/blob - src/gdcmjpeg/jclhuff.c
*** empty log message ***
[gdcm.git] / src / gdcmjpeg / jclhuff.c
1 /*
2  * jclhuff.c
3  *
4  * Copyright (C) 1991-1998, 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 lossless JPEG.
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 "jlossls.h"    /* Private declarations for lossless codec */
21 #include "jchuff.h"    /* Declarations shared with jc*huff.c */
22
23
24 /* Expanded entropy encoder object for Huffman encoding.
25  *
26  * The savable_state subrecord contains fields that change within an MCU,
27  * but must not be updated permanently until we complete the MCU.
28  */
29
30 typedef struct {
31   INT32 put_buffer;    /* current bit-accumulation buffer */
32   int put_bits;      /* # of bits now in it */
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 #define ASSIGN_STATE(dest,src)  \
44   ((dest).put_buffer = (src).put_buffer, \
45    (dest).put_bits = (src).put_bits)
46 #endif
47
48
49 typedef struct {
50   int ci, yoffset, MCU_width;
51 } lhe_input_ptr_info;
52
53
54 typedef struct {
55   savable_state saved;    /* Bit buffer at start of MCU */
56
57   /* These fields are NOT loaded into local working state. */
58   unsigned int restarts_to_go;  /* MCUs left in this restart interval */
59   int next_restart_num;    /* next restart number to write (0-7) */
60
61   /* Pointers to derived tables (these workspaces have image lifespan) */
62   c_derived_tbl * derived_tbls[NUM_HUFF_TBLS];
63
64   /* Pointers to derived tables to be used for each data unit within an MCU */
65   c_derived_tbl * cur_tbls[C_MAX_DATA_UNITS_IN_MCU];
66
67 #ifdef ENTROPY_OPT_SUPPORTED  /* Statistics tables for optimization */
68   long * count_ptrs[NUM_HUFF_TBLS];
69
70   /* Pointers to stats tables to be used for each data unit within an MCU */
71   long * cur_counts[C_MAX_DATA_UNITS_IN_MCU];
72 #endif
73
74   /* Pointers to the proper input difference row for each group of data units
75    * within an MCU.  For each component, there are Vi groups of Hi data units.
76    */
77   JDIFFROW input_ptr[C_MAX_DATA_UNITS_IN_MCU];
78
79   /* Number of input pointers in use for the current MCU.  This is the sum
80    * of all Vi in the MCU.
81    */
82   int num_input_ptrs;
83
84   /* Information used for positioning the input pointers within the input
85    * difference rows.
86    */
87   lhe_input_ptr_info input_ptr_info[C_MAX_DATA_UNITS_IN_MCU];
88
89   /* Index of the proper input pointer for each data unit within an MCU */
90   int input_ptr_index[C_MAX_DATA_UNITS_IN_MCU];
91
92 } lhuff_entropy_encoder;
93
94 typedef lhuff_entropy_encoder * lhuff_entropy_ptr;
95
96 /* Working state while writing an MCU.
97  * This struct contains all the fields that are needed by subroutines.
98  */
99
100 typedef struct {
101   JOCTET * next_output_byte;  /* => next byte to write in buffer */
102   size_t free_in_buffer;  /* # of byte spaces remaining in buffer */
103   savable_state cur;    /* Current bit buffer & DC state */
104   j_compress_ptr cinfo;    /* dump_buffer needs access to this */
105 } working_state;
106
107
108 /* Forward declarations */
109 METHODDEF(JDIMENSION) encode_mcus_huff (j_compress_ptr cinfo,
110           JDIFFIMAGE diff_buf,
111           JDIMENSION MCU_row_num,
112           JDIMENSION MCU_col_num,
113           JDIMENSION nMCU);
114 METHODDEF(void) finish_pass_huff JPP((j_compress_ptr cinfo));
115 #ifdef ENTROPY_OPT_SUPPORTED
116 METHODDEF(JDIMENSION) encode_mcus_gather (j_compress_ptr cinfo,
117             JDIFFIMAGE diff_buf,
118             JDIMENSION MCU_row_num,
119             JDIMENSION MCU_col_num,
120             JDIMENSION nMCU);
121 METHODDEF(void) finish_pass_gather JPP((j_compress_ptr cinfo));
122 #endif
123
124
125 /*
126  * Initialize for a Huffman-compressed scan.
127  * If gather_statistics is TRUE, we do not output anything during the scan,
128  * just count the Huffman symbols used and generate Huffman code tables.
129  */
130
131 METHODDEF(void)
132 start_pass_huff (j_compress_ptr cinfo, boolean gather_statistics)
133 {
134   j_lossless_c_ptr losslsc = (j_lossless_c_ptr) cinfo->codec;
135   lhuff_entropy_ptr entropy = (lhuff_entropy_ptr) losslsc->entropy_private;
136   int ci, dctbl, sampn, ptrn, yoffset, xoffset;
137   jpeg_component_info * compptr;
138
139   if (gather_statistics) {
140 #ifdef ENTROPY_OPT_SUPPORTED
141     losslsc->entropy_encode_mcus = encode_mcus_gather;
142     losslsc->pub.entropy_finish_pass = finish_pass_gather;
143 #else
144     ERREXIT(cinfo, JERR_NOT_COMPILED);
145 #endif
146   } else {
147     losslsc->entropy_encode_mcus = encode_mcus_huff;
148     losslsc->pub.entropy_finish_pass = finish_pass_huff;
149   }
150
151   for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
152     compptr = cinfo->cur_comp_info[ci];
153     dctbl = compptr->dc_tbl_no;
154     if (gather_statistics) {
155 #ifdef ENTROPY_OPT_SUPPORTED
156       /* Check for invalid table indexes */
157       /* (make_c_derived_tbl does this in the other path) */
158       if (dctbl < 0 || dctbl >= NUM_HUFF_TBLS)
159   ERREXIT1(cinfo, JERR_NO_HUFF_TABLE, dctbl);
160       /* Allocate and zero the statistics tables */
161       /* Note that jpeg_gen_optimal_table expects 257 entries in each table! */
162       if (entropy->count_ptrs[dctbl] == NULL)
163   entropy->count_ptrs[dctbl] = (long *)
164     (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
165               257 * SIZEOF(long));
166       MEMZERO(entropy->count_ptrs[dctbl], 257 * SIZEOF(long));
167 #endif
168     } else {
169       /* Compute derived values for Huffman tables */
170       /* We may do this more than once for a table, but it's not expensive */
171       jpeg_make_c_derived_tbl(cinfo, TRUE, dctbl,
172             & entropy->derived_tbls[dctbl]);
173     }
174   }
175
176   /* Precalculate encoding info for each sample in an MCU of this scan */
177   for (sampn = 0, ptrn = 0; sampn < cinfo->data_units_in_MCU;) {
178     compptr = cinfo->cur_comp_info[cinfo->MCU_membership[sampn]];
179     ci = compptr->component_index;
180     /*    ci = cinfo->MCU_membership[sampn];
181     compptr = cinfo->cur_comp_info[ci];*/
182     for (yoffset = 0; yoffset < compptr->MCU_height; yoffset++, ptrn++) {
183       /* Precalculate the setup info for each input pointer */
184       entropy->input_ptr_info[ptrn].ci = ci;
185       entropy->input_ptr_info[ptrn].yoffset = yoffset;
186       entropy->input_ptr_info[ptrn].MCU_width = compptr->MCU_width;
187       for (xoffset = 0; xoffset < compptr->MCU_width; xoffset++, sampn++) {
188   /* Precalculate the input pointer index for each sample */
189   entropy->input_ptr_index[sampn] = ptrn;
190   /* Precalculate which tables to use for each sample */
191   entropy->cur_tbls[sampn] = entropy->derived_tbls[compptr->dc_tbl_no];
192   entropy->cur_counts[sampn] = entropy->count_ptrs[compptr->dc_tbl_no];
193       }
194     }
195   }
196   entropy->num_input_ptrs = ptrn;
197
198   /* Initialize bit buffer to empty */
199   entropy->saved.put_buffer = 0;
200   entropy->saved.put_bits = 0;
201
202   /* Initialize restart stuff */
203   entropy->restarts_to_go = cinfo->restart_interval;
204   entropy->next_restart_num = 0;
205 }
206
207
208 /* Outputting bytes to the file */
209
210 /* Emit a byte, taking 'action' if must suspend. */
211 #define emit_byte(state,val,action)  \
212   { *(state)->next_output_byte++ = (JOCTET) (val);  \
213     if (--(state)->free_in_buffer == 0)  \
214       if (! dump_buffer(state))  \
215         { action; } }
216
217
218 LOCAL(boolean)
219 dump_buffer (working_state * state)
220 /* Empty the output buffer; return TRUE if successful, FALSE if must suspend */
221 {
222   struct jpeg_destination_mgr * dest = state->cinfo->dest;
223
224   if (! (*dest->empty_output_buffer) (state->cinfo))
225     return FALSE;
226   /* After a successful buffer dump, must reset buffer pointers */
227   state->next_output_byte = dest->next_output_byte;
228   state->free_in_buffer = dest->free_in_buffer;
229   return TRUE;
230 }
231
232
233 /* Outputting bits to the file */
234
235 /* Only the right 24 bits of put_buffer are used; the valid bits are
236  * left-justified in this part.  At most 16 bits can be passed to emit_bits
237  * in one call, and we never retain more than 7 bits in put_buffer
238  * between calls, so 24 bits are sufficient.
239  */
240
241 INLINE
242 LOCAL(boolean)
243 emit_bits (working_state * state, unsigned int code, int size)
244 /* Emit some bits; return TRUE if successful, FALSE if must suspend */
245 {
246   /* This routine is heavily used, so it's worth coding tightly. */
247   register INT32 put_buffer = (INT32) code;
248   register int put_bits = state->cur.put_bits;
249
250   /* if size is 0, caller used an invalid Huffman table entry */
251   if (size == 0)
252     ERREXIT(state->cinfo, JERR_HUFF_MISSING_CODE);
253
254   put_buffer &= (((INT32) 1)<<size) - 1; /* mask off any extra bits in code */
255   
256   put_bits += size;    /* new number of bits in buffer */
257   
258   put_buffer <<= 24 - put_bits; /* align incoming bits */
259
260   put_buffer |= state->cur.put_buffer; /* and merge with old buffer contents */
261   
262   while (put_bits >= 8) {
263     int c = (int) ((put_buffer >> 16) & 0xFF);
264     
265     emit_byte(state, c, return FALSE);
266     if (c == 0xFF) {    /* need to stuff a zero byte? */
267       emit_byte(state, 0, return FALSE);
268     }
269     put_buffer <<= 8;
270     put_bits -= 8;
271   }
272
273   state->cur.put_buffer = put_buffer; /* update state variables */
274   state->cur.put_bits = put_bits;
275
276   return TRUE;
277 }
278
279
280 LOCAL(boolean)
281 flush_bits (working_state * state)
282 {
283   if (! emit_bits(state, 0x7F, 7)) /* fill any partial byte with ones */
284     return FALSE;
285   state->cur.put_buffer = 0;  /* and reset bit-buffer to empty */
286   state->cur.put_bits = 0;
287   return TRUE;
288 }
289
290
291 /*
292  * Emit a restart marker & resynchronize predictions.
293  */
294
295 LOCAL(boolean)
296 emit_restart (working_state * state, int restart_num)
297 {
298   /* int ci; */
299
300   if (! flush_bits(state))
301     return FALSE;
302
303   emit_byte(state, 0xFF, return FALSE);
304   emit_byte(state, JPEG_RST0 + restart_num, return FALSE);
305
306   /* The restart counter is not updated until we successfully write the MCU. */
307
308   return TRUE;
309 }
310
311
312 /*
313  * Encode and output one nMCU's worth of Huffman-compressed differences.
314  */
315
316 METHODDEF(JDIMENSION)
317 encode_mcus_huff (j_compress_ptr cinfo, JDIFFIMAGE diff_buf,
318       JDIMENSION MCU_row_num, JDIMENSION MCU_col_num,
319       JDIMENSION nMCU)
320 {
321   j_lossless_c_ptr losslsc = (j_lossless_c_ptr) cinfo->codec;
322   lhuff_entropy_ptr entropy = (lhuff_entropy_ptr) losslsc->entropy_private;
323   working_state state;
324   unsigned int mcu_num;
325   int sampn, ci, yoffset, MCU_width, ptrn;
326   /* jpeg_component_info * compptr; */
327
328   /* Load up working state */
329   state.next_output_byte = cinfo->dest->next_output_byte;
330   state.free_in_buffer = cinfo->dest->free_in_buffer;
331   ASSIGN_STATE(state.cur, entropy->saved);
332   state.cinfo = cinfo;
333
334   /* Emit restart marker if needed */
335   if (cinfo->restart_interval) {
336     if (entropy->restarts_to_go == 0)
337       if (! emit_restart(&state, entropy->next_restart_num))
338   return 0;
339   }
340
341   /* Set input pointer locations based on MCU_col_num */
342   for (ptrn = 0; ptrn < entropy->num_input_ptrs; ptrn++) {
343     ci = entropy->input_ptr_info[ptrn].ci;
344     yoffset = entropy->input_ptr_info[ptrn].yoffset;
345     MCU_width = entropy->input_ptr_info[ptrn].MCU_width;
346     entropy->input_ptr[ptrn] =
347       diff_buf[ci][MCU_row_num + yoffset] + (MCU_col_num * MCU_width);
348   }
349
350   for (mcu_num = 0; mcu_num < nMCU; mcu_num++) {
351
352     /* Inner loop handles the samples in the MCU */
353     for (sampn = 0; sampn < cinfo->data_units_in_MCU; sampn++) {
354       register int temp, temp2 /* , temp3 */ ;
355       register int nbits;
356       c_derived_tbl *dctbl = entropy->cur_tbls[sampn];
357   
358       /* Encode the difference per section H.1.2.2 */
359   
360       /* Input the sample difference */
361       temp = *entropy->input_ptr[entropy->input_ptr_index[sampn]]++;
362
363       if (temp & 0x8000) {  /* instead of temp < 0 */
364   temp = (-temp) & 0x7FFF; /* absolute value, mod 2^16 */
365   if (temp == 0)    /* special case: magnitude = 32768 */
366     temp2 = temp = 0x8000;
367   temp2 = ~ temp;    /* one's complement of magnitude */
368       } else {
369   temp &= 0x7FFF;    /* abs value mod 2^16 */
370   temp2 = temp;    /* magnitude */
371       }
372
373       /* Find the number of bits needed for the magnitude of the difference */
374       nbits = 0;
375       while (temp) {
376   nbits++;
377   temp >>= 1;
378       }
379       /* Check for out-of-range difference values.
380        */
381       if (nbits > MAX_DIFF_BITS)
382   ERREXIT(cinfo, JERR_BAD_DIFF);
383   
384       /* Emit the Huffman-coded symbol for the number of bits */
385       if (! emit_bits(&state, dctbl->ehufco[nbits], dctbl->ehufsi[nbits]))
386   return mcu_num;
387
388       /* Emit that number of bits of the value, if positive, */
389       /* or the complement of its magnitude, if negative. */
390       if (nbits &&    /* emit_bits rejects calls with size 0 */
391     nbits != 16)    /* special case: no bits should be emitted */
392   if (! emit_bits(&state, (unsigned int) temp2, nbits))
393     return mcu_num;
394     }
395
396     /* Completed MCU, so update state */
397     cinfo->dest->next_output_byte = state.next_output_byte;
398     cinfo->dest->free_in_buffer = state.free_in_buffer;
399     ASSIGN_STATE(entropy->saved, state.cur);
400
401     /* Update restart-interval state too */
402     if (cinfo->restart_interval) {
403       if (entropy->restarts_to_go == 0) {
404   entropy->restarts_to_go = cinfo->restart_interval;
405   entropy->next_restart_num++;
406   entropy->next_restart_num &= 7;
407       }
408       entropy->restarts_to_go--;
409     }
410
411   }
412
413   return nMCU;
414 }
415
416
417 /*
418  * Finish up at the end of a Huffman-compressed scan.
419  */
420
421 METHODDEF(void)
422 finish_pass_huff (j_compress_ptr cinfo)
423 {
424   j_lossless_c_ptr losslsc = (j_lossless_c_ptr) cinfo->codec;
425   lhuff_entropy_ptr entropy = (lhuff_entropy_ptr) losslsc->entropy_private;
426   working_state state;
427
428   /* Load up working state ... flush_bits needs it */
429   state.next_output_byte = cinfo->dest->next_output_byte;
430   state.free_in_buffer = cinfo->dest->free_in_buffer;
431   ASSIGN_STATE(state.cur, entropy->saved);
432   state.cinfo = cinfo;
433
434   /* Flush out the last data */
435   if (! flush_bits(&state))
436     ERREXIT(cinfo, JERR_CANT_SUSPEND);
437
438   /* Update state */
439   cinfo->dest->next_output_byte = state.next_output_byte;
440   cinfo->dest->free_in_buffer = state.free_in_buffer;
441   ASSIGN_STATE(entropy->saved, state.cur);
442 }
443
444
445 /*
446  * Huffman coding optimization.
447  *
448  * We first scan the supplied data and count the number of uses of each symbol
449  * that is to be Huffman-coded. (This process MUST agree with the code above.)
450  * Then we build a Huffman coding tree for the observed counts.
451  * Symbols which are not needed at all for the particular image are not
452  * assigned any code, which saves space in the DHT marker as well as in
453  * the compressed data.
454  */
455
456 #ifdef ENTROPY_OPT_SUPPORTED
457
458 /*
459  * Trial-encode one nMCU's worth of Huffman-compressed differences.
460  * No data is actually output, so no suspension return is possible.
461  */
462
463 METHODDEF(JDIMENSION)
464 encode_mcus_gather (j_compress_ptr cinfo, JDIFFIMAGE diff_buf,
465         JDIMENSION MCU_row_num, JDIMENSION MCU_col_num,
466         JDIMENSION nMCU)
467 {
468   j_lossless_c_ptr losslsc = (j_lossless_c_ptr) cinfo->codec;
469   lhuff_entropy_ptr entropy = (lhuff_entropy_ptr) losslsc->entropy_private;
470   unsigned int mcu_num; 
471   int sampn, ci, yoffset, MCU_width, ptrn;
472   /* jpeg_component_info * compptr; */
473
474   /* Take care of restart intervals if needed */
475   if (cinfo->restart_interval) {
476     if (entropy->restarts_to_go == 0) {
477       /* Update restart state */
478       entropy->restarts_to_go = cinfo->restart_interval;
479     }
480     entropy->restarts_to_go--;
481   }
482
483   /* Set input pointer locations based on MCU_col_num */
484   for (ptrn = 0; ptrn < entropy->num_input_ptrs; ptrn++) {
485     ci = entropy->input_ptr_info[ptrn].ci;
486     yoffset = entropy->input_ptr_info[ptrn].yoffset;
487     MCU_width = entropy->input_ptr_info[ptrn].MCU_width;
488     entropy->input_ptr[ptrn] =
489       diff_buf[ci][MCU_row_num + yoffset] + (MCU_col_num * MCU_width);
490   }
491
492   for (mcu_num = 0; mcu_num < nMCU; mcu_num++) {
493
494     /* Inner loop handles the samples in the MCU */
495     for (sampn = 0; sampn < cinfo->data_units_in_MCU; sampn++) {
496       register int temp;
497       register int nbits;
498       /* c_derived_tbl *dctbl = entropy->cur_tbls[sampn]; */
499       long * counts = entropy->cur_counts[sampn];
500   
501       /* Encode the difference per section H.1.2.2 */
502   
503       /* Input the sample difference */
504       temp = *entropy->input_ptr[entropy->input_ptr_index[sampn]]++;
505
506       if (temp & 0x8000) {  /* instead of temp < 0 */
507   temp = (-temp) & 0x7FFF; /* absolute value, mod 2^16 */
508   if (temp == 0)    /* special case: magnitude = 32768 */
509     temp = 0x8000;
510       } else
511   temp &= 0x7FFF;    /* abs value mod 2^16 */
512
513       /* Find the number of bits needed for the magnitude of the difference */
514       nbits = 0;
515       while (temp) {
516   nbits++;
517   temp >>= 1;
518       }
519       /* Check for out-of-range difference values.
520        */
521       if (nbits > MAX_DIFF_BITS)
522   ERREXIT(cinfo, JERR_BAD_DIFF);
523   
524       /* Count the Huffman symbol for the number of bits */
525       counts[nbits]++;
526     }
527   }
528
529   return nMCU;
530 }
531
532
533 /*
534  * Finish up a statistics-gathering pass and create the new Huffman tables.
535  */
536
537 METHODDEF(void)
538 finish_pass_gather (j_compress_ptr cinfo)
539 {
540   j_lossless_c_ptr losslsc = (j_lossless_c_ptr) cinfo->codec;
541   lhuff_entropy_ptr entropy = (lhuff_entropy_ptr) losslsc->entropy_private;
542   int ci, dctbl;
543   jpeg_component_info * compptr;
544   JHUFF_TBL **htblptr;
545   boolean did_dc[NUM_HUFF_TBLS];
546
547   /* It's important not to apply jpeg_gen_optimal_table more than once
548    * per table, because it clobbers the input frequency counts!
549    */
550   MEMZERO(did_dc, SIZEOF(did_dc));
551
552   for (ci = 0; ci < cinfo->comps_in_scan; ci++) {
553     compptr = cinfo->cur_comp_info[ci];
554     dctbl = compptr->dc_tbl_no;
555     if (! did_dc[dctbl]) {
556       htblptr = & cinfo->dc_huff_tbl_ptrs[dctbl];
557       if (*htblptr == NULL)
558   *htblptr = jpeg_alloc_huff_table((j_common_ptr) cinfo);
559       jpeg_gen_optimal_table(cinfo, *htblptr, entropy->count_ptrs[dctbl]);
560       did_dc[dctbl] = TRUE;
561     }
562   }
563 }
564
565
566 #endif /* ENTROPY_OPT_SUPPORTED */
567
568
569 METHODDEF(boolean)
570 need_optimization_pass (j_compress_ptr cinfo)
571 {
572   (void)cinfo;
573   return TRUE;
574 }
575
576
577 /*
578  * Module initialization routine for Huffman entropy encoding.
579  */
580
581 GLOBAL(void)
582 jinit_lhuff_encoder (j_compress_ptr cinfo)
583 {
584   j_lossless_c_ptr losslsc = (j_lossless_c_ptr) cinfo->codec;
585   lhuff_entropy_ptr entropy;
586   int i;
587
588   entropy = (lhuff_entropy_ptr)
589     (*cinfo->mem->alloc_small) ((j_common_ptr) cinfo, JPOOL_IMAGE,
590         SIZEOF(lhuff_entropy_encoder));
591   losslsc->entropy_private = (struct jpeg_entropy_encoder *) entropy;
592   losslsc->pub.entropy_start_pass = start_pass_huff;
593   losslsc->pub.need_optimization_pass = need_optimization_pass;
594
595   /* Mark tables unallocated */
596   for (i = 0; i < NUM_HUFF_TBLS; i++) {
597     entropy->derived_tbls[i] = NULL;
598 #ifdef ENTROPY_OPT_SUPPORTED
599     entropy->count_ptrs[i] = NULL;
600 #endif
601   }
602 }