Source code: org/jfor/jfor/tools/jpeg/Huffman.java
1 /**
2 * File: Huffmann.java
3 *
4 *
5 * Date Author Changes
6 * Aug 17 01 Andreas Putz Created
7 */
8 package org.jfor.jfor.tools.jpeg;
9
10 import java.util.Vector;
11 import java.io.BufferedOutputStream;
12 import java.io.IOException;
13
14 /*-----------------------------------------------------------------------------
15 * jfor - Open-Source XSL-FO to RTF converter - see www.jfor.org
16 *
17 * ====================================================================
18 * jfor Apache-Style Software License.
19 * Copyright (c) 2002 by the jfor project. All rights reserved.
20 *
21 * Redistribution and use in source and binary forms, with or without
22 * modification, are permitted provided that the following conditions
23 * are met:
24 *
25 * 1. Redistributions of source code must retain the above copyright
26 * notice, this list of conditions and the following disclaimer.
27 *
28 * 2. Redistributions in binary form must reproduce the above copyright
29 * notice, this list of conditions and the following disclaimer in
30 * the documentation and/or other materials provided with the
31 * distribution.
32 *
33 * 3. The end-user documentation included with the redistribution,
34 * if any, must include the following acknowledgment:
35 * "This product includes software developed
36 * by the jfor project (http://www.jfor.org)."
37 * Alternately, this acknowledgment may appear in the software itself,
38 * if and wherever such third-party acknowledgments normally appear.
39 *
40 * 4. The name "jfor" must not be used to endorse
41 * or promote products derived from this software without prior written
42 * permission. For written permission, please contact info@jfor.org.
43 *
44 * 5. Products derived from this software may not be called "jfor",
45 * nor may "jfor" appear in their name, without prior written
46 * permission of info@jfor.org.
47 *
48 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
49 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
50 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
51 * DISCLAIMED. IN NO EVENT SHALL THE JFOR PROJECT OR ITS CONTRIBUTORS BE
52 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
53 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
54 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
55 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
56 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
57 * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
58 * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
59 * ====================================================================
60 * Contributor(s):
61 -----------------------------------------------------------------------------*/
62
63 /**
64 * This class was modified by James R. Weeks on 3/27/98.
65 * It now incorporates Huffman table derivation as in the C jpeg library
66 * from the IJG, Jpeg-6a.
67 */
68 class Huffman
69 {
70 //////////////////////////////////////////////////
71 // @@ Members
72 //////////////////////////////////////////////////
73
74 private int bufferPutBits;
75 private int bufferPutBuffer;
76
77 private Object DC_matrix[] = null;
78 private Object AC_matrix[] = null;
79
80 private Vector bits = null;
81 private Vector val = null;
82
83
84 //////////////////////////////////////////////////
85 // @@ Definitions
86 //////////////////////////////////////////////////
87
88 private int[] bitsDCluminance =
89 {
90 0x00, 0, 1, 5, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0
91 };
92 private int[] valDCluminance =
93 {
94 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
95 };
96 private int[] bitsDCchrominance =
97 {
98 0x01, 0, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0
99 };
100 private int[] valDCchrominance =
101 {
102 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
103 };
104 private int[] bitsACluminance =
105 {
106 0x10, 0, 2, 1, 3, 3, 2, 4, 3, 5, 5, 4, 4, 0, 0, 1, 0x7d
107 };
108 private int[] valACluminance =
109 {
110 0x01, 0x02, 0x03, 0x00, 0x04, 0x11, 0x05, 0x12, 0x21, 0x31, 0x41, 0x06, 0x13, 0x51, 0x61,
111 0x07, 0x22, 0x71, 0x14, 0x32, 0x81, 0x91, 0xa1, 0x08, 0x23, 0x42, 0xb1, 0xc1, 0x15, 0x52,
112 0xd1, 0xf0, 0x24, 0x33, 0x62, 0x72, 0x82, 0x09, 0x0a, 0x16, 0x17, 0x18, 0x19, 0x1a, 0x25,
113 0x26, 0x27, 0x28, 0x29, 0x2a, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x3a, 0x43, 0x44, 0x45,
114 0x46, 0x47, 0x48, 0x49, 0x4a, 0x53, 0x54, 0x55, 0x56, 0x57, 0x58, 0x59, 0x5a, 0x63, 0x64,
115 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78, 0x79, 0x7a, 0x83,
116 0x84, 0x85, 0x86, 0x87, 0x88, 0x89, 0x8a, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98, 0x99,
117 0x9a, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7, 0xa8, 0xa9, 0xaa, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6,
118 0xb7, 0xb8, 0xb9, 0xba, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7, 0xc8, 0xc9, 0xca, 0xd2, 0xd3,
119 0xd4, 0xd5, 0xd6, 0xd7, 0xd8, 0xd9, 0xda, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7, 0xe8,
120 0xe9, 0xea, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 0xf8, 0xf9, 0xfa
121 };
122 private int[] bitsACchrominance =
123 {
124 0x11, 0, 2, 1, 2, 4, 4, 3, 4, 7, 5, 4, 4, 0, 1, 2, 0x77
125 };
126
127 private int[] valACchrominance =
128 {
129 0x00, 0x01, 0x02, 0x03, 0x11, 0x04, 0x05, 0x21, 0x31, 0x06, 0x12, 0x41, 0x51, 0x07, 0x61,
130 0x71, 0x13, 0x22, 0x32, 0x81, 0x08, 0x14, 0x42, 0x91, 0xa1, 0xb1, 0xc1, 0x09, 0x23, 0x33,
131 0x52, 0xf0, 0x15, 0x62, 0x72, 0xd1, 0x0a, 0x16, 0x24, 0x34, 0xe1, 0x25, 0xf1, 0x17, 0x18,
132 0x19, 0x1a, 0x26, 0x27, 0x28, 0x29, 0x2a, 0x35, 0x36, 0x37, 0x38, 0x39, 0x3a, 0x43, 0x44,
133 0x45, 0x46, 0x47, 0x48, 0x49, 0x4a, 0x53, 0x54, 0x55, 0x56, 0x57, 0x58, 0x59, 0x5a, 0x63,
134 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6a, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78, 0x79, 0x7a,
135 0x82, 0x83, 0x84, 0x85, 0x86, 0x87, 0x88, 0x89, 0x8a, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97,
136 0x98, 0x99, 0x9a, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7, 0xa8, 0xa9, 0xaa, 0xb2, 0xb3, 0xb4,
137 0xb5, 0xb6, 0xb7, 0xb8, 0xb9, 0xba, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7, 0xc8, 0xc9, 0xca,
138 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 0xd8, 0xd9, 0xda, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7,
139 0xe8, 0xe9, 0xea, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 0xf8, 0xf9, 0xfa
140 };
141
142 /**
143 * jpegNaturalOrder[i] is the natural-order position of the i'th element
144 * of zigzag order.
145 */
146 static int[] jpegNaturalOrder =
147 {
148 0, 1, 8, 16, 9, 2, 3, 10, 17, 24, 32, 25, 18, 11, 4, 5, 12, 19, 26, 33, 40, 48, 41, 34, 27,
149 20, 13, 6, 7, 14, 21, 28, 35, 42, 49, 56, 57, 50, 43, 36, 29, 22, 15, 23, 30, 37, 44, 51,
150 58, 59, 52, 45, 38, 31, 39, 46, 53, 60, 61, 54, 47, 55, 62, 63,
151 };
152
153
154 //////////////////////////////////////////////////
155 // @@ Construction
156 //////////////////////////////////////////////////
157
158 /**
159 * The Huffman class constructor.
160 */
161 Huffman ()
162 {
163 bits = new Vector ();
164
165 bits.addElement (bitsDCluminance);
166 bits.addElement (bitsACluminance);
167 bits.addElement (bitsDCchrominance);
168 bits.addElement (bitsACchrominance);
169
170 val = new Vector ();
171
172 val.addElement (valDCluminance);
173 val.addElement (valACluminance);
174 val.addElement (valDCchrominance);
175 val.addElement (valACchrominance);
176 initHuf ();
177 }
178
179 /**
180 * Dispose.
181 */
182 public void dispose ()
183 {
184 DC_matrix = null;
185 AC_matrix = null;
186 bits = null;
187 val = null;
188 }
189
190
191 //////////////////////////////////////////////////
192 // @@ Member access
193 //////////////////////////////////////////////////
194
195 /**
196 * Gets the bits.
197 * @param index Index
198 * @return Integer array
199 */
200 int[] getBits (int index)
201 {
202 return (int []) bits.elementAt (index);
203 }
204
205 /**
206 * Get the values.
207 * @param index Index
208 * @return Integer array
209 */
210 int [] getVal (int index)
211 {
212 return (int []) val.elementAt (index);
213 }
214
215
216 //////////////////////////////////////////////////
217 // @@ Methods
218 //////////////////////////////////////////////////
219
220 /**
221 * HuffmanBlockEncoder run length encodes and Huffman encodes the quantized
222 * data.
223 *
224 * @param outStream Stream for output
225 * @param zigzag
226 * @param prec
227 * @param dCcode
228 * @param aCcode
229 */
230 void encodeHuffmanBlock (BufferedOutputStream outStream, int zigzag[], int prec,
231 int dCcode, int aCcode)
232 {
233 // The DC portion
234
235 int temp = zigzag[0] - prec;
236 int temp2 = temp;
237
238 if (temp < 0)
239 {
240 temp = -temp;
241 temp2--;
242 }
243
244 int nbits = 0;
245
246 while (temp != 0)
247 {
248 nbits++;
249 temp >>= 1;
250 }
251
252 // if (nbits > 11) nbits = 11;
253 bufferIt (outStream, ((int[][]) DC_matrix[dCcode])[nbits][0],
254 ((int[][]) DC_matrix[dCcode])[nbits][1]);
255
256 // The arguments in bufferIt are code and size.
257 if (nbits != 0)
258 {
259 bufferIt (outStream, temp2, nbits);
260 }
261
262 // The AC portion
263
264 int r = 0;
265
266 for (int k = 1; k < 64; k++)
267 {
268 if ((temp = zigzag[jpegNaturalOrder[k]]) == 0)
269 {
270 r++;
271 }
272 else
273 {
274 while (r > 15)
275 {
276 bufferIt (outStream, ((int[][]) AC_matrix[aCcode])[0xF0][0],
277 ((int[][]) AC_matrix[aCcode])[0xF0][1]);
278
279 r -= 16;
280 }
281
282 temp2 = temp;
283
284 if (temp < 0)
285 {
286 temp = -temp;
287 temp2--;
288 }
289
290 nbits = 1;
291
292 while ((temp >>= 1) != 0)
293 {
294 nbits++;
295 }
296
297 int i = (r << 4) + nbits;
298
299 bufferIt (outStream, ((int[][]) AC_matrix[aCcode])[i][0],
300 ((int[][]) AC_matrix[aCcode])[i][1]);
301 bufferIt (outStream, temp2, nbits);
302
303 r = 0;
304 }
305 }
306
307 if (r > 0)
308 {
309 bufferIt (outStream, ((int[][]) AC_matrix[aCcode])[0][0],
310 ((int[][]) AC_matrix[aCcode])[0][1]);
311 }
312
313 }
314
315 /**
316 * Uses an integer long (32 bits) buffer to store the Huffman encoded bits
317 * and sends them to outStream by the byte.
318 *
319 * @param outStream Stream for output
320 * @param code Code
321 * @param size Size
322 */
323 void bufferIt (BufferedOutputStream outStream, int code, int size)
324 {
325 int PutBuffer = code;
326 int PutBits = bufferPutBits;
327
328 PutBuffer &= (1 << size) - 1;
329 PutBits += size;
330 PutBuffer <<= 24 - PutBits;
331 PutBuffer |= bufferPutBuffer;
332
333 while (PutBits >= 8)
334 {
335 int c = ((PutBuffer >> 16) & 0xFF);
336
337 try
338 {
339 outStream.write (c);
340 }
341 catch (IOException e)
342 {
343 System.out.println ("IO Error: " + e.getMessage ());
344 }
345
346 if (c == 0xFF)
347 {
348 try
349 {
350 outStream.write (0);
351 }
352 catch (IOException e)
353 {
354 System.out.println ("IO Error: " + e.getMessage ());
355 }
356 }
357
358 PutBuffer <<= 8;
359 PutBits -= 8;
360 }
361
362 bufferPutBuffer = PutBuffer;
363 bufferPutBits = PutBits;
364
365 }
366
367 /**
368 * Flushed the buffer to output stream.
369 *
370 * @param outStream Stream for output
371 */
372 void flushBuffer (BufferedOutputStream outStream)
373 {
374 int PutBuffer = bufferPutBuffer;
375 int PutBits = bufferPutBits;
376
377 while (PutBits >= 8)
378 {
379 int c = ((PutBuffer >> 16) & 0xFF);
380
381 try
382 {
383 outStream.write (c);
384 }
385 catch (IOException e)
386 {
387 System.out.println ("IO Error: " + e.getMessage ());
388 }
389
390 if (c == 0xFF)
391 {
392 try
393 {
394 outStream.write (0);
395 }
396 catch (IOException e)
397 {
398 System.out.println ("IO Error: " + e.getMessage ());
399 }
400 }
401
402 PutBuffer <<= 8;
403 PutBits -= 8;
404 }
405
406 if (PutBits > 0)
407 {
408 int c = ((PutBuffer >> 16) & 0xFF);
409
410 try
411 {
412 outStream.write (c);
413 }
414 catch (IOException e)
415 {
416 System.out.println ("IO Error: " + e.getMessage ());
417 }
418 }
419 }
420
421 /**
422 * Initialisation of the Huffman codes for Luminance and Chrominance.
423 * This code results in the same tables created in the IJG Jpeg-6a
424 * library.
425 */
426 void initHuf ()
427 {
428 int[][] DC_matrix0 = new int[12][2];
429 int[][] DC_matrix1 = new int[12][2];
430 int[][] AC_matrix0 = new int[255][2];
431 int[][] AC_matrix1 = new int[255][2];
432 DC_matrix = new Object[2];
433 AC_matrix = new Object[2];
434
435 int[] huffsize = new int[257];
436 int[] huffcode = new int[257];
437
438 /*
439 * init of the DC values for the chrominance
440 * [][0] is the code [][1] is the number of bit
441 */
442
443 int p = 0;
444
445 for (int l = 1; l <= 16; l++)
446 {
447 for (int i = 1; i <= bitsDCchrominance[l]; i++)
448 {
449 huffsize[p++] = l;
450 }
451 }
452
453 huffsize[p] = 0;
454 int lastp = p;
455
456 int code = 0;
457 int si = huffsize[0];
458 p = 0;
459
460 while (huffsize[p] != 0)
461 {
462 while (huffsize[p] == si)
463 {
464 huffcode[p++] = code;
465 code++;
466 }
467
468 code <<= 1;
469 si++;
470 }
471
472 for (p = 0; p < lastp; p++)
473 {
474 DC_matrix1[valDCchrominance[p]][0] = huffcode[p];
475 DC_matrix1[valDCchrominance[p]][1] = huffsize[p];
476 }
477
478 /*
479 * Init of the AC hufmann code for the chrominance
480 * matrix [][][0] is the code & matrix[][][1] is the number of bit needed
481 */
482
483 p = 0;
484
485 for (int l = 1; l <= 16; l++)
486 {
487 for (int i = 1; i <= bitsACchrominance[l]; i++)
488 {
489 huffsize[p++] = l;
490 }
491 }
492
493 huffsize[p] = 0;
494 lastp = p;
495
496 code = 0;
497 si = huffsize[0];
498 p = 0;
499
500 while (huffsize[p] != 0)
501 {
502 while (huffsize[p] == si)
503 {
504 huffcode[p++] = code;
505 code++;
506 }
507
508 code <<= 1;
509 si++;
510 }
511
512 for (p = 0; p < lastp; p++)
513 {
514 AC_matrix1[valACchrominance[p]][0] = huffcode[p];
515 AC_matrix1[valACchrominance[p]][1] = huffsize[p];
516 }
517
518 /*
519 * init of the DC values for the luminance
520 * [][0] is the code [][1] is the number of bit
521 */
522 p = 0;
523
524 for (int l = 1; l <= 16; l++)
525 {
526 for (int i = 1; i <= bitsDCluminance[l]; i++)
527 {
528 huffsize[p++] = l;
529 }
530 }
531
532 huffsize[p] = 0;
533 lastp = p;
534
535 code = 0;
536 si = huffsize[0];
537 p = 0;
538
539 while (huffsize[p] != 0)
540 {
541 while (huffsize[p] == si)
542 {
543 huffcode[p++] = code;
544 code++;
545 }
546
547 code <<= 1;
548 si++;
549 }
550
551 for (p = 0; p < lastp; p++)
552 {
553 DC_matrix0[valDCluminance[p]][0] = huffcode[p];
554 DC_matrix0[valDCluminance[p]][1] = huffsize[p];
555 }
556
557 /*
558 * Init of the AC hufmann code for luminance
559 * matrix [][][0] is the code & matrix[][][1] is the number of bit
560 */
561
562 p = 0;
563
564 for (int l = 1; l <= 16; l++)
565 {
566 for (int i = 1; i <= bitsACluminance[l]; i++)
567 {
568 huffsize[p++] = l;
569 }
570 }
571
572 huffsize[p] = 0;
573 lastp = p;
574
575 code = 0;
576 si = huffsize[0];
577 p = 0;
578
579 while (huffsize[p] != 0)
580 {
581 while (huffsize[p] == si)
582 {
583 huffcode[p++] = code;
584 code++;
585 }
586
587 code <<= 1;
588 si++;
589 }
590
591 for (int q = 0; q < lastp; q++)
592 {
593 AC_matrix0[valACluminance[q]][0] = huffcode[q];
594 AC_matrix0[valACluminance[q]][1] = huffsize[q];
595 }
596
597 DC_matrix[0] = DC_matrix0;
598 DC_matrix[1] = DC_matrix1;
599 AC_matrix[0] = AC_matrix0;
600 AC_matrix[1] = AC_matrix1;
601 }
602 }