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