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