-#include "q3data.h"\r
-\r
-#if 0\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
-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
-#endif\r
+#include "q3data.h"
+
+#if 0
+/*
+==================
+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;
+}
+
+#endif
projects / xonotic / netradiant.git / blobdiff