ceph/src/zstd/contrib/long_distance_matching/ldm.c

   1 #include <limits.h>
   2 #include <stdint.h>
   3 #include <stdio.h>
   4 #include <stdlib.h>
   5 #include <string.h>
   6
   7 #include "ldm.h"
   8
   9 #define LDM_HASHTABLESIZE (1 << (LDM_MEMORY_USAGE))
  10 #define LDM_HASHTABLESIZE_U32 ((LDM_HASHTABLESIZE) >> 2)
  11 #define LDM_HASHTABLESIZE_U64 ((LDM_HASHTABLESIZE) >> 3)
  12
  13 #if USE_CHECKSUM
  14   #define LDM_HASH_ENTRY_SIZE_LOG 3
  15 #else
  16   #define LDM_HASH_ENTRY_SIZE_LOG 2
  17 #endif
  18
  19 // Entries are inserted into the table HASH_ONLY_EVERY + 1 times "on average".
  20 #ifndef HASH_ONLY_EVERY_LOG
  21   #define HASH_ONLY_EVERY_LOG (LDM_WINDOW_SIZE_LOG-((LDM_MEMORY_USAGE)-(LDM_HASH_ENTRY_SIZE_LOG)))
  22 #endif
  23
  24 #define HASH_ONLY_EVERY ((1 << (HASH_ONLY_EVERY_LOG)) - 1)
  25
  26 #define HASH_BUCKET_SIZE (1 << (HASH_BUCKET_SIZE_LOG))
  27 #define NUM_HASH_BUCKETS_LOG ((LDM_MEMORY_USAGE)-(LDM_HASH_ENTRY_SIZE_LOG)-(HASH_BUCKET_SIZE_LOG))
  28
  29 #define HASH_CHAR_OFFSET 10
  30
  31 // Take the first match in the hash bucket only.
  32 //#define ZSTD_SKIP
  33
  34 static const U64 prime8bytes = 11400714785074694791ULL;
  35
  36 // Type of the small hash used to index into the hash table.
  37 typedef U32 hash_t;
  38
  39 #if USE_CHECKSUM
  40 typedef struct LDM_hashEntry {
  41   U32 offset;
  42   U32 checksum;
  43 } LDM_hashEntry;
  44 #else
  45 typedef struct LDM_hashEntry {
  46   U32 offset;
  47 } LDM_hashEntry;
  48 #endif
  49
  50 struct LDM_compressStats {
  51   U32 windowSizeLog, hashTableSizeLog;
  52   U32 numMatches;
  53   U64 totalMatchLength;
  54   U64 totalLiteralLength;
  55   U64 totalOffset;
  56
  57   U32 matchLengthHistogram[32];
  58
  59   U32 minOffset, maxOffset;
  60   U32 offsetHistogram[32];
  61 };
  62
  63 typedef struct LDM_hashTable LDM_hashTable;
  64
  65 struct LDM_CCtx {
  66   size_t isize;             /* Input size */
  67   size_t maxOSize;          /* Maximum output size */
  68
  69   const BYTE *ibase;        /* Base of input */
  70   const BYTE *ip;           /* Current input position */
  71   const BYTE *iend;         /* End of input */
  72
  73   // Maximum input position such that hashing at the position does not exceed
  74   // end of input.
  75   const BYTE *ihashLimit;
  76
  77   // Maximum input position such that finding a match of at least the minimum
  78   // match length does not exceed end of input.
  79   const BYTE *imatchLimit;
  80
  81   const BYTE *obase;        /* Base of output */
  82   BYTE *op;                 /* Output */
  83
  84   const BYTE *anchor;       /* Anchor to start of current (match) block */
  85
  86   LDM_compressStats stats;            /* Compression statistics */
  87
  88   LDM_hashTable *hashTable;
  89
  90   const BYTE *lastPosHashed;          /* Last position hashed */
  91   U64 lastHash;
  92
  93   const BYTE *nextIp;                 // TODO: this is redundant (ip + step)
  94   const BYTE *nextPosHashed;
  95   U64 nextHash;
  96
  97   unsigned step;                      // ip step, should be 1.
  98
  99   const BYTE *lagIp;
 100   U64 lagHash;
 101 };
 102
 103 struct LDM_hashTable {
 104   U32 numBuckets;          // The number of buckets.
 105   U32 numEntries;          // numBuckets * HASH_BUCKET_SIZE.
 106
 107   LDM_hashEntry *entries;
 108   BYTE *bucketOffsets;     // A pointer (per bucket) to the next insert position.
 109 };
 110
 111 static void HASH_destroyTable(LDM_hashTable *table) {
 112   free(table->entries);
 113   free(table->bucketOffsets);
 114   free(table);
 115 }
 116
 117 /**
 118  * Create a hash table that can contain size elements.
 119  * The number of buckets is determined by size >> HASH_BUCKET_SIZE_LOG.
 120  *
 121  * Returns NULL if table creation failed.
 122  */
 123 static LDM_hashTable *HASH_createTable(U32 size) {
 124   LDM_hashTable *table = malloc(sizeof(LDM_hashTable));
 125   if (!table) return NULL;
 126
 127   table->numBuckets = size >> HASH_BUCKET_SIZE_LOG;
 128   table->numEntries = size;
 129   table->entries = calloc(size, sizeof(LDM_hashEntry));
 130   table->bucketOffsets = calloc(size >> HASH_BUCKET_SIZE_LOG, sizeof(BYTE));
 131
 132   if (!table->entries || !table->bucketOffsets) {
 133     HASH_destroyTable(table);
 134     return NULL;
 135   }
 136
 137   return table;
 138 }
 139
 140 static LDM_hashEntry *getBucket(const LDM_hashTable *table, const hash_t hash) {
 141   return table->entries + (hash << HASH_BUCKET_SIZE_LOG);
 142 }
 143
 144 static unsigned ZSTD_NbCommonBytes (register size_t val) {
 145   if (MEM_isLittleEndian()) {
 146     if (MEM_64bits()) {
 147 #    if defined(_MSC_VER) && defined(_WIN64)
 148       unsigned long r = 0;
 149       _BitScanForward64( &r, (U64)val );
 150       return (unsigned)(r>>3);
 151 #     elif defined(__GNUC__) && (__GNUC__ >= 3)
 152       return (__builtin_ctzll((U64)val) >> 3);
 153 #     else
 154       static const int DeBruijnBytePos[64] = { 0, 0, 0, 0, 0, 1, 1, 2,
 155                                                0, 3, 1, 3, 1, 4, 2, 7,
 156                                                0, 2, 3, 6, 1, 5, 3, 5,
 157                                                1, 3, 4, 4, 2, 5, 6, 7,
 158                                                7, 0, 1, 2, 3, 3, 4, 6,
 159                                                2, 6, 5, 5, 3, 4, 5, 6,
 160                                                7, 1, 2, 4, 6, 4, 4, 5,
 161                                                7, 2, 6, 5, 7, 6, 7, 7 };
 162       return DeBruijnBytePos[
 163           ((U64)((val & -(long long)val) * 0x0218A392CDABBD3FULL)) >> 58];
 164 #     endif
 165   } else { /* 32 bits */
 166 #     if defined(_MSC_VER)
 167       unsigned long r=0;
 168       _BitScanForward( &r, (U32)val );
 169       return (unsigned)(r>>3);
 170 #     elif defined(__GNUC__) && (__GNUC__ >= 3)
 171       return (__builtin_ctz((U32)val) >> 3);
 172 #     else
 173       static const int DeBruijnBytePos[32] = { 0, 0, 3, 0, 3, 1, 3, 0,
 174                                                3, 2, 2, 1, 3, 2, 0, 1,
 175                                                3, 3, 1, 2, 2, 2, 2, 0,
 176                                                3, 1, 2, 0, 1, 0, 1, 1 };
 177       return DeBruijnBytePos[
 178           ((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];
 179 #     endif
 180     }
 181   } else {  /* Big Endian CPU */
 182     if (MEM_64bits()) {
 183 #     if defined(_MSC_VER) && defined(_WIN64)
 184       unsigned long r = 0;
 185       _BitScanReverse64( &r, val );
 186       return (unsigned)(r>>3);
 187 #     elif defined(__GNUC__) && (__GNUC__ >= 3)
 188       return (__builtin_clzll(val) >> 3);
 189 #     else
 190       unsigned r;
 191       /* calculate this way due to compiler complaining in 32-bits mode */
 192       const unsigned n32 = sizeof(size_t)*4;
 193       if (!(val>>n32)) { r=4; } else { r=0; val>>=n32; }
 194       if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; }
 195       r += (!val);
 196       return r;
 197 #       endif
 198     } else { /* 32 bits */
 199 #     if defined(_MSC_VER)
 200       unsigned long r = 0;
 201       _BitScanReverse( &r, (unsigned long)val );
 202       return (unsigned)(r>>3);
 203 #     elif defined(__GNUC__) && (__GNUC__ >= 3)
 204       return (__builtin_clz((U32)val) >> 3);
 205 #     else
 206       unsigned r;
 207       if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; }
 208       r += (!val);
 209       return r;
 210 #     endif
 211     }
 212   }
 213 }
 214
 215 // From lib/compress/zstd_compress.c
 216 static size_t ZSTD_count(const BYTE *pIn, const BYTE *pMatch,
 217                          const BYTE *const pInLimit) {
 218     const BYTE * const pStart = pIn;
 219     const BYTE * const pInLoopLimit = pInLimit - (sizeof(size_t)-1);
 220
 221     while (pIn < pInLoopLimit) {
 222         size_t const diff = MEM_readST(pMatch) ^ MEM_readST(pIn);
 223         if (!diff) {
 224           pIn += sizeof(size_t);
 225           pMatch += sizeof(size_t);
 226           continue;
 227         }
 228         pIn += ZSTD_NbCommonBytes(diff);
 229         return (size_t)(pIn - pStart);
 230     }
 231
 232     if (MEM_64bits()) {
 233       if ((pIn < (pInLimit - 3)) && (MEM_read32(pMatch) == MEM_read32(pIn))) {
 234         pIn += 4;
 235         pMatch += 4;
 236       }
 237     }
 238     if ((pIn < (pInLimit - 1)) && (MEM_read16(pMatch) == MEM_read16(pIn))) {
 239       pIn += 2;
 240       pMatch += 2;
 241     }
 242     if ((pIn < pInLimit) && (*pMatch == *pIn)) {
 243       pIn++;
 244     }
 245     return (size_t)(pIn - pStart);
 246 }
 247
 248 /**
 249  * Count number of bytes that match backwards before pIn and pMatch.
 250  *
 251  * We count only bytes where pMatch > pBase and pIn > pAnchor.
 252  */
 253 static size_t countBackwardsMatch(const BYTE *pIn, const BYTE *pAnchor,
 254                                   const BYTE *pMatch, const BYTE *pBase) {
 255   size_t matchLength = 0;
 256   while (pIn > pAnchor && pMatch > pBase && pIn[-1] == pMatch[-1]) {
 257     pIn--;
 258     pMatch--;
 259     matchLength++;
 260   }
 261   return matchLength;
 262 }
 263
 264 /**
 265  * Returns a pointer to the entry in the hash table matching the hash and
 266  * checksum with the "longest match length" as defined below. The forward and
 267  * backward match lengths are written to *pForwardMatchLength and
 268  * *pBackwardMatchLength.
 269  *
 270  * The match length is defined based on cctx->ip and the entry's offset.
 271  * The forward match is computed from cctx->ip and entry->offset + cctx->ibase.
 272  * The backward match is computed backwards from cctx->ip and
 273  * cctx->ibase only if the forward match is longer than LDM_MIN_MATCH_LENGTH.
 274  */
 275 static LDM_hashEntry *HASH_getBestEntry(const LDM_CCtx *cctx,
 276                                         const hash_t hash,
 277                                         const U32 checksum,
 278                                         U64 *pForwardMatchLength,
 279                                         U64 *pBackwardMatchLength) {
 280   LDM_hashTable *table = cctx->hashTable;
 281   LDM_hashEntry *bucket = getBucket(table, hash);
 282   LDM_hashEntry *cur;
 283   LDM_hashEntry *bestEntry = NULL;
 284   U64 bestMatchLength = 0;
 285 #if !(USE_CHECKSUM)
 286   (void)checksum;
 287 #endif
 288   for (cur = bucket; cur < bucket + HASH_BUCKET_SIZE; ++cur) {
 289     const BYTE *pMatch = cur->offset + cctx->ibase;
 290
 291     // Check checksum for faster check.
 292 #if USE_CHECKSUM
 293     if (cur->checksum == checksum &&
 294         cctx->ip - pMatch <= LDM_WINDOW_SIZE) {
 295 #else
 296     if (cctx->ip - pMatch <= LDM_WINDOW_SIZE) {
 297 #endif
 298       U64 forwardMatchLength = ZSTD_count(cctx->ip, pMatch, cctx->iend);
 299       U64 backwardMatchLength, totalMatchLength;
 300
 301       // Only take matches where the forward match length is large enough
 302       // for speed.
 303       if (forwardMatchLength < LDM_MIN_MATCH_LENGTH) {
 304         continue;
 305       }
 306
 307       backwardMatchLength =
 308           countBackwardsMatch(cctx->ip, cctx->anchor,
 309                               cur->offset + cctx->ibase,
 310                               cctx->ibase);
 311
 312       totalMatchLength = forwardMatchLength + backwardMatchLength;
 313
 314       if (totalMatchLength >= bestMatchLength) {
 315         bestMatchLength = totalMatchLength;
 316         *pForwardMatchLength = forwardMatchLength;
 317         *pBackwardMatchLength = backwardMatchLength;
 318
 319         bestEntry = cur;
 320 #ifdef ZSTD_SKIP
 321         return cur;
 322 #endif
 323       }
 324     }
 325   }
 326   if (bestEntry != NULL) {
 327     return bestEntry;
 328   }
 329   return NULL;
 330 }
 331
 332 /**
 333  * Insert an entry into the hash table. The table uses a "circular buffer",
 334  * with the oldest entry overwritten.
 335  */
 336 static void HASH_insert(LDM_hashTable *table,
 337                         const hash_t hash, const LDM_hashEntry entry) {
 338   *(getBucket(table, hash) + table->bucketOffsets[hash]) = entry;
 339   table->bucketOffsets[hash]++;
 340   table->bucketOffsets[hash] &= HASH_BUCKET_SIZE - 1;
 341 }
 342
 343 static void HASH_outputTableOccupancy(const LDM_hashTable *table) {
 344   U32 ctr = 0;
 345   LDM_hashEntry *cur = table->entries;
 346   LDM_hashEntry *end = table->entries + (table->numBuckets * HASH_BUCKET_SIZE);
 347   for (; cur < end; ++cur) {
 348     if (cur->offset == 0) {
 349       ctr++;
 350     }
 351   }
 352
 353   // The number of buckets is repeated as a check for now.
 354   printf("Num buckets, bucket size: %d (2^%d), %d\n",
 355          table->numBuckets, NUM_HASH_BUCKETS_LOG, HASH_BUCKET_SIZE);
 356   printf("Hash table size, empty slots, %% empty: %u, %u, %.3f\n",
 357          table->numEntries, ctr,
 358          100.0 * (double)(ctr) / table->numEntries);
 359 }
 360
 361 // TODO: This can be done more efficiently, for example by using builtin
 362 // functions (but it is not that important as it is only used for computing
 363 // stats).
 364 static int intLog2(U64 x) {
 365   int ret = 0;
 366   while (x >>= 1) {
 367     ret++;
 368   }
 369   return ret;
 370 }
 371
 372 void LDM_printCompressStats(const LDM_compressStats *stats) {
 373   printf("=====================\n");
 374   printf("Compression statistics\n");
 375   printf("Window size, hash table size (bytes): 2^%u, 2^%u\n",
 376           stats->windowSizeLog, stats->hashTableSizeLog);
 377   printf("num matches, total match length, %% matched: %u, %llu, %.3f\n",
 378           stats->numMatches,
 379           stats->totalMatchLength,
 380           100.0 * (double)stats->totalMatchLength /
 381               (double)(stats->totalMatchLength + stats->totalLiteralLength));
 382   printf("avg match length: %.1f\n", ((double)stats->totalMatchLength) /
 383                                          (double)stats->numMatches);
 384   printf("avg literal length, total literalLength: %.1f, %llu\n",
 385          ((double)stats->totalLiteralLength) / (double)stats->numMatches,
 386          stats->totalLiteralLength);
 387   printf("avg offset length: %.1f\n",
 388          ((double)stats->totalOffset) / (double)stats->numMatches);
 389   printf("min offset, max offset: %u, %u\n",
 390          stats->minOffset, stats->maxOffset);
 391
 392   printf("\n");
 393   printf("offset histogram | match length histogram\n");
 394   printf("offset/ML, num matches, %% of matches | num matches, %% of matches\n");
 395
 396   {
 397     int i;
 398     int logMaxOffset = intLog2(stats->maxOffset);
 399     for (i = 0; i <= logMaxOffset; i++) {
 400       printf("2^%*d: %10u    %6.3f%% |2^%*d:  %10u    %6.3f \n",
 401              2, i,
 402              stats->offsetHistogram[i],
 403              100.0 * (double) stats->offsetHistogram[i] /
 404                      (double) stats->numMatches,
 405              2, i,
 406              stats->matchLengthHistogram[i],
 407              100.0 * (double) stats->matchLengthHistogram[i] /
 408                      (double) stats->numMatches);
 409     }
 410   }
 411   printf("\n");
 412   printf("=====================\n");
 413 }
 414
 415 /**
 416  * Return the upper (most significant) NUM_HASH_BUCKETS_LOG bits.
 417  */
 418 static hash_t getSmallHash(U64 hash) {
 419   return hash >> (64 - NUM_HASH_BUCKETS_LOG);
 420 }
 421
 422 /**
 423  * Return the 32 bits after the upper NUM_HASH_BUCKETS_LOG bits.
 424  */
 425 static U32 getChecksum(U64 hash) {
 426   return (hash >> (64 - 32 - NUM_HASH_BUCKETS_LOG)) & 0xFFFFFFFF;
 427 }
 428
 429 #if INSERT_BY_TAG
 430 static U32 lowerBitsFromHfHash(U64 hash) {
 431   // The number of bits used so far is NUM_HASH_BUCKETS_LOG + 32.
 432   // So there are 32 - NUM_HASH_BUCKETS_LOG bits left.
 433   // Occasional hashing requires HASH_ONLY_EVERY_LOG bits.
 434   // So if 32 - LDMHASHLOG < HASH_ONLY_EVERY_LOG, just return lower bits
 435   // allowing for reuse of bits.
 436   if (32 - NUM_HASH_BUCKETS_LOG < HASH_ONLY_EVERY_LOG) {
 437     return hash & HASH_ONLY_EVERY;
 438   } else {
 439     // Otherwise shift by
 440     // (32 - NUM_HASH_BUCKETS_LOG - HASH_ONLY_EVERY_LOG) bits first.
 441     return (hash >> (32 - NUM_HASH_BUCKETS_LOG - HASH_ONLY_EVERY_LOG)) &
 442            HASH_ONLY_EVERY;
 443   }
 444 }
 445 #endif
 446
 447 /**
 448  * Get a 64-bit hash using the first len bytes from buf.
 449  *
 450  * Giving bytes s = s_1, s_2, ... s_k, the hash is defined to be
 451  * H(s) = s_1*(a^(k-1)) + s_2*(a^(k-2)) + ... + s_k*(a^0)
 452  *
 453  * where the constant a is defined to be prime8bytes.
 454  *
 455  * The implementation adds an offset to each byte, so
 456  * H(s) = (s_1 + HASH_CHAR_OFFSET)*(a^(k-1)) + ...
 457  */
 458 static U64 getHash(const BYTE *buf, U32 len) {
 459   U64 ret = 0;
 460   U32 i;
 461   for (i = 0; i < len; i++) {
 462     ret *= prime8bytes;
 463     ret += buf[i] + HASH_CHAR_OFFSET;
 464   }
 465   return ret;
 466
 467 }
 468
 469 static U64 ipow(U64 base, U64 exp) {
 470   U64 ret = 1;
 471   while (exp) {
 472     if (exp & 1) {
 473       ret *= base;
 474     }
 475     exp >>= 1;
 476     base *= base;
 477   }
 478   return ret;
 479 }
 480
 481 static U64 updateHash(U64 hash, U32 len,
 482                       BYTE toRemove, BYTE toAdd) {
 483   // TODO: this relies on compiler optimization.
 484   // The exponential can be calculated explicitly as len is constant.
 485   hash -= ((toRemove + HASH_CHAR_OFFSET) *
 486           ipow(prime8bytes, len - 1));
 487   hash *= prime8bytes;
 488   hash += toAdd + HASH_CHAR_OFFSET;
 489   return hash;
 490 }
 491
 492 /**
 493  * Update cctx->nextHash and cctx->nextPosHashed
 494  * based on cctx->lastHash and cctx->lastPosHashed.
 495  *
 496  * This uses a rolling hash and requires that the last position hashed
 497  * corresponds to cctx->nextIp - step.
 498  */
 499 static void setNextHash(LDM_CCtx *cctx) {
 500   cctx->nextHash = updateHash(
 501       cctx->lastHash, LDM_HASH_LENGTH,
 502       cctx->lastPosHashed[0],
 503       cctx->lastPosHashed[LDM_HASH_LENGTH]);
 504   cctx->nextPosHashed = cctx->nextIp;
 505
 506 #if LDM_LAG
 507   if (cctx->ip - cctx->ibase > LDM_LAG) {
 508     cctx->lagHash = updateHash(
 509       cctx->lagHash, LDM_HASH_LENGTH,
 510       cctx->lagIp[0], cctx->lagIp[LDM_HASH_LENGTH]);
 511     cctx->lagIp++;
 512   }
 513 #endif
 514 }
 515
 516 static void putHashOfCurrentPositionFromHash(LDM_CCtx *cctx, U64 hash) {
 517   // Hash only every HASH_ONLY_EVERY times, based on cctx->ip.
 518   // Note: this works only when cctx->step is 1.
 519 #if LDM_LAG
 520   if (cctx -> lagIp - cctx->ibase > 0) {
 521 #if INSERT_BY_TAG
 522     U32 hashEveryMask = lowerBitsFromHfHash(cctx->lagHash);
 523     if (hashEveryMask == HASH_ONLY_EVERY) {
 524 #else
 525     if (((cctx->ip - cctx->ibase) & HASH_ONLY_EVERY) == HASH_ONLY_EVERY) {
 526 #endif
 527       U32 smallHash = getSmallHash(cctx->lagHash);
 528
 529 #   if USE_CHECKSUM
 530       U32 checksum = getChecksum(cctx->lagHash);
 531       const LDM_hashEntry entry = { cctx->lagIp - cctx->ibase, checksum };
 532 #   else
 533       const LDM_hashEntry entry = { cctx->lagIp - cctx->ibase };
 534 #   endif
 535
 536       HASH_insert(cctx->hashTable, smallHash, entry);
 537     }
 538   } else {
 539 #endif // LDM_LAG
 540 #if INSERT_BY_TAG
 541     U32 hashEveryMask = lowerBitsFromHfHash(hash);
 542     if (hashEveryMask == HASH_ONLY_EVERY) {
 543 #else
 544     if (((cctx->ip - cctx->ibase) & HASH_ONLY_EVERY) == HASH_ONLY_EVERY) {
 545 #endif
 546       U32 smallHash = getSmallHash(hash);
 547
 548 #if USE_CHECKSUM
 549       U32 checksum = getChecksum(hash);
 550       const LDM_hashEntry entry = { cctx->ip - cctx->ibase, checksum };
 551 #else
 552       const LDM_hashEntry entry = { cctx->ip - cctx->ibase };
 553 #endif
 554       HASH_insert(cctx->hashTable, smallHash, entry);
 555     }
 556 #if LDM_LAG
 557   }
 558 #endif
 559
 560   cctx->lastPosHashed = cctx->ip;
 561   cctx->lastHash = hash;
 562 }
 563
 564 /**
 565  * Copy over the cctx->lastHash, and cctx->lastPosHashed
 566  * fields from the "next" fields.
 567  *
 568  * This requires that cctx->ip == cctx->nextPosHashed.
 569  */
 570 static void LDM_updateLastHashFromNextHash(LDM_CCtx *cctx) {
 571   putHashOfCurrentPositionFromHash(cctx, cctx->nextHash);
 572 }
 573
 574 /**
 575  * Insert hash of the current position into the hash table.
 576  */
 577 static void LDM_putHashOfCurrentPosition(LDM_CCtx *cctx) {
 578   U64 hash = getHash(cctx->ip, LDM_HASH_LENGTH);
 579
 580   putHashOfCurrentPositionFromHash(cctx, hash);
 581 }
 582
 583 size_t LDM_initializeCCtx(LDM_CCtx *cctx,
 584                           const void *src, size_t srcSize,
 585                           void *dst, size_t maxDstSize) {
 586   cctx->isize = srcSize;
 587   cctx->maxOSize = maxDstSize;
 588
 589   cctx->ibase = (const BYTE *)src;
 590   cctx->ip = cctx->ibase;
 591   cctx->iend = cctx->ibase + srcSize;
 592
 593   cctx->ihashLimit = cctx->iend - LDM_HASH_LENGTH;
 594   cctx->imatchLimit = cctx->iend - LDM_MIN_MATCH_LENGTH;
 595
 596   cctx->obase = (BYTE *)dst;
 597   cctx->op = (BYTE *)dst;
 598
 599   cctx->anchor = cctx->ibase;
 600
 601   memset(&(cctx->stats), 0, sizeof(cctx->stats));
 602 #if USE_CHECKSUM
 603   cctx->hashTable = HASH_createTable(LDM_HASHTABLESIZE_U64);
 604 #else
 605   cctx->hashTable = HASH_createTable(LDM_HASHTABLESIZE_U32);
 606 #endif
 607
 608   if (!cctx->hashTable) return 1;
 609
 610   cctx->stats.minOffset = UINT_MAX;
 611   cctx->stats.windowSizeLog = LDM_WINDOW_SIZE_LOG;
 612   cctx->stats.hashTableSizeLog = LDM_MEMORY_USAGE;
 613
 614   cctx->lastPosHashed = NULL;
 615
 616   cctx->step = 1;   // Fixed to be 1 for now. Changing may break things.
 617   cctx->nextIp = cctx->ip + cctx->step;
 618   cctx->nextPosHashed = 0;
 619
 620   return 0;
 621 }
 622
 623 void LDM_destroyCCtx(LDM_CCtx *cctx) {
 624   HASH_destroyTable(cctx->hashTable);
 625 }
 626
 627 /**
 628  * Finds the "best" match.
 629  *
 630  * Returns 0 if successful and 1 otherwise (i.e. no match can be found
 631  * in the remaining input that is long enough).
 632  *
 633  * forwardMatchLength contains the forward length of the match.
 634  */
 635 static int LDM_findBestMatch(LDM_CCtx *cctx, const BYTE **match,
 636                              U64 *forwardMatchLength, U64 *backwardMatchLength) {
 637
 638   LDM_hashEntry *entry = NULL;
 639   cctx->nextIp = cctx->ip + cctx->step;
 640
 641   while (entry == NULL) {
 642     U64 hash;
 643     hash_t smallHash;
 644     U32 checksum;
 645 #if INSERT_BY_TAG
 646     U32 hashEveryMask;
 647 #endif
 648     setNextHash(cctx);
 649
 650     hash = cctx->nextHash;
 651     smallHash = getSmallHash(hash);
 652     checksum = getChecksum(hash);
 653 #if INSERT_BY_TAG
 654     hashEveryMask = lowerBitsFromHfHash(hash);
 655 #endif
 656
 657     cctx->ip = cctx->nextIp;
 658     cctx->nextIp += cctx->step;
 659
 660     if (cctx->ip > cctx->imatchLimit) {
 661       return 1;
 662     }
 663 #if INSERT_BY_TAG
 664     if (hashEveryMask == HASH_ONLY_EVERY) {
 665
 666       entry = HASH_getBestEntry(cctx, smallHash, checksum,
 667                                 forwardMatchLength, backwardMatchLength);
 668     }
 669 #else
 670     entry = HASH_getBestEntry(cctx, smallHash, checksum,
 671                               forwardMatchLength, backwardMatchLength);
 672 #endif
 673
 674     if (entry != NULL) {
 675       *match = entry->offset + cctx->ibase;
 676     }
 677
 678     putHashOfCurrentPositionFromHash(cctx, hash);
 679
 680   }
 681   setNextHash(cctx);
 682   return 0;
 683 }
 684
 685 void LDM_encodeLiteralLengthAndLiterals(
 686     LDM_CCtx *cctx, BYTE *pToken, const U64 literalLength) {
 687   /* Encode the literal length. */
 688   if (literalLength >= RUN_MASK) {
 689     U64 len = (U64)literalLength - RUN_MASK;
 690     *pToken = (RUN_MASK << ML_BITS);
 691     for (; len >= 255; len -= 255) {
 692       *(cctx->op)++ = 255;
 693     }
 694     *(cctx->op)++ = (BYTE)len;
 695   } else {
 696     *pToken = (BYTE)(literalLength << ML_BITS);
 697   }
 698
 699   /* Encode the literals. */
 700   memcpy(cctx->op, cctx->anchor, literalLength);
 701   cctx->op += literalLength;
 702 }
 703
 704 void LDM_outputBlock(LDM_CCtx *cctx,
 705                      const U64 literalLength,
 706                      const U32 offset,
 707                      const U64 matchLength) {
 708   BYTE *pToken = cctx->op++;
 709
 710   /* Encode the literal length and literals. */
 711   LDM_encodeLiteralLengthAndLiterals(cctx, pToken, literalLength);
 712
 713   /* Encode the offset. */
 714   MEM_write32(cctx->op, offset);
 715   cctx->op += LDM_OFFSET_SIZE;
 716
 717   /* Encode the match length. */
 718   if (matchLength >= ML_MASK) {
 719     U64 matchLengthRemaining = matchLength;
 720     *pToken += ML_MASK;
 721     matchLengthRemaining -= ML_MASK;
 722     MEM_write32(cctx->op, 0xFFFFFFFF);
 723     while (matchLengthRemaining >= 4*0xFF) {
 724       cctx->op += 4;
 725       MEM_write32(cctx->op, 0xffffffff);
 726       matchLengthRemaining -= 4*0xFF;
 727     }
 728     cctx->op += matchLengthRemaining / 255;
 729     *(cctx->op)++ = (BYTE)(matchLengthRemaining % 255);
 730   } else {
 731     *pToken += (BYTE)(matchLength);
 732   }
 733 }
 734
 735 // TODO: maxDstSize is unused. This function may seg fault when writing
 736 // beyond the size of dst, as it does not check maxDstSize. Writing to
 737 // a buffer and performing checks is a possible solution.
 738 //
 739 // This is based upon lz4.
 740 size_t LDM_compress(const void *src, size_t srcSize,
 741                     void *dst, size_t maxDstSize) {
 742   LDM_CCtx cctx;
 743   const BYTE *match = NULL;
 744   U64 forwardMatchLength = 0;
 745   U64 backwardsMatchLength = 0;
 746
 747   if (LDM_initializeCCtx(&cctx, src, srcSize, dst, maxDstSize)) {
 748     // Initialization failed.
 749     return 0;
 750   }
 751
 752 #ifdef OUTPUT_CONFIGURATION
 753   LDM_outputConfiguration();
 754 #endif
 755
 756   /* Hash the first position and put it into the hash table. */
 757   LDM_putHashOfCurrentPosition(&cctx);
 758
 759   cctx.lagIp = cctx.ip;
 760   cctx.lagHash = cctx.lastHash;
 761
 762   /**
 763    * Find a match.
 764    * If no more matches can be found (i.e. the length of the remaining input
 765    * is less than the minimum match length), then stop searching for matches
 766    * and encode the final literals.
 767    */
 768   while (!LDM_findBestMatch(&cctx, &match, &forwardMatchLength,
 769                            &backwardsMatchLength)) {
 770
 771 #ifdef COMPUTE_STATS
 772     cctx.stats.numMatches++;
 773 #endif
 774
 775      cctx.ip -= backwardsMatchLength;
 776      match -= backwardsMatchLength;
 777
 778     /**
 779      * Write current block (literals, literal length, match offset, match
 780      * length) and update pointers and hashes.
 781      */
 782     {
 783       const U64 literalLength = cctx.ip - cctx.anchor;
 784       const U32 offset = cctx.ip - match;
 785       const U64 matchLength = forwardMatchLength +
 786                               backwardsMatchLength -
 787                               LDM_MIN_MATCH_LENGTH;
 788
 789       LDM_outputBlock(&cctx, literalLength, offset, matchLength);
 790
 791 #ifdef COMPUTE_STATS
 792       cctx.stats.totalLiteralLength += literalLength;
 793       cctx.stats.totalOffset += offset;
 794       cctx.stats.totalMatchLength += matchLength + LDM_MIN_MATCH_LENGTH;
 795       cctx.stats.minOffset =
 796           offset < cctx.stats.minOffset ? offset : cctx.stats.minOffset;
 797       cctx.stats.maxOffset =
 798           offset > cctx.stats.maxOffset ? offset : cctx.stats.maxOffset;
 799       cctx.stats.offsetHistogram[(U32)intLog2(offset)]++;
 800       cctx.stats.matchLengthHistogram[
 801           (U32)intLog2(matchLength + LDM_MIN_MATCH_LENGTH)]++;
 802 #endif
 803
 804       // Move ip to end of block, inserting hashes at each position.
 805       cctx.nextIp = cctx.ip + cctx.step;
 806       while (cctx.ip < cctx.anchor + LDM_MIN_MATCH_LENGTH +
 807                        matchLength + literalLength) {
 808         if (cctx.ip > cctx.lastPosHashed) {
 809           // TODO: Simplify.
 810           LDM_updateLastHashFromNextHash(&cctx);
 811           setNextHash(&cctx);
 812         }
 813         cctx.ip++;
 814         cctx.nextIp++;
 815       }
 816     }
 817
 818     // Set start of next block to current input pointer.
 819     cctx.anchor = cctx.ip;
 820     LDM_updateLastHashFromNextHash(&cctx);
 821   }
 822
 823   /* Encode the last literals (no more matches). */
 824   {
 825     const U64 lastRun = cctx.iend - cctx.anchor;
 826     BYTE *pToken = cctx.op++;
 827     LDM_encodeLiteralLengthAndLiterals(&cctx, pToken, lastRun);
 828   }
 829
 830 #ifdef COMPUTE_STATS
 831   LDM_printCompressStats(&cctx.stats);
 832   HASH_outputTableOccupancy(cctx.hashTable);
 833 #endif
 834
 835   {
 836     const size_t ret = cctx.op - cctx.obase;
 837     LDM_destroyCCtx(&cctx);
 838     return ret;
 839   }
 840 }
 841
 842 void LDM_outputConfiguration(void) {
 843   printf("=====================\n");
 844   printf("Configuration\n");
 845   printf("LDM_WINDOW_SIZE_LOG: %d\n", LDM_WINDOW_SIZE_LOG);
 846   printf("LDM_MIN_MATCH_LENGTH, LDM_HASH_LENGTH: %d, %d\n",
 847          LDM_MIN_MATCH_LENGTH, LDM_HASH_LENGTH);
 848   printf("LDM_MEMORY_USAGE: %d\n", LDM_MEMORY_USAGE);
 849   printf("HASH_ONLY_EVERY_LOG: %d\n", HASH_ONLY_EVERY_LOG);
 850   printf("HASH_BUCKET_SIZE_LOG: %d\n", HASH_BUCKET_SIZE_LOG);
 851   printf("LDM_LAG: %d\n", LDM_LAG);
 852   printf("USE_CHECKSUM: %d\n", USE_CHECKSUM);
 853   printf("INSERT_BY_TAG: %d\n", INSERT_BY_TAG);
 854   printf("HASH_CHAR_OFFSET: %d\n", HASH_CHAR_OFFSET);
 855   printf("=====================\n");
 856 }
 857