Line data Source code
1 : /*
2 : Common functions of New Generation Entropy library
3 : Copyright (C) 2016, Yann Collet.
4 :
5 : BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
6 :
7 : Redistribution and use in source and binary forms, with or without
8 : modification, are permitted provided that the following conditions are
9 : met:
10 :
11 : * Redistributions of source code must retain the above copyright
12 : notice, this list of conditions and the following disclaimer.
13 : * Redistributions in binary form must reproduce the above
14 : copyright notice, this list of conditions and the following disclaimer
15 : in the documentation and/or other materials provided with the
16 : distribution.
17 :
18 : THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 : "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 : LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 : A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22 : OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 : SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24 : LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 : DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 : THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 : (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 : OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 :
30 : You can contact the author at :
31 : - FSE+HUF source repository : https://github.com/Cyan4973/FiniteStateEntropy
32 : - Public forum : https://groups.google.com/forum/#!forum/lz4c
33 : *************************************************************************** */
34 :
35 : /* *************************************
36 : * Dependencies
37 : ***************************************/
38 : #include "mem.h"
39 : #include "error_private.h" /* ERR_*, ERROR */
40 : #define FSE_STATIC_LINKING_ONLY /* FSE_MIN_TABLELOG */
41 : #include "fse.h"
42 : #define HUF_STATIC_LINKING_ONLY /* HUF_TABLELOG_ABSOLUTEMAX */
43 : #include "huf.h"
44 :
45 :
46 : /*-****************************************
47 : * FSE Error Management
48 : ******************************************/
49 18130 : unsigned FSE_isError(size_t code) { return ERR_isError(code); }
50 :
51 0 : const char* FSE_getErrorName(size_t code) { return ERR_getErrorName(code); }
52 :
53 :
54 : /* **************************************************************
55 : * HUF Error Management
56 : ****************************************************************/
57 37706 : unsigned HUF_isError(size_t code) { return ERR_isError(code); }
58 :
59 0 : const char* HUF_getErrorName(size_t code) { return ERR_getErrorName(code); }
60 :
61 :
62 : /*-**************************************************************
63 : * FSE NCount encoding-decoding
64 : ****************************************************************/
65 113766 : static short FSE_abs(short a) { return (short)(a<0 ? -a : a); }
66 :
67 5908 : size_t FSE_readNCount (short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr,
68 : const void* headerBuffer, size_t hbSize)
69 : {
70 5908 : const BYTE* const istart = (const BYTE*) headerBuffer;
71 5908 : const BYTE* const iend = istart + hbSize;
72 5908 : const BYTE* ip = istart;
73 : int nbBits;
74 : int remaining;
75 : int threshold;
76 : U32 bitStream;
77 : int bitCount;
78 5908 : unsigned charnum = 0;
79 5908 : int previous0 = 0;
80 :
81 5908 : if (hbSize < 4) return ERROR(srcSize_wrong);
82 5908 : bitStream = MEM_readLE32(ip);
83 5908 : nbBits = (bitStream & 0xF) + FSE_MIN_TABLELOG; /* extract tableLog */
84 5908 : if (nbBits > FSE_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge);
85 5908 : bitStream >>= 4;
86 5908 : bitCount = 4;
87 5908 : *tableLogPtr = nbBits;
88 5908 : remaining = (1<<nbBits)+1;
89 5908 : threshold = 1<<nbBits;
90 5908 : nbBits++;
91 :
92 125582 : while ((remaining>1) & (charnum<=*maxSVPtr)) {
93 113766 : if (previous0) {
94 9698 : unsigned n0 = charnum;
95 19410 : while ((bitStream & 0xFFFF) == 0xFFFF) {
96 14 : n0 += 24;
97 14 : if (ip < iend-5) {
98 14 : ip += 2;
99 14 : bitStream = MEM_readLE32(ip) >> bitCount;
100 : } else {
101 0 : bitStream >>= 16;
102 0 : bitCount += 16;
103 : } }
104 20054 : while ((bitStream & 3) == 3) {
105 658 : n0 += 3;
106 658 : bitStream >>= 2;
107 658 : bitCount += 2;
108 : }
109 9698 : n0 += bitStream & 3;
110 9698 : bitCount += 2;
111 9698 : if (n0 > *maxSVPtr) return ERROR(maxSymbolValue_tooSmall);
112 9698 : while (charnum < n0) normalizedCounter[charnum++] = 0;
113 9698 : if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) {
114 9698 : ip += bitCount>>3;
115 9698 : bitCount &= 7;
116 9698 : bitStream = MEM_readLE32(ip) >> bitCount;
117 : } else {
118 0 : bitStream >>= 2;
119 : } }
120 113766 : { short const max = (short)((2*threshold-1)-remaining);
121 : short count;
122 :
123 113766 : if ((bitStream & (threshold-1)) < (U32)max) {
124 80958 : count = (short)(bitStream & (threshold-1));
125 80958 : bitCount += nbBits-1;
126 : } else {
127 32808 : count = (short)(bitStream & (2*threshold-1));
128 32808 : if (count >= threshold) count -= max;
129 32808 : bitCount += nbBits;
130 : }
131 :
132 113766 : count--; /* extra accuracy */
133 113766 : remaining -= FSE_abs(count);
134 113766 : normalizedCounter[charnum++] = count;
135 113766 : previous0 = !count;
136 270704 : while (remaining < threshold) {
137 43172 : nbBits--;
138 43172 : threshold >>= 1;
139 : }
140 :
141 113766 : if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) {
142 113766 : ip += bitCount>>3;
143 113766 : bitCount &= 7;
144 : } else {
145 0 : bitCount -= (int)(8 * (iend - 4 - ip));
146 0 : ip = iend - 4;
147 : }
148 113766 : bitStream = MEM_readLE32(ip) >> (bitCount & 31);
149 : } } /* while ((remaining>1) & (charnum<=*maxSVPtr)) */
150 5908 : if (remaining != 1) return ERROR(corruption_detected);
151 5908 : if (bitCount > 32) return ERROR(corruption_detected);
152 5908 : *maxSVPtr = charnum-1;
153 :
154 5908 : ip += (bitCount+7)>>3;
155 5908 : return ip-istart;
156 : }
157 :
158 :
159 : /*! HUF_readStats() :
160 : Read compact Huffman tree, saved by HUF_writeCTable().
161 : `huffWeight` is destination buffer.
162 : @return : size read from `src` , or an error Code .
163 : Note : Needed by HUF_readCTable() and HUF_readDTableX?() .
164 : */
165 2004 : size_t HUF_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats,
166 : U32* nbSymbolsPtr, U32* tableLogPtr,
167 : const void* src, size_t srcSize)
168 : {
169 : U32 weightTotal;
170 2004 : const BYTE* ip = (const BYTE*) src;
171 2004 : size_t iSize = ip[0];
172 : size_t oSize;
173 :
174 : /* memset(huffWeight, 0, hwSize); *//* is not necessary, even though some analyzer complain ... */
175 :
176 2004 : if (iSize >= 128) { /* special header */
177 0 : oSize = iSize - 127;
178 0 : iSize = ((oSize+1)/2);
179 0 : if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
180 0 : if (oSize >= hwSize) return ERROR(corruption_detected);
181 0 : ip += 1;
182 : { U32 n;
183 0 : for (n=0; n<oSize; n+=2) {
184 0 : huffWeight[n] = ip[n/2] >> 4;
185 0 : huffWeight[n+1] = ip[n/2] & 15;
186 : } } }
187 : else { /* header compressed with FSE (normal case) */
188 2004 : if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
189 2004 : oSize = FSE_decompress(huffWeight, hwSize-1, ip+1, iSize); /* max (hwSize-1) values decoded, as last one is implied */
190 2004 : if (FSE_isError(oSize)) return oSize;
191 : }
192 :
193 : /* collect weight stats */
194 2004 : memset(rankStats, 0, (HUF_TABLELOG_ABSOLUTEMAX + 1) * sizeof(U32));
195 2004 : weightTotal = 0;
196 508252 : { U32 n; for (n=0; n<oSize; n++) {
197 506248 : if (huffWeight[n] >= HUF_TABLELOG_ABSOLUTEMAX) return ERROR(corruption_detected);
198 506248 : rankStats[huffWeight[n]]++;
199 506248 : weightTotal += (1 << huffWeight[n]) >> 1;
200 : } }
201 :
202 : /* get last non-null symbol weight (implied, total must be 2^n) */
203 2004 : { U32 const tableLog = BIT_highbit32(weightTotal) + 1;
204 2004 : if (tableLog > HUF_TABLELOG_ABSOLUTEMAX) return ERROR(corruption_detected);
205 2004 : *tableLogPtr = tableLog;
206 : /* determine last weight */
207 2004 : { U32 const total = 1 << tableLog;
208 2004 : U32 const rest = total - weightTotal;
209 2004 : U32 const verif = 1 << BIT_highbit32(rest);
210 2004 : U32 const lastWeight = BIT_highbit32(rest) + 1;
211 2004 : if (verif != rest) return ERROR(corruption_detected); /* last value must be a clean power of 2 */
212 2004 : huffWeight[oSize] = (BYTE)lastWeight;
213 2004 : rankStats[lastWeight]++;
214 : } }
215 :
216 : /* check tree construction validity */
217 2004 : if ((rankStats[1] < 2) || (rankStats[1] & 1)) return ERROR(corruption_detected); /* by construction : at least 2 elts of rank 1, must be even */
218 :
219 : /* results */
220 2004 : *nbSymbolsPtr = (U32)(oSize+1);
221 2004 : return iSize+1;
222 : }
|
