Mercurial > public > mercurial-scm > hg

annotate contrib/python-zstandard/zstd/common/entropy_common.c @ 40121:73fef626dae3

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
zstandard: vendor python-zstandard 0.10.1 This was just released. 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. setup.py was updated to pass a new argument to python-zstandard's function for returning an Extension instance. Upstream had to change to use relative paths because Python 3.7's packaging doesn't seem to like absolute paths when defining sources, includes, etc. The default relative path calculation is relative to setup_zstd.py which is different from the directory of Mercurial's setup.py. The project contains a vendored copy of zstandard 1.3.6. The old version was 1.3.4. The API should be backwards compatible and nothing in core should need adjusted. However, there is a new "chunker" API that we may find useful in places where we want to emit compressed chunks of a fixed size. There are a pair of bug fixes in 0.10.0 with regards to compressobj() and decompressobj() when block flushing is used. I actually found these bugs when introducing these APIs in Mercurial! But existing Mercurial code is not affected because we don't perform block flushing. # no-check-commit because 3rd party code has different style guidelines Differential Revision: https://phab.mercurial-scm.org/D4911
author Gregory Szorc <gregory.szorc@gmail.com>
date Mon, 08 Oct 2018 16:27:40 -0700
parents b1fb341d8a61
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
30434
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 Common functions of New Generation Entropy library
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
3 Copyright (C) 2016, Yann Collet.
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 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
6
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
7 Redistribution and use in source and binary forms, with or without
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
8 modification, are permitted provided that the following conditions are
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
9 met:
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
10
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
11 * Redistributions of source code must retain the above copyright
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
12 notice, this list of conditions and the following disclaimer.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
13 * Redistributions in binary form must reproduce the above
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
14 copyright notice, this list of conditions and the following disclaimer
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
15 in the documentation and/or other materials provided with the
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
16 distribution.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
17
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
18 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
19 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
20 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
21 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
22 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
23 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
24 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
25 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
26 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
27 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
29
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
30 You can contact the author at :
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
31 - FSE+HUF source repository : https://github.com/Cyan4973/FiniteStateEntropy
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
32 - Public forum : https://groups.google.com/forum/#!forum/lz4c
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
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
35 /* *************************************
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
36 * Dependencies
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
37 ***************************************/
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
38 #include "mem.h"
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
39 #include "error_private.h" /* ERR_*, ERROR */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
40 #define FSE_STATIC_LINKING_ONLY /* FSE_MIN_TABLELOG */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
41 #include "fse.h"
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
42 #define HUF_STATIC_LINKING_ONLY /* HUF_TABLELOG_ABSOLUTEMAX */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
43 #include "huf.h"
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
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
46 /*=== Version ===*/
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
47 unsigned FSE_versionNumber(void) { return FSE_VERSION_NUMBER; }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
48
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
49
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
50 /*=== Error Management ===*/
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
51 unsigned FSE_isError(size_t code) { return ERR_isError(code); }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
52 const char* FSE_getErrorName(size_t code) { return ERR_getErrorName(code); }
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 unsigned HUF_isError(size_t code) { return ERR_isError(code); }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
55 const char* HUF_getErrorName(size_t code) { return ERR_getErrorName(code); }
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
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
58 /*-**************************************************************
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
59 * FSE NCount encoding-decoding
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
60 ****************************************************************/
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
61 size_t FSE_readNCount (short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr,
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
62 const void* headerBuffer, size_t hbSize)
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 const BYTE* const istart = (const BYTE*) headerBuffer;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
65 const BYTE* const iend = istart + hbSize;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
66 const BYTE* ip = istart;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
67 int nbBits;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
68 int remaining;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
69 int threshold;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
70 U32 bitStream;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
71 int bitCount;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
72 unsigned charnum = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
73 int previous0 = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
74
40121
73fef626dae3 zstandard: vendor python-zstandard 0.10.1
Gregory Szorc <gregory.szorc@gmail.com>
parents: 37495
diff changeset
75 if (hbSize < 4) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1
Gregory Szorc <gregory.szorc@gmail.com>
parents: 37495
diff changeset
76 /* This function only works when hbSize >= 4 */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1
Gregory Szorc <gregory.szorc@gmail.com>
parents: 37495
diff changeset
77 char buffer[4];
73fef626dae3 zstandard: vendor python-zstandard 0.10.1
Gregory Szorc <gregory.szorc@gmail.com>
parents: 37495
diff changeset
78 memset(buffer, 0, sizeof(buffer));
73fef626dae3 zstandard: vendor python-zstandard 0.10.1
Gregory Szorc <gregory.szorc@gmail.com>
parents: 37495
diff changeset
79 memcpy(buffer, headerBuffer, hbSize);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1
Gregory Szorc <gregory.szorc@gmail.com>
parents: 37495
diff changeset
80 { size_t const countSize = FSE_readNCount(normalizedCounter, maxSVPtr, tableLogPtr,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1
Gregory Szorc <gregory.szorc@gmail.com>
parents: 37495
diff changeset
81 buffer, sizeof(buffer));
73fef626dae3 zstandard: vendor python-zstandard 0.10.1
Gregory Szorc <gregory.szorc@gmail.com>
parents: 37495
diff changeset
82 if (FSE_isError(countSize)) return countSize;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1
Gregory Szorc <gregory.szorc@gmail.com>
parents: 37495
diff changeset
83 if (countSize > hbSize) return ERROR(corruption_detected);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1
Gregory Szorc <gregory.szorc@gmail.com>
parents: 37495
diff changeset
84 return countSize;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1
Gregory Szorc <gregory.szorc@gmail.com>
parents: 37495
diff changeset
85 } }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1
Gregory Szorc <gregory.szorc@gmail.com>
parents: 37495
diff changeset
86 assert(hbSize >= 4);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1
Gregory Szorc <gregory.szorc@gmail.com>
parents: 37495
diff changeset
87
73fef626dae3 zstandard: vendor python-zstandard 0.10.1
Gregory Szorc <gregory.szorc@gmail.com>
parents: 37495
diff changeset
88 /* init */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1
Gregory Szorc <gregory.szorc@gmail.com>
parents: 37495
diff changeset
89 memset(normalizedCounter, 0, (*maxSVPtr+1) * sizeof(normalizedCounter[0])); /* all symbols not present in NCount have a frequency of 0 */
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
90 bitStream = MEM_readLE32(ip);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
91 nbBits = (bitStream & 0xF) + FSE_MIN_TABLELOG; /* extract tableLog */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
92 if (nbBits > FSE_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
93 bitStream >>= 4;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
94 bitCount = 4;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
95 *tableLogPtr = nbBits;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
96 remaining = (1<<nbBits)+1;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
97 threshold = 1<<nbBits;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
98 nbBits++;
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 while ((remaining>1) & (charnum<=*maxSVPtr)) {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
101 if (previous0) {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
102 unsigned n0 = charnum;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
103 while ((bitStream & 0xFFFF) == 0xFFFF) {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
104 n0 += 24;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
105 if (ip < iend-5) {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
106 ip += 2;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
107 bitStream = MEM_readLE32(ip) >> bitCount;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
108 } else {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
109 bitStream >>= 16;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
110 bitCount += 16;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
111 } }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
112 while ((bitStream & 3) == 3) {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
113 n0 += 3;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
114 bitStream >>= 2;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
115 bitCount += 2;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
116 }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
117 n0 += bitStream & 3;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
118 bitCount += 2;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
119 if (n0 > *maxSVPtr) return ERROR(maxSymbolValue_tooSmall);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
120 while (charnum < n0) normalizedCounter[charnum++] = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
121 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) {
40121
73fef626dae3 zstandard: vendor python-zstandard 0.10.1
Gregory Szorc <gregory.szorc@gmail.com>
parents: 37495
diff changeset
122 assert((bitCount >> 3) <= 3); /* For first condition to work */
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
123 ip += bitCount>>3;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
124 bitCount &= 7;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
125 bitStream = MEM_readLE32(ip) >> bitCount;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
126 } else {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
127 bitStream >>= 2;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
128 } }
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
129 { int const max = (2*threshold-1) - remaining;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
130 int count;
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
131
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
132 if ((bitStream & (threshold-1)) < (U32)max) {
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
133 count = bitStream & (threshold-1);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
134 bitCount += nbBits-1;
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
135 } else {
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
136 count = bitStream & (2*threshold-1);
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
137 if (count >= threshold) count -= max;
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
138 bitCount += nbBits;
30434
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 count--; /* extra accuracy */
37495
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
142 remaining -= count < 0 ? -count : count; /* -1 means +1 */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30822
diff changeset
143 normalizedCounter[charnum++] = (short)count;
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
144 previous0 = !count;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
145 while (remaining < threshold) {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
146 nbBits--;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
147 threshold >>= 1;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
148 }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
149
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
150 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
151 ip += bitCount>>3;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
152 bitCount &= 7;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
153 } else {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
154 bitCount -= (int)(8 * (iend - 4 - ip));
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
155 ip = iend - 4;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
156 }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
157 bitStream = MEM_readLE32(ip) >> (bitCount & 31);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
158 } } /* while ((remaining>1) & (charnum<=*maxSVPtr)) */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
159 if (remaining != 1) return ERROR(corruption_detected);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
160 if (bitCount > 32) return ERROR(corruption_detected);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
161 *maxSVPtr = charnum-1;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
162
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
163 ip += (bitCount+7)>>3;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
164 return ip-istart;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
165 }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
166
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
167
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
168 /*! HUF_readStats() :
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
169 Read compact Huffman tree, saved by HUF_writeCTable().
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
170 `huffWeight` is destination buffer.
30822
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30434
diff changeset
171 `rankStats` is assumed to be a table of at least HUF_TABLELOG_MAX U32.
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
172 @return : size read from `src` , or an error Code .
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
173 Note : Needed by HUF_readCTable() and HUF_readDTableX?() .
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
174 */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
175 size_t HUF_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats,
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
176 U32* nbSymbolsPtr, U32* tableLogPtr,
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
177 const void* src, size_t srcSize)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
178 {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
179 U32 weightTotal;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
180 const BYTE* ip = (const BYTE*) src;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
181 size_t iSize;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
182 size_t oSize;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
183
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
184 if (!srcSize) return ERROR(srcSize_wrong);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
185 iSize = ip[0];
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
186 /* memset(huffWeight, 0, hwSize); *//* is not necessary, even though some analyzer complain ... */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
187
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
188 if (iSize >= 128) { /* special header */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
189 oSize = iSize - 127;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
190 iSize = ((oSize+1)/2);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
191 if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
192 if (oSize >= hwSize) return ERROR(corruption_detected);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
193 ip += 1;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
194 { U32 n;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
195 for (n=0; n<oSize; n+=2) {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
196 huffWeight[n] = ip[n/2] >> 4;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
197 huffWeight[n+1] = ip[n/2] & 15;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
198 } } }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
199 else { /* header compressed with FSE (normal case) */
30822
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30434
diff changeset
200 FSE_DTable fseWorkspace[FSE_DTABLE_SIZE_U32(6)]; /* 6 is max possible tableLog for HUF header (maybe even 5, to be tested) */
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
201 if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
30822
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30434
diff changeset
202 oSize = FSE_decompress_wksp(huffWeight, hwSize-1, ip+1, iSize, fseWorkspace, 6); /* max (hwSize-1) values decoded, as last one is implied */
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
203 if (FSE_isError(oSize)) return oSize;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
204 }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
205
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
206 /* collect weight stats */
30822
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30434
diff changeset
207 memset(rankStats, 0, (HUF_TABLELOG_MAX + 1) * sizeof(U32));
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
208 weightTotal = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
209 { U32 n; for (n=0; n<oSize; n++) {
30822
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30434
diff changeset
210 if (huffWeight[n] >= HUF_TABLELOG_MAX) return ERROR(corruption_detected);
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
211 rankStats[huffWeight[n]]++;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
212 weightTotal += (1 << huffWeight[n]) >> 1;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
213 } }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
214 if (weightTotal == 0) return ERROR(corruption_detected);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
215
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
216 /* get last non-null symbol weight (implied, total must be 2^n) */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
217 { U32 const tableLog = BIT_highbit32(weightTotal) + 1;
30822
b54a2984cdd4 zstd: vendor python-zstandard 0.6.0
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30434
diff changeset
218 if (tableLog > HUF_TABLELOG_MAX) return ERROR(corruption_detected);
30434
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
219 *tableLogPtr = tableLog;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
220 /* determine last weight */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
221 { U32 const total = 1 << tableLog;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
222 U32 const rest = total - weightTotal;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
223 U32 const verif = 1 << BIT_highbit32(rest);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
224 U32 const lastWeight = BIT_highbit32(rest) + 1;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
225 if (verif != rest) return ERROR(corruption_detected); /* last value must be a clean power of 2 */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
226 huffWeight[oSize] = (BYTE)lastWeight;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
227 rankStats[lastWeight]++;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
228 } }
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 /* check tree construction validity */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
231 if ((rankStats[1] < 2) || (rankStats[1] & 1)) return ERROR(corruption_detected); /* by construction : at least 2 elts of rank 1, must be even */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
232
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
233 /* results */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
234 *nbSymbolsPtr = (U32)(oSize+1);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
235 return iSize+1;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
236 }