bundles/org.simantics.fastlz/native/fastlz.c

   1 /*
   2   FastLZ - lightning-fast lossless compression library
   3
   4   Copyright (C) 2007 Ariya Hidayat (ariya@kde.org)
   5   Copyright (C) 2006 Ariya Hidayat (ariya@kde.org)
   6   Copyright (C) 2005 Ariya Hidayat (ariya@kde.org)
   7
   8   Permission is hereby granted, free of charge, to any person obtaining a copy
   9   of this software and associated documentation files (the "Software"), to deal
  10   in the Software without restriction, including without limitation the rights
  11   to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  12   copies of the Software, and to permit persons to whom the Software is
  13   furnished to do so, subject to the following conditions:
  14
  15   The above copyright notice and this permission notice shall be included in
  16   all copies or substantial portions of the Software.
  17
  18   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  19   IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  20   FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  21   AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  22   LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  23   OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  24   THE SOFTWARE.
  25 */
  26
  27 #if !defined(FASTLZ__COMPRESSOR) && !defined(FASTLZ_DECOMPRESSOR)
  28
  29 /*
  30  * Always check for bound when decompressing.
  31  * Generally it is best to leave it defined.
  32  */
  33 #define FASTLZ_SAFE
  34
  35 /*
  36  * Give hints to the compiler for branch prediction optimization.
  37  */
  38 #if defined(__GNUC__) && (__GNUC__ > 2)
  39 #define FASTLZ_EXPECT_CONDITIONAL(c)    (__builtin_expect((c), 1))
  40 #define FASTLZ_UNEXPECT_CONDITIONAL(c)  (__builtin_expect((c), 0))
  41 #else
  42 #define FASTLZ_EXPECT_CONDITIONAL(c)    (c)
  43 #define FASTLZ_UNEXPECT_CONDITIONAL(c)  (c)
  44 #endif
  45
  46 /*
  47  * Use inlined functions for supported systems.
  48  */
  49 #if defined(__GNUC__) || defined(__DMC__) || defined(__POCC__) || defined(__WATCOMC__) || defined(__SUNPRO_C)
  50 #define FASTLZ_INLINE inline
  51 #elif defined(__BORLANDC__) || defined(_MSC_VER) || defined(__LCC__)
  52 #define FASTLZ_INLINE __inline
  53 #else
  54 #define FASTLZ_INLINE
  55 #endif
  56
  57 /*
  58  * Prevent accessing more than 8-bit at once, except on x86 architectures.
  59  */
  60 #if !defined(FASTLZ_STRICT_ALIGN)
  61 #define FASTLZ_STRICT_ALIGN
  62 #if defined(__i386__) || defined(__386)  /* GNU C, Sun Studio */
  63 #undef FASTLZ_STRICT_ALIGN
  64 #elif defined(__i486__) || defined(__i586__) || defined(__i686__) /* GNU C */
  65 #undef FASTLZ_STRICT_ALIGN
  66 #elif defined(_M_IX86) /* Intel, MSVC */
  67 #undef FASTLZ_STRICT_ALIGN
  68 #elif defined(__386)
  69 #undef FASTLZ_STRICT_ALIGN
  70 #elif defined(_X86_) /* MinGW */
  71 #undef FASTLZ_STRICT_ALIGN
  72 #elif defined(__I86__) /* Digital Mars */
  73 #undef FASTLZ_STRICT_ALIGN
  74 #endif
  75 #endif
  76
  77 /*
  78  * FIXME: use preprocessor magic to set this on different platforms!
  79  */
  80 typedef unsigned char  flzuint8;
  81 typedef unsigned short flzuint16;
  82 typedef unsigned int   flzuint32;
  83
  84 /* prototypes */
  85 int fastlz_compress(const void* input, int length, void* output);
  86 int fastlz_compress_level(int level, const void* input, int length, void* output);
  87 int fastlz_decompress(const void* input, int length, void* output, int maxout);
  88
  89 #define MAX_COPY       32
  90 #define MAX_LEN       264  /* 256 + 8 */
  91 #define MAX_DISTANCE 8192
  92
  93 #if !defined(FASTLZ_STRICT_ALIGN)
  94 #define FASTLZ_READU16(p) *((const flzuint16*)(p))
  95 #else
  96 #define FASTLZ_READU16(p) ((p)[0] | (p)[1]<<8)
  97 #endif
  98
  99 #define HASH_LOG  13
 100 #define HASH_SIZE (1<< HASH_LOG)
 101 #define HASH_MASK  (HASH_SIZE-1)
 102 #define HASH_FUNCTION(v,p) { v = FASTLZ_READU16(p); v ^= FASTLZ_READU16(p+1)^(v>>(16-HASH_LOG));v &= HASH_MASK; }
 103
 104 #undef FASTLZ_LEVEL
 105 #define FASTLZ_LEVEL 1
 106
 107 #undef FASTLZ_COMPRESSOR
 108 #undef FASTLZ_DECOMPRESSOR
 109 #define FASTLZ_COMPRESSOR fastlz1_compress
 110 #define FASTLZ_DECOMPRESSOR fastlz1_decompress
 111 static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void* input, int length, void* output);
 112 static FASTLZ_INLINE int FASTLZ_DECOMPRESSOR(const void* input, int length, void* output, int maxout);
 113 #include "fastlz.c"
 114
 115 #undef FASTLZ_LEVEL
 116 #define FASTLZ_LEVEL 2
 117
 118 #undef MAX_DISTANCE
 119 #define MAX_DISTANCE 8191
 120 #define MAX_FARDISTANCE (65535+MAX_DISTANCE-1)
 121
 122 #undef FASTLZ_COMPRESSOR
 123 #undef FASTLZ_DECOMPRESSOR
 124 #define FASTLZ_COMPRESSOR fastlz2_compress
 125 #define FASTLZ_DECOMPRESSOR fastlz2_decompress
 126 static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void* input, int length, void* output);
 127 static FASTLZ_INLINE int FASTLZ_DECOMPRESSOR(const void* input, int length, void* output, int maxout);
 128 #include "fastlz.c"
 129
 130 int fastlz_compress(const void* input, int length, void* output)
 131 {
 132   /* for short block, choose fastlz1 */
 133   if(length < 65536)
 134     return fastlz1_compress(input, length, output);
 135
 136   /* else... */
 137   return fastlz2_compress(input, length, output);
 138 }
 139
 140 int fastlz_decompress(const void* input, int length, void* output, int maxout)
 141 {
 142   /* magic identifier for compression level */
 143   int level = ((*(const flzuint8*)input) >> 5) + 1;
 144
 145   if(level == 1)
 146     return fastlz1_decompress(input, length, output, maxout);
 147   if(level == 2)
 148     return fastlz2_decompress(input, length, output, maxout);
 149
 150   /* unknown level, trigger error */
 151   return 0;
 152 }
 153
 154 int fastlz_compress_level(int level, const void* input, int length, void* output)
 155 {
 156   if(level == 1)
 157     return fastlz1_compress(input, length, output);
 158   if(level == 2)
 159     return fastlz2_compress(input, length, output);
 160
 161   return 0;
 162 }
 163
 164 #else /* !defined(FASTLZ_COMPRESSOR) && !defined(FASTLZ_DECOMPRESSOR) */
 165
 166 static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void* input, int length, void* output)
 167 {
 168   const flzuint8* ip = (const flzuint8*) input;
 169   const flzuint8* ip_bound = ip + length - 2;
 170   const flzuint8* ip_limit = ip + length - 12;
 171   flzuint8* op = (flzuint8*) output;
 172
 173   const flzuint8* htab[HASH_SIZE];
 174   const flzuint8** hslot;
 175   flzuint32 hval;
 176
 177   flzuint32 copy;
 178
 179   /* sanity check */
 180   if(FASTLZ_UNEXPECT_CONDITIONAL(length < 4))
 181   {
 182     if(length)
 183     {
 184       /* create literal copy only */
 185       *op++ = length-1;
 186       ip_bound++;
 187       while(ip <= ip_bound)
 188         *op++ = *ip++;
 189       return length+1;
 190     }
 191     else
 192       return 0;
 193   }
 194
 195   /* initializes hash table */
 196   for (hslot = htab; hslot < htab + HASH_SIZE; hslot++)
 197     *hslot = ip;
 198
 199   /* we start with literal copy */
 200   copy = 2;
 201   *op++ = MAX_COPY-1;
 202   *op++ = *ip++;
 203   *op++ = *ip++;
 204
 205   /* main loop */
 206   while(FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit))
 207   {
 208     const flzuint8* ref;
 209     flzuint32 distance;
 210
 211     /* minimum match length */
 212     flzuint32 len = 3;
 213
 214     /* comparison starting-point */
 215     const flzuint8* anchor = ip;
 216
 217     /* check for a run */
 218 #if FASTLZ_LEVEL==2
 219     if(ip[0] == ip[-1] && FASTLZ_READU16(ip-1)==FASTLZ_READU16(ip+1))
 220     {
 221       distance = 1;
 222       ip += 3;
 223       ref = anchor - 1 + 3;
 224       goto match;
 225     }
 226 #endif
 227
 228     /* find potential match */
 229     HASH_FUNCTION(hval,ip);
 230     hslot = htab + hval;
 231     ref = htab[hval];
 232
 233     /* calculate distance to the match */
 234     distance = anchor - ref;
 235
 236     /* update hash table */
 237     *hslot = anchor;
 238
 239     /* is this a match? check the first 3 bytes */
 240     if(distance==0 ||
 241 #if FASTLZ_LEVEL==1
 242     (distance >= MAX_DISTANCE) ||
 243 #else
 244     (distance >= MAX_FARDISTANCE) ||
 245 #endif
 246     *ref++ != *ip++ || *ref++!=*ip++ || *ref++!=*ip++)
 247       goto literal;
 248
 249 #if FASTLZ_LEVEL==2
 250     /* far, needs at least 5-byte match */
 251     if(distance >= MAX_DISTANCE)
 252     {
 253       if(*ip++ != *ref++ || *ip++!= *ref++)
 254         goto literal;
 255       len += 2;
 256     }
 257
 258     match:
 259 #endif
 260
 261     /* last matched byte */
 262     ip = anchor + len;
 263
 264     /* distance is biased */
 265     distance--;
 266
 267     if(!distance)
 268     {
 269       /* zero distance means a run */
 270       flzuint8 x = ip[-1];
 271       while(ip < ip_bound)
 272         if(*ref++ != x) break; else ip++;
 273     }
 274     else
 275     for(;;)
 276     {
 277       /* safe because the outer check against ip limit */
 278       if(*ref++ != *ip++) break;
 279       if(*ref++ != *ip++) break;
 280       if(*ref++ != *ip++) break;
 281       if(*ref++ != *ip++) break;
 282       if(*ref++ != *ip++) break;
 283       if(*ref++ != *ip++) break;
 284       if(*ref++ != *ip++) break;
 285       if(*ref++ != *ip++) break;
 286       while(ip < ip_bound)
 287         if(*ref++ != *ip++) break;
 288       break;
 289     }
 290
 291     /* if we have copied something, adjust the copy count */
 292     if(copy)
 293       /* copy is biased, '0' means 1 byte copy */
 294       *(op-copy-1) = copy-1;
 295     else
 296       /* back, to overwrite the copy count */
 297       op--;
 298
 299     /* reset literal counter */
 300     copy = 0;
 301
 302     /* length is biased, '1' means a match of 3 bytes */
 303     ip -= 3;
 304     len = ip - anchor;
 305
 306     /* encode the match */
 307 #if FASTLZ_LEVEL==2
 308     if(distance < MAX_DISTANCE)
 309     {
 310       if(len < 7)
 311       {
 312         *op++ = (len << 5) + (distance >> 8);
 313         *op++ = (distance & 255);
 314       }
 315       else
 316       {
 317         *op++ = (7 << 5) + (distance >> 8);
 318         for(len-=7; len >= 255; len-= 255)
 319           *op++ = 255;
 320         *op++ = len;
 321         *op++ = (distance & 255);
 322       }
 323     }
 324     else
 325     {
 326       /* far away, but not yet in the another galaxy... */
 327       if(len < 7)
 328       {
 329         distance -= MAX_DISTANCE;
 330         *op++ = (len << 5) + 31;
 331         *op++ = 255;
 332         *op++ = distance >> 8;
 333         *op++ = distance & 255;
 334       }
 335       else
 336       {
 337         distance -= MAX_DISTANCE;
 338         *op++ = (7 << 5) + 31;
 339         for(len-=7; len >= 255; len-= 255)
 340           *op++ = 255;
 341         *op++ = len;
 342         *op++ = 255;
 343         *op++ = distance >> 8;
 344         *op++ = distance & 255;
 345       }
 346     }
 347 #else
 348
 349     if(FASTLZ_UNEXPECT_CONDITIONAL(len > MAX_LEN-2))
 350       while(len > MAX_LEN-2)
 351       {
 352         *op++ = (7 << 5) + (distance >> 8);
 353         *op++ = MAX_LEN - 2 - 7 -2;
 354         *op++ = (distance & 255);
 355         len -= MAX_LEN-2;
 356       }
 357
 358     if(len < 7)
 359     {
 360       *op++ = (len << 5) + (distance >> 8);
 361       *op++ = (distance & 255);
 362     }
 363     else
 364     {
 365       *op++ = (7 << 5) + (distance >> 8);
 366       *op++ = len - 7;
 367       *op++ = (distance & 255);
 368     }
 369 #endif
 370
 371     /* update the hash at match boundary */
 372     HASH_FUNCTION(hval,ip);
 373     htab[hval] = ip++;
 374     HASH_FUNCTION(hval,ip);
 375     htab[hval] = ip++;
 376
 377     /* assuming literal copy */
 378     *op++ = MAX_COPY-1;
 379
 380     continue;
 381
 382     literal:
 383       *op++ = *anchor++;
 384       ip = anchor;
 385       copy++;
 386       if(FASTLZ_UNEXPECT_CONDITIONAL(copy == MAX_COPY))
 387       {
 388         copy = 0;
 389         *op++ = MAX_COPY-1;
 390       }
 391   }
 392
 393   /* left-over as literal copy */
 394   ip_bound++;
 395   while(ip <= ip_bound)
 396   {
 397     *op++ = *ip++;
 398     copy++;
 399     if(copy == MAX_COPY)
 400     {
 401       copy = 0;
 402       *op++ = MAX_COPY-1;
 403     }
 404   }
 405
 406   /* if we have copied something, adjust the copy length */
 407   if(copy)
 408     *(op-copy-1) = copy-1;
 409   else
 410     op--;
 411
 412 #if FASTLZ_LEVEL==2
 413   /* marker for fastlz2 */
 414   *(flzuint8*)output |= (1 << 5);
 415 #endif
 416
 417   return op - (flzuint8*)output;
 418 }
 419
 420 static FASTLZ_INLINE int FASTLZ_DECOMPRESSOR(const void* input, int length, void* output, int maxout)
 421 {
 422   const flzuint8* ip = (const flzuint8*) input;
 423   const flzuint8* ip_limit  = ip + length;
 424   flzuint8* op = (flzuint8*) output;
 425   flzuint8* op_limit = op + maxout;
 426   flzuint32 ctrl = (*ip++) & 31;
 427   int loop = 1;
 428
 429   do
 430   {
 431     const flzuint8* ref = op;
 432     flzuint32 len = ctrl >> 5;
 433     flzuint32 ofs = (ctrl & 31) << 8;
 434
 435     if(ctrl >= 32)
 436     {
 437 #if FASTLZ_LEVEL==2
 438       flzuint8 code;
 439 #endif
 440       len--;
 441       ref -= ofs;
 442       if (len == 7-1)
 443 #if FASTLZ_LEVEL==1
 444         len += *ip++;
 445       ref -= *ip++;
 446 #else
 447         do
 448         {
 449           code = *ip++;
 450           len += code;
 451         } while (code==255);
 452       code = *ip++;
 453       ref -= code;
 454
 455       /* match from 16-bit distance */
 456       if(FASTLZ_UNEXPECT_CONDITIONAL(code==255))
 457       if(FASTLZ_EXPECT_CONDITIONAL(ofs==(31 << 8)))
 458       {
 459         ofs = (*ip++) << 8;
 460         ofs += *ip++;
 461         ref = op - ofs - MAX_DISTANCE;
 462       }
 463 #endif
 464
 465 #ifdef FASTLZ_SAFE
 466       if (FASTLZ_UNEXPECT_CONDITIONAL(op + len + 3 > op_limit))
 467         return 0;
 468
 469       if (FASTLZ_UNEXPECT_CONDITIONAL(ref-1 < (flzuint8 *)output))
 470         return 0;
 471 #endif
 472
 473       if(FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit))
 474         ctrl = *ip++;
 475       else
 476         loop = 0;
 477
 478       if(ref == op)
 479       {
 480         /* optimize copy for a run */
 481         flzuint8 b = ref[-1];
 482         *op++ = b;
 483         *op++ = b;
 484         *op++ = b;
 485         for(; len; --len)
 486           *op++ = b;
 487       }
 488       else
 489       {
 490 #if !defined(FASTLZ_STRICT_ALIGN)
 491         const flzuint16* p;
 492         flzuint16* q;
 493 #endif
 494         /* copy from reference */
 495         ref--;
 496         *op++ = *ref++;
 497         *op++ = *ref++;
 498         *op++ = *ref++;
 499
 500 #if !defined(FASTLZ_STRICT_ALIGN)
 501         /* copy a byte, so that now it's word aligned */
 502         if(len & 1)
 503         {
 504           *op++ = *ref++;
 505           len--;
 506         }
 507
 508         /* copy 16-bit at once */
 509         q = (flzuint16*) op;
 510         op += len;
 511         p = (const flzuint16*) ref;
 512         for(len>>=1; len > 4; len-=4)
 513         {
 514           *q++ = *p++;
 515           *q++ = *p++;
 516           *q++ = *p++;
 517           *q++ = *p++;
 518         }
 519         for(; len; --len)
 520           *q++ = *p++;
 521 #else
 522         for(; len; --len)
 523           *op++ = *ref++;
 524 #endif
 525       }
 526     }
 527     else
 528     {
 529       ctrl++;
 530 #ifdef FASTLZ_SAFE
 531       if (FASTLZ_UNEXPECT_CONDITIONAL(op + ctrl > op_limit))
 532         return 0;
 533       if (FASTLZ_UNEXPECT_CONDITIONAL(ip + ctrl > ip_limit))
 534         return 0;
 535 #endif
 536
 537       *op++ = *ip++;
 538       for(--ctrl; ctrl; ctrl--)
 539         *op++ = *ip++;
 540
 541       loop = FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit);
 542       if(loop)
 543         ctrl = *ip++;
 544     }
 545   }
 546   while(FASTLZ_EXPECT_CONDITIONAL(loop));
 547
 548   return op - (flzuint8*)output;
 549 }
 550
 551 #endif /* !defined(FASTLZ_COMPRESSOR) && !defined(FASTLZ_DECOMPRESSOR) */