static size_t ZDICT_analyzeEntropy()

in lib/dictBuilder/zdict.c [654:837]


static size_t ZDICT_analyzeEntropy(void*  dstBuffer, size_t maxDstSize,
                                   int compressionLevel,
                             const void*  srcBuffer, const size_t* fileSizes, unsigned nbFiles,
                             const void* dictBuffer, size_t  dictBufferSize,
                                   unsigned notificationLevel)
{
    unsigned countLit[256];
    HUF_CREATE_STATIC_CTABLE(hufTable, 255);
    unsigned offcodeCount[OFFCODE_MAX+1];
    short offcodeNCount[OFFCODE_MAX+1];
    U32 offcodeMax = ZSTD_highbit32((U32)(dictBufferSize + 128 KB));
    unsigned matchLengthCount[MaxML+1];
    short matchLengthNCount[MaxML+1];
    unsigned litLengthCount[MaxLL+1];
    short litLengthNCount[MaxLL+1];
    U32 repOffset[MAXREPOFFSET];
    offsetCount_t bestRepOffset[ZSTD_REP_NUM+1];
    EStats_ress_t esr = { NULL, NULL, NULL };
    ZSTD_parameters params;
    U32 u, huffLog = 11, Offlog = OffFSELog, mlLog = MLFSELog, llLog = LLFSELog, total;
    size_t pos = 0, errorCode;
    size_t eSize = 0;
    size_t const totalSrcSize = ZDICT_totalSampleSize(fileSizes, nbFiles);
    size_t const averageSampleSize = totalSrcSize / (nbFiles + !nbFiles);
    BYTE* dstPtr = (BYTE*)dstBuffer;

    /* init */
    DEBUGLOG(4, "ZDICT_analyzeEntropy");
    if (offcodeMax>OFFCODE_MAX) { eSize = ERROR(dictionaryCreation_failed); goto _cleanup; }   /* too large dictionary */
    for (u=0; u<256; u++) countLit[u] = 1;   /* any character must be described */
    for (u=0; u<=offcodeMax; u++) offcodeCount[u] = 1;
    for (u=0; u<=MaxML; u++) matchLengthCount[u] = 1;
    for (u=0; u<=MaxLL; u++) litLengthCount[u] = 1;
    memset(repOffset, 0, sizeof(repOffset));
    repOffset[1] = repOffset[4] = repOffset[8] = 1;
    memset(bestRepOffset, 0, sizeof(bestRepOffset));
    if (compressionLevel==0) compressionLevel = ZSTD_CLEVEL_DEFAULT;
    params = ZSTD_getParams(compressionLevel, averageSampleSize, dictBufferSize);

    esr.dict = ZSTD_createCDict_advanced(dictBuffer, dictBufferSize, ZSTD_dlm_byRef, ZSTD_dct_rawContent, params.cParams, ZSTD_defaultCMem);
    esr.zc = ZSTD_createCCtx();
    esr.workPlace = malloc(ZSTD_BLOCKSIZE_MAX);
    if (!esr.dict || !esr.zc || !esr.workPlace) {
        eSize = ERROR(memory_allocation);
        DISPLAYLEVEL(1, "Not enough memory \n");
        goto _cleanup;
    }

    /* collect stats on all samples */
    for (u=0; u<nbFiles; u++) {
        ZDICT_countEStats(esr, &params,
                          countLit, offcodeCount, matchLengthCount, litLengthCount, repOffset,
                         (const char*)srcBuffer + pos, fileSizes[u],
                          notificationLevel);
        pos += fileSizes[u];
    }

    if (notificationLevel >= 4) {
        /* writeStats */
        DISPLAYLEVEL(4, "Offset Code Frequencies : \n");
        for (u=0; u<=offcodeMax; u++) {
            DISPLAYLEVEL(4, "%2u :%7u \n", u, offcodeCount[u]);
    }   }

    /* analyze, build stats, starting with literals */
    {   size_t maxNbBits = HUF_buildCTable (hufTable, countLit, 255, huffLog);
        if (HUF_isError(maxNbBits)) {
            eSize = maxNbBits;
            DISPLAYLEVEL(1, " HUF_buildCTable error \n");
            goto _cleanup;
        }
        if (maxNbBits==8) {  /* not compressible : will fail on HUF_writeCTable() */
            DISPLAYLEVEL(2, "warning : pathological dataset : literals are not compressible : samples are noisy or too regular \n");
            ZDICT_flatLit(countLit);  /* replace distribution by a fake "mostly flat but still compressible" distribution, that HUF_writeCTable() can encode */
            maxNbBits = HUF_buildCTable (hufTable, countLit, 255, huffLog);
            assert(maxNbBits==9);
        }
        huffLog = (U32)maxNbBits;
    }

    /* looking for most common first offsets */
    {   U32 offset;
        for (offset=1; offset<MAXREPOFFSET; offset++)
            ZDICT_insertSortCount(bestRepOffset, offset, repOffset[offset]);
    }
    /* note : the result of this phase should be used to better appreciate the impact on statistics */

    total=0; for (u=0; u<=offcodeMax; u++) total+=offcodeCount[u];
    errorCode = FSE_normalizeCount(offcodeNCount, Offlog, offcodeCount, total, offcodeMax, /* useLowProbCount */ 1);
    if (FSE_isError(errorCode)) {
        eSize = errorCode;
        DISPLAYLEVEL(1, "FSE_normalizeCount error with offcodeCount \n");
        goto _cleanup;
    }
    Offlog = (U32)errorCode;

    total=0; for (u=0; u<=MaxML; u++) total+=matchLengthCount[u];
    errorCode = FSE_normalizeCount(matchLengthNCount, mlLog, matchLengthCount, total, MaxML, /* useLowProbCount */ 1);
    if (FSE_isError(errorCode)) {
        eSize = errorCode;
        DISPLAYLEVEL(1, "FSE_normalizeCount error with matchLengthCount \n");
        goto _cleanup;
    }
    mlLog = (U32)errorCode;

    total=0; for (u=0; u<=MaxLL; u++) total+=litLengthCount[u];
    errorCode = FSE_normalizeCount(litLengthNCount, llLog, litLengthCount, total, MaxLL, /* useLowProbCount */ 1);
    if (FSE_isError(errorCode)) {
        eSize = errorCode;
        DISPLAYLEVEL(1, "FSE_normalizeCount error with litLengthCount \n");
        goto _cleanup;
    }
    llLog = (U32)errorCode;

    /* write result to buffer */
    {   size_t const hhSize = HUF_writeCTable(dstPtr, maxDstSize, hufTable, 255, huffLog);
        if (HUF_isError(hhSize)) {
            eSize = hhSize;
            DISPLAYLEVEL(1, "HUF_writeCTable error \n");
            goto _cleanup;
        }
        dstPtr += hhSize;
        maxDstSize -= hhSize;
        eSize += hhSize;
    }

    {   size_t const ohSize = FSE_writeNCount(dstPtr, maxDstSize, offcodeNCount, OFFCODE_MAX, Offlog);
        if (FSE_isError(ohSize)) {
            eSize = ohSize;
            DISPLAYLEVEL(1, "FSE_writeNCount error with offcodeNCount \n");
            goto _cleanup;
        }
        dstPtr += ohSize;
        maxDstSize -= ohSize;
        eSize += ohSize;
    }

    {   size_t const mhSize = FSE_writeNCount(dstPtr, maxDstSize, matchLengthNCount, MaxML, mlLog);
        if (FSE_isError(mhSize)) {
            eSize = mhSize;
            DISPLAYLEVEL(1, "FSE_writeNCount error with matchLengthNCount \n");
            goto _cleanup;
        }
        dstPtr += mhSize;
        maxDstSize -= mhSize;
        eSize += mhSize;
    }

    {   size_t const lhSize = FSE_writeNCount(dstPtr, maxDstSize, litLengthNCount, MaxLL, llLog);
        if (FSE_isError(lhSize)) {
            eSize = lhSize;
            DISPLAYLEVEL(1, "FSE_writeNCount error with litlengthNCount \n");
            goto _cleanup;
        }
        dstPtr += lhSize;
        maxDstSize -= lhSize;
        eSize += lhSize;
    }

    if (maxDstSize<12) {
        eSize = ERROR(dstSize_tooSmall);
        DISPLAYLEVEL(1, "not enough space to write RepOffsets \n");
        goto _cleanup;
    }
# if 0
    MEM_writeLE32(dstPtr+0, bestRepOffset[0].offset);
    MEM_writeLE32(dstPtr+4, bestRepOffset[1].offset);
    MEM_writeLE32(dstPtr+8, bestRepOffset[2].offset);
#else
    /* at this stage, we don't use the result of "most common first offset",
     * as the impact of statistics is not properly evaluated */
    MEM_writeLE32(dstPtr+0, repStartValue[0]);
    MEM_writeLE32(dstPtr+4, repStartValue[1]);
    MEM_writeLE32(dstPtr+8, repStartValue[2]);
#endif
    eSize += 12;

_cleanup:
    ZSTD_freeCDict(esr.dict);
    ZSTD_freeCCtx(esr.zc);
    free(esr.workPlace);

    return eSize;
}