]> de.git.xonotic.org Git - xonotic/netradiant.git/blob - tools/quake3/q3data/compress.c
* moved zeroradiant (1.6) into trunk
[xonotic/netradiant.git] / tools / quake3 / q3data / compress.c
1 #include "q3data.h"
2
3 #if 0
4 /*
5 ==================
6 MTF
7 ==================
8 */
9 cblock_t MTF (cblock_t in)
10 {
11         int                     i, j, b, code;
12         byte            *out_p;
13         int                     index[256];
14         cblock_t        out;
15
16         out_p = out.data = malloc(in.count + 4);
17
18         // write count
19         *out_p++ = in.count&255;
20         *out_p++ = (in.count>>8)&255;
21         *out_p++ = (in.count>>16)&255;
22         *out_p++ = (in.count>>24)&255;
23
24         for (i=0 ; i<256 ; i++)
25                 index[i] = i;
26
27         for (i=0 ; i<in.count ; i++)
28         {
29                 b = in.data[i];
30                 code = index[b];
31                 *out_p++ = code;
32                 
33                 // shuffle b indexes to 0
34                 for (j=0 ; j<256 ; j++)
35                         if (index[j] < code)
36                                 index[j]++;
37                 index[b] = 0;
38         }
39
40         out.count = out_p - out.data;
41
42         return out;
43 }
44
45
46 //==========================================================================
47
48 int             bwt_size;
49 byte    *bwt_data;
50
51 int bwtCompare (const void *elem1, const void *elem2)
52 {
53         int             i;
54         int             i1, i2;
55         int             b1, b2;
56
57         i1 = *(int *)elem1;
58         i2 = *(int *)elem2;
59
60         for (i=0 ; i<bwt_size ; i++)
61         {
62                 b1 = bwt_data[i1];
63                 b2 = bwt_data[i2];
64                 if (b1 < b2)
65                         return -1;
66                 if (b1 > b2)
67                         return 1;
68                 if (++i1 == bwt_size)
69                         i1 = 0;
70                 if (++i2 == bwt_size)
71                         i2 = 0;
72         }
73
74         return 0;
75 }
76
77 /*
78 ==================
79 BWT
80 ==================
81 */
82 cblock_t BWT (cblock_t in)
83 {
84         int             *sorted;
85         int             i;
86         byte    *out_p;
87         cblock_t        out;
88
89         bwt_size = in.count;
90         bwt_data = in.data;
91
92         sorted = malloc(in.count*sizeof(*sorted));
93         for (i=0 ; i<in.count ; i++)
94                 sorted[i] = i;
95         qsort (sorted, in.count, sizeof(*sorted), bwtCompare);
96
97         out_p = out.data = malloc(in.count + 8);
98
99         // write count
100         *out_p++ = in.count&255;
101         *out_p++ = (in.count>>8)&255;
102         *out_p++ = (in.count>>16)&255;
103         *out_p++ = (in.count>>24)&255;
104
105         // write head index
106         for (i=0 ; i<in.count ; i++)
107                 if (sorted[i] == 0)
108                         break;
109         *out_p++ = i&255;
110         *out_p++ = (i>>8)&255;
111         *out_p++ = (i>>16)&255;
112         *out_p++ = (i>>24)&255;
113
114         // write the L column
115         for (i=0 ; i<in.count ; i++)
116                 *out_p++ = in.data[(sorted[i]+in.count-1)%in.count];
117
118         free (sorted);
119
120         out.count = out_p - out.data;
121
122         return out;
123 }
124
125 //==========================================================================
126
127 typedef struct hnode_s
128 {
129         int                     count;
130         qboolean        used;
131         int                     children[2];
132 } hnode_t;
133
134 int                     numhnodes;
135 hnode_t         hnodes[512];
136 unsigned        charbits[256];
137 int                     charbitscount[256];
138
139 int     SmallestNode (void)
140 {
141         int             i;
142         int             best, bestnode;
143
144         best = 99999999;
145         bestnode = -1;
146         for (i=0 ; i<numhnodes ; i++)
147         {
148                 if (hnodes[i].used)
149                         continue;
150                 if (!hnodes[i].count)
151                         continue;
152                 if (hnodes[i].count < best)
153                 {
154                         best = hnodes[i].count;
155                         bestnode = i;
156                 }
157         }
158
159         if (bestnode == -1)
160                 return -1;
161
162         hnodes[bestnode].used = true;
163         return bestnode;
164 }
165
166 void BuildChars (int nodenum, unsigned bits, int bitcount)
167 {
168         hnode_t *node;
169
170         if (nodenum < 256)
171         {
172                 if (bitcount > 32)
173                         Error ("bitcount > 32");
174                 charbits[nodenum] = bits;
175                 charbitscount[nodenum] = bitcount;
176                 return;
177         }
178
179         node = &hnodes[nodenum];
180         bits <<= 1;
181         BuildChars (node->children[0], bits, bitcount+1);
182         bits |= 1;
183         BuildChars (node->children[1], bits, bitcount+1);
184 }
185
186 /*
187 ==================
188 Huffman
189 ==================
190 */
191 cblock_t Huffman (cblock_t in)
192 {
193         int                     i;
194         hnode_t         *node;
195         int                     outbits, c;
196         unsigned        bits;
197         byte            *out_p;
198         cblock_t        out;
199         int                     max, maxchar;
200
201         // count
202         memset (hnodes, 0, sizeof(hnodes));
203         for (i=0 ; i<in.count ; i++)
204                 hnodes[in.data[i]].count++;
205
206         // normalize counts
207         max = 0;
208         maxchar = 0;
209         for (i=0 ; i<256 ; i++)
210         {
211                 if (hnodes[i].count > max)
212                 {
213                         max = hnodes[i].count;
214                         maxchar = i;
215                 }
216         }
217         if (max == 0)
218                 Error ("Huffman: max == 0");
219
220         for (i=0 ; i<256 ; i++)
221         {
222                 hnodes[i].count = (hnodes[i].count*255+max-1) / max;
223         }
224
225         // build the nodes
226         numhnodes = 256;
227         while (numhnodes != 511)
228         {
229                 node = &hnodes[numhnodes];
230
231                 // pick two lowest counts
232                 node->children[0] = SmallestNode ();
233                 if (node->children[0] == -1)
234                         break;  // no more
235
236                 node->children[1] = SmallestNode ();
237                 if (node->children[1] == -1)
238                 {
239                         if (node->children[0] != numhnodes-1)
240                                 Error ("Bad smallestnode");
241                         break;
242                 }
243                 node->count = hnodes[node->children[0]].count + 
244                         hnodes[node->children[1]].count;
245                 numhnodes++;
246         }
247
248         BuildChars (numhnodes-1, 0, 0);
249
250         out_p = out.data = malloc(in.count*2 + 1024);
251         memset (out_p, 0, in.count*2+1024);
252
253         // write count
254         *out_p++ = in.count&255;
255         *out_p++ = (in.count>>8)&255;
256         *out_p++ = (in.count>>16)&255;
257         *out_p++ = (in.count>>24)&255;
258
259         // save out the 256 normalized counts so the tree can be recreated
260         for (i=0 ; i<256 ; i++)
261                 *out_p++ = hnodes[i].count;
262
263         // write bits
264         outbits = 0;
265         for (i=0 ; i<in.count ; i++)
266         {
267                 c = charbitscount[in.data[i]];
268                 bits = charbits[in.data[i]];
269                 while (c)
270                 {
271                         c--;
272                         if (bits & (1<<c))
273                                 out_p[outbits>>3] |= 1<<(outbits&7);
274                         outbits++;
275                 }
276         }
277
278         out_p += (outbits+7)>>3;
279
280         out.count = out_p - out.data;
281
282         return out;
283 }
284
285 //==========================================================================
286
287 /*
288 ==================
289 RLE
290 ==================
291 */
292 #define RLE_CODE        0xe8
293 #define RLE_TRIPPLE     0xe9
294
295 int     rle_counts[256];
296 int     rle_bytes[256];
297
298 cblock_t RLE (cblock_t in)
299 {
300         int             i;
301         byte    *out_p;
302         int             val;
303         int             repeat;
304         cblock_t        out;
305
306         out_p = out.data = malloc (in.count*2);
307
308         // write count
309         *out_p++ = in.count&255;
310         *out_p++ = (in.count>>8)&255;
311         *out_p++ = (in.count>>16)&255;
312         *out_p++ = (in.count>>24)&255;
313
314         for (i=0 ; i<in.count ; )
315         {
316                 val = in.data[i];
317                 rle_bytes[val]++;
318                 repeat = 1;
319                 i++;
320                 while (i<in.count && repeat < 255 && in.data[i] == val)
321                 {
322                         repeat++;
323                         i++;
324                 }
325 if (repeat < 256)
326 rle_counts[repeat]++;
327                 if (repeat > 3 || val == RLE_CODE)
328                 {
329                         *out_p++ = RLE_CODE;
330                         *out_p++ = val;
331                         *out_p++ = repeat;
332                 }
333                 else
334                 {
335                         while (repeat--)
336                                 *out_p++ = val;
337                 }
338         }
339
340         out.count = out_p - out.data;
341         return out;
342 }
343
344 //==========================================================================
345
346 unsigned        lzss_head[256];
347 unsigned        lzss_next[0x20000];
348
349 /*
350 ==================
351 LZSS
352 ==================
353 */
354 #define BACK_WINDOW             0x10000
355 #define BACK_BITS               16
356 #define FRONT_WINDOW    16
357 #define FRONT_BITS              4
358 cblock_t LZSS (cblock_t in)
359 {
360         int             i;
361         byte    *out_p;
362         cblock_t        out;
363         int             val;
364         int             j, start, max;
365         int             bestlength, beststart;
366         int             outbits;
367
368 if (in.count >= sizeof(lzss_next)/4)
369 Error ("LZSS: too big");
370
371         memset (lzss_head, -1, sizeof(lzss_head));
372
373         out_p = out.data = malloc (in.count*2);
374         memset (out.data, 0, in.count*2);
375
376         // write count
377         *out_p++ = in.count&255;
378         *out_p++ = (in.count>>8)&255;
379         *out_p++ = (in.count>>16)&255;
380         *out_p++ = (in.count>>24)&255;
381
382         outbits = 0;
383         for (i=0 ; i<in.count ; )
384         {
385                 val = in.data[i];
386 #if 1
387 // chained search
388                 bestlength = 0;
389                 beststart = 0;
390
391                 max = FRONT_WINDOW;
392                 if (i + max > in.count)
393                         max = in.count - i;
394
395                 start = lzss_head[val];
396                 while (start != -1 && start >= i-BACK_WINDOW)
397                 {                       
398                         // count match length
399                         for (j=0 ; j<max ; j++)
400                                 if (in.data[start+j] != in.data[i+j])
401                                         break;
402                         if (j > bestlength)
403                         {
404                                 bestlength = j;
405                                 beststart = start;
406                         }
407                         start = lzss_next[start];
408                 }
409
410 #else
411 // slow simple search
412                 // search for a match
413                 max = FRONT_WINDOW;
414                 if (i + max > in.count)
415                         max = in.count - i;
416
417                 start = i - BACK_WINDOW;
418                 if (start < 0)
419                         start = 0;
420                 bestlength = 0;
421                 beststart = 0;
422                 for ( ; start < i ; start++)
423                 {
424                         if (in.data[start] != val)
425                                 continue;
426                         // count match length
427                         for (j=0 ; j<max ; j++)
428                                 if (in.data[start+j] != in.data[i+j])
429                                         break;
430                         if (j > bestlength)
431                         {
432                                 bestlength = j;
433                                 beststart = start;
434                         }
435                 }
436 #endif
437                 beststart = BACK_WINDOW - (i-beststart);
438
439                 if (bestlength < 3)
440                 {       // output a single char
441                         bestlength = 1;
442
443                         out_p[outbits>>3] |= 1<<(outbits&7);    // set bit to mark char
444                         outbits++;
445                         for (j=0 ; j<8 ; j++, outbits++)
446                                 if (val & (1<<j) )
447                                         out_p[outbits>>3] |= 1<<(outbits&7);
448                 }
449                 else
450                 {       // output a phrase
451                         outbits++;      // leave a 0 bit to mark phrase
452                         for (j=0 ; j<BACK_BITS ; j++, outbits++)
453                                 if (beststart & (1<<j) )
454                                         out_p[outbits>>3] |= 1<<(outbits&7);
455                         for (j=0 ; j<FRONT_BITS ; j++, outbits++)
456                                 if (bestlength & (1<<j) )
457                                         out_p[outbits>>3] |= 1<<(outbits&7);
458                 }
459
460                 while (bestlength--)
461                 {
462                         val = in.data[i];
463                         lzss_next[i] = lzss_head[val];
464                         lzss_head[val] = i;
465                         i++;
466                 }
467         }
468
469         out_p += (outbits+7)>>3;
470         out.count = out_p - out.data;
471         return out;
472 }
473
474 //==========================================================================
475
476 #define MIN_REPT        15
477 #define MAX_REPT        0
478 #define HUF_TOKENS      (256+MAX_REPT)
479
480 unsigned        charbits1[256][HUF_TOKENS];
481 int                     charbitscount1[256][HUF_TOKENS];
482
483 hnode_t         hnodes1[256][HUF_TOKENS*2];
484 int                     numhnodes1[256];
485
486 int                     order0counts[256];
487
488 /*
489 ==================
490 SmallestNode1
491 ==================
492 */
493 int     SmallestNode1 (hnode_t *hnodes, int numhnodes)
494 {
495         int             i;
496         int             best, bestnode;
497
498         best = 99999999;
499         bestnode = -1;
500         for (i=0 ; i<numhnodes ; i++)
501         {
502                 if (hnodes[i].used)
503                         continue;
504                 if (!hnodes[i].count)
505                         continue;
506                 if (hnodes[i].count < best)
507                 {
508                         best = hnodes[i].count;
509                         bestnode = i;
510                 }
511         }
512
513         if (bestnode == -1)
514                 return -1;
515
516         hnodes[bestnode].used = true;
517         return bestnode;
518 }
519
520
521 /*
522 ==================
523 BuildChars1
524 ==================
525 */
526 void BuildChars1 (int prev, int nodenum, unsigned bits, int bitcount)
527 {
528         hnode_t *node;
529
530         if (nodenum < HUF_TOKENS)
531         {
532                 if (bitcount > 32)
533                         Error ("bitcount > 32");
534                 charbits1[prev][nodenum] = bits;
535                 charbitscount1[prev][nodenum] = bitcount;
536                 return;
537         }
538
539         node = &hnodes1[prev][nodenum];
540         bits <<= 1;
541         BuildChars1 (prev, node->children[0], bits, bitcount+1);
542         bits |= 1;
543         BuildChars1 (prev, node->children[1], bits, bitcount+1);
544 }
545
546
547 /*
548 ==================
549 BuildTree1
550 ==================
551 */
552 void BuildTree1 (int prev)
553 {
554         hnode_t         *node, *nodebase;
555         int                     numhnodes;
556
557         // build the nodes
558         numhnodes = HUF_TOKENS;
559         nodebase = hnodes1[prev];
560         while (1)
561         {
562                 node = &nodebase[numhnodes];
563
564                 // pick two lowest counts
565                 node->children[0] = SmallestNode1 (nodebase, numhnodes);
566                 if (node->children[0] == -1)
567                         break;  // no more
568
569                 node->children[1] = SmallestNode1 (nodebase, numhnodes);
570                 if (node->children[1] == -1)
571                         break;
572
573                 node->count = nodebase[node->children[0]].count + 
574                         nodebase[node->children[1]].count;
575                 numhnodes++;
576         }
577         numhnodes1[prev] = numhnodes-1;
578         BuildChars1 (prev, numhnodes-1, 0, 0);
579 }
580
581
582 /*
583 ==================
584 Huffman1_Count
585 ==================
586 */
587 void Huffman1_Count (cblock_t in)
588 {
589         int             i;
590         int             prev;
591         int             v;
592         int             rept;
593
594         prev = 0;
595         for (i=0 ; i<in.count ; i++)
596         {
597                 v = in.data[i];
598                 order0counts[v]++;
599                 hnodes1[prev][v].count++;
600                 prev = v;
601 #if 1
602                 for (rept=1 ; i+rept < in.count && rept < MAX_REPT ; rept++)
603                         if (in.data[i+rept] != v)
604                                 break;
605                 if (rept > MIN_REPT)
606                 {
607                         hnodes1[prev][255+rept].count++;
608                         i += rept-1;
609                 }
610 #endif
611         }
612 }
613
614
615 /*
616 ==================
617 Huffman1_Build
618 ==================
619 */
620 byte    scaled[256][HUF_TOKENS];
621 void Huffman1_Build (FILE *f)
622 {
623         int             i, j, v;
624         int             max;
625         int             total;
626
627         for (i=0 ; i<256 ; i++)
628         {
629                 // normalize and save the counts
630                 max = 0;
631                 for (j=0 ; j<HUF_TOKENS ; j++)
632                 {
633                         if (hnodes1[i][j].count > max)
634                                 max = hnodes1[i][j].count;
635                 }
636                 if (max == 0)
637                         max = 1;
638                 total = 0;
639                 for (j=0 ; j<HUF_TOKENS ; j++)
640                 {       // easy to overflow 32 bits here!
641                         v = (hnodes1[i][j].count*(double)255+max-1)/max;
642                         if (v > 255)
643                                 Error ("v > 255");
644                         scaled[i][j] = hnodes1[i][j].count = v;
645                         if (v)
646                                 total++;
647                 }
648                 if (total == 1)
649                 {       // must have two tokens
650                         if (!scaled[i][0])
651                                 scaled[i][0] = hnodes1[i][0].count = 1;
652                         else
653                                 scaled[i][1] = hnodes1[i][1].count = 1;
654                 }
655
656                 BuildTree1 (i);
657         }
658
659 #if 0
660         // count up the total bits
661         total = 0;
662         for (i=0 ; i<256 ; i++)
663                 for (j=0 ; j<256 ; j++)
664                         total += charbitscount1[i][j] * hnodes1[i][j].count;
665
666         total = (total+7)/8;
667         printf ("%i bytes huffman1 compressed\n", total);
668 #endif
669
670         fwrite (scaled, 1, sizeof(scaled), f);
671 }
672
673 /*
674 ==================
675 Huffman1
676
677 Order 1 compression with pre-built table
678 ==================
679 */
680 cblock_t Huffman1 (cblock_t in)
681 {
682         int                     i;
683         int                     outbits, c;
684         unsigned        bits;
685         byte            *out_p;
686         cblock_t        out;
687         int                     prev;
688         int                     v;
689         int                     rept;
690
691         out_p = out.data = malloc(in.count*2 + 1024);
692         memset (out_p, 0, in.count*2+1024);
693
694         // write count
695         *out_p++ = in.count&255;
696         *out_p++ = (in.count>>8)&255;
697         *out_p++ = (in.count>>16)&255;
698         *out_p++ = (in.count>>24)&255;
699
700         // write bits
701         outbits = 0;
702         prev = 0;
703         for (i=0 ; i<in.count ; i++)
704         {
705                 v = in.data[i];
706
707                 c = charbitscount1[prev][v];
708                 bits = charbits1[prev][v];
709                 if (!c)
710                         Error ("!bits");
711                 while (c)
712                 {
713                         c--;
714                         if (bits & (1<<c))
715                                 out_p[outbits>>3] |= 1<<(outbits&7);
716                         outbits++;
717                 }
718
719                 prev = v;
720 #if 1
721                 // check for repeat encodes
722                 for (rept=1 ; i+rept < in.count && rept < MAX_REPT ; rept++)
723                         if (in.data[i+rept] != v)
724                                 break;
725                 if (rept > MIN_REPT)
726                 {
727                         c = charbitscount1[prev][255+rept];
728                         bits = charbits1[prev][255+rept];
729                         if (!c)
730                                 Error ("!bits");
731                         while (c)
732                         {
733                                 c--;
734                                 if (bits & (1<<c))
735                                         out_p[outbits>>3] |= 1<<(outbits&7);
736                                 outbits++;
737                         }
738                         i += rept-1;
739                 }
740 #endif
741         }
742
743         out_p += (outbits+7)>>3;
744
745         out.count = out_p - out.data;
746
747         return out;
748 }
749
750 #endif