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