2 Copyright (C) 1999-2007 id Software, Inc. and contributors.
3 For a list of contributors, see the accompanying CONTRIBUTORS file.
5 This file is part of GtkRadiant.
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.
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.
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
30 cblock_t MTF (cblock_t in)
37 out_p = out.data = malloc(in.count + 4);
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;
45 for (i=0 ; i<256 ; i++)
48 for (i=0 ; i<in.count ; i++)
54 // shuffle b indexes to 0
55 for (j=0 ; j<256 ; j++)
61 out.count = out_p - out.data;
67 //==========================================================================
72 int bwtCompare (const void *elem1, const void *elem2)
81 for (i=0 ; i<bwt_size ; i++)
103 cblock_t BWT (cblock_t in)
113 sorted = malloc(in.count*sizeof(*sorted));
114 for (i=0 ; i<in.count ; i++)
116 qsort (sorted, in.count, sizeof(*sorted), bwtCompare);
118 out_p = out.data = malloc(in.count + 8);
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;
127 for (i=0 ; i<in.count ; i++)
131 *out_p++ = (i>>8)&255;
132 *out_p++ = (i>>16)&255;
133 *out_p++ = (i>>24)&255;
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];
141 out.count = out_p - out.data;
146 //==========================================================================
148 typedef struct hnode_s
157 unsigned charbits[256];
158 int charbitscount[256];
160 int SmallestNode (void)
167 for (i=0 ; i<numhnodes ; i++)
171 if (!hnodes[i].count)
173 if (hnodes[i].count < best)
175 best = hnodes[i].count;
183 hnodes[bestnode].used = true;
187 void BuildChars (int nodenum, unsigned bits, int bitcount)
194 Error ("bitcount > 32");
195 charbits[nodenum] = bits;
196 charbitscount[nodenum] = bitcount;
200 node = &hnodes[nodenum];
202 BuildChars (node->children[0], bits, bitcount+1);
204 BuildChars (node->children[1], bits, bitcount+1);
212 cblock_t Huffman (cblock_t in)
223 memset (hnodes, 0, sizeof(hnodes));
224 for (i=0 ; i<in.count ; i++)
225 hnodes[in.data[i]].count++;
230 for (i=0 ; i<256 ; i++)
232 if (hnodes[i].count > max)
234 max = hnodes[i].count;
239 Error ("Huffman: max == 0");
241 for (i=0 ; i<256 ; i++)
243 hnodes[i].count = (hnodes[i].count*255+max-1) / max;
248 while (numhnodes != 511)
250 node = &hnodes[numhnodes];
252 // pick two lowest counts
253 node->children[0] = SmallestNode ();
254 if (node->children[0] == -1)
257 node->children[1] = SmallestNode ();
258 if (node->children[1] == -1)
260 if (node->children[0] != numhnodes-1)
261 Error ("Bad smallestnode");
264 node->count = hnodes[node->children[0]].count +
265 hnodes[node->children[1]].count;
269 BuildChars (numhnodes-1, 0, 0);
271 out_p = out.data = malloc(in.count*2 + 1024);
272 memset (out_p, 0, in.count*2+1024);
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;
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;
286 for (i=0 ; i<in.count ; i++)
288 c = charbitscount[in.data[i]];
289 bits = charbits[in.data[i]];
294 out_p[outbits>>3] |= 1<<(outbits&7);
299 out_p += (outbits+7)>>3;
301 out.count = out_p - out.data;
306 //==========================================================================
313 #define RLE_CODE 0xe8
314 #define RLE_TRIPPLE 0xe9
319 cblock_t RLE (cblock_t in)
327 out_p = out.data = malloc (in.count*2);
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;
335 for (i=0 ; i<in.count ; )
341 while (i<in.count && repeat < 255 && in.data[i] == val)
347 rle_counts[repeat]++;
348 if (repeat > 3 || val == RLE_CODE)
361 out.count = out_p - out.data;
365 //==========================================================================
367 unsigned lzss_head[256];
368 unsigned lzss_next[0x20000];
375 #define BACK_WINDOW 0x10000
377 #define FRONT_WINDOW 16
379 cblock_t LZSS (cblock_t in)
386 int bestlength, beststart;
389 if (in.count >= sizeof(lzss_next)/4)
390 Error ("LZSS: too big");
392 memset (lzss_head, -1, sizeof(lzss_head));
394 out_p = out.data = malloc (in.count*2);
395 memset (out.data, 0, in.count*2);
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;
404 for (i=0 ; i<in.count ; )
413 if (i + max > in.count)
416 start = lzss_head[val];
417 while (start != -1 && start >= i-BACK_WINDOW)
419 // count match length
420 for (j=0 ; j<max ; j++)
421 if (in.data[start+j] != in.data[i+j])
428 start = lzss_next[start];
432 // slow simple search
433 // search for a match
435 if (i + max > in.count)
438 start = i - BACK_WINDOW;
443 for ( ; start < i ; start++)
445 if (in.data[start] != val)
447 // count match length
448 for (j=0 ; j<max ; j++)
449 if (in.data[start+j] != in.data[i+j])
458 beststart = BACK_WINDOW - (i-beststart);
461 { // output a single char
464 out_p[outbits>>3] |= 1<<(outbits&7); // set bit to mark char
466 for (j=0 ; j<8 ; j++, outbits++)
468 out_p[outbits>>3] |= 1<<(outbits&7);
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);
484 lzss_next[i] = lzss_head[val];
490 out_p += (outbits+7)>>3;
491 out.count = out_p - out.data;
495 //==========================================================================
499 #define HUF_TOKENS (256+MAX_REPT)
501 unsigned charbits1[256][HUF_TOKENS];
502 int charbitscount1[256][HUF_TOKENS];
504 hnode_t hnodes1[256][HUF_TOKENS*2];
507 int order0counts[256];
514 int SmallestNode1 (hnode_t *hnodes, int numhnodes)
521 for (i=0 ; i<numhnodes ; i++)
525 if (!hnodes[i].count)
527 if (hnodes[i].count < best)
529 best = hnodes[i].count;
537 hnodes[bestnode].used = true;
547 void BuildChars1 (int prev, int nodenum, unsigned bits, int bitcount)
551 if (nodenum < HUF_TOKENS)
554 Error ("bitcount > 32");
555 charbits1[prev][nodenum] = bits;
556 charbitscount1[prev][nodenum] = bitcount;
560 node = &hnodes1[prev][nodenum];
562 BuildChars1 (prev, node->children[0], bits, bitcount+1);
564 BuildChars1 (prev, node->children[1], bits, bitcount+1);
573 void BuildTree1 (int prev)
575 hnode_t *node, *nodebase;
579 numhnodes = HUF_TOKENS;
580 nodebase = hnodes1[prev];
583 node = &nodebase[numhnodes];
585 // pick two lowest counts
586 node->children[0] = SmallestNode1 (nodebase, numhnodes);
587 if (node->children[0] == -1)
590 node->children[1] = SmallestNode1 (nodebase, numhnodes);
591 if (node->children[1] == -1)
594 node->count = nodebase[node->children[0]].count +
595 nodebase[node->children[1]].count;
598 numhnodes1[prev] = numhnodes-1;
599 BuildChars1 (prev, numhnodes-1, 0, 0);
608 void Huffman1_Count (cblock_t in)
616 for (i=0 ; i<in.count ; i++)
620 hnodes1[prev][v].count++;
623 for (rept=1 ; i+rept < in.count && rept < MAX_REPT ; rept++)
624 if (in.data[i+rept] != v)
628 hnodes1[prev][255+rept].count++;
641 byte scaled[256][HUF_TOKENS];
642 void Huffman1_Build (FILE *f)
648 for (i=0 ; i<256 ; i++)
650 // normalize and save the counts
652 for (j=0 ; j<HUF_TOKENS ; j++)
654 if (hnodes1[i][j].count > max)
655 max = hnodes1[i][j].count;
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;
665 scaled[i][j] = hnodes1[i][j].count = v;
670 { // must have two tokens
672 scaled[i][0] = hnodes1[i][0].count = 1;
674 scaled[i][1] = hnodes1[i][1].count = 1;
681 // count up the total bits
683 for (i=0 ; i<256 ; i++)
684 for (j=0 ; j<256 ; j++)
685 total += charbitscount1[i][j] * hnodes1[i][j].count;
688 printf ("%i bytes huffman1 compressed\n", total);
691 fwrite (scaled, 1, sizeof(scaled), f);
698 Order 1 compression with pre-built table
701 cblock_t Huffman1 (cblock_t in)
712 out_p = out.data = malloc(in.count*2 + 1024);
713 memset (out_p, 0, in.count*2+1024);
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;
724 for (i=0 ; i<in.count ; i++)
728 c = charbitscount1[prev][v];
729 bits = charbits1[prev][v];
736 out_p[outbits>>3] |= 1<<(outbits&7);
742 // check for repeat encodes
743 for (rept=1 ; i+rept < in.count && rept < MAX_REPT ; rept++)
744 if (in.data[i+rept] != v)
748 c = charbitscount1[prev][255+rept];
749 bits = charbits1[prev][255+rept];
756 out_p[outbits>>3] |= 1<<(outbits&7);
764 out_p += (outbits+7)>>3;
766 out.count = out_p - out.data;