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