2 Copyright (C) 1999-2006 Id Software, Inc. and contributors.
3 For a list of contributors, see the accompanying CONTRIBUTORS file.
5 This file is part of GtkRadiant.
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.
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.
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
29 ===============================================================================
33 ===============================================================================
43 int dataofs; // chunk starts this many bytes from file start
54 int samplecounts[0x10000];
58 short GetLittleShort( void ){
61 val = val + ( *( data_p + 1 ) << 8 );
66 int GetLittleLong( void ){
69 val = val + ( *( data_p + 1 ) << 8 );
70 val = val + ( *( data_p + 2 ) << 16 );
71 val = val + ( *( data_p + 3 ) << 24 );
76 void FindNextChunk( char *name ){
81 if ( data_p >= iff_end ) { // didn't find the chunk
87 iff_chunk_len = GetLittleLong();
88 if ( iff_chunk_len < 0 ) {
92 // if (iff_chunk_len > 1024*1024)
93 // Sys_Error ("FindNextChunk: %i length is past the 1 meg sanity limit", iff_chunk_len);
95 last_chunk = data_p + 8 + ( ( iff_chunk_len + 1 ) & ~1 );
96 if ( !strncmp( data_p, name, 4 ) ) {
102 void FindChunk( char *name ){
103 last_chunk = iff_data;
104 FindNextChunk( name );
108 void DumpChunks( void ){
115 memcpy( str, 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 );
128 wavinfo_t GetWavinfo( char *name, byte *wav, int wavlength ){
134 memset( &info, 0, sizeof( info ) );
141 iff_end = wav + wavlength;
145 if ( !( data_p && !strncmp( data_p + 8, "WAVE", 4 ) ) ) {
146 printf( "Missing RIFF/WAVE chunks\n" );
151 iff_data = data_p + 12;
156 printf( "Missing fmt chunk\n" );
160 format = GetLittleShort();
162 printf( "Microsoft PCM format only\n" );
166 info.channels = GetLittleShort();
167 info.rate = GetLittleLong();
169 info.width = GetLittleShort() / 8;
175 info.loopstart = GetLittleLong();
176 // Com_Printf("loopstart=%d\n", sfx->loopstart);
178 // if the next chunk is a LIST chunk, look for a cue length marker
179 FindNextChunk( "LIST" );
181 if ( !strncmp( data_p + 28, "mark", 4 ) ) { // this is not a proper parse, but it works with cooledit...
183 i = GetLittleLong(); // samples in loop
184 info.samples = info.loopstart + i;
195 printf( "Missing data chunk\n" );
200 samples = GetLittleLong();
202 if ( info.samples ) {
203 if ( samples < info.samples ) {
204 Error( "Sound %s has a bad loop length", name );
208 info.samples = samples;
211 info.dataofs = data_p - wav;
216 //=====================================================================
223 void LoadSoundtrack( void ){
230 sprintf( name, "%svideo/%s/%s.wav", gamedir, base, base );
231 printf( "%s\n", name );
232 f = fopen( name, "rb" );
234 printf( "no soundtrack for %s\n", base );
237 len = Q_filelength( f );
238 soundtrack = malloc( len );
239 fread( soundtrack, 1, len, f );
242 wavinfo = GetWavinfo( name, soundtrack, len );
244 // count samples for compression
245 memset( samplecounts, 0, sizeof( samplecounts ) );
247 j = wavinfo.samples / 2;
248 for ( i = 0 ; i < j ; i++ )
250 val = ( (unsigned short *)( soundtrack + wavinfo.dataofs ) )[i];
254 for ( i = 0 ; i < 0x10000 ; i++ )
255 if ( samplecounts[i] ) {
259 printf( "%i unique sample values\n", val );
267 void WriteSound( FILE *output, int frame ){
275 width = wavinfo.width * wavinfo.channels;
277 start = frame * wavinfo.rate / 14;
278 end = ( frame + 1 ) * wavinfo.rate / 14;
281 for ( i = 0 ; i < count ; i++ )
284 if ( sample > wavinfo.samples || !soundtrack ) {
285 fwrite( &empty, 1, width, output );
288 fwrite( soundtrack + wavinfo.dataofs + sample * width, 1, width,output );
293 //==========================================================================
300 cblock_t MTF( cblock_t in ){
306 out_p = out.data = malloc( in.count + 4 );
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;
314 for ( i = 0 ; i < 256 ; i++ )
317 for ( i = 0 ; i < in.count ; i++ )
323 // shuffle b indexes to 0
324 for ( j = 0 ; j < 256 ; j++ )
325 if ( index[j] < code ) {
331 out.count = out_p - out.data;
337 //==========================================================================
342 int bwtCompare( const void *elem1, const void *elem2 ){
350 for ( i = 0 ; i < bwt_size ; i++ )
360 if ( ++i1 == bwt_size ) {
363 if ( ++i2 == bwt_size ) {
376 cblock_t BWT( cblock_t in ){
385 sorted = malloc( in.count * sizeof( *sorted ) );
386 for ( i = 0 ; i < in.count ; i++ )
388 qsort( sorted, in.count, sizeof( *sorted ), bwtCompare );
390 out_p = out.data = malloc( in.count + 8 );
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;
399 for ( i = 0 ; i < in.count ; i++ )
400 if ( sorted[i] == 0 ) {
404 *out_p++ = ( i >> 8 ) & 255;
405 *out_p++ = ( i >> 16 ) & 255;
406 *out_p++ = ( i >> 24 ) & 255;
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];
414 out.count = out_p - out.data;
419 //==========================================================================
421 typedef struct hnode_s
430 unsigned charbits[256];
431 int charbitscount[256];
433 int SmallestNode( void ){
439 for ( i = 0 ; i < numhnodes ; i++ )
441 if ( hnodes[i].used ) {
444 if ( !hnodes[i].count ) {
447 if ( hnodes[i].count < best ) {
448 best = hnodes[i].count;
453 if ( bestnode == -1 ) {
457 hnodes[bestnode].used = true;
461 void BuildChars( int nodenum, unsigned bits, int bitcount ){
464 if ( nodenum < 256 ) {
465 if ( bitcount > 32 ) {
466 Error( "bitcount > 32" );
468 charbits[nodenum] = bits;
469 charbitscount[nodenum] = bitcount;
473 node = &hnodes[nodenum];
475 BuildChars( node->children[0], bits, bitcount + 1 );
477 BuildChars( node->children[1], bits, bitcount + 1 );
486 cblock_t Huffman( cblock_t in ){
496 memset( hnodes, 0, sizeof( hnodes ) );
497 for ( i = 0 ; i < in.count ; i++ )
498 hnodes[in.data[i]].count++;
503 for ( i = 0 ; i < 256 ; i++ )
505 if ( hnodes[i].count > max ) {
506 max = hnodes[i].count;
511 Error( "Huffman: max == 0" );
514 for ( i = 0 ; i < 256 ; i++ )
516 hnodes[i].count = ( hnodes[i].count * 255 + max - 1 ) / max;
521 while ( numhnodes != 511 )
523 node = &hnodes[numhnodes];
525 // pick two lowest counts
526 node->children[0] = SmallestNode();
527 if ( node->children[0] == -1 ) {
531 node->children[1] = SmallestNode();
532 if ( node->children[1] == -1 ) {
533 if ( node->children[0] != numhnodes - 1 ) {
534 Error( "Bad smallestnode" );
538 node->count = hnodes[node->children[0]].count +
539 hnodes[node->children[1]].count;
543 BuildChars( numhnodes - 1, 0, 0 );
545 out_p = out.data = malloc( in.count * 2 + 1024 );
546 memset( out_p, 0, in.count * 2 + 1024 );
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;
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;
560 for ( i = 0 ; i < in.count ; i++ )
562 c = charbitscount[in.data[i]];
563 bits = charbits[in.data[i]];
567 if ( bits & ( 1 << c ) ) {
568 out_p[outbits >> 3] |= 1 << ( outbits & 7 );
574 out_p += ( outbits + 7 ) >> 3;
576 out.count = out_p - out.data;
581 //==========================================================================
588 #define RLE_CODE 0xe8
589 #define RLE_TRIPPLE 0xe9
594 cblock_t RLE( cblock_t in ){
601 out_p = out.data = malloc( in.count * 2 );
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;
609 for ( i = 0 ; i < in.count ; )
615 while ( i < in.count && repeat < 255 && in.data[i] == val )
620 if ( repeat < 256 ) {
621 rle_counts[repeat]++;
623 if ( repeat > 3 || val == RLE_CODE ) {
635 out.count = out_p - out.data;
639 //==========================================================================
641 unsigned lzss_head[256];
642 unsigned lzss_next[0x20000];
649 #define BACK_WINDOW 0x10000
651 #define FRONT_WINDOW 16
653 cblock_t LZSS( cblock_t in ){
659 int bestlength, beststart;
662 if ( in.count >= sizeof( lzss_next ) / 4 ) {
663 Error( "LZSS: too big" );
666 memset( lzss_head, -1, sizeof( lzss_head ) );
668 out_p = out.data = malloc( in.count * 2 );
669 memset( out.data, 0, in.count * 2 );
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;
678 for ( i = 0 ; i < in.count ; )
687 if ( i + max > in.count ) {
691 start = lzss_head[val];
692 while ( start != -1 && start >= i - BACK_WINDOW )
694 // count match length
695 for ( j = 0 ; j < max ; j++ )
696 if ( in.data[start + j] != in.data[i + j] ) {
699 if ( j > bestlength ) {
703 start = lzss_next[start];
707 // slow simple search
708 // search for a match
710 if ( i + max > in.count ) {
714 start = i - BACK_WINDOW;
720 for ( ; start < i ; start++ )
722 if ( in.data[start] != val ) {
725 // count match length
726 for ( j = 0 ; j < max ; j++ )
727 if ( in.data[start + j] != in.data[i + j] ) {
730 if ( j > bestlength ) {
736 beststart = BACK_WINDOW - ( i - beststart );
738 if ( bestlength < 3 ) { // output a single char
741 out_p[outbits >> 3] |= 1 << ( outbits & 7 ); // set bit to mark char
743 for ( j = 0 ; j < 8 ; j++, outbits++ )
744 if ( val & ( 1 << j ) ) {
745 out_p[outbits >> 3] |= 1 << ( outbits & 7 );
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 );
755 for ( j = 0 ; j < FRONT_BITS ; j++, outbits++ )
756 if ( bestlength & ( 1 << j ) ) {
757 out_p[outbits >> 3] |= 1 << ( outbits & 7 );
761 while ( bestlength-- )
764 lzss_next[i] = lzss_head[val];
770 out_p += ( outbits + 7 ) >> 3;
771 out.count = out_p - out.data;
775 //==========================================================================
779 #define HUF_TOKENS ( 256 + MAX_REPT )
781 unsigned charbits1[256][HUF_TOKENS];
782 int charbitscount1[256][HUF_TOKENS];
784 hnode_t hnodes1[256][HUF_TOKENS * 2];
787 int order0counts[256];
794 int SmallestNode1( hnode_t *hnodes, int numhnodes ){
800 for ( i = 0 ; i < numhnodes ; i++ )
802 if ( hnodes[i].used ) {
805 if ( !hnodes[i].count ) {
808 if ( hnodes[i].count < best ) {
809 best = hnodes[i].count;
814 if ( bestnode == -1 ) {
818 hnodes[bestnode].used = true;
828 void BuildChars1( int prev, int nodenum, unsigned bits, int bitcount ){
831 if ( nodenum < HUF_TOKENS ) {
832 if ( bitcount > 32 ) {
833 Error( "bitcount > 32" );
835 charbits1[prev][nodenum] = bits;
836 charbitscount1[prev][nodenum] = bitcount;
840 node = &hnodes1[prev][nodenum];
842 BuildChars1( prev, node->children[0], bits, bitcount + 1 );
844 BuildChars1( prev, node->children[1], bits, bitcount + 1 );
853 void BuildTree1( int prev ){
854 hnode_t *node, *nodebase;
858 numhnodes = HUF_TOKENS;
859 nodebase = hnodes1[prev];
862 node = &nodebase[numhnodes];
864 // pick two lowest counts
865 node->children[0] = SmallestNode1( nodebase, numhnodes );
866 if ( node->children[0] == -1 ) {
870 node->children[1] = SmallestNode1( nodebase, numhnodes );
871 if ( node->children[1] == -1 ) {
875 node->count = nodebase[node->children[0]].count +
876 nodebase[node->children[1]].count;
879 numhnodes1[prev] = numhnodes - 1;
880 BuildChars1( prev, numhnodes - 1, 0, 0 );
889 void Huffman1_Count( cblock_t in ){
896 for ( i = 0 ; i < in.count ; i++ )
900 hnodes1[prev][v].count++;
903 for ( rept = 1 ; i + rept < in.count && rept < MAX_REPT ; rept++ )
904 if ( in.data[i + rept] != v ) {
907 if ( rept > MIN_REPT ) {
908 hnodes1[prev][255 + rept].count++;
921 byte scaled[256][HUF_TOKENS];
922 void Huffman1_Build( FILE *f ){
927 for ( i = 0 ; i < 256 ; i++ )
929 // normalize and save the counts
931 for ( j = 0 ; j < HUF_TOKENS ; j++ )
933 if ( hnodes1[i][j].count > max ) {
934 max = hnodes1[i][j].count;
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;
947 scaled[i][j] = hnodes1[i][j].count = v;
952 if ( total == 1 ) { // must have two tokens
953 if ( !scaled[i][0] ) {
954 scaled[i][0] = hnodes1[i][0].count = 1;
957 scaled[i][1] = hnodes1[i][1].count = 1;
965 // count up the total bits
967 for ( i = 0 ; i < 256 ; i++ )
968 for ( j = 0 ; j < 256 ; j++ )
969 total += charbitscount1[i][j] * hnodes1[i][j].count;
971 total = ( total + 7 ) / 8;
972 printf( "%i bytes huffman1 compressed\n", total );
975 fwrite( scaled, 1, sizeof( scaled ), f );
982 Order 1 compression with pre-built table
985 cblock_t Huffman1( cblock_t in ){
995 out_p = out.data = malloc( in.count * 2 + 1024 );
996 memset( out_p, 0, in.count * 2 + 1024 );
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;
1007 for ( i = 0 ; i < in.count ; i++ )
1011 c = charbitscount1[prev][v];
1012 bits = charbits1[prev][v];
1019 if ( bits & ( 1 << c ) ) {
1020 out_p[outbits >> 3] |= 1 << ( outbits & 7 );
1027 // check for repeat encodes
1028 for ( rept = 1 ; i + rept < in.count && rept < MAX_REPT ; rept++ )
1029 if ( in.data[i + rept] != v ) {
1032 if ( rept > MIN_REPT ) {
1033 c = charbitscount1[prev][255 + rept];
1034 bits = charbits1[prev][255 + rept];
1041 if ( bits & ( 1 << c ) ) {
1042 out_p[outbits >> 3] |= 1 << ( outbits & 7 );
1051 out_p += ( outbits + 7 ) >> 3;
1053 out.count = out_p - out.data;
1058 //==========================================================================
1066 cblock_t LoadFrame( char *base, int frame, int digits, byte **palette ){
1067 int ten3, ten2, ten1, ten0;
1076 ten3 = frame / 1000;
1077 ten2 = ( frame - ten3 * 1000 ) / 100;
1078 ten1 = ( frame - ten3 * 1000 - ten2 * 100 ) / 10;
1081 if ( digits == 4 ) {
1082 sprintf( name, "%svideo/%s/%s%i%i%i%i.pcx", gamedir, base, base, ten3, ten2, ten1, ten0 );
1085 sprintf( name, "%svideo/%s/%s%i%i%i.pcx", gamedir, base, base, ten2, ten1, ten0 );
1088 f = fopen( name, "rb" );
1095 printf( "%s\n", name );
1096 Load256Image( name, &in.data, palette, &width, &height );
1097 in.count = width * height;
1098 // FIXME: map 0 and 255!
1115 video <directory> <framedigits>
1118 void Cmd_Video( void ){
1119 char savename[1024];
1122 int startframe, frame;
1125 byte current_palette[768];
1129 cblock_t in, huffman;
1134 strcpy( base, token );
1136 // sprintf (savename, "video/%s.cin", token);
1137 // ReleaseFile (savename);
1142 digits = atoi( token );
1144 // optionally skip frames
1145 if ( TokenAvailable() ) {
1147 startframe = atoi( token );
1153 sprintf( savename, "%svideo/%s.cin", gamedir, base );
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 ) );
1164 // load the entire sound wav file if present
1167 if ( digits == 4 ) {
1168 sprintf( name, "%svideo/%s/%s0000.pcx", gamedir, base, base );
1171 sprintf( name, "%svideo/%s/%s000.pcx", gamedir, base, base );
1174 printf( "%s\n", name );
1175 Load256Image( name, NULL, &palette, &width, &height );
1177 output = fopen( savename, "wb" );
1179 Error( "Can't open %s", savename );
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 );
1194 // build the dictionary
1195 for ( frame = startframe ; ; frame++ )
1197 printf( "counting ", frame );
1198 in = LoadFrame( base, frame, digits, &palette );
1202 Huffman1_Count( in );
1207 // build nodes and write counts
1208 Huffman1_Build( output );
1211 memset( current_palette, 0, sizeof( current_palette ) );
1213 // compress it with the dictionary
1214 for ( frame = startframe ; ; frame++ )
1216 printf( "packing ", frame );
1217 in = LoadFrame( base, frame, digits, &palette );
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 );
1233 command = 0; // no palette change
1234 fwrite( &command, 1, 4, output );
1238 huffman = Huffman1( in );
1239 printf( "%5i bytes after huffman1\n", huffman.count );
1241 swap = LittleLong( huffman.count );
1242 fwrite( &swap, 1, sizeof( swap ), output );
1244 fwrite( huffman.data, 1, huffman.count, output );
1246 // save some sound samples
1247 WriteSound( output, frame );
1251 free( huffman.data );
1255 // write end-of-file command
1257 fwrite( &command, 1, 4, output );
1259 printf( "Total size: %i\n", ftell( output ) );