deps/libchdr/deps/zstd-1.5.5/contrib/externalSequenceProducer/sequence_producer.c

   1 /*
   2  * Copyright (c) Yann Collet, Meta Platforms, 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 #include "zstd_compress_internal.h"
  12 #include "sequence_producer.h"
  13
  14 #define HSIZE 1024
  15 static U32 const HLOG = 10;
  16 static U32 const MLS = 4;
  17 static U32 const BADIDX = 0xffffffff;
  18
  19 size_t simpleSequenceProducer(
  20   void* sequenceProducerState,
  21   ZSTD_Sequence* outSeqs, size_t outSeqsCapacity,
  22   const void* src, size_t srcSize,
  23   const void* dict, size_t dictSize,
  24   int compressionLevel,
  25   size_t windowSize
  26 ) {
  27     const BYTE* const istart = (const BYTE*)src;
  28     const BYTE* const iend = istart + srcSize;
  29     const BYTE* ip = istart;
  30     const BYTE* anchor = istart;
  31     size_t seqCount = 0;
  32     U32 hashTable[HSIZE];
  33
  34     (void)sequenceProducerState;
  35     (void)dict;
  36     (void)dictSize;
  37     (void)outSeqsCapacity;
  38     (void)compressionLevel;
  39
  40     {   int i;
  41         for (i=0; i < HSIZE; i++) {
  42             hashTable[i] = BADIDX;
  43     }   }
  44
  45     while (ip + MLS < iend) {
  46         size_t const hash = ZSTD_hashPtr(ip, HLOG, MLS);
  47         U32 const matchIndex = hashTable[hash];
  48         hashTable[hash] = (U32)(ip - istart);
  49
  50         if (matchIndex != BADIDX) {
  51             const BYTE* const match = istart + matchIndex;
  52             U32 const matchLen = (U32)ZSTD_count(ip, match, iend);
  53             if (matchLen >= ZSTD_MINMATCH_MIN) {
  54                 U32 const litLen = (U32)(ip - anchor);
  55                 U32 const offset = (U32)(ip - match);
  56                 ZSTD_Sequence const seq = {
  57                     offset, litLen, matchLen, 0
  58                 };
  59
  60                 /* Note: it's crucial to stay within the window size! */
  61                 if (offset <= windowSize) {
  62                     outSeqs[seqCount++] = seq;
  63                     ip += matchLen;
  64                     anchor = ip;
  65                     continue;
  66                 }
  67             }
  68         }
  69
  70         ip++;
  71     }
  72
  73     {   ZSTD_Sequence const finalSeq = {
  74             0, (U32)(iend - anchor), 0, 0
  75         };
  76         outSeqs[seqCount++] = finalSeq;
  77     }
  78
  79     return seqCount;
  80 }