-#include "qdata.h"\r
-#include "inout.h"\r
-\r
-byte *soundtrack;\r
-char base[32];\r
-\r
-/*\r
-===============================================================================\r
-\r
-WAV loading\r
-\r
-===============================================================================\r
-*/\r
-\r
-typedef struct\r
-{\r
- int rate;\r
- int width;\r
- int channels;\r
- int loopstart;\r
- int samples;\r
- int dataofs; // chunk starts this many bytes from file start\r
-} wavinfo_t;\r
-\r
-\r
-byte *data_p;\r
-byte *iff_end;\r
-byte *last_chunk;\r
-byte *iff_data;\r
-int iff_chunk_len;\r
-\r
-\r
-int samplecounts[0x10000];\r
-\r
-wavinfo_t wavinfo;\r
-\r
-short GetLittleShort(void)\r
-{\r
- short val = 0;\r
- val = *data_p;\r
- val = val + (*(data_p+1)<<8);\r
- data_p += 2;\r
- return val;\r
-}\r
-\r
-int GetLittleLong(void)\r
-{\r
- int val = 0;\r
- val = *data_p;\r
- val = val + (*(data_p+1)<<8);\r
- val = val + (*(data_p+2)<<16);\r
- val = val + (*(data_p+3)<<24);\r
- data_p += 4;\r
- return val;\r
-}\r
-\r
-void FindNextChunk(char *name)\r
-{\r
- while (1)\r
- {\r
- data_p=last_chunk;\r
-\r
- if (data_p >= iff_end)\r
- { // didn't find the chunk\r
- data_p = NULL;\r
- return;\r
- }\r
- \r
- data_p += 4;\r
- iff_chunk_len = GetLittleLong();\r
- if (iff_chunk_len < 0)\r
- {\r
- data_p = NULL;\r
- return;\r
- }\r
-// if (iff_chunk_len > 1024*1024)\r
-// Sys_Error ("FindNextChunk: %i length is past the 1 meg sanity limit", iff_chunk_len);\r
- data_p -= 8;\r
- last_chunk = data_p + 8 + ( (iff_chunk_len + 1) & ~1 );\r
- if (!strncmp(data_p, name, 4))\r
- return;\r
- }\r
-}\r
-\r
-void FindChunk(char *name)\r
-{\r
- last_chunk = iff_data;\r
- FindNextChunk (name);\r
-}\r
-\r
-\r
-void DumpChunks(void)\r
-{\r
- char str[5];\r
- \r
- str[4] = 0;\r
- data_p=iff_data;\r
- do\r
- {\r
- memcpy (str, data_p, 4);\r
- data_p += 4;\r
- iff_chunk_len = GetLittleLong();\r
- printf ("0x%x : %s (%d)\n", (int)(data_p - 4), str, iff_chunk_len);\r
- data_p += (iff_chunk_len + 1) & ~1;\r
- } while (data_p < iff_end);\r
-}\r
-\r
-/*\r
-============\r
-GetWavinfo\r
-============\r
-*/\r
-wavinfo_t GetWavinfo (char *name, byte *wav, int wavlength)\r
-{\r
- wavinfo_t info;\r
- int i;\r
- int format;\r
- int samples;\r
-\r
- memset (&info, 0, sizeof(info));\r
-\r
- if (!wav)\r
- return info;\r
- \r
- iff_data = wav;\r
- iff_end = wav + wavlength;\r
-\r
-// find "RIFF" chunk\r
- FindChunk("RIFF");\r
- if (!(data_p && !strncmp(data_p+8, "WAVE", 4)))\r
- {\r
- printf("Missing RIFF/WAVE chunks\n");\r
- return info;\r
- }\r
-\r
-// get "fmt " chunk\r
- iff_data = data_p + 12;\r
-// DumpChunks ();\r
-\r
- FindChunk("fmt ");\r
- if (!data_p)\r
- {\r
- printf("Missing fmt chunk\n");\r
- return info;\r
- }\r
- data_p += 8;\r
- format = GetLittleShort();\r
- if (format != 1)\r
- {\r
- printf("Microsoft PCM format only\n");\r
- return info;\r
- }\r
-\r
- info.channels = GetLittleShort();\r
- info.rate = GetLittleLong();\r
- data_p += 4+2;\r
- info.width = GetLittleShort() / 8;\r
-\r
-// get cue chunk\r
- FindChunk("cue ");\r
- if (data_p)\r
- {\r
- data_p += 32;\r
- info.loopstart = GetLittleLong();\r
-// Com_Printf("loopstart=%d\n", sfx->loopstart);\r
-\r
- // if the next chunk is a LIST chunk, look for a cue length marker\r
- FindNextChunk ("LIST");\r
- if (data_p)\r
- {\r
- if (!strncmp (data_p + 28, "mark", 4))\r
- { // this is not a proper parse, but it works with cooledit...\r
- data_p += 24;\r
- i = GetLittleLong (); // samples in loop\r
- info.samples = info.loopstart + i;\r
- }\r
- }\r
- }\r
- else\r
- info.loopstart = -1;\r
-\r
-// find data chunk\r
- FindChunk("data");\r
- if (!data_p)\r
- {\r
- printf("Missing data chunk\n");\r
- return info;\r
- }\r
-\r
- data_p += 4;\r
- samples = GetLittleLong ();\r
-\r
- if (info.samples)\r
- {\r
- if (samples < info.samples)\r
- Error ("Sound %s has a bad loop length", name);\r
- }\r
- else\r
- info.samples = samples;\r
-\r
- info.dataofs = data_p - wav;\r
-\r
- return info;\r
-}\r
-\r
-//=====================================================================\r
-\r
-/*\r
-==============\r
-LoadSoundtrack\r
-==============\r
-*/\r
-void LoadSoundtrack (void)\r
-{\r
- char name[1024];\r
- FILE *f;\r
- int len;\r
- int i, val, j;\r
-\r
- soundtrack = NULL;\r
- sprintf (name, "%svideo/%s/%s.wav", gamedir, base, base);\r
- printf ("%s\n", name);\r
- f = fopen (name, "rb");\r
- if (!f)\r
- {\r
- printf ("no soundtrack for %s\n", base);\r
- return;\r
- }\r
- len = Q_filelength(f);\r
- soundtrack = malloc(len);\r
- fread (soundtrack, 1, len, f);\r
- fclose (f);\r
-\r
- wavinfo = GetWavinfo (name, soundtrack, len);\r
-\r
- // count samples for compression\r
- memset (samplecounts, 0, sizeof(samplecounts));\r
-\r
- j = wavinfo.samples/2;\r
- for (i=0 ; i<j ; i++)\r
- {\r
- val = ((unsigned short *)( soundtrack + wavinfo.dataofs))[i];\r
- samplecounts[val]++;\r
- }\r
- val = 0;\r
- for (i=0 ; i<0x10000 ; i++)\r
- if (samplecounts[i])\r
- val++;\r
-\r
- printf ("%i unique sample values\n", val);\r
-}\r
-\r
-/*\r
-==================\r
-WriteSound\r
-==================\r
-*/\r
-void WriteSound (FILE *output, int frame)\r
-{\r
- int start, end;\r
- int count;\r
- int empty = 0;\r
- int i;\r
- int sample;\r
- int width;\r
-\r
- width = wavinfo.width * wavinfo.channels;\r
-\r
- start = frame*wavinfo.rate/14;\r
- end = (frame+1)*wavinfo.rate/14;\r
- count = end - start;\r
-\r
- for (i=0 ; i<count ; i++)\r
- {\r
- sample = start+i;\r
- if (sample > wavinfo.samples || !soundtrack)\r
- fwrite (&empty, 1, width, output);\r
- else\r
- fwrite (soundtrack + wavinfo.dataofs + sample*width, 1, width,output);\r
- }\r
-}\r
-\r
-//==========================================================================\r
-\r
-/*\r
-==================\r
-MTF\r
-==================\r
-*/\r
-cblock_t MTF (cblock_t in)\r
-{\r
- int i, j, b, code;\r
- byte *out_p;\r
- int index[256];\r
- cblock_t out;\r
-\r
- out_p = out.data = malloc(in.count + 4);\r
-\r
- // write count\r
- *out_p++ = in.count&255;\r
- *out_p++ = (in.count>>8)&255;\r
- *out_p++ = (in.count>>16)&255;\r
- *out_p++ = (in.count>>24)&255;\r
-\r
- for (i=0 ; i<256 ; i++)\r
- index[i] = i;\r
-\r
- for (i=0 ; i<in.count ; i++)\r
- {\r
- b = in.data[i];\r
- code = index[b];\r
- *out_p++ = code;\r
- \r
- // shuffle b indexes to 0\r
- for (j=0 ; j<256 ; j++)\r
- if (index[j] < code)\r
- index[j]++;\r
- index[b] = 0;\r
- }\r
-\r
- out.count = out_p - out.data;\r
-\r
- return out;\r
-}\r
-\r
-\r
-//==========================================================================\r
-\r
-int bwt_size;\r
-byte *bwt_data;\r
-\r
-int bwtCompare (const void *elem1, const void *elem2)\r
-{\r
- int i;\r
- int i1, i2;\r
- int b1, b2;\r
-\r
- i1 = *(int *)elem1;\r
- i2 = *(int *)elem2;\r
-\r
- for (i=0 ; i<bwt_size ; i++)\r
- {\r
- b1 = bwt_data[i1];\r
- b2 = bwt_data[i2];\r
- if (b1 < b2)\r
- return -1;\r
- if (b1 > b2)\r
- return 1;\r
- if (++i1 == bwt_size)\r
- i1 = 0;\r
- if (++i2 == bwt_size)\r
- i2 = 0;\r
- }\r
-\r
- return 0;\r
-}\r
-\r
-/*\r
-==================\r
-BWT\r
-==================\r
-*/\r
-cblock_t BWT (cblock_t in)\r
-{\r
- int *sorted;\r
- int i;\r
- byte *out_p;\r
- cblock_t out;\r
-\r
- bwt_size = in.count;\r
- bwt_data = in.data;\r
-\r
- sorted = malloc(in.count*sizeof(*sorted));\r
- for (i=0 ; i<in.count ; i++)\r
- sorted[i] = i;\r
- qsort (sorted, in.count, sizeof(*sorted), bwtCompare);\r
-\r
- out_p = out.data = malloc(in.count + 8);\r
-\r
- // write count\r
- *out_p++ = in.count&255;\r
- *out_p++ = (in.count>>8)&255;\r
- *out_p++ = (in.count>>16)&255;\r
- *out_p++ = (in.count>>24)&255;\r
-\r
- // write head index\r
- for (i=0 ; i<in.count ; i++)\r
- if (sorted[i] == 0)\r
- break;\r
- *out_p++ = i&255;\r
- *out_p++ = (i>>8)&255;\r
- *out_p++ = (i>>16)&255;\r
- *out_p++ = (i>>24)&255;\r
-\r
- // write the L column\r
- for (i=0 ; i<in.count ; i++)\r
- *out_p++ = in.data[(sorted[i]+in.count-1)%in.count];\r
-\r
- free (sorted);\r
-\r
- out.count = out_p - out.data;\r
-\r
- return out;\r
-}\r
-\r
-//==========================================================================\r
-\r
-typedef struct hnode_s\r
-{\r
- int count;\r
- qboolean used;\r
- int children[2];\r
-} hnode_t;\r
-\r
-int numhnodes;\r
-hnode_t hnodes[512];\r
-unsigned charbits[256];\r
-int charbitscount[256];\r
-\r
-int SmallestNode (void)\r
-{\r
- int i;\r
- int best, bestnode;\r
-\r
- best = 99999999;\r
- bestnode = -1;\r
- for (i=0 ; i<numhnodes ; i++)\r
- {\r
- if (hnodes[i].used)\r
- continue;\r
- if (!hnodes[i].count)\r
- continue;\r
- if (hnodes[i].count < best)\r
- {\r
- best = hnodes[i].count;\r
- bestnode = i;\r
- }\r
- }\r
-\r
- if (bestnode == -1)\r
- return -1;\r
-\r
- hnodes[bestnode].used = true;\r
- return bestnode;\r
-}\r
-\r
-void BuildChars (int nodenum, unsigned bits, int bitcount)\r
-{\r
- hnode_t *node;\r
-\r
- if (nodenum < 256)\r
- {\r
- if (bitcount > 32)\r
- Error ("bitcount > 32");\r
- charbits[nodenum] = bits;\r
- charbitscount[nodenum] = bitcount;\r
- return;\r
- }\r
-\r
- node = &hnodes[nodenum];\r
- bits <<= 1;\r
- BuildChars (node->children[0], bits, bitcount+1);\r
- bits |= 1;\r
- BuildChars (node->children[1], bits, bitcount+1);\r
-}\r
-\r
-\r
-/*\r
-==================\r
-Huffman\r
-==================\r
-*/\r
-cblock_t Huffman (cblock_t in)\r
-{\r
- int i;\r
- hnode_t *node;\r
- int outbits, c;\r
- unsigned bits;\r
- byte *out_p;\r
- cblock_t out;\r
- int max, maxchar;\r
-\r
- // count\r
- memset (hnodes, 0, sizeof(hnodes));\r
- for (i=0 ; i<in.count ; i++)\r
- hnodes[in.data[i]].count++;\r
-\r
- // normalize counts\r
- max = 0;\r
- maxchar = 0;\r
- for (i=0 ; i<256 ; i++)\r
- {\r
- if (hnodes[i].count > max)\r
- {\r
- max = hnodes[i].count;\r
- maxchar = i;\r
- }\r
- }\r
- if (max == 0)\r
- Error ("Huffman: max == 0");\r
-\r
- for (i=0 ; i<256 ; i++)\r
- {\r
- hnodes[i].count = (hnodes[i].count*255+max-1) / max;\r
- }\r
-\r
- // build the nodes\r
- numhnodes = 256;\r
- while (numhnodes != 511)\r
- {\r
- node = &hnodes[numhnodes];\r
-\r
- // pick two lowest counts\r
- node->children[0] = SmallestNode ();\r
- if (node->children[0] == -1)\r
- break; // no more\r
-\r
- node->children[1] = SmallestNode ();\r
- if (node->children[1] == -1)\r
- {\r
- if (node->children[0] != numhnodes-1)\r
- Error ("Bad smallestnode");\r
- break;\r
- }\r
- node->count = hnodes[node->children[0]].count + \r
- hnodes[node->children[1]].count;\r
- numhnodes++;\r
- }\r
-\r
- BuildChars (numhnodes-1, 0, 0);\r
-\r
- out_p = out.data = malloc(in.count*2 + 1024);\r
- memset (out_p, 0, in.count*2+1024);\r
-\r
- // write count\r
- *out_p++ = in.count&255;\r
- *out_p++ = (in.count>>8)&255;\r
- *out_p++ = (in.count>>16)&255;\r
- *out_p++ = (in.count>>24)&255;\r
-\r
- // save out the 256 normalized counts so the tree can be recreated\r
- for (i=0 ; i<256 ; i++)\r
- *out_p++ = hnodes[i].count;\r
-\r
- // write bits\r
- outbits = 0;\r
- for (i=0 ; i<in.count ; i++)\r
- {\r
- c = charbitscount[in.data[i]];\r
- bits = charbits[in.data[i]];\r
- while (c)\r
- {\r
- c--;\r
- if (bits & (1<<c))\r
- out_p[outbits>>3] |= 1<<(outbits&7);\r
- outbits++;\r
- }\r
- }\r
-\r
- out_p += (outbits+7)>>3;\r
-\r
- out.count = out_p - out.data;\r
-\r
- return out;\r
-}\r
-\r
-//==========================================================================\r
-\r
-/*\r
-==================\r
-RLE\r
-==================\r
-*/\r
-#define RLE_CODE 0xe8\r
-#define RLE_TRIPPLE 0xe9\r
-\r
-int rle_counts[256];\r
-int rle_bytes[256];\r
-\r
-cblock_t RLE (cblock_t in)\r
-{\r
- int i;\r
- byte *out_p;\r
- int val;\r
- int repeat;\r
- cblock_t out;\r
-\r
- out_p = out.data = malloc (in.count*2);\r
-\r
- // write count\r
- *out_p++ = in.count&255;\r
- *out_p++ = (in.count>>8)&255;\r
- *out_p++ = (in.count>>16)&255;\r
- *out_p++ = (in.count>>24)&255;\r
-\r
- for (i=0 ; i<in.count ; )\r
- {\r
- val = in.data[i];\r
- rle_bytes[val]++;\r
- repeat = 1;\r
- i++;\r
- while (i<in.count && repeat < 255 && in.data[i] == val)\r
- {\r
- repeat++;\r
- i++;\r
- }\r
-if (repeat < 256)\r
-rle_counts[repeat]++;\r
- if (repeat > 3 || val == RLE_CODE)\r
- {\r
- *out_p++ = RLE_CODE;\r
- *out_p++ = val;\r
- *out_p++ = repeat;\r
- }\r
- else\r
- {\r
- while (repeat--)\r
- *out_p++ = val;\r
- }\r
- }\r
-\r
- out.count = out_p - out.data;\r
- return out;\r
-}\r
-\r
-//==========================================================================\r
-\r
-unsigned lzss_head[256];\r
-unsigned lzss_next[0x20000];\r
-\r
-/*\r
-==================\r
-LZSS\r
-==================\r
-*/\r
-#define BACK_WINDOW 0x10000\r
-#define BACK_BITS 16\r
-#define FRONT_WINDOW 16\r
-#define FRONT_BITS 4\r
-cblock_t LZSS (cblock_t in)\r
-{\r
- int i;\r
- byte *out_p;\r
- cblock_t out;\r
- int val;\r
- int j, start, max;\r
- int bestlength, beststart;\r
- int outbits;\r
-\r
-if (in.count >= sizeof(lzss_next)/4)\r
-Error ("LZSS: too big");\r
-\r
- memset (lzss_head, -1, sizeof(lzss_head));\r
-\r
- out_p = out.data = malloc (in.count*2);\r
- memset (out.data, 0, in.count*2);\r
-\r
- // write count\r
- *out_p++ = in.count&255;\r
- *out_p++ = (in.count>>8)&255;\r
- *out_p++ = (in.count>>16)&255;\r
- *out_p++ = (in.count>>24)&255;\r
-\r
- outbits = 0;\r
- for (i=0 ; i<in.count ; )\r
- {\r
- val = in.data[i];\r
-#if 1\r
-// chained search\r
- bestlength = 0;\r
- beststart = 0;\r
-\r
- max = FRONT_WINDOW;\r
- if (i + max > in.count)\r
- max = in.count - i;\r
-\r
- start = lzss_head[val];\r
- while (start != -1 && start >= i-BACK_WINDOW)\r
- { \r
- // count match length\r
- for (j=0 ; j<max ; j++)\r
- if (in.data[start+j] != in.data[i+j])\r
- break;\r
- if (j > bestlength)\r
- {\r
- bestlength = j;\r
- beststart = start;\r
- }\r
- start = lzss_next[start];\r
- }\r
-\r
-#else\r
-// slow simple search\r
- // search for a match\r
- max = FRONT_WINDOW;\r
- if (i + max > in.count)\r
- max = in.count - i;\r
-\r
- start = i - BACK_WINDOW;\r
- if (start < 0)\r
- start = 0;\r
- bestlength = 0;\r
- beststart = 0;\r
- for ( ; start < i ; start++)\r
- {\r
- if (in.data[start] != val)\r
- continue;\r
- // count match length\r
- for (j=0 ; j<max ; j++)\r
- if (in.data[start+j] != in.data[i+j])\r
- break;\r
- if (j > bestlength)\r
- {\r
- bestlength = j;\r
- beststart = start;\r
- }\r
- }\r
-#endif\r
- beststart = BACK_WINDOW - (i-beststart);\r
-\r
- if (bestlength < 3)\r
- { // output a single char\r
- bestlength = 1;\r
-\r
- out_p[outbits>>3] |= 1<<(outbits&7); // set bit to mark char\r
- outbits++;\r
- for (j=0 ; j<8 ; j++, outbits++)\r
- if (val & (1<<j) )\r
- out_p[outbits>>3] |= 1<<(outbits&7);\r
- }\r
- else\r
- { // output a phrase\r
- outbits++; // leave a 0 bit to mark phrase\r
- for (j=0 ; j<BACK_BITS ; j++, outbits++)\r
- if (beststart & (1<<j) )\r
- out_p[outbits>>3] |= 1<<(outbits&7);\r
- for (j=0 ; j<FRONT_BITS ; j++, outbits++)\r
- if (bestlength & (1<<j) )\r
- out_p[outbits>>3] |= 1<<(outbits&7);\r
- }\r
-\r
- while (bestlength--)\r
- {\r
- val = in.data[i];\r
- lzss_next[i] = lzss_head[val];\r
- lzss_head[val] = i;\r
- i++;\r
- }\r
- }\r
-\r
- out_p += (outbits+7)>>3;\r
- out.count = out_p - out.data;\r
- return out;\r
-}\r
-\r
-//==========================================================================\r
-\r
-#define MIN_REPT 15\r
-#define MAX_REPT 0\r
-#define HUF_TOKENS (256+MAX_REPT)\r
-\r
-unsigned charbits1[256][HUF_TOKENS];\r
-int charbitscount1[256][HUF_TOKENS];\r
-\r
-hnode_t hnodes1[256][HUF_TOKENS*2];\r
-int numhnodes1[256];\r
-\r
-int order0counts[256];\r
-\r
-/*\r
-==================\r
-SmallestNode1\r
-==================\r
-*/\r
-int SmallestNode1 (hnode_t *hnodes, int numhnodes)\r
-{\r
- int i;\r
- int best, bestnode;\r
-\r
- best = 99999999;\r
- bestnode = -1;\r
- for (i=0 ; i<numhnodes ; i++)\r
- {\r
- if (hnodes[i].used)\r
- continue;\r
- if (!hnodes[i].count)\r
- continue;\r
- if (hnodes[i].count < best)\r
- {\r
- best = hnodes[i].count;\r
- bestnode = i;\r
- }\r
- }\r
-\r
- if (bestnode == -1)\r
- return -1;\r
-\r
- hnodes[bestnode].used = true;\r
- return bestnode;\r
-}\r
-\r
-\r
-/*\r
-==================\r
-BuildChars1\r
-==================\r
-*/\r
-void BuildChars1 (int prev, int nodenum, unsigned bits, int bitcount)\r
-{\r
- hnode_t *node;\r
-\r
- if (nodenum < HUF_TOKENS)\r
- {\r
- if (bitcount > 32)\r
- Error ("bitcount > 32");\r
- charbits1[prev][nodenum] = bits;\r
- charbitscount1[prev][nodenum] = bitcount;\r
- return;\r
- }\r
-\r
- node = &hnodes1[prev][nodenum];\r
- bits <<= 1;\r
- BuildChars1 (prev, node->children[0], bits, bitcount+1);\r
- bits |= 1;\r
- BuildChars1 (prev, node->children[1], bits, bitcount+1);\r
-}\r
-\r
-\r
-/*\r
-==================\r
-BuildTree1\r
-==================\r
-*/\r
-void BuildTree1 (int prev)\r
-{\r
- hnode_t *node, *nodebase;\r
- int numhnodes;\r
-\r
- // build the nodes\r
- numhnodes = HUF_TOKENS;\r
- nodebase = hnodes1[prev];\r
- while (1)\r
- {\r
- node = &nodebase[numhnodes];\r
-\r
- // pick two lowest counts\r
- node->children[0] = SmallestNode1 (nodebase, numhnodes);\r
- if (node->children[0] == -1)\r
- break; // no more\r
-\r
- node->children[1] = SmallestNode1 (nodebase, numhnodes);\r
- if (node->children[1] == -1)\r
- break;\r
-\r
- node->count = nodebase[node->children[0]].count + \r
- nodebase[node->children[1]].count;\r
- numhnodes++;\r
- }\r
- numhnodes1[prev] = numhnodes-1;\r
- BuildChars1 (prev, numhnodes-1, 0, 0);\r
-}\r
-\r
-\r
-/*\r
-==================\r
-Huffman1_Count\r
-==================\r
-*/\r
-void Huffman1_Count (cblock_t in)\r
-{\r
- int i;\r
- int prev;\r
- int v;\r
- int rept;\r
-\r
- prev = 0;\r
- for (i=0 ; i<in.count ; i++)\r
- {\r
- v = in.data[i];\r
- order0counts[v]++;\r
- hnodes1[prev][v].count++;\r
- prev = v;\r
-#if 1\r
- for (rept=1 ; i+rept < in.count && rept < MAX_REPT ; rept++)\r
- if (in.data[i+rept] != v)\r
- break;\r
- if (rept > MIN_REPT)\r
- {\r
- hnodes1[prev][255+rept].count++;\r
- i += rept-1;\r
- }\r
-#endif\r
- }\r
-}\r
-\r
-\r
-/*\r
-==================\r
-Huffman1_Build\r
-==================\r
-*/\r
-byte scaled[256][HUF_TOKENS];\r
-void Huffman1_Build (FILE *f)\r
-{\r
- int i, j, v;\r
- int max;\r
- int total;\r
-\r
- for (i=0 ; i<256 ; i++)\r
- {\r
- // normalize and save the counts\r
- max = 0;\r
- for (j=0 ; j<HUF_TOKENS ; j++)\r
- {\r
- if (hnodes1[i][j].count > max)\r
- max = hnodes1[i][j].count;\r
- }\r
- if (max == 0)\r
- max = 1;\r
- total = 0;\r
- for (j=0 ; j<HUF_TOKENS ; j++)\r
- { // easy to overflow 32 bits here!\r
- v = (hnodes1[i][j].count*(double)255+max-1)/max;\r
- if (v > 255)\r
- Error ("v > 255");\r
- scaled[i][j] = hnodes1[i][j].count = v;\r
- if (v)\r
- total++;\r
- }\r
- if (total == 1)\r
- { // must have two tokens\r
- if (!scaled[i][0])\r
- scaled[i][0] = hnodes1[i][0].count = 1;\r
- else\r
- scaled[i][1] = hnodes1[i][1].count = 1;\r
- }\r
-\r
- BuildTree1 (i);\r
- }\r
-\r
-#if 0\r
- // count up the total bits\r
- total = 0;\r
- for (i=0 ; i<256 ; i++)\r
- for (j=0 ; j<256 ; j++)\r
- total += charbitscount1[i][j] * hnodes1[i][j].count;\r
-\r
- total = (total+7)/8;\r
- printf ("%i bytes huffman1 compressed\n", total);\r
-#endif\r
-\r
- fwrite (scaled, 1, sizeof(scaled), f);\r
-}\r
-\r
-/*\r
-==================\r
-Huffman1\r
-\r
-Order 1 compression with pre-built table\r
-==================\r
-*/\r
-cblock_t Huffman1 (cblock_t in)\r
-{\r
- int i;\r
- int outbits, c;\r
- unsigned bits;\r
- byte *out_p;\r
- cblock_t out;\r
- int prev;\r
- int v;\r
- int rept;\r
-\r
- out_p = out.data = malloc(in.count*2 + 1024);\r
- memset (out_p, 0, in.count*2+1024);\r
-\r
- // write count\r
- *out_p++ = in.count&255;\r
- *out_p++ = (in.count>>8)&255;\r
- *out_p++ = (in.count>>16)&255;\r
- *out_p++ = (in.count>>24)&255;\r
-\r
- // write bits\r
- outbits = 0;\r
- prev = 0;\r
- for (i=0 ; i<in.count ; i++)\r
- {\r
- v = in.data[i];\r
-\r
- c = charbitscount1[prev][v];\r
- bits = charbits1[prev][v];\r
- if (!c)\r
- Error ("!bits");\r
- while (c)\r
- {\r
- c--;\r
- if (bits & (1<<c))\r
- out_p[outbits>>3] |= 1<<(outbits&7);\r
- outbits++;\r
- }\r
-\r
- prev = v;\r
-#if 1\r
- // check for repeat encodes\r
- for (rept=1 ; i+rept < in.count && rept < MAX_REPT ; rept++)\r
- if (in.data[i+rept] != v)\r
- break;\r
- if (rept > MIN_REPT)\r
- {\r
- c = charbitscount1[prev][255+rept];\r
- bits = charbits1[prev][255+rept];\r
- if (!c)\r
- Error ("!bits");\r
- while (c)\r
- {\r
- c--;\r
- if (bits & (1<<c))\r
- out_p[outbits>>3] |= 1<<(outbits&7);\r
- outbits++;\r
- }\r
- i += rept-1;\r
- }\r
-#endif\r
- }\r
-\r
- out_p += (outbits+7)>>3;\r
-\r
- out.count = out_p - out.data;\r
-\r
- return out;\r
-}\r
-\r
-//==========================================================================\r
-\r
-\r
-/*\r
-===================\r
-LoadFrame\r
-===================\r
-*/\r
-cblock_t LoadFrame (char *base, int frame, int digits, byte **palette)\r
-{\r
- int ten3, ten2, ten1, ten0;\r
- cblock_t in;\r
- int width, height;\r
- char name[1024];\r
- FILE *f;\r
-\r
- in.data = NULL;\r
- in.count = -1;\r
-\r
- ten3 = frame/1000;\r
- ten2 = (frame-ten3*1000)/100;\r
- ten1 = (frame-ten3*1000-ten2*100)/10;\r
- ten0 = frame%10;\r
-\r
- if (digits == 4)\r
- sprintf (name, "%svideo/%s/%s%i%i%i%i.pcx", gamedir, base, base, ten3, ten2, ten1, ten0);\r
- else\r
- sprintf (name, "%svideo/%s/%s%i%i%i.pcx", gamedir, base, base, ten2, ten1, ten0);\r
-\r
- f = fopen(name, "rb");\r
- if (!f)\r
- {\r
- in.data = NULL;\r
- return in;\r
- }\r
- fclose (f);\r
-\r
- printf ("%s\n", name);\r
- Load256Image (name, &in.data, palette, &width, &height);\r
- in.count = width*height;\r
-// FIXME: map 0 and 255!\r
-\r
-#if 0\r
- // rle compress\r
- rle = RLE(in);\r
- free (in.data);\r
-\r
- return rle;\r
-#endif\r
-\r
- return in;\r
-}\r
-\r
-/*\r
-===============\r
-Cmd_Video\r
-\r
-video <directory> <framedigits>\r
-===============\r
-*/\r
-void Cmd_Video (void)\r
-{\r
- char savename[1024];\r
- char name[1024];\r
- FILE *output;\r
- int startframe, frame;\r
- byte *palette;\r
- int width, height;\r
- byte current_palette[768];\r
- int command;\r
- int i;\r
- int digits;\r
- cblock_t in, huffman;\r
- int swap;\r
-\r
-\r
- GetToken (false);\r
- strcpy (base, token);\r
- if (g_release)\r
- {\r
-// sprintf (savename, "video/%s.cin", token);\r
-// ReleaseFile (savename);\r
- return;\r
- }\r
-\r
- GetToken (false);\r
- digits = atoi(token);\r
-\r
- // optionally skip frames\r
- if (TokenAvailable ())\r
- {\r
- GetToken (false);\r
- startframe = atoi(token);\r
- }\r
- else\r
- startframe=0;\r
-\r
- sprintf (savename, "%svideo/%s.cin", gamedir, base);\r
-\r
-\r
- // clear stuff\r
- memset (charbits1, 0, sizeof(charbits1));\r
- memset (charbitscount1, 0, sizeof(charbitscount1));\r
- memset (hnodes1, 0, sizeof(hnodes1));\r
- memset (numhnodes1, 0, sizeof(numhnodes1));\r
- memset (order0counts, 0, sizeof(order0counts));\r
-\r
-\r
- // load the entire sound wav file if present\r
- LoadSoundtrack ();\r
-\r
- if (digits == 4)\r
- sprintf (name, "%svideo/%s/%s0000.pcx", gamedir, base, base);\r
- else\r
- sprintf (name, "%svideo/%s/%s000.pcx", gamedir, base, base);\r
-\r
- printf ("%s\n", name);\r
- Load256Image (name, NULL, &palette, &width, &height);\r
-\r
- output = fopen (savename, "wb");\r
- if (!output)\r
- Error ("Can't open %s", savename);\r
-\r
- // write header info\r
- i = LittleLong (width);\r
- fwrite (&i, 4, 1, output);\r
- i = LittleLong (height);\r
- fwrite (&i, 4, 1, output);\r
- i = LittleLong (wavinfo.rate);\r
- fwrite (&i, 4, 1, output);\r
- i = LittleLong (wavinfo.width);\r
- fwrite (&i, 4, 1, output);\r
- i = LittleLong (wavinfo.channels);\r
- fwrite (&i, 4, 1, output);\r
-\r
- // build the dictionary\r
- for ( frame=startframe ; ; frame++)\r
- {\r
- printf ("counting ", frame);\r
- in = LoadFrame (base, frame, digits, &palette);\r
- if (!in.data)\r
- break;\r
- Huffman1_Count (in);\r
- free (in.data);\r
- }\r
- printf ("\n");\r
-\r
- // build nodes and write counts\r
- Huffman1_Build (output);\r
-\r
-\r
- memset (current_palette, 0, sizeof(current_palette));\r
-\r
- // compress it with the dictionary\r
- for (frame=startframe ; ; frame++)\r
- {\r
- printf ("packing ", frame);\r
- in = LoadFrame (base, frame, digits, &palette);\r
- if (!in.data)\r
- break;\r
-\r
- // see if the palette has changed\r
- for (i=0 ; i<768 ; i++)\r
- if (palette[i] != current_palette[i])\r
- {\r
- // write a palette change\r
- memcpy (current_palette, palette, sizeof(current_palette));\r
- command = LittleLong(1);\r
- fwrite (&command, 1, 4, output);\r
- fwrite (current_palette, 1, sizeof(current_palette), output);\r
- break;\r
- }\r
- if (i == 768)\r
- {\r
- command = 0; // no palette change\r
- fwrite (&command, 1, 4, output);\r
- }\r
-\r
- // save the image\r
- huffman = Huffman1 (in);\r
- printf ("%5i bytes after huffman1\n", huffman.count);\r
-\r
- swap = LittleLong (huffman.count);\r
- fwrite (&swap, 1, sizeof(swap), output);\r
-\r
- fwrite (huffman.data, 1, huffman.count, output);\r
-\r
- // save some sound samples\r
- WriteSound (output, frame);\r
-\r
- free (palette);\r
- free (in.data);\r
- free (huffman.data);\r
- }\r
- printf ("\n");\r
-\r
- // write end-of-file command\r
- command = 2;\r
- fwrite (&command, 1, 4, output);\r
-\r
- printf ("Total size: %i\n", ftell (output));\r
-\r
- fclose (output);\r
-\r
- if (soundtrack)\r
- free (soundtrack);\r
-}\r
+#include "qdata.h"
+#include "inout.h"
+
+byte *soundtrack;
+char base[32];
+
+/*
+===============================================================================
+
+WAV loading
+
+===============================================================================
+*/
+
+typedef struct
+{
+ int rate;
+ int width;
+ int channels;
+ int loopstart;
+ int samples;
+ int dataofs; // chunk starts this many bytes from file start
+} wavinfo_t;
+
+
+byte *data_p;
+byte *iff_end;
+byte *last_chunk;
+byte *iff_data;
+int iff_chunk_len;
+
+
+int samplecounts[0x10000];
+
+wavinfo_t wavinfo;
+
+short GetLittleShort(void)
+{
+ short val = 0;
+ val = *data_p;
+ val = val + (*(data_p+1)<<8);
+ data_p += 2;
+ return val;
+}
+
+int GetLittleLong(void)
+{
+ int val = 0;
+ val = *data_p;
+ val = val + (*(data_p+1)<<8);
+ val = val + (*(data_p+2)<<16);
+ val = val + (*(data_p+3)<<24);
+ data_p += 4;
+ return val;
+}
+
+void FindNextChunk(char *name)
+{
+ while (1)
+ {
+ data_p=last_chunk;
+
+ if (data_p >= iff_end)
+ { // didn't find the chunk
+ data_p = NULL;
+ return;
+ }
+
+ data_p += 4;
+ iff_chunk_len = GetLittleLong();
+ if (iff_chunk_len < 0)
+ {
+ data_p = NULL;
+ return;
+ }
+// if (iff_chunk_len > 1024*1024)
+// Sys_Error ("FindNextChunk: %i length is past the 1 meg sanity limit", iff_chunk_len);
+ data_p -= 8;
+ last_chunk = data_p + 8 + ( (iff_chunk_len + 1) & ~1 );
+ if (!strncmp(data_p, name, 4))
+ return;
+ }
+}
+
+void FindChunk(char *name)
+{
+ last_chunk = iff_data;
+ FindNextChunk (name);
+}
+
+
+void DumpChunks(void)
+{
+ char str[5];
+
+ str[4] = 0;
+ data_p=iff_data;
+ do
+ {
+ memcpy (str, data_p, 4);
+ data_p += 4;
+ iff_chunk_len = GetLittleLong();
+ printf ("0x%x : %s (%d)\n", (int)(data_p - 4), str, iff_chunk_len);
+ data_p += (iff_chunk_len + 1) & ~1;
+ } while (data_p < iff_end);
+}
+
+/*
+============
+GetWavinfo
+============
+*/
+wavinfo_t GetWavinfo (char *name, byte *wav, int wavlength)
+{
+ wavinfo_t info;
+ int i;
+ int format;
+ int samples;
+
+ memset (&info, 0, sizeof(info));
+
+ if (!wav)
+ return info;
+
+ iff_data = wav;
+ iff_end = wav + wavlength;
+
+// find "RIFF" chunk
+ FindChunk("RIFF");
+ if (!(data_p && !strncmp(data_p+8, "WAVE", 4)))
+ {
+ printf("Missing RIFF/WAVE chunks\n");
+ return info;
+ }
+
+// get "fmt " chunk
+ iff_data = data_p + 12;
+// DumpChunks ();
+
+ FindChunk("fmt ");
+ if (!data_p)
+ {
+ printf("Missing fmt chunk\n");
+ return info;
+ }
+ data_p += 8;
+ format = GetLittleShort();
+ if (format != 1)
+ {
+ printf("Microsoft PCM format only\n");
+ return info;
+ }
+
+ info.channels = GetLittleShort();
+ info.rate = GetLittleLong();
+ data_p += 4+2;
+ info.width = GetLittleShort() / 8;
+
+// get cue chunk
+ FindChunk("cue ");
+ if (data_p)
+ {
+ data_p += 32;
+ info.loopstart = GetLittleLong();
+// Com_Printf("loopstart=%d\n", sfx->loopstart);
+
+ // if the next chunk is a LIST chunk, look for a cue length marker
+ FindNextChunk ("LIST");
+ if (data_p)
+ {
+ if (!strncmp (data_p + 28, "mark", 4))
+ { // this is not a proper parse, but it works with cooledit...
+ data_p += 24;
+ i = GetLittleLong (); // samples in loop
+ info.samples = info.loopstart + i;
+ }
+ }
+ }
+ else
+ info.loopstart = -1;
+
+// find data chunk
+ FindChunk("data");
+ if (!data_p)
+ {
+ printf("Missing data chunk\n");
+ return info;
+ }
+
+ data_p += 4;
+ samples = GetLittleLong ();
+
+ if (info.samples)
+ {
+ if (samples < info.samples)
+ Error ("Sound %s has a bad loop length", name);
+ }
+ else
+ info.samples = samples;
+
+ info.dataofs = data_p - wav;
+
+ return info;
+}
+
+//=====================================================================
+
+/*
+==============
+LoadSoundtrack
+==============
+*/
+void LoadSoundtrack (void)
+{
+ char name[1024];
+ FILE *f;
+ int len;
+ int i, val, j;
+
+ soundtrack = NULL;
+ sprintf (name, "%svideo/%s/%s.wav", gamedir, base, base);
+ printf ("%s\n", name);
+ f = fopen (name, "rb");
+ if (!f)
+ {
+ printf ("no soundtrack for %s\n", base);
+ return;
+ }
+ len = Q_filelength(f);
+ soundtrack = malloc(len);
+ fread (soundtrack, 1, len, f);
+ fclose (f);
+
+ wavinfo = GetWavinfo (name, soundtrack, len);
+
+ // count samples for compression
+ memset (samplecounts, 0, sizeof(samplecounts));
+
+ j = wavinfo.samples/2;
+ for (i=0 ; i<j ; i++)
+ {
+ val = ((unsigned short *)( soundtrack + wavinfo.dataofs))[i];
+ samplecounts[val]++;
+ }
+ val = 0;
+ for (i=0 ; i<0x10000 ; i++)
+ if (samplecounts[i])
+ val++;
+
+ printf ("%i unique sample values\n", val);
+}
+
+/*
+==================
+WriteSound
+==================
+*/
+void WriteSound (FILE *output, int frame)
+{
+ int start, end;
+ int count;
+ int empty = 0;
+ int i;
+ int sample;
+ int width;
+
+ width = wavinfo.width * wavinfo.channels;
+
+ start = frame*wavinfo.rate/14;
+ end = (frame+1)*wavinfo.rate/14;
+ count = end - start;
+
+ for (i=0 ; i<count ; i++)
+ {
+ sample = start+i;
+ if (sample > wavinfo.samples || !soundtrack)
+ fwrite (&empty, 1, width, output);
+ else
+ fwrite (soundtrack + wavinfo.dataofs + sample*width, 1, width,output);
+ }
+}
+
+//==========================================================================
+
+/*
+==================
+MTF
+==================
+*/
+cblock_t MTF (cblock_t in)
+{
+ int i, j, b, code;
+ byte *out_p;
+ int index[256];
+ cblock_t out;
+
+ out_p = out.data = malloc(in.count + 4);
+
+ // write count
+ *out_p++ = in.count&255;
+ *out_p++ = (in.count>>8)&255;
+ *out_p++ = (in.count>>16)&255;
+ *out_p++ = (in.count>>24)&255;
+
+ for (i=0 ; i<256 ; i++)
+ index[i] = i;
+
+ for (i=0 ; i<in.count ; i++)
+ {
+ b = in.data[i];
+ code = index[b];
+ *out_p++ = code;
+
+ // shuffle b indexes to 0
+ for (j=0 ; j<256 ; j++)
+ if (index[j] < code)
+ index[j]++;
+ index[b] = 0;
+ }
+
+ out.count = out_p - out.data;
+
+ return out;
+}
+
+
+//==========================================================================
+
+int bwt_size;
+byte *bwt_data;
+
+int bwtCompare (const void *elem1, const void *elem2)
+{
+ int i;
+ int i1, i2;
+ int b1, b2;
+
+ i1 = *(int *)elem1;
+ i2 = *(int *)elem2;
+
+ for (i=0 ; i<bwt_size ; i++)
+ {
+ b1 = bwt_data[i1];
+ b2 = bwt_data[i2];
+ if (b1 < b2)
+ return -1;
+ if (b1 > b2)
+ return 1;
+ if (++i1 == bwt_size)
+ i1 = 0;
+ if (++i2 == bwt_size)
+ i2 = 0;
+ }
+
+ return 0;
+}
+
+/*
+==================
+BWT
+==================
+*/
+cblock_t BWT (cblock_t in)
+{
+ int *sorted;
+ int i;
+ byte *out_p;
+ cblock_t out;
+
+ bwt_size = in.count;
+ bwt_data = in.data;
+
+ sorted = malloc(in.count*sizeof(*sorted));
+ for (i=0 ; i<in.count ; i++)
+ sorted[i] = i;
+ qsort (sorted, in.count, sizeof(*sorted), bwtCompare);
+
+ out_p = out.data = malloc(in.count + 8);
+
+ // write count
+ *out_p++ = in.count&255;
+ *out_p++ = (in.count>>8)&255;
+ *out_p++ = (in.count>>16)&255;
+ *out_p++ = (in.count>>24)&255;
+
+ // write head index
+ for (i=0 ; i<in.count ; i++)
+ if (sorted[i] == 0)
+ break;
+ *out_p++ = i&255;
+ *out_p++ = (i>>8)&255;
+ *out_p++ = (i>>16)&255;
+ *out_p++ = (i>>24)&255;
+
+ // write the L column
+ for (i=0 ; i<in.count ; i++)
+ *out_p++ = in.data[(sorted[i]+in.count-1)%in.count];
+
+ free (sorted);
+
+ out.count = out_p - out.data;
+
+ return out;
+}
+
+//==========================================================================
+
+typedef struct hnode_s
+{
+ int count;
+ qboolean used;
+ int children[2];
+} hnode_t;
+
+int numhnodes;
+hnode_t hnodes[512];
+unsigned charbits[256];
+int charbitscount[256];
+
+int SmallestNode (void)
+{
+ int i;
+ int best, bestnode;
+
+ best = 99999999;
+ bestnode = -1;
+ for (i=0 ; i<numhnodes ; i++)
+ {
+ if (hnodes[i].used)
+ continue;
+ if (!hnodes[i].count)
+ continue;
+ if (hnodes[i].count < best)
+ {
+ best = hnodes[i].count;
+ bestnode = i;
+ }
+ }
+
+ if (bestnode == -1)
+ return -1;
+
+ hnodes[bestnode].used = true;
+ return bestnode;
+}
+
+void BuildChars (int nodenum, unsigned bits, int bitcount)
+{
+ hnode_t *node;
+
+ if (nodenum < 256)
+ {
+ if (bitcount > 32)
+ Error ("bitcount > 32");
+ charbits[nodenum] = bits;
+ charbitscount[nodenum] = bitcount;
+ return;
+ }
+
+ node = &hnodes[nodenum];
+ bits <<= 1;
+ BuildChars (node->children[0], bits, bitcount+1);
+ bits |= 1;
+ BuildChars (node->children[1], bits, bitcount+1);
+}
+
+
+/*
+==================
+Huffman
+==================
+*/
+cblock_t Huffman (cblock_t in)
+{
+ int i;
+ hnode_t *node;
+ int outbits, c;
+ unsigned bits;
+ byte *out_p;
+ cblock_t out;
+ int max, maxchar;
+
+ // count
+ memset (hnodes, 0, sizeof(hnodes));
+ for (i=0 ; i<in.count ; i++)
+ hnodes[in.data[i]].count++;
+
+ // normalize counts
+ max = 0;
+ maxchar = 0;
+ for (i=0 ; i<256 ; i++)
+ {
+ if (hnodes[i].count > max)
+ {
+ max = hnodes[i].count;
+ maxchar = i;
+ }
+ }
+ if (max == 0)
+ Error ("Huffman: max == 0");
+
+ for (i=0 ; i<256 ; i++)
+ {
+ hnodes[i].count = (hnodes[i].count*255+max-1) / max;
+ }
+
+ // build the nodes
+ numhnodes = 256;
+ while (numhnodes != 511)
+ {
+ node = &hnodes[numhnodes];
+
+ // pick two lowest counts
+ node->children[0] = SmallestNode ();
+ if (node->children[0] == -1)
+ break; // no more
+
+ node->children[1] = SmallestNode ();
+ if (node->children[1] == -1)
+ {
+ if (node->children[0] != numhnodes-1)
+ Error ("Bad smallestnode");
+ break;
+ }
+ node->count = hnodes[node->children[0]].count +
+ hnodes[node->children[1]].count;
+ numhnodes++;
+ }
+
+ BuildChars (numhnodes-1, 0, 0);
+
+ out_p = out.data = malloc(in.count*2 + 1024);
+ memset (out_p, 0, in.count*2+1024);
+
+ // write count
+ *out_p++ = in.count&255;
+ *out_p++ = (in.count>>8)&255;
+ *out_p++ = (in.count>>16)&255;
+ *out_p++ = (in.count>>24)&255;
+
+ // save out the 256 normalized counts so the tree can be recreated
+ for (i=0 ; i<256 ; i++)
+ *out_p++ = hnodes[i].count;
+
+ // write bits
+ outbits = 0;
+ for (i=0 ; i<in.count ; i++)
+ {
+ c = charbitscount[in.data[i]];
+ bits = charbits[in.data[i]];
+ while (c)
+ {
+ c--;
+ if (bits & (1<<c))
+ out_p[outbits>>3] |= 1<<(outbits&7);
+ outbits++;
+ }
+ }
+
+ out_p += (outbits+7)>>3;
+
+ out.count = out_p - out.data;
+
+ return out;
+}
+
+//==========================================================================
+
+/*
+==================
+RLE
+==================
+*/
+#define RLE_CODE 0xe8
+#define RLE_TRIPPLE 0xe9
+
+int rle_counts[256];
+int rle_bytes[256];
+
+cblock_t RLE (cblock_t in)
+{
+ int i;
+ byte *out_p;
+ int val;
+ int repeat;
+ cblock_t out;
+
+ out_p = out.data = malloc (in.count*2);
+
+ // write count
+ *out_p++ = in.count&255;
+ *out_p++ = (in.count>>8)&255;
+ *out_p++ = (in.count>>16)&255;
+ *out_p++ = (in.count>>24)&255;
+
+ for (i=0 ; i<in.count ; )
+ {
+ val = in.data[i];
+ rle_bytes[val]++;
+ repeat = 1;
+ i++;
+ while (i<in.count && repeat < 255 && in.data[i] == val)
+ {
+ repeat++;
+ i++;
+ }
+if (repeat < 256)
+rle_counts[repeat]++;
+ if (repeat > 3 || val == RLE_CODE)
+ {
+ *out_p++ = RLE_CODE;
+ *out_p++ = val;
+ *out_p++ = repeat;
+ }
+ else
+ {
+ while (repeat--)
+ *out_p++ = val;
+ }
+ }
+
+ out.count = out_p - out.data;
+ return out;
+}
+
+//==========================================================================
+
+unsigned lzss_head[256];
+unsigned lzss_next[0x20000];
+
+/*
+==================
+LZSS
+==================
+*/
+#define BACK_WINDOW 0x10000
+#define BACK_BITS 16
+#define FRONT_WINDOW 16
+#define FRONT_BITS 4
+cblock_t LZSS (cblock_t in)
+{
+ int i;
+ byte *out_p;
+ cblock_t out;
+ int val;
+ int j, start, max;
+ int bestlength, beststart;
+ int outbits;
+
+if (in.count >= sizeof(lzss_next)/4)
+Error ("LZSS: too big");
+
+ memset (lzss_head, -1, sizeof(lzss_head));
+
+ out_p = out.data = malloc (in.count*2);
+ memset (out.data, 0, in.count*2);
+
+ // write count
+ *out_p++ = in.count&255;
+ *out_p++ = (in.count>>8)&255;
+ *out_p++ = (in.count>>16)&255;
+ *out_p++ = (in.count>>24)&255;
+
+ outbits = 0;
+ for (i=0 ; i<in.count ; )
+ {
+ val = in.data[i];
+#if 1
+// chained search
+ bestlength = 0;
+ beststart = 0;
+
+ max = FRONT_WINDOW;
+ if (i + max > in.count)
+ max = in.count - i;
+
+ start = lzss_head[val];
+ while (start != -1 && start >= i-BACK_WINDOW)
+ {
+ // count match length
+ for (j=0 ; j<max ; j++)
+ if (in.data[start+j] != in.data[i+j])
+ break;
+ if (j > bestlength)
+ {
+ bestlength = j;
+ beststart = start;
+ }
+ start = lzss_next[start];
+ }
+
+#else
+// slow simple search
+ // search for a match
+ max = FRONT_WINDOW;
+ if (i + max > in.count)
+ max = in.count - i;
+
+ start = i - BACK_WINDOW;
+ if (start < 0)
+ start = 0;
+ bestlength = 0;
+ beststart = 0;
+ for ( ; start < i ; start++)
+ {
+ if (in.data[start] != val)
+ continue;
+ // count match length
+ for (j=0 ; j<max ; j++)
+ if (in.data[start+j] != in.data[i+j])
+ break;
+ if (j > bestlength)
+ {
+ bestlength = j;
+ beststart = start;
+ }
+ }
+#endif
+ beststart = BACK_WINDOW - (i-beststart);
+
+ if (bestlength < 3)
+ { // output a single char
+ bestlength = 1;
+
+ out_p[outbits>>3] |= 1<<(outbits&7); // set bit to mark char
+ outbits++;
+ for (j=0 ; j<8 ; j++, outbits++)
+ if (val & (1<<j) )
+ out_p[outbits>>3] |= 1<<(outbits&7);
+ }
+ else
+ { // output a phrase
+ outbits++; // leave a 0 bit to mark phrase
+ for (j=0 ; j<BACK_BITS ; j++, outbits++)
+ if (beststart & (1<<j) )
+ out_p[outbits>>3] |= 1<<(outbits&7);
+ for (j=0 ; j<FRONT_BITS ; j++, outbits++)
+ if (bestlength & (1<<j) )
+ out_p[outbits>>3] |= 1<<(outbits&7);
+ }
+
+ while (bestlength--)
+ {
+ val = in.data[i];
+ lzss_next[i] = lzss_head[val];
+ lzss_head[val] = i;
+ i++;
+ }
+ }
+
+ out_p += (outbits+7)>>3;
+ out.count = out_p - out.data;
+ return out;
+}
+
+//==========================================================================
+
+#define MIN_REPT 15
+#define MAX_REPT 0
+#define HUF_TOKENS (256+MAX_REPT)
+
+unsigned charbits1[256][HUF_TOKENS];
+int charbitscount1[256][HUF_TOKENS];
+
+hnode_t hnodes1[256][HUF_TOKENS*2];
+int numhnodes1[256];
+
+int order0counts[256];
+
+/*
+==================
+SmallestNode1
+==================
+*/
+int SmallestNode1 (hnode_t *hnodes, int numhnodes)
+{
+ int i;
+ int best, bestnode;
+
+ best = 99999999;
+ bestnode = -1;
+ for (i=0 ; i<numhnodes ; i++)
+ {
+ if (hnodes[i].used)
+ continue;
+ if (!hnodes[i].count)
+ continue;
+ if (hnodes[i].count < best)
+ {
+ best = hnodes[i].count;
+ bestnode = i;
+ }
+ }
+
+ if (bestnode == -1)
+ return -1;
+
+ hnodes[bestnode].used = true;
+ return bestnode;
+}
+
+
+/*
+==================
+BuildChars1
+==================
+*/
+void BuildChars1 (int prev, int nodenum, unsigned bits, int bitcount)
+{
+ hnode_t *node;
+
+ if (nodenum < HUF_TOKENS)
+ {
+ if (bitcount > 32)
+ Error ("bitcount > 32");
+ charbits1[prev][nodenum] = bits;
+ charbitscount1[prev][nodenum] = bitcount;
+ return;
+ }
+
+ node = &hnodes1[prev][nodenum];
+ bits <<= 1;
+ BuildChars1 (prev, node->children[0], bits, bitcount+1);
+ bits |= 1;
+ BuildChars1 (prev, node->children[1], bits, bitcount+1);
+}
+
+
+/*
+==================
+BuildTree1
+==================
+*/
+void BuildTree1 (int prev)
+{
+ hnode_t *node, *nodebase;
+ int numhnodes;
+
+ // build the nodes
+ numhnodes = HUF_TOKENS;
+ nodebase = hnodes1[prev];
+ while (1)
+ {
+ node = &nodebase[numhnodes];
+
+ // pick two lowest counts
+ node->children[0] = SmallestNode1 (nodebase, numhnodes);
+ if (node->children[0] == -1)
+ break; // no more
+
+ node->children[1] = SmallestNode1 (nodebase, numhnodes);
+ if (node->children[1] == -1)
+ break;
+
+ node->count = nodebase[node->children[0]].count +
+ nodebase[node->children[1]].count;
+ numhnodes++;
+ }
+ numhnodes1[prev] = numhnodes-1;
+ BuildChars1 (prev, numhnodes-1, 0, 0);
+}
+
+
+/*
+==================
+Huffman1_Count
+==================
+*/
+void Huffman1_Count (cblock_t in)
+{
+ int i;
+ int prev;
+ int v;
+ int rept;
+
+ prev = 0;
+ for (i=0 ; i<in.count ; i++)
+ {
+ v = in.data[i];
+ order0counts[v]++;
+ hnodes1[prev][v].count++;
+ prev = v;
+#if 1
+ for (rept=1 ; i+rept < in.count && rept < MAX_REPT ; rept++)
+ if (in.data[i+rept] != v)
+ break;
+ if (rept > MIN_REPT)
+ {
+ hnodes1[prev][255+rept].count++;
+ i += rept-1;
+ }
+#endif
+ }
+}
+
+
+/*
+==================
+Huffman1_Build
+==================
+*/
+byte scaled[256][HUF_TOKENS];
+void Huffman1_Build (FILE *f)
+{
+ int i, j, v;
+ int max;
+ int total;
+
+ for (i=0 ; i<256 ; i++)
+ {
+ // normalize and save the counts
+ max = 0;
+ for (j=0 ; j<HUF_TOKENS ; j++)
+ {
+ if (hnodes1[i][j].count > max)
+ max = hnodes1[i][j].count;
+ }
+ if (max == 0)
+ max = 1;
+ total = 0;
+ for (j=0 ; j<HUF_TOKENS ; j++)
+ { // easy to overflow 32 bits here!
+ v = (hnodes1[i][j].count*(double)255+max-1)/max;
+ if (v > 255)
+ Error ("v > 255");
+ scaled[i][j] = hnodes1[i][j].count = v;
+ if (v)
+ total++;
+ }
+ if (total == 1)
+ { // must have two tokens
+ if (!scaled[i][0])
+ scaled[i][0] = hnodes1[i][0].count = 1;
+ else
+ scaled[i][1] = hnodes1[i][1].count = 1;
+ }
+
+ BuildTree1 (i);
+ }
+
+#if 0
+ // count up the total bits
+ total = 0;
+ for (i=0 ; i<256 ; i++)
+ for (j=0 ; j<256 ; j++)
+ total += charbitscount1[i][j] * hnodes1[i][j].count;
+
+ total = (total+7)/8;
+ printf ("%i bytes huffman1 compressed\n", total);
+#endif
+
+ fwrite (scaled, 1, sizeof(scaled), f);
+}
+
+/*
+==================
+Huffman1
+
+Order 1 compression with pre-built table
+==================
+*/
+cblock_t Huffman1 (cblock_t in)
+{
+ int i;
+ int outbits, c;
+ unsigned bits;
+ byte *out_p;
+ cblock_t out;
+ int prev;
+ int v;
+ int rept;
+
+ out_p = out.data = malloc(in.count*2 + 1024);
+ memset (out_p, 0, in.count*2+1024);
+
+ // write count
+ *out_p++ = in.count&255;
+ *out_p++ = (in.count>>8)&255;
+ *out_p++ = (in.count>>16)&255;
+ *out_p++ = (in.count>>24)&255;
+
+ // write bits
+ outbits = 0;
+ prev = 0;
+ for (i=0 ; i<in.count ; i++)
+ {
+ v = in.data[i];
+
+ c = charbitscount1[prev][v];
+ bits = charbits1[prev][v];
+ if (!c)
+ Error ("!bits");
+ while (c)
+ {
+ c--;
+ if (bits & (1<<c))
+ out_p[outbits>>3] |= 1<<(outbits&7);
+ outbits++;
+ }
+
+ prev = v;
+#if 1
+ // check for repeat encodes
+ for (rept=1 ; i+rept < in.count && rept < MAX_REPT ; rept++)
+ if (in.data[i+rept] != v)
+ break;
+ if (rept > MIN_REPT)
+ {
+ c = charbitscount1[prev][255+rept];
+ bits = charbits1[prev][255+rept];
+ if (!c)
+ Error ("!bits");
+ while (c)
+ {
+ c--;
+ if (bits & (1<<c))
+ out_p[outbits>>3] |= 1<<(outbits&7);
+ outbits++;
+ }
+ i += rept-1;
+ }
+#endif
+ }
+
+ out_p += (outbits+7)>>3;
+
+ out.count = out_p - out.data;
+
+ return out;
+}
+
+//==========================================================================
+
+
+/*
+===================
+LoadFrame
+===================
+*/
+cblock_t LoadFrame (char *base, int frame, int digits, byte **palette)
+{
+ int ten3, ten2, ten1, ten0;
+ cblock_t in;
+ int width, height;
+ char name[1024];
+ FILE *f;
+
+ in.data = NULL;
+ in.count = -1;
+
+ ten3 = frame/1000;
+ ten2 = (frame-ten3*1000)/100;
+ ten1 = (frame-ten3*1000-ten2*100)/10;
+ ten0 = frame%10;
+
+ if (digits == 4)
+ sprintf (name, "%svideo/%s/%s%i%i%i%i.pcx", gamedir, base, base, ten3, ten2, ten1, ten0);
+ else
+ sprintf (name, "%svideo/%s/%s%i%i%i.pcx", gamedir, base, base, ten2, ten1, ten0);
+
+ f = fopen(name, "rb");
+ if (!f)
+ {
+ in.data = NULL;
+ return in;
+ }
+ fclose (f);
+
+ printf ("%s\n", name);
+ Load256Image (name, &in.data, palette, &width, &height);
+ in.count = width*height;
+// FIXME: map 0 and 255!
+
+#if 0
+ // rle compress
+ rle = RLE(in);
+ free (in.data);
+
+ return rle;
+#endif
+
+ return in;
+}
+
+/*
+===============
+Cmd_Video
+
+video <directory> <framedigits>
+===============
+*/
+void Cmd_Video (void)
+{
+ char savename[1024];
+ char name[1024];
+ FILE *output;
+ int startframe, frame;
+ byte *palette;
+ int width, height;
+ byte current_palette[768];
+ int command;
+ int i;
+ int digits;
+ cblock_t in, huffman;
+ int swap;
+
+
+ GetToken (false);
+ strcpy (base, token);
+ if (g_release)
+ {
+// sprintf (savename, "video/%s.cin", token);
+// ReleaseFile (savename);
+ return;
+ }
+
+ GetToken (false);
+ digits = atoi(token);
+
+ // optionally skip frames
+ if (TokenAvailable ())
+ {
+ GetToken (false);
+ startframe = atoi(token);
+ }
+ else
+ startframe=0;
+
+ sprintf (savename, "%svideo/%s.cin", gamedir, base);
+
+
+ // clear stuff
+ memset (charbits1, 0, sizeof(charbits1));
+ memset (charbitscount1, 0, sizeof(charbitscount1));
+ memset (hnodes1, 0, sizeof(hnodes1));
+ memset (numhnodes1, 0, sizeof(numhnodes1));
+ memset (order0counts, 0, sizeof(order0counts));
+
+
+ // load the entire sound wav file if present
+ LoadSoundtrack ();
+
+ if (digits == 4)
+ sprintf (name, "%svideo/%s/%s0000.pcx", gamedir, base, base);
+ else
+ sprintf (name, "%svideo/%s/%s000.pcx", gamedir, base, base);
+
+ printf ("%s\n", name);
+ Load256Image (name, NULL, &palette, &width, &height);
+
+ output = fopen (savename, "wb");
+ if (!output)
+ Error ("Can't open %s", savename);
+
+ // write header info
+ i = LittleLong (width);
+ fwrite (&i, 4, 1, output);
+ i = LittleLong (height);
+ fwrite (&i, 4, 1, output);
+ i = LittleLong (wavinfo.rate);
+ fwrite (&i, 4, 1, output);
+ i = LittleLong (wavinfo.width);
+ fwrite (&i, 4, 1, output);
+ i = LittleLong (wavinfo.channels);
+ fwrite (&i, 4, 1, output);
+
+ // build the dictionary
+ for ( frame=startframe ; ; frame++)
+ {
+ printf ("counting ", frame);
+ in = LoadFrame (base, frame, digits, &palette);
+ if (!in.data)
+ break;
+ Huffman1_Count (in);
+ free (in.data);
+ }
+ printf ("\n");
+
+ // build nodes and write counts
+ Huffman1_Build (output);
+
+
+ memset (current_palette, 0, sizeof(current_palette));
+
+ // compress it with the dictionary
+ for (frame=startframe ; ; frame++)
+ {
+ printf ("packing ", frame);
+ in = LoadFrame (base, frame, digits, &palette);
+ if (!in.data)
+ break;
+
+ // see if the palette has changed
+ for (i=0 ; i<768 ; i++)
+ if (palette[i] != current_palette[i])
+ {
+ // write a palette change
+ memcpy (current_palette, palette, sizeof(current_palette));
+ command = LittleLong(1);
+ fwrite (&command, 1, 4, output);
+ fwrite (current_palette, 1, sizeof(current_palette), output);
+ break;
+ }
+ if (i == 768)
+ {
+ command = 0; // no palette change
+ fwrite (&command, 1, 4, output);
+ }
+
+ // save the image
+ huffman = Huffman1 (in);
+ printf ("%5i bytes after huffman1\n", huffman.count);
+
+ swap = LittleLong (huffman.count);
+ fwrite (&swap, 1, sizeof(swap), output);
+
+ fwrite (huffman.data, 1, huffman.count, output);
+
+ // save some sound samples
+ WriteSound (output, frame);
+
+ free (palette);
+ free (in.data);
+ free (huffman.data);
+ }
+ printf ("\n");
+
+ // write end-of-file command
+ command = 2;
+ fwrite (&command, 1, 4, output);
+
+ printf ("Total size: %i\n", ftell (output));
+
+ fclose (output);
+
+ if (soundtrack)
+ free (soundtrack);
+}
projects / xonotic / netradiant.git / blobdiff