mercurial-scm/hg: contrib/python-zstandard/zstd/compress/zstd_compress

annotate contrib/python-zstandard/zstd/compress/zstd_compress_internal.h @ 42937:69de49c4e39c

zstandard: vendor python-zstandard 0.12 The upstream source distribution from PyPI was extracted. Unwanted files were removed. The clang-format ignore list was updated to reflect the new source of files. test-repo-compengines.t was updated to reflect a change in behavior of the zstd library. The project contains a vendored copy of zstandard 1.4.3. The old version was 1.3.8. This should result in some minor performance wins. # no-check-commit because 3rd party code has different style guidelines Differential Revision: https://phab.mercurial-scm.org/D6858

author	Gregory Szorc <gregory.szorc@gmail.com>
date	Sun, 15 Sep 2019 20:04:00 -0700
parents	675775c33ab6
children	de7838053207

rev	line source
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1 /*
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	2 * Copyright (c) 2016-present, Yann Collet, Facebook, Inc.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	3 * All rights reserved.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	4 *
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	5 * This source code is licensed under both the BSD-style license (found in the
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	6 * LICENSE file in the root directory of this source tree) and the GPLv2 (found
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	7 * in the COPYING file in the root directory of this source tree).
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	8 * You may select, at your option, one of the above-listed licenses.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	9 */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	10
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	11 /* This header contains definitions
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	12 * that shall only be used by modules within lib/compress.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	13 */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	14
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	15 #ifndef ZSTD_COMPRESS_H
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	16 #define ZSTD_COMPRESS_H
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	17
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	18 /-************************************
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	19 * Dependencies
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	20 ***************************************/
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	21 #include "zstd_internal.h"
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	22 #ifdef ZSTD_MULTITHREAD
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	23 # include "zstdmt_compress.h"
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	24 #endif
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	25
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	26 #if defined (__cplusplus)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	27 extern "C" {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	28 #endif
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	29
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	30
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	31 /-************************************
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	32 * Constants
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	33 ***************************************/
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	34 #define kSearchStrength 8
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	35 #define HASH_READ_SIZE 8
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	36 #define ZSTD_DUBT_UNSORTED_MARK 1 /* For btlazy2 strategy, index ZSTD_DUBT_UNSORTED_MARK==1 means "unsorted".
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	37 It could be confused for a real successor at index "1", if sorted as larger than its predecessor.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	38 It's not a big deal though : candidate will just be sorted again.
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	39 Additionally, candidate position 1 will be lost.
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	40 But candidate 1 cannot hide a large tree of candidates, so it's a minimal loss.
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	41 The benefit is that ZSTD_DUBT_UNSORTED_MARK cannot be mishandled after table re-use with a different strategy.
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	42 This constant is required by ZSTD_compressBlock_btlazy2() and ZSTD_reduceTable_internal() */
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	43
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	44
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	45 /-************************************
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	46 * Context memory management
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	47 ***************************************/
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	48 typedef enum { ZSTDcs_created=0, ZSTDcs_init, ZSTDcs_ongoing, ZSTDcs_ending } ZSTD_compressionStage_e;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	49 typedef enum { zcss_init=0, zcss_load, zcss_flush } ZSTD_cStreamStage;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	50
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	51 typedef struct ZSTD_prefixDict_s {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	52 const void* dict;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	53 size_t dictSize;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	54 ZSTD_dictContentType_e dictContentType;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	55 } ZSTD_prefixDict;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	56
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	57 typedef struct {
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	58 void* dictBuffer;
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	59 void const* dict;
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	60 size_t dictSize;
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	61 ZSTD_dictContentType_e dictContentType;
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	62 ZSTD_CDict* cdict;
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	63 } ZSTD_localDict;
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	64
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	65 typedef struct {
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	66 U32 CTable[HUF_CTABLE_SIZE_U32(255)];
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	67 HUF_repeat repeatMode;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	68 } ZSTD_hufCTables_t;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	69
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	70 typedef struct {
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	71 FSE_CTable offcodeCTable[FSE_CTABLE_SIZE_U32(OffFSELog, MaxOff)];
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	72 FSE_CTable matchlengthCTable[FSE_CTABLE_SIZE_U32(MLFSELog, MaxML)];
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	73 FSE_CTable litlengthCTable[FSE_CTABLE_SIZE_U32(LLFSELog, MaxLL)];
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	74 FSE_repeat offcode_repeatMode;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	75 FSE_repeat matchlength_repeatMode;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	76 FSE_repeat litlength_repeatMode;
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	77 } ZSTD_fseCTables_t;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	78
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	79 typedef struct {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	80 ZSTD_hufCTables_t huf;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	81 ZSTD_fseCTables_t fse;
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	82 } ZSTD_entropyCTables_t;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	83
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	84 typedef struct {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	85 U32 off;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	86 U32 len;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	87 } ZSTD_match_t;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	88
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	89 typedef struct {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	90 int price;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	91 U32 off;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	92 U32 mlen;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	93 U32 litlen;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	94 U32 rep[ZSTD_REP_NUM];
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	95 } ZSTD_optimal_t;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	96
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	97 typedef enum { zop_dynamic=0, zop_predef } ZSTD_OptPrice_e;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	98
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	99 typedef struct {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	100 /* All tables are allocated inside cctx->workspace by ZSTD_resetCCtx_internal() */
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	101 unsigned* litFreq; /* table of literals statistics, of size 256 */
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	102 unsigned* litLengthFreq; /* table of litLength statistics, of size (MaxLL+1) */
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	103 unsigned* matchLengthFreq; /* table of matchLength statistics, of size (MaxML+1) */
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	104 unsigned* offCodeFreq; /* table of offCode statistics, of size (MaxOff+1) */
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	105 ZSTD_match_t* matchTable; /* list of found matches, of size ZSTD_OPT_NUM+1 */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	106 ZSTD_optimal_t* priceTable; /* All positions tracked by optimal parser, of size ZSTD_OPT_NUM+1 */
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	107
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	108 U32 litSum; /* nb of literals */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	109 U32 litLengthSum; /* nb of litLength codes */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	110 U32 matchLengthSum; /* nb of matchLength codes */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	111 U32 offCodeSum; /* nb of offset codes */
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	112 U32 litSumBasePrice; /* to compare to log2(litfreq) */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	113 U32 litLengthSumBasePrice; /* to compare to log2(llfreq) */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	114 U32 matchLengthSumBasePrice;/* to compare to log2(mlfreq) */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	115 U32 offCodeSumBasePrice; /* to compare to log2(offreq) */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	116 ZSTD_OptPrice_e priceType; /* prices can be determined dynamically, or follow a pre-defined cost structure */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	117 const ZSTD_entropyCTables_t* symbolCosts; /* pre-calculated dictionary statistics */
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	118 ZSTD_literalCompressionMode_e literalCompressionMode;
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	119 } optState_t;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	120
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	121 typedef struct {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	122 ZSTD_entropyCTables_t entropy;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	123 U32 rep[ZSTD_REP_NUM];
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	124 } ZSTD_compressedBlockState_t;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	125
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	126 typedef struct {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	127 BYTE const* nextSrc; /* next block here to continue on current prefix */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	128 BYTE const* base; /* All regular indexes relative to this position */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	129 BYTE const* dictBase; /* extDict indexes relative to this position */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	130 U32 dictLimit; /* below that point, need extDict */
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	131 U32 lowLimit; /* below that point, no more valid data */
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	132 } ZSTD_window_t;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	133
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	134 typedef struct ZSTD_matchState_t ZSTD_matchState_t;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	135 struct ZSTD_matchState_t {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	136 ZSTD_window_t window; /* State for window round buffer management */
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	137 U32 loadedDictEnd; /* index of end of dictionary, within context's referential.
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	138 * When loadedDictEnd != 0, a dictionary is in use, and still valid.
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	139 * This relies on a mechanism to set loadedDictEnd=0 when dictionary is no longer within distance.
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	140 * Such mechanism is provided within ZSTD_window_enforceMaxDist() and ZSTD_checkDictValidity().
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	141 * When dict referential is copied into active context (i.e. not attached),
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	142 * loadedDictEnd == dictSize, since referential starts from zero.
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	143 */
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	144 U32 nextToUpdate; /* index from which to continue table update */
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	145 U32 hashLog3; /* dispatch table for matches of len==3 : larger == faster, more memory */
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	146 U32* hashTable;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	147 U32* hashTable3;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	148 U32* chainTable;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	149 optState_t opt; /* optimal parser state */
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	150 const ZSTD_matchState_t* dictMatchState;
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	151 ZSTD_compressionParameters cParams;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	152 };
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	153
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	154 typedef struct {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	155 ZSTD_compressedBlockState_t* prevCBlock;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	156 ZSTD_compressedBlockState_t* nextCBlock;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	157 ZSTD_matchState_t matchState;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	158 } ZSTD_blockState_t;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	159
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	160 typedef struct {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	161 U32 offset;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	162 U32 checksum;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	163 } ldmEntry_t;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	164
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	165 typedef struct {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	166 ZSTD_window_t window; /* State for the window round buffer management */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	167 ldmEntry_t* hashTable;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	168 BYTE* bucketOffsets; /* Next position in bucket to insert entry */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	169 U64 hashPower; /* Used to compute the rolling hash.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	170 * Depends on ldmParams.minMatchLength */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	171 } ldmState_t;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	172
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	173 typedef struct {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	174 U32 enableLdm; /* 1 if enable long distance matching */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	175 U32 hashLog; /* Log size of hashTable */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	176 U32 bucketSizeLog; /* Log bucket size for collision resolution, at most 8 */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	177 U32 minMatchLength; /* Minimum match length */
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	178 U32 hashRateLog; /* Log number of entries to skip */
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	179 U32 windowLog; /* Window log for the LDM */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	180 } ldmParams_t;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	181
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	182 typedef struct {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	183 U32 offset;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	184 U32 litLength;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	185 U32 matchLength;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	186 } rawSeq;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	187
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	188 typedef struct {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	189 rawSeq* seq; /* The start of the sequences */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	190 size_t pos; /* The position where reading stopped. <= size. */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	191 size_t size; /* The number of sequences. <= capacity. */
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	192 size_t capacity; /* The capacity starting from `seq` pointer */
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	193 } rawSeqStore_t;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	194
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	195 struct ZSTD_CCtx_params_s {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	196 ZSTD_format_e format;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	197 ZSTD_compressionParameters cParams;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	198 ZSTD_frameParameters fParams;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	199
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	200 int compressionLevel;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	201 int forceWindow; /* force back-references to respect limit of
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	202 * 1<<wLog, even for dictionary */
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	203 size_t targetCBlockSize; /* Tries to fit compressed block size to be around targetCBlockSize.
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	204 * No target when targetCBlockSize == 0.
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	205 * There is no guarantee on compressed block size */
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	206
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	207 ZSTD_dictAttachPref_e attachDictPref;
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	208 ZSTD_literalCompressionMode_e literalCompressionMode;
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	209
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	210 /* Multithreading: used to pass parameters to mtctx */
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	211 int nbWorkers;
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	212 size_t jobSize;
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	213 int overlapLog;
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	214 int rsyncable;
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	215
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	216 /* Long distance matching parameters */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	217 ldmParams_t ldmParams;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	218
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	219 /* Internal use, for createCCtxParams() and freeCCtxParams() only */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	220 ZSTD_customMem customMem;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	221 }; /* typedef'd to ZSTD_CCtx_params within "zstd.h" */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	222
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	223 struct ZSTD_CCtx_s {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	224 ZSTD_compressionStage_e stage;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	225 int cParamsChanged; /* == 1 if cParams(except wlog) or compression level are changed in requestedParams. Triggers transmission of new params to ZSTDMT (if available) then reset to 0. */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	226 int bmi2; /* == 1 if the CPU supports BMI2 and 0 otherwise. CPU support is determined dynamically once per context lifetime. */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	227 ZSTD_CCtx_params requestedParams;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	228 ZSTD_CCtx_params appliedParams;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	229 U32 dictID;
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	230
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	231 int workSpaceOversizedDuration;
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	232 void* workSpace;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	233 size_t workSpaceSize;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	234 size_t blockSize;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	235 unsigned long long pledgedSrcSizePlusOne; /* this way, 0 (default) == unknown */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	236 unsigned long long consumedSrcSize;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	237 unsigned long long producedCSize;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	238 XXH64_state_t xxhState;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	239 ZSTD_customMem customMem;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	240 size_t staticSize;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	241
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	242 seqStore_t seqStore; /* sequences storage ptrs */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	243 ldmState_t ldmState; /* long distance matching state */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	244 rawSeq* ldmSequences; /* Storage for the ldm output sequences */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	245 size_t maxNbLdmSequences;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	246 rawSeqStore_t externSeqStore; /* Mutable reference to external sequences */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	247 ZSTD_blockState_t blockState;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	248 U32* entropyWorkspace; /* entropy workspace of HUF_WORKSPACE_SIZE bytes */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	249
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	250 /* streaming */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	251 char* inBuff;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	252 size_t inBuffSize;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	253 size_t inToCompress;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	254 size_t inBuffPos;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	255 size_t inBuffTarget;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	256 char* outBuff;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	257 size_t outBuffSize;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	258 size_t outBuffContentSize;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	259 size_t outBuffFlushedSize;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	260 ZSTD_cStreamStage streamStage;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	261 U32 frameEnded;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	262
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	263 /* Dictionary */
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	264 ZSTD_localDict localDict;
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	265 const ZSTD_CDict* cdict;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	266 ZSTD_prefixDict prefixDict; /* single-usage dictionary */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	267
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	268 /* Multi-threading */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	269 #ifdef ZSTD_MULTITHREAD
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	270 ZSTDMT_CCtx* mtctx;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	271 #endif
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	272 };
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	273
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	274 typedef enum { ZSTD_dtlm_fast, ZSTD_dtlm_full } ZSTD_dictTableLoadMethod_e;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	275
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	276 typedef enum { ZSTD_noDict = 0, ZSTD_extDict = 1, ZSTD_dictMatchState = 2 } ZSTD_dictMode_e;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	277
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	278
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	279 typedef size_t (*ZSTD_blockCompressor) (
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	280 ZSTD_matchState_t* bs, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	281 void const* src, size_t srcSize);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	282 ZSTD_blockCompressor ZSTD_selectBlockCompressor(ZSTD_strategy strat, ZSTD_dictMode_e dictMode);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	283
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	284
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	285 MEM_STATIC U32 ZSTD_LLcode(U32 litLength)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	286 {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	287 static const BYTE LL_Code[64] = { 0, 1, 2, 3, 4, 5, 6, 7,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	288 8, 9, 10, 11, 12, 13, 14, 15,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	289 16, 16, 17, 17, 18, 18, 19, 19,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	290 20, 20, 20, 20, 21, 21, 21, 21,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	291 22, 22, 22, 22, 22, 22, 22, 22,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	292 23, 23, 23, 23, 23, 23, 23, 23,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	293 24, 24, 24, 24, 24, 24, 24, 24,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	294 24, 24, 24, 24, 24, 24, 24, 24 };
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	295 static const U32 LL_deltaCode = 19;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	296 return (litLength > 63) ? ZSTD_highbit32(litLength) + LL_deltaCode : LL_Code[litLength];
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	297 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	298
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	299 /* ZSTD_MLcode() :
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	300 * note : mlBase = matchLength - MINMATCH;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	301 * because it's the format it's stored in seqStore->sequences */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	302 MEM_STATIC U32 ZSTD_MLcode(U32 mlBase)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	303 {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	304 static const BYTE ML_Code[128] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	305 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	306 32, 32, 33, 33, 34, 34, 35, 35, 36, 36, 36, 36, 37, 37, 37, 37,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	307 38, 38, 38, 38, 38, 38, 38, 38, 39, 39, 39, 39, 39, 39, 39, 39,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	308 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	309 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	310 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	311 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42 };
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	312 static const U32 ML_deltaCode = 36;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	313 return (mlBase > 127) ? ZSTD_highbit32(mlBase) + ML_deltaCode : ML_Code[mlBase];
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	314 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	315
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	316 /* ZSTD_cParam_withinBounds:
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	317 * @return 1 if value is within cParam bounds,
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	318 * 0 otherwise */
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	319 MEM_STATIC int ZSTD_cParam_withinBounds(ZSTD_cParameter cParam, int value)
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	320 {
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	321 ZSTD_bounds const bounds = ZSTD_cParam_getBounds(cParam);
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	322 if (ZSTD_isError(bounds.error)) return 0;
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	323 if (value < bounds.lowerBound) return 0;
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	324 if (value > bounds.upperBound) return 0;
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	325 return 1;
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	326 }
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	327
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	328 /* ZSTD_minGain() :
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	329 * minimum compression required
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	330 * to generate a compress block or a compressed literals section.
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	331 * note : use same formula for both situations */
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	332 MEM_STATIC size_t ZSTD_minGain(size_t srcSize, ZSTD_strategy strat)
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	333 {
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	334 U32 const minlog = (strat>=ZSTD_btultra) ? (U32)(strat) - 1 : 6;
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	335 ZSTD_STATIC_ASSERT(ZSTD_btultra == 8);
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	336 assert(ZSTD_cParam_withinBounds(ZSTD_c_strategy, strat));
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	337 return (srcSize >> minlog) + 2;
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	338 }
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	339
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	340 /*! ZSTD_storeSeq() :
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	341 * Store a sequence (literal length, literals, offset code and match length code) into seqStore_t.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	342 * `offsetCode` : distance to match + 3 (values 1-3 are repCodes).
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	343 * `mlBase` : matchLength - MINMATCH
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	344 */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	345 MEM_STATIC void ZSTD_storeSeq(seqStore_t* seqStorePtr, size_t litLength, const void* literals, U32 offsetCode, size_t mlBase)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	346 {
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	347 #if defined(DEBUGLEVEL) && (DEBUGLEVEL >= 6)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	348 static const BYTE* g_start = NULL;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	349 if (g_start==NULL) g_start = (const BYTE)literals; / note : index only works for compression within a single segment */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	350 { U32 const pos = (U32)((const BYTE*)literals - g_start);
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	351 DEBUGLOG(6, "Cpos%7u :%3u literals, match%4u bytes at offCode%7u",
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	352 pos, (U32)litLength, (U32)mlBase+MINMATCH, (U32)offsetCode);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	353 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	354 #endif
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	355 assert((size_t)(seqStorePtr->sequences - seqStorePtr->sequencesStart) < seqStorePtr->maxNbSeq);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	356 /* copy Literals */
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	357 assert(seqStorePtr->maxNbLit <= 128 KB);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	358 assert(seqStorePtr->lit + litLength <= seqStorePtr->litStart + seqStorePtr->maxNbLit);
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	359 ZSTD_wildcopy(seqStorePtr->lit, literals, (ptrdiff_t)litLength, ZSTD_no_overlap);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	360 seqStorePtr->lit += litLength;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	361
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	362 /* literal Length */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	363 if (litLength>0xFFFF) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	364 assert(seqStorePtr->longLengthID == 0); /* there can only be a single long length */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	365 seqStorePtr->longLengthID = 1;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	366 seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	367 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	368 seqStorePtr->sequences[0].litLength = (U16)litLength;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	369
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	370 /* match offset */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	371 seqStorePtr->sequences[0].offset = offsetCode + 1;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	372
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	373 /* match Length */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	374 if (mlBase>0xFFFF) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	375 assert(seqStorePtr->longLengthID == 0); /* there can only be a single long length */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	376 seqStorePtr->longLengthID = 2;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	377 seqStorePtr->longLengthPos = (U32)(seqStorePtr->sequences - seqStorePtr->sequencesStart);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	378 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	379 seqStorePtr->sequences[0].matchLength = (U16)mlBase;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	380
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	381 seqStorePtr->sequences++;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	382 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	383
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	384
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	385 /-************************************
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	386 * Match length counter
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	387 ***************************************/
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	388 static unsigned ZSTD_NbCommonBytes (size_t val)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	389 {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	390 if (MEM_isLittleEndian()) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	391 if (MEM_64bits()) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	392 # if defined(_MSC_VER) && defined(_WIN64)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	393 unsigned long r = 0;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	394 _BitScanForward64( &r, (U64)val );
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	395 return (unsigned)(r>>3);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	396 # elif defined(__GNUC__) && (__GNUC__ >= 4)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	397 return (__builtin_ctzll((U64)val) >> 3);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	398 # else
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	399 static const int DeBruijnBytePos[64] = { 0, 0, 0, 0, 0, 1, 1, 2,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	400 0, 3, 1, 3, 1, 4, 2, 7,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	401 0, 2, 3, 6, 1, 5, 3, 5,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	402 1, 3, 4, 4, 2, 5, 6, 7,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	403 7, 0, 1, 2, 3, 3, 4, 6,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	404 2, 6, 5, 5, 3, 4, 5, 6,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	405 7, 1, 2, 4, 6, 4, 4, 5,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	406 7, 2, 6, 5, 7, 6, 7, 7 };
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	407 return DeBruijnBytePos[((U64)((val & -(long long)val) * 0x0218A392CDABBD3FULL)) >> 58];
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	408 # endif
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	409 } else { /* 32 bits */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	410 # if defined(_MSC_VER)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	411 unsigned long r=0;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	412 _BitScanForward( &r, (U32)val );
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	413 return (unsigned)(r>>3);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	414 # elif defined(__GNUC__) && (__GNUC__ >= 3)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	415 return (__builtin_ctz((U32)val) >> 3);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	416 # else
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	417 static const int DeBruijnBytePos[32] = { 0, 0, 3, 0, 3, 1, 3, 0,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	418 3, 2, 2, 1, 3, 2, 0, 1,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	419 3, 3, 1, 2, 2, 2, 2, 0,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	420 3, 1, 2, 0, 1, 0, 1, 1 };
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	421 return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	422 # endif
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	423 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	424 } else { /* Big Endian CPU */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	425 if (MEM_64bits()) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	426 # if defined(_MSC_VER) && defined(_WIN64)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	427 unsigned long r = 0;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	428 _BitScanReverse64( &r, val );
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	429 return (unsigned)(r>>3);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	430 # elif defined(__GNUC__) && (__GNUC__ >= 4)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	431 return (__builtin_clzll(val) >> 3);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	432 # else
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	433 unsigned r;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	434 const unsigned n32 = sizeof(size_t)4; / calculate this way due to compiler complaining in 32-bits mode */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	435 if (!(val>>n32)) { r=4; } else { r=0; val>>=n32; }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	436 if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	437 r += (!val);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	438 return r;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	439 # endif
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	440 } else { /* 32 bits */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	441 # if defined(_MSC_VER)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	442 unsigned long r = 0;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	443 _BitScanReverse( &r, (unsigned long)val );
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	444 return (unsigned)(r>>3);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	445 # elif defined(__GNUC__) && (__GNUC__ >= 3)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	446 return (__builtin_clz((U32)val) >> 3);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	447 # else
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	448 unsigned r;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	449 if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	450 r += (!val);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	451 return r;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	452 # endif
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	453 } }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	454 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	455
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	456
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	457 MEM_STATIC size_t ZSTD_count(const BYTE* pIn, const BYTE* pMatch, const BYTE* const pInLimit)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	458 {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	459 const BYTE* const pStart = pIn;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	460 const BYTE* const pInLoopLimit = pInLimit - (sizeof(size_t)-1);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	461
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	462 if (pIn < pInLoopLimit) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	463 { size_t const diff = MEM_readST(pMatch) ^ MEM_readST(pIn);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	464 if (diff) return ZSTD_NbCommonBytes(diff); }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	465 pIn+=sizeof(size_t); pMatch+=sizeof(size_t);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	466 while (pIn < pInLoopLimit) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	467 size_t const diff = MEM_readST(pMatch) ^ MEM_readST(pIn);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	468 if (!diff) { pIn+=sizeof(size_t); pMatch+=sizeof(size_t); continue; }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	469 pIn += ZSTD_NbCommonBytes(diff);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	470 return (size_t)(pIn - pStart);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	471 } }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	472 if (MEM_64bits() && (pIn<(pInLimit-3)) && (MEM_read32(pMatch) == MEM_read32(pIn))) { pIn+=4; pMatch+=4; }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	473 if ((pIn<(pInLimit-1)) && (MEM_read16(pMatch) == MEM_read16(pIn))) { pIn+=2; pMatch+=2; }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	474 if ((pIn<pInLimit) && (pMatch == pIn)) pIn++;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	475 return (size_t)(pIn - pStart);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	476 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	477
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	478 /** ZSTD_count_2segments() :
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	479 * can count match length with `ip` & `match` in 2 different segments.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	480 * convention : on reaching mEnd, match count continue starting from iStart
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	481 */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	482 MEM_STATIC size_t
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	483 ZSTD_count_2segments(const BYTE* ip, const BYTE* match,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	484 const BYTE* iEnd, const BYTE* mEnd, const BYTE* iStart)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	485 {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	486 const BYTE* const vEnd = MIN( ip + (mEnd - match), iEnd);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	487 size_t const matchLength = ZSTD_count(ip, match, vEnd);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	488 if (match + matchLength != mEnd) return matchLength;
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	489 DEBUGLOG(7, "ZSTD_count_2segments: found a 2-parts match (current length==%zu)", matchLength);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	490 DEBUGLOG(7, "distance from match beginning to end dictionary = %zi", mEnd - match);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	491 DEBUGLOG(7, "distance from current pos to end buffer = %zi", iEnd - ip);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	492 DEBUGLOG(7, "next byte : ip==%02X, istart==%02X", ip[matchLength], *iStart);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	493 DEBUGLOG(7, "final match length = %zu", matchLength + ZSTD_count(ip+matchLength, iStart, iEnd));
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	494 return matchLength + ZSTD_count(ip+matchLength, iStart, iEnd);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	495 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	496
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	497
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	498 /-************************************
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	499 * Hashes
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	500 ***************************************/
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	501 static const U32 prime3bytes = 506832829U;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	502 static U32 ZSTD_hash3(U32 u, U32 h) { return ((u << (32-24)) * prime3bytes) >> (32-h) ; }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	503 MEM_STATIC size_t ZSTD_hash3Ptr(const void* ptr, U32 h) { return ZSTD_hash3(MEM_readLE32(ptr), h); } /* only in zstd_opt.h */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	504
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	505 static const U32 prime4bytes = 2654435761U;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	506 static U32 ZSTD_hash4(U32 u, U32 h) { return (u * prime4bytes) >> (32-h) ; }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	507 static size_t ZSTD_hash4Ptr(const void* ptr, U32 h) { return ZSTD_hash4(MEM_read32(ptr), h); }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	508
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	509 static const U64 prime5bytes = 889523592379ULL;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	510 static size_t ZSTD_hash5(U64 u, U32 h) { return (size_t)(((u << (64-40)) * prime5bytes) >> (64-h)) ; }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	511 static size_t ZSTD_hash5Ptr(const void* p, U32 h) { return ZSTD_hash5(MEM_readLE64(p), h); }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	512
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	513 static const U64 prime6bytes = 227718039650203ULL;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	514 static size_t ZSTD_hash6(U64 u, U32 h) { return (size_t)(((u << (64-48)) * prime6bytes) >> (64-h)) ; }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	515 static size_t ZSTD_hash6Ptr(const void* p, U32 h) { return ZSTD_hash6(MEM_readLE64(p), h); }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	516
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	517 static const U64 prime7bytes = 58295818150454627ULL;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	518 static size_t ZSTD_hash7(U64 u, U32 h) { return (size_t)(((u << (64-56)) * prime7bytes) >> (64-h)) ; }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	519 static size_t ZSTD_hash7Ptr(const void* p, U32 h) { return ZSTD_hash7(MEM_readLE64(p), h); }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	520
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	521 static const U64 prime8bytes = 0xCF1BBCDCB7A56463ULL;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	522 static size_t ZSTD_hash8(U64 u, U32 h) { return (size_t)(((u) * prime8bytes) >> (64-h)) ; }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	523 static size_t ZSTD_hash8Ptr(const void* p, U32 h) { return ZSTD_hash8(MEM_readLE64(p), h); }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	524
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	525 MEM_STATIC size_t ZSTD_hashPtr(const void* p, U32 hBits, U32 mls)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	526 {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	527 switch(mls)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	528 {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	529 default:
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	530 case 4: return ZSTD_hash4Ptr(p, hBits);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	531 case 5: return ZSTD_hash5Ptr(p, hBits);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	532 case 6: return ZSTD_hash6Ptr(p, hBits);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	533 case 7: return ZSTD_hash7Ptr(p, hBits);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	534 case 8: return ZSTD_hash8Ptr(p, hBits);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	535 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	536 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	537
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	538 /** ZSTD_ipow() :
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	539 * Return base^exponent.
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	540 */
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	541 static U64 ZSTD_ipow(U64 base, U64 exponent)
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	542 {
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	543 U64 power = 1;
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	544 while (exponent) {
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	545 if (exponent & 1) power *= base;
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	546 exponent >>= 1;
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	547 base *= base;
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	548 }
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	549 return power;
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	550 }
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	551
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	552 #define ZSTD_ROLL_HASH_CHAR_OFFSET 10
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	553
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	554 /** ZSTD_rollingHash_append() :
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	555 * Add the buffer to the hash value.
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	556 */
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	557 static U64 ZSTD_rollingHash_append(U64 hash, void const* buf, size_t size)
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	558 {
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	559 BYTE const* istart = (BYTE const*)buf;
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	560 size_t pos;
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	561 for (pos = 0; pos < size; ++pos) {
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	562 hash *= prime8bytes;
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	563 hash += istart[pos] + ZSTD_ROLL_HASH_CHAR_OFFSET;
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	564 }
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	565 return hash;
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	566 }
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	567
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	568 /** ZSTD_rollingHash_compute() :
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	569 * Compute the rolling hash value of the buffer.
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	570 */
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	571 MEM_STATIC U64 ZSTD_rollingHash_compute(void const* buf, size_t size)
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	572 {
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	573 return ZSTD_rollingHash_append(0, buf, size);
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	574 }
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	575
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	576 /** ZSTD_rollingHash_primePower() :
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	577 * Compute the primePower to be passed to ZSTD_rollingHash_rotate() for a hash
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	578 * over a window of length bytes.
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	579 */
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	580 MEM_STATIC U64 ZSTD_rollingHash_primePower(U32 length)
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	581 {
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	582 return ZSTD_ipow(prime8bytes, length - 1);
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	583 }
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	584
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	585 /** ZSTD_rollingHash_rotate() :
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	586 * Rotate the rolling hash by one byte.
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	587 */
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	588 MEM_STATIC U64 ZSTD_rollingHash_rotate(U64 hash, BYTE toRemove, BYTE toAdd, U64 primePower)
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	589 {
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	590 hash -= (toRemove + ZSTD_ROLL_HASH_CHAR_OFFSET) * primePower;
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	591 hash *= prime8bytes;
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	592 hash += toAdd + ZSTD_ROLL_HASH_CHAR_OFFSET;
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	593 return hash;
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	594 }
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	595
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	596 /-************************************
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	597 * Round buffer management
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	598 ***************************************/
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	599 #if (ZSTD_WINDOWLOG_MAX_64 > 31)
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	600 # error "ZSTD_WINDOWLOG_MAX is too large : would overflow ZSTD_CURRENT_MAX"
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	601 #endif
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	602 /* Max current allowed */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	603 #define ZSTD_CURRENT_MAX ((3U << 29) + (1U << ZSTD_WINDOWLOG_MAX))
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	604 /* Maximum chunk size before overflow correction needs to be called again */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	605 #define ZSTD_CHUNKSIZE_MAX \
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	606 ( ((U32)-1) /* Maximum ending current index */ \
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	607 - ZSTD_CURRENT_MAX) /* Maximum beginning lowLimit */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	608
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	609 /**
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	610 * ZSTD_window_clear():
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	611 * Clears the window containing the history by simply setting it to empty.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	612 */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	613 MEM_STATIC void ZSTD_window_clear(ZSTD_window_t* window)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	614 {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	615 size_t const endT = (size_t)(window->nextSrc - window->base);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	616 U32 const end = (U32)endT;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	617
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	618 window->lowLimit = end;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	619 window->dictLimit = end;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	620 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	621
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	622 /**
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	623 * ZSTD_window_hasExtDict():
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	624 * Returns non-zero if the window has a non-empty extDict.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	625 */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	626 MEM_STATIC U32 ZSTD_window_hasExtDict(ZSTD_window_t const window)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	627 {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	628 return window.lowLimit < window.dictLimit;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	629 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	630
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	631 /**
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	632 * ZSTD_matchState_dictMode():
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	633 * Inspects the provided matchState and figures out what dictMode should be
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	634 * passed to the compressor.
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	635 */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	636 MEM_STATIC ZSTD_dictMode_e ZSTD_matchState_dictMode(const ZSTD_matchState_t *ms)
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	637 {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	638 return ZSTD_window_hasExtDict(ms->window) ?
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	639 ZSTD_extDict :
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	640 ms->dictMatchState != NULL ?
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	641 ZSTD_dictMatchState :
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	642 ZSTD_noDict;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	643 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	644
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	645 /**
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	646 * ZSTD_window_needOverflowCorrection():
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	647 * Returns non-zero if the indices are getting too large and need overflow
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	648 * protection.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	649 */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	650 MEM_STATIC U32 ZSTD_window_needOverflowCorrection(ZSTD_window_t const window,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	651 void const* srcEnd)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	652 {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	653 U32 const current = (U32)((BYTE const*)srcEnd - window.base);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	654 return current > ZSTD_CURRENT_MAX;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	655 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	656
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	657 /**
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	658 * ZSTD_window_correctOverflow():
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	659 * Reduces the indices to protect from index overflow.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	660 * Returns the correction made to the indices, which must be applied to every
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	661 * stored index.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	662 *
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	663 * The least significant cycleLog bits of the indices must remain the same,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	664 * which may be 0. Every index up to maxDist in the past must be valid.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	665 * NOTE: (maxDist & cycleMask) must be zero.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	666 */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	667 MEM_STATIC U32 ZSTD_window_correctOverflow(ZSTD_window_t* window, U32 cycleLog,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	668 U32 maxDist, void const* src)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	669 {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	670 /* preemptive overflow correction:
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	671 * 1. correction is large enough:
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	672 * lowLimit > (3<<29) ==> current > 3<<29 + 1<<windowLog
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	673 * 1<<windowLog <= newCurrent < 1<<chainLog + 1<<windowLog
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	674 *
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	675 * current - newCurrent
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	676 * > (3<<29 + 1<<windowLog) - (1<<windowLog + 1<<chainLog)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	677 * > (3<<29) - (1<<chainLog)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	678 * > (3<<29) - (1<<30) (NOTE: chainLog <= 30)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	679 * > 1<<29
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	680 *
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	681 * 2. (ip+ZSTD_CHUNKSIZE_MAX - cctx->base) doesn't overflow:
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	682 * After correction, current is less than (1<<chainLog + 1<<windowLog).
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	683 * In 64-bit mode we are safe, because we have 64-bit ptrdiff_t.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	684 * In 32-bit mode we are safe, because (chainLog <= 29), so
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	685 * ip+ZSTD_CHUNKSIZE_MAX - cctx->base < 1<<32.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	686 * 3. (cctx->lowLimit + 1<<windowLog) < 1<<32:
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	687 * windowLog <= 31 ==> 3<<29 + 1<<windowLog < 7<<29 < 1<<32.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	688 */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	689 U32 const cycleMask = (1U << cycleLog) - 1;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	690 U32 const current = (U32)((BYTE const*)src - window->base);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	691 U32 const newCurrent = (current & cycleMask) + maxDist;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	692 U32 const correction = current - newCurrent;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	693 assert((maxDist & cycleMask) == 0);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	694 assert(current > newCurrent);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	695 /* Loose bound, should be around 1<<29 (see above) */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	696 assert(correction > 1<<28);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	697
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	698 window->base += correction;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	699 window->dictBase += correction;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	700 window->lowLimit -= correction;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	701 window->dictLimit -= correction;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	702
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	703 DEBUGLOG(4, "Correction of 0x%x bytes to lowLimit=0x%x", correction,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	704 window->lowLimit);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	705 return correction;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	706 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	707
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	708 /**
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	709 * ZSTD_window_enforceMaxDist():
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	710 * Updates lowLimit so that:
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	711 * (srcEnd - base) - lowLimit == maxDist + loadedDictEnd
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	712 *
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	713 * It ensures index is valid as long as index >= lowLimit.
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	714 * This must be called before a block compression call.
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	715 *
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	716 * loadedDictEnd is only defined if a dictionary is in use for current compression.
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	717 * As the name implies, loadedDictEnd represents the index at end of dictionary.
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	718 * The value lies within context's referential, it can be directly compared to blockEndIdx.
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	719 *
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	720 * If loadedDictEndPtr is NULL, no dictionary is in use, and we use loadedDictEnd == 0.
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	721 * If loadedDictEndPtr is not NULL, we set it to zero after updating lowLimit.
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	722 * This is because dictionaries are allowed to be referenced fully
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	723 * as long as the last byte of the dictionary is in the window.
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	724 * Once input has progressed beyond window size, dictionary cannot be referenced anymore.
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	725 *
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	726 * In normal dict mode, the dictionary lies between lowLimit and dictLimit.
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	727 * In dictMatchState mode, lowLimit and dictLimit are the same,
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	728 * and the dictionary is below them.
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	729 * forceWindow and dictMatchState are therefore incompatible.
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	730 */
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	731 MEM_STATIC void
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	732 ZSTD_window_enforceMaxDist(ZSTD_window_t* window,
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	733 const void* blockEnd,
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	734 U32 maxDist,
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	735 U32* loadedDictEndPtr,
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	736 const ZSTD_matchState_t** dictMatchStatePtr)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	737 {
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	738 U32 const blockEndIdx = (U32)((BYTE const*)blockEnd - window->base);
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	739 U32 const loadedDictEnd = (loadedDictEndPtr != NULL) ? *loadedDictEndPtr : 0;
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	740 DEBUGLOG(5, "ZSTD_window_enforceMaxDist: blockEndIdx=%u, maxDist=%u, loadedDictEnd=%u",
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	741 (unsigned)blockEndIdx, (unsigned)maxDist, (unsigned)loadedDictEnd);
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	742
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	743 /* - When there is no dictionary : loadedDictEnd == 0.
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	744 In which case, the test (blockEndIdx > maxDist) is merely to avoid
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	745 overflowing next operation `newLowLimit = blockEndIdx - maxDist`.
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	746 - When there is a standard dictionary :
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	747 Index referential is copied from the dictionary,
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	748 which means it starts from 0.
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	749 In which case, loadedDictEnd == dictSize,
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	750 and it makes sense to compare `blockEndIdx > maxDist + dictSize`
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	751 since `blockEndIdx` also starts from zero.
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	752 - When there is an attached dictionary :
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	753 loadedDictEnd is expressed within the referential of the context,
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	754 so it can be directly compared against blockEndIdx.
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	755 */
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	756 if (blockEndIdx > maxDist + loadedDictEnd) {
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	757 U32 const newLowLimit = blockEndIdx - maxDist;
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	758 if (window->lowLimit < newLowLimit) window->lowLimit = newLowLimit;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	759 if (window->dictLimit < window->lowLimit) {
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	760 DEBUGLOG(5, "Update dictLimit to match lowLimit, from %u to %u",
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	761 (unsigned)window->dictLimit, (unsigned)window->lowLimit);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	762 window->dictLimit = window->lowLimit;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	763 }
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	764 /* On reaching window size, dictionaries are invalidated */
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	765 if (loadedDictEndPtr) *loadedDictEndPtr = 0;
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	766 if (dictMatchStatePtr) *dictMatchStatePtr = NULL;
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	767 }
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	768 }
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	769
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	770 /* Similar to ZSTD_window_enforceMaxDist(),
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	771 * but only invalidates dictionary
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	772 * when input progresses beyond window size.
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	773 * assumption : loadedDictEndPtr and dictMatchStatePtr are valid (non NULL)
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	774 * loadedDictEnd uses same referential as window->base
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	775 * maxDist is the window size */
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	776 MEM_STATIC void
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	777 ZSTD_checkDictValidity(const ZSTD_window_t* window,
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	778 const void* blockEnd,
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	779 U32 maxDist,
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	780 U32* loadedDictEndPtr,
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	781 const ZSTD_matchState_t** dictMatchStatePtr)
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	782 {
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	783 assert(loadedDictEndPtr != NULL);
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	784 assert(dictMatchStatePtr != NULL);
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	785 { U32 const blockEndIdx = (U32)((BYTE const*)blockEnd - window->base);
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	786 U32 const loadedDictEnd = *loadedDictEndPtr;
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	787 DEBUGLOG(5, "ZSTD_checkDictValidity: blockEndIdx=%u, maxDist=%u, loadedDictEnd=%u",
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	788 (unsigned)blockEndIdx, (unsigned)maxDist, (unsigned)loadedDictEnd);
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	789 assert(blockEndIdx >= loadedDictEnd);
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	790
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	791 if (blockEndIdx > loadedDictEnd + maxDist) {
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	792 /* On reaching window size, dictionaries are invalidated.
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	793 * For simplification, if window size is reached anywhere within next block,
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	794 * the dictionary is invalidated for the full block.
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	795 */
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	796 DEBUGLOG(6, "invalidating dictionary for current block (distance > windowSize)");
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	797 *loadedDictEndPtr = 0;
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	798 *dictMatchStatePtr = NULL;
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	799 } else {
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	800 if (*loadedDictEndPtr != 0) {
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	801 DEBUGLOG(6, "dictionary considered valid for current block");
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	802 } } }
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	803 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	804
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	805 /**
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	806 * ZSTD_window_update():
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	807 * Updates the window by appending [src, src + srcSize) to the window.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	808 * If it is not contiguous, the current prefix becomes the extDict, and we
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	809 * forget about the extDict. Handles overlap of the prefix and extDict.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	810 * Returns non-zero if the segment is contiguous.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	811 */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	812 MEM_STATIC U32 ZSTD_window_update(ZSTD_window_t* window,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	813 void const* src, size_t srcSize)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	814 {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	815 BYTE const* const ip = (BYTE const*)src;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	816 U32 contiguous = 1;
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	817 DEBUGLOG(5, "ZSTD_window_update");
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	818 /* Check if blocks follow each other */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	819 if (src != window->nextSrc) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	820 /* not contiguous */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	821 size_t const distanceFromBase = (size_t)(window->nextSrc - window->base);
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	822 DEBUGLOG(5, "Non contiguous blocks, new segment starts at %u", window->dictLimit);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	823 window->lowLimit = window->dictLimit;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	824 assert(distanceFromBase == (size_t)(U32)distanceFromBase); /* should never overflow */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	825 window->dictLimit = (U32)distanceFromBase;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	826 window->dictBase = window->base;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	827 window->base = ip - distanceFromBase;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	828 // ms->nextToUpdate = window->dictLimit;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	829 if (window->dictLimit - window->lowLimit < HASH_READ_SIZE) window->lowLimit = window->dictLimit; /* too small extDict */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	830 contiguous = 0;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	831 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	832 window->nextSrc = ip + srcSize;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	833 /* if input and dictionary overlap : reduce dictionary (area presumed modified by input) */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	834 if ( (ip+srcSize > window->dictBase + window->lowLimit)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	835 & (ip < window->dictBase + window->dictLimit)) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	836 ptrdiff_t const highInputIdx = (ip + srcSize) - window->dictBase;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	837 U32 const lowLimitMax = (highInputIdx > (ptrdiff_t)window->dictLimit) ? window->dictLimit : (U32)highInputIdx;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	838 window->lowLimit = lowLimitMax;
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	839 DEBUGLOG(5, "Overlapping extDict and input : new lowLimit = %u", window->lowLimit);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	840 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	841 return contiguous;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	842 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	843
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	844 MEM_STATIC U32 ZSTD_getLowestMatchIndex(const ZSTD_matchState_t* ms, U32 current, unsigned windowLog)
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	845 {
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	846 U32 const maxDistance = 1U << windowLog;
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	847 U32 const lowestValid = ms->window.lowLimit;
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	848 U32 const withinWindow = (current - lowestValid > maxDistance) ? current - maxDistance : lowestValid;
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	849 U32 const isDictionary = (ms->loadedDictEnd != 0);
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	850 U32 const matchLowest = isDictionary ? lowestValid : withinWindow;
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	851 return matchLowest;
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	852 }
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	853
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	854
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	855
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	856 /* debug functions */
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	857 #if (DEBUGLEVEL>=2)
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	858
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	859 MEM_STATIC double ZSTD_fWeight(U32 rawStat)
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	860 {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	861 U32 const fp_accuracy = 8;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	862 U32 const fp_multiplier = (1 << fp_accuracy);
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	863 U32 const newStat = rawStat + 1;
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	864 U32 const hb = ZSTD_highbit32(newStat);
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	865 U32 const BWeight = hb * fp_multiplier;
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	866 U32 const FWeight = (newStat << fp_accuracy) >> hb;
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	867 U32 const weight = BWeight + FWeight;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	868 assert(hb + fp_accuracy < 31);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	869 return (double)weight / fp_multiplier;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	870 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	871
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	872 /* display a table content,
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	873 * listing each element, its frequency, and its predicted bit cost */
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	874 MEM_STATIC void ZSTD_debugTable(const U32* table, U32 max)
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	875 {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	876 unsigned u, sum;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	877 for (u=0, sum=0; u<=max; u++) sum += table[u];
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	878 DEBUGLOG(2, "total nb elts: %u", sum);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	879 for (u=0; u<=max; u++) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	880 DEBUGLOG(2, "%2u: %5u (%.2f)",
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	881 u, table[u], ZSTD_fWeight(sum) - ZSTD_fWeight(table[u]) );
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	882 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	883 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	884
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	885 #endif
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	886
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	887
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	888 #if defined (__cplusplus)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	889 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	890 #endif
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	891
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	892
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	893 /* ==============================================================
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	894 * Private declarations
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	895 * These prototypes shall only be called from within lib/compress
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	896 * ============================================================== */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	897
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	898 /* ZSTD_getCParamsFromCCtxParams() :
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	899 * cParams are built depending on compressionLevel, src size hints,
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	900 * LDM and manually set compression parameters.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	901 */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	902 ZSTD_compressionParameters ZSTD_getCParamsFromCCtxParams(
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	903 const ZSTD_CCtx_params* CCtxParams, U64 srcSizeHint, size_t dictSize);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	904
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	905 /*! ZSTD_initCStream_internal() :
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	906 * Private use only. Init streaming operation.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	907 * expects params to be valid.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	908 * must receive dict, or cdict, or none, but not both.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	909 * @return : 0, or an error code */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	910 size_t ZSTD_initCStream_internal(ZSTD_CStream* zcs,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	911 const void* dict, size_t dictSize,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	912 const ZSTD_CDict* cdict,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	913 ZSTD_CCtx_params params, unsigned long long pledgedSrcSize);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	914
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	915 void ZSTD_resetSeqStore(seqStore_t* ssPtr);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	916
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	917 /*! ZSTD_getCParamsFromCDict() :
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	918 * as the name implies */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	919 ZSTD_compressionParameters ZSTD_getCParamsFromCDict(const ZSTD_CDict* cdict);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	920
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	921 /* ZSTD_compressBegin_advanced_internal() :
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	922 * Private use only. To be called from zstdmt_compress.c. */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	923 size_t ZSTD_compressBegin_advanced_internal(ZSTD_CCtx* cctx,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	924 const void* dict, size_t dictSize,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	925 ZSTD_dictContentType_e dictContentType,
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	926 ZSTD_dictTableLoadMethod_e dtlm,
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	927 const ZSTD_CDict* cdict,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	928 ZSTD_CCtx_params params,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	929 unsigned long long pledgedSrcSize);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	930
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	931 /* ZSTD_compress_advanced_internal() :
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	932 * Private use only. To be called from zstdmt_compress.c. */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	933 size_t ZSTD_compress_advanced_internal(ZSTD_CCtx* cctx,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	934 void* dst, size_t dstCapacity,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	935 const void* src, size_t srcSize,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	936 const void* dict,size_t dictSize,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	937 ZSTD_CCtx_params params);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	938
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	939
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	940 /* ZSTD_writeLastEmptyBlock() :
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	941 * output an empty Block with end-of-frame mark to complete a frame
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	942 * @return : size of data written into `dst` (== ZSTD_blockHeaderSize (defined in zstd_internal.h))
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	943 * or an error code if `dstCapacity` is too small (<ZSTD_blockHeaderSize)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	944 */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	945 size_t ZSTD_writeLastEmptyBlock(void* dst, size_t dstCapacity);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	946
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	947
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	948 /* ZSTD_referenceExternalSequences() :
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	949 * Must be called before starting a compression operation.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	950 * seqs must parse a prefix of the source.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	951 * This cannot be used when long range matching is enabled.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	952 * Zstd will use these sequences, and pass the literals to a secondary block
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	953 * compressor.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	954 * @return : An error code on failure.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	955 * NOTE: seqs are not verified! Invalid sequences can cause out-of-bounds memory
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	956 * access and data corruption.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	957 */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	958 size_t ZSTD_referenceExternalSequences(ZSTD_CCtx* cctx, rawSeq* seq, size_t nbSeq);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	959
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	960
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	961 #endif /* ZSTD_COMPRESS_H */

Mercurial > public > mercurial-scm > hg

annotate contrib/python-zstandard/zstd/compress/zstd_compress_internal.h @ 42937:69de49c4e39c