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