SnapPlane reenabled by namespace because of multiple reports of
[xonotic/netradiant.git] / 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 }