tools/quake2/qdata/video.c

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