hphp/runtime/ext/zlib/quicklz.inc

   1 // Fast data compression library
   2 // Copyright (C) 2006-2009 Lasse Mikkel Reinhold
   3 // lar@quicklz.com
   4 //
   5 // QuickLZ can be used for free under the GPL-1 or GPL-2 license (where anything
   6 // released into public must be open source) or under a commercial license if such
   7 // has been acquired (see http://www.quicklz.com/order.html). The commercial license
   8 // does not cover derived or ported versions created by third parties under GPL.
   9
  10 // BETA VERSION BETA VERSION BETA VERSION BETA VERSION BETA VERSION BETA VERSION BETA VERSION BETA VERSION BETA VERSION BETA VERSION BETA VERSION
  11 // BETA VERSION BETA VERSION BETA VERSION BETA VERSION BETA VERSION BETA VERSION BETA VERSION BETA VERSION BETA VERSION BETA VERSION BETA VERSION
  12 // BETA VERSION BETA VERSION BETA VERSION BETA VERSION BETA VERSION BETA VERSION BETA VERSION BETA VERSION BETA VERSION BETA VERSION BETA VERSION
  13 // BETA VERSION BETA VERSION BETA VERSION BETA VERSION BETA VERSION BETA VERSION BETA VERSION BETA VERSION BETA VERSION BETA VERSION BETA VERSION
  14 // BETA VERSION BETA VERSION BETA VERSION BETA VERSION BETA VERSION BETA VERSION BETA VERSION BETA VERSION BETA VERSION BETA VERSION BETA VERSION
  15
  16 // 1.5.0 BETA 2
  17
  18 #include "quicklz.h"
  19
  20 #if QLZ_VERSION_MAJOR != 1 || QLZ_VERSION_MINOR != 5 || QLZ_VERSION_REVISION != 0
  21         #error quicklz.c and quicklz.h have different versions
  22 #endif
  23
  24 #if (defined(__X86__) || defined(__i386__) || defined(i386) || defined(_M_IX86) || defined(__386__) || defined(__x86_64__) || defined(_M_X64))
  25         #define X86X64
  26 #endif
  27
  28 #define MINOFFSET 2
  29 #define UNCONDITIONAL_MATCHLEN 6
  30 #define UNCOMPRESSED_END 4
  31 #define CWORD_LEN 4
  32
  33 #ifdef CAST
  34 #undef CAST
  35 #undef OFFSET_BASE
  36 #endif
  37
  38 #if QLZ_COMPRESSION_LEVEL == 1 && defined QLZ_PTR_64 && QLZ_STREAMING_BUFFER == 0
  39         #define OFFSET_BASE source
  40         #define CAST (ui32)(size_t)
  41 #else
  42         #define OFFSET_BASE 0
  43         #define CAST
  44 #endif
  45
  46 int qlz_get_setting(int setting)
  47 {
  48         switch (setting)
  49         {
  50                 case 0: return QLZ_COMPRESSION_LEVEL;
  51                 case 1: return sizeof(qlz_state_compress);
  52                 case 2: return sizeof(qlz_state_decompress);
  53                 case 3: return QLZ_STREAMING_BUFFER;
  54 #ifdef QLZ_MEMORY_SAFE
  55                 case 6: return 1;
  56 #else
  57                 case 6: return 0;
  58 #endif
  59                 case 7: return QLZ_VERSION_MAJOR;
  60                 case 8: return QLZ_VERSION_MINOR;
  61                 case 9: return QLZ_VERSION_REVISION;
  62         }
  63         return -1;
  64 }
  65
  66 #if QLZ_COMPRESSION_LEVEL == 1
  67 static int same(const unsigned char *src, size_t n)
  68 {
  69         while(n > 0 && *(src + n) == *src)
  70                 n--;
  71         return n == 0 ? 1 : 0;
  72 }
  73 #endif
  74
  75 static void reset_table_compress(qlz_state_compress *state)
  76 {
  77         int i;
  78         for(i = 0; i < QLZ_HASH_VALUES; i++)
  79         {
  80 #if QLZ_COMPRESSION_LEVEL == 1
  81                 state->hash[i].offset = 0;
  82 #else
  83                 state->hash_counter[i] = 0;
  84 #endif
  85         }
  86 }
  87
  88 static void reset_table_decompress(qlz_state_decompress *state)
  89 {
  90         int i;
  91         (void)state;
  92         (void)i;
  93 #if QLZ_COMPRESSION_LEVEL == 2
  94         for(i = 0; i < QLZ_HASH_VALUES; i++)
  95         {
  96                 state->hash_counter[i] = 0;
  97         }
  98 #endif
  99 }
 100
 101 static __inline ui32 hash_func(ui32 i)
 102 {
 103 #if QLZ_COMPRESSION_LEVEL == 2
 104         return ((i >> 9) ^ (i >> 13) ^ i) & (QLZ_HASH_VALUES - 1);
 105 #else
 106         return ((i >> 12) ^ i) & (QLZ_HASH_VALUES - 1);
 107 #endif
 108 }
 109
 110 static __inline ui32 fast_read(void const *src, ui32 bytes)
 111 {
 112 #ifndef X86X64
 113         unsigned char *p = (unsigned char*)src;
 114         switch (bytes)
 115         {
 116                 case 4:
 117                         return(*p | *(p + 1) << 8 | *(p + 2) << 16 | *(p + 3) << 24);
 118                 case 3:
 119                         return(*p | *(p + 1) << 8 | *(p + 2) << 16);
 120                 case 2:
 121                         return(*p | *(p + 1) << 8);
 122                 case 1:
 123                         return(*p);
 124         }
 125         return 0;
 126 #else
 127         if (bytes >= 1 && bytes <= 4)
 128                 return *((ui32*)src);
 129         else
 130                 return 0;
 131 #endif
 132 }
 133
 134 static __inline ui32 hashat(const unsigned char *src)
 135 {
 136         ui32 fetch, hash;
 137         fetch = fast_read(src, 3);
 138         hash = hash_func(fetch);
 139         return hash;
 140 }
 141
 142 static __inline void fast_write(ui32 f, void *dst, size_t bytes)
 143 {
 144 #ifndef X86X64
 145         unsigned char *p = (unsigned char*)dst;
 146
 147         switch (bytes)
 148         {
 149                 case 4:
 150                         *p = (unsigned char)f;
 151                         *(p + 1) = (unsigned char)(f >> 8);
 152                         *(p + 2) = (unsigned char)(f >> 16);
 153                         *(p + 3) = (unsigned char)(f >> 24);
 154                         return;
 155                 case 3:
 156                         *p = (unsigned char)f;
 157                         *(p + 1) = (unsigned char)(f >> 8);
 158                         *(p + 2) = (unsigned char)(f >> 16);
 159                         return;
 160                 case 2:
 161                         *p = (unsigned char)f;
 162                         *(p + 1) = (unsigned char)(f >> 8);
 163                         return;
 164                 case 1:
 165                         *p = (unsigned char)f;
 166                         return;
 167         }
 168 #else
 169         switch (bytes)
 170         {
 171                 case 4:
 172                         *((ui32*)dst) = f;
 173                         return;
 174                 case 3:
 175                         *((ui32*)dst) = f;
 176                         return;
 177                 case 2:
 178                         *((ui16 *)dst) = (ui16)f;
 179                         return;
 180                 case 1:
 181                         *((unsigned char*)dst) = (unsigned char)f;
 182                         return;
 183         }
 184 #endif
 185 }
 186
 187
 188 size_t qlz_size_decompressed(const char *source)
 189 {
 190         ui32 n, r;
 191         n = (((*source) & 2) == 2) ? 4 : 1;
 192         r = fast_read(source + 1 + n, n);
 193         r = r & (0xffffffff >> ((4 - n)*8));
 194         return r;
 195 }
 196
 197 size_t qlz_size_compressed(const char *source)
 198 {
 199         ui32 n, r;
 200         n = (((*source) & 2) == 2) ? 4 : 1;
 201         r = fast_read(source + 1, n);
 202         r = r & (0xffffffff >> ((4 - n)*8));
 203         return r;
 204 }
 205
 206 size_t qlz_size_header(const char *source)
 207 {
 208         size_t n = 2*((((*source) & 2) == 2) ? 4 : 1) + 1;
 209         return n;
 210 }
 211
 212
 213 static __inline void memcpy_up(unsigned char *dst, const unsigned char *src, ui32 n)
 214 {
 215         // Caution if modifying memcpy_up! Overlap of dst and src must be special handled.
 216 #ifndef X86X64
 217         unsigned char *end = dst + n;
 218         while(dst < end)
 219         {
 220                 *dst = *src;
 221                 dst++;
 222                 src++;
 223         }
 224 #else
 225         ui32 f = 0;
 226         do
 227         {
 228                 *(ui32 *)(dst + f) = *(ui32 *)(src + f);
 229                 f += MINOFFSET + 1;
 230         }
 231         while (f < n);
 232 #endif
 233 }
 234
 235 static __inline void update_hash(qlz_state_decompress *state, const unsigned char *s)
 236 {
 237 #if QLZ_COMPRESSION_LEVEL == 1
 238         ui32 hash;
 239         hash = hashat(s);
 240         state->hash[hash].offset = s;
 241         state->hash_counter[hash] = 1;
 242 #elif QLZ_COMPRESSION_LEVEL == 2
 243         ui32 hash;
 244         unsigned char c;
 245         hash = hashat(s);
 246         c = state->hash_counter[hash];
 247         state->hash[hash].offset[c & (QLZ_POINTERS - 1)] = s;
 248         c++;
 249         state->hash_counter[hash] = c;
 250 #endif
 251         (void)state;
 252         (void)s;
 253 }
 254
 255 #if QLZ_COMPRESSION_LEVEL <= 2
 256 static void update_hash_upto(qlz_state_decompress *state, unsigned char **lh, const unsigned char *max)
 257 {
 258         while(*lh < max)
 259         {
 260                 (*lh)++;
 261                 update_hash(state, *lh);
 262         }
 263 }
 264 #endif
 265
 266 static size_t qlz_compress_core(const unsigned char *source, unsigned char *destination, size_t size, qlz_state_compress *state)
 267 {
 268         const unsigned char *last_byte = source + size - 1;
 269         const unsigned char *src = source;
 270         unsigned char *cword_ptr = destination;
 271         unsigned char *dst = destination + CWORD_LEN;
 272         ui32 cword_val = 1U << 31;
 273         const unsigned char *last_matchstart = last_byte - UNCONDITIONAL_MATCHLEN - UNCOMPRESSED_END;
 274         ui32 fetch = 0;
 275         unsigned int lits = 0;
 276
 277         (void) lits;
 278
 279         if(src <= last_matchstart)
 280                 fetch = fast_read(src, 3);
 281
 282         while(src <= last_matchstart)
 283         {
 284                 if ((cword_val & 1) == 1)
 285                 {
 286                         // store uncompressed if compression ratio is too low
 287                         if (src > source + (size >> 1) && dst - destination > src - source - ((src - source) >> 5))
 288                                 return 0;
 289
 290                         fast_write((cword_val >> 1) | (1U << 31), cword_ptr, CWORD_LEN);
 291
 292                         cword_ptr = dst;
 293                         dst += CWORD_LEN;
 294                         cword_val = 1U << 31;
 295                         fetch = fast_read(src, 3);
 296                 }
 297 #if QLZ_COMPRESSION_LEVEL == 1
 298                 {
 299                         const unsigned char *o;
 300                         ui32 hash, cached;
 301
 302                         hash = hash_func(fetch);
 303                         cached = fetch ^ state->hash[hash].cache;
 304                         state->hash[hash].cache = fetch;
 305
 306                         o = state->hash[hash].offset + OFFSET_BASE;
 307                         state->hash[hash].offset = CAST(src - OFFSET_BASE);
 308
 309 #ifdef X86X64
 310                         if ((cached & 0xffffff) == 0 && o != OFFSET_BASE && (src - o > MINOFFSET || (src == o + 1 && lits >= 3 && src > source + 3 && same(src - 3, 6))))
 311                         {
 312                                 if(cached != 0)
 313                                 {
 314 #else
 315                         if (cached == 0 && o != OFFSET_BASE && (src - o > MINOFFSET || (src == o + 1 && lits >= 3 && src > source + 3 && same(src - 3, 6))))
 316                         {
 317                                 if (*(o + 3) != *(src + 3))
 318                                 {
 319 #endif
 320                                         hash <<= 4;
 321                                         cword_val = (cword_val >> 1) | (1U << 31);
 322                                         fast_write((3 - 2) | hash, dst, 2);
 323                                         src += 3;
 324                                         dst += 2;
 325                                 }
 326                                 else
 327                                 {
 328                                         const unsigned char *old_src = src;
 329                                         size_t matchlen;
 330                                         hash <<= 4;
 331
 332                                         cword_val = (cword_val >> 1) | (1U << 31);
 333                                         src += 4;
 334
 335                                         if(*(o + (src - old_src)) == *src)
 336                                         {
 337                                                 src++;
 338                                                 if(*(o + (src - old_src)) == *src)
 339                                                 {
 340                                                         size_t q = last_byte - UNCOMPRESSED_END - (src - 5) + 1;
 341                                                         size_t remaining = q > 255 ? 255 : q;
 342                                                         src++;
 343                                                         while(*(o + (src - old_src)) == *src && (size_t)(src - old_src) < remaining)
 344                                                                 src++;
 345                                                 }
 346                                         }
 347
 348                                         matchlen = src - old_src;
 349                                         if (matchlen < 18)
 350                                         {
 351                                                 fast_write((ui32)(matchlen - 2) | hash, dst, 2);
 352                                                 dst += 2;
 353                                         }
 354                                         else
 355                                         {
 356                                                 fast_write((ui32)(matchlen << 16) | hash, dst, 3);
 357                                                 dst += 3;
 358                                         }
 359                                 }
 360                                 fetch = fast_read(src, 3);
 361                                 lits = 0;
 362                         }
 363                         else
 364                         {
 365                                 lits++;
 366                                 *dst = *src;
 367                                 src++;
 368                                 dst++;
 369                                 cword_val = (cword_val >> 1);
 370 #ifdef X86X64
 371                                 fetch = fast_read(src, 3);
 372 #else
 373                                 fetch = (fetch >> 8 & 0xffff) | (*(src + 2) << 16);
 374 #endif
 375                         }
 376                 }
 377 #elif QLZ_COMPRESSION_LEVEL >= 2
 378                 {
 379                         const unsigned char *o, *offset2;
 380                         ui32 hash, matchlen, k, m, best_k = 0;
 381                         unsigned char c;
 382                         size_t remaining = (last_byte - UNCOMPRESSED_END - src + 1) > 255 ? 255 : (last_byte - UNCOMPRESSED_END - src + 1);
 383                         (void)best_k;
 384
 385
 386                         //hash = hashat(src);
 387                         fetch = fast_read(src, 3);
 388                         hash = hash_func(fetch);
 389
 390                         c = state->hash_counter[hash];
 391
 392                         offset2 = state->hash[hash].offset[0];
 393                         if(offset2 < src - MINOFFSET && c > 0 && ((fast_read(offset2, 3) ^ fetch) & 0xffffff) == 0)
 394                         {
 395                                 matchlen = 3;
 396                                 if(*(offset2 + matchlen) == *(src + matchlen))
 397                                 {
 398                                         matchlen = 4;
 399                                         while(*(offset2 + matchlen) == *(src + matchlen) && matchlen < remaining)
 400                                                 matchlen++;
 401                                 }
 402                         }
 403                         else
 404                                 matchlen = 0;
 405                         for(k = 1; k < QLZ_POINTERS && c > k; k++)
 406                         {
 407                                 o = state->hash[hash].offset[k];
 408 #if QLZ_COMPRESSION_LEVEL == 3
 409                                 if(((fast_read(o, 3) ^ fetch) & 0xffffff) == 0 && o < src - MINOFFSET)
 410 #elif QLZ_COMPRESSION_LEVEL == 2
 411                                 if(*(src + matchlen) == *(o + matchlen) && ((fast_read(o, 3) ^ fetch) & 0xffffff) == 0 && o < src - MINOFFSET)
 412 #endif
 413                                 {
 414                                         m = 3;
 415                                         while(*(o + m) == *(src + m) && m < remaining)
 416                                                 m++;
 417 #if QLZ_COMPRESSION_LEVEL == 3
 418                                         if ((m > matchlen) || (m == matchlen && o > offset2))
 419 #elif QLZ_COMPRESSION_LEVEL == 2
 420                                         if (m > matchlen)
 421 #endif
 422                                         {
 423                                                 offset2 = o;
 424                                                 matchlen = m;
 425                                                 best_k = k;
 426                                         }
 427                                 }
 428                         }
 429                         o = offset2;
 430                         state->hash[hash].offset[c & (QLZ_POINTERS - 1)] = src;
 431                         c++;
 432                         state->hash_counter[hash] = c;
 433
 434 #if QLZ_COMPRESSION_LEVEL == 3
 435                         if(matchlen > 2 && src - o < 131071)
 436                         {
 437                                 ui32 u;
 438                                 size_t offset = src - o;
 439
 440                                 for(u = 1; u < matchlen; u++)
 441                                 {
 442                                         hash = hashat(src + u);
 443                                         c = state->hash_counter[hash]++;
 444                                         state->hash[hash].offset[c & (QLZ_POINTERS - 1)] = src + u;
 445                                 }
 446
 447                                 cword_val = (cword_val >> 1) | (1U << 31);
 448                                 src += matchlen;
 449
 450                                 if(matchlen == 3 && offset <= 63)
 451                                 {
 452                                         *dst = (unsigned char)(offset << 2);
 453                                         dst++;
 454                                 }
 455                                 else if (matchlen == 3 && offset <= 16383)
 456                                 {
 457                                         ui32 f = (ui32)((offset << 2) | 1);
 458                                         fast_write(f, dst, 2);
 459                                         dst += 2;
 460                                 }
 461                                 else if (matchlen <= 18 && offset <= 1023)
 462                                 {
 463                                         ui32 f = ((matchlen - 3) << 2) | ((ui32)offset << 6) | 2;
 464                                         fast_write(f, dst, 2);
 465                                         dst += 2;
 466                                 }
 467
 468                                 else if(matchlen <= 33)
 469                                 {
 470                                         ui32 f = ((matchlen - 2) << 2) | ((ui32)offset << 7) | 3;
 471                                         fast_write(f, dst, 3);
 472                                         dst += 3;
 473                                 }
 474                                 else
 475                                 {
 476                                         ui32 f = ((matchlen - 3) << 7) | ((ui32)offset << 15) | 3;
 477                                         fast_write(f, dst, 4);
 478                                         dst += 4;
 479                                 }
 480                         }
 481                         else
 482                         {
 483                                 *dst = *src;
 484                                 src++;
 485                                 dst++;
 486                                 cword_val = (cword_val >> 1);
 487                         }
 488 #elif QLZ_COMPRESSION_LEVEL == 2
 489
 490                         if(matchlen > 2)
 491                         {
 492                                 cword_val = (cword_val >> 1) | (1U << 31);
 493                                 src += matchlen;
 494
 495                                 if (matchlen < 10)
 496                                 {
 497                                         ui32 f = best_k | ((matchlen - 2) << 2) | (hash << 5);
 498                                         fast_write(f, dst, 2);
 499                                         dst += 2;
 500                                 }
 501                                 else
 502                                 {
 503                                         ui32 f = best_k | (matchlen << 16) | (hash << 5);
 504                                         fast_write(f, dst, 3);
 505                                         dst += 3;
 506                                 }
 507                         }
 508                         else
 509                         {
 510                                 *dst = *src;
 511                                 src++;
 512                                 dst++;
 513                                 cword_val = (cword_val >> 1);
 514                         }
 515 #endif
 516                 }
 517 #endif
 518         }
 519         while (src <= last_byte)
 520         {
 521                 if ((cword_val & 1) == 1)
 522                 {
 523                         fast_write((cword_val >> 1) | (1U << 31), cword_ptr, CWORD_LEN);
 524                         cword_ptr = dst;
 525                         dst += CWORD_LEN;
 526                         cword_val = 1U << 31;
 527                 }
 528 #if QLZ_COMPRESSION_LEVEL < 3
 529                 if (src <= last_byte - 3)
 530                 {
 531 #if QLZ_COMPRESSION_LEVEL == 1
 532                         ui32 hash, fetch;
 533                         fetch = fast_read(src, 3);
 534                         hash = hash_func(fetch);
 535                         state->hash[hash].offset = CAST(src - OFFSET_BASE);
 536                         state->hash[hash].cache = fetch;
 537 #elif QLZ_COMPRESSION_LEVEL == 2
 538                         ui32 hash;
 539                         unsigned char c;
 540                         hash = hashat(src);
 541                         c = state->hash_counter[hash];
 542                         state->hash[hash].offset[c & (QLZ_POINTERS - 1)] = src;
 543                         c++;
 544                         state->hash_counter[hash] = c;
 545 #endif
 546                 }
 547 #endif
 548                 *dst = *src;
 549                 src++;
 550                 dst++;
 551                 cword_val = (cword_val >> 1);
 552         }
 553
 554         while((cword_val & 1) != 1)
 555                 cword_val = (cword_val >> 1);
 556
 557         fast_write((cword_val >> 1) | (1U << 31), cword_ptr, CWORD_LEN);
 558
 559         // min. size must be 9 bytes so that the qlz_size functions can take 9 bytes as argument
 560         return dst - destination < 9 ? 9 : dst - destination;
 561 }
 562
 563 static size_t qlz_decompress_core(const unsigned char *source, unsigned char *destination, size_t size, qlz_state_decompress *state, const unsigned char *history)
 564 {
 565         const unsigned char *src = source + qlz_size_header((const char *)source);
 566         unsigned char *dst = destination;
 567         const unsigned char *last_destination_byte = destination + size - 1;
 568         ui32 cword_val = 1;
 569         const unsigned char *last_matchstart = last_destination_byte - UNCONDITIONAL_MATCHLEN - UNCOMPRESSED_END;
 570         unsigned char *last_hashed = destination - 1;
 571         const unsigned char *last_source_byte = source + qlz_size_compressed((const char *)source) - 1;
 572         static const ui32 bitlut[16] = {4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0};
 573
 574         (void) last_source_byte;
 575         (void) last_hashed;
 576         (void) state;
 577         (void) history;
 578
 579         for(;;)
 580         {
 581                 ui32 fetch;
 582
 583                 if (cword_val == 1)
 584                 {
 585 #ifdef QLZ_MEMORY_SAFE
 586                         if(src + CWORD_LEN - 1 > last_source_byte)
 587                                 return 0;
 588 #endif
 589                         cword_val = fast_read(src, CWORD_LEN);
 590                         src += CWORD_LEN;
 591                 }
 592
 593 #ifdef QLZ_MEMORY_SAFE
 594                         if(src + 4 - 1 > last_source_byte)
 595                                 return 0;
 596 #endif
 597
 598                 fetch = fast_read(src, 4);
 599
 600                 if ((cword_val & 1) == 1)
 601                 {
 602                         ui32 matchlen;
 603                         const unsigned char *offset2;
 604
 605 #if QLZ_COMPRESSION_LEVEL == 1
 606                         ui32 hash;
 607                         cword_val = cword_val >> 1;
 608                         hash = (fetch >> 4) & 0xfff;
 609                         offset2 = (const unsigned char *)(size_t)state->hash[hash].offset;
 610
 611                         if((fetch & 0xf) != 0)
 612                         {
 613                                 matchlen = (fetch & 0xf) + 2;
 614                                 src += 2;
 615                         }
 616                         else
 617                         {
 618                                 matchlen = *(src + 2);
 619                                 src += 3;
 620                         }
 621
 622 #elif QLZ_COMPRESSION_LEVEL == 2
 623                         ui32 hash;
 624                         unsigned char c;
 625                         cword_val = cword_val >> 1;
 626                         hash = (fetch >> 5) & 0x7ff;
 627                         c = (unsigned char)(fetch & 0x3);
 628                         offset2 = state->hash[hash].offset[c];
 629
 630                         if((fetch & (28)) != 0)
 631                         {
 632                                 matchlen = ((fetch >> 2) & 0x7) + 2;
 633                                 src += 2;
 634                         }
 635                         else
 636                         {
 637                                 matchlen = *(src + 2);
 638                                 src += 3;
 639                         }
 640
 641 #elif QLZ_COMPRESSION_LEVEL == 3
 642                         ui32 offset;
 643                         cword_val = cword_val >> 1;
 644                         if ((fetch & 3) == 0)
 645                         {
 646                                 offset = (fetch & 0xff) >> 2;
 647                                 matchlen = 3;
 648                                 src++;
 649                         }
 650                         else if ((fetch & 2) == 0)
 651                         {
 652                                 offset = (fetch & 0xffff) >> 2;
 653                                 matchlen = 3;
 654                                 src += 2;
 655                         }
 656                         else if ((fetch & 1) == 0)
 657                         {
 658                                 offset = (fetch & 0xffff) >> 6;
 659                                 matchlen = ((fetch >> 2) & 15) + 3;
 660                                 src += 2;
 661                         }
 662                         else if ((fetch & 127) != 3)
 663                         {
 664                                 offset = (fetch >> 7) & 0x1ffff;
 665                                 matchlen = ((fetch >> 2) & 0x1f) + 2;
 666                                 src += 3;
 667                         }
 668                         else
 669                         {
 670                                 offset = (fetch >> 15);
 671                                 matchlen = ((fetch >> 7) & 255) + 3;
 672                                 src += 4;
 673                         }
 674
 675                         offset2 = dst - offset;
 676 #endif
 677
 678 #ifdef QLZ_MEMORY_SAFE
 679                         if(offset2 < history || offset2 > dst - MINOFFSET - 1)
 680                                 return 0;
 681
 682                         if(matchlen > (ui32)(last_destination_byte - dst - UNCOMPRESSED_END + 1))
 683                                 return 0;
 684 #endif
 685
 686                         memcpy_up(dst, offset2, matchlen);
 687                         dst += matchlen;
 688
 689 #if QLZ_COMPRESSION_LEVEL <= 2
 690                         update_hash_upto(state, &last_hashed, dst - matchlen);
 691                         last_hashed = dst - 1;
 692 #endif
 693                 }
 694                 else
 695                 {
 696                         if (dst < last_matchstart)
 697                         {
 698                                 unsigned int n = bitlut[cword_val & 0xf];
 699 #ifdef X86X64
 700                                 *(ui32 *)dst = *(ui32 *)src;
 701 #else
 702                                 memcpy_up(dst, src, 4);
 703 #endif
 704                                 cword_val = cword_val >> n;
 705                                 dst += n;
 706                                 src += n;
 707 #if QLZ_COMPRESSION_LEVEL <= 2
 708                                 update_hash_upto(state, &last_hashed, dst - 3);
 709 #endif
 710                         }
 711                         else
 712                         {
 713                                 while(dst <= last_destination_byte)
 714                                 {
 715                                         if (cword_val == 1)
 716                                         {
 717                                                 src += CWORD_LEN;
 718                                                 cword_val = 1U << 31;
 719                                         }
 720 #ifdef QLZ_MEMORY_SAFE
 721                                         if(src >= last_source_byte + 1)
 722                                                 return 0;
 723 #endif
 724                                         *dst = *src;
 725                                         dst++;
 726                                         src++;
 727                                         cword_val = cword_val >> 1;
 728                                 }
 729
 730 #if QLZ_COMPRESSION_LEVEL <= 2
 731                                 update_hash_upto(state, &last_hashed, last_destination_byte - 3); // todo, use constant
 732 #endif
 733                                 return size;
 734                         }
 735
 736                 }
 737         }
 738 }
 739
 740 size_t qlz_compress(const void *source, char *destination, size_t size, qlz_state_compress *state)
 741 {
 742         size_t r;
 743         ui32 compressed;
 744         size_t base;
 745
 746         if(size == 0 || size > 0xffffffff - 400)
 747                 return 0;
 748
 749         if(size < 216)
 750                 base = 3;
 751         else
 752                 base = 9;
 753
 754 #if QLZ_STREAMING_BUFFER > 0
 755         if (state->stream_counter + size - 1 >= QLZ_STREAMING_BUFFER)
 756 #endif
 757         {
 758                 reset_table_compress(state);
 759                 r = base + qlz_compress_core((const unsigned char *)source, (unsigned char*)destination + base, size, state);
 760 #if QLZ_STREAMING_BUFFER > 0
 761                 reset_table_compress(state);
 762 #endif
 763                 if(r == base)
 764                 {
 765                         memcpy(destination + base, source, size);
 766                         r = size + base;
 767                         compressed = 0;
 768                 }
 769                 else
 770                 {
 771                         compressed = 1;
 772                 }
 773                 state->stream_counter = 0;
 774         }
 775 #if QLZ_STREAMING_BUFFER > 0
 776         else
 777         {
 778                 unsigned char *src = state->stream_buffer + state->stream_counter;
 779
 780                 memcpy(src, source, size);
 781                 r = base + qlz_compress_core(src, (unsigned char*)destination + base, size, state);
 782
 783                 if(r == base)
 784                 {
 785                         memcpy(destination + base, src, size);
 786                         r = size + base;
 787                         compressed = 0;
 788                         reset_table_compress(state);
 789                 }
 790                 else
 791                 {
 792                         compressed = 1;
 793                 }
 794                 state->stream_counter += size;
 795         }
 796 #endif
 797         if(base == 3)
 798         {
 799                 *destination = (unsigned char)(0 | compressed);
 800                 *(destination + 1) = (unsigned char)r;
 801                 *(destination + 2) = (unsigned char)size;
 802         }
 803         else
 804         {
 805                 *destination = (unsigned char)(2 | compressed);
 806                 fast_write((ui32)r, destination + 1, 4);
 807                 fast_write((ui32)size, destination + 5, 4);
 808         }
 809
 810         *destination |= (QLZ_COMPRESSION_LEVEL << 2);
 811         *destination |= (1 << 6);
 812         *destination |= ((QLZ_STREAMING_BUFFER == 0 ? 0 : (QLZ_STREAMING_BUFFER == 100000 ? 1 : (QLZ_STREAMING_BUFFER == 1000000 ? 2 : 3))) << 4);
 813
 814 // 76543210
 815 // 01SSLLHC
 816
 817         return r;
 818 }
 819
 820 size_t qlz_decompress(const char *source, void *destination, qlz_state_decompress *state)
 821 {
 822         size_t dsiz = qlz_size_decompressed(source);
 823
 824 #if QLZ_STREAMING_BUFFER > 0
 825         if (state->stream_counter + qlz_size_decompressed(source) - 1 >= QLZ_STREAMING_BUFFER)
 826 #endif
 827         {
 828                 if((*source & 1) == 1)
 829                 {
 830                         reset_table_decompress(state);
 831                         dsiz = qlz_decompress_core((const unsigned char *)source, (unsigned char *)destination, dsiz, state, (const unsigned char *)destination);
 832                 }
 833                 else
 834                 {
 835                         memcpy(destination, source + qlz_size_header(source), dsiz);
 836                 }
 837                 state->stream_counter = 0;
 838                 reset_table_decompress(state);
 839         }
 840 #if QLZ_STREAMING_BUFFER > 0
 841         else
 842         {
 843                 unsigned char *dst = state->stream_buffer + state->stream_counter;
 844                 if((*source & 1) == 1)
 845                 {
 846                         dsiz = qlz_decompress_core((const unsigned char *)source, dst, dsiz, state, (const unsigned char *)state->stream_buffer);
 847                 }
 848                 else
 849                 {
 850                         memcpy(dst, source + qlz_size_header(source), dsiz);
 851                         reset_table_decompress(state);
 852                 }
 853                 memcpy(destination, dst, dsiz);
 854                 state->stream_counter += dsiz;
 855         }
 856 #endif
 857         return dsiz;
 858 }