1 /*************************************************************
2 Copyright (C) 1990, 1991, 1993 Andy C. Hung, all rights reserved.
3 PUBLIC DOMAIN LICENSE: Stanford University Portable Video Research
4 Group. If you use this software, you agree to the following: This
5 program package is purely experimental, and is licensed "as is".
6 Permission is granted to use, modify, and distribute this program
7 without charge for any purpose, provided this license/ disclaimer
8 notice appears in the copies. No warranty or maintenance is given,
9 either expressed or implied. In no event shall the author(s) be
10 liable to you or a third party for any special, incidental,
11 consequential, or other damages, arising out of the use or inability
12 to use the program for any purpose (or the loss of data), even if we
13 have been advised of such possibilities. Any public reference or
14 advertisement of this source code should refer to it as the Portable
15 Video Research Group (PVRG) code, and not by any author(s) (or
16 Stanford University) name.
17 *************************************************************/
18
19 /*
20 ************************************************************
21 huffman.c
22
23 This file represents the core Huffman routines, most of them
24 implemented with the JPEG reference. These routines are not very fast
25 and can be improved, but comprise very little of software run-time.
26
27 ************************************************************
28 */
29
30 /*LABEL huffman.c */
31
32 /* Include files */
33
34 #include "globals.h"
35 #include "stream.h"
36 #include <stdlib.h> /* exit */
37
38 /*PUBLIC*/
39
40 static void CodeSize();
41 static void CountBits();
42 static void AdjustBits();
43 static void SortInput();
44 static void SizeTable();
45 static void CodeTable();
46 static void OrderCodes();
47 static void DecoderTables();
48
49 extern void MakeHuffman();
50 extern void SpecifiedHuffman();
51 extern void MakeDecoderHuffman();
52 extern void ReadHuffman();
53 extern void WriteHuffman();
54 extern int DecodeHuffman();
55 extern void EncodeHuffman();
56 extern void MakeXhuff();
57 extern void MakeEhuff();
58 extern void MakeDhuff();
59 extern void UseACHuffman();
60 extern void UseDCHuffman();
61 extern void SetACHuffman();
62 extern void SetDCHuffman();
63 extern void PrintHuffman();
64 extern void PrintTable();
65
66 /*PRIVATE*/
67
68 extern int Loud;
69 extern int ErrorValue;
70 extern IMAGE *CImage;
71 extern FRAME *CFrame;
72 extern SCAN *CScan;
73
74
75 static int frequency[257];
76 static int codesize[257];
77 static int huffsize[257];
78 static int huffcode[257];
79 static int lastp;
80 static int others[257];
81 static XHUFF *Xhuff=NULL;
82 static DHUFF *Dhuff=NULL;
83 static EHUFF *Ehuff=NULL;
84
85 #define fgetb megetb
86 #define fputv meputv
87
88 #define ClearFrequency() \
89 {int *cfip; for(cfip=frequency;cfip<frequency+257;*(cfip++)=0);}
90 #define ClearCodeSize() \
91 {int *ccsip; for(ccsip=codesize;ccsip<codesize+257;*(ccsip++)=0);}
92 #define ClearOthers() \
93 {int *coip; for(coip=others;coip<others+257;*(coip++)= -1);}
94 #define ClearBits() \
95 {int *cbip; for(cbip=Xhuff->bits;cbip<Xhuff->bits+36;*(cbip++)=0);}
96 #define ClearEcodes() \
97 {int *cip,*dip;dip=Ehuff->ehufsi;cip=Ehuff->ehufco;\
98 while(cip<codesize+257){*(cip++)=0; *(dip++)=0;}}
99
100 /*START*/
101
102 /*BFUNC
103
104 CodeSize() is used to size up which codes are found. This part merely
105 generates a series of code lengths of which any particular usage is
106 determined by the order of frequency of access. Note that the code
107 word associated with 0xffff has been restricted.
108
109 EFUNC*/
110
CodeSize()111 static void CodeSize()
112 {
113 BEGIN("CodeSize")
114 int *cfip,i;
115 int least_value,next_least_value;
116 int least_value_index,next_least_value_index;
117
118 frequency[256] = 1; /* Add an extra code to ensure 0xffff not taken. */
119 ClearCodeSize();
120 ClearOthers();
121 while(1)
122 {
123 least_value = next_least_value = 0x7fffffff; /* largest word */
124 least_value_index = next_least_value_index = -1;
125 cfip = frequency;
126 for(i=0;i<257;i++) /* Find two smallest values */
127 {
128 if (*cfip)
129 {
130 if (*cfip <= least_value)
131 {
132 next_least_value = least_value;
133 least_value = *cfip;
134 next_least_value_index = least_value_index;
135 least_value_index = i;
136 }
137 else if (*cfip <= next_least_value)
138 {
139 next_least_value = *cfip;
140 next_least_value_index = i;
141 }
142 }
143 cfip++;
144 }
145 if (next_least_value_index == -1) /* If only one value, finished */
146 {
147 break;
148 }
149 frequency[least_value_index] += frequency[next_least_value_index];
150 frequency[next_least_value_index] = 0;
151 codesize[least_value_index]++;
152 while(others[least_value_index] != -1)
153 {
154 least_value_index = others[least_value_index];
155 codesize[least_value_index]++;
156 }
157 others[least_value_index] = next_least_value_index;
158 do
159 {
160 codesize[next_least_value_index]++;
161 }
162 while((next_least_value_index = others[next_least_value_index]) != -1);
163 }
164 }
165
166 /*BFUNC
167
168 CountBits() tabulates a histogram of the number of codes with a give
169 bit-length.
170
171 EFUNC*/
172
CountBits()173 static void CountBits()
174 {
175 BEGIN("CountBits")
176 int *csptr;
177
178 ClearBits();
179 for(csptr=codesize+256;csptr>=codesize;csptr--)
180 {
181 if (*csptr)
182 {
183 Xhuff->bits[*csptr]++;
184 }
185 }
186 }
187
188 /*BFUNC
189
190 AdjustBits() is used to trim the Huffman code tree into 16 bit code
191 words only.
192
193 EFUNC*/
194
AdjustBits()195 static void AdjustBits()
196 {
197 BEGIN("AdjustBits")
198 int i,j;
199
200 i=32;
201 while(1)
202 {
203 if (Xhuff->bits[i]>0)
204 {
205 j = i-1;
206 while(!Xhuff->bits[--j]); /* Change from JPEG Manual */
207 Xhuff->bits[i] -= 2; /* Remove 2 of the longest hufco */
208 Xhuff->bits[i-1]++; /* Add one hufco to its prefix */
209 Xhuff->bits[j]--; /* Remove hufco from next length */
210 Xhuff->bits[j+1] += 2; /* to be prefix to one hufco */
211 } /* from j term and the one */
212 /* hufco from the i (longest) term.*/
213 else if (--i==16)
214 {
215 break;
216 }
217 }
218 while(!Xhuff->bits[i]) /* If fortunate enough not to use */
219 { /* any 16 bit codes, then find out */
220 i--; /* where last codes are. */
221 }
222 Xhuff->bits[i]--; /* Get rid of the extra code that generated 0xffff */
223 }
224
225 /*BFUNC
226
227 SortInput() assembles the codes in increasing order with code length.
228 Since we know the bit-lengths in increasing order, they will
229 correspond to the codes with decreasing frequency. This sort is O(mn),),
230 not the greatest.
231
232 EFUNC*/
233
SortInput()234 static void SortInput()
235 {
236 BEGIN("SortInput")
237 int i,j,p;
238
239 for(p=0,i=1;i<33;i++) /* Designate a length in i. */
240 {
241 for(j=0;j<256;j++) /* Find all codes with a given length. */
242 {
243 if (codesize[j]==i)
244 {
245 Xhuff->huffval[p++] = j; /* Add that value to be associated */
246 } /* with the next largest code. */
247 }
248 }
249 }
250
251 /*BFUNC
252
253 SizeTable() is used to associate a size with the code in increasing
254 length. For example, it would be 44556677... in huffsize[]. Lastp is
255 the number of codes used.
256
257 EFUNC*/
258
SizeTable()259 static void SizeTable()
260 {
261 BEGIN("SizeTable")
262 int i,j,p;
263
264 for(p=0,i=1;i<17;i++)
265 {
266 for(j=1;j<=Xhuff->bits[i];j++)
267 {
268 huffsize[p++] = i;
269 }
270 }
271 huffsize[p] = 0;
272 lastp = p;
273 }
274
275
276 /*BFUNC
277
278 CodeTable() is used to generate the codes once the hufsizes are known.
279
280 EFUNC*/
281
CodeTable()282 static void CodeTable()
283 {
284 BEGIN("CodeTable")
285 int p,code,size;
286
287 p=0;
288 code=0;
289 size = huffsize[0];
290 while(1)
291 {
292 do
293 {
294 huffcode[p++] = code++;
295 }
296 while((huffsize[p]==size)&&(p<257)); /* Overflow Detection */
297 if (!huffsize[p]) /* All finished. */
298 {
299 break;
300 }
301 do /* Shift next code to expand prefix. */
302 {
303 code <<= 1;
304 size++;
305 }
306 while(huffsize[p] != size);
307 }
308 }
309
310 /*BFUNC
311
312 OrderCodes() reorders from the monotonically increasing Huffman-code
313 words into an array which is indexed on the actual value represented
314 by the codes. This converts the Xhuff structure into an Ehuff
315 structure.
316
317 EFUNC*/
318
OrderCodes()319 static void OrderCodes()
320 {
321 BEGIN("OrderCodes")
322 int index,p;
323
324 for(p=0;p<lastp;p++)
325 {
326 index = Xhuff->huffval[p];
327 Ehuff->ehufco[index] = huffcode[p];
328 Ehuff->ehufsi[index] = huffsize[p];
329 }
330 }
331
332 /*BFUNC
333
334 DecoderTables() takes the Xhuff and converts it to a form suitable for
335 the JPEG suggested decoder. This is not the fastest method but it is
336 the reference method.
337
338 EFUNC*/
339
DecoderTables()340 static void DecoderTables()
341 {
342 BEGIN("DecoderTables")
343 int l,p;
344
345 for(Dhuff->ml=1,p=0,l=1;l<=16;l++)
346 {
347 if (Xhuff->bits[l]==0)
348 {
349 Dhuff->maxcode[l] = -1; /* Watch out JPEG is wrong here */
350 } /* We use -1 to indicate skipping. */
351 else
352 {
353 Dhuff->valptr[l]=p;
354 Dhuff->mincode[l]=huffcode[p];
355 p+=Xhuff->bits[l]-1;
356 Dhuff->maxcode[l]=huffcode[p];
357 Dhuff->ml = l;
358 p++;
359 }
360 }
361 Dhuff->maxcode[Dhuff->ml]++;
362 }
363
364 /*BFUNC
365
366 MakeHuffman() is used to create the Huffman table from the frequency
367 passed into it.
368
369 EFUNC*/
370
MakeHuffman(freq)371 void MakeHuffman(freq)
372 int *freq;
373 {
374 BEGIN("MakeHuffman")
375 int *ptr;
376
377 for(ptr=frequency;ptr<frequency+256;ptr++)
378 *ptr= *(freq++);
379
380 CodeSize();
381 CountBits();
382 AdjustBits();
383 SortInput();
384 SizeTable(); /*From Xhuff to Ehuff */
385 CodeTable();
386 OrderCodes();
387 }
388
389 /*BFUNC
390
391 SpecifiedHuffman() is used to create the Huffman table from the bits
392 and the huffvals passed into it.
393
394 EFUNC*/
395
SpecifiedHuffman(bts,hvls)396 void SpecifiedHuffman(bts,hvls)
397 int *bts;
398 int *hvls;
399 {
400 BEGIN("MakeHuffman")
401 int i;
402 int accum;
403
404 for(accum=0,i=0;i<16;i++)
405 {
406 accum+= bts[i];
407 Xhuff->bits[i+1] = bts[i]; /* Shift offset for internal specs.*/
408 }
409 for(i=0;i<accum;i++)
410 {
411 Xhuff->huffval[i] = hvls[i];
412 }
413 SizeTable(); /*From Xhuff to Ehuff */
414 CodeTable();
415 OrderCodes();
416 }
417
418 /*BFUNC
419
420 MakeDecoderHuffman() creates the decoder tables from the Xhuff structure.
421
422 EFUNC*/
423
MakeDecoderHuffman()424 void MakeDecoderHuffman()
425 {
426 BEGIN("MakeDecoderHuffman")
427
428 SizeTable();
429 CodeTable();
430 DecoderTables();
431 }
432
433 /*BFUNC
434
435 ReadHuffman() reads in a Huffman structure from the currently open
436 stream.
437
438 EFUNC*/
439
ReadHuffman()440 void ReadHuffman()
441 {
442 BEGIN("ReadHuffman")
443 int i,accum;
444
445 for(accum=0,i=1;i<=16;i++)
446 {
447 Xhuff->bits[i]=bgetc();
448 accum += Xhuff->bits[i];
449 }
450 if (Loud > NOISY)
451 {
452 printf("Huffman Read In:\n");
453 printf("NUMBER OF CODES %d\n",accum);
454 }
455 for(i=0;i<accum;i++)
456 {
457 Xhuff->huffval[i] = bgetc();
458 }
459 SizeTable();
460 CodeTable();
461 DecoderTables();
462 if (Loud > NOISY)
463 {
464 printf("Huffman Read In:\n");
465 for(i=1;i<=16;i++)
466 {
467 printf("DHUFF->MAXCODE DHUFF->MINCODE DHUFF->VALPTR %d %d %d\n",
468 Dhuff->maxcode[i],Dhuff->mincode[i],Dhuff->valptr[i]);
469 }
470 }
471 }
472
473 /*BFUNC
474
475 WriteHuffman() writes the Huffman out to the stream. This Huffman
476 structure is written from the Xhuff structure.
477
478 EFUNC*/
479
WriteHuffman()480 void WriteHuffman()
481 {
482 BEGIN("WriteHuffman")
483 int i,accum;
484
485 if (Xhuff)
486 {
487 for(accum=0,i=1;i<=16;i++)
488 {
489 bputc(Xhuff->bits[i]);
490 accum += Xhuff->bits[i];
491 }
492 for(i=0;i<accum;i++)
493 {
494 bputc(Xhuff->huffval[i]);
495 }
496 }
497 else
498 {
499 WHEREAMI();
500 printf("Null Huffman table found.\n");
501 }
502 }
503
504 /*BFUNC
505
506 DecodeHuffman() returns the value decoded from the Huffman stream.
507 The Dhuff must be loaded before this function be called.
508
509 EFUNC*/
510
DecodeHuffman()511 int DecodeHuffman()
512 {
513 BEGIN("DecodeHuffman")
514 int code,l,p;
515
516 if (!Dhuff)
517 {
518 WHEREAMI();
519 printf("Unreferenced decoder Huffman table!\n");
520 exit(ERROR_HUFFMAN_READ);
521 }
522 code = fgetb();
523 for(l=1;code>Dhuff->maxcode[l];l++)
524 {
525 if (Loud > WHISPER)
526 {
527 WHEREAMI();
528 printf("CurrentCode=%d Length=%d Dhuff->Maxcode=%d\n",
529 code,l,Dhuff->maxcode[l]);
530 }
531 code= (code<<1)+fgetb();
532 }
533 if(code<Dhuff->maxcode[Dhuff->ml])
534 {
535 p = Dhuff->valptr[l] + code - Dhuff->mincode[l];
536 if (Loud > WHISPER)
537 {
538 WHEREAMI();
539 printf("HuffmanDecoded code: %d value: %d\n",p,Xhuff->huffval[p]);
540 }
541 return(Xhuff->huffval[p]);
542 }
543 else
544 {
545 WHEREAMI();
546 /*printf("Huffman read error: l=%d code=%d\n");*/
547 Resync();
548 ErrorValue = ERROR_HUFFMAN_READ;
549 return(0);
550 }
551 }
552
553 /*BFUNC
554
555 EncodeHuffman() places the Huffman code for the value onto the stream.
556
557 EFUNC*/
558
EncodeHuffman(value)559 void EncodeHuffman(value)
560 int value;
561 {
562 BEGIN("EncodeHuffman")
563
564 if (Loud > WHISPER)
565 {
566 WHEREAMI();
567 printf("HUFFMAN_OUTPUT value=%d Ehuff->ehufsi=%d Ehuff->ehufco=%d\n",
568 value,Ehuff->ehufsi[value],Ehuff->ehufco[value]);
569 }
570 if (!Ehuff)
571 {
572 WHEREAMI();
573 printf("Encoding with Null Huffman table.\n");
574 exit(ERROR_HUFFMAN_ENCODE);
575 }
576 if (Ehuff->ehufsi[value])
577 {
578 fputv(Ehuff->ehufsi[value],Ehuff->ehufco[value]);
579 }
580 else
581 {
582 WHEREAMI();
583 printf("Null Code for [%d] Encountered:\n",value);
584 printf("*** Dumping Huffman Table ***\n");
585 PrintHuffman();
586 printf("***\n");
587 ErrorValue = ERROR_HUFFMAN_ENCODE;
588 exit(ErrorValue);
589 }
590 }
591
592 /*BFUNC
593
594 MakeXhuff() creates a Huffman structure and puts it into the current
595 slot.
596
597 EFUNC*/
598
MakeXhuff()599 void MakeXhuff()
600 {
601 BEGIN("MakeXhuff")
602
603 if (!(Xhuff = MakeStructure(XHUFF)))
604 {
605 WHEREAMI();
606 printf("Cannot allocate memory for Xhuff structure.\n");
607 exit(ERROR_MEMORY);
608 }
609 }
610
611 /*BFUNC
612
613 MakeEhuff() creates a Huffman structure and puts it into the current
614 slot.
615
616 EFUNC*/
617
MakeEhuff()618 void MakeEhuff()
619 {
620 BEGIN("MakeEhuff")
621
622 if (!(Ehuff = MakeStructure(EHUFF)))
623 {
624 WHEREAMI();
625 printf("Cannot allocate memory for Ehuff structure.\n");
626 exit(ERROR_MEMORY);
627 }
628 }
629
630 /*BFUNC
631
632 MakeDhuff() creates a Huffman structure and puts it into the current
633 slot.
634
635 EFUNC*/
636
MakeDhuff()637 void MakeDhuff()
638 {
639 BEGIN("MakeDhuff")
640
641 if (!(Dhuff = MakeStructure(DHUFF)))
642 {
643 WHEREAMI();
644 printf("Cannot allocate memory for Dhuff structure.\n");
645 exit(ERROR_MEMORY);
646 }
647 }
648
649 /*BFUNC
650
651 UseACHuffman() installs the appropriate Huffman structure from the
652 CImage structure.
653
654 EFUNC*/
655
UseACHuffman(index)656 void UseACHuffman(index)
657 int index;
658 {
659 BEGIN("UseACHuffman")
660
661 Xhuff = CImage->ACXhuff[index];
662 Dhuff = CImage->ACDhuff[index];
663 Ehuff = CImage->ACEhuff[index];
664 if (!Dhuff && !Ehuff)
665 {
666 WHEREAMI();
667 printf("Reference to nonexistent table %d.\n",index);
668 }
669 }
670
671 /*BFUNC
672
673 UseDCHuffman() installs the DC Huffman structure from the CImage
674 structure.
675
676 EFUNC*/
677
UseDCHuffman(index)678 void UseDCHuffman(index)
679 int index;
680 {
681 BEGIN("UseDCHuffman")
682
683 Xhuff = CImage->DCXhuff[index];
684 Dhuff = CImage->DCDhuff[index];
685 Ehuff = CImage->DCEhuff[index];
686 if (!Dhuff && !Ehuff)
687 {
688 WHEREAMI();
689 printf("Reference to nonexistent table %d.\n",index);
690 }
691 }
692
693 /*BFUNC
694
695 SetACHuffman() sets the CImage structure contents to be the current
696 Huffman structure.
697
698 EFUNC*/
699
SetACHuffman(index)700 void SetACHuffman(index)
701 int index;
702 {
703 BEGIN("SetACHuffman")
704
705 CImage->ACXhuff[index] = Xhuff;
706 CImage->ACDhuff[index] = Dhuff;
707 CImage->ACEhuff[index] = Ehuff;
708 }
709
710 /*BFUNC
711
712 SetDCHuffman() sets the CImage structure contents to be the current
713 Huffman structure.
714
715 EFUNC*/
716
SetDCHuffman(index)717 void SetDCHuffman(index)
718 int index;
719 {
720 BEGIN("SetDCHuffman")
721
722 CImage->DCXhuff[index] = Xhuff;
723 CImage->DCDhuff[index] = Dhuff;
724 CImage->DCEhuff[index] = Ehuff;
725 }
726
727 /*BFUNC
728
729 PrintHuffman() prints out the current Huffman structure.
730
731 EFUNC*/
732
PrintHuffman()733 void PrintHuffman()
734 {
735 BEGIN("PrintHuffman")
736 int i;
737
738 if (Xhuff)
739 {
740 printf("Xhuff ID: %p\n",(void*)Xhuff);
741 printf("Bits: [length:number]\n");
742 for(i=1;i<9;i++)
743 {
744 printf("[%d:%d]",i,Xhuff->bits[i]);
745 }
746 printf("\n");
747 for(i=9;i<17;i++)
748 {
749 printf("[%d:%d]",i,Xhuff->bits[i]);
750 }
751 printf("\n");
752
753 printf("Huffval:\n");
754 PrintTable(Xhuff->huffval);
755 }
756 if (Ehuff)
757 {
758 printf("Ehuff ID: %p\n",(void*)Ehuff);
759 printf("Ehufco:\n");
760 PrintTable(Ehuff->ehufco);
761 printf("Ehufsi:\n");
762 PrintTable(Ehuff->ehufsi);
763 }
764 if (Dhuff)
765 {
766 printf("Dhuff ID: %p\n",(void*)Dhuff);
767 printf("MaxLength: %d\n",Dhuff->ml);
768 printf("[index:MaxCode:MinCode:ValPtr]\n");
769 for(i=1;i<5;i++)
770 {
771 printf("[%d:%2x:%2x:%2x]",
772 i,
773 Dhuff->maxcode[i],
774 Dhuff->mincode[i],
775 Dhuff->valptr[i]);
776 }
777 printf("\n");
778 for(i=5;i<9;i++)
779 {
780 printf("[%d:%2x:%2x:%2x]",
781 i,
782 Dhuff->maxcode[i],
783 Dhuff->mincode[i],
784 Dhuff->valptr[i]);
785 }
786 printf("\n");
787 for(i=9;i<13;i++)
788 {
789 printf("[%d:%2x:%2x:%2x]",
790 i,
791 Dhuff->maxcode[i],
792 Dhuff->mincode[i],
793 Dhuff->valptr[i]);
794 }
795 printf("\n");
796 for(i=13;i<17;i++)
797 {
798 printf("[%d:%2x:%2x:%2x]",
799 i,
800 Dhuff->maxcode[i],
801 Dhuff->mincode[i],
802 Dhuff->valptr[i]);
803 }
804 printf("\n");
805 }
806 }
807
808 /*BFUNC
809
810 PrintTable() prints out a table to the screen. The table is assumed to
811 be a 16x16 matrix represented by a single integer pointer.
812
813 EFUNC*/
814
PrintTable(table)815 void PrintTable(table)
816 int *table;
817 {
818 BEGIN("PrintTable")
819 int i,j;
820
821 for(i=0;i<16;i++)
822 {
823 for(j=0;j<16;j++)
824 {
825 printf("%2x ",*(table++));
826 }
827 printf("\n");
828 }
829 }
830
831
832
833 /*END*/
834