2 // LordHavoc: my little compression library
8 typedef unsigned char byte;
11 #define HCOMPRESS_CORRUPT -1
30 int hc_readimmediate(hcblock *b)
32 return b->data[b->position++];
35 int hc_readsize(hcblock *b)
38 return b->data[b->position - 2];
41 int hc_readoffset(hcblock *b)
44 return b->data[b->position - 2];
47 int hc_readbit(hcblock *b)
49 return b->data[b->position++];
52 void hc_writeimmediate(hcblock *b, int num)
54 b->data[b->size++] = num;
57 void hc_writesize(hcblock *b, int num)
59 b->data[b->size] = num;
63 void hc_writeoffset(hcblock *b, int num)
65 b->data[b->size] = num;
69 void hc_writebit(hcblock *b, int num)
71 b->data[b->size++] = num;
74 int hcompress_decompress(void *inaddr, void *outaddr, int insize, int outsize)
84 int commandbits, commandbyte, count, temp;
87 while (outsize && insize)
93 return HCOMPRESS_CORRUPT;
98 return HCOMPRESS_CORRUPT;
102 for (;commandbits && outsize;commandbits--,commandbyte >>= 1)
104 if (commandbyte & 1) // reference
107 return HCOMPRESS_CORRUPT;
108 size = (in[0] >> 4) + 3;
110 return HCOMPRESS_CORRUPT;
113 tempout = out - ((((in[0] << 8) | in[1]) & 0xFFF) + 1);
114 if ((int) tempout < (int) outaddr)
115 return HCOMPRESS_CORRUPT;
121 if (!insize || !outsize)
122 return HCOMPRESS_CORRUPT;
129 else // copy 8 bytes straight
131 if (insize < 8 || outsize < 8)
132 return HCOMPRESS_CORRUPT;
145 if (insize || outsize)
146 return HCOMPRESS_CORRUPT;
147 return ((int) out - (int) outaddr);
149 return HCOMPRESS_CORRUPT;
152 int hcompress_compress(void *indata, void *outdata, int size)
157 unsigned short size; // if size == 0, offset holds the immediate value
158 unsigned short offset;
160 int offsetcount[65536];
164 int c, i, j, l, bestsize, bestposition, maxlen;
169 int start; // start of the chain
170 int length; // length of the chain
171 } hashindex[256][256];
173 token = qmalloc(size*sizeof(struct hctoken));
174 hashtable = qmalloc(size*sizeof(int));
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
183 for (i = 0;i < 256;i++)
185 for (j = 0;j < 256;j++)
187 hashindex[i][j].start = c;
188 c += hashindex[i][j].length;
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;
201 while (position < size)
204 if (position + 1 == size) // this is the last byte
206 h = &hashtable[hashindex[c][0].start];
207 l = hashindex[c][0].length;
211 h = &hashtable[hashindex[c][*in].start];
212 l = hashindex[c][0].length;
216 if (*h < position - 65535) // too old, nudge up the chain to avoid finding this one again
218 if (position + 1 == size)
220 hashindex[c][0].start++;
221 hashindex[c][0].length--;
225 hashindex[c][*in].start++;
226 hashindex[c][*in].length--;
239 maxlen = size - position;
242 for (i = 0;i < maxlen;i++)
255 token[tokens].size = bestsize;
256 token[tokens++].offset = position - bestposition; // offset backward
257 sizecount[bestsize - 3]++;
258 offsetcount[position - bestposition]++;
262 // write an immediate
263 token[tokens].size = 0;
264 token[tokens++].offset = c;
269 // no remaining occurances, write an immediate
270 token[tokens].size = 0;
271 token[tokens++].offset = c;
276 // no remaining occurances, write an immediate
277 token[tokens].size = 0;
278 token[tokens++].offset = c;
281 return HCOMPRESS_CORRUPT;
284 int i, index, insize = size, outsize = 0, commandbyte = 0, commandbits = 0;
285 struct hcompress_hashchain
290 short hashindex[65536];
297 for (i = 0;i < 65536;i++)
299 for (i = 0;i < 4096;i++)
301 hashchain[i].next = -1;
302 hashchain[i].key = -1;
308 if (insize >= 3) // enough data left to compress
310 key = in[0] | (in[1] << 8);
313 index = ((int) in + 1) & 0xFFF;
314 if (hash[index].key >= 0)
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;
321 hash[index].key = key;
322 hash[index].next = hashindex[key];
323 hashindex[key] = index;
329 ref[commandbits].type = 0;
330 ref[commandbits++].data = *in++;