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