tools/quake2/qdata/video.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 "qdata.h"
  23 #include "inout.h"
  24
  25 byte    *soundtrack;
  26 char base[32];
  27
  28 /*
  29    ===============================================================================
  30
  31    WAV loading
  32
  33    ===============================================================================
  34  */
  35
  36 typedef struct
  37 {
  38         int rate;
  39         int width;
  40         int channels;
  41         int loopstart;
  42         int samples;
  43         int dataofs;                // chunk starts this many bytes from file start
  44 } wavinfo_t;
  45
  46
  47 byte    *data_p;
  48 byte    *iff_end;
  49 byte    *last_chunk;
  50 byte    *iff_data;
  51 int iff_chunk_len;
  52
  53
  54 int samplecounts[0x10000];
  55
  56 wavinfo_t wavinfo;
  57
  58 short GetLittleShort( void ){
  59         short val = 0;
  60         val = *data_p;
  61         val = val + ( *( data_p + 1 ) << 8 );
  62         data_p += 2;
  63         return val;
  64 }
  65
  66 int GetLittleLong( void ){
  67         int val = 0;
  68         val = *data_p;
  69         val = val + ( *( data_p + 1 ) << 8 );
  70         val = val + ( *( data_p + 2 ) << 16 );
  71         val = val + ( *( data_p + 3 ) << 24 );
  72         data_p += 4;
  73         return val;
  74 }
  75
  76 void FindNextChunk( char *name ){
  77         while ( 1 )
  78         {
  79                 data_p = last_chunk;
  80
  81                 if ( data_p >= iff_end ) { // didn't find the chunk
  82                         data_p = NULL;
  83                         return;
  84                 }
  85
  86                 data_p += 4;
  87                 iff_chunk_len = GetLittleLong();
  88                 if ( iff_chunk_len < 0 ) {
  89                         data_p = NULL;
  90                         return;
  91                 }
  92 //              if (iff_chunk_len > 1024*1024)
  93 //                      Sys_Error ("FindNextChunk: %i length is past the 1 meg sanity limit", iff_chunk_len);
  94                 data_p -= 8;
  95                 last_chunk = data_p + 8 + ( ( iff_chunk_len + 1 ) & ~1 );
  96                 if ( !strncmp( data_p, name, 4 ) ) {
  97                         return;
  98                 }
  99         }
 100 }
 101
 102 void FindChunk( char *name ){
 103         last_chunk = iff_data;
 104         FindNextChunk( name );
 105 }
 106
 107
 108 void DumpChunks( void ){
 109         char str[5];
 110
 111         str[4] = 0;
 112         data_p = iff_data;
 113         do
 114         {
 115                 memcpy( str, data_p, 4 );
 116                 data_p += 4;
 117                 iff_chunk_len = GetLittleLong();
 118                 printf( "0x%x : %s (%d)\n", (int)( data_p - 4 ), str, iff_chunk_len );
 119                 data_p += ( iff_chunk_len + 1 ) & ~1;
 120         } while ( data_p < iff_end );
 121 }
 122
 123 /*
 124    ============
 125    GetWavinfo
 126    ============
 127  */
 128 wavinfo_t GetWavinfo( char *name, byte *wav, int wavlength ){
 129         wavinfo_t info;
 130         int i;
 131         int format;
 132         int samples;
 133
 134         memset( &info, 0, sizeof( info ) );
 135
 136         if ( !wav ) {
 137                 return info;
 138         }
 139
 140         iff_data = wav;
 141         iff_end = wav + wavlength;
 142
 143 // find "RIFF" chunk
 144         FindChunk( "RIFF" );
 145         if ( !( data_p && !strncmp( data_p + 8, "WAVE", 4 ) ) ) {
 146                 printf( "Missing RIFF/WAVE chunks\n" );
 147                 return info;
 148         }
 149
 150 // get "fmt " chunk
 151         iff_data = data_p + 12;
 152 // DumpChunks ();
 153
 154         FindChunk( "fmt " );
 155         if ( !data_p ) {
 156                 printf( "Missing fmt chunk\n" );
 157                 return info;
 158         }
 159         data_p += 8;
 160         format = GetLittleShort();
 161         if ( format != 1 ) {
 162                 printf( "Microsoft PCM format only\n" );
 163                 return info;
 164         }
 165
 166         info.channels = GetLittleShort();
 167         info.rate = GetLittleLong();
 168         data_p += 4 + 2;
 169         info.width = GetLittleShort() / 8;
 170
 171 // get cue chunk
 172         FindChunk( "cue " );
 173         if ( data_p ) {
 174                 data_p += 32;
 175                 info.loopstart = GetLittleLong();
 176 //              Com_Printf("loopstart=%d\n", sfx->loopstart);
 177
 178                 // if the next chunk is a LIST chunk, look for a cue length marker
 179                 FindNextChunk( "LIST" );
 180                 if ( data_p ) {
 181                         if ( !strncmp( data_p + 28, "mark", 4 ) ) { // this is not a proper parse, but it works with cooledit...
 182                                 data_p += 24;
 183                                 i = GetLittleLong();    // samples in loop
 184                                 info.samples = info.loopstart + i;
 185                         }
 186                 }
 187         }
 188         else{
 189                 info.loopstart = -1;
 190         }
 191
 192 // find data chunk
 193         FindChunk( "data" );
 194         if ( !data_p ) {
 195                 printf( "Missing data chunk\n" );
 196                 return info;
 197         }
 198
 199         data_p += 4;
 200         samples = GetLittleLong();
 201
 202         if ( info.samples ) {
 203                 if ( samples < info.samples ) {
 204                         Error( "Sound %s has a bad loop length", name );
 205                 }
 206         }
 207         else{
 208                 info.samples = samples;
 209         }
 210
 211         info.dataofs = data_p - wav;
 212
 213         return info;
 214 }
 215
 216 //=====================================================================
 217
 218 /*
 219    ==============
 220    LoadSoundtrack
 221    ==============
 222  */
 223 void LoadSoundtrack( void ){
 224         char name[1024];
 225         FILE    *f;
 226         int len;
 227         int i, val, j;
 228
 229         soundtrack = NULL;
 230         sprintf( name, "%svideo/%s/%s.wav", gamedir, base, base );
 231         printf( "%s\n", name );
 232         f = fopen( name, "rb" );
 233         if ( !f ) {
 234                 printf( "no soundtrack for %s\n", base );
 235                 return;
 236         }
 237         len = Q_filelength( f );
 238         soundtrack = malloc( len );
 239         fread( soundtrack, 1, len, f );
 240         fclose( f );
 241
 242         wavinfo = GetWavinfo( name, soundtrack, len );
 243
 244         // count samples for compression
 245         memset( samplecounts, 0, sizeof( samplecounts ) );
 246
 247         j = wavinfo.samples / 2;
 248         for ( i = 0 ; i < j ; i++ )
 249         {
 250                 val = ( (unsigned short *)( soundtrack + wavinfo.dataofs ) )[i];
 251                 samplecounts[val]++;
 252         }
 253         val = 0;
 254         for ( i = 0 ; i < 0x10000 ; i++ )
 255                 if ( samplecounts[i] ) {
 256                         val++;
 257                 }
 258
 259         printf( "%i unique sample values\n", val );
 260 }
 261
 262 /*
 263    ==================
 264    WriteSound
 265    ==================
 266  */
 267 void WriteSound( FILE *output, int frame ){
 268         int start, end;
 269         int count;
 270         int empty = 0;
 271         int i;
 272         int sample;
 273         int width;
 274
 275         width = wavinfo.width * wavinfo.channels;
 276
 277         start = frame * wavinfo.rate / 14;
 278         end = ( frame + 1 ) * wavinfo.rate / 14;
 279         count = end - start;
 280
 281         for ( i = 0 ; i < count ; i++ )
 282         {
 283                 sample = start + i;
 284                 if ( sample > wavinfo.samples || !soundtrack ) {
 285                         fwrite( &empty, 1, width, output );
 286                 }
 287                 else{
 288                         fwrite( soundtrack + wavinfo.dataofs + sample * width, 1, width,output );
 289                 }
 290         }
 291 }
 292
 293 //==========================================================================
 294
 295 /*
 296    ==================
 297    MTF
 298    ==================
 299  */
 300 cblock_t MTF( cblock_t in ){
 301         int i, j, b, code;
 302         byte        *out_p;
 303         int index[256];
 304         cblock_t out;
 305
 306         out_p = out.data = malloc( in.count + 4 );
 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 < 256 ; i++ )
 315                 index[i] = i;
 316
 317         for ( i = 0 ; i < in.count ; i++ )
 318         {
 319                 b = in.data[i];
 320                 code = index[b];
 321                 *out_p++ = code;
 322
 323                 // shuffle b indexes to 0
 324                 for ( j = 0 ; j < 256 ; j++ )
 325                         if ( index[j] < code ) {
 326                                 index[j]++;
 327                         }
 328                 index[b] = 0;
 329         }
 330
 331         out.count = out_p - out.data;
 332
 333         return out;
 334 }
 335
 336
 337 //==========================================================================
 338
 339 int bwt_size;
 340 byte    *bwt_data;
 341
 342 int bwtCompare( const void *elem1, const void *elem2 ){
 343         int i;
 344         int i1, i2;
 345         int b1, b2;
 346
 347         i1 = *(int *)elem1;
 348         i2 = *(int *)elem2;
 349
 350         for ( i = 0 ; i < bwt_size ; i++ )
 351         {
 352                 b1 = bwt_data[i1];
 353                 b2 = bwt_data[i2];
 354                 if ( b1 < b2 ) {
 355                         return -1;
 356                 }
 357                 if ( b1 > b2 ) {
 358                         return 1;
 359                 }
 360                 if ( ++i1 == bwt_size ) {
 361                         i1 = 0;
 362                 }
 363                 if ( ++i2 == bwt_size ) {
 364                         i2 = 0;
 365                 }
 366         }
 367
 368         return 0;
 369 }
 370
 371 /*
 372    ==================
 373    BWT
 374    ==================
 375  */
 376 cblock_t BWT( cblock_t in ){
 377         int     *sorted;
 378         int i;
 379         byte    *out_p;
 380         cblock_t out;
 381
 382         bwt_size = in.count;
 383         bwt_data = in.data;
 384
 385         sorted = malloc( in.count * sizeof( *sorted ) );
 386         for ( i = 0 ; i < in.count ; i++ )
 387                 sorted[i] = i;
 388         qsort( sorted, in.count, sizeof( *sorted ), bwtCompare );
 389
 390         out_p = out.data = malloc( in.count + 8 );
 391
 392         // write count
 393         *out_p++ = in.count & 255;
 394         *out_p++ = ( in.count >> 8 ) & 255;
 395         *out_p++ = ( in.count >> 16 ) & 255;
 396         *out_p++ = ( in.count >> 24 ) & 255;
 397
 398         // write head index
 399         for ( i = 0 ; i < in.count ; i++ )
 400                 if ( sorted[i] == 0 ) {
 401                         break;
 402                 }
 403         *out_p++ = i & 255;
 404         *out_p++ = ( i >> 8 ) & 255;
 405         *out_p++ = ( i >> 16 ) & 255;
 406         *out_p++ = ( i >> 24 ) & 255;
 407
 408         // write the L column
 409         for ( i = 0 ; i < in.count ; i++ )
 410                 *out_p++ = in.data[( sorted[i] + in.count - 1 ) % in.count];
 411
 412         free( sorted );
 413
 414         out.count = out_p - out.data;
 415
 416         return out;
 417 }
 418
 419 //==========================================================================
 420
 421 typedef struct hnode_s
 422 {
 423         int count;
 424         qboolean used;
 425         int children[2];
 426 } hnode_t;
 427
 428 int numhnodes;
 429 hnode_t hnodes[512];
 430 unsigned charbits[256];
 431 int charbitscount[256];
 432
 433 int SmallestNode( void ){
 434         int i;
 435         int best, bestnode;
 436
 437         best = 99999999;
 438         bestnode = -1;
 439         for ( i = 0 ; i < numhnodes ; i++ )
 440         {
 441                 if ( hnodes[i].used ) {
 442                         continue;
 443                 }
 444                 if ( !hnodes[i].count ) {
 445                         continue;
 446                 }
 447                 if ( hnodes[i].count < best ) {
 448                         best = hnodes[i].count;
 449                         bestnode = i;
 450                 }
 451         }
 452
 453         if ( bestnode == -1 ) {
 454                 return -1;
 455         }
 456
 457         hnodes[bestnode].used = true;
 458         return bestnode;
 459 }
 460
 461 void BuildChars( int nodenum, unsigned bits, int bitcount ){
 462         hnode_t *node;
 463
 464         if ( nodenum < 256 ) {
 465                 if ( bitcount > 32 ) {
 466                         Error( "bitcount > 32" );
 467                 }
 468                 charbits[nodenum] = bits;
 469                 charbitscount[nodenum] = bitcount;
 470                 return;
 471         }
 472
 473         node = &hnodes[nodenum];
 474         bits <<= 1;
 475         BuildChars( node->children[0], bits, bitcount + 1 );
 476         bits |= 1;
 477         BuildChars( node->children[1], bits, bitcount + 1 );
 478 }
 479
 480
 481 /*
 482    ==================
 483    Huffman
 484    ==================
 485  */
 486 cblock_t Huffman( cblock_t in ){
 487         int i;
 488         hnode_t     *node;
 489         int outbits, c;
 490         unsigned bits;
 491         byte        *out_p;
 492         cblock_t out;
 493         int max, maxchar;
 494
 495         // count
 496         memset( hnodes, 0, sizeof( hnodes ) );
 497         for ( i = 0 ; i < in.count ; i++ )
 498                 hnodes[in.data[i]].count++;
 499
 500         // normalize counts
 501         max = 0;
 502         maxchar = 0;
 503         for ( i = 0 ; i < 256 ; i++ )
 504         {
 505                 if ( hnodes[i].count > max ) {
 506                         max = hnodes[i].count;
 507                         maxchar = i;
 508                 }
 509         }
 510         if ( max == 0 ) {
 511                 Error( "Huffman: max == 0" );
 512         }
 513
 514         for ( i = 0 ; i < 256 ; i++ )
 515         {
 516                 hnodes[i].count = ( hnodes[i].count * 255 + max - 1 ) / max;
 517         }
 518
 519         // build the nodes
 520         numhnodes = 256;
 521         while ( numhnodes != 511 )
 522         {
 523                 node = &hnodes[numhnodes];
 524
 525                 // pick two lowest counts
 526                 node->children[0] = SmallestNode();
 527                 if ( node->children[0] == -1 ) {
 528                         break;  // no more
 529
 530                 }
 531                 node->children[1] = SmallestNode();
 532                 if ( node->children[1] == -1 ) {
 533                         if ( node->children[0] != numhnodes - 1 ) {
 534                                 Error( "Bad smallestnode" );
 535                         }
 536                         break;
 537                 }
 538                 node->count = hnodes[node->children[0]].count +
 539                                           hnodes[node->children[1]].count;
 540                 numhnodes++;
 541         }
 542
 543         BuildChars( numhnodes - 1, 0, 0 );
 544
 545         out_p = out.data = malloc( in.count * 2 + 1024 );
 546         memset( out_p, 0, in.count * 2 + 1024 );
 547
 548         // write count
 549         *out_p++ = in.count & 255;
 550         *out_p++ = ( in.count >> 8 ) & 255;
 551         *out_p++ = ( in.count >> 16 ) & 255;
 552         *out_p++ = ( in.count >> 24 ) & 255;
 553
 554         // save out the 256 normalized counts so the tree can be recreated
 555         for ( i = 0 ; i < 256 ; i++ )
 556                 *out_p++ = hnodes[i].count;
 557
 558         // write bits
 559         outbits = 0;
 560         for ( i = 0 ; i < in.count ; i++ )
 561         {
 562                 c = charbitscount[in.data[i]];
 563                 bits = charbits[in.data[i]];
 564                 while ( c )
 565                 {
 566                         c--;
 567                         if ( bits & ( 1 << c ) ) {
 568                                 out_p[outbits >> 3] |= 1 << ( outbits & 7 );
 569                         }
 570                         outbits++;
 571                 }
 572         }
 573
 574         out_p += ( outbits + 7 ) >> 3;
 575
 576         out.count = out_p - out.data;
 577
 578         return out;
 579 }
 580
 581 //==========================================================================
 582
 583 /*
 584    ==================
 585    RLE
 586    ==================
 587  */
 588 #define RLE_CODE    0xe8
 589 #define RLE_TRIPPLE 0xe9
 590
 591 int rle_counts[256];
 592 int rle_bytes[256];
 593
 594 cblock_t RLE( cblock_t in ){
 595         int i;
 596         byte    *out_p;
 597         int val;
 598         int repeat;
 599         cblock_t out;
 600
 601         out_p = out.data = malloc( in.count * 2 );
 602
 603         // write count
 604         *out_p++ = in.count & 255;
 605         *out_p++ = ( in.count >> 8 ) & 255;
 606         *out_p++ = ( in.count >> 16 ) & 255;
 607         *out_p++ = ( in.count >> 24 ) & 255;
 608
 609         for ( i = 0 ; i < in.count ; )
 610         {
 611                 val = in.data[i];
 612                 rle_bytes[val]++;
 613                 repeat = 1;
 614                 i++;
 615                 while ( i < in.count && repeat < 255 && in.data[i] == val )
 616                 {
 617                         repeat++;
 618                         i++;
 619                 }
 620                 if ( repeat < 256 ) {
 621                         rle_counts[repeat]++;
 622                 }
 623                 if ( repeat > 3 || val == RLE_CODE ) {
 624                         *out_p++ = RLE_CODE;
 625                         *out_p++ = val;
 626                         *out_p++ = repeat;
 627                 }
 628                 else
 629                 {
 630                         while ( repeat-- )
 631                                 *out_p++ = val;
 632                 }
 633         }
 634
 635         out.count = out_p - out.data;
 636         return out;
 637 }
 638
 639 //==========================================================================
 640
 641 unsigned lzss_head[256];
 642 unsigned lzss_next[0x20000];
 643
 644 /*
 645    ==================
 646    LZSS
 647    ==================
 648  */
 649 #define BACK_WINDOW     0x10000
 650 #define BACK_BITS       16
 651 #define FRONT_WINDOW    16
 652 #define FRONT_BITS      4
 653 cblock_t LZSS( cblock_t in ){
 654         int i;
 655         byte    *out_p;
 656         cblock_t out;
 657         int val;
 658         int j, start, max;
 659         int bestlength, beststart;
 660         int outbits;
 661
 662         if ( in.count >= sizeof( lzss_next ) / 4 ) {
 663                 Error( "LZSS: too big" );
 664         }
 665
 666         memset( lzss_head, -1, sizeof( lzss_head ) );
 667
 668         out_p = out.data = malloc( in.count * 2 );
 669         memset( out.data, 0, in.count * 2 );
 670
 671         // write count
 672         *out_p++ = in.count & 255;
 673         *out_p++ = ( in.count >> 8 ) & 255;
 674         *out_p++ = ( in.count >> 16 ) & 255;
 675         *out_p++ = ( in.count >> 24 ) & 255;
 676
 677         outbits = 0;
 678         for ( i = 0 ; i < in.count ; )
 679         {
 680                 val = in.data[i];
 681 #if 1
 682 // chained search
 683                 bestlength = 0;
 684                 beststart = 0;
 685
 686                 max = FRONT_WINDOW;
 687                 if ( i + max > in.count ) {
 688                         max = in.count - i;
 689                 }
 690
 691                 start = lzss_head[val];
 692                 while ( start != -1 && start >= i - BACK_WINDOW )
 693                 {
 694                         // count match length
 695                         for ( j = 0 ; j < max ; j++ )
 696                                 if ( in.data[start + j] != in.data[i + j] ) {
 697                                         break;
 698                                 }
 699                         if ( j > bestlength ) {
 700                                 bestlength = j;
 701                                 beststart = start;
 702                         }
 703                         start = lzss_next[start];
 704                 }
 705
 706 #else
 707 // slow simple search
 708                 // search for a match
 709                 max = FRONT_WINDOW;
 710                 if ( i + max > in.count ) {
 711                         max = in.count - i;
 712                 }
 713
 714                 start = i - BACK_WINDOW;
 715                 if ( start < 0 ) {
 716                         start = 0;
 717                 }
 718                 bestlength = 0;
 719                 beststart = 0;
 720                 for ( ; start < i ; start++ )
 721                 {
 722                         if ( in.data[start] != val ) {
 723                                 continue;
 724                         }
 725                         // count match length
 726                         for ( j = 0 ; j < max ; j++ )
 727                                 if ( in.data[start + j] != in.data[i + j] ) {
 728                                         break;
 729                                 }
 730                         if ( j > bestlength ) {
 731                                 bestlength = j;
 732                                 beststart = start;
 733                         }
 734                 }
 735 #endif
 736                 beststart = BACK_WINDOW - ( i - beststart );
 737
 738                 if ( bestlength < 3 ) { // output a single char
 739                         bestlength = 1;
 740
 741                         out_p[outbits >> 3] |= 1 << ( outbits & 7 );    // set bit to mark char
 742                         outbits++;
 743                         for ( j = 0 ; j < 8 ; j++, outbits++ )
 744                                 if ( val & ( 1 << j ) ) {
 745                                         out_p[outbits >> 3] |= 1 << ( outbits & 7 );
 746                                 }
 747                 }
 748                 else
 749                 {   // output a phrase
 750                         outbits++;  // leave a 0 bit to mark phrase
 751                         for ( j = 0 ; j < BACK_BITS ; j++, outbits++ )
 752                                 if ( beststart & ( 1 << j ) ) {
 753                                         out_p[outbits >> 3] |= 1 << ( outbits & 7 );
 754                                 }
 755                         for ( j = 0 ; j < FRONT_BITS ; j++, outbits++ )
 756                                 if ( bestlength & ( 1 << j ) ) {
 757                                         out_p[outbits >> 3] |= 1 << ( outbits & 7 );
 758                                 }
 759                 }
 760
 761                 while ( bestlength-- )
 762                 {
 763                         val = in.data[i];
 764                         lzss_next[i] = lzss_head[val];
 765                         lzss_head[val] = i;
 766                         i++;
 767                 }
 768         }
 769
 770         out_p += ( outbits + 7 ) >> 3;
 771         out.count = out_p - out.data;
 772         return out;
 773 }
 774
 775 //==========================================================================
 776
 777 #define MIN_REPT    15
 778 #define MAX_REPT    0
 779 #define HUF_TOKENS  ( 256 + MAX_REPT )
 780
 781 unsigned charbits1[256][HUF_TOKENS];
 782 int charbitscount1[256][HUF_TOKENS];
 783
 784 hnode_t hnodes1[256][HUF_TOKENS * 2];
 785 int numhnodes1[256];
 786
 787 int order0counts[256];
 788
 789 /*
 790    ==================
 791    SmallestNode1
 792    ==================
 793  */
 794 int SmallestNode1( hnode_t *hnodes, int numhnodes ){
 795         int i;
 796         int best, bestnode;
 797
 798         best = 99999999;
 799         bestnode = -1;
 800         for ( i = 0 ; i < numhnodes ; i++ )
 801         {
 802                 if ( hnodes[i].used ) {
 803                         continue;
 804                 }
 805                 if ( !hnodes[i].count ) {
 806                         continue;
 807                 }
 808                 if ( hnodes[i].count < best ) {
 809                         best = hnodes[i].count;
 810                         bestnode = i;
 811                 }
 812         }
 813
 814         if ( bestnode == -1 ) {
 815                 return -1;
 816         }
 817
 818         hnodes[bestnode].used = true;
 819         return bestnode;
 820 }
 821
 822
 823 /*
 824    ==================
 825    BuildChars1
 826    ==================
 827  */
 828 void BuildChars1( int prev, int nodenum, unsigned bits, int bitcount ){
 829         hnode_t *node;
 830
 831         if ( nodenum < HUF_TOKENS ) {
 832                 if ( bitcount > 32 ) {
 833                         Error( "bitcount > 32" );
 834                 }
 835                 charbits1[prev][nodenum] = bits;
 836                 charbitscount1[prev][nodenum] = bitcount;
 837                 return;
 838         }
 839
 840         node = &hnodes1[prev][nodenum];
 841         bits <<= 1;
 842         BuildChars1( prev, node->children[0], bits, bitcount + 1 );
 843         bits |= 1;
 844         BuildChars1( prev, node->children[1], bits, bitcount + 1 );
 845 }
 846
 847
 848 /*
 849    ==================
 850    BuildTree1
 851    ==================
 852  */
 853 void BuildTree1( int prev ){
 854         hnode_t     *node, *nodebase;
 855         int numhnodes;
 856
 857         // build the nodes
 858         numhnodes = HUF_TOKENS;
 859         nodebase = hnodes1[prev];
 860         while ( 1 )
 861         {
 862                 node = &nodebase[numhnodes];
 863
 864                 // pick two lowest counts
 865                 node->children[0] = SmallestNode1( nodebase, numhnodes );
 866                 if ( node->children[0] == -1 ) {
 867                         break;  // no more
 868
 869                 }
 870                 node->children[1] = SmallestNode1( nodebase, numhnodes );
 871                 if ( node->children[1] == -1 ) {
 872                         break;
 873                 }
 874
 875                 node->count = nodebase[node->children[0]].count +
 876                                           nodebase[node->children[1]].count;
 877                 numhnodes++;
 878         }
 879         numhnodes1[prev] = numhnodes - 1;
 880         BuildChars1( prev, numhnodes - 1, 0, 0 );
 881 }
 882
 883
 884 /*
 885    ==================
 886    Huffman1_Count
 887    ==================
 888  */
 889 void Huffman1_Count( cblock_t in ){
 890         int i;
 891         int prev;
 892         int v;
 893         int rept;
 894
 895         prev = 0;
 896         for ( i = 0 ; i < in.count ; i++ )
 897         {
 898                 v = in.data[i];
 899                 order0counts[v]++;
 900                 hnodes1[prev][v].count++;
 901                 prev = v;
 902 #if 1
 903                 for ( rept = 1 ; i + rept < in.count && rept < MAX_REPT ; rept++ )
 904                         if ( in.data[i + rept] != v ) {
 905                                 break;
 906                         }
 907                 if ( rept > MIN_REPT ) {
 908                         hnodes1[prev][255 + rept].count++;
 909                         i += rept - 1;
 910                 }
 911 #endif
 912         }
 913 }
 914
 915
 916 /*
 917    ==================
 918    Huffman1_Build
 919    ==================
 920  */
 921 byte scaled[256][HUF_TOKENS];
 922 void Huffman1_Build( FILE *f ){
 923         int i, j, v;
 924         int max;
 925         int total;
 926
 927         for ( i = 0 ; i < 256 ; i++ )
 928         {
 929                 // normalize and save the counts
 930                 max = 0;
 931                 for ( j = 0 ; j < HUF_TOKENS ; j++ )
 932                 {
 933                         if ( hnodes1[i][j].count > max ) {
 934                                 max = hnodes1[i][j].count;
 935                         }
 936                 }
 937                 if ( max == 0 ) {
 938                         max = 1;
 939                 }
 940                 total = 0;
 941                 for ( j = 0 ; j < HUF_TOKENS ; j++ )
 942                 {   // easy to overflow 32 bits here!
 943                         v = ( hnodes1[i][j].count * (double)255 + max - 1 ) / max;
 944                         if ( v > 255 ) {
 945                                 Error( "v > 255" );
 946                         }
 947                         scaled[i][j] = hnodes1[i][j].count = v;
 948                         if ( v ) {
 949                                 total++;
 950                         }
 951                 }
 952                 if ( total == 1 ) { // must have two tokens
 953                         if ( !scaled[i][0] ) {
 954                                 scaled[i][0] = hnodes1[i][0].count = 1;
 955                         }
 956                         else{
 957                                 scaled[i][1] = hnodes1[i][1].count = 1;
 958                         }
 959                 }
 960
 961                 BuildTree1( i );
 962         }
 963
 964 #if 0
 965         // count up the total bits
 966         total = 0;
 967         for ( i = 0 ; i < 256 ; i++ )
 968                 for ( j = 0 ; j < 256 ; j++ )
 969                         total += charbitscount1[i][j] * hnodes1[i][j].count;
 970
 971         total = ( total + 7 ) / 8;
 972         printf( "%i bytes huffman1 compressed\n", total );
 973 #endif
 974
 975         fwrite( scaled, 1, sizeof( scaled ), f );
 976 }
 977
 978 /*
 979    ==================
 980    Huffman1
 981
 982    Order 1 compression with pre-built table
 983    ==================
 984  */
 985 cblock_t Huffman1( cblock_t in ){
 986         int i;
 987         int outbits, c;
 988         unsigned bits;
 989         byte        *out_p;
 990         cblock_t out;
 991         int prev;
 992         int v;
 993         int rept;
 994
 995         out_p = out.data = malloc( in.count * 2 + 1024 );
 996         memset( out_p, 0, in.count * 2 + 1024 );
 997
 998         // write count
 999         *out_p++ = in.count & 255;
1000         *out_p++ = ( in.count >> 8 ) & 255;
1001         *out_p++ = ( in.count >> 16 ) & 255;
1002         *out_p++ = ( in.count >> 24 ) & 255;
1003
1004         // write bits
1005         outbits = 0;
1006         prev = 0;
1007         for ( i = 0 ; i < in.count ; i++ )
1008         {
1009                 v = in.data[i];
1010
1011                 c = charbitscount1[prev][v];
1012                 bits = charbits1[prev][v];
1013                 if ( !c ) {
1014                         Error( "!bits" );
1015                 }
1016                 while ( c )
1017                 {
1018                         c--;
1019                         if ( bits & ( 1 << c ) ) {
1020                                 out_p[outbits >> 3] |= 1 << ( outbits & 7 );
1021                         }
1022                         outbits++;
1023                 }
1024
1025                 prev = v;
1026 #if 1
1027                 // check for repeat encodes
1028                 for ( rept = 1 ; i + rept < in.count && rept < MAX_REPT ; rept++ )
1029                         if ( in.data[i + rept] != v ) {
1030                                 break;
1031                         }
1032                 if ( rept > MIN_REPT ) {
1033                         c = charbitscount1[prev][255 + rept];
1034                         bits = charbits1[prev][255 + rept];
1035                         if ( !c ) {
1036                                 Error( "!bits" );
1037                         }
1038                         while ( c )
1039                         {
1040                                 c--;
1041                                 if ( bits & ( 1 << c ) ) {
1042                                         out_p[outbits >> 3] |= 1 << ( outbits & 7 );
1043                                 }
1044                                 outbits++;
1045                         }
1046                         i += rept - 1;
1047                 }
1048 #endif
1049         }
1050
1051         out_p += ( outbits + 7 ) >> 3;
1052
1053         out.count = out_p - out.data;
1054
1055         return out;
1056 }
1057
1058 //==========================================================================
1059
1060
1061 /*
1062    ===================
1063    LoadFrame
1064    ===================
1065  */
1066 cblock_t LoadFrame( char *base, int frame, int digits, byte **palette ){
1067         int ten3, ten2, ten1, ten0;
1068         cblock_t in;
1069         int width, height;
1070         char name[1024];
1071         FILE        *f;
1072
1073         in.data = NULL;
1074         in.count = -1;
1075
1076         ten3 = frame / 1000;
1077         ten2 = ( frame - ten3 * 1000 ) / 100;
1078         ten1 = ( frame - ten3 * 1000 - ten2 * 100 ) / 10;
1079         ten0 = frame % 10;
1080
1081         if ( digits == 4 ) {
1082                 sprintf( name, "%svideo/%s/%s%i%i%i%i.pcx", gamedir, base, base, ten3, ten2, ten1, ten0 );
1083         }
1084         else{
1085                 sprintf( name, "%svideo/%s/%s%i%i%i.pcx", gamedir, base, base, ten2, ten1, ten0 );
1086         }
1087
1088         f = fopen( name, "rb" );
1089         if ( !f ) {
1090                 in.data = NULL;
1091                 return in;
1092         }
1093         fclose( f );
1094
1095         printf( "%s\n", name );
1096         Load256Image( name, &in.data, palette, &width, &height );
1097         in.count = width * height;
1098 // FIXME: map 0 and 255!
1099
1100 #if 0
1101         // rle compress
1102         rle = RLE( in );
1103         free( in.data );
1104
1105         return rle;
1106 #endif
1107
1108         return in;
1109 }
1110
1111 /*
1112    ===============
1113    Cmd_Video
1114
1115    video <directory> <framedigits>
1116    ===============
1117  */
1118 void Cmd_Video( void ){
1119         char savename[1024];
1120         char name[1024];
1121         FILE    *output;
1122         int startframe, frame;
1123         byte    *palette;
1124         int width, height;
1125         byte current_palette[768];
1126         int command;
1127         int i;
1128         int digits;
1129         cblock_t in, huffman;
1130         int swap;
1131
1132
1133         GetToken( false );
1134         strcpy( base, token );
1135         if ( g_release ) {
1136 //              sprintf (savename, "video/%s.cin", token);
1137 //              ReleaseFile (savename);
1138                 return;
1139         }
1140
1141         GetToken( false );
1142         digits = atoi( token );
1143
1144         // optionally skip frames
1145         if ( TokenAvailable() ) {
1146                 GetToken( false );
1147                 startframe = atoi( token );
1148         }
1149         else{
1150                 startframe = 0;
1151         }
1152
1153         sprintf( savename, "%svideo/%s.cin", gamedir, base );
1154
1155
1156         // clear stuff
1157         memset( charbits1, 0, sizeof( charbits1 ) );
1158         memset( charbitscount1, 0, sizeof( charbitscount1 ) );
1159         memset( hnodes1, 0, sizeof( hnodes1 ) );
1160         memset( numhnodes1, 0, sizeof( numhnodes1 ) );
1161         memset( order0counts, 0, sizeof( order0counts ) );
1162
1163
1164         // load the entire sound wav file if present
1165         LoadSoundtrack();
1166
1167         if ( digits == 4 ) {
1168                 sprintf( name, "%svideo/%s/%s0000.pcx", gamedir, base, base );
1169         }
1170         else{
1171                 sprintf( name, "%svideo/%s/%s000.pcx", gamedir, base, base );
1172         }
1173
1174         printf( "%s\n", name );
1175         Load256Image( name, NULL, &palette, &width, &height );
1176
1177         output = fopen( savename, "wb" );
1178         if ( !output ) {
1179                 Error( "Can't open %s", savename );
1180         }
1181
1182         // write header info
1183         i = LittleLong( width );
1184         fwrite( &i, 4, 1, output );
1185         i = LittleLong( height );
1186         fwrite( &i, 4, 1, output );
1187         i = LittleLong( wavinfo.rate );
1188         fwrite( &i, 4, 1, output );
1189         i = LittleLong( wavinfo.width );
1190         fwrite( &i, 4, 1, output );
1191         i = LittleLong( wavinfo.channels );
1192         fwrite( &i, 4, 1, output );
1193
1194         // build the dictionary
1195         for ( frame = startframe ;  ; frame++ )
1196         {
1197                 printf( "counting ", frame );
1198                 in = LoadFrame( base, frame, digits, &palette );
1199                 if ( !in.data ) {
1200                         break;
1201                 }
1202                 Huffman1_Count( in );
1203                 free( in.data );
1204         }
1205         printf( "\n" );
1206
1207         // build nodes and write counts
1208         Huffman1_Build( output );
1209
1210
1211         memset( current_palette, 0, sizeof( current_palette ) );
1212
1213         // compress it with the dictionary
1214         for ( frame = startframe ;  ; frame++ )
1215         {
1216                 printf( "packing ", frame );
1217                 in = LoadFrame( base, frame, digits, &palette );
1218                 if ( !in.data ) {
1219                         break;
1220                 }
1221
1222                 // see if the palette has changed
1223                 for ( i = 0 ; i < 768 ; i++ )
1224                         if ( palette[i] != current_palette[i] ) {
1225                                 // write a palette change
1226                                 memcpy( current_palette, palette, sizeof( current_palette ) );
1227                                 command = LittleLong( 1 );
1228                                 fwrite( &command, 1, 4, output );
1229                                 fwrite( current_palette, 1, sizeof( current_palette ), output );
1230                                 break;
1231                         }
1232                 if ( i == 768 ) {
1233                         command = 0;    // no palette change
1234                         fwrite( &command, 1, 4, output );
1235                 }
1236
1237                 // save the image
1238                 huffman = Huffman1( in );
1239                 printf( "%5i bytes after huffman1\n", huffman.count );
1240
1241                 swap = LittleLong( huffman.count );
1242                 fwrite( &swap, 1, sizeof( swap ), output );
1243
1244                 fwrite( huffman.data, 1, huffman.count, output );
1245
1246                 // save some sound samples
1247                 WriteSound( output, frame );
1248
1249                 free( palette );
1250                 free( in.data );
1251                 free( huffman.data );
1252         }
1253         printf( "\n" );
1254
1255         // write end-of-file command
1256         command = 2;
1257         fwrite( &command, 1, 4, output );
1258
1259         printf( "Total size: %i\n", ftell( output ) );
1260
1261         fclose( output );
1262
1263         if ( soundtrack ) {
1264                 free( soundtrack );
1265         }
1266 }