Mercurial > public > mercurial-scm > hg-stable
annotate contrib/python-zstandard/zstd/common/zstd_internal.h @ 30443:2e484bdea8c4
zstd: vendor zstd 1.1.1
zstd is a new compression format and it is awesome, yielding
higher compression ratios and significantly faster compression
and decompression operations compared to zlib (our current
compression engine of choice) across the board.
We want zstd to be a 1st class citizen in Mercurial and to eventually
be the preferred compression format for various operations.
This patch starts the formal process of supporting zstd by vendoring
a copy of zstd. Why do we need to vendor zstd? Good question.
First, zstd is relatively new and not widely available yet. If we
didn't vendor zstd or distribute it with Mercurial, most users likely
wouldn't have zstd installed or even available to install. What good
is a feature if you can't use it? Vendoring and distributing the zstd
sources gives us the highest liklihood that zstd will be available to
Mercurial installs.
Second, the Python bindings to zstd (which will be vendored in a
separate changeset) make use of zstd APIs that are only available
via static linking. One reason they are only available via static
linking is that they are unstable and could change at any time.
While it might be possible for the Python bindings to attempt to
talk to different versions of the zstd C library, the safest thing to
do is link against a specific, known-working version of zstd. This
is why the Python zstd bindings themselves vendor zstd and why we
must as well. This also explains why the added files are in a
"python-zstandard" directory.
The added files are from the 1.1.1 release of zstd (Git commit
4c0b44f8ced84c4c8edfa07b564d31e4fa3e8885 from
https://github.com/facebook/zstd) and are added without modifications.
Not all files from the zstd "distribution" have been added. Notably
missing are files to support interacting with "legacy," pre-1.0
versions of zstd. The decision of which files to include is made by
the upstream python-zstandard project (which I'm the author of). The
files in this commit are a snapshot of the files from the 0.5.0
release of that project, Git commit
e637c1b214d5f869cf8116c550dcae23ec13b677 from
https://github.com/indygreg/python-zstandard.
author | Gregory Szorc <gregory.szorc@gmail.com> |
---|---|
date | Thu, 10 Nov 2016 21:45:29 -0800 |
parents | |
children | b54a2984cdd4 |
rev | line source |
---|---|
30443
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
1 /** |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
2 * Copyright (c) 2016-present, Yann Collet, Facebook, Inc. |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
3 * All rights reserved. |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
4 * |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
5 * This source code is licensed under the BSD-style license found in the |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
6 * LICENSE file in the root directory of this source tree. An additional grant |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
7 * of patent rights can be found in the PATENTS file in the same directory. |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
8 */ |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
9 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
10 #ifndef ZSTD_CCOMMON_H_MODULE |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
11 #define ZSTD_CCOMMON_H_MODULE |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
12 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
13 /*-******************************************************* |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
14 * Compiler specifics |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
15 *********************************************************/ |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
16 #ifdef _MSC_VER /* Visual Studio */ |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
17 # define FORCE_INLINE static __forceinline |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
18 # include <intrin.h> /* For Visual 2005 */ |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
19 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
20 # pragma warning(disable : 4324) /* disable: C4324: padded structure */ |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
21 # pragma warning(disable : 4100) /* disable: C4100: unreferenced formal parameter */ |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
22 #else |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
23 # if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */ |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
24 # ifdef __GNUC__ |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
25 # define FORCE_INLINE static inline __attribute__((always_inline)) |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
26 # else |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
27 # define FORCE_INLINE static inline |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
28 # endif |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
29 # else |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
30 # define FORCE_INLINE static |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
31 # endif /* __STDC_VERSION__ */ |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
32 #endif |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
33 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
34 #ifdef _MSC_VER |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
35 # define FORCE_NOINLINE static __declspec(noinline) |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
36 #else |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
37 # ifdef __GNUC__ |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
38 # define FORCE_NOINLINE static __attribute__((__noinline__)) |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
39 # else |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
40 # define FORCE_NOINLINE static |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
41 # endif |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
42 #endif |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
43 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
44 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
45 /*-************************************* |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
46 * Dependencies |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
47 ***************************************/ |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
48 #include "mem.h" |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
49 #include "error_private.h" |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
50 #define ZSTD_STATIC_LINKING_ONLY |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
51 #include "zstd.h" |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
52 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
53 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
54 /*-************************************* |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
55 * shared macros |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
56 ***************************************/ |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
57 #define MIN(a,b) ((a)<(b) ? (a) : (b)) |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
58 #define MAX(a,b) ((a)>(b) ? (a) : (b)) |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
59 #define CHECK_F(f) { size_t const errcod = f; if (ERR_isError(errcod)) return errcod; } /* check and Forward error code */ |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
60 #define CHECK_E(f, e) { size_t const errcod = f; if (ERR_isError(errcod)) return ERROR(e); } /* check and send Error code */ |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
61 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
62 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
63 /*-************************************* |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
64 * Common constants |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
65 ***************************************/ |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
66 #define ZSTD_OPT_NUM (1<<12) |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
67 #define ZSTD_DICT_MAGIC 0xEC30A437 /* v0.7+ */ |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
68 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
69 #define ZSTD_REP_NUM 3 /* number of repcodes */ |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
70 #define ZSTD_REP_CHECK (ZSTD_REP_NUM) /* number of repcodes to check by the optimal parser */ |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
71 #define ZSTD_REP_MOVE (ZSTD_REP_NUM-1) |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
72 #define ZSTD_REP_MOVE_OPT (ZSTD_REP_NUM) |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
73 static const U32 repStartValue[ZSTD_REP_NUM] = { 1, 4, 8 }; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
74 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
75 #define KB *(1 <<10) |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
76 #define MB *(1 <<20) |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
77 #define GB *(1U<<30) |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
78 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
79 #define BIT7 128 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
80 #define BIT6 64 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
81 #define BIT5 32 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
82 #define BIT4 16 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
83 #define BIT1 2 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
84 #define BIT0 1 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
85 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
86 #define ZSTD_WINDOWLOG_ABSOLUTEMIN 10 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
87 static const size_t ZSTD_fcs_fieldSize[4] = { 0, 2, 4, 8 }; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
88 static const size_t ZSTD_did_fieldSize[4] = { 0, 1, 2, 4 }; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
89 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
90 #define ZSTD_BLOCKHEADERSIZE 3 /* C standard doesn't allow `static const` variable to be init using another `static const` variable */ |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
91 static const size_t ZSTD_blockHeaderSize = ZSTD_BLOCKHEADERSIZE; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
92 typedef enum { bt_raw, bt_rle, bt_compressed, bt_reserved } blockType_e; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
93 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
94 #define MIN_SEQUENCES_SIZE 1 /* nbSeq==0 */ |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
95 #define MIN_CBLOCK_SIZE (1 /*litCSize*/ + 1 /* RLE or RAW */ + MIN_SEQUENCES_SIZE /* nbSeq==0 */) /* for a non-null block */ |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
96 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
97 #define HufLog 12 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
98 typedef enum { set_basic, set_rle, set_compressed, set_repeat } symbolEncodingType_e; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
99 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
100 #define LONGNBSEQ 0x7F00 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
101 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
102 #define MINMATCH 3 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
103 #define EQUAL_READ32 4 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
104 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
105 #define Litbits 8 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
106 #define MaxLit ((1<<Litbits) - 1) |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
107 #define MaxML 52 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
108 #define MaxLL 35 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
109 #define MaxOff 28 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
110 #define MaxSeq MAX(MaxLL, MaxML) /* Assumption : MaxOff < MaxLL,MaxML */ |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
111 #define MLFSELog 9 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
112 #define LLFSELog 9 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
113 #define OffFSELog 8 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
114 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
115 static const U32 LL_bits[MaxLL+1] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
116 1, 1, 1, 1, 2, 2, 3, 3, 4, 6, 7, 8, 9,10,11,12, |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
117 13,14,15,16 }; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
118 static const S16 LL_defaultNorm[MaxLL+1] = { 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
119 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 1, 1, 1, 1, 1, |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
120 -1,-1,-1,-1 }; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
121 #define LL_DEFAULTNORMLOG 6 /* for static allocation */ |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
122 static const U32 LL_defaultNormLog = LL_DEFAULTNORMLOG; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
123 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
124 static const U32 ML_bits[MaxML+1] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
125 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
126 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 7, 8, 9,10,11, |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
127 12,13,14,15,16 }; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
128 static const S16 ML_defaultNorm[MaxML+1] = { 1, 4, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
129 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
130 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,-1,-1, |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
131 -1,-1,-1,-1,-1 }; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
132 #define ML_DEFAULTNORMLOG 6 /* for static allocation */ |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
133 static const U32 ML_defaultNormLog = ML_DEFAULTNORMLOG; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
134 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
135 static const S16 OF_defaultNorm[MaxOff+1] = { 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
136 1, 1, 1, 1, 1, 1, 1, 1,-1,-1,-1,-1,-1 }; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
137 #define OF_DEFAULTNORMLOG 5 /* for static allocation */ |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
138 static const U32 OF_defaultNormLog = OF_DEFAULTNORMLOG; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
139 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
140 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
141 /*-******************************************* |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
142 * Shared functions to include for inlining |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
143 *********************************************/ |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
144 static void ZSTD_copy8(void* dst, const void* src) { memcpy(dst, src, 8); } |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
145 #define COPY8(d,s) { ZSTD_copy8(d,s); d+=8; s+=8; } |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
146 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
147 /*! ZSTD_wildcopy() : |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
148 * custom version of memcpy(), can copy up to 7 bytes too many (8 bytes if length==0) */ |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
149 #define WILDCOPY_OVERLENGTH 8 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
150 MEM_STATIC void ZSTD_wildcopy(void* dst, const void* src, size_t length) |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
151 { |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
152 const BYTE* ip = (const BYTE*)src; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
153 BYTE* op = (BYTE*)dst; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
154 BYTE* const oend = op + length; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
155 do |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
156 COPY8(op, ip) |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
157 while (op < oend); |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
158 } |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
159 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
160 MEM_STATIC void ZSTD_wildcopy_e(void* dst, const void* src, void* dstEnd) /* should be faster for decoding, but strangely, not verified on all platform */ |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
161 { |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
162 const BYTE* ip = (const BYTE*)src; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
163 BYTE* op = (BYTE*)dst; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
164 BYTE* const oend = (BYTE*)dstEnd; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
165 do |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
166 COPY8(op, ip) |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
167 while (op < oend); |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
168 } |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
169 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
170 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
171 /*-******************************************* |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
172 * Private interfaces |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
173 *********************************************/ |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
174 typedef struct ZSTD_stats_s ZSTD_stats_t; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
175 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
176 typedef struct { |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
177 U32 off; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
178 U32 len; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
179 } ZSTD_match_t; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
180 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
181 typedef struct { |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
182 U32 price; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
183 U32 off; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
184 U32 mlen; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
185 U32 litlen; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
186 U32 rep[ZSTD_REP_NUM]; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
187 } ZSTD_optimal_t; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
188 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
189 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
190 typedef struct seqDef_s { |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
191 U32 offset; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
192 U16 litLength; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
193 U16 matchLength; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
194 } seqDef; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
195 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
196 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
197 typedef struct { |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
198 seqDef* sequencesStart; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
199 seqDef* sequences; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
200 BYTE* litStart; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
201 BYTE* lit; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
202 BYTE* llCode; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
203 BYTE* mlCode; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
204 BYTE* ofCode; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
205 U32 longLengthID; /* 0 == no longLength; 1 == Lit.longLength; 2 == Match.longLength; */ |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
206 U32 longLengthPos; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
207 /* opt */ |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
208 ZSTD_optimal_t* priceTable; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
209 ZSTD_match_t* matchTable; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
210 U32* matchLengthFreq; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
211 U32* litLengthFreq; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
212 U32* litFreq; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
213 U32* offCodeFreq; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
214 U32 matchLengthSum; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
215 U32 matchSum; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
216 U32 litLengthSum; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
217 U32 litSum; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
218 U32 offCodeSum; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
219 U32 log2matchLengthSum; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
220 U32 log2matchSum; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
221 U32 log2litLengthSum; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
222 U32 log2litSum; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
223 U32 log2offCodeSum; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
224 U32 factor; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
225 U32 cachedPrice; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
226 U32 cachedLitLength; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
227 const BYTE* cachedLiterals; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
228 } seqStore_t; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
229 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
230 const seqStore_t* ZSTD_getSeqStore(const ZSTD_CCtx* ctx); |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
231 void ZSTD_seqToCodes(const seqStore_t* seqStorePtr); |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
232 int ZSTD_isSkipFrame(ZSTD_DCtx* dctx); |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
233 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
234 /* custom memory allocation functions */ |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
235 void* ZSTD_defaultAllocFunction(void* opaque, size_t size); |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
236 void ZSTD_defaultFreeFunction(void* opaque, void* address); |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
237 static const ZSTD_customMem defaultCustomMem = { ZSTD_defaultAllocFunction, ZSTD_defaultFreeFunction, NULL }; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
238 void* ZSTD_malloc(size_t size, ZSTD_customMem customMem); |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
239 void ZSTD_free(void* ptr, ZSTD_customMem customMem); |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
240 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
241 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
242 /*====== common function ======*/ |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
243 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
244 MEM_STATIC U32 ZSTD_highbit32(U32 val) |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
245 { |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
246 # if defined(_MSC_VER) /* Visual */ |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
247 unsigned long r=0; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
248 _BitScanReverse(&r, val); |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
249 return (unsigned)r; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
250 # elif defined(__GNUC__) && (__GNUC__ >= 3) /* GCC Intrinsic */ |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
251 return 31 - __builtin_clz(val); |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
252 # else /* Software version */ |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
253 static const int DeBruijnClz[32] = { 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 }; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
254 U32 v = val; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
255 int r; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
256 v |= v >> 1; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
257 v |= v >> 2; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
258 v |= v >> 4; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
259 v |= v >> 8; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
260 v |= v >> 16; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
261 r = DeBruijnClz[(U32)(v * 0x07C4ACDDU) >> 27]; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
262 return r; |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
263 # endif |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
264 } |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
265 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
266 |
2e484bdea8c4
zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff
changeset
|
267 #endif /* ZSTD_CCOMMON_H_MODULE */ |