2 Copyright (C) 1999-2007 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
24 // Sound error handling (when sound too short)
26 // adpcm encoding of sound
36 #define HUF_TOKENS ( 256 + MAX_REPT )
40 #define M_PI 3.14159265358979323846 // matches value in gcc v2 math.h
41 #define SQRT2 1.414213562
43 typedef struct hnode_s
57 int dataofs; // chunk starts this many bytes from file start
60 // These weren`t picked out my ass....
61 // They were defined at http://www.rahul.net/jfm/dct.html
62 // However, I think he plucked them out of his ass.....
64 float Quantise[BLOCKSIZE * BLOCKSIZE];
66 float LUT_Quantise[BLOCKSIZE * BLOCKSIZE] =
68 16.0F / 16.0F, 11.0F / 16.0F, 10.0F / 16.0F, 16.0F / 16.0F, 24.0F / 16.0F, 40.0F / 16.0F, 51.0F / 16.0F, 61.0F / 16.0F,
69 12.0F / 16.0F, 13.0F / 16.0F, 14.0F / 16.0F, 19.0F / 16.0F, 26.0F / 16.0F, 58.0F / 16.0F, 60.0F / 16.0F, 55.0F / 16.0F,
70 14.0F / 16.0F, 13.0F / 16.0F, 16.0F / 16.0F, 24.0F / 16.0F, 40.0F / 16.0F, 57.0F / 16.0F, 69.0F / 16.0F, 56.0F / 16.0F,
71 14.0F / 16.0F, 17.0F / 16.0F, 22.0F / 16.0F, 29.0F / 16.0F, 51.0F / 16.0F, 87.0F / 16.0F, 80.0F / 16.0F, 62.0F / 16.0F,
72 18.0F / 16.0F, 22.0F / 16.0F, 37.0F / 16.0F, 56.0F / 16.0F, 68.0F / 16.0F,109.0F / 16.0F,103.0F / 16.0F, 77.0F / 16.0F,
73 24.0F / 16.0F, 35.0F / 16.0F, 55.0F / 16.0F, 64.0F / 16.0F, 81.0F / 16.0F,104.0F / 16.0F,113.0F / 16.0F, 92.0F / 16.0F,
74 49.0F / 16.0F, 64.0F / 16.0F, 78.0F / 16.0F, 87.0F / 16.0F,103.0F / 16.0F,121.0F / 16.0F,120.0F / 16.0F,101.0F / 16.0F,
75 72.0F / 16.0F, 92.0F / 16.0F, 95.0F / 16.0F, 98.0F / 16.0F,112.0F / 16.0F,100.0F / 16.0F,103.0F / 16.0F, 99.0F / 16.0F
78 int LUT_ZZ[BLOCKSIZE * BLOCKSIZE] =
85 5, 12, 19, 26, 33, 40,
86 48, 41, 34, 27, 20, 13, 6,
87 7, 14, 21, 28, 35, 42, 49, 56,
88 57, 50, 43, 36, 29, 22, 15,
89 23, 30, 37, 44, 51, 58,
101 byte scaled[256][HUF_TOKENS];
102 unsigned int charbits1[256][HUF_TOKENS];
103 int charbitscount1[256][HUF_TOKENS];
104 hnode_t hnodes1[256][HUF_TOKENS * 2];
106 int order0counts[256];
109 unsigned charbits[256];
110 int charbitscount[256];
120 float dctbase[BLOCKSIZE][BLOCKSIZE];
121 float red[BLOCKSIZE * BLOCKSIZE];
122 float green[BLOCKSIZE * BLOCKSIZE];
123 float blue[BLOCKSIZE * BLOCKSIZE];
124 float temp[BLOCKSIZE * BLOCKSIZE];
130 ===============================================================================
134 ===============================================================================
137 /* Intel ADPCM step variation table */
138 static int indexTable[16] =
140 -1, -1, -1, -1, 2, 4, 6, 8,
141 -1, -1, -1, -1, 2, 4, 6, 8,
144 static int stepsizeTable[89] =
146 7, 8, 9, 10, 11, 12, 13, 14, 16, 17,
147 19, 21, 23, 25, 28, 31, 34, 37, 41, 45,
148 50, 55, 60, 66, 73, 80, 88, 97, 107, 118,
149 130, 143, 157, 173, 190, 209, 230, 253, 279, 307,
150 337, 371, 408, 449, 494, 544, 598, 658, 724, 796,
151 876, 963, 1060, 1166, 1282, 1411, 1552, 1707, 1878, 2066,
152 2272, 2499, 2749, 3024, 3327, 3660, 4026, 4428, 4871, 5358,
153 5894, 6484, 7132, 7845, 8630, 9493, 10442, 11487, 12635, 13899,
154 15289, 16818, 18500, 20350, 22385, 24623, 27086, 29794, 32767
158 static void adpcm_decoder( char *indata, short *outdata, int len, adpcm_state_t *state ){
159 signed char *inp; /* Input buffer pointer */
160 short *outp; /* output buffer pointer */
161 int sign; /* Current adpcm sign bit */
162 int delta; /* Current adpcm output value */
163 int step; /* Stepsize */
164 int valpred; /* Predicted value */
165 int vpdiff; /* Current change to valpred */
166 int index; /* Current step change index */
167 int inputbuffer; /* place to keep next 4-bit value */
168 int bufferstep; /* toggle between inputbuffer/input */
171 inp = (signed char *)indata;
173 valpred = state->valprev;
174 index = state->index;
175 step = stepsizeTable[index];
179 for (; len > 0; len-- )
181 /* Step 1 - get the delta value */
183 delta = inputbuffer & 0xf;
187 inputbuffer = *inp++;
188 delta = ( inputbuffer >> 4 ) & 0xf;
190 bufferstep = !bufferstep;
192 /* Step 2 - Find new index value (for later) */
193 index += indexTable[delta];
201 /* Step 3 - Separate sign and magnitude */
205 /* Step 4 - Compute difference and new predicted value */
207 ** Computes 'vpdiff = (delta+0.5)*step/4', but see comment
228 /* Step 5 - clamp output value */
229 if ( valpred > 32767 ) {
232 else if ( valpred < -32768 ) {
236 /* Step 6 - Update step value */
237 step = stepsizeTable[index];
239 /* Step 7 - Output value */
243 state->valprev = valpred;
244 state->index = index;
248 void adpcm_coder( short *inp, adpcm_t *adpcm ){
249 int val; /* Current input sample value */
250 int sign; /* Current adpcm sign bit */
251 int delta; /* Current adpcm output value */
252 int diff; /* Difference between val and valprev */
253 int step; /* Stepsize */
254 int valpred; /* Predicted output value */
255 int vpdiff; /* Current change to valpred */
256 int index; /* Current step change index */
257 int outputbuffer; /* place to keep previous 4-bit value */
258 int bufferstep; /* toggle between outputbuffer/output */
259 adpcm_state_t *state;
263 state = &adpcm->state;
267 valpred = state->in_valprev;
268 index = state->in_index;
269 step = stepsizeTable[index];
276 /* Step 1 - compute difference with previous value */
277 diff = val - valpred;
278 sign = ( diff < 0 ) ? 8 : 0;
283 /* Step 2 - Divide and clamp */
285 ** This code *approximately* computes:
286 ** delta = diff*4/step;
287 ** vpdiff = (delta+0.5)*step/4;
288 ** but in shift step bits are dropped. The net result of this is
289 ** that even if you have fast mul/div hardware you cannot put it to
290 ** good use since the fixup would be too expensive.
293 vpdiff = ( step >> 3 );
295 if ( diff >= step ) {
301 if ( diff >= step ) {
307 if ( diff >= step ) {
312 /* Step 3 - Update previous value */
320 /* Step 4 - Clamp previous value to 16 bits */
321 if ( valpred > 32767 ) {
324 else if ( valpred < -32768 ) {
328 /* Step 5 - Assemble value, update index and step values */
331 index += indexTable[delta];
338 step = stepsizeTable[index];
340 /* Step 6 - Output value */
342 outputbuffer = ( delta << 4 ) & 0xf0;
345 *outp++ = ( delta & 0x0f ) | outputbuffer;
348 bufferstep = !bufferstep;
351 /* Output last step, if needed */
353 *outp++ = outputbuffer;
356 state->out_valprev = valpred;
357 state->out_index = index;
360 void FindNextChunk( char *name ){
365 if ( data_p >= iff_end ) { // didn't find the chunk
371 iff_chunk_len = *(long *)data_p;
373 if ( iff_chunk_len < 0 ) {
379 last_chunk = data_p + 8 + ( ( iff_chunk_len + 1 ) & ~1 );
380 if ( !strncmp( data_p, name, 4 ) ) {
386 void FindChunk( char *name ){
387 last_chunk = iff_data;
388 FindNextChunk( name );
391 void DumpChunks( void ){
398 memcpy( str, data_p, 4 );
400 iff_chunk_len = *(long *)data_p;
402 printf( "0x%x : %s (%d)\n", (int)( data_p - 4 ), str, iff_chunk_len );
403 data_p += ( iff_chunk_len + 1 ) & ~1;
405 while ( data_p < iff_end );
413 wavinfo_t GetWavinfo( char *name, byte *wav, int wavlength ){
419 memset( &info, 0, sizeof( info ) );
426 iff_end = wav + wavlength;
430 if ( !( data_p && !strncmp( data_p + 8, "WAVE", 4 ) ) ) {
431 printf( "Missing RIFF/WAVE chunks\n" );
436 iff_data = data_p + 12;
440 printf( "Missing fmt chunk\n" );
444 format = *(short *)data_p;
447 printf( "Microsoft PCM format only\n" );
451 info.channels = *(short *)data_p;
453 info.rate = *(long *)data_p;
456 info.width = *(short *)data_p / 8;
463 info.loopstart = *(long *)data_p;
466 // if the next chunk is a LIST chunk, look for a cue length marker
467 FindNextChunk( "LIST" );
469 // this is not a proper parse, but it works with cooledit...
470 if ( !strncmp( data_p + 28, "mark", 4 ) ) {
472 i = *(long *)data_p; // samples in loop
474 info.samples = info.loopstart + i;
485 printf( "Missing data chunk\n" );
490 samples = *(long *)data_p;
493 if ( info.samples ) {
494 if ( samples < info.samples ) {
495 Error( "Sound %s has a bad loop length", name );
499 info.samples = samples;
502 info.dataofs = data_p - wav;
510 void LoadSoundtrack(){
516 sprintf( name, "%svideo/%s/%s.wav", gamedir, base, base );
517 printf( "\nLoading sound : %s\n", name );
518 f = fopen( name, "rb" );
520 printf( "\nNo soundtrack for %s\n", base );
523 len = Q_filelength( f );
524 soundtrack = SafeMalloc( len, "LoadSoundtrack" );
525 fread( soundtrack, 1, len, f );
528 wavinfo = GetWavinfo( name, soundtrack, len );
529 adpcm.state.out_valprev = 0;
530 adpcm.state.out_index = 0;
533 // ==================
535 // ==================
537 int WriteSound( FILE *output, int frame, int numframes ){
544 width = wavinfo.width * wavinfo.channels;
545 start = ( ( frame * wavinfo.rate / 14 ) + 31 ) & 0xffffffe0; // start sample
546 end = ( ( ( frame + numframes ) * wavinfo.rate / 14 ) + 31 ) & 0xffffffe0; // end sample
549 work = soundtrack + wavinfo.dataofs + ( start * width );
550 adpcm.state.count = count * wavinfo.channels; // Number of samples
551 adpcm.state.in_valprev = adpcm.state.out_valprev;
552 adpcm.state.in_index = adpcm.state.out_index;
553 adpcm_coder( (short *)work, &adpcm );
554 WriteHeader( output, FC_SOUND_22KMADPCM, FC_ADPCM_VERSION, ( adpcm.state.count / 2 ) + sizeof( adpcm_state_t ), (char *)&adpcm );
557 // ==============================
558 // Basic run length encoder
559 // ==============================
561 char *RLEZZ( char *in, char *out ){
568 srun = idx; // Start of run
572 if ( in[LUT_ZZ[idx]] != in[LUT_ZZ[idx + 1]] ) {
577 count = (char)( idx - srun ); // count of repeated bytes
582 if ( in[LUT_ZZ[idx]] == in[LUT_ZZ[idx + 1]] ) {
591 count = (char)( idx - srun ); // count of unique bytes
594 *out++ = in[LUT_ZZ[srun++]];
598 *out++ = -( count + 1 );
599 *out++ = in[LUT_ZZ[idx]];
606 // ==============================
607 // Discrete Cosine Transformation
608 // ==============================
610 void init_base( float quant ){
613 for ( y = 0; y < BLOCKSIZE; y++ )
614 for ( x = 0; x < BLOCKSIZE; x++ )
620 dctbase[y][x] = SQRT2 * cos( ( ( x * 2 + 1 ) * y * M_PI ) / ( BLOCKSIZE * 2 ) );
624 for ( y = 0; y < BLOCKSIZE * BLOCKSIZE; y++ )
625 Quantise[y] = LUT_Quantise[y] / quant;
628 void SplitComponents( byte *src, int width, int height ){
634 for ( i = 0; i < BLOCKSIZE; i++, src += ( width - BLOCKSIZE ) * 4 )
635 for ( j = 0; j < BLOCKSIZE; j++ )
637 *tr++ = ( (float)*src++ ) - 128.0F;
638 *tg++ = ( (float)*src++ ) - 128.0F;
639 *tb++ = ( (float)*src++ ) - 128.0F;
644 void transferH( float *src, float *dst ){
649 for ( y = 0; y < BLOCKSIZE; y++, src += BLOCKSIZE )
651 for ( dy = 0; dy < BLOCKSIZE; dy++ )
655 for ( dx = 0; dx < BLOCKSIZE; dx++, work++ )
656 sum += dctbase[dy][dx] * *work;
658 *dst++ = sum / BLOCKSIZE;
663 void transferV( float *src, float *dst ){
668 for ( x = 0; x < BLOCKSIZE; x++, src++, dst++ )
670 for ( fy = 0; fy < BLOCKSIZE; fy++ )
674 for ( dy = 0; dy < BLOCKSIZE; dy++, work += BLOCKSIZE )
675 sum += dctbase[fy][dy] * *work;
677 dst[fy * BLOCKSIZE] = sum / BLOCKSIZE;
682 char *Combine( byte *dst, float *p, float *q ){
684 byte rlesrc[BLOCKSIZE * BLOCKSIZE];
689 for ( j = 0; j < BLOCKSIZE; j++ )
690 for ( i = 0; i < BLOCKSIZE; i++ )
692 c = (int)( ( *p++ / *q++ ) + 128.5F );
705 dst = RLEZZ( rlesrc, dst );
709 char *CombineComponents( char *dst, int width, int height ){
710 dst = Combine( dst, red, Quantise );
711 dst = Combine( dst, green, Quantise );
712 dst = Combine( dst, blue, Quantise );
716 void DCT( cblock_t *out, cblock_t in, int width, int height ){
722 for ( y = 0; y < height; y += BLOCKSIZE )
723 for ( x = 0; x < width; x += BLOCKSIZE )
725 cursrc = in.data + ( ( y * width ) + x ) * 4;
726 SplitComponents( cursrc, width, height );
727 transferH( red, temp );
728 transferV( temp, red );
729 transferH( green, temp );
730 transferV( temp, green );
731 transferH( blue, temp );
732 transferV( temp, blue );
733 curdst = CombineComponents( curdst, width, height );
735 out->count = curdst - out->data;
738 // ==================
740 // ==================
742 void BuildChars1( int prev, int nodenum, unsigned bits, int bitcount ){
745 if ( nodenum < HUF_TOKENS ) {
746 if ( bitcount > 32 ) {
747 Error( "bitcount > 32" );
749 charbits1[prev][nodenum] = bits;
750 charbitscount1[prev][nodenum] = bitcount;
754 node = &hnodes1[prev][nodenum];
756 BuildChars1( prev, node->children[0], bits, bitcount + 1 );
758 BuildChars1( prev, node->children[1], bits, bitcount + 1 );
761 // ==================
763 // ==================
765 int SmallestNode1( hnode_t *hnodes, int numhnodes ){
771 for ( i = 0; i < numhnodes; i++ )
773 if ( hnodes[i].used ) {
776 if ( !hnodes[i].count ) {
779 if ( hnodes[i].count < best ) {
780 best = hnodes[i].count;
785 if ( bestnode == -1 ) {
789 hnodes[bestnode].used = true;
793 // ==================
795 // ==================
797 void BuildTree1( int prev ){
798 hnode_t *node, *nodebase;
802 numhnodes = HUF_TOKENS;
803 nodebase = hnodes1[prev];
806 node = &nodebase[numhnodes];
808 // pick two lowest counts
809 node->children[0] = SmallestNode1( nodebase, numhnodes );
810 if ( node->children[0] == -1 ) {
814 node->children[1] = SmallestNode1( nodebase, numhnodes );
815 if ( node->children[1] == -1 ) {
819 node->count = nodebase[node->children[0]].count +
820 nodebase[node->children[1]].count;
823 numhnodes1[prev] = numhnodes - 1;
824 BuildChars1( prev, numhnodes - 1, 0, 0 );
827 // ==================
829 // ==================
831 void Huffman1_Count( cblock_t in ){
838 for ( i = 0; i < in.count; i++ )
842 hnodes1[prev][v].count++;
845 for ( rept = 1; ( i + rept < in.count ) && ( rept < MAX_REPT ); rept++ )
846 if ( in.data[i + rept] != v ) {
849 if ( rept > MIN_REPT ) {
850 hnodes1[prev][255 + rept].count++;
856 // ==================
858 // ==================
860 void Huffman1_Build(){
865 for ( i = 0; i < 256; i++ )
867 // normalize and save the counts
869 for ( j = 0; j < HUF_TOKENS; j++ )
871 if ( hnodes1[i][j].count > max ) {
872 max = hnodes1[i][j].count;
879 // easy to overflow 32 bits here!
880 for ( j = 0; j < HUF_TOKENS; j++ )
882 v = ( hnodes1[i][j].count * (double) 255 + max - 1 ) / max;
886 scaled[i][j] = hnodes1[i][j].count = v;
891 if ( total == 1 ) { // must have two tokens
892 if ( !scaled[i][0] ) {
893 scaled[i][0] = hnodes1[i][0].count = 1;
896 scaled[i][1] = hnodes1[i][1].count = 1;
903 // ==================
905 // Order 1 compression with pre-built table
906 // ==================
908 cblock_t Huffman1( cblock_t in ){
918 out_p = out.data = SafeMalloc( ( in.count * 2 ) + 1024 + 4, "Huffman" );
919 memset( out_p, 0, ( in.count * 2 ) + 1024 + 4 );
921 // leave space for compressed count
924 *(long *)out_p = in.count;
930 for ( i = 0; i < in.count; i++ )
934 c = charbitscount1[prev][v];
935 bits = charbits1[prev][v];
942 if ( bits & ( 1 << c ) ) {
943 out_p[outbits >> 3] |= 1 << ( outbits & 7 );
949 // check for repeat encodes
950 for ( rept = 1; ( i + rept < in.count ) && ( rept < MAX_REPT ); rept++ )
951 if ( in.data[i + rept] != v ) {
954 if ( rept > MIN_REPT ) {
955 c = charbitscount1[prev][255 + rept];
956 bits = charbits1[prev][255 + rept];
963 if ( bits & ( 1 << c ) ) {
964 out_p[outbits >> 3] |= 1 << ( outbits & 7 );
971 out_p += ( outbits + 7 ) >> 3;
972 out.count = out_p - out.data;
975 *(long *)out_p = out.count;
978 // ===================
980 // ===================
982 void LoadFrame( cblock_t *out, char *base, int frame ){
990 sprintf( name, "%svideo/%s/%s%04i.tga", gamedir, base, base, frame );
992 f = fopen( name, "rb" );
999 LoadTGA( name, &in.data, &width, &height );
1000 if ( ( width != cinehead.Width ) || ( height != cinehead.Height ) ) {
1002 printf( "Invalid picture size\n" );
1006 out->data = SafeMalloc( width * height * 3, "LoadFrame" ); // rle could possibly expand file so this not 100% safe (however DCT should force a lot of compression)
1007 DCT( out, in, width, height );
1011 // ==================================
1014 // video <directory> <framedigits>
1015 // ==================================
1023 cblock_t in, huffman;
1027 int min_rle_size, warnings;
1028 int ave_image, ave_sound;
1030 GetScriptToken( false );
1031 strcpy( base, token );
1036 GetScriptToken( false );
1037 dctconst = atof( token );
1038 GetScriptToken( false );
1039 maxsize = atoi( token );
1041 sprintf( savename, "%svideo/%s.cin", gamedir, base );
1044 memset( charbits1, 0, sizeof( charbits1 ) );
1045 memset( charbitscount1, 0, sizeof( charbitscount1 ) );
1046 memset( hnodes1, 0, sizeof( hnodes1 ) );
1047 memset( numhnodes1, 0, sizeof( numhnodes1 ) );
1048 memset( order0counts, 0, sizeof( order0counts ) );
1050 // load the entire sound wav file if present
1053 cinehead.SndRate = wavinfo.rate;
1054 cinehead.SndWidth = wavinfo.width;
1055 cinehead.SndChannels = wavinfo.channels;
1057 sprintf( name, "%svideo/%s/%s0000.tga", gamedir, base, base );
1058 printf( "Loading sequence : %s\n", name );
1059 printf( "DCT constant : %f\n", dctconst );
1061 LoadTGA( name, NULL, &width, &height );
1063 output = fopen( savename, "wb" );
1065 Error( "Can't open %s", savename );
1068 if ( ( width % BLOCKSIZE ) || ( height % BLOCKSIZE ) ) {
1069 Error( "Width and height must be a multiple of %d", BLOCKSIZE );
1072 cinehead.Width = width;
1073 cinehead.Height = height;
1074 init_base( dctconst );
1076 // build the dictionary
1077 printf( "Counting : " );
1079 for ( frame = 0; ; frame++ )
1082 LoadFrame( &in, base, frame );
1086 Huffman1_Count( in );
1087 if ( in.count > min_rle_size ) {
1088 min_rle_size = in.count;
1093 cinehead.NumFrames = frame;
1094 printf( "Num Frames : %d\n", frame );
1095 cinehead.MaxRleSize = ( min_rle_size + 0x1f ) & 0xfffffe0;
1096 cinehead.MaxSndSize = ( ( 4 * wavinfo.rate * wavinfo.channels / 14 ) + 0x1f ) & 0xffffffe0;
1098 WriteHeader( output, FC_HEADER_NAME, FC_HEADER_VERSION, sizeof( CineHead_t ), &cinehead );
1100 // build nodes and write counts
1102 WriteHeader( output, FC_HUFFBITS_NAME, FC_HUFFBITS_VERSION, sizeof( scaled ), scaled );
1103 WriteHeader( output, FC_QUANT_NAME, FC_QUANT_VERSION, sizeof( Quantise ), Quantise );
1108 // compress it with the dictionary
1110 ssize = WriteSound( output, frame, 4 );
1114 for ( frame = 0; frame < cinehead.NumFrames; frame++ )
1116 // save some sound samples
1117 printf( "Packing : ", frame );
1118 LoadFrame( &in, base, frame );
1121 huffman = Huffman1( in );
1122 printf( "%d bytes rle, %d bytes huffman", in.count, huffman.count );
1123 size = ( huffman.count + 3 ) & 0xfffffffc; // round up to longwords
1124 if ( size > maxsize ) {
1125 printf( " ** WARNING **" );
1129 ave_image += huffman.count;
1131 WriteHeader( output, FC_IMAGE_NAME, FC_IMAGE_VERSION, size, huffman.data );
1133 ssize = WriteSound( output, frame + 4, 1 );
1138 free( huffman.data );
1140 printf( "\nTotal size: %d (headers + %d image + %d sound)\n", ftell( output ), ave_image, ave_sound );
1141 printf( "Data rate : %d bytes per sec (image and sound)\n", ( ave_image + ave_sound ) / cinehead.NumFrames );
1142 printf( "Cin created ok with %d warnings.\n", warnings );