/*

 * Copyright (c) 2016-present, Yann Collet, Facebook, Inc.

 * 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).

 */

#include "zstd_ldm.h"

#include "debug.h"

#include "zstd_fast.h"          /* ZSTD_fillHashTable() */

#include "zstd_double_fast.h"   /* ZSTD_fillDoubleHashTable() */

#define LDM_BUCKET_SIZE_LOG 3

#define LDM_MIN_MATCH_LENGTH 64

#define LDM_HASH_RLOG 7

#define LDM_HASH_CHAR_OFFSET 10

void ZSTD_ldm_adjustParameters(ldmParams_t* params,

                               ZSTD_compressionParameters const* cParams)

{

    params->windowLog = cParams->windowLog;

    ZSTD_STATIC_ASSERT(LDM_BUCKET_SIZE_LOG <= ZSTD_LDM_BUCKETSIZELOG_MAX);

    DEBUGLOG(4, "ZSTD_ldm_adjustParameters");

    if (!params->bucketSizeLog) params->bucketSizeLog = LDM_BUCKET_SIZE_LOG;

    if (!params->minMatchLength) params->minMatchLength = LDM_MIN_MATCH_LENGTH;

    if (cParams->strategy >= ZSTD_btopt) {

      /* Get out of the way of the optimal parser */

      U32 const minMatch = MAX(cParams->targetLength, params->minMatchLength);

      assert(minMatch >= ZSTD_LDM_MINMATCH_MIN);

      assert(minMatch <= ZSTD_LDM_MINMATCH_MAX);

      params->minMatchLength = minMatch;

    }

    if (params->hashLog == 0) {

        params->hashLog = MAX(ZSTD_HASHLOG_MIN, params->windowLog - LDM_HASH_RLOG);

        assert(params->hashLog <= ZSTD_HASHLOG_MAX);

    }

    if (params->hashRateLog == 0) {

        params->hashRateLog = params->windowLog < params->hashLog

                                   ? 0

                                   : params->windowLog - params->hashLog;

    }

    params->bucketSizeLog = MIN(params->bucketSizeLog, params->hashLog);

}

size_t ZSTD_ldm_getTableSize(ldmParams_t params)

{

    size_t const ldmHSize = ((size_t)1) << params.hashLog;

    size_t const ldmBucketSizeLog = MIN(params.bucketSizeLog, params.hashLog);

    size_t const ldmBucketSize = ((size_t)1) << (params.hashLog - ldmBucketSizeLog);

    size_t const totalSize = ZSTD_cwksp_alloc_size(ldmBucketSize)

                           + ZSTD_cwksp_alloc_size(ldmHSize * sizeof(ldmEntry_t));

    return params.enableLdm ? totalSize : 0;

}

size_t ZSTD_ldm_getMaxNbSeq(ldmParams_t params, size_t maxChunkSize)

{

    return params.enableLdm ? (maxChunkSize / params.minMatchLength) : 0;

}

/** ZSTD_ldm_getSmallHash() :

 *  numBits should be <= 32

 *  If numBits==0, returns 0.

 *  @return : the most significant numBits of value. */

static U32 ZSTD_ldm_getSmallHash(U64 value, U32 numBits)

{

    assert(numBits <= 32);

    return numBits == 0 ? 0 : (U32)(value >> (64 - numBits));

}

/** ZSTD_ldm_getChecksum() :

 *  numBitsToDiscard should be <= 32

 *  @return : the next most significant 32 bits after numBitsToDiscard */

static U32 ZSTD_ldm_getChecksum(U64 hash, U32 numBitsToDiscard)

{

    assert(numBitsToDiscard <= 32);

    return (hash >> (64 - 32 - numBitsToDiscard)) & 0xFFFFFFFF;

}

/** ZSTD_ldm_getTag() ;

 *  Given the hash, returns the most significant numTagBits bits

 *  after (32 + hbits) bits.

 *

 *  If there are not enough bits remaining, return the last

 *  numTagBits bits. */

static U32 ZSTD_ldm_getTag(U64 hash, U32 hbits, U32 numTagBits)

{

    assert(numTagBits < 32 && hbits <= 32);

    if (32 - hbits < numTagBits) {

        return hash & (((U32)1 << numTagBits) - 1);

    } else {

        return (hash >> (32 - hbits - numTagBits)) & (((U32)1 << numTagBits) - 1);

    }

}

/** ZSTD_ldm_getBucket() :

 *  Returns a pointer to the start of the bucket associated with hash. */

static ldmEntry_t* ZSTD_ldm_getBucket(

        ldmState_t* ldmState, size_t hash, ldmParams_t const ldmParams)

{

    return ldmState->hashTable + (hash << ldmParams.bucketSizeLog);

}

/** ZSTD_ldm_insertEntry() :

 *  Insert the entry with corresponding hash into the hash table */

static void ZSTD_ldm_insertEntry(ldmState_t* ldmState,

                                 size_t const hash, const ldmEntry_t entry,

                                 ldmParams_t const ldmParams)

{

    BYTE* const bucketOffsets = ldmState->bucketOffsets;

    *(ZSTD_ldm_getBucket(ldmState, hash, ldmParams) + bucketOffsets[hash]) = entry;

    bucketOffsets[hash]++;

    bucketOffsets[hash] &= ((U32)1 << ldmParams.bucketSizeLog) - 1;

}

/** ZSTD_ldm_makeEntryAndInsertByTag() :

 *

 *  Gets the small hash, checksum, and tag from the rollingHash.

 *

 *  If the tag matches (1 << ldmParams.hashRateLog)-1, then

 *  creates an ldmEntry from the offset, and inserts it into the hash table.

 *

 *  hBits is the length of the small hash, which is the most significant hBits

 *  of rollingHash. The checksum is the next 32 most significant bits, followed

 *  by ldmParams.hashRateLog bits that make up the tag. */

static void ZSTD_ldm_makeEntryAndInsertByTag(ldmState_t* ldmState,

                                             U64 const rollingHash,

                                             U32 const hBits,

                                             U32 const offset,

                                             ldmParams_t const ldmParams)

{

    U32 const tag = ZSTD_ldm_getTag(rollingHash, hBits, ldmParams.hashRateLog);

    U32 const tagMask = ((U32)1 << ldmParams.hashRateLog) - 1;

    if (tag == tagMask) {

        U32 const hash = ZSTD_ldm_getSmallHash(rollingHash, hBits);

        U32 const checksum = ZSTD_ldm_getChecksum(rollingHash, hBits);

        ldmEntry_t entry;

        entry.offset = offset;

        entry.checksum = checksum;

        ZSTD_ldm_insertEntry(ldmState, hash, entry, ldmParams);

    }

}

/** ZSTD_ldm_countBackwardsMatch() :

 *  Returns the number of bytes that match backwards before pIn and pMatch.

 *

 *  We count only bytes where pMatch >= pBase and pIn >= pAnchor. */

static size_t ZSTD_ldm_countBackwardsMatch(

            const BYTE* pIn, const BYTE* pAnchor,

            const BYTE* pMatch, const BYTE* pBase)

{

    size_t matchLength = 0;

    while (pIn > pAnchor && pMatch > pBase && pIn[-1] == pMatch[-1]) {

        pIn--;

        pMatch--;

        matchLength++;

    }

    return matchLength;

}

/** ZSTD_ldm_fillFastTables() :

 *

 *  Fills the relevant tables for the ZSTD_fast and ZSTD_dfast strategies.

 *  This is similar to ZSTD_loadDictionaryContent.

 *

 *  The tables for the other strategies are filled within their

 *  block compressors. */

static size_t ZSTD_ldm_fillFastTables(ZSTD_matchState_t* ms,

                                      void const* end)

{

    const BYTE* const iend = (const BYTE*)end;

    switch(ms->cParams.strategy)

    {

    case ZSTD_fast:

        ZSTD_fillHashTable(ms, iend, ZSTD_dtlm_fast);

        break;

    case ZSTD_dfast:

        ZSTD_fillDoubleHashTable(ms, iend, ZSTD_dtlm_fast);

        break;

    case ZSTD_greedy:

    case ZSTD_lazy:

    case ZSTD_lazy2:

    case ZSTD_btlazy2:

    case ZSTD_btopt:

    case ZSTD_btultra:

    case ZSTD_btultra2:

        break;

    default:

        assert(0);  /* not possible : not a valid strategy id */

    }

    return 0;

}

/** ZSTD_ldm_fillLdmHashTable() :

 *

 *  Fills hashTable from (lastHashed + 1) to iend (non-inclusive).

 *  lastHash is the rolling hash that corresponds to lastHashed.

 *

 *  Returns the rolling hash corresponding to position iend-1. */

static U64 ZSTD_ldm_fillLdmHashTable(ldmState_t* state,

                                     U64 lastHash, const BYTE* lastHashed,

                                     const BYTE* iend, const BYTE* base,

                                     U32 hBits, ldmParams_t const ldmParams)

{

    U64 rollingHash = lastHash;

    const BYTE* cur = lastHashed + 1;

    while (cur < iend) {

        rollingHash = ZSTD_rollingHash_rotate(rollingHash, cur[-1],

                                              cur[ldmParams.minMatchLength-1],

                                              state->hashPower);

        ZSTD_ldm_makeEntryAndInsertByTag(state,

                                         rollingHash, hBits,

                                         (U32)(cur - base), ldmParams);

        ++cur;

    }

    return rollingHash;

}

/** ZSTD_ldm_limitTableUpdate() :

 *

 *  Sets cctx->nextToUpdate to a position corresponding closer to anchor

 *  if it is far way

 *  (after a long match, only update tables a limited amount). */

static void ZSTD_ldm_limitTableUpdate(ZSTD_matchState_t* ms, const BYTE* anchor)

{

    U32 const current = (U32)(anchor - ms->window.base);

    if (current > ms->nextToUpdate + 1024) {

        ms->nextToUpdate =

            current - MIN(512, current - ms->nextToUpdate - 1024);

    }

}

static size_t ZSTD_ldm_generateSequences_internal(

        ldmState_t* ldmState, rawSeqStore_t* rawSeqStore,

        ldmParams_t const* params, void const* src, size_t srcSize)

{

    /* LDM parameters */

    int const extDict = ZSTD_window_hasExtDict(ldmState->window);

    U32 const minMatchLength = params->minMatchLength;

    U64 const hashPower = ldmState->hashPower;

    U32 const hBits = params->hashLog - params->bucketSizeLog;

    U32 const ldmBucketSize = 1U << params->bucketSizeLog;

    U32 const hashRateLog = params->hashRateLog;

    U32 const ldmTagMask = (1U << params->hashRateLog) - 1;

    /* Prefix and extDict parameters */

    U32 const dictLimit = ldmState->window.dictLimit;

    U32 const lowestIndex = extDict ? ldmState->window.lowLimit : dictLimit;

    BYTE const* const base = ldmState->window.base;

    BYTE const* const dictBase = extDict ? ldmState->window.dictBase : NULL;

    BYTE const* const dictStart = extDict ? dictBase + lowestIndex : NULL;

    BYTE const* const dictEnd = extDict ? dictBase + dictLimit : NULL;

    BYTE const* const lowPrefixPtr = base + dictLimit;

    /* Input bounds */

    BYTE const* const istart = (BYTE const*)src;

    BYTE const* const iend = istart + srcSize;

    BYTE const* const ilimit = iend - MAX(minMatchLength, HASH_READ_SIZE);

    /* Input positions */

    BYTE const* anchor = istart;

    BYTE const* ip = istart;

    /* Rolling hash */

    BYTE const* lastHashed = NULL;

    U64 rollingHash = 0;

    while (ip <= ilimit) {

        size_t mLength;

        U32 const current = (U32)(ip - base);

        size_t forwardMatchLength = 0, backwardMatchLength = 0;

        ldmEntry_t* bestEntry = NULL;

        if (ip != istart) {

            rollingHash = ZSTD_rollingHash_rotate(rollingHash, lastHashed[0],

                                                  lastHashed[minMatchLength],

                                                  hashPower);

        } else {

            rollingHash = ZSTD_rollingHash_compute(ip, minMatchLength);

        }

        lastHashed = ip;

        /* Do not insert and do not look for a match */

        if (ZSTD_ldm_getTag(rollingHash, hBits, hashRateLog) != ldmTagMask) {

           ip++;

           continue;

        }

        /* Get the best entry and compute the match lengths */

        {

            ldmEntry_t* const bucket =

                ZSTD_ldm_getBucket(ldmState,

                                   ZSTD_ldm_getSmallHash(rollingHash, hBits),

                                   *params);

            ldmEntry_t* cur;

            size_t bestMatchLength = 0;

            U32 const checksum = ZSTD_ldm_getChecksum(rollingHash, hBits);

            for (cur = bucket; cur < bucket + ldmBucketSize; ++cur) {

                size_t curForwardMatchLength, curBackwardMatchLength,

                       curTotalMatchLength;

                if (cur->checksum != checksum || cur->offset <= lowestIndex) {

                    continue;

                }

                if (extDict) {

                    BYTE const* const curMatchBase =

                        cur->offset < dictLimit ? dictBase : base;

                    BYTE const* const pMatch = curMatchBase + cur->offset;

                    BYTE const* const matchEnd =

                        cur->offset < dictLimit ? dictEnd : iend;

                    BYTE const* const lowMatchPtr =

                        cur->offset < dictLimit ? dictStart : lowPrefixPtr;

                    curForwardMatchLength = ZSTD_count_2segments(

                                                ip, pMatch, iend,

                                                matchEnd, lowPrefixPtr);

                    if (curForwardMatchLength < minMatchLength) {

                        continue;

                    }

                    curBackwardMatchLength =

                        ZSTD_ldm_countBackwardsMatch(ip, anchor, pMatch,

                                                     lowMatchPtr);

                    curTotalMatchLength = curForwardMatchLength +

                                          curBackwardMatchLength;

                } else { /* !extDict */

                    BYTE const* const pMatch = base + cur->offset;

                    curForwardMatchLength = ZSTD_count(ip, pMatch, iend);

                    if (curForwardMatchLength < minMatchLength) {

                        continue;

                    }

                    curBackwardMatchLength =

                        ZSTD_ldm_countBackwardsMatch(ip, anchor, pMatch,

                                                     lowPrefixPtr);

                    curTotalMatchLength = curForwardMatchLength +

                                          curBackwardMatchLength;

                }

                if (curTotalMatchLength > bestMatchLength) {

                    bestMatchLength = curTotalMatchLength;

                    forwardMatchLength = curForwardMatchLength;

                    backwardMatchLength = curBackwardMatchLength;

                    bestEntry = cur;

                }

            }

        }

        /* No match found -- continue searching */

        if (bestEntry == NULL) {

            ZSTD_ldm_makeEntryAndInsertByTag(ldmState, rollingHash,

                                             hBits, current,

                                             *params);

            ip++;

            continue;

        }

        /* Match found */

        mLength = forwardMatchLength + backwardMatchLength;

        ip -= backwardMatchLength;

        {

            /* Store the sequence:

             * ip = current - backwardMatchLength

             * The match is at (bestEntry->offset - backwardMatchLength)

             */

            U32 const matchIndex = bestEntry->offset;

            U32 const offset = current - matchIndex;

            rawSeq* const seq = rawSeqStore->seq + rawSeqStore->size;

            /* Out of sequence storage */

            if (rawSeqStore->size == rawSeqStore->capacity)

                return ERROR(dstSize_tooSmall);

            seq->litLength = (U32)(ip - anchor);

            seq->matchLength = (U32)mLength;

            seq->offset = offset;

            rawSeqStore->size++;

        }

        /* Insert the current entry into the hash table */

        ZSTD_ldm_makeEntryAndInsertByTag(ldmState, rollingHash, hBits,

                                         (U32)(lastHashed - base),

                                         *params);

        assert(ip + backwardMatchLength == lastHashed);

        /* Fill the hash table from lastHashed+1 to ip+mLength*/

        /* Heuristic: don't need to fill the entire table at end of block */

        if (ip + mLength <= ilimit) {

            rollingHash = ZSTD_ldm_fillLdmHashTable(

                              ldmState, rollingHash, lastHashed,

                              ip + mLength, base, hBits, *params);

            lastHashed = ip + mLength - 1;

        }

        ip += mLength;

        anchor = ip;

    }

    return iend - anchor;

}

/*! ZSTD_ldm_reduceTable() :

 *  reduce table indexes by `reducerValue` */

static void ZSTD_ldm_reduceTable(ldmEntry_t* const table, U32 const size,

                                 U32 const reducerValue)

{

    U32 u;

    for (u = 0; u < size; u++) {

        if (table[u].offset < reducerValue) table[u].offset = 0;

        else table[u].offset -= reducerValue;

    }

}

size_t ZSTD_ldm_generateSequences(

        ldmState_t* ldmState, rawSeqStore_t* sequences,

        ldmParams_t const* params, void const* src, size_t srcSize)

{

    U32 const maxDist = 1U << params->windowLog;

    BYTE const* const istart = (BYTE const*)src;

    BYTE const* const iend = istart + srcSize;

    size_t const kMaxChunkSize = 1 << 20;

    size_t const nbChunks = (srcSize / kMaxChunkSize) + ((srcSize % kMaxChunkSize) != 0);

    size_t chunk;

    size_t leftoverSize = 0;

    assert(ZSTD_CHUNKSIZE_MAX >= kMaxChunkSize);

    /* Check that ZSTD_window_update() has been called for this chunk prior

     * to passing it to this function.

     */

    assert(ldmState->window.nextSrc >= (BYTE const*)src + srcSize);

    /* The input could be very large (in zstdmt), so it must be broken up into

     * chunks to enforce the maximum distance and handle overflow correction.

     */

    assert(sequences->pos <= sequences->size);

    assert(sequences->size <= sequences->capacity);

    for (chunk = 0; chunk < nbChunks && sequences->size < sequences->capacity; ++chunk) {

        BYTE const* const chunkStart = istart + chunk * kMaxChunkSize;

        size_t const remaining = (size_t)(iend - chunkStart);

        BYTE const *const chunkEnd =

            (remaining < kMaxChunkSize) ? iend : chunkStart + kMaxChunkSize;

        size_t const chunkSize = chunkEnd - chunkStart;

        size_t newLeftoverSize;

        size_t const prevSize = sequences->size;

        assert(chunkStart < iend);

        /* 1. Perform overflow correction if necessary. */

        if (ZSTD_window_needOverflowCorrection(ldmState->window, chunkEnd)) {

            U32 const ldmHSize = 1U << params->hashLog;

            U32 const correction = ZSTD_window_correctOverflow(

                &ldmState->window, /* cycleLog */ 0, maxDist, chunkStart);

            ZSTD_ldm_reduceTable(ldmState->hashTable, ldmHSize, correction);

        }

        /* 2. We enforce the maximum offset allowed.

         *

         * kMaxChunkSize should be small enough that we don't lose too much of

         * the window through early invalidation.

         * TODO: * Test the chunk size.

         *       * Try invalidation after the sequence generation and test the

         *         the offset against maxDist directly.

         */

        ZSTD_window_enforceMaxDist(&ldmState->window, chunkEnd, maxDist, NULL, NULL);

        /* 3. Generate the sequences for the chunk, and get newLeftoverSize. */

        newLeftoverSize = ZSTD_ldm_generateSequences_internal(

            ldmState, sequences, params, chunkStart, chunkSize);

        if (ZSTD_isError(newLeftoverSize))

            return newLeftoverSize;

        /* 4. We add the leftover literals from previous iterations to the first

         *    newly generated sequence, or add the `newLeftoverSize` if none are

         *    generated.

         */

        /* Prepend the leftover literals from the last call */

        if (prevSize < sequences->size) {

            sequences->seq[prevSize].litLength += (U32)leftoverSize;

            leftoverSize = newLeftoverSize;

        } else {

            assert(newLeftoverSize == chunkSize);

            leftoverSize += chunkSize;

        }

    }

    return 0;

}

void ZSTD_ldm_skipSequences(rawSeqStore_t* rawSeqStore, size_t srcSize, U32 const minMatch) {

    while (srcSize > 0 && rawSeqStore->pos < rawSeqStore->size) {

        rawSeq* seq = rawSeqStore->seq + rawSeqStore->pos;

        if (srcSize <= seq->litLength) {

            /* Skip past srcSize literals */

            seq->litLength -= (U32)srcSize;

            return;

        }

        srcSize -= seq->litLength;

        seq->litLength = 0;

        if (srcSize < seq->matchLength) {

            /* Skip past the first srcSize of the match */

            seq->matchLength -= (U32)srcSize;

            if (seq->matchLength < minMatch) {

                /* The match is too short, omit it */

                if (rawSeqStore->pos + 1 < rawSeqStore->size) {

                    seq[1].litLength += seq[0].matchLength;

                }

                rawSeqStore->pos++;

            }

            return;

        }

        srcSize -= seq->matchLength;

        seq->matchLength = 0;

        rawSeqStore->pos++;

    }

}

/**

 * If the sequence length is longer than remaining then the sequence is split

 * between this block and the next.

 *

 * Returns the current sequence to handle, or if the rest of the block should

 * be literals, it returns a sequence with offset == 0.

 */

static rawSeq maybeSplitSequence(rawSeqStore_t* rawSeqStore,

                                 U32 const remaining, U32 const minMatch)

{

    rawSeq sequence = rawSeqStore->seq[rawSeqStore->pos];

    assert(sequence.offset > 0);

    /* Likely: No partial sequence */

    if (remaining >= sequence.litLength + sequence.matchLength) {