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