Richard Boegli's CnC_Generals_Zero_Hour Fork WIP
This is documentation of Richard Boegil's Zero Hour Fork
 
Loading...
Searching...
No Matches
huffencode.cpp
Go to the documentation of this file.
1/*
2** Command & Conquer Generals Zero Hour(tm)
3** Copyright 2025 Electronic Arts Inc.
4**
5** This program is free software: you can redistribute it and/or modify
6** it under the terms of the GNU General Public License as published by
7** the Free Software Foundation, either version 3 of the License, or
8** (at your option) any later version.
9**
10** This program is distributed in the hope that it will be useful,
11** but WITHOUT ANY WARRANTY; without even the implied warranty of
12** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13** GNU General Public License for more details.
14**
15** You should have received a copy of the GNU General Public License
16** along with this program. If not, see <http://www.gnu.org/licenses/>.
17*/
18
19// Copyright (C) Electronic Arts Canada Inc. 1995-2002. All rights reserved.
20
21#ifndef __HUFWRITE
22#define __HUFWRITE 1
23
24#include <string.h>
25#include "codex.h"
26#include "huffcodex.h"
27
28/****************************************************************/
29/* Internal Functions */
30/****************************************************************/
31
32struct HUFFMemStruct
33{
34 char *ptr;
35 int len;
36};
37
38#define HUFFBIGNUM 32000
39#define HUFFTREESIZE 520
40#define HUFFCODES 256
41#define HUFFMAXBITS 16
42#define HUFFREPTBL 252
43
44struct HuffEncodeContext
45{
46 char qleapcode[HUFFCODES];
47 unsigned int count[768];
48 unsigned int bitnum[HUFFMAXBITS+1];
49 unsigned int repbits[HUFFREPTBL];
50 unsigned int repbase[HUFFREPTBL];
51 unsigned int tree_left[HUFFTREESIZE];
52 unsigned int tree_right[HUFFTREESIZE];
53 unsigned int bitsarray[HUFFCODES];
54 unsigned int patternarray[HUFFCODES];
55 unsigned int masks[17];
56 unsigned int packbits;
57 unsigned int workpattern;
58 unsigned char *buffer;
59 unsigned char *bufptr;
60 int flen;
61 unsigned int csum;
62 unsigned int mostbits;
63 unsigned int codes;
64 unsigned int chainused;
65 unsigned int clue;
66 unsigned int dclue;
67 unsigned int clues;
68 unsigned int dclues;
69 int mindelta;
70 int maxdelta;
71 unsigned int plen;
72 unsigned int ulen;
73 unsigned int sortptr[HUFFCODES];
74};
75
76static void HUFF_deltabytes(const void *source,void *dest,int len)
77{
78 const unsigned char *s = (const unsigned char *) source;
79 unsigned char *d = (unsigned char *) dest;
80 unsigned char c;
81 unsigned char c1;
82 const unsigned char *send;
83
84 c = '\0';
85 send = s+len;
86 while (s<send)
87 {
88 c1 = *s++;
89 *d++ = (unsigned char)(c1-c);
90 c = c1;
91 }
92}
93
94
95static void HUFF_writebits(struct HuffEncodeContext *EC,
96 struct HUFFMemStruct *dest,
97 unsigned int bitpattern,
98 unsigned int len)
99{
100 if (len > 16)
101 {
102 HUFF_writebits(EC,dest,(unsigned int) (bitpattern>>16), len-16);
103 HUFF_writebits(EC,dest,(unsigned int) bitpattern, 16);
104 }
105 else
106 {
107 EC->packbits += len;
108 EC->workpattern += (bitpattern & EC->masks[len]) << (24-EC->packbits);
109 while (EC->packbits > 7)
110 {
111 *(dest->ptr+dest->len) = (unsigned char) (EC->workpattern >> 16);
112 ++dest->len;
113
114 EC->workpattern = EC->workpattern << 8;
115 EC->packbits -= 8;
116 ++EC->plen;
117 }
118 }
119}
120
121static void HUFF_treechase(struct HuffEncodeContext *EC,
122 unsigned int node,
123 unsigned int bits)
124{
125 if (node < HUFFCODES)
126 EC->bitsarray[node] = bits;
127 else
128 { HUFF_treechase(EC,EC->tree_left[node], bits+1);
129 HUFF_treechase(EC,EC->tree_right[node], bits+1);
130 }
131}
132
133static void HUFF_maketree(struct HuffEncodeContext *EC)
134{
135 unsigned int i, i1;
136 unsigned int ptr1;
137 unsigned int val1, val2;
138
139 unsigned int ptr2, nodes;
140
141 unsigned int list_count[HUFFCODES+2];
142 unsigned int list_ptr[HUFFCODES+2];
143
144/* initialize tree */
145
146/* registers vars usage
147 i - code
148 i1 - code index (number of unjoined codes)
149 i2 -
150 i3 -
151*/
152
153 nodes = HUFFCODES;
154 i1 = 0;
155 list_count[i1++] = 0L;
156 for (i=0; i<HUFFCODES; ++i)
157 { EC->bitsarray[i] = 99;
158 if (EC->count[i])
159 { list_count[i1] = (unsigned int) EC->count[i];
160 list_ptr[i1++] = i;
161 }
162 }
163 EC->codes = i1-1;
164
165/* make tree */
166
167/* registers vars usage
168 i - code index/temp
169 i1 - number of unjoined codes
170 i2 -
171 i3 -
172*/
173
174 if (i1>2)
175 {
176 while (i1>2)
177 {
178 /* get 2 smallest node counts */
179
180 i = i1;
181 val1 = list_count[--i]; /* initialize 2 values */
182 ptr1 = i;
183 val2 = list_count[--i];
184 ptr2 = i;
185 if (val1 < val2)
186 { val2 = val1;
187 ptr2 = ptr1;
188 val1 = list_count[i];
189 ptr1 = i;
190 }
191
192 while (i)
193 { --i;
194 while (list_count[i] > val1)
195 --i;
196
197 if (i)
198 { val1 = list_count[i];
199 ptr1 = i;
200 if (val1 <= val2)
201 { val1 = val2;
202 ptr1 = ptr2;
203 val2 = list_count[i];
204 ptr2 = i;
205 }
206 }
207 }
208
209 EC->tree_left[nodes] = list_ptr[ptr1];
210 EC->tree_right[nodes] = list_ptr[ptr2];
211 list_count[ptr1] = val1 + val2;
212 list_ptr[ptr1] = nodes;
213 list_count[ptr2] = list_count[--i1];
214 list_ptr[ptr2] = list_ptr[i1];
215 ++nodes;
216 }
217
218 /* traverse tree */
219
220 HUFF_treechase(EC,nodes-1, 0);
221 }
222 else
223 {
224 /* traverse tree */
225
226 HUFF_treechase(EC,list_ptr[EC->codes], 1);
227 }
228}
229
230static int HUFF_minrep(struct HuffEncodeContext *EC,
231 unsigned int remaining,
232 unsigned int r)
233{
234 int min, min1, use, newremaining;
235
236 if (r)
237 { min = HUFF_minrep(EC,remaining, r-1);
238 if (EC->count[EC->clue+r])
239 { use = remaining/r;
240 newremaining = remaining-(use*r);
241 min1 = HUFF_minrep(EC,newremaining, r-1)+EC->bitsarray[EC->clue+r]*use;
242 if (min1<min)
243 min = min1;
244 }
245 }
246 else
247 { min = 0;
248 if (remaining)
249 { min = 20;
250 if (remaining<HUFFREPTBL)
251 min = EC->bitsarray[EC->clue]+3+EC->repbits[remaining]*2;
252 }
253 }
254 return(min);
255}
256
257static void HUFF_writenum(struct HuffEncodeContext *EC,
258 struct HUFFMemStruct *dest,
259 unsigned int num)
260{
261 unsigned int dphuf;
262 unsigned int dbase;
263
264 if (num<HUFFREPTBL)
265 { dphuf = EC->repbits[(unsigned int) num];
266 dbase = (unsigned int) EC->repbase[(unsigned int) num];
267 }
268 else
269 { if (num<508L)
270 { dphuf = 6;
271 dbase = 252L;
272 }
273 else if (num<1020L)
274 { dphuf = 7;
275 dbase = 508L;
276 }
277 else if (num<2044L)
278 { dphuf = 8;
279 dbase = 1020L;
280 }
281 else if (num<4092L)
282 { dphuf = 9;
283 dbase = 2044L;
284 }
285 else if (num<8188L)
286 { dphuf = 10;
287 dbase = 4092L;
288 }
289 else if (num<16380L)
290 { dphuf = 11;
291 dbase = 8188L;
292 }
293 else if (num<32764L)
294 { dphuf = 12;
295 dbase = 16380L;
296 }
297 else if (num<65532L)
298 { dphuf = 13;
299 dbase = 32764L;
300 }
301 else if (num<131068L)
302 { dphuf = 14;
303 dbase = 65532L;
304 }
305 else if (num<262140L)
306 { dphuf = 15;
307 dbase = 131068L;
308 }
309 else if (num<524288L)
310 { dphuf = 16;
311 dbase = 262140L;
312 }
313 else if (num<1048576L)
314 { dphuf = 17;
315 dbase = 524288L;
316 }
317 else
318 { dphuf = 18;
319 dbase = 1048576L;
320 }
321 }
322 HUFF_writebits(EC,dest,(unsigned int) 0x00000001, dphuf+1);
323 HUFF_writebits(EC,dest,(unsigned int) (num - dbase), dphuf+2);
324}
325
326/* write explicite byte ([clue] 0gn [0] [byte]) */
327
328static void HUFF_writeexp(struct HuffEncodeContext *EC,
329 struct HUFFMemStruct *dest,
330 unsigned int code)
331{
332 HUFF_writebits(EC,dest,EC->patternarray[EC->clue], EC->bitsarray[EC->clue]);
333 HUFF_writenum(EC,dest,0L);
334 HUFF_writebits(EC,dest,(unsigned int) code, 9);
335}
336
337static void HUFF_writecode(struct HuffEncodeContext *EC,
338 struct HUFFMemStruct *dest,
339 unsigned int code)
340{
341 if (code==EC->clue)
342 HUFF_writeexp(EC,dest,code);
343 else
344 HUFF_writebits(EC,dest,EC->patternarray[code], EC->bitsarray[code]);
345}
346
347static void HUFF_init(struct HuffEncodeContext *EC)
348{
349 unsigned int i;
350
351/* precalculate repeat field lengths */
352
353/* registers vars usage
354 i - num
355 i1 -
356 i2 -
357 i3 -
358*/
359
360 i = 0;
361 while (i<4)
362 { EC->repbits[i] = 0;
363 EC->repbase[i++] = 0L;
364 }
365 while (i<12)
366 { EC->repbits[i] = 1;
367 EC->repbase[i++] = 4L;
368 }
369 while (i<28)
370 { EC->repbits[i] = 2;
371 EC->repbase[i++] = 12L;
372 }
373 while (i<60)
374 { EC->repbits[i] = 3;
375 EC->repbase[i++] = 28L;
376 }
377 while (i<124)
378 { EC->repbits[i] = 4;
379 EC->repbase[i++] = 60L;
380 }
381 while (i<252)
382 { EC->repbits[i] = 5;
383 EC->repbase[i++] = 124L;
384 }
385}
386
387
388static void HUFF_analysis(struct HuffEncodeContext *EC,
389 unsigned int opt,
390 unsigned int chainsaw)
391{
392 unsigned char *bptr1;
393 unsigned char *bptr2;
394 unsigned int i;
395 unsigned int i1;
396 unsigned int i2=0;
397 unsigned int i3;
398
399 unsigned int thres=0;
400 int di;
401 unsigned int pattern;
402 unsigned int rep1;
403 unsigned int repn;
404 unsigned int ncode;
405 unsigned int irep;
406 unsigned int remaining;
407
408 unsigned int count2[HUFFCODES];
409 unsigned int dcount[HUFFCODES];
410
411/* count file (pass 1) */
412
413/* registers vars usage
414 i - current byte
415 i1 - previous byte
416 i2 - rep
417 i3 - checksum
418*/
419
420 for (i=0; i<768; ++i)
421 EC->count[i] = 0;
422
423 bptr1 = EC->buffer;
424 i1 = 256;
425 i3 = 0;
426 while (bptr1<EC->bufptr)
427 { i = (unsigned int) *bptr1++;
428 i3 = i3 + i;
429 if (i == i1)
430 {
431 i2 = 0;
432 bptr2 = bptr1+30000;
433 if (bptr2>(EC->bufptr))
434 bptr2 = EC->bufptr;
435
436 while ((i == i1) && (bptr1 < bptr2))
437 { ++i2;
438 i = (unsigned int) *bptr1++;
439 i3 = i3 + i;
440 }
441
442 if (i2 < 255)
443 ++EC->count[512+i2];
444 else
445 ++EC->count[512];
446 }
447 ++EC->count[i];
448 ++EC->count[((i+256-i1)&255)+256];
449 i1 = i;
450 }
451 EC->csum = i3;
452 if (!EC->count[512])
453 ++EC->count[512];
454
455/* find clue bytes */
456
457/* registers vars usage
458 i - code
459 i1 - cluebyte
460 i2 - clues
461 i3 - best forced clue
462*/
463
464 EC->clues = 0;
465 EC->dclues = 0;
466 i3 = 0;
467 for (i=0;i<HUFFCODES; ++i)
468 { i1 = i;
469 i2 = 0;
470 if (EC->count[i]<EC->count[i3])
471 i3 = i;
472 while (!EC->count[i] && (i<256))
473 { ++i2;
474 ++i;
475 }
476 if (i2 >= EC->dclues)
477 { EC->dclue = i1;
478 EC->dclues = i2;
479 if (EC->dclues >= EC->clues)
480 { EC->dclue = EC->clue;
481 EC->dclues = EC->clues;
482 EC->clue = i1;
483 EC->clues = i2;
484 }
485 }
486 }
487
488/* force a clue byte */
489
490 if (opt & 32)
491 { if (!EC->clues)
492 { EC->clues = 1;
493 EC->clue = i3;
494 }
495 }
496
497/* disable & split clue bytes */
498
499 if ((~opt) & 2)
500 { if (EC->clues>1)
501 EC->clues = 1;
502 if ((~opt) & 1)
503 EC->clues = 0;
504 }
505 if ((~opt) & 4)
506 EC->dclues = 0;
507 else
508 { if (EC->dclues > 10)
509 { i1 = EC->clue;
510 i2 = EC->clues;
511 EC->clue = EC->dclue;
512 EC->clues = EC->dclues;
513 EC->dclue = i1;
514 EC->dclues = i2;
515 }
516
517 if ((EC->clues*4) < EC->dclues)
518 { EC->clues = EC->dclues/4;
519 EC->dclues = EC->dclues-EC->clues;
520 EC->clue = EC->dclue+EC->dclues;
521 }
522 }
523
524
525/* copy delta clue bytes */
526
527 if (EC->dclues)
528 {
529 EC->mindelta = -((int)EC->dclues/2);
530 EC->maxdelta = EC->dclues+EC->mindelta;
531 thres = (int) (EC->ulen/25);
532
533 for (i=1;i<=(unsigned int)EC->maxdelta;++i)
534 if (EC->count[256+i] > thres)
535 EC->count[EC->dclue+(i-1)*2] = EC->count[256+i];
536 for (i=1;i<=(unsigned int)(-EC->mindelta);++i)
537 if (EC->count[512-i] > thres)
538 EC->count[EC->dclue+(i-1)*2+1] = EC->count[512-i];
539
540/* adjust delta clues */
541
542 for (i=0, i2=0;i<EC->dclues;++i)
543 if (EC->count[EC->dclue+i])
544 i2 = i;
545 di = EC->dclues-i2-1;
546 EC->dclues -= di;
547 if (EC->clue == (EC->dclue+EC->dclues+di))
548 { EC->clue -= di;
549 EC->clues += di;
550 }
551 EC->mindelta = -((int)EC->dclues/2);
552 EC->maxdelta = EC->dclues+EC->mindelta;
553 }
554
555/* copy rep clue bytes */
556
557 if (EC->clues)
558 {
559 for (i=0;i<EC->clues;++i)
560 EC->count[EC->clue+i] = EC->count[512+i];
561 }
562
563/* make a first approximation tree */
564
565 HUFF_maketree(EC);
566
567
568
569/* remove implied rep clues */
570
571/* registers vars usage
572 i - clues
573 i1 - minrep
574 i2 -
575 i3 -
576*/
577
578 if (EC->clues>1)
579 {
580 for (i=1; i<EC->clues; ++i)
581 { i1 = i-1;
582 if (i1>8)
583 i1 = 8;
584 if (EC->count[EC->clue+i])
585 { i1 = HUFF_minrep(EC,i,i1);
586 if ((i1 <= EC->bitsarray[EC->clue+i])
587 || (EC->count[EC->clue+i]*(i1-EC->bitsarray[EC->clue+i])<(i/2)))
588 { EC->count[EC->clue+i] = 0;
589 }
590 }
591 }
592 }
593
594/* count file (pass 2) */
595
596/* registers vars usage
597 i - current byte
598 i1 - previous byte
599 i2 - rep
600 i3 - rep2
601*/
602
603 for (i=0; i<HUFFCODES; ++i)
604 { count2[i] = EC->count[i];
605 dcount[i] = 0;
606 EC->count[i] = 0;
607 EC->count[256+i] = 0;
608 EC->count[512+i] = 0;
609 }
610
611 i = 1;
612 i1 = 256;
613 bptr1 = EC->buffer;
614 while (bptr1<EC->bufptr)
615 { i = (unsigned int) *bptr1++;
616 if (i == i1)
617 {
618 i2 = 0;
619 bptr2 = bptr1+30000;
620 if (bptr2>(EC->bufptr))
621 bptr2 = EC->bufptr;
622
623 while ((i == i1) && (bptr1 < bptr2))
624 { i = (unsigned int) *bptr1++;
625 ++i2;
626 }
627
628 repn = HUFFBIGNUM;
629 irep = HUFFBIGNUM;
630 ncode = i2*EC->bitsarray[i1];
631 if (EC->clues)
632 {
633 if (count2[EC->clue])
634 { repn = 20;
635 if (i2 < HUFFREPTBL)
636 repn = EC->bitsarray[EC->clue]+3+EC->repbits[i2]*2;
637 }
638 if (EC->clues>1)
639 {
640 remaining = i2;
641 irep = 0;
642 i3=EC->clues-1;
643 while (i3)
644 { if (count2[EC->clue+i3])
645 { rep1 = remaining/i3;
646 irep = irep+rep1*EC->bitsarray[EC->clue+i3];
647 remaining = remaining-rep1*i3;
648 }
649 --i3;
650 }
651 if (remaining)
652 irep=HUFFBIGNUM;
653 }
654 }
655
656 if ((ncode<=repn) && (ncode<=irep))
657 EC->count[i1] += i2;
658 else
659 { if (repn < irep)
660 ++EC->count[EC->clue];
661 else
662 {
663 remaining = i2;
664 irep = 0;
665 i3=EC->clues-1;
666 while (i3)
667 { if (count2[EC->clue+i3])
668 { rep1 = remaining/i3;
669 irep = irep+rep1*EC->bitsarray[EC->clue+i3];
670 remaining = remaining-rep1*i3;
671 EC->count[EC->clue+i3] += rep1;
672 }
673 --i3;
674 }
675 }
676 }
677 }
678 if (EC->dclues)
679 { i3 = 0;
680 di = i-i1;
681 if (di <= EC->maxdelta)
682 { if (di >= EC->mindelta)
683 { di = (i-i1-1)*2+EC->dclue;
684 if (i<i1)
685 di = (i1-i-1)*2+EC->dclue+1;
686 if (count2[di]>thres)
687 { if (count2[i]<4)
688 ++i3;
689 if (EC->bitsarray[di] < EC->bitsarray[i])
690 ++i3;
691 if (EC->bitsarray[di] == EC->bitsarray[i])
692 if (EC->count[di] > EC->count[i])
693 ++i3;
694 }
695 }
696 }
697 if (i3)
698 ++EC->count[di];
699 else
700 ++EC->count[i];
701 }
702 else
703 ++EC->count[i];
704 i1 = i;
705 }
706
707/* force a clue byte */
708
709 if (opt & 32)
710 ++EC->count[EC->clue];
711
712/* make a second approximation tree */
713
714 HUFF_maketree(EC);
715
716/* chainsaw IV branch clipping algorithm */
717
718/* - maintains perfect tree
719
720 - find intest code
721 - find intest branch thats shorter than maximum bits
722 - graft one branch to the shorter branch
723 - shorten the other code by 1
724*/
725
726/* registers vars usage
727 i - code
728 i1 - codes lengths
729 i2 - int code1 ptr
730 i3 - int code2 ptr
731*/
732
733 EC->chainused = 0;
734 i1 = 99;
735 while (i1>chainsaw)
736 { i1 = 0;
737 for (i=0; i<HUFFCODES; ++i) /* find intest code */
738 { if (EC->count[i])
739 { if (EC->bitsarray[i]>=i1)
740 { i3 = i2;
741 i2 = i;
742 i1 = EC->bitsarray[i];
743 }
744 }
745 }
746
747 if (i1>chainsaw)
748 {
749 i1 = 0;
750 while (i1<HUFFCODES)
751 { if (EC->count[i1])
752 {
753 if (EC->bitsarray[i1]<chainsaw)
754 break;
755 }
756 ++i1;
757 }
758 for (i=i1; i<HUFFCODES; ++i) /* find code to graft to */
759 { if (EC->count[i])
760 {
761 if ((EC->bitsarray[i]<chainsaw) && (EC->bitsarray[i]>EC->bitsarray[i1]))
762 i1 = i;
763 }
764 }
765
766 i = EC->bitsarray[i1]+1; /* graft to short code */
767 EC->bitsarray[i1] = i;
768 EC->bitsarray[i2] = i;
769 EC->bitsarray[i3] = EC->bitsarray[i3]-1;/* shorten other code by 1 */
770
771 EC->chainused = chainsaw;
772 i1 = 99;
773 }
774 }
775
776/* if huffman inhibited make all codes 8 bits */
777
778/* registers vars usage
779 i - code
780 i1 - 8
781 i2 -
782 i3 -
783*/
784
785 if ((~opt) & 8)
786 {
787 i1 = 8;
788 for (i=0; i<HUFFCODES; ++i)
789 EC->bitsarray[i] = i1;
790 }
791
792/* count bitnums */
793
794/* registers vars usage
795 i - code/bits
796 i1 -
797 i2 -
798 i3 -
799*/
800
801 for (i=0; i<=HUFFMAXBITS; ++i)
802 EC->bitnum[i] = 0;
803 for (i=0; i<HUFFCODES; ++i)
804 { if (EC->bitsarray[i]<=HUFFMAXBITS)
805 ++EC->bitnum[EC->bitsarray[i]];
806 }
807
808/* sort codes */
809
810/* registers vars usage
811 i - next sorted ptr
812 i1 - code
813 i2 - bits
814 i3 - EC->mostbits
815*/
816
817 i=0;
818 i3=0;
819 for (i2=1; i2<=HUFFMAXBITS; ++i2)
820 { if (EC->bitnum[i2])
821 { for (i1=0; i1<HUFFCODES; ++i1)
822 if (EC->bitsarray[i1] == i2)
823 EC->sortptr[i++] = i1;
824 i3 = i2;
825 }
826 }
827 EC->mostbits = i3;
828
829/* assign bit patterns */
830
831/* registers vars usage
832 i - code index
833 i1 - code
834 i2 - bits
835 i3 -
836*/
837
838 pattern = 0L;
839 i2 = 0;
840 for (i=0; i<EC->codes; ++i)
841 { i1 = EC->sortptr[i];
842 while (i2 < EC->bitsarray[i1])
843 { ++i2;
844 pattern = pattern << 1;
845 }
846 EC->patternarray[i1] = pattern;
847 ++pattern;
848 }
849}
850
851
852static void HUFF_pack(struct HuffEncodeContext *EC,
853 struct HUFFMemStruct *dest,
854 unsigned int opt)
855{
856 unsigned char *bptr1;
857 unsigned char *bptr2;
858 unsigned int i;
859 unsigned int i1;
860 unsigned int i2;
861 unsigned int i3;
862 int uptype;
863 unsigned int hlen, ibits, rladjust;
864 int di, firstcode, firstbits;
865 unsigned int rep1, repn, ncode, irep, remaining,curpc;
866
867/* write header */
868
869 curpc = 0L;
870
871 uptype = 38;
872 rladjust = 1;
873 if (uptype==38)
874 {
875 if (uptype==34)
876 {
877 HUFF_writenum(EC,dest,(unsigned int) EC->ulen);
878
879 ibits = 0;
880 if ((opt & 16) && (!EC->chainused))
881 ibits = 1;
882
883 i = 0; /* write options field */
884 if (EC->clues)
885 i = 1;
886 if (ibits)
887 i += 2;
888 if (EC->dclues)
889 i += 4;
890 HUFF_writenum(EC,dest,(unsigned int) i);
891
892 if (EC->clues)
893 { HUFF_writenum(EC,dest,(unsigned int) EC->clue);
894 HUFF_writenum(EC,dest,(unsigned int) EC->clues);
895 }
896 if (EC->dclues)
897 { HUFF_writenum(EC,dest,(unsigned int) EC->dclue);
898 HUFF_writenum(EC,dest,(unsigned int) EC->dclues);
899 }
900
901 if (!ibits)
902 HUFF_writenum(EC,dest,(unsigned int) EC->mostbits);
903 }
904 else
905 {
906 HUFF_writebits(EC,dest,(unsigned int) EC->clue, 8); /* clue */
907 rladjust = 0;
908 }
909
910 for (i=1; i <= EC->mostbits; ++i)
911 HUFF_writenum(EC,dest,(unsigned int) EC->bitnum[i]);
912
913 for (i=0; i<HUFFCODES; ++i)
914 EC->qleapcode[i] = 0;
915
916 i = 0;
917 i2 = 255;
918 firstbits = 0;
919 firstcode = -1;
920 while (i<EC->codes)
921 {
922 i1 = EC->sortptr[i];
923#if 0
924 if (EC->bitsarray[i1]!=firstbits)
925 {
926 i2 = firstcode;
927 firstcode = i1;
928 firstbits = EC->bitsarray[i2];
929 }
930#endif
931
932/* calculate leapfrog delta */
933
934 di = -1;
935 do
936 {
937 i2 = (i2+1)&255;
938 if (!EC->qleapcode[i2])
939 ++di;
940 } while (i1!=i2);
941 EC->qleapcode[i2] = 1;
942 HUFF_writenum(EC,dest,(unsigned int) di);
943 ++i;
944 }
945 }
946 hlen = EC->plen+1;
947
948 if (!EC->clues)
949 EC->clue = HUFFBIGNUM;
950
951/* write packed file */
952
953/* registers vars usage
954 i - current byte
955 i1 - previous byte
956 i2 - rep
957 i3 - rep2
958*/
959
960 i = 1;
961 i1 = 256;
962 bptr1 = EC->buffer;
963 while (bptr1<EC->bufptr)
964 { i = (unsigned int) *bptr1++;
965
966 if (i == i1)
967 {
968 i2 = 0;
969 bptr2 = bptr1+30000;
970 if (bptr2>(EC->bufptr))
971 bptr2 = EC->bufptr;
972
973 while ((i == i1) && (bptr1 < bptr2))
974 { i = (unsigned int) *bptr1++;
975 ++i2;
976 }
977
978 repn = HUFFBIGNUM;
979 irep = HUFFBIGNUM;
980 ncode = i2*EC->bitsarray[i1];
981 if (EC->clues)
982 {
983 if (EC->count[EC->clue])
984 { repn = 20;
985 if (i2 < HUFFREPTBL)
986 repn = EC->bitsarray[EC->clue]+3+EC->repbits[i2]*2;
987 }
988 if (EC->clues>1)
989 {
990 remaining = i2;
991 irep = 0;
992 i3=EC->clues-1;
993 while (i3)
994 { if (EC->count[EC->clue+i3])
995 { rep1 = remaining/i3;
996 irep = irep+rep1*EC->bitsarray[EC->clue+i3];
997 remaining = remaining-rep1*i3;
998 }
999 --i3;
1000 }
1001 if (remaining)
1002 irep = HUFFBIGNUM;
1003 }
1004 }
1005
1006 if ((ncode<=repn) && (ncode<=irep))
1007 {
1008 while (i2--)
1009 HUFF_writecode(EC,dest,i1);
1010 }
1011 else
1012 { if (repn < irep)
1013 {
1014 HUFF_writebits(EC,dest,EC->patternarray[EC->clue], EC->bitsarray[EC->clue]);
1015 HUFF_writenum(EC,dest,(unsigned int) (i2-rladjust));
1016 }
1017 else
1018 {
1019 remaining = i2;
1020 irep = 0;
1021 i3=EC->clues-1;
1022 while (i3)
1023 { if (EC->count[EC->clue+i3])
1024 { rep1 = remaining/i3;
1025 irep = irep+rep1*EC->bitsarray[EC->clue+i3];
1026 remaining = remaining-rep1*i3;
1027 while (rep1--)
1028 HUFF_writecode(EC,dest,EC->clue+i3);
1029 }
1030 --i3;
1031 }
1032 }
1033 }
1034 }
1035 i3 = 0;
1036 if (EC->dclues)
1037 {
1038 di = i-i1;
1039 if ((di <= EC->maxdelta) && (di >= EC->mindelta))
1040 { di = (i-i1-1)*2+EC->dclue;
1041 if (i<i1)
1042 di = (i1-i-1)*2+EC->dclue+1;
1043 if (EC->bitsarray[di] < EC->bitsarray[i])
1044 { HUFF_writebits(EC,dest,EC->patternarray[di], EC->bitsarray[di]);
1045 ++i3;
1046 }
1047 }
1048 }
1049 i1 = i;
1050 if (!i3)
1051 HUFF_writecode(EC,dest,i);
1052
1053 if (((int) bptr1- (int) EC->buffer) >= (int)(EC->plen+curpc))
1054 curpc = (int) bptr1 - (int) EC->buffer - EC->plen;
1055 }
1056
1057 /* write EOF ([clue] 0gn [10]) */
1058
1059 HUFF_writebits(EC,dest,EC->patternarray[EC->clue], EC->bitsarray[EC->clue]);
1060 HUFF_writenum(EC,dest,0L);
1061 HUFF_writebits(EC,dest,(unsigned int) 2, 2);
1062
1063 /* flush bits */
1064
1065 HUFF_writebits(EC,dest,(unsigned int) 0,7);
1066
1067 curpc += 2;
1068}
1069
1070static int HUFF_packfile(struct HuffEncodeContext *EC,
1071 struct HUFFMemStruct *infile,
1072 struct HUFFMemStruct *outfile,
1073 int ulen,
1074 int deltaed)
1075{
1076 unsigned int i;
1077 unsigned int uptype=0;
1078 unsigned int chainsaw;
1079 unsigned int opt;
1080
1081/* set defaults */
1082
1083 EC->packbits = 0;
1084 EC->workpattern = 0L;
1085 chainsaw = 15;
1086 EC->masks[0] = 0;
1087 for (i=1;i<17;++i)
1088 EC->masks[i] = (EC->masks[i-1] << 1) + 1;
1089
1090/* initialize huffman vars */
1091
1092 HUFF_init(EC);
1093
1094/* read in a source file */
1095
1096 EC->buffer = (unsigned char *) (infile->ptr);
1097 EC->flen = infile->len;
1098
1099 EC->ulen = EC->flen;
1100 EC->bufptr = EC->buffer + EC->flen;
1101
1102/* pack a file */
1103
1104 outfile->ptr = outfile->ptr;
1105 outfile->len = 0L;
1106
1107 EC->packbits = 0;
1108 EC->workpattern = 0L;
1109 EC->plen = 0L;
1110
1111 opt = 57 | 49;
1112
1113 HUFF_analysis(EC,opt, chainsaw);
1114
1115/* write standard header stuff (type/signature/ulen/adjust) */
1116
1117 if (ulen>0xffffff) // 32 bit header required
1118 {
1119 /* simple fb6 header */
1120
1121 if (ulen==infile->len)
1122 {
1123 if (deltaed==0) uptype = 0xb0fb;
1124 else if (deltaed==1) uptype = 0xb2fb;
1125 else if (deltaed==2) uptype = 0xb4fb;
1126 HUFF_writebits(EC,outfile,(unsigned int) uptype, 16);
1127 HUFF_writebits(EC,outfile,(unsigned int) infile->len, 32);
1128 }
1129
1130 /* composite fb4 header */
1131
1132 else
1133 {
1134 if (deltaed==0) uptype = 0xb1fb;
1135 else if (deltaed==1) uptype = 0xb3fb;
1136 else if (deltaed==2) uptype = 0xb5fb;
1137 HUFF_writebits(EC,outfile,(unsigned int) uptype, 16);
1138 HUFF_writebits(EC,outfile,(unsigned int) ulen, 32);
1139 HUFF_writebits(EC,outfile,(unsigned int) infile->len, 32);
1140 }
1141 }
1142 else
1143 {
1144 /* simple fb6 header */
1145
1146
1147 if (ulen==infile->len)
1148 {
1149 if (deltaed==0) uptype = 0x30fb;
1150 else if (deltaed==1) uptype = 0x32fb;
1151 else if (deltaed==2) uptype = 0x34fb;
1152 HUFF_writebits(EC,outfile,(unsigned int) uptype, 16);
1153 HUFF_writebits(EC,outfile,(unsigned int) infile->len, 24);
1154 }
1155
1156 /* composite fb4 header */
1157
1158 else
1159 {
1160 if (deltaed==0) uptype = 0x31fb;
1161 else if (deltaed==1) uptype = 0x33fb;
1162 else if (deltaed==2) uptype = 0x35fb;
1163 HUFF_writebits(EC,outfile,(unsigned int) uptype, 16);
1164 HUFF_writebits(EC,outfile,(unsigned int) ulen, 24);
1165 HUFF_writebits(EC,outfile,(unsigned int) infile->len, 24);
1166 }
1167 }
1168
1169 HUFF_pack(EC,outfile, opt);
1170
1171 return(outfile->len);
1172}
1173
1174
1175/****************************************************************/
1176/* Encode Function */
1177/****************************************************************/
1178
1179int GCALL HUFF_encode(void *compresseddata, const void *source, int sourcesize, int *opts)
1180{
1181 int plen=0;
1182 struct HUFFMemStruct infile;
1183 struct HUFFMemStruct outfile;
1184 struct HuffEncodeContext *EC=0;
1185 void *deltabuf=0;
1186 int opt=0;
1187 if (opts)
1188 opt = opts[0];
1189
1190 EC = (struct HuffEncodeContext *)galloc(sizeof(struct HuffEncodeContext));
1191 if (EC)
1192 {
1193 switch (opt)
1194 {
1195 default:
1196 case 0:
1197 infile.ptr = (char *)source;
1198 break;
1199
1200 case 1:
1201 deltabuf = galloc(sourcesize);
1202 HUFF_deltabytes(source,deltabuf,sourcesize);
1203 infile.ptr = (char *) deltabuf;
1204 break;
1205
1206 case 2:
1207 deltabuf = galloc(sourcesize);
1208 HUFF_deltabytes(source,deltabuf,sourcesize);
1209 HUFF_deltabytes(deltabuf,deltabuf,sourcesize);
1210 infile.ptr = (char *) deltabuf;
1211 break;
1212 }
1213
1214 infile.len = sourcesize;
1215 outfile.ptr = (char *)compresseddata;
1216 outfile.len = sourcesize;
1217
1218 plen = HUFF_packfile(EC,&infile, &outfile, sourcesize, opt);
1219
1220 if (deltabuf) gfree(deltabuf);
1221 gfree(EC);
1222 }
1223 return(plen);
1224}
1225
1226#endif
1227
min
#define min(x, y)
Definition BaseType.h:101
gfree
#define gfree
Definition gimex.h:360
galloc
#define galloc
Definition gimex.h:356
GCALL
#define GCALL
Definition codex.h:81
HUFF_encode
int GCALL HUFF_encode(void *compresseddata, const void *source, int sourcesize, int *opts)
Definition huffencode.cpp:1179
HUFFMAXBITS
#define HUFFMAXBITS
Definition huffencode.cpp:41
HUFFREPTBL
#define HUFFREPTBL
Definition huffencode.cpp:42
HUFFTREESIZE
#define HUFFTREESIZE
Definition huffencode.cpp:39
HUFFBIGNUM
#define HUFFBIGNUM
Definition huffencode.cpp:38
HUFFCODES
#define HUFFCODES
Definition huffencode.cpp:40
HuffEncodeContext::plen
unsigned int plen
Definition huffencode.cpp:71
HuffEncodeContext::tree_left
unsigned int tree_left[HUFFTREESIZE]
Definition huffencode.cpp:51
HuffEncodeContext::bitsarray
unsigned int bitsarray[HUFFCODES]
Definition huffencode.cpp:53
HuffEncodeContext::patternarray
unsigned int patternarray[HUFFCODES]
Definition huffencode.cpp:54
HuffEncodeContext::buffer
unsigned char * buffer
Definition huffencode.cpp:58
HuffEncodeContext::chainused
unsigned int chainused
Definition huffencode.cpp:64
HuffEncodeContext::ulen
unsigned int ulen
Definition huffencode.cpp:72
HuffEncodeContext::masks
unsigned int masks[17]
Definition huffencode.cpp:55
HuffEncodeContext::packbits
unsigned int packbits
Definition huffencode.cpp:56
HuffEncodeContext::dclues
unsigned int dclues
Definition huffencode.cpp:68
HuffEncodeContext::clues
unsigned int clues
Definition huffencode.cpp:67
HuffEncodeContext::bufptr
unsigned char * bufptr
Definition huffencode.cpp:59
HuffEncodeContext::workpattern
unsigned int workpattern
Definition huffencode.cpp:57
HuffEncodeContext::repbase
unsigned int repbase[HUFFREPTBL]
Definition huffencode.cpp:50
HuffEncodeContext::csum
unsigned int csum
Definition huffencode.cpp:61
HuffEncodeContext::count
unsigned int count[768]
Definition huffencode.cpp:47
HuffEncodeContext::clue
unsigned int clue
Definition huffencode.cpp:65
HuffEncodeContext::codes
unsigned int codes
Definition huffencode.cpp:63
HuffEncodeContext::bitnum
unsigned int bitnum[HUFFMAXBITS+1]
Definition huffencode.cpp:48
HuffEncodeContext::repbits
unsigned int repbits[HUFFREPTBL]
Definition huffencode.cpp:49
HuffEncodeContext::dclue
unsigned int dclue
Definition huffencode.cpp:66
HuffEncodeContext::tree_right
unsigned int tree_right[HUFFTREESIZE]
Definition huffencode.cpp:52
HuffEncodeContext::qleapcode
char qleapcode[HUFFCODES]
Definition huffencode.cpp:46
HuffEncodeContext::sortptr
unsigned int sortptr[HUFFCODES]
Definition huffencode.cpp:73
HuffEncodeContext::mostbits
unsigned int mostbits
Definition huffencode.cpp:62