Mercurial > public > mercurial-scm > hg

annotate contrib/python-zstandard/zstd/common/entropy_common.c @ 30434:2e484bdea8c4

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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
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
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
46 /*-****************************************
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
47 * FSE Error Management
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
48 ******************************************/
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
49 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
50
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
51 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
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 * HUF Error Management
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 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
58
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
59 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
60
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 * FSE NCount encoding-decoding
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
64 ****************************************************************/
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
65 static short FSE_abs(short a) { return (short)(a<0 ? -a : a); }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
66
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
67 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
68 const void* headerBuffer, size_t hbSize)
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
69 {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
70 const BYTE* const istart = (const BYTE*) headerBuffer;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
71 const BYTE* const iend = istart + hbSize;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
72 const BYTE* ip = istart;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
73 int nbBits;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
74 int remaining;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
75 int threshold;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
76 U32 bitStream;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
77 int bitCount;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
78 unsigned charnum = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
79 int previous0 = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
80
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
81 if (hbSize < 4) return ERROR(srcSize_wrong);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
82 bitStream = MEM_readLE32(ip);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
83 nbBits = (bitStream & 0xF) + FSE_MIN_TABLELOG; /* extract tableLog */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
84 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
85 bitStream >>= 4;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
86 bitCount = 4;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
87 *tableLogPtr = nbBits;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
88 remaining = (1<<nbBits)+1;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
89 threshold = 1<<nbBits;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
90 nbBits++;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
91
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
92 while ((remaining>1) & (charnum<=*maxSVPtr)) {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
93 if (previous0) {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
94 unsigned n0 = charnum;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
95 while ((bitStream & 0xFFFF) == 0xFFFF) {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
96 n0 += 24;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
97 if (ip < iend-5) {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
98 ip += 2;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
99 bitStream = MEM_readLE32(ip) >> bitCount;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
100 } else {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
101 bitStream >>= 16;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
102 bitCount += 16;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
103 } }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
104 while ((bitStream & 3) == 3) {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
105 n0 += 3;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
106 bitStream >>= 2;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
107 bitCount += 2;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
108 }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
109 n0 += bitStream & 3;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
110 bitCount += 2;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
111 if (n0 > *maxSVPtr) return ERROR(maxSymbolValue_tooSmall);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
112 while (charnum < n0) normalizedCounter[charnum++] = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
113 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
114 ip += bitCount>>3;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
115 bitCount &= 7;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
116 bitStream = MEM_readLE32(ip) >> bitCount;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
117 } else {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
118 bitStream >>= 2;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
119 } }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
120 { short const max = (short)((2*threshold-1)-remaining);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
121 short count;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
122
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
123 if ((bitStream & (threshold-1)) < (U32)max) {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
124 count = (short)(bitStream & (threshold-1));
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
125 bitCount += nbBits-1;
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 count = (short)(bitStream & (2*threshold-1));
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
128 if (count >= threshold) count -= max;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
129 bitCount += nbBits;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
130 }
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 count--; /* extra accuracy */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
133 remaining -= FSE_abs(count);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
134 normalizedCounter[charnum++] = count;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
135 previous0 = !count;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
136 while (remaining < threshold) {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
137 nbBits--;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
138 threshold >>= 1;
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 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
142 ip += bitCount>>3;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
143 bitCount &= 7;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
144 } else {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
145 bitCount -= (int)(8 * (iend - 4 - ip));
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
146 ip = iend - 4;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
147 }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
148 bitStream = MEM_readLE32(ip) >> (bitCount & 31);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
149 } } /* while ((remaining>1) & (charnum<=*maxSVPtr)) */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
150 if (remaining != 1) return ERROR(corruption_detected);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
151 if (bitCount > 32) return ERROR(corruption_detected);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
152 *maxSVPtr = charnum-1;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
153
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
154 ip += (bitCount+7)>>3;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
155 return ip-istart;
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
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 /*! HUF_readStats() :
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
160 Read compact Huffman tree, saved by HUF_writeCTable().
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
161 `huffWeight` is destination buffer.
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
162 @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
163 Note : Needed by HUF_readCTable() and HUF_readDTableX?() .
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
164 */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
165 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
166 U32* nbSymbolsPtr, U32* tableLogPtr,
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
167 const void* src, size_t srcSize)
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 U32 weightTotal;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
170 const BYTE* ip = (const BYTE*) src;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
171 size_t iSize;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
172 size_t oSize;
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 if (!srcSize) return ERROR(srcSize_wrong);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
175 iSize = ip[0];
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
176 /* 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
177
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
178 if (iSize >= 128) { /* special header */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
179 oSize = iSize - 127;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
180 iSize = ((oSize+1)/2);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
181 if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
182 if (oSize >= hwSize) return ERROR(corruption_detected);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
183 ip += 1;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
184 { U32 n;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
185 for (n=0; n<oSize; n+=2) {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
186 huffWeight[n] = ip[n/2] >> 4;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
187 huffWeight[n+1] = ip[n/2] & 15;
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 else { /* header compressed with FSE (normal case) */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
190 if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
191 oSize = FSE_decompress(huffWeight, hwSize-1, ip+1, iSize); /* max (hwSize-1) values decoded, as last one is implied */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
192 if (FSE_isError(oSize)) return oSize;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
193 }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
194
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
195 /* collect weight stats */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
196 memset(rankStats, 0, (HUF_TABLELOG_ABSOLUTEMAX + 1) * sizeof(U32));
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
197 weightTotal = 0;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
198 { U32 n; for (n=0; n<oSize; n++) {
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
199 if (huffWeight[n] >= HUF_TABLELOG_ABSOLUTEMAX) return ERROR(corruption_detected);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
200 rankStats[huffWeight[n]]++;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
201 weightTotal += (1 << huffWeight[n]) >> 1;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
202 } }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
203 if (weightTotal == 0) return ERROR(corruption_detected);
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 /* 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
206 { U32 const tableLog = BIT_highbit32(weightTotal) + 1;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
207 if (tableLog > HUF_TABLELOG_ABSOLUTEMAX) return ERROR(corruption_detected);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
208 *tableLogPtr = tableLog;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
209 /* determine last weight */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
210 { U32 const total = 1 << tableLog;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
211 U32 const rest = total - weightTotal;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
212 U32 const verif = 1 << BIT_highbit32(rest);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
213 U32 const lastWeight = BIT_highbit32(rest) + 1;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
214 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
215 huffWeight[oSize] = (BYTE)lastWeight;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
216 rankStats[lastWeight]++;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
217 } }
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
218
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
219 /* check tree construction validity */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
220 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
221
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
222 /* results */
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
223 *nbSymbolsPtr = (U32)(oSize+1);
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
224 return iSize+1;
2e484bdea8c4 zstd: vendor zstd 1.1.1
Gregory Szorc <gregory.szorc@gmail.com>
parents:
diff changeset
225 }