tools/quake3/q3data/compress.c

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