tools/quake2/qdata/video.c

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