tests/paramgrill.c

   1 /*
   2  * Copyright (c) 2015-present, Yann Collet, Facebook, Inc.
   3  * All rights reserved.
   4  *
   5  * This source code is licensed under both the BSD-style license (found in the
   6  * LICENSE file in the root directory of this source tree) and the GPLv2 (found
   7  * in the COPYING file in the root directory of this source tree).
   8  * You may select, at your option, one of the above-listed licenses.
   9  */
  10
  11
  12 /*-************************************
  13 *  Dependencies
  14 **************************************/
  15 #include "util.h"      /* Compiler options, UTIL_GetFileSize */
  16 #include <stdlib.h>    /* malloc */
  17 #include <stdio.h>     /* fprintf, fopen, ftello64 */
  18 #include <string.h>    /* strcmp */
  19 #include <math.h>      /* log */
  20 #include <time.h>
  21
  22 #include "mem.h"
  23 #define ZSTD_STATIC_LINKING_ONLY   /* ZSTD_parameters, ZSTD_estimateCCtxSize */
  24 #include "zstd.h"
  25 #include "datagen.h"
  26 #include "xxhash.h"
  27 #include "util.h"
  28
  29
  30 /*-************************************
  31 *  Constants
  32 **************************************/
  33 #define PROGRAM_DESCRIPTION "ZSTD parameters tester"
  34 #define AUTHOR "Yann Collet"
  35 #define WELCOME_MESSAGE "*** %s %s %i-bits, by %s (%s) ***\n", PROGRAM_DESCRIPTION, ZSTD_VERSION_STRING, (int)(sizeof(void*)*8), AUTHOR, __DATE__
  36
  37
  38 #define KB *(1<<10)
  39 #define MB *(1<<20)
  40 #define GB *(1ULL<<30)
  41
  42 #define NBLOOPS    2
  43 #define TIMELOOP  (2 * SEC_TO_MICRO)
  44
  45 #define NB_LEVELS_TRACKED 30
  46
  47 static const size_t maxMemory = (sizeof(size_t)==4)  ?  (2 GB - 64 MB) : (size_t)(1ULL << ((sizeof(size_t)*8)-31));
  48
  49 #define COMPRESSIBILITY_DEFAULT 0.50
  50 static const size_t sampleSize = 10000000;
  51
  52 static const double g_grillDuration_s = 90000;   /* about 24 hours */
  53 static const U64 g_maxParamTime = 15 * SEC_TO_MICRO;
  54 static const U64 g_maxVariationTime = 60 * SEC_TO_MICRO;
  55 static const int g_maxNbVariations = 64;
  56
  57
  58 /*-************************************
  59 *  Macros
  60 **************************************/
  61 #define DISPLAY(...)  fprintf(stderr, __VA_ARGS__)
  62
  63 #undef MIN
  64 #undef MAX
  65 #define MIN(a,b)   ( (a) < (b) ? (a) : (b) )
  66 #define MAX(a,b)   ( (a) > (b) ? (a) : (b) )
  67
  68
  69 /*-************************************
  70 *  Benchmark Parameters
  71 **************************************/
  72 static U32 g_nbIterations = NBLOOPS;
  73 static double g_compressibility = COMPRESSIBILITY_DEFAULT;
  74 static U32 g_blockSize = 0;
  75 static U32 g_rand = 1;
  76 static U32 g_singleRun = 0;
  77 static U32 g_target = 0;
  78 static U32 g_noSeed = 0;
  79 static ZSTD_compressionParameters g_params = { 0, 0, 0, 0, 0, 0, ZSTD_greedy };
  80
  81 void BMK_SetNbIterations(int nbLoops)
  82 {
  83     g_nbIterations = nbLoops;
  84     DISPLAY("- %u iterations -\n", g_nbIterations);
  85 }
  86
  87
  88 /*-*******************************************************
  89 *  Private functions
  90 *********************************************************/
  91
  92 /* accuracy in seconds only, span can be multiple years */
  93 static double BMK_timeSpan(time_t tStart) { return difftime(time(NULL), tStart); }
  94
  95 static size_t BMK_findMaxMem(U64 requiredMem)
  96 {
  97     size_t const step = 64 MB;
  98     void* testmem = NULL;
  99
 100     requiredMem = (((requiredMem >> 26) + 1) << 26);
 101     if (requiredMem > maxMemory) requiredMem = maxMemory;
 102
 103     requiredMem += 2*step;
 104     while (!testmem) {
 105         requiredMem -= step;
 106         testmem = malloc ((size_t)requiredMem);
 107     }
 108
 109     free (testmem);
 110     return (size_t) (requiredMem - step);
 111 }
 112
 113
 114 static U32 FUZ_rotl32(U32 x, U32 r)
 115 {
 116     return ((x << r) | (x >> (32 - r)));
 117 }
 118
 119 U32 FUZ_rand(U32* src)
 120 {
 121     const U32 prime1 = 2654435761U;
 122     const U32 prime2 = 2246822519U;
 123     U32 rand32 = *src;
 124     rand32 *= prime1;
 125     rand32 += prime2;
 126     rand32  = FUZ_rotl32(rand32, 13);
 127     *src = rand32;
 128     return rand32 >> 5;
 129 }
 130
 131
 132 /*-*******************************************************
 133 *  Bench functions
 134 *********************************************************/
 135 typedef struct {
 136     size_t cSize;
 137     double cSpeed;   /* bytes / sec */
 138     double dSpeed;
 139 } BMK_result_t;
 140
 141 typedef struct
 142 {
 143     const char* srcPtr;
 144     size_t srcSize;
 145     char*  cPtr;
 146     size_t cRoom;
 147     size_t cSize;
 148     char*  resPtr;
 149     size_t resSize;
 150 } blockParam_t;
 151
 152
 153 static size_t BMK_benchParam(BMK_result_t* resultPtr,
 154                              const void* srcBuffer, size_t srcSize,
 155                              ZSTD_CCtx* ctx,
 156                              const ZSTD_compressionParameters cParams)
 157 {
 158     const size_t blockSize = g_blockSize ? g_blockSize : srcSize;
 159     const U32 nbBlocks = (U32) ((srcSize + (blockSize-1)) / blockSize);
 160     blockParam_t* const blockTable = (blockParam_t*) malloc(nbBlocks * sizeof(blockParam_t));
 161     const size_t maxCompressedSize = (size_t)nbBlocks * ZSTD_compressBound(blockSize);
 162     void* const compressedBuffer = malloc(maxCompressedSize);
 163     void* const resultBuffer = malloc(srcSize);
 164     ZSTD_parameters params;
 165     U32 Wlog = cParams.windowLog;
 166     U32 Clog = cParams.chainLog;
 167     U32 Hlog = cParams.hashLog;
 168     U32 Slog = cParams.searchLog;
 169     U32 Slength = cParams.searchLength;
 170     U32 Tlength = cParams.targetLength;
 171     ZSTD_strategy strat = cParams.strategy;
 172     char name[30] = { 0 };
 173     U64 crcOrig;
 174
 175     /* init result for early exit */
 176     resultPtr->cSize = srcSize;
 177     resultPtr->cSpeed = 0.;
 178     resultPtr->dSpeed = 0.;
 179
 180     /* Memory allocation & restrictions */
 181     snprintf(name, 30, "Sw%02uc%02uh%02us%02ul%1ut%03uS%1u", Wlog, Clog, Hlog, Slog, Slength, Tlength, strat);
 182     if (!compressedBuffer || !resultBuffer || !blockTable) {
 183         DISPLAY("\nError: not enough memory!\n");
 184         free(compressedBuffer);
 185         free(resultBuffer);
 186         free(blockTable);
 187         return 12;
 188     }
 189
 190     /* Calculating input Checksum */
 191     crcOrig = XXH64(srcBuffer, srcSize, 0);
 192
 193     /* Init blockTable data */
 194     {
 195         U32 i;
 196         size_t remaining = srcSize;
 197         const char* srcPtr = (const char*)srcBuffer;
 198         char* cPtr = (char*)compressedBuffer;
 199         char* resPtr = (char*)resultBuffer;
 200         for (i=0; i<nbBlocks; i++) {
 201             size_t thisBlockSize = MIN(remaining, blockSize);
 202             blockTable[i].srcPtr = srcPtr;
 203             blockTable[i].cPtr = cPtr;
 204             blockTable[i].resPtr = resPtr;
 205             blockTable[i].srcSize = thisBlockSize;
 206             blockTable[i].cRoom = ZSTD_compressBound(thisBlockSize);
 207             srcPtr += thisBlockSize;
 208             cPtr += blockTable[i].cRoom;
 209             resPtr += thisBlockSize;
 210             remaining -= thisBlockSize;
 211     }   }
 212
 213     /* warmimg up memory */
 214     RDG_genBuffer(compressedBuffer, maxCompressedSize, 0.10, 0.10, 1);
 215
 216     /* Bench */
 217     {   U32 loopNb;
 218         size_t cSize = 0;
 219         double fastestC = 100000000., fastestD = 100000000.;
 220         double ratio = 0.;
 221         UTIL_time_t const benchStart = UTIL_getTime();
 222
 223         DISPLAY("\r%79s\r", "");
 224         memset(&params, 0, sizeof(params));
 225         params.cParams = cParams;
 226         for (loopNb = 1; loopNb <= g_nbIterations; loopNb++) {
 227             int nbLoops;
 228             U32 blockNb;
 229             UTIL_time_t roundStart;
 230             U64 roundClock;
 231
 232             { U64 const benchTime = UTIL_clockSpanMicro(benchStart);
 233               if (benchTime > g_maxParamTime) break; }
 234
 235             /* Compression */
 236             DISPLAY("\r%1u-%s : %9u ->", loopNb, name, (U32)srcSize);
 237             memset(compressedBuffer, 0xE5, maxCompressedSize);
 238
 239             nbLoops = 0;
 240             UTIL_waitForNextTick();
 241             roundStart = UTIL_getTime();
 242             while (UTIL_clockSpanMicro(roundStart) < TIMELOOP) {
 243                 for (blockNb=0; blockNb<nbBlocks; blockNb++)
 244                     blockTable[blockNb].cSize = ZSTD_compress_advanced(ctx,
 245                                                     blockTable[blockNb].cPtr,  blockTable[blockNb].cRoom,
 246                                                     blockTable[blockNb].srcPtr, blockTable[blockNb].srcSize,
 247                                                     NULL, 0,
 248                                                     params);
 249                 nbLoops++;
 250             }
 251             roundClock = UTIL_clockSpanMicro(roundStart);
 252
 253             cSize = 0;
 254             for (blockNb=0; blockNb<nbBlocks; blockNb++)
 255                 cSize += blockTable[blockNb].cSize;
 256             ratio = (double)srcSize / (double)cSize;
 257             if ((double)roundClock < fastestC * SEC_TO_MICRO * nbLoops) fastestC = ((double)roundClock / SEC_TO_MICRO) / nbLoops;
 258             DISPLAY("\r");
 259             DISPLAY("%1u-%s : %9u ->", loopNb, name, (U32)srcSize);
 260             DISPLAY(" %9u (%4.3f),%7.1f MB/s", (U32)cSize, ratio, (double)srcSize / fastestC / 1000000.);
 261             resultPtr->cSize = cSize;
 262             resultPtr->cSpeed = (double)srcSize / fastestC;
 263
 264 #if 1
 265             /* Decompression */
 266             memset(resultBuffer, 0xD6, srcSize);
 267
 268             nbLoops = 0;
 269             UTIL_waitForNextTick();
 270             roundStart = UTIL_getTime();
 271             for ( ; UTIL_clockSpanMicro(roundStart) < TIMELOOP; nbLoops++) {
 272                 for (blockNb=0; blockNb<nbBlocks; blockNb++)
 273                     blockTable[blockNb].resSize = ZSTD_decompress(blockTable[blockNb].resPtr, blockTable[blockNb].srcSize,
 274                                                                   blockTable[blockNb].cPtr, blockTable[blockNb].cSize);
 275             }
 276             roundClock = UTIL_clockSpanMicro(roundStart);
 277
 278             if ((double)roundClock < fastestD * SEC_TO_MICRO * nbLoops) fastestD = ((double)roundClock / SEC_TO_MICRO) / nbLoops;
 279             DISPLAY("\r");
 280             DISPLAY("%1u-%s : %9u -> ", loopNb, name, (U32)srcSize);
 281             DISPLAY("%9u (%4.3f),%7.1f MB/s, ", (U32)cSize, ratio, (double)srcSize / fastestC / 1000000.);
 282             DISPLAY("%7.1f MB/s", (double)srcSize / fastestD / 1000000.);
 283             resultPtr->dSpeed = (double)srcSize / fastestD;
 284
 285             /* CRC Checking */
 286             {   U64 const crcCheck = XXH64(resultBuffer, srcSize, 0);
 287                 if (crcOrig!=crcCheck) {
 288                     unsigned u;
 289                     unsigned eBlockSize = (unsigned)(MIN(65536*2, blockSize));
 290                     DISPLAY("\n!!! WARNING !!! Invalid Checksum : %x != %x\n", (unsigned)crcOrig, (unsigned)crcCheck);
 291                     for (u=0; u<srcSize; u++) {
 292                         if (((const BYTE*)srcBuffer)[u] != ((BYTE*)resultBuffer)[u]) {
 293                             printf("Decoding error at pos %u (block %u, pos %u) \n", u, u / eBlockSize, u % eBlockSize);
 294                             break;
 295                     }   }
 296                     break;
 297             }   }
 298 #endif
 299     }   }
 300
 301     /* End cleaning */
 302     DISPLAY("\r");
 303     free(compressedBuffer);
 304     free(resultBuffer);
 305     return 0;
 306 }
 307
 308
 309 const char* g_stratName[ZSTD_btultra+1] = {
 310                 "(none)       ", "ZSTD_fast    ", "ZSTD_dfast   ",
 311                 "ZSTD_greedy  ", "ZSTD_lazy    ", "ZSTD_lazy2   ",
 312                 "ZSTD_btlazy2 ", "ZSTD_btopt   ", "ZSTD_btultra "};
 313
 314 static void BMK_printWinner(FILE* f, U32 cLevel, BMK_result_t result, ZSTD_compressionParameters params, size_t srcSize)
 315 {
 316     DISPLAY("\r%79s\r", "");
 317     fprintf(f,"    {%3u,%3u,%3u,%3u,%3u,%3u, %s },  ",
 318             params.windowLog, params.chainLog, params.hashLog, params.searchLog, params.searchLength,
 319             params.targetLength, g_stratName[(U32)(params.strategy)]);
 320     fprintf(f,
 321             "/* level %2u */   /* R:%5.3f at %5.1f MB/s - %5.1f MB/s */\n",
 322             cLevel, (double)srcSize / result.cSize, result.cSpeed / 1000000., result.dSpeed / 1000000.);
 323 }
 324
 325
 326 static double g_cSpeedTarget[NB_LEVELS_TRACKED] = { 0. };   /* NB_LEVELS_TRACKED : checked at main() */
 327
 328 typedef struct {
 329     BMK_result_t result;
 330     ZSTD_compressionParameters params;
 331 } winnerInfo_t;
 332
 333 static void BMK_printWinners2(FILE* f, const winnerInfo_t* winners, size_t srcSize)
 334 {
 335     int cLevel;
 336
 337     fprintf(f, "\n /* Proposed configurations : */ \n");
 338     fprintf(f, "    /* W,  C,  H,  S,  L,  T, strat */ \n");
 339
 340     for (cLevel=0; cLevel <= ZSTD_maxCLevel(); cLevel++)
 341         BMK_printWinner(f, cLevel, winners[cLevel].result, winners[cLevel].params, srcSize);
 342 }
 343
 344
 345 static void BMK_printWinners(FILE* f, const winnerInfo_t* winners, size_t srcSize)
 346 {
 347     fseek(f, 0, SEEK_SET);
 348     BMK_printWinners2(f, winners, srcSize);
 349     fflush(f);
 350     BMK_printWinners2(stdout, winners, srcSize);
 351 }
 352
 353 static int BMK_seed(winnerInfo_t* winners, const ZSTD_compressionParameters params,
 354               const void* srcBuffer, size_t srcSize,
 355                     ZSTD_CCtx* ctx)
 356 {
 357     BMK_result_t testResult;
 358     int better = 0;
 359     int cLevel;
 360
 361     BMK_benchParam(&testResult, srcBuffer, srcSize, ctx, params);
 362
 363     for (cLevel = 1; cLevel <= ZSTD_maxCLevel(); cLevel++) {
 364         if (testResult.cSpeed < g_cSpeedTarget[cLevel])
 365             continue;   /* not fast enough for this level */
 366         if (winners[cLevel].result.cSize==0) {
 367             /* first solution for this cLevel */
 368             winners[cLevel].result = testResult;
 369             winners[cLevel].params = params;
 370             BMK_printWinner(stdout, cLevel, testResult, params, srcSize);
 371             better = 1;
 372             continue;
 373         }
 374
 375         if ((double)testResult.cSize <= ((double)winners[cLevel].result.cSize * (1. + (0.02 / cLevel))) ) {
 376             /* Validate solution is "good enough" */
 377             double W_ratio = (double)srcSize / testResult.cSize;
 378             double O_ratio = (double)srcSize / winners[cLevel].result.cSize;
 379             double W_ratioNote = log (W_ratio);
 380             double O_ratioNote = log (O_ratio);
 381             size_t W_DMemUsed = (1 << params.windowLog) + (16 KB);
 382             size_t O_DMemUsed = (1 << winners[cLevel].params.windowLog) + (16 KB);
 383             double W_DMemUsed_note = W_ratioNote * ( 40 + 9*cLevel) - log((double)W_DMemUsed);
 384             double O_DMemUsed_note = O_ratioNote * ( 40 + 9*cLevel) - log((double)O_DMemUsed);
 385
 386             size_t W_CMemUsed = (1 << params.windowLog) + ZSTD_estimateCCtxSize_usingCParams(params);
 387             size_t O_CMemUsed = (1 << winners[cLevel].params.windowLog) + ZSTD_estimateCCtxSize_usingCParams(winners[cLevel].params);
 388             double W_CMemUsed_note = W_ratioNote * ( 50 + 13*cLevel) - log((double)W_CMemUsed);
 389             double O_CMemUsed_note = O_ratioNote * ( 50 + 13*cLevel) - log((double)O_CMemUsed);
 390
 391             double W_CSpeed_note = W_ratioNote * ( 30 + 10*cLevel) + log(testResult.cSpeed);
 392             double O_CSpeed_note = O_ratioNote * ( 30 + 10*cLevel) + log(winners[cLevel].result.cSpeed);
 393
 394             double W_DSpeed_note = W_ratioNote * ( 20 + 2*cLevel) + log(testResult.dSpeed);
 395             double O_DSpeed_note = O_ratioNote * ( 20 + 2*cLevel) + log(winners[cLevel].result.dSpeed);
 396
 397             if (W_DMemUsed_note < O_DMemUsed_note) {
 398                 /* uses too much Decompression memory for too little benefit */
 399                 if (W_ratio > O_ratio)
 400                 DISPLAY ("Decompression Memory : %5.3f @ %4.1f MB  vs  %5.3f @ %4.1f MB   : not enough for level %i\n",
 401                          W_ratio, (double)(W_DMemUsed) / 1024 / 1024,
 402                          O_ratio, (double)(O_DMemUsed) / 1024 / 1024,   cLevel);
 403                 continue;
 404             }
 405             if (W_CMemUsed_note < O_CMemUsed_note) {
 406                 /* uses too much memory for compression for too little benefit */
 407                 if (W_ratio > O_ratio)
 408                 DISPLAY ("Compression Memory : %5.3f @ %4.1f MB  vs  %5.3f @ %4.1f MB   : not enough for level %i\n",
 409                          W_ratio, (double)(W_CMemUsed) / 1024 / 1024,
 410                          O_ratio, (double)(O_CMemUsed) / 1024 / 1024,   cLevel);
 411                 continue;
 412             }
 413             if (W_CSpeed_note   < O_CSpeed_note  ) {
 414                 /* too large compression speed difference for the compression benefit */
 415                 if (W_ratio > O_ratio)
 416                 DISPLAY ("Compression Speed : %5.3f @ %4.1f MB/s  vs  %5.3f @ %4.1f MB/s   : not enough for level %i\n",
 417                          W_ratio, testResult.cSpeed / 1000000,
 418                          O_ratio, winners[cLevel].result.cSpeed / 1000000.,   cLevel);
 419                 continue;
 420             }
 421             if (W_DSpeed_note   < O_DSpeed_note  ) {
 422                 /* too large decompression speed difference for the compression benefit */
 423                 if (W_ratio > O_ratio)
 424                 DISPLAY ("Decompression Speed : %5.3f @ %4.1f MB/s  vs  %5.3f @ %4.1f MB/s   : not enough for level %i\n",
 425                          W_ratio, testResult.dSpeed / 1000000.,
 426                          O_ratio, winners[cLevel].result.dSpeed / 1000000.,   cLevel);
 427                 continue;
 428             }
 429
 430             if (W_ratio < O_ratio)
 431                 DISPLAY("Solution %4.3f selected over %4.3f at level %i, due to better secondary statistics \n", W_ratio, O_ratio, cLevel);
 432
 433             winners[cLevel].result = testResult;
 434             winners[cLevel].params = params;
 435             BMK_printWinner(stdout, cLevel, testResult, params, srcSize);
 436
 437             better = 1;
 438     }   }
 439
 440     return better;
 441 }
 442
 443
 444 /* nullified useless params, to ensure count stats */
 445 static ZSTD_compressionParameters* sanitizeParams(ZSTD_compressionParameters params)
 446 {
 447     g_params = params;
 448     if (params.strategy == ZSTD_fast)
 449         g_params.chainLog = 0, g_params.searchLog = 0;
 450     if (params.strategy == ZSTD_dfast)
 451         g_params.searchLog = 0;
 452     if (params.strategy != ZSTD_btopt && params.strategy != ZSTD_btultra)
 453         g_params.targetLength = 0;
 454     return &g_params;
 455 }
 456
 457
 458 static void paramVariation(ZSTD_compressionParameters* ptr)
 459 {
 460     ZSTD_compressionParameters p;
 461     U32 validated = 0;
 462     while (!validated) {
 463         U32 nbChanges = (FUZ_rand(&g_rand) & 3) + 1;
 464         p = *ptr;
 465         for ( ; nbChanges ; nbChanges--) {
 466             const U32 changeID = FUZ_rand(&g_rand) % 14;
 467             switch(changeID)
 468             {
 469             case 0:
 470                 p.chainLog++; break;
 471             case 1:
 472                 p.chainLog--; break;
 473             case 2:
 474                 p.hashLog++; break;
 475             case 3:
 476                 p.hashLog--; break;
 477             case 4:
 478                 p.searchLog++; break;
 479             case 5:
 480                 p.searchLog--; break;
 481             case 6:
 482                 p.windowLog++; break;
 483             case 7:
 484                 p.windowLog--; break;
 485             case 8:
 486                 p.searchLength++; break;
 487             case 9:
 488                 p.searchLength--; break;
 489             case 10:
 490                 p.strategy = (ZSTD_strategy)(((U32)p.strategy)+1); break;
 491             case 11:
 492                 p.strategy = (ZSTD_strategy)(((U32)p.strategy)-1); break;
 493             case 12:
 494                 p.targetLength *= 1 + ((double)(FUZ_rand(&g_rand)&255)) / 256.; break;
 495             case 13:
 496                 p.targetLength /= 1 + ((double)(FUZ_rand(&g_rand)&255)) / 256.; break;
 497             }
 498         }
 499         validated = !ZSTD_isError(ZSTD_checkCParams(p));
 500     }
 501     *ptr = p;
 502 }
 503
 504
 505 #define PARAMTABLELOG   25
 506 #define PARAMTABLESIZE (1<<PARAMTABLELOG)
 507 #define PARAMTABLEMASK (PARAMTABLESIZE-1)
 508 static BYTE g_alreadyTested[PARAMTABLESIZE] = {0};   /* init to zero */
 509
 510 #define NB_TESTS_PLAYED(p) \
 511     g_alreadyTested[(XXH64(sanitizeParams(p), sizeof(p), 0) >> 3) & PARAMTABLEMASK]
 512
 513
 514 static void playAround(FILE* f, winnerInfo_t* winners,
 515                        ZSTD_compressionParameters params,
 516                        const void* srcBuffer, size_t srcSize,
 517                        ZSTD_CCtx* ctx)
 518 {
 519     int nbVariations = 0;
 520     UTIL_time_t const clockStart = UTIL_getTime();
 521
 522     while (UTIL_clockSpanMicro(clockStart) < g_maxVariationTime) {
 523         ZSTD_compressionParameters p = params;
 524
 525         if (nbVariations++ > g_maxNbVariations) break;
 526         paramVariation(&p);
 527
 528         /* exclude faster if already played params */
 529         if (FUZ_rand(&g_rand) & ((1 << NB_TESTS_PLAYED(p))-1))
 530             continue;
 531
 532         /* test */
 533         NB_TESTS_PLAYED(p)++;
 534         if (!BMK_seed(winners, p, srcBuffer, srcSize, ctx)) continue;
 535
 536         /* improvement found => search more */
 537         BMK_printWinners(f, winners, srcSize);
 538         playAround(f, winners, p, srcBuffer, srcSize, ctx);
 539     }
 540
 541 }
 542
 543
 544 static ZSTD_compressionParameters randomParams(void)
 545 {
 546     ZSTD_compressionParameters p;
 547     U32 validated = 0;
 548     while (!validated) {
 549         /* totally random entry */
 550         p.chainLog   = (FUZ_rand(&g_rand) % (ZSTD_CHAINLOG_MAX+1 - ZSTD_CHAINLOG_MIN)) + ZSTD_CHAINLOG_MIN;
 551         p.hashLog    = (FUZ_rand(&g_rand) % (ZSTD_HASHLOG_MAX+1 - ZSTD_HASHLOG_MIN)) + ZSTD_HASHLOG_MIN;
 552         p.searchLog  = (FUZ_rand(&g_rand) % (ZSTD_SEARCHLOG_MAX+1 - ZSTD_SEARCHLOG_MIN)) + ZSTD_SEARCHLOG_MIN;
 553         p.windowLog  = (FUZ_rand(&g_rand) % (ZSTD_WINDOWLOG_MAX+1 - ZSTD_WINDOWLOG_MIN)) + ZSTD_WINDOWLOG_MIN;
 554         p.searchLength=(FUZ_rand(&g_rand) % (ZSTD_SEARCHLENGTH_MAX+1 - ZSTD_SEARCHLENGTH_MIN)) + ZSTD_SEARCHLENGTH_MIN;
 555         p.targetLength=(FUZ_rand(&g_rand) % (512)) + ZSTD_TARGETLENGTH_MIN;
 556         p.strategy   = (ZSTD_strategy) (FUZ_rand(&g_rand) % (ZSTD_btultra +1));
 557         validated = !ZSTD_isError(ZSTD_checkCParams(p));
 558     }
 559     return p;
 560 }
 561
 562 static void BMK_selectRandomStart(
 563                        FILE* f, winnerInfo_t* winners,
 564                        const void* srcBuffer, size_t srcSize,
 565                        ZSTD_CCtx* ctx)
 566 {
 567     U32 const id = (FUZ_rand(&g_rand) % (ZSTD_maxCLevel()+1));
 568     if ((id==0) || (winners[id].params.windowLog==0)) {
 569         /* totally random entry */
 570         ZSTD_compressionParameters const p = ZSTD_adjustCParams(randomParams(), srcSize, 0);
 571         playAround(f, winners, p, srcBuffer, srcSize, ctx);
 572     }
 573     else
 574         playAround(f, winners, winners[id].params, srcBuffer, srcSize, ctx);
 575 }
 576
 577
 578 static void BMK_benchMem(void* srcBuffer, size_t srcSize)
 579 {
 580     ZSTD_CCtx* const ctx = ZSTD_createCCtx();
 581     ZSTD_compressionParameters params;
 582     winnerInfo_t winners[NB_LEVELS_TRACKED];
 583     const char* const rfName = "grillResults.txt";
 584     FILE* const f = fopen(rfName, "w");
 585     const size_t blockSize = g_blockSize ? g_blockSize : srcSize;
 586
 587     /* init */
 588     if (ctx==NULL) { DISPLAY("ZSTD_createCCtx() failed \n"); exit(1); }
 589     memset(winners, 0, sizeof(winners));
 590     if (f==NULL) { DISPLAY("error opening %s \n", rfName); exit(1); }
 591
 592     if (g_singleRun) {
 593         BMK_result_t testResult;
 594         g_params = ZSTD_adjustCParams(g_params, srcSize, 0);
 595         BMK_benchParam(&testResult, srcBuffer, srcSize, ctx, g_params);
 596         DISPLAY("\n");
 597         return;
 598     }
 599
 600     if (g_target)
 601         g_cSpeedTarget[1] = g_target * 1000000;
 602     else {
 603         /* baseline config for level 1 */
 604         BMK_result_t testResult;
 605         params = ZSTD_getCParams(1, blockSize, 0);
 606         BMK_benchParam(&testResult, srcBuffer, srcSize, ctx, params);
 607         g_cSpeedTarget[1] = (testResult.cSpeed * 31) / 32;
 608     }
 609
 610     /* establish speed objectives (relative to level 1) */
 611     {   int i;
 612         for (i=2; i<=ZSTD_maxCLevel(); i++)
 613             g_cSpeedTarget[i] = (g_cSpeedTarget[i-1] * 25) / 32;
 614     }
 615
 616     /* populate initial solution */
 617     {   const int maxSeeds = g_noSeed ? 1 : ZSTD_maxCLevel();
 618         int i;
 619         for (i=0; i<=maxSeeds; i++) {
 620             params = ZSTD_getCParams(i, blockSize, 0);
 621             BMK_seed(winners, params, srcBuffer, srcSize, ctx);
 622     }   }
 623     BMK_printWinners(f, winners, srcSize);
 624
 625     /* start tests */
 626     {   const time_t grillStart = time(NULL);
 627         do {
 628             BMK_selectRandomStart(f, winners, srcBuffer, srcSize, ctx);
 629         } while (BMK_timeSpan(grillStart) < g_grillDuration_s);
 630     }
 631
 632     /* end summary */
 633     BMK_printWinners(f, winners, srcSize);
 634     DISPLAY("grillParams operations completed \n");
 635
 636     /* clean up*/
 637     fclose(f);
 638     ZSTD_freeCCtx(ctx);
 639 }
 640
 641
 642 static int benchSample(void)
 643 {
 644     void* origBuff;
 645     size_t const benchedSize = sampleSize;
 646     const char* const name = "Sample 10MiB";
 647
 648     /* Allocation */
 649     origBuff = malloc(benchedSize);
 650     if (!origBuff) { DISPLAY("\nError: not enough memory!\n"); return 12; }
 651
 652     /* Fill buffer */
 653     RDG_genBuffer(origBuff, benchedSize, g_compressibility, 0.0, 0);
 654
 655     /* bench */
 656     DISPLAY("\r%79s\r", "");
 657     DISPLAY("using %s %i%%: \n", name, (int)(g_compressibility*100));
 658     BMK_benchMem(origBuff, benchedSize);
 659
 660     free(origBuff);
 661     return 0;
 662 }
 663
 664
 665 int benchFiles(const char** fileNamesTable, int nbFiles)
 666 {
 667     int fileIdx=0;
 668
 669     /* Loop for each file */
 670     while (fileIdx<nbFiles) {
 671         const char* const inFileName = fileNamesTable[fileIdx++];
 672         FILE* const inFile = fopen( inFileName, "rb" );
 673         U64 const inFileSize = UTIL_getFileSize(inFileName);
 674         size_t benchedSize;
 675         void* origBuff;
 676
 677         /* Check file existence */
 678         if (inFile==NULL) {
 679             DISPLAY( "Pb opening %s\n", inFileName);
 680             return 11;
 681         }
 682         if (inFileSize == UTIL_FILESIZE_UNKNOWN) {
 683             DISPLAY("Pb evaluatin size of %s \n", inFileName);
 684             fclose(inFile);
 685             return 11;
 686         }
 687
 688         /* Memory allocation */
 689         benchedSize = BMK_findMaxMem(inFileSize*3) / 3;
 690         if ((U64)benchedSize > inFileSize) benchedSize = (size_t)inFileSize;
 691         if (benchedSize < inFileSize)
 692             DISPLAY("Not enough memory for '%s' full size; testing %i MB only...\n", inFileName, (int)(benchedSize>>20));
 693         origBuff = malloc(benchedSize);
 694         if (origBuff==NULL) {
 695             DISPLAY("\nError: not enough memory!\n");
 696             fclose(inFile);
 697             return 12;
 698         }
 699
 700         /* Fill input buffer */
 701         DISPLAY("Loading %s...       \r", inFileName);
 702         {   size_t const readSize = fread(origBuff, 1, benchedSize, inFile);
 703             fclose(inFile);
 704             if(readSize != benchedSize) {
 705                 DISPLAY("\nError: problem reading file '%s' !!    \n", inFileName);
 706                 free(origBuff);
 707                 return 13;
 708         }   }
 709
 710         /* bench */
 711         DISPLAY("\r%79s\r", "");
 712         DISPLAY("using %s : \n", inFileName);
 713         BMK_benchMem(origBuff, benchedSize);
 714
 715         /* clean */
 716         free(origBuff);
 717     }
 718
 719     return 0;
 720 }
 721
 722
 723 static void BMK_translateAdvancedParams(ZSTD_compressionParameters params)
 724 {
 725     DISPLAY("--zstd=windowLog=%u,chainLog=%u,hashLog=%u,searchLog=%u,searchLength=%u,targetLength=%u,strategy=%u \n",
 726              params.windowLog, params.chainLog, params.hashLog, params.searchLog, params.searchLength, params.targetLength, (U32)(params.strategy));
 727 }
 728
 729 /* optimizeForSize():
 730  * targetSpeed : expressed in MB/s */
 731 int optimizeForSize(const char* inFileName, U32 targetSpeed)
 732 {
 733     FILE* const inFile = fopen( inFileName, "rb" );
 734     U64 const inFileSize = UTIL_getFileSize(inFileName);
 735     size_t benchedSize = BMK_findMaxMem(inFileSize*3) / 3;
 736     void* origBuff;
 737
 738     /* Init */
 739     if (inFile==NULL) { DISPLAY( "Pb opening %s\n", inFileName); return 11; }
 740     if (inFileSize == UTIL_FILESIZE_UNKNOWN) {
 741         DISPLAY("Pb evaluatin size of %s \n", inFileName);
 742         fclose(inFile);
 743         return 11;
 744     }
 745
 746     /* Memory allocation & restrictions */
 747     if ((U64)benchedSize > inFileSize) benchedSize = (size_t)inFileSize;
 748     if (benchedSize < inFileSize) {
 749         DISPLAY("Not enough memory for '%s' \n", inFileName);
 750         fclose(inFile);
 751         return 11;
 752     }
 753
 754     /* Alloc */
 755     origBuff = malloc(benchedSize);
 756     if(!origBuff) {
 757         DISPLAY("\nError: not enough memory!\n");
 758         fclose(inFile);
 759         return 12;
 760     }
 761
 762     /* Fill input buffer */
 763     DISPLAY("Loading %s...       \r", inFileName);
 764     {   size_t const readSize = fread(origBuff, 1, benchedSize, inFile);
 765         fclose(inFile);
 766         if(readSize != benchedSize) {
 767             DISPLAY("\nError: problem reading file '%s' !!    \n", inFileName);
 768             free(origBuff);
 769             return 13;
 770     }   }
 771
 772     /* bench */
 773     DISPLAY("\r%79s\r", "");
 774     DISPLAY("optimizing for %s - limit speed %u MB/s \n", inFileName, targetSpeed);
 775     targetSpeed *= 1000000;
 776
 777     {   ZSTD_CCtx* const ctx = ZSTD_createCCtx();
 778         winnerInfo_t winner;
 779         BMK_result_t candidate;
 780         const size_t blockSize = g_blockSize ? g_blockSize : benchedSize;
 781
 782         /* init */
 783         if (ctx==NULL) { DISPLAY("\n ZSTD_createCCtx error \n"); free(origBuff); return 14;}
 784         memset(&winner, 0, sizeof(winner));
 785         winner.result.cSize = (size_t)(-1);
 786
 787         /* find best solution from default params */
 788         {   const int maxSeeds = g_noSeed ? 1 : ZSTD_maxCLevel();
 789             int i;
 790             for (i=1; i<=maxSeeds; i++) {
 791                 ZSTD_compressionParameters const CParams = ZSTD_getCParams(i, blockSize, 0);
 792                 BMK_benchParam(&candidate, origBuff, benchedSize, ctx, CParams);
 793                 if (candidate.cSpeed < targetSpeed)
 794                     break;
 795                 if ( (candidate.cSize < winner.result.cSize)
 796                    | ((candidate.cSize == winner.result.cSize) & (candidate.cSpeed > winner.result.cSpeed)) )
 797                 {
 798                     winner.params = CParams;
 799                     winner.result = candidate;
 800                     BMK_printWinner(stdout, i, winner.result, winner.params, benchedSize);
 801             }   }
 802         }
 803         BMK_printWinner(stdout, 99, winner.result, winner.params, benchedSize);
 804         BMK_translateAdvancedParams(winner.params);
 805
 806         /* start tests */
 807         {   time_t const grillStart = time(NULL);
 808             do {
 809                 ZSTD_compressionParameters params = winner.params;
 810                 paramVariation(&params);
 811                 if ((FUZ_rand(&g_rand) & 31) == 3) params = randomParams();  /* totally random config to improve search space */
 812                 params = ZSTD_adjustCParams(params, blockSize, 0);
 813
 814                 /* exclude faster if already played set of params */
 815                 if (FUZ_rand(&g_rand) & ((1 << NB_TESTS_PLAYED(params))-1)) continue;
 816
 817                 /* test */
 818                 NB_TESTS_PLAYED(params)++;
 819                 BMK_benchParam(&candidate, origBuff, benchedSize, ctx, params);
 820
 821                 /* improvement found => new winner */
 822                 if ( (candidate.cSpeed > targetSpeed)
 823                    & ( (candidate.cSize < winner.result.cSize)
 824                      | ((candidate.cSize == winner.result.cSize) & (candidate.cSpeed > winner.result.cSpeed)) )  )
 825                 {
 826                     winner.params = params;
 827                     winner.result = candidate;
 828                     BMK_printWinner(stdout, 99, winner.result, winner.params, benchedSize);
 829                     BMK_translateAdvancedParams(winner.params);
 830                 }
 831             } while (BMK_timeSpan(grillStart) < g_grillDuration_s);
 832         }
 833
 834         /* end summary */
 835         BMK_printWinner(stdout, 99, winner.result, winner.params, benchedSize);
 836         DISPLAY("grillParams size - optimizer completed \n");
 837
 838         /* clean up*/
 839         ZSTD_freeCCtx(ctx);
 840     }
 841
 842     free(origBuff);
 843     return 0;
 844 }
 845
 846
 847 static int usage(const char* exename)
 848 {
 849     DISPLAY( "Usage :\n");
 850     DISPLAY( "      %s [arg] file\n", exename);
 851     DISPLAY( "Arguments :\n");
 852     DISPLAY( " file : path to the file used as reference (if none, generates a compressible sample)\n");
 853     DISPLAY( " -H/-h  : Help (this text + advanced options)\n");
 854     return 0;
 855 }
 856
 857 static int usage_advanced(void)
 858 {
 859     DISPLAY( "\nAdvanced options :\n");
 860     DISPLAY( " -T#    : set level 1 speed objective \n");
 861     DISPLAY( " -B#    : cut input into blocks of size # (default : single block) \n");
 862     DISPLAY( " -i#    : iteration loops [1-9](default : %i) \n", NBLOOPS);
 863     DISPLAY( " -O#    : find Optimized parameters for # MB/s compression speed (default : 0) \n");
 864     DISPLAY( " -S     : Single run \n");
 865     DISPLAY( " -P#    : generated sample compressibility (default : %.1f%%) \n", COMPRESSIBILITY_DEFAULT * 100);
 866     return 0;
 867 }
 868
 869 static int badusage(const char* exename)
 870 {
 871     DISPLAY("Wrong parameters\n");
 872     usage(exename);
 873     return 1;
 874 }
 875
 876 int main(int argc, const char** argv)
 877 {
 878     int i,
 879         filenamesStart=0,
 880         result;
 881     const char* exename=argv[0];
 882     const char* input_filename=0;
 883     U32 optimizer = 0;
 884     U32 main_pause = 0;
 885     U32 targetSpeed = 0;
 886
 887     /* checks */
 888     if (NB_LEVELS_TRACKED <= ZSTD_maxCLevel()) {
 889         DISPLAY("Error : NB_LEVELS_TRACKED <= ZSTD_maxCLevel() \n");
 890         exit(1);
 891     }
 892
 893     /* Welcome message */
 894     DISPLAY(WELCOME_MESSAGE);
 895
 896     if (argc<1) { badusage(exename); return 1; }
 897
 898     for(i=1; i<argc; i++) {
 899         const char* argument = argv[i];
 900
 901         if(!argument) continue;   /* Protection if argument empty */
 902
 903         if(!strcmp(argument,"--no-seed")) { g_noSeed = 1; continue; }
 904
 905         /* Decode command (note : aggregated commands are allowed) */
 906         if (argument[0]=='-') {
 907             argument++;
 908
 909             while (argument[0]!=0) {
 910
 911                 switch(argument[0])
 912                 {
 913                     /* Display help on usage */
 914                 case 'h' :
 915                 case 'H': usage(exename); usage_advanced(); return 0;
 916
 917                     /* Pause at the end (hidden option) */
 918                 case 'p': main_pause = 1; argument++; break;
 919
 920                     /* Modify Nb Iterations */
 921                 case 'i':
 922                     argument++;
 923                     if ((argument[0] >='0') & (argument[0] <='9'))
 924                         g_nbIterations = *argument++ - '0';
 925                     break;
 926
 927                     /* Sample compressibility (when no file provided) */
 928                 case 'P':
 929                     argument++;
 930                     {   U32 proba32 = 0;
 931                         while ((argument[0]>= '0') & (argument[0]<= '9'))
 932                             proba32 = (proba32*10) + (*argument++ - '0');
 933                         g_compressibility = (double)proba32 / 100.;
 934                     }
 935                     break;
 936
 937                 case 'O':
 938                     argument++;
 939                     optimizer=1;
 940                     targetSpeed = 0;
 941                     while ((*argument >= '0') & (*argument <= '9'))
 942                         targetSpeed = (targetSpeed*10) + (*argument++ - '0');
 943                     break;
 944
 945                     /* Run Single conf */
 946                 case 'S':
 947                     g_singleRun = 1;
 948                     argument++;
 949                     g_params = ZSTD_getCParams(2, g_blockSize, 0);
 950                     for ( ; ; ) {
 951                         switch(*argument)
 952                         {
 953                         case 'w':
 954                             g_params.windowLog = 0;
 955                             argument++;
 956                             while ((*argument>= '0') && (*argument<='9'))
 957                                 g_params.windowLog *= 10, g_params.windowLog += *argument++ - '0';
 958                             continue;
 959                         case 'c':
 960                             g_params.chainLog = 0;
 961                             argument++;
 962                             while ((*argument>= '0') && (*argument<='9'))
 963                                 g_params.chainLog *= 10, g_params.chainLog += *argument++ - '0';
 964                             continue;
 965                         case 'h':
 966                             g_params.hashLog = 0;
 967                             argument++;
 968                             while ((*argument>= '0') && (*argument<='9'))
 969                                 g_params.hashLog *= 10, g_params.hashLog += *argument++ - '0';
 970                             continue;
 971                         case 's':
 972                             g_params.searchLog = 0;
 973                             argument++;
 974                             while ((*argument>= '0') && (*argument<='9'))
 975                                 g_params.searchLog *= 10, g_params.searchLog += *argument++ - '0';
 976                             continue;
 977                         case 'l':  /* search length */
 978                             g_params.searchLength = 0;
 979                             argument++;
 980                             while ((*argument>= '0') && (*argument<='9'))
 981                                 g_params.searchLength *= 10, g_params.searchLength += *argument++ - '0';
 982                             continue;
 983                         case 't':  /* target length */
 984                             g_params.targetLength = 0;
 985                             argument++;
 986                             while ((*argument>= '0') && (*argument<='9'))
 987                                 g_params.targetLength *= 10, g_params.targetLength += *argument++ - '0';
 988                             continue;
 989                         case 'S':  /* strategy */
 990                             argument++;
 991                             while ((*argument>= '0') && (*argument<='9'))
 992                                 g_params.strategy = (ZSTD_strategy)(*argument++ - '0');
 993                             continue;
 994                         case 'L':
 995                             {   int cLevel = 0;
 996                                 argument++;
 997                                 while ((*argument>= '0') && (*argument<='9'))
 998                                     cLevel *= 10, cLevel += *argument++ - '0';
 999                                 g_params = ZSTD_getCParams(cLevel, g_blockSize, 0);
1000                                 continue;
1001                             }
1002                         default : ;
1003                         }
1004                         break;
1005                     }
1006                     break;
1007
1008                     /* target level1 speed objective, in MB/s */
1009                 case 'T':
1010                     argument++;
1011                     g_target = 0;
1012                     while ((*argument >= '0') && (*argument <= '9'))
1013                         g_target = (g_target*10) + (*argument++ - '0');
1014                     break;
1015
1016                     /* cut input into blocks */
1017                 case 'B':
1018                     g_blockSize = 0;
1019                     argument++;
1020                     while ((*argument >='0') & (*argument <='9'))
1021                         g_blockSize = (g_blockSize*10) + (*argument++ - '0');
1022                     if (*argument=='K') g_blockSize<<=10, argument++;  /* allows using KB notation */
1023                     if (*argument=='M') g_blockSize<<=20, argument++;
1024                     if (*argument=='B') argument++;
1025                     DISPLAY("using %u KB block size \n", g_blockSize>>10);
1026                     break;
1027
1028                     /* Unknown command */
1029                 default : return badusage(exename);
1030                 }
1031             }
1032             continue;
1033         }   /* if (argument[0]=='-') */
1034
1035         /* first provided filename is input */
1036         if (!input_filename) { input_filename=argument; filenamesStart=i; continue; }
1037     }
1038
1039     if (filenamesStart==0)
1040         result = benchSample();
1041     else {
1042         if (optimizer)
1043             result = optimizeForSize(input_filename, targetSpeed);
1044         else
1045             result = benchFiles(argv+filenamesStart, argc-filenamesStart);
1046     }
1047
1048     if (main_pause) { int unused; printf("press enter...\n"); unused = getchar(); (void)unused; }
1049
1050     return result;
1051 }