paramgrill.c

/*
 * Copyright (c) Meta Platforms, Inc. and affiliates.
 * All rights reserved.
 *
 * This source code is licensed under both the BSD-style license (found in the
 * LICENSE file in the root directory of this source tree) and the GPLv2 (found
 * in the COPYING file in the root directory of this source tree).
 * You may select, at your option, one of the above-listed licenses.
 */


/*-************************************
*  Dependencies
**************************************/
#include "util.h"      /* Ensure platform.h is compiled first; also : compiler options, UTIL_GetFileSize */
#include <stdlib.h>    /* malloc */
#include <stdio.h>     /* fprintf, fopen, ftello64 */
#include <string.h>    /* strcmp */
#include <math.h>      /* log */
#include <assert.h>

#include "timefn.h"    /* SEC_TO_MICRO, UTIL_time_t, UTIL_clockSpanMicro, UTIL_clockSpanNano, UTIL_getTime */
#include "mem.h"
#define ZSTD_STATIC_LINKING_ONLY   /* ZSTD_parameters, ZSTD_estimateCCtxSize */
#include "zstd.h"
#include "datagen.h"
#include "xxhash.h"
#include "benchfn.h"
#include "benchzstd.h"
#include "zstd_errors.h"
#include "zstd_internal.h"     /* should not be needed */


/*-************************************
*  Constants
**************************************/
#define PROGRAM_DESCRIPTION "ZSTD parameters tester"
#define AUTHOR "Yann Collet"
#define WELCOME_MESSAGE "*** %s %s %i-bits, by %s ***\n", PROGRAM_DESCRIPTION, ZSTD_VERSION_STRING, (int)(sizeof(void*)*8), AUTHOR

#define TIMELOOP_NANOSEC      (1*1000000000ULL) /* 1 second */
#define NB_LEVELS_TRACKED 22   /* ensured being >= ZSTD_maxCLevel() in BMK_init_level_constraints() */

static const size_t maxMemory = (sizeof(size_t)==4)  ?  (2 GB - 64 MB) : (size_t)(1ULL << ((sizeof(size_t)*8)-31));

#define COMPRESSIBILITY_DEFAULT 0.50

static const U64 g_maxVariationTime = 60 * SEC_TO_MICRO;
static const int g_maxNbVariations = 64;


/*-************************************
*  Macros
**************************************/
#define DISPLAY(...)  fprintf(stderr, __VA_ARGS__)
#define DISPLAYLEVEL(n, ...) if(g_displayLevel >= n) { fprintf(stderr, __VA_ARGS__); }
#define DEBUGOUTPUT(...) { if (DEBUG) DISPLAY(__VA_ARGS__); }

#define TIMED 0
#ifndef DEBUG
#  define DEBUG 0
#endif

#undef MIN
#undef MAX
#define MIN(a,b)   ( (a) < (b) ? (a) : (b) )
#define MAX(a,b)   ( (a) > (b) ? (a) : (b) )
#define CUSTOM_LEVEL 99
#define BASE_CLEVEL 1

#define FADT_MIN 0
#define FADT_MAX ((U32)-1)

#define WLOG_RANGE (ZSTD_WINDOWLOG_MAX - ZSTD_WINDOWLOG_MIN + 1)
#define CLOG_RANGE (ZSTD_CHAINLOG_MAX - ZSTD_CHAINLOG_MIN + 1)
#define HLOG_RANGE (ZSTD_HASHLOG_MAX - ZSTD_HASHLOG_MIN + 1)
#define SLOG_RANGE (ZSTD_SEARCHLOG_MAX - ZSTD_SEARCHLOG_MIN + 1)
#define MML_RANGE  (ZSTD_MINMATCH_MAX - ZSTD_MINMATCH_MIN + 1)
#define TLEN_RANGE  17
#define STRT_RANGE (ZSTD_STRATEGY_MAX - ZSTD_STRATEGY_MIN + 1)
#define FADT_RANGE   3

#define CHECKTIME(r) { if(BMK_timeSpan_s(g_time) > g_timeLimit_s) { DEBUGOUTPUT("Time Limit Reached\n"); return r; } }
#define CHECKTIMEGT(ret, val, _gototag) { if(BMK_timeSpan_s(g_time) > g_timeLimit_s) { DEBUGOUTPUT("Time Limit Reached\n"); ret = val; goto _gototag; } }

#define PARAM_UNSET ((U32)-2) /* can't be -1 b/c fadt uses -1 */

static const char* g_stratName[ZSTD_STRATEGY_MAX+1] = {
                "(none)       ", "ZSTD_fast    ", "ZSTD_dfast   ",
                "ZSTD_greedy  ", "ZSTD_lazy    ", "ZSTD_lazy2   ",
                "ZSTD_btlazy2 ", "ZSTD_btopt   ", "ZSTD_btultra ",
                "ZSTD_btultra2"};

static const U32 tlen_table[TLEN_RANGE] = { 0, 1, 2, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 128, 256, 512, 999 };


/*-************************************
*  Setup for Adding new params
**************************************/

/* indices for each of the variables */
typedef enum {
    wlog_ind = 0,
    clog_ind = 1,
    hlog_ind = 2,
    slog_ind = 3,
    mml_ind  = 4,
    tlen_ind = 5,
    strt_ind = 6,
    fadt_ind = 7, /* forceAttachDict */
    NUM_PARAMS = 8
} varInds_t;

typedef struct {
    U32 vals[NUM_PARAMS];
} paramValues_t;

/* minimum value of parameters */
static const U32 mintable[NUM_PARAMS] =
        { ZSTD_WINDOWLOG_MIN, ZSTD_CHAINLOG_MIN, ZSTD_HASHLOG_MIN, ZSTD_SEARCHLOG_MIN, ZSTD_MINMATCH_MIN, ZSTD_TARGETLENGTH_MIN, ZSTD_STRATEGY_MIN, FADT_MIN };

/* maximum value of parameters */
static const U32 maxtable[NUM_PARAMS] =
        { ZSTD_WINDOWLOG_MAX, ZSTD_CHAINLOG_MAX, ZSTD_HASHLOG_MAX, ZSTD_SEARCHLOG_MAX, ZSTD_MINMATCH_MAX, ZSTD_TARGETLENGTH_MAX, ZSTD_STRATEGY_MAX, FADT_MAX };

/* # of values parameters can take on */
static const U32 rangetable[NUM_PARAMS] =
        { WLOG_RANGE, CLOG_RANGE, HLOG_RANGE, SLOG_RANGE, MML_RANGE, TLEN_RANGE, STRT_RANGE, FADT_RANGE };

/* ZSTD_cctxSetParameter() index to set */
static const ZSTD_cParameter cctxSetParamTable[NUM_PARAMS] =
        { ZSTD_c_windowLog, ZSTD_c_chainLog, ZSTD_c_hashLog, ZSTD_c_searchLog, ZSTD_c_minMatch, ZSTD_c_targetLength, ZSTD_c_strategy, ZSTD_c_forceAttachDict };

/* names of parameters */
static const char* g_paramNames[NUM_PARAMS] =
        { "windowLog", "chainLog", "hashLog","searchLog", "minMatch", "targetLength", "strategy", "forceAttachDict" };

/* shortened names of parameters */
static const char* g_shortParamNames[NUM_PARAMS] =
        { "wlog", "clog", "hlog", "slog", "mml", "tlen", "strat", "fadt" };

/* maps value from { 0 to rangetable[param] - 1 } to valid paramvalues */
static U32 rangeMap(varInds_t param, int ind)
{
    U32 const uind = (U32)MAX(MIN(ind, (int)rangetable[param] - 1), 0);
    switch(param) {
        case wlog_ind: /* using default: triggers -Wswitch-enum */
        case clog_ind:
        case hlog_ind:
        case slog_ind:
        case mml_ind:
        case strt_ind:
            return mintable[param] + uind;
        case tlen_ind:
            return tlen_table[uind];
        case fadt_ind: /* 0, 1, 2 -> -1, 0, 1 */
            return uind - 1;
        case NUM_PARAMS:
        default:;
    }
    DISPLAY("Error, not a valid param\n ");
    assert(0);
    return (U32)-1;
}

/* inverse of rangeMap */
static int invRangeMap(varInds_t param, U32 value)
{
    value = MIN(MAX(mintable[param], value), maxtable[param]);
    switch(param) {
        case wlog_ind:
        case clog_ind:
        case hlog_ind:
        case slog_ind:
        case mml_ind:
        case strt_ind:
            return (int)(value - mintable[param]);
        case tlen_ind: /* bin search */
        {
            int lo = 0;
            int hi = TLEN_RANGE;
            while(lo < hi) {
                int mid = (lo + hi) / 2;
                if(tlen_table[mid] < value) {
                    lo = mid + 1;
                } if(tlen_table[mid] == value) {
                    return mid;
                } else {
                    hi = mid;
                }
            }
            return lo;
        }
        case fadt_ind:
            return (int)value + 1;
        case NUM_PARAMS:
        default:;
    }
    DISPLAY("Error, not a valid param\n ");
    assert(0);
    return -2;
}

/* display of params */
static void displayParamVal(FILE* f, varInds_t param, unsigned value, int width)
{
    switch(param) {
        case wlog_ind:
        case clog_ind:
        case hlog_ind:
        case slog_ind:
        case mml_ind:
        case tlen_ind:
            if(width) {
                fprintf(f, "%*u", width, value);
            } else {
                fprintf(f, "%u", value);
            }
            break;
        case strt_ind:
            if(width) {
                fprintf(f, "%*s", width, g_stratName[value]);
            } else {
                fprintf(f, "%s", g_stratName[value]);
            }
            break;
        case fadt_ind:   /* force attach dict */
            if(width) {
                fprintf(f, "%*d", width, (int)value);
            } else {
                fprintf(f, "%d", (int)value);
            }
            break;
        case NUM_PARAMS:
        default:
            DISPLAY("Error, not a valid param\n ");
            assert(0);
            break;
    }
}


/*-************************************
*  Benchmark Parameters/Global Variables
**************************************/

/* General Utility */
static U32 g_timeLimit_s = 99999;   /* about 27 hours */
static UTIL_time_t g_time; /* to be used to compare solution finding speeds to compare to original */
static U32 g_blockSize = 0;
static U32 g_rand = 1;

/* Display */
static int g_displayLevel = 3;
static BYTE g_silenceParams[NUM_PARAMS];   /* can selectively silence some params when displaying them */

/* Mode Selection */
static U32 g_singleRun = 0;
static U32 g_optimizer = 0;
static int g_optmode = 0;

/* For cLevel Table generation */
static U32 g_target = 0;
static U32 g_noSeed = 0;

/* For optimizer */
static paramValues_t g_params; /* Initialized at the beginning of main w/ emptyParams() function */
static double g_ratioMultiplier = 5.;
static U32 g_strictness = PARAM_UNSET; /* range 1 - 100, measure of how strict  */
static BMK_benchResult_t g_lvltarget;

typedef enum {
    directMap,
    xxhashMap,
    noMemo
} memoTableType_t;

typedef struct {
    memoTableType_t tableType;
    BYTE* table;
    size_t tableLen;
    varInds_t varArray[NUM_PARAMS];
    size_t varLen;
} memoTable_t;

typedef struct {
    BMK_benchResult_t result;
    paramValues_t params;
} winnerInfo_t;

typedef struct {
    U32 cSpeed;  /* bytes / sec */
    U32 dSpeed;
    U32 cMem;    /* bytes */
} constraint_t;

typedef struct winner_ll_node winner_ll_node;
struct winner_ll_node {
    winnerInfo_t res;
    winner_ll_node* next;
};

static winner_ll_node* g_winners; /* linked list sorted ascending by cSize & cSpeed */

/*
 * Additional Global Variables (Defined Above Use)
 * g_level_constraint
 * g_alreadyTested
 * g_maxTries
 * g_clockGranularity
 */


/*-*******************************************************
*  General Util Functions
*********************************************************/

/* nullified useless params, to ensure count stats */
/* cleans up params for memoizing / display */
static paramValues_t sanitizeParams(paramValues_t params)
{
    if (params.vals[strt_ind] == ZSTD_fast)
        params.vals[clog_ind] = 0, params.vals[slog_ind] = 0;
    if (params.vals[strt_ind] == ZSTD_dfast)
        params.vals[slog_ind] = 0;
    if ( (params.vals[strt_ind] < ZSTD_btopt) && (params.vals[strt_ind] != ZSTD_fast) )
        params.vals[tlen_ind] = 0;

    return params;
}

static ZSTD_compressionParameters pvalsToCParams(paramValues_t p)
{
    ZSTD_compressionParameters c;
    memset(&c, 0, sizeof(ZSTD_compressionParameters));
    c.windowLog = p.vals[wlog_ind];
    c.chainLog = p.vals[clog_ind];
    c.hashLog = p.vals[hlog_ind];
    c.searchLog = p.vals[slog_ind];
    c.minMatch = p.vals[mml_ind];
    c.targetLength = p.vals[tlen_ind];
    c.strategy = p.vals[strt_ind];
    /* no forceAttachDict */
    return c;
}

static paramValues_t cParamsToPVals(ZSTD_compressionParameters c)
{
    paramValues_t p;
    varInds_t i;
    p.vals[wlog_ind] = c.windowLog;
    p.vals[clog_ind] = c.chainLog;
    p.vals[hlog_ind] = c.hashLog;
    p.vals[slog_ind] = c.searchLog;
    p.vals[mml_ind]  = c.minMatch;
    p.vals[tlen_ind] = c.targetLength;
    p.vals[strt_ind] = c.strategy;

    /* set all other params to their minimum value */
    for (i = strt_ind + 1; i < NUM_PARAMS; i++) {
        p.vals[i] = mintable[i];
    }
    return p;
}

/* equivalent of ZSTD_adjustCParams for paramValues_t */
static paramValues_t
adjustParams(paramValues_t p, const size_t maxBlockSize, const size_t dictSize)
{
    paramValues_t ot = p;
    varInds_t i;
    p = cParamsToPVals(ZSTD_adjustCParams(pvalsToCParams(p), maxBlockSize, dictSize));
    if (!dictSize) { p.vals[fadt_ind] = 0; }
    /* retain value of all other parameters */
    for(i = strt_ind + 1; i < NUM_PARAMS; i++) {
        p.vals[i] = ot.vals[i];
    }
    return p;
}

static size_t BMK_findMaxMem(U64 requiredMem)
{
    size_t const step = 64 MB;
    void* testmem = NULL;

    requiredMem = (((requiredMem >> 26) + 1) << 26);
    if (requiredMem > maxMemory) requiredMem = maxMemory;

    requiredMem += 2 * step;
    while (!testmem && requiredMem > 0) {
        testmem = malloc ((size_t)requiredMem);
        requiredMem -= step;
    }

    free (testmem);
    return (size_t) requiredMem;
}

/* accuracy in seconds only, span can be multiple years */
static U32 BMK_timeSpan_s(const UTIL_time_t tStart)
{
    return (U32)(UTIL_clockSpanMicro(tStart) / 1000000ULL);
}

static U32 FUZ_rotl32(U32 x, U32 r)
{
    return ((x << r) | (x >> (32 - r)));
}

static U32 FUZ_rand(U32* src)
{
    const U32 prime1 = 2654435761U;
    const U32 prime2 = 2246822519U;
    U32 rand32 = *src;
    rand32 *= prime1;
    rand32 += prime2;
    rand32  = FUZ_rotl32(rand32, 13);
    *src = rand32;
    return rand32 >> 5;
}

#define BOUNDCHECK(val,min,max) {                     \
    if (((val)<(min)) | ((val)>(max))) {              \
        DISPLAY("INVALID PARAMETER CONSTRAINTS\n");   \
        return 0;                                     \
}   }

static int paramValid(const paramValues_t paramTarget)
{
    U32 i;
    for(i = 0; i < NUM_PARAMS; i++) {
        BOUNDCHECK(paramTarget.vals[i], mintable[i], maxtable[i]);
    }
    return 1;
}

/* cParamUnsetMin() :
 * if any parameter in paramTarget is not yet set,
 * it will receive its corresponding minimal value.
 * This function never fails */
static paramValues_t cParamUnsetMin(paramValues_t paramTarget)
{
    varInds_t vi;
    for (vi = 0; vi < NUM_PARAMS; vi++) {
        if (paramTarget.vals[vi] == PARAM_UNSET) {
            paramTarget.vals[vi] = mintable[vi];
        }
    }
    return paramTarget;
}

static paramValues_t emptyParams(void)
{
    U32 i;
    paramValues_t p;
    for(i = 0; i < NUM_PARAMS; i++) {
        p.vals[i] = PARAM_UNSET;
    }
    return p;
}

static winnerInfo_t initWinnerInfo(const paramValues_t p)
{
    winnerInfo_t w1;
    w1.result.cSpeed = 0;
    w1.result.dSpeed = 0;
    w1.result.cMem = (size_t)-1;
    w1.result.cSize = (size_t)-1;
    w1.params = p;
    return w1;
}

static paramValues_t
overwriteParams(paramValues_t base, const paramValues_t mask)
{
    U32 i;
    for(i = 0; i < NUM_PARAMS; i++) {
        if(mask.vals[i] != PARAM_UNSET) {
            base.vals[i] = mask.vals[i];
        }
    }
    return base;
}

static void
paramVaryOnce(const varInds_t paramIndex, const int amt, paramValues_t* ptr)
{
    ptr->vals[paramIndex] = rangeMap(paramIndex,
                                     invRangeMap(paramIndex, ptr->vals[paramIndex]) + amt);
}

/* varies ptr by nbChanges respecting varyParams*/
static void
paramVariation(paramValues_t* ptr, memoTable_t* mtAll, const U32 nbChanges)
{
    paramValues_t p;
    int validated = 0;
    while (!validated) {
        U32 i;
        p = *ptr;
        for (i = 0 ; i < nbChanges ; i++) {
            const U32 changeID = (U32)FUZ_rand(&g_rand) % (mtAll[p.vals[strt_ind]].varLen << 1);
            paramVaryOnce(mtAll[p.vals[strt_ind]].varArray[changeID >> 1],
                          (int)((changeID & 1) << 1) - 1,
                          &p);
        }
        validated = paramValid(p);
    }
    *ptr = p;
}

/* Completely random parameter selection */
static paramValues_t randomParams(void)
{
    varInds_t v; paramValues_t p;
    for(v = 0; v < NUM_PARAMS; v++) {
        p.vals[v] = rangeMap(v, (int)(FUZ_rand(&g_rand) % rangetable[v]));
    }
    return p;
}

static U64 g_clockGranularity = 100000000ULL;

static void init_clockGranularity(void)
{
    UTIL_time_t const clockStart = UTIL_getTime();
    U64 el1 = 0, el2 = 0;
    int i = 0;
    do {
        el1 = el2;
        el2 = UTIL_clockSpanNano(clockStart);
        if(el1 < el2) {
            U64 iv = el2 - el1;
            if(g_clockGranularity > iv) {
                g_clockGranularity = iv;
                i = 0;
            } else {
                i++;
            }
        }
    } while(i < 10);
    DEBUGOUTPUT("Granularity: %llu\n", (unsigned long long)g_clockGranularity);
}

/*-************************************
*  Optimizer Util Functions
**************************************/

/* checks results are feasible */
static int feasible(const BMK_benchResult_t results, const constraint_t target) {
    return (results.cSpeed >= target.cSpeed)
        && (results.dSpeed >= target.dSpeed)
        && (results.cMem <= target.cMem)
        && (!g_optmode || results.cSize <= g_lvltarget.cSize);
}

/* hill climbing value for part 1 */
/* Scoring here is a linear reward for all set constraints normalized between 0 and 1
 * (with 0 at 0 and 1 being fully fulfilling the constraint), summed with a logarithmic
 * bonus to exceeding the constraint value. We also give linear ratio for compression ratio.
 * The constant factors are experimental.
 */
static double
resultScore(const BMK_benchResult_t res, const size_t srcSize, const constraint_t target)
{
    double cs = 0., ds = 0., rt, cm = 0.;
    const double r1 = 1, r2 = 0.1, rtr = 0.5;
    double ret;
    if(target.cSpeed) { cs = (double)res.cSpeed / (double)target.cSpeed; }
    if(target.dSpeed) { ds = (double)res.dSpeed / (double)target.dSpeed; }
    if(target.cMem != (U32)-1) { cm = (double)target.cMem / (double)res.cMem; }
    rt = ((double)srcSize / (double)res.cSize);

    ret = (MIN(1, cs) + MIN(1, ds)  + MIN(1, cm))*r1 + rt * rtr +
         (MAX(0, log(cs))+ MAX(0, log(ds))+ MAX(0, log(cm))) * r2;

    return ret;
}

/* calculates normalized squared euclidean distance of result1 if it is in the first quadrant relative to lvlRes */
static double
resultDistLvl(const BMK_benchResult_t result1, const BMK_benchResult_t lvlRes)
{
    double normalizedCSpeedGain1 = ((double)result1.cSpeed / (double)lvlRes.cSpeed) - 1;
    double normalizedRatioGain1 = ((double)lvlRes.cSize / (double)result1.cSize) - 1;
    if(normalizedRatioGain1 < 0 || normalizedCSpeedGain1 < 0) {
        return 0.0;
    }
    return normalizedRatioGain1 * g_ratioMultiplier + normalizedCSpeedGain1;
}

/* return true if r2 strictly better than r1 */
static int
compareResultLT(const BMK_benchResult_t result1, const BMK_benchResult_t result2, const constraint_t target, size_t srcSize)
{
    if(feasible(result1, target) && feasible(result2, target)) {
        if(g_optmode) {
            return resultDistLvl(result1, g_lvltarget) < resultDistLvl(result2, g_lvltarget);
        } else {
            return (result1.cSize > result2.cSize)
                || (result1.cSize == result2.cSize && result2.cSpeed > result1.cSpeed)
                || (result1.cSize == result2.cSize && result2.cSpeed == result1.cSpeed && result2.dSpeed > result1.dSpeed);
        }
    }
    return feasible(result2, target)
        || (!feasible(result1, target)
            && (resultScore(result1, srcSize, target) < resultScore(result2, srcSize, target)));
}

static constraint_t relaxTarget(constraint_t target) {
    target.cMem = (U32)-1;
    target.cSpeed = (target.cSpeed * g_strictness) / 100;
    target.dSpeed = (target.dSpeed * g_strictness) / 100;
    return target;
}

static void optimizerAdjustInput(paramValues_t* pc, const size_t maxBlockSize)
{
    varInds_t v;
    for(v = 0; v < NUM_PARAMS; v++) {
        if(pc->vals[v] != PARAM_UNSET) {
            U32 newval = MIN(MAX(pc->vals[v], mintable[v]), maxtable[v]);
            if(newval != pc->vals[v]) {
                pc->vals[v] = newval;
                DISPLAY("Warning: parameter %s not in valid range, adjusting to ",
                        g_paramNames[v]);
                displayParamVal(stderr, v, newval, 0); DISPLAY("\n");
            }
        }
    }

    if(pc->vals[wlog_ind] != PARAM_UNSET) {

        U32 sshb = maxBlockSize > 1 ? ZSTD_highbit32((U32)(maxBlockSize-1)) + 1 : 1;
        /* edge case of highBit not working for 0 */

        if(maxBlockSize < (1ULL << 31) && sshb + 1 < pc->vals[wlog_ind]) {
            U32 adjust = MAX(mintable[wlog_ind], sshb);
            if(adjust != pc->vals[wlog_ind]) {
                pc->vals[wlog_ind] = adjust;
                DISPLAY("Warning: windowLog larger than src/block size, adjusted to %u\n",
                        (unsigned)pc->vals[wlog_ind]);
            }
        }
    }

    if(pc->vals[wlog_ind] != PARAM_UNSET && pc->vals[clog_ind] != PARAM_UNSET) {
        U32 maxclog;
        if(pc->vals[strt_ind] == PARAM_UNSET || pc->vals[strt_ind] >= (U32)ZSTD_btlazy2) {
            maxclog = pc->vals[wlog_ind] + 1;
        } else {
            maxclog = pc->vals[wlog_ind];
        }

        if(pc->vals[clog_ind] > maxclog) {
            pc->vals[clog_ind] = maxclog;
            DISPLAY("Warning: chainlog too much larger than windowLog size, adjusted to %u\n",
                    (unsigned)pc->vals[clog_ind]);
        }
    }

    if(pc->vals[wlog_ind] != PARAM_UNSET && pc->vals[hlog_ind] != PARAM_UNSET) {
        if(pc->vals[wlog_ind] + 1 < pc->vals[hlog_ind]) {
            pc->vals[hlog_ind] = pc->vals[wlog_ind] + 1;
            DISPLAY("Warning: hashlog too much larger than windowLog size, adjusted to %u\n",
                    (unsigned)pc->vals[hlog_ind]);
        }
    }

    if(pc->vals[slog_ind] != PARAM_UNSET && pc->vals[clog_ind] != PARAM_UNSET) {
        if(pc->vals[slog_ind] > pc->vals[clog_ind]) {
            pc->vals[clog_ind] = pc->vals[slog_ind];
            DISPLAY("Warning: searchLog larger than chainLog, adjusted to %u\n",
                    (unsigned)pc->vals[slog_ind]);
        }
    }
}

static int
redundantParams(const paramValues_t paramValues, const constraint_t target, const size_t maxBlockSize)
{
    return
       (ZSTD_estimateCStreamSize_usingCParams(pvalsToCParams(paramValues)) > (size_t)target.cMem) /* Uses too much memory */
    || ((1ULL << (paramValues.vals[wlog_ind] - 1)) >= maxBlockSize && paramValues.vals[wlog_ind] != mintable[wlog_ind]) /* wlog too much bigger than src size */
    || (paramValues.vals[clog_ind] > (paramValues.vals[wlog_ind] + (paramValues.vals[strt_ind] > ZSTD_btlazy2))) /* chainLog larger than windowLog*/
    || (paramValues.vals[slog_ind] > paramValues.vals[clog_ind]) /* searchLog larger than chainLog */
    || (paramValues.vals[hlog_ind] > paramValues.vals[wlog_ind] + 1); /* hashLog larger than windowLog + 1 */
}


/*-************************************
*  Display Functions
**************************************/

/* BMK_paramValues_into_commandLine() :
 * transform a set of parameters paramValues_t
 * into a command line compatible with `zstd` syntax
 * and writes it into FILE* f.
 * f must be already opened and writable */
static void
BMK_paramValues_into_commandLine(FILE* f, const paramValues_t params)
{
    varInds_t v;
    int first = 1;
    fprintf(f,"--zstd=");
    for (v = 0; v < NUM_PARAMS; v++) {
        if (g_silenceParams[v]) { continue; }
        if (!first) { fprintf(f, ","); }
        fprintf(f,"%s=", g_paramNames[v]);

        if (v == strt_ind) { fprintf(f,"%u", (unsigned)params.vals[v]); }
        else { displayParamVal(f, v, params.vals[v], 0); }
        first = 0;
    }
    fprintf(f, "\n");
}


/* comparison function: */
/* strictly better, strictly worse, equal, speed-side adv, size-side adv */
#define WORSE_RESULT 0
#define BETTER_RESULT 1
#define ERROR_RESULT 2

#define SPEED_RESULT 4
#define SIZE_RESULT 5
/* maybe have epsilon-eq to limit table size? */
static int
speedSizeCompare(const BMK_benchResult_t r1, const BMK_benchResult_t r2)
{
    if(r1.cSpeed < r2.cSpeed) {
        if(r1.cSize >= r2.cSize) {
            return BETTER_RESULT;
        }
        return SPEED_RESULT; /* r2 is smaller but not faster. */
    } else {
        if(r1.cSize <= r2.cSize) {
            return WORSE_RESULT;
        }
        return SIZE_RESULT; /* r2 is faster but not smaller */
    }
}

/* 0 for insertion, 1 for no insert */
/* maintain invariant speedSizeCompare(n, n->next) = SPEED_RESULT */
static int
insertWinner(const winnerInfo_t w, const constraint_t targetConstraints)
{
    BMK_benchResult_t r = w.result;
    winner_ll_node* cur_node = g_winners;
    /* first node to insert */
    if(!feasible(r, targetConstraints)) {
        return 1;
    }

    if(g_winners == NULL) {
        winner_ll_node* first_node = malloc(sizeof(winner_ll_node));
        if(first_node == NULL) {
            return 1;
        }
        first_node->next = NULL;
        first_node->res = w;
        g_winners = first_node;
        return 0;
    }

    while(cur_node->next != NULL) {
        switch(speedSizeCompare(cur_node->res.result, r)) {
            case WORSE_RESULT:
            {
                return 1; /* never insert if better */
            }
            case BETTER_RESULT:
            {
                winner_ll_node* tmp;
                cur_node->res = cur_node->next->res;
                tmp = cur_node->next;
                cur_node->next = cur_node->next->next;
                free(tmp);
                break;
            }
            case SIZE_RESULT:
            {
                cur_node = cur_node->next;
                break;
            }
            case SPEED_RESULT: /* insert after first size result, then return */
            {
                winner_ll_node* newnode = malloc(sizeof(winner_ll_node));
                if(newnode == NULL) {
                    return 1;
                }
                newnode->res = cur_node->res;
                cur_node->res = w;
                newnode->next = cur_node->next;
                cur_node->next = newnode;
                return 0;
            }
        }

    }

    assert(cur_node->next == NULL);
    switch(speedSizeCompare(cur_node->res.result, r)) {
        case WORSE_RESULT:
        {
            return 1; /* never insert if better */
        }
        case BETTER_RESULT:
        {
            cur_node->res = w;
            return 0;
        }
        case SIZE_RESULT:
        {
            winner_ll_node* newnode = malloc(sizeof(winner_ll_node));
            if(newnode == NULL) {
                return 1;
            }
            newnode->res = w;
            newnode->next = NULL;
            cur_node->next = newnode;
            return 0;
        }
        case SPEED_RESULT: /* insert before first size result, then return */
        {
            winner_ll_node* newnode = malloc(sizeof(winner_ll_node));
            if(newnode == NULL) {
                return 1;
            }
            newnode->res = cur_node->res;
            cur_node->res = w;
            newnode->next = cur_node->next;
            cur_node->next = newnode;
            return 0;
        }
        default:
            return 1;
    }
}

static void
BMK_displayOneResult(FILE* f, winnerInfo_t res, const size_t srcSize)
{
    varInds_t v;
    int first = 1;
    res.params = cParamUnsetMin(res.params);
    fprintf(f, "    {");
    for (v = 0; v < NUM_PARAMS; v++) {
        if (g_silenceParams[v]) { continue; }
        if (!first) { fprintf(f, ","); }
        displayParamVal(f, v, res.params.vals[v], 3);
        first = 0;
    }

    {   double const ratio = res.result.cSize ?
                            (double)srcSize / (double)res.result.cSize : 0;
        double const cSpeedMBps = (double)res.result.cSpeed / MB_UNIT;
        double const dSpeedMBps = (double)res.result.dSpeed / MB_UNIT;

        fprintf(f, " },     /* R:%5.3f at %5.1f MB/s - %5.1f MB/s */\n",
                            ratio, cSpeedMBps, dSpeedMBps);
    }
}

/* Writes to f the results of a parameter benchmark */
/* when used with --optimize, will only print results better than previously discovered */
static void
BMK_printWinner(FILE* f, const int cLevel, const BMK_benchResult_t result, const paramValues_t params, const size_t srcSize)
{
    char lvlstr[15] = "Custom Level";
    winnerInfo_t w;
    w.params = params;
    w.result = result;

    fprintf(f, "\r%79s\r", "");

    if(cLevel != CUSTOM_LEVEL) {
        snprintf(lvlstr, 15, "  Level %2d  ", cLevel);
    }

    if(TIMED) {
        const U64 mn_in_ns = 60ULL * TIMELOOP_NANOSEC;
        const U64 time_ns = UTIL_clockSpanNano(g_time);
        const U64 minutes = time_ns / mn_in_ns;
        fprintf(f, "%1lu:%2lu:%05.2f - ",
                (unsigned long) minutes / 60,
                (unsigned long) minutes % 60,
                (double)(time_ns - (minutes * mn_in_ns)) / TIMELOOP_NANOSEC );
    }

    fprintf(f, "/* %s */   ", lvlstr);
    BMK_displayOneResult(f, w, srcSize);
}

static void
BMK_printWinnerOpt(FILE* f, const U32 cLevel, const BMK_benchResult_t result, const paramValues_t params, const constraint_t targetConstraints, const size_t srcSize)
{
    /* global winner used for constraints */
                                    /* cSize, cSpeed, dSpeed, cMem */
    static winnerInfo_t g_winner = { { (size_t)-1LL, 0, 0, (size_t)-1LL },
                                     { { PARAM_UNSET, PARAM_UNSET, PARAM_UNSET, PARAM_UNSET, PARAM_UNSET, PARAM_UNSET, PARAM_UNSET, PARAM_UNSET } }
                                   };
    if ( DEBUG
      || compareResultLT(g_winner.result, result, targetConstraints, srcSize)
      || g_displayLevel >= 4) {
        if ( DEBUG
          && compareResultLT(g_winner.result, result, targetConstraints, srcSize)) {
            DISPLAY("New Winner: \n");
        }

        if(g_displayLevel >= 2) {
            BMK_printWinner(f, cLevel, result, params, srcSize);
        }

        if(compareResultLT(g_winner.result, result, targetConstraints, srcSize)) {
            if(g_displayLevel >= 1) { BMK_paramValues_into_commandLine(f, params); }
            g_winner.result = result;
            g_winner.params = params;
        }
    }

    if(g_optmode && g_optimizer && (DEBUG || g_displayLevel == 3)) {
        winnerInfo_t w;
        winner_ll_node* n;
        w.result = result;
        w.params = params;
        insertWinner(w, targetConstraints);

        if(!DEBUG) { fprintf(f, "\033c"); }
        fprintf(f, "\n");

        /* the table */
        fprintf(f, "================================\n");
        for(n = g_winners; n != NULL; n = n->next) {
            BMK_displayOneResult(f, n->res, srcSize);
        }
        fprintf(f, "================================\n");
        fprintf(f, "Level Bounds: R: > %.3f AND C: < %.1f MB/s \n\n",
            (double)srcSize / (double)g_lvltarget.cSize, (double)g_lvltarget.cSpeed / MB_UNIT);


        fprintf(f, "Overall Winner: \n");
        BMK_displayOneResult(f, g_winner, srcSize);
        BMK_paramValues_into_commandLine(f, g_winner.params);

        fprintf(f, "Latest BMK: \n");\
        BMK_displayOneResult(f, w, srcSize);
    }
}


/* BMK_print_cLevelEntry() :
 * Writes one cLevelTable entry, for one level.
 * f must exist, be already opened, and be seekable.
 * this function cannot error.
 */
static void
BMK_print_cLevelEntry(FILE* f, const int cLevel,
                      paramValues_t params,
                      const BMK_benchResult_t result, const size_t srcSize)
{
    varInds_t v;
    int first = 1;

    assert(cLevel >= 0);
    assert(cLevel <= NB_LEVELS_TRACKED);
    params = cParamUnsetMin(params);

    fprintf(f, "   {");
    /* print cParams.
     * assumption : all cParams are present and in order in the following range */
    for (v = 0; v <= strt_ind; v++) {
        if (!first) { fprintf(f, ","); }
        displayParamVal(f, v, params.vals[v], 3);
        first = 0;
    }
    /* print comment */
    {   double const ratio = result.cSize ?
                            (double)srcSize / (double)result.cSize : 0;
        double const cSpeedMBps = (double)result.cSpeed / MB_UNIT;
        double const dSpeedMBps = (double)result.dSpeed / MB_UNIT;

        fprintf(f, " },   /* level %2i:  R=%5.3f at %5.1f MB/s - %5.1f MB/s */\n",
                             cLevel, ratio, cSpeedMBps, dSpeedMBps);
    }
}


/* BMK_print_cLevelTable() :
 * print candidate compression table into proposed FILE* f.
 * f must exist, be already opened, and be seekable.
 * winners must be a table of NB_LEVELS_TRACKED+1 elements winnerInfo_t, all entries presumed initialized
 * this function cannot error.
 */
static void
BMK_print_cLevelTable(FILE* f, const winnerInfo_t* winners, const size_t srcSize)
{
    int cLevel;