1*01826a49SYabin Cui /*
2*01826a49SYabin Cui * Copyright (c) Yann Collet, Meta Platforms, Inc.
3*01826a49SYabin Cui * All rights reserved.
4*01826a49SYabin Cui *
5*01826a49SYabin Cui * This source code is licensed under both the BSD-style license (found in the
6*01826a49SYabin Cui * LICENSE file in the root directory of this source tree) and the GPLv2 (found
7*01826a49SYabin Cui * in the COPYING file in the root directory of this source tree).
8*01826a49SYabin Cui * You may select, at your option, one of the above-listed licenses.
9*01826a49SYabin Cui */
10*01826a49SYabin Cui
11*01826a49SYabin Cui #include "zstd_compress_internal.h"
12*01826a49SYabin Cui #include "sequence_producer.h"
13*01826a49SYabin Cui
14*01826a49SYabin Cui #define HSIZE 1024
15*01826a49SYabin Cui static U32 const HLOG = 10;
16*01826a49SYabin Cui static U32 const MLS = 4;
17*01826a49SYabin Cui static U32 const BADIDX = 0xffffffff;
18*01826a49SYabin Cui
simpleSequenceProducer(void * sequenceProducerState,ZSTD_Sequence * outSeqs,size_t outSeqsCapacity,const void * src,size_t srcSize,const void * dict,size_t dictSize,int compressionLevel,size_t windowSize)19*01826a49SYabin Cui size_t simpleSequenceProducer(
20*01826a49SYabin Cui void* sequenceProducerState,
21*01826a49SYabin Cui ZSTD_Sequence* outSeqs, size_t outSeqsCapacity,
22*01826a49SYabin Cui const void* src, size_t srcSize,
23*01826a49SYabin Cui const void* dict, size_t dictSize,
24*01826a49SYabin Cui int compressionLevel,
25*01826a49SYabin Cui size_t windowSize
26*01826a49SYabin Cui ) {
27*01826a49SYabin Cui const BYTE* const istart = (const BYTE*)src;
28*01826a49SYabin Cui const BYTE* const iend = istart + srcSize;
29*01826a49SYabin Cui const BYTE* ip = istart;
30*01826a49SYabin Cui const BYTE* anchor = istart;
31*01826a49SYabin Cui size_t seqCount = 0;
32*01826a49SYabin Cui U32 hashTable[HSIZE];
33*01826a49SYabin Cui
34*01826a49SYabin Cui (void)sequenceProducerState;
35*01826a49SYabin Cui (void)dict;
36*01826a49SYabin Cui (void)dictSize;
37*01826a49SYabin Cui (void)outSeqsCapacity;
38*01826a49SYabin Cui (void)compressionLevel;
39*01826a49SYabin Cui
40*01826a49SYabin Cui { int i;
41*01826a49SYabin Cui for (i=0; i < HSIZE; i++) {
42*01826a49SYabin Cui hashTable[i] = BADIDX;
43*01826a49SYabin Cui } }
44*01826a49SYabin Cui
45*01826a49SYabin Cui while (ip + MLS < iend) {
46*01826a49SYabin Cui size_t const hash = ZSTD_hashPtr(ip, HLOG, MLS);
47*01826a49SYabin Cui U32 const matchIndex = hashTable[hash];
48*01826a49SYabin Cui hashTable[hash] = (U32)(ip - istart);
49*01826a49SYabin Cui
50*01826a49SYabin Cui if (matchIndex != BADIDX) {
51*01826a49SYabin Cui const BYTE* const match = istart + matchIndex;
52*01826a49SYabin Cui U32 const matchLen = (U32)ZSTD_count(ip, match, iend);
53*01826a49SYabin Cui if (matchLen >= ZSTD_MINMATCH_MIN) {
54*01826a49SYabin Cui U32 const litLen = (U32)(ip - anchor);
55*01826a49SYabin Cui U32 const offset = (U32)(ip - match);
56*01826a49SYabin Cui ZSTD_Sequence const seq = {
57*01826a49SYabin Cui offset, litLen, matchLen, 0
58*01826a49SYabin Cui };
59*01826a49SYabin Cui
60*01826a49SYabin Cui /* Note: it's crucial to stay within the window size! */
61*01826a49SYabin Cui if (offset <= windowSize) {
62*01826a49SYabin Cui outSeqs[seqCount++] = seq;
63*01826a49SYabin Cui ip += matchLen;
64*01826a49SYabin Cui anchor = ip;
65*01826a49SYabin Cui continue;
66*01826a49SYabin Cui }
67*01826a49SYabin Cui }
68*01826a49SYabin Cui }
69*01826a49SYabin Cui
70*01826a49SYabin Cui ip++;
71*01826a49SYabin Cui }
72*01826a49SYabin Cui
73*01826a49SYabin Cui { ZSTD_Sequence const finalSeq = {
74*01826a49SYabin Cui 0, (U32)(iend - anchor), 0, 0
75*01826a49SYabin Cui };
76*01826a49SYabin Cui outSeqs[seqCount++] = finalSeq;
77*01826a49SYabin Cui }
78*01826a49SYabin Cui
79*01826a49SYabin Cui return seqCount;
80*01826a49SYabin Cui }
81