Small fixes to tab completion
[xonotic/darkplaces.git] / hcompress.c
1
2 // LordHavoc: my little compression library
3
4 #if 0
5 #include <stdlib.h>
6
7 #ifndef byte
8 typedef unsigned char byte;
9 #endif
10
11 #define HCOMPRESS_CORRUPT -1
12
13 typedef struct
14 {
15         int position;
16         int size;
17         byte *data;
18 } hcblock;
19
20 typedef struct
21 {
22         int identifer;
23         int compressedsize;
24         int decompressedsize;
25         int compressedcrc;
26         int decompressedcrc;
27         byte data[0];
28 } storagehcblock;
29
30 int hc_readimmediate(hcblock *b)
31 {
32         return b->data[b->position++];
33 }
34
35 int hc_readsize(hcblock *b)
36 {
37         b->position += 2;
38         return b->data[b->position - 2];
39 }
40
41 int hc_readoffset(hcblock *b)
42 {
43         b->position += 2;
44         return b->data[b->position - 2];
45 }
46
47 int hc_readbit(hcblock *b)
48 {
49         return b->data[b->position++];
50 }
51
52 void hc_writeimmediate(hcblock *b, int num)
53 {
54         b->data[b->size++] = num;
55 }
56
57 void hc_writesize(hcblock *b, int num)
58 {
59         b->data[b->size] = num;
60         b->size += 2;
61 }
62
63 void hc_writeoffset(hcblock *b, int num)
64 {
65         b->data[b->size] = num;
66         b->size += 2;
67 }
68
69 void hc_writebit(hcblock *b, int num)
70 {
71         b->data[b->size++] = num;
72 }
73
74 int hcompress_decompress(void *inaddr, void *outaddr, int insize, int outsize)
75 {
76         /*
77         byte *in, *out;
78         hcblock b;
79         b.position = 0;
80         b.size = 0;
81         b.
82         b = inaddr;
83         if (
84         int commandbits, commandbyte, count, temp;
85         in = inaddr;
86         out = outaddr;
87         while (outsize && insize)
88         {
89                 hc_readbit(
90                 if (!commandbits)
91                 {
92                         if (!insize)
93                                 return HCOMPRESS_CORRUPT;
94                         commandbyte = *in++;
95                         commandbits = 8;
96                         insize--;
97                         if (!insize)
98                                 return HCOMPRESS_CORRUPT;
99                 }
100                 if (commandbyte)
101                 {
102                         for (;commandbits && outsize;commandbits--,commandbyte >>= 1)
103                         {
104                                 if (commandbyte & 1) // reference
105                                 {
106                                         if (insize < 2)
107                                                 return HCOMPRESS_CORRUPT;
108                                         size = (in[0] >> 4) + 3;
109                                         if (size > outsize)
110                                                 return HCOMPRESS_CORRUPT;
111                                         insize -= 2;
112                                         outsize -= size;
113                                         tempout = out - ((((in[0] << 8) | in[1]) & 0xFFF) + 1);
114                                         if ((int) tempout < (int) outaddr)
115                                                 return HCOMPRESS_CORRUPT;
116                                         while (size--)
117                                                 *out++ = *tempout++;
118                                 }
119                                 else
120                                 {
121                                         if (!insize || !outsize)
122                                                 return HCOMPRESS_CORRUPT;
123                                         *out++ = *in++;
124                                         insize--;
125                                         outsize--;
126                                 }
127                         }
128                 }
129                 else // copy 8 bytes straight
130                 {
131                         if (insize < 8 || outsize < 8)
132                                 return HCOMPRESS_CORRUPT;
133                         *out++ = *in++;
134                         *out++ = *in++;
135                         *out++ = *in++;
136                         *out++ = *in++;
137                         *out++ = *in++;
138                         *out++ = *in++;
139                         *out++ = *in++;
140                         *out++ = *in++;
141                         insize -= 8;
142                         outsize -= 8;
143                 }
144         }
145         if (insize || outsize)
146                 return HCOMPRESS_CORRUPT;
147         return ((int) out - (int) outaddr);
148         */
149         return HCOMPRESS_CORRUPT;
150 }
151
152 int hcompress_compress(void *indata, void *outdata, int size)
153 {
154         byte *in, *out;
155         struct hctoken
156         {
157                 unsigned short size; // if size == 0, offset holds the immediate value
158                 unsigned short offset;
159         } *token;
160         int offsetcount[65536];
161         int sizecount[256];
162         int tokens = 0;
163         int position = 0;
164         int c, i, j, l, bestsize, bestposition, maxlen;
165         int *h;
166         byte *c1, *c2;
167         struct
168         {
169                 int start; // start of the chain
170                 int length; // length of the chain
171         } hashindex[256][256];
172         int *hashtable;
173         token = qmalloc(size*sizeof(struct hctoken));
174         hashtable = qmalloc(size*sizeof(int));
175         in = indata;
176         memset(&hashindex, 0, sizeof(hashindex));
177         // count the chain lengths
178         for (i = 0;i < size-1;i++)
179                 hashindex[in[i]][in[i+1]].length++;
180         hashindex[in[i]][0].length++;
181         // assign starting positions for each chain
182         c = 0;
183         for (i = 0;i < 256;i++)
184         {
185                 for (j = 0;j < 256;j++)
186                 {
187                         hashindex[i][j].start = c;
188                         c += hashindex[i][j].length;
189                 }
190         }
191         // enter the data into the chains
192         for (i = 0;i < size-1;i++)
193                 hashtable[hashindex[in[i]][in[i+1]].start++] = i;
194         hashtable[hashindex[in[i]][0].start++] = i;
195         // adjust start positions back to what they should be
196         for (i = 0;i < 256;i++)
197                 for (j = 0;j < 256;j++)
198                         hashindex[i][j].start -= hashindex[i][j].length;
199         // now the real work
200         out = outdata;
201         while (position < size)
202         {
203                 c = *in++;
204                 if (position + 1 == size) // this is the last byte
205                 {
206                         h = &hashtable[hashindex[c][0].start];
207                         l = hashindex[c][0].length;
208                 }
209                 else
210                 {
211                         h = &hashtable[hashindex[c][*in].start];
212                         l = hashindex[c][0].length;
213                 }
214                 if (l)
215                 {
216                         if (*h < position - 65535) // too old, nudge up the chain to avoid finding this one again
217                         {
218                                 if (position + 1 == size)
219                                 {
220                                         hashindex[c][0].start++;
221                                         hashindex[c][0].length--;
222                                 }
223                                 else
224                                 {
225                                         hashindex[c][*in].start++;
226                                         hashindex[c][*in].length--;
227                                 }
228                                 h++;
229                                 l--;
230                         }
231                         if (l)
232                         {
233                                 bestsize = 0;
234                                 bestposition = 0;
235                                 while (l--)
236                                 {
237                                         c1 = &in[*h];
238                                         c2 = &in[position];
239                                         maxlen = size - position;
240                                         if (maxlen > 258)
241                                                 maxlen = 258;
242                                         for (i = 0;i < maxlen;i++)
243                                                 if (*c1++ != *c2++)
244                                                         break;
245                                         if (i > bestsize)
246                                         {
247                                                 bestsize = i;
248                                                 bestposition = *h;
249                                         }
250                                         h++;
251                                 }
252                                 if (bestsize >= 3)
253                                 {
254                                         // write a reference
255                                         token[tokens].size = bestsize;
256                                         token[tokens++].offset = position - bestposition; // offset backward
257                                         sizecount[bestsize - 3]++;
258                                         offsetcount[position - bestposition]++;
259                                 }
260                                 else
261                                 {
262                                         // write an immediate
263                                         token[tokens].size = 0;
264                                         token[tokens++].offset = c;
265                                 }
266                         }
267                         else
268                         {
269                                 // no remaining occurances, write an immediate
270                                 token[tokens].size = 0;
271                                 token[tokens++].offset = c;
272                         }
273                 }
274                 else
275                 {
276                         // no remaining occurances, write an immediate
277                         token[tokens].size = 0;
278                         token[tokens++].offset = c;
279                 }
280         }
281         return HCOMPRESS_CORRUPT;
282
283         /*
284         int i, index, insize = size, outsize = 0, commandbyte = 0, commandbits = 0;
285         struct hcompress_hashchain
286         {
287                 short prev, next;
288                 int key;
289         } hashchain[4096];
290         short hashindex[65536];
291         int hashvalue[4096];
292         struct
293         {
294                 byte type;
295                 unsigned short data;
296         } ref[8];
297         for (i = 0;i < 65536;i++)
298                 hashindex[i] = -1;
299         for (i = 0;i < 4096;i++)
300         {
301                 hashchain[i].next = -1;
302                 hashchain[i].key = -1;
303         }
304         in = indata;
305         out = outdata;
306         while(insize)
307         {
308                 if (insize >= 3) // enough data left to compress
309                 {
310                         key = in[0] | (in[1] << 8);
311                         if (hashindex[
312                         for (
313                         index = ((int) in + 1) & 0xFFF;
314                         if (hash[index].key >= 0)
315                         {
316                                 if (hashindex[hash[index].key] == index)
317                                         hashindex[hash[index].key] = -1;
318                                 if (hash[index].prev >= 0)
319                                         hash[hash[index].prev].next = hash[index].next;
320                         }
321                         hash[index].key = key;
322                         hash[index].next = hashindex[key];
323                         hashindex[key] = index;
324                 }
325                 else
326                 {
327                         while (insize--)
328                         {
329                                 ref[commandbits].type = 0;
330                                 ref[commandbits++].data = *in++;
331                         }
332                 }
333         }
334         */
335 }
336 #endif