src/libwdx/libwdx.c

   1 /*
   2  * original code: WDOSX-Pack v1.07, (c) 1999-2001 by Joergen Ibsen / Jibz
   3  * for data and executable compression software: http://www.ibsensoftware.com/
   4  */
   5 #include "libwdx.h"
   6
   7 #include <stdio.h>
   8
   9 #include <setjmp.h>
  10 #include <stdint.h>
  11 #include <stdlib.h>
  12 #include <string.h>
  13
  14
  15 #ifndef WDX_EXCLUDE_CRC
  16 uint32_t wdxCRC32 (const void *src, int len) {
  17   static const unsigned int crctab[16] = {
  18     0x00000000, 0x1db71064, 0x3b6e20c8, 0x26d930ac, 0x76dc4190,
  19     0x6b6b51f4, 0x4db26158, 0x5005713c, 0xedb88320, 0xf00f9344,
  20     0xd6d6a3e8, 0xcb61b38c, 0x9b64c2b0, 0x86d3d2d4, 0xa00ae278,
  21     0xbdbdf21c
  22   };
  23   const uint8_t *buf = (const uint8_t *)src;
  24   uint32_t crc = 0xffffffffUL;
  25   //
  26   if (src == NULL || len < 1) return 0;
  27   while (len--) {
  28     crc ^= *buf++;
  29     crc = crctab[crc&0x0f]^(crc>>4);
  30     crc = crctab[crc&0x0f]^(crc>>4);
  31   }
  32   return crc^0xffffffffUL;
  33 }
  34 #endif
  35
  36
  37 #define WDXUNPACK_LEN2_LIMIT  1920
  38
  39 #define WDXFatalError()  longjmp(errJP, 666)
  40
  41
  42 #ifndef WDX_EXCLUDE_PACKER
  43 int wdxPackBufferSize (int inSize) {
  44   if (inSize < 1) return 0;
  45   return inSize+((inSize+7)/8)+2;
  46 }
  47
  48
  49 int wdxPack (void *dest, int destSize, const void *source, int length) {
  50   typedef struct {
  51     uint32_t pos;
  52     uint32_t len;
  53   } TheMatch;
  54   /* global variables */
  55   const uint8_t *inBuffer = (const uint8_t *)source, *sourceOfs, *backPtr;
  56   uint8_t *outBuffer = (uint8_t *)dest;
  57   uint32_t nextBackEntry;
  58   uint8_t *tagByte;
  59   int bitCount;
  60   uint32_t *backTable; /* back-table, array */
  61   //uint32_t lookup[256][256]; /* lookup-table */ /*FIXME: made dynamic*/
  62   uint32_t *lookup = NULL; /* lookup-table */ /*FIXME: made dynamic*/
  63   uint32_t lastMatchPos = 0;
  64   int lastWasMatch = 0;
  65   jmp_buf errJP;
  66   uint32_t bytesOut = 0;
  67
  68   void advanceTagByte (int bit) {
  69     /* check bitcount and then decrement */
  70     if (bitCount == 0) {
  71       if (--destSize < 0) WDXFatalError();
  72       bitCount = 8;
  73       tagByte = outBuffer++;
  74       *tagByte = 0;
  75       ++bytesOut;
  76     }
  77     /* shift in bit */
  78     *tagByte = ((*tagByte)<<1)|(bit?1:0);
  79     --bitCount;
  80   }
  81
  82   /* output Gamma2-code for val in range [2..?] ... */
  83   void outputGamma (uint32_t val) {
  84     uint32_t invertlen = 0, invert = 0;
  85     //
  86     /* rotate bits into invert (except last) */
  87     do {
  88       invert = (invert<<1)|(val&0x01);
  89       ++invertlen;
  90       val = (val>>1)&0x7FFFFFFF;
  91     } while (val > 1);
  92     /* output Gamma2-encoded bits */
  93     for (--invertlen; invertlen > 0; --invertlen) {
  94       advanceTagByte(invert&0x01);
  95       advanceTagByte(1);
  96       invert >>= 1;
  97     }
  98     advanceTagByte(invert&0x01);
  99     advanceTagByte(0);
 100   }
 101
 102   void outputLiteral (uint8_t lit) {
 103     lastWasMatch = 0;
 104     advanceTagByte(0); /* 0 indicates a literal */
 105     if (--destSize < 0) WDXFatalError();
 106     *outBuffer++ = lit; /* output the literal */
 107     ++bytesOut;
 108   }
 109
 110   void outputCodePair (uint32_t pos, uint32_t len, const uint8_t *buffer) {
 111     /* if we just had a match, don't use lastMatchPos */
 112     if (lastWasMatch) {
 113       /* if a short match is too far away, encode it as two literals instead */
 114       if (pos > WDXUNPACK_LEN2_LIMIT && len == 2) {
 115         outputLiteral(buffer[0]);
 116         outputLiteral(buffer[1]);
 117       } else {
 118         advanceTagByte(1); /* 1 indicates a match */
 119         /* a match more than WDXUNPACK_LEN2_LIMIT bytes back will be longer than 2 */
 120         if (pos > WDXUNPACK_LEN2_LIMIT) --len;
 121         outputGamma(len); /* output length */
 122         lastMatchPos = pos--;
 123         /*assert(pos >= 0);*/
 124         outputGamma(((pos>>6)&0x3FFFFFFF)+2); /* output high part of position */
 125         /* output low 6 bits of position */
 126         advanceTagByte(pos&0x20);
 127         advanceTagByte(pos&0x10);
 128         advanceTagByte(pos&0x08);
 129         advanceTagByte(pos&0x04);
 130         advanceTagByte(pos&0x02);
 131         advanceTagByte(pos&0x01);
 132       }
 133     } else {
 134       lastWasMatch = 1;
 135       /* if a short match is too far away, encode it as two literals instead */
 136       if (pos > WDXUNPACK_LEN2_LIMIT && len == 2 && pos != lastMatchPos) {
 137         outputLiteral(buffer[0]);
 138         outputLiteral(buffer[1]);
 139       } else {
 140         advanceTagByte(1); /* 1 indicates a match */
 141         /* a match more than WDXUNPACK_LEN2_LIMIT bytes back will be longer than 2 */
 142         if (pos > WDXUNPACK_LEN2_LIMIT && pos != lastMatchPos) --len;
 143         outputGamma(len); /* output length */
 144         /* output position */
 145         if (pos == lastMatchPos) {
 146           /* a match with position 0 means use last position */
 147           advanceTagByte(0);
 148           advanceTagByte(0);
 149         } else {
 150           lastMatchPos = pos--;
 151           /*assert(pos >= 0);*/
 152           outputGamma(((pos>>6)&0x3FFFFFFF)+3); /* output high part of position */
 153           /* output low 6 bits of position */
 154           advanceTagByte(pos&0x20);
 155           advanceTagByte(pos&0x10);
 156           advanceTagByte(pos&0x08);
 157           advanceTagByte(pos&0x04);
 158           advanceTagByte(pos&0x02);
 159           advanceTagByte(pos&0x01);
 160         }
 161       }
 162     }
 163   }
 164
 165   void findMatch (TheMatch *thematch, const uint8_t *buffer, uint32_t lookback, uint32_t lookforward) {
 166     uint32_t backPos, matchLen, bestMatchLen, bestMatchPos;
 167     const uint8_t *ptr;
 168     uint32_t i0, i1;
 169     uint32_t idx0, idx1;
 170     //
 171     /* temporary variables to avoid indirect addressing into the match */
 172     bestMatchLen = 0; bestMatchPos = 0;
 173     /* update lookup- and backtable up to current position */
 174     while (backPtr < buffer) {
 175       idx0 = backPtr[0];
 176       idx1 = backPtr[1];
 177       backTable[nextBackEntry] = lookup[idx0*256+idx1];
 178       lookup[idx0*256+idx1] = nextBackEntry;
 179       ++nextBackEntry;
 180       ++backPtr;
 181     }
 182     /* get position by looking up next two bytes */
 183     backPos = lookup[buffer[0]*256+buffer[1]];
 184     if (backPos != 0 && lookforward > 1) {
 185       ptr = backPos+sourceOfs;
 186       /* go backwards until before buffer */
 187       while (ptr >= buffer && backPos != 0) {
 188         /*backPos := PInt(Integer(backTable)+backPos*4)^;*/
 189         backPos = backTable[backPos];
 190         ptr = backPos+sourceOfs;
 191       }
 192       /* search through table entries */
 193       while (backPos != 0 && buffer-ptr <= lookback) {
 194         matchLen = 2;
 195         /* if this position has a chance to be better */
 196         if (*(ptr+bestMatchLen) == *(buffer+bestMatchLen)) {
 197           /* scan it */
 198           while (matchLen < lookforward && *(ptr+matchLen) == *(buffer+matchLen)) ++matchLen;
 199           /* check it */
 200           i0 = buffer-ptr==lastMatchPos ? 1 : 0;
 201           i1 = bestMatchPos==lastMatchPos ? 1 : 0;
 202           if (matchLen+i0 > bestMatchLen+i1) {
 203             bestMatchLen = matchLen;
 204             if (bestMatchLen == lookforward) backPos = 0;
 205             bestMatchPos = buffer-ptr;
 206           }
 207         }
 208         /* move backwards to next position */
 209         /*backPos := PInt(Integer(backTable)+backPos*4)^;*/
 210         backPos = backTable[backPos];
 211         ptr = backPos+sourceOfs;
 212       }
 213     }
 214     /* forget match if too far away */
 215     if (bestMatchPos > WDXUNPACK_LEN2_LIMIT && bestMatchLen == 2 && bestMatchPos != lastMatchPos) {
 216       bestMatchLen = 0;
 217       bestMatchPos = 0;
 218     }
 219     /* update the match with best match */
 220     thematch->len = bestMatchLen;
 221     thematch->pos = bestMatchPos;
 222   }
 223
 224   /* main code */
 225   TheMatch match, nextmatch, literalmatch, testmatch;
 226   uint32_t pos, lastpos, literalCount;
 227   //int i, j;
 228   uint32_t i0, i1;
 229
 230   if (length < 1) return 0;
 231   if (destSize < 2) return -1;
 232   if (!(backTable = malloc((length+4)*4))) return -2; /* out of memory */
 233   if (!(lookup = malloc(256*256*4))) { free(backTable); return -2; } /* out of memory */
 234
 235   if (setjmp(errJP)) {
 236     /* compressing error */
 237     free(lookup);
 238     free(backTable);
 239     return -1;
 240   }
 241
 242   memset(&match, 0, sizeof(match));
 243   memset(&nextmatch, 0, sizeof(nextmatch));
 244   memset(&literalmatch, 0, sizeof(literalmatch));
 245   memset(&testmatch, 0, sizeof(testmatch));
 246   literalmatch.pos = literalmatch.len = 0;
 247   sourceOfs = inBuffer-1;
 248   /* init lookup- and backtable */
 249   /*for (i = 0; i <= 255; ++i) for (j = 0; j <= 255; ++j) lookup[i*256+j] = 0;*/
 250   memset(lookup, 0, 256*256*4);
 251   memset(backTable, 0, (length+4)*4);
 252   backPtr = inBuffer;
 253   backTable[0] = 0;
 254   nextBackEntry = 1;
 255   lastpos = -1;
 256   lastMatchPos = -1;
 257   lastWasMatch = 0;
 258   literalCount = 0;
 259   /* the first byte is sent verbatim */
 260   *outBuffer++ = *inBuffer++;
 261   --destSize;
 262   ++bytesOut;
 263   /* init tag-byte */
 264   bitCount = 8;
 265   *(tagByte = outBuffer++) = 0;
 266   --destSize;
 267   ++bytesOut;
 268   /* pack data */
 269   pos = 1;
 270   while (pos < length) {
 271     /* find best match at current position (if not already found) */
 272     if (pos == lastpos) {
 273       match.len = nextmatch.len;
 274       match.pos = nextmatch.pos;
 275     } else {
 276       findMatch(&match, inBuffer, pos, length-pos);
 277     }
 278     /* if we found a match, find the best match at the next position */
 279     if (match.len != 0) {
 280       findMatch(&nextmatch, inBuffer+1, pos+1, length-(pos+1));
 281       lastpos = pos+1;
 282     } else {
 283       nextmatch.len = 0;
 284     }
 285     /* decide if we should output a match or a literal */
 286     i0 = (match.pos==lastMatchPos ? 1 : 0);
 287     i1 = (nextmatch.pos==lastMatchPos ? 1 : 0);
 288     if (match.len != 0 && match.len+i0 >= nextmatch.len+i1) {
 289       /* output any pending literals */
 290       if (literalCount != 0) {
 291         if (literalCount == 1) {
 292           outputLiteral(inBuffer[-1]);
 293         } else {
 294           /* check if there is a closer match with the required length */
 295           findMatch(&testmatch, inBuffer-literalCount, literalmatch.pos, literalCount);
 296           if (testmatch.len >= literalCount) outputCodePair(testmatch.pos, literalCount, inBuffer-literalCount);
 297           else outputCodePair(literalmatch.pos, literalCount, inBuffer-literalCount);
 298         }
 299         literalCount = 0;
 300       }
 301       /* output match */
 302       outputCodePair(match.pos, match.len, inBuffer);
 303       inBuffer += match.len;
 304       pos += match.len;
 305     } else {
 306       /* check if we are allready collecting literals */
 307       if (literalCount != 0) {
 308         /* if so, continue.. */
 309         ++literalCount;
 310         /* have we collected as many as possible? */
 311         if (literalCount == literalmatch.len) {
 312           outputCodePair(literalmatch.pos, literalCount, inBuffer-literalCount+1);
 313           literalCount = 0;
 314         }
 315       } else {
 316         /* if we had a match which was not good enough, then save it.. */
 317         if (match.len != 0) {
 318           literalmatch.len = match.len;
 319           literalmatch.pos = match.pos;
 320           ++literalCount;
 321         } else {
 322           /* if not, we have to output the literal now */
 323           outputLiteral(inBuffer[0]);
 324         }
 325       }
 326       ++inBuffer;
 327       ++pos;
 328     }
 329   }
 330   /* output any remaining literal bytes */
 331   if (literalCount != 0) {
 332     if (literalCount == 1) outputLiteral(inBuffer[-1]);
 333     else outputCodePair(literalmatch.pos, literalCount, inBuffer-literalCount);
 334   }
 335   /* switch last tagByte into position */
 336   if (bitCount != 8) *tagByte <<= bitCount;
 337   //
 338   free(lookup);
 339   free(backTable);
 340   return bytesOut;
 341 }
 342 #endif
 343
 344
 345 #ifndef WDX_EXCLUDE_UNPACKER
 346 int wdxUnpack (void *bufOut, int outSize, const void *bufIn, int inSize) {
 347   const uint8_t *src = (const uint8_t *)bufIn;
 348   uint8_t *dest = (uint8_t *)bufOut, *pp;
 349   uint8_t fbyte = 0;
 350   int lastMatchPos = 0, lastWasMatch = 0, len, pos, b, bCount = 0, origOutSz = outSize;
 351   jmp_buf errJP;
 352   int itsOk = 0;
 353
 354   int getBit (void) {
 355     int res;
 356     //
 357     if (bCount <= 0) {
 358       if (inSize < 1) WDXFatalError();
 359       fbyte = *src++;
 360       --inSize;
 361       bCount = 8;
 362     }
 363     res = (fbyte&0x80)!=0 ? 1 : 0;
 364     fbyte = (fbyte&0x7f)<<1;
 365     --bCount;
 366     return res;
 367   }
 368
 369   int getGamma (void) {
 370     int res = 1;
 371     //
 372     do {
 373       res = (res<<1)|getBit();
 374     } while (getBit() == 1);
 375     return res;
 376   }
 377
 378   /* get 6 low bits of position */
 379   int getLoPos (int pos) {
 380     for (int f = 0; f < 6; ++f) pos = (pos<<1)|getBit();
 381     return pos;
 382   }
 383
 384   /* main code */
 385   if (outSize < 1) return 0;
 386   if (inSize < 1) return -1; /* out of input data */
 387
 388   if (setjmp(errJP)) {
 389     /* decompressing error */
 390     if (!itsOk) return -1;
 391     return origOutSz-outSize;
 392   }
 393
 394   /* the first byte was sent verbatim */
 395   *dest++ = *src++;
 396   --inSize;
 397   --outSize;
 398   while (outSize > 0) {
 399     itsOk = 1;
 400     b = getBit();
 401     itsOk = 0;
 402     if (b == 0) {
 403       /* literal */
 404       if (inSize < 1) break;
 405       *dest++ = *src++;
 406       --inSize;
 407       --outSize;
 408       lastWasMatch = 0;
 409     } else {
 410       /* match */
 411       len = getGamma();
 412       if (lastWasMatch) {
 413         pos = getGamma()-2;
 414         pos = getLoPos(pos)+1;
 415         lastMatchPos = pos;
 416         if (pos > WDXUNPACK_LEN2_LIMIT) ++len;
 417       } else {
 418         lastWasMatch = 1;
 419         pos = getGamma()-2;
 420         /* same position as last match? */
 421         if (pos == 0) pos = lastMatchPos;
 422         else {
 423           pos = getLoPos(pos-1)+1;
 424           lastMatchPos = pos;
 425           if (pos > WDXUNPACK_LEN2_LIMIT) ++len;
 426         }
 427       }
 428       /* copy match */
 429       pp = dest-pos;
 430       if ((void *)pp < (void *)bufOut) return -1; /* shit! */
 431       for (; len > 0 && outSize > 0; --outSize, --len) *dest++ = *pp++;
 432     }
 433   }
 434   return origOutSz-outSize;
 435 }
 436 #endif