]>
Commit | Line | Data |
---|---|---|
11fdf7f2 | 1 | /* |
7c673cae FG |
2 | * Copyright (c) 2016-present, Yann Collet, Facebook, Inc. |
3 | * All rights reserved. | |
4 | * | |
11fdf7f2 TL |
5 | * This source code is licensed under both the BSD-style license (found in the |
6 | * LICENSE file in the root directory of this source tree) and the GPLv2 (found | |
7 | * in the COPYING file in the root directory of this source tree). | |
8 | * You may select, at your option, one of the above-listed licenses. | |
7c673cae FG |
9 | */ |
10 | ||
11 | ||
12 | /*- Dependencies -*/ | |
13 | #include "zstd_v06.h" | |
14 | #include <stddef.h> /* size_t, ptrdiff_t */ | |
15 | #include <string.h> /* memcpy */ | |
16 | #include <stdlib.h> /* malloc, free, qsort */ | |
17 | #include "error_private.h" | |
18 | ||
19 | ||
20 | ||
21 | /* ****************************************************************** | |
22 | mem.h | |
23 | low-level memory access routines | |
24 | Copyright (C) 2013-2015, Yann Collet. | |
25 | ||
26 | BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) | |
27 | ||
28 | Redistribution and use in source and binary forms, with or without | |
29 | modification, are permitted provided that the following conditions are | |
30 | met: | |
31 | ||
32 | * Redistributions of source code must retain the above copyright | |
33 | notice, this list of conditions and the following disclaimer. | |
34 | * Redistributions in binary form must reproduce the above | |
35 | copyright notice, this list of conditions and the following disclaimer | |
36 | in the documentation and/or other materials provided with the | |
37 | distribution. | |
38 | ||
39 | THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
40 | "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
41 | LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | |
42 | A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | |
43 | OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
44 | SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | |
45 | LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
46 | DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |
47 | THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
48 | (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
49 | OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
50 | ||
51 | You can contact the author at : | |
52 | - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy | |
53 | - Public forum : https://groups.google.com/forum/#!forum/lz4c | |
54 | ****************************************************************** */ | |
55 | #ifndef MEM_H_MODULE | |
56 | #define MEM_H_MODULE | |
57 | ||
58 | #if defined (__cplusplus) | |
59 | extern "C" { | |
60 | #endif | |
61 | ||
62 | ||
63 | /*-**************************************** | |
64 | * Compiler specifics | |
65 | ******************************************/ | |
66 | #if defined(_MSC_VER) /* Visual Studio */ | |
67 | # include <stdlib.h> /* _byteswap_ulong */ | |
68 | # include <intrin.h> /* _byteswap_* */ | |
69 | #endif | |
70 | #if defined(__GNUC__) | |
71 | # define MEM_STATIC static __attribute__((unused)) | |
72 | #elif defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) | |
73 | # define MEM_STATIC static inline | |
74 | #elif defined(_MSC_VER) | |
75 | # define MEM_STATIC static __inline | |
76 | #else | |
77 | # define MEM_STATIC static /* this version may generate warnings for unused static functions; disable the relevant warning */ | |
78 | #endif | |
79 | ||
80 | ||
81 | /*-************************************************************** | |
82 | * Basic Types | |
83 | *****************************************************************/ | |
84 | #if !defined (__VMS) && (defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) ) | |
85 | # include <stdint.h> | |
86 | typedef uint8_t BYTE; | |
87 | typedef uint16_t U16; | |
88 | typedef int16_t S16; | |
89 | typedef uint32_t U32; | |
90 | typedef int32_t S32; | |
91 | typedef uint64_t U64; | |
92 | typedef int64_t S64; | |
93 | #else | |
94 | typedef unsigned char BYTE; | |
95 | typedef unsigned short U16; | |
96 | typedef signed short S16; | |
97 | typedef unsigned int U32; | |
98 | typedef signed int S32; | |
99 | typedef unsigned long long U64; | |
100 | typedef signed long long S64; | |
101 | #endif | |
102 | ||
103 | ||
104 | /*-************************************************************** | |
105 | * Memory I/O | |
106 | *****************************************************************/ | |
107 | /* MEM_FORCE_MEMORY_ACCESS : | |
108 | * By default, access to unaligned memory is controlled by `memcpy()`, which is safe and portable. | |
109 | * Unfortunately, on some target/compiler combinations, the generated assembly is sub-optimal. | |
110 | * The below switch allow to select different access method for improved performance. | |
111 | * Method 0 (default) : use `memcpy()`. Safe and portable. | |
112 | * Method 1 : `__packed` statement. It depends on compiler extension (ie, not portable). | |
113 | * This method is safe if your compiler supports it, and *generally* as fast or faster than `memcpy`. | |
114 | * Method 2 : direct access. This method is portable but violate C standard. | |
115 | * It can generate buggy code on targets depending on alignment. | |
116 | * In some circumstances, it's the only known way to get the most performance (ie GCC + ARMv6) | |
117 | * See http://fastcompression.blogspot.fr/2015/08/accessing-unaligned-memory.html for details. | |
118 | * Prefer these methods in priority order (0 > 1 > 2) | |
119 | */ | |
120 | #ifndef MEM_FORCE_MEMORY_ACCESS /* can be defined externally, on command line for example */ | |
121 | # if defined(__GNUC__) && ( defined(__ARM_ARCH_6__) || defined(__ARM_ARCH_6J__) || defined(__ARM_ARCH_6K__) || defined(__ARM_ARCH_6Z__) || defined(__ARM_ARCH_6ZK__) || defined(__ARM_ARCH_6T2__) ) | |
122 | # define MEM_FORCE_MEMORY_ACCESS 2 | |
123 | # elif (defined(__INTEL_COMPILER) && !defined(WIN32)) || \ | |
124 | (defined(__GNUC__) && ( defined(__ARM_ARCH_7__) || defined(__ARM_ARCH_7A__) || defined(__ARM_ARCH_7R__) || defined(__ARM_ARCH_7M__) || defined(__ARM_ARCH_7S__) )) | |
125 | # define MEM_FORCE_MEMORY_ACCESS 1 | |
126 | # endif | |
127 | #endif | |
128 | ||
129 | MEM_STATIC unsigned MEM_32bits(void) { return sizeof(size_t)==4; } | |
130 | MEM_STATIC unsigned MEM_64bits(void) { return sizeof(size_t)==8; } | |
131 | ||
132 | MEM_STATIC unsigned MEM_isLittleEndian(void) | |
133 | { | |
134 | const union { U32 u; BYTE c[4]; } one = { 1 }; /* don't use static : performance detrimental */ | |
135 | return one.c[0]; | |
136 | } | |
137 | ||
138 | #if defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==2) | |
139 | ||
140 | /* violates C standard, by lying on structure alignment. | |
141 | Only use if no other choice to achieve best performance on target platform */ | |
142 | MEM_STATIC U16 MEM_read16(const void* memPtr) { return *(const U16*) memPtr; } | |
143 | MEM_STATIC U32 MEM_read32(const void* memPtr) { return *(const U32*) memPtr; } | |
144 | MEM_STATIC U64 MEM_read64(const void* memPtr) { return *(const U64*) memPtr; } | |
145 | ||
146 | MEM_STATIC void MEM_write16(void* memPtr, U16 value) { *(U16*)memPtr = value; } | |
147 | ||
148 | #elif defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==1) | |
149 | ||
150 | /* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */ | |
151 | /* currently only defined for gcc and icc */ | |
152 | typedef union { U16 u16; U32 u32; U64 u64; size_t st; } __attribute__((packed)) unalign; | |
153 | ||
154 | MEM_STATIC U16 MEM_read16(const void* ptr) { return ((const unalign*)ptr)->u16; } | |
155 | MEM_STATIC U32 MEM_read32(const void* ptr) { return ((const unalign*)ptr)->u32; } | |
156 | MEM_STATIC U64 MEM_read64(const void* ptr) { return ((const unalign*)ptr)->u64; } | |
157 | ||
158 | MEM_STATIC void MEM_write16(void* memPtr, U16 value) { ((unalign*)memPtr)->u16 = value; } | |
159 | ||
160 | #else | |
161 | ||
162 | /* default method, safe and standard. | |
163 | can sometimes prove slower */ | |
164 | ||
165 | MEM_STATIC U16 MEM_read16(const void* memPtr) | |
166 | { | |
167 | U16 val; memcpy(&val, memPtr, sizeof(val)); return val; | |
168 | } | |
169 | ||
170 | MEM_STATIC U32 MEM_read32(const void* memPtr) | |
171 | { | |
172 | U32 val; memcpy(&val, memPtr, sizeof(val)); return val; | |
173 | } | |
174 | ||
175 | MEM_STATIC U64 MEM_read64(const void* memPtr) | |
176 | { | |
177 | U64 val; memcpy(&val, memPtr, sizeof(val)); return val; | |
178 | } | |
179 | ||
180 | MEM_STATIC void MEM_write16(void* memPtr, U16 value) | |
181 | { | |
182 | memcpy(memPtr, &value, sizeof(value)); | |
183 | } | |
184 | ||
185 | ||
186 | #endif /* MEM_FORCE_MEMORY_ACCESS */ | |
187 | ||
188 | MEM_STATIC U32 MEM_swap32(U32 in) | |
189 | { | |
190 | #if defined(_MSC_VER) /* Visual Studio */ | |
191 | return _byteswap_ulong(in); | |
192 | #elif defined (__GNUC__) | |
193 | return __builtin_bswap32(in); | |
194 | #else | |
195 | return ((in << 24) & 0xff000000 ) | | |
196 | ((in << 8) & 0x00ff0000 ) | | |
197 | ((in >> 8) & 0x0000ff00 ) | | |
198 | ((in >> 24) & 0x000000ff ); | |
199 | #endif | |
200 | } | |
201 | ||
202 | MEM_STATIC U64 MEM_swap64(U64 in) | |
203 | { | |
204 | #if defined(_MSC_VER) /* Visual Studio */ | |
205 | return _byteswap_uint64(in); | |
206 | #elif defined (__GNUC__) | |
207 | return __builtin_bswap64(in); | |
208 | #else | |
209 | return ((in << 56) & 0xff00000000000000ULL) | | |
210 | ((in << 40) & 0x00ff000000000000ULL) | | |
211 | ((in << 24) & 0x0000ff0000000000ULL) | | |
212 | ((in << 8) & 0x000000ff00000000ULL) | | |
213 | ((in >> 8) & 0x00000000ff000000ULL) | | |
214 | ((in >> 24) & 0x0000000000ff0000ULL) | | |
215 | ((in >> 40) & 0x000000000000ff00ULL) | | |
216 | ((in >> 56) & 0x00000000000000ffULL); | |
217 | #endif | |
218 | } | |
219 | ||
220 | ||
221 | /*=== Little endian r/w ===*/ | |
222 | ||
223 | MEM_STATIC U16 MEM_readLE16(const void* memPtr) | |
224 | { | |
225 | if (MEM_isLittleEndian()) | |
226 | return MEM_read16(memPtr); | |
227 | else { | |
228 | const BYTE* p = (const BYTE*)memPtr; | |
229 | return (U16)(p[0] + (p[1]<<8)); | |
230 | } | |
231 | } | |
232 | ||
233 | MEM_STATIC void MEM_writeLE16(void* memPtr, U16 val) | |
234 | { | |
235 | if (MEM_isLittleEndian()) { | |
236 | MEM_write16(memPtr, val); | |
237 | } else { | |
238 | BYTE* p = (BYTE*)memPtr; | |
239 | p[0] = (BYTE)val; | |
240 | p[1] = (BYTE)(val>>8); | |
241 | } | |
242 | } | |
243 | ||
244 | MEM_STATIC U32 MEM_readLE32(const void* memPtr) | |
245 | { | |
246 | if (MEM_isLittleEndian()) | |
247 | return MEM_read32(memPtr); | |
248 | else | |
249 | return MEM_swap32(MEM_read32(memPtr)); | |
250 | } | |
251 | ||
252 | ||
253 | MEM_STATIC U64 MEM_readLE64(const void* memPtr) | |
254 | { | |
255 | if (MEM_isLittleEndian()) | |
256 | return MEM_read64(memPtr); | |
257 | else | |
258 | return MEM_swap64(MEM_read64(memPtr)); | |
259 | } | |
260 | ||
261 | ||
262 | MEM_STATIC size_t MEM_readLEST(const void* memPtr) | |
263 | { | |
264 | if (MEM_32bits()) | |
265 | return (size_t)MEM_readLE32(memPtr); | |
266 | else | |
267 | return (size_t)MEM_readLE64(memPtr); | |
268 | } | |
269 | ||
270 | ||
271 | ||
272 | #if defined (__cplusplus) | |
273 | } | |
274 | #endif | |
275 | ||
276 | #endif /* MEM_H_MODULE */ | |
277 | ||
278 | /* | |
279 | zstd - standard compression library | |
280 | Header File for static linking only | |
281 | Copyright (C) 2014-2016, Yann Collet. | |
282 | ||
283 | BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) | |
284 | ||
285 | Redistribution and use in source and binary forms, with or without | |
286 | modification, are permitted provided that the following conditions are | |
287 | met: | |
288 | * Redistributions of source code must retain the above copyright | |
289 | notice, this list of conditions and the following disclaimer. | |
290 | * Redistributions in binary form must reproduce the above | |
291 | copyright notice, this list of conditions and the following disclaimer | |
292 | in the documentation and/or other materials provided with the | |
293 | distribution. | |
294 | THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
295 | "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
296 | LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | |
297 | A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | |
298 | OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
299 | SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | |
300 | LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
301 | DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |
302 | THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
303 | (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
304 | OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
305 | ||
306 | You can contact the author at : | |
307 | - zstd homepage : http://www.zstd.net | |
308 | */ | |
309 | #ifndef ZSTDv06_STATIC_H | |
310 | #define ZSTDv06_STATIC_H | |
311 | ||
312 | /* The prototypes defined within this file are considered experimental. | |
313 | * They should not be used in the context DLL as they may change in the future. | |
314 | * Prefer static linking if you need them, to control breaking version changes issues. | |
315 | */ | |
316 | ||
317 | #if defined (__cplusplus) | |
318 | extern "C" { | |
319 | #endif | |
320 | ||
321 | ||
322 | ||
323 | /*- Advanced Decompression functions -*/ | |
324 | ||
325 | /*! ZSTDv06_decompress_usingPreparedDCtx() : | |
326 | * Same as ZSTDv06_decompress_usingDict, but using a reference context `preparedDCtx`, where dictionary has been loaded. | |
327 | * It avoids reloading the dictionary each time. | |
328 | * `preparedDCtx` must have been properly initialized using ZSTDv06_decompressBegin_usingDict(). | |
329 | * Requires 2 contexts : 1 for reference (preparedDCtx), which will not be modified, and 1 to run the decompression operation (dctx) */ | |
330 | ZSTDLIBv06_API size_t ZSTDv06_decompress_usingPreparedDCtx( | |
331 | ZSTDv06_DCtx* dctx, const ZSTDv06_DCtx* preparedDCtx, | |
332 | void* dst, size_t dstCapacity, | |
333 | const void* src, size_t srcSize); | |
334 | ||
335 | ||
336 | ||
337 | #define ZSTDv06_FRAMEHEADERSIZE_MAX 13 /* for static allocation */ | |
338 | static const size_t ZSTDv06_frameHeaderSize_min = 5; | |
339 | static const size_t ZSTDv06_frameHeaderSize_max = ZSTDv06_FRAMEHEADERSIZE_MAX; | |
340 | ||
341 | ZSTDLIBv06_API size_t ZSTDv06_decompressBegin(ZSTDv06_DCtx* dctx); | |
342 | ||
343 | /* | |
344 | Streaming decompression, direct mode (bufferless) | |
345 | ||
346 | A ZSTDv06_DCtx object is required to track streaming operations. | |
347 | Use ZSTDv06_createDCtx() / ZSTDv06_freeDCtx() to manage it. | |
348 | A ZSTDv06_DCtx object can be re-used multiple times. | |
349 | ||
350 | First optional operation is to retrieve frame parameters, using ZSTDv06_getFrameParams(), which doesn't consume the input. | |
351 | It can provide the minimum size of rolling buffer required to properly decompress data, | |
352 | and optionally the final size of uncompressed content. | |
353 | (Note : content size is an optional info that may not be present. 0 means : content size unknown) | |
354 | Frame parameters are extracted from the beginning of compressed frame. | |
355 | The amount of data to read is variable, from ZSTDv06_frameHeaderSize_min to ZSTDv06_frameHeaderSize_max (so if `srcSize` >= ZSTDv06_frameHeaderSize_max, it will always work) | |
356 | If `srcSize` is too small for operation to succeed, function will return the minimum size it requires to produce a result. | |
357 | Result : 0 when successful, it means the ZSTDv06_frameParams structure has been filled. | |
358 | >0 : means there is not enough data into `src`. Provides the expected size to successfully decode header. | |
359 | errorCode, which can be tested using ZSTDv06_isError() | |
360 | ||
361 | Start decompression, with ZSTDv06_decompressBegin() or ZSTDv06_decompressBegin_usingDict(). | |
362 | Alternatively, you can copy a prepared context, using ZSTDv06_copyDCtx(). | |
363 | ||
364 | Then use ZSTDv06_nextSrcSizeToDecompress() and ZSTDv06_decompressContinue() alternatively. | |
365 | ZSTDv06_nextSrcSizeToDecompress() tells how much bytes to provide as 'srcSize' to ZSTDv06_decompressContinue(). | |
366 | ZSTDv06_decompressContinue() requires this exact amount of bytes, or it will fail. | |
367 | ZSTDv06_decompressContinue() needs previous data blocks during decompression, up to (1 << windowlog). | |
368 | They should preferably be located contiguously, prior to current block. Alternatively, a round buffer is also possible. | |
369 | ||
370 | @result of ZSTDv06_decompressContinue() is the number of bytes regenerated within 'dst' (necessarily <= dstCapacity) | |
371 | It can be zero, which is not an error; it just means ZSTDv06_decompressContinue() has decoded some header. | |
372 | ||
373 | A frame is fully decoded when ZSTDv06_nextSrcSizeToDecompress() returns zero. | |
374 | Context can then be reset to start a new decompression. | |
375 | */ | |
376 | ||
377 | ||
378 | /* ************************************** | |
379 | * Block functions | |
380 | ****************************************/ | |
381 | /*! Block functions produce and decode raw zstd blocks, without frame metadata. | |
382 | User will have to take in charge required information to regenerate data, such as compressed and content sizes. | |
383 | ||
384 | A few rules to respect : | |
385 | - Uncompressed block size must be <= ZSTDv06_BLOCKSIZE_MAX (128 KB) | |
386 | - Compressing or decompressing requires a context structure | |
387 | + Use ZSTDv06_createCCtx() and ZSTDv06_createDCtx() | |
388 | - It is necessary to init context before starting | |
389 | + compression : ZSTDv06_compressBegin() | |
390 | + decompression : ZSTDv06_decompressBegin() | |
391 | + variants _usingDict() are also allowed | |
392 | + copyCCtx() and copyDCtx() work too | |
393 | - When a block is considered not compressible enough, ZSTDv06_compressBlock() result will be zero. | |
394 | In which case, nothing is produced into `dst`. | |
395 | + User must test for such outcome and deal directly with uncompressed data | |
396 | + ZSTDv06_decompressBlock() doesn't accept uncompressed data as input !! | |
397 | */ | |
398 | ||
399 | #define ZSTDv06_BLOCKSIZE_MAX (128 * 1024) /* define, for static allocation */ | |
400 | ZSTDLIBv06_API size_t ZSTDv06_decompressBlock(ZSTDv06_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize); | |
401 | ||
402 | ||
403 | ||
404 | #if defined (__cplusplus) | |
405 | } | |
406 | #endif | |
407 | ||
408 | #endif /* ZSTDv06_STATIC_H */ | |
409 | /* | |
410 | zstd_internal - common functions to include | |
411 | Header File for include | |
412 | Copyright (C) 2014-2016, Yann Collet. | |
413 | ||
414 | BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) | |
415 | ||
416 | Redistribution and use in source and binary forms, with or without | |
417 | modification, are permitted provided that the following conditions are | |
418 | met: | |
419 | * Redistributions of source code must retain the above copyright | |
420 | notice, this list of conditions and the following disclaimer. | |
421 | * Redistributions in binary form must reproduce the above | |
422 | copyright notice, this list of conditions and the following disclaimer | |
423 | in the documentation and/or other materials provided with the | |
424 | distribution. | |
425 | THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
426 | "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
427 | LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | |
428 | A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | |
429 | OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
430 | SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | |
431 | LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
432 | DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |
433 | THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
434 | (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
435 | OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
436 | ||
437 | You can contact the author at : | |
438 | - zstd homepage : https://www.zstd.net | |
439 | */ | |
440 | #ifndef ZSTDv06_CCOMMON_H_MODULE | |
441 | #define ZSTDv06_CCOMMON_H_MODULE | |
442 | ||
443 | ||
444 | /*-************************************* | |
445 | * Common macros | |
446 | ***************************************/ | |
447 | #define MIN(a,b) ((a)<(b) ? (a) : (b)) | |
448 | #define MAX(a,b) ((a)>(b) ? (a) : (b)) | |
449 | ||
450 | ||
451 | /*-************************************* | |
452 | * Common constants | |
453 | ***************************************/ | |
454 | #define ZSTDv06_DICT_MAGIC 0xEC30A436 | |
455 | ||
456 | #define ZSTDv06_REP_NUM 3 | |
457 | #define ZSTDv06_REP_INIT ZSTDv06_REP_NUM | |
458 | #define ZSTDv06_REP_MOVE (ZSTDv06_REP_NUM-1) | |
459 | ||
460 | #define KB *(1 <<10) | |
461 | #define MB *(1 <<20) | |
462 | #define GB *(1U<<30) | |
463 | ||
464 | #define BIT7 128 | |
465 | #define BIT6 64 | |
466 | #define BIT5 32 | |
467 | #define BIT4 16 | |
468 | #define BIT1 2 | |
469 | #define BIT0 1 | |
470 | ||
471 | #define ZSTDv06_WINDOWLOG_ABSOLUTEMIN 12 | |
472 | static const size_t ZSTDv06_fcs_fieldSize[4] = { 0, 1, 2, 8 }; | |
473 | ||
474 | #define ZSTDv06_BLOCKHEADERSIZE 3 /* because C standard does not allow a static const value to be defined using another static const value .... :( */ | |
475 | static const size_t ZSTDv06_blockHeaderSize = ZSTDv06_BLOCKHEADERSIZE; | |
476 | typedef enum { bt_compressed, bt_raw, bt_rle, bt_end } blockType_t; | |
477 | ||
478 | #define MIN_SEQUENCES_SIZE 1 /* nbSeq==0 */ | |
479 | #define MIN_CBLOCK_SIZE (1 /*litCSize*/ + 1 /* RLE or RAW */ + MIN_SEQUENCES_SIZE /* nbSeq==0 */) /* for a non-null block */ | |
480 | ||
481 | #define HufLog 12 | |
482 | ||
483 | #define IS_HUF 0 | |
484 | #define IS_PCH 1 | |
485 | #define IS_RAW 2 | |
486 | #define IS_RLE 3 | |
487 | ||
488 | #define LONGNBSEQ 0x7F00 | |
489 | ||
490 | #define MINMATCH 3 | |
491 | #define EQUAL_READ32 4 | |
492 | #define REPCODE_STARTVALUE 1 | |
493 | ||
494 | #define Litbits 8 | |
495 | #define MaxLit ((1<<Litbits) - 1) | |
496 | #define MaxML 52 | |
497 | #define MaxLL 35 | |
498 | #define MaxOff 28 | |
499 | #define MaxSeq MAX(MaxLL, MaxML) /* Assumption : MaxOff < MaxLL,MaxML */ | |
500 | #define MLFSELog 9 | |
501 | #define LLFSELog 9 | |
502 | #define OffFSELog 8 | |
503 | ||
504 | #define FSEv06_ENCODING_RAW 0 | |
505 | #define FSEv06_ENCODING_RLE 1 | |
506 | #define FSEv06_ENCODING_STATIC 2 | |
507 | #define FSEv06_ENCODING_DYNAMIC 3 | |
508 | ||
509 | static const U32 LL_bits[MaxLL+1] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, | |
510 | 1, 1, 1, 1, 2, 2, 3, 3, 4, 6, 7, 8, 9,10,11,12, | |
511 | 13,14,15,16 }; | |
512 | static const S16 LL_defaultNorm[MaxLL+1] = { 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, | |
513 | 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 1, 1, 1, 1, 1, | |
514 | -1,-1,-1,-1 }; | |
515 | static const U32 LL_defaultNormLog = 6; | |
516 | ||
517 | static const U32 ML_bits[MaxML+1] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, | |
518 | 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, | |
519 | 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 7, 8, 9,10,11, | |
520 | 12,13,14,15,16 }; | |
521 | static const S16 ML_defaultNorm[MaxML+1] = { 1, 4, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, | |
522 | 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, | |
523 | 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,-1,-1, | |
524 | -1,-1,-1,-1,-1 }; | |
525 | static const U32 ML_defaultNormLog = 6; | |
526 | ||
527 | static const S16 OF_defaultNorm[MaxOff+1] = { 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, | |
528 | 1, 1, 1, 1, 1, 1, 1, 1,-1,-1,-1,-1,-1 }; | |
529 | static const U32 OF_defaultNormLog = 5; | |
530 | ||
531 | ||
532 | /*-******************************************* | |
533 | * Shared functions to include for inlining | |
534 | *********************************************/ | |
535 | static void ZSTDv06_copy8(void* dst, const void* src) { memcpy(dst, src, 8); } | |
536 | #define COPY8(d,s) { ZSTDv06_copy8(d,s); d+=8; s+=8; } | |
537 | ||
538 | /*! ZSTDv06_wildcopy() : | |
539 | * custom version of memcpy(), can copy up to 7 bytes too many (8 bytes if length==0) */ | |
540 | #define WILDCOPY_OVERLENGTH 8 | |
541 | MEM_STATIC void ZSTDv06_wildcopy(void* dst, const void* src, ptrdiff_t length) | |
542 | { | |
543 | const BYTE* ip = (const BYTE*)src; | |
544 | BYTE* op = (BYTE*)dst; | |
545 | BYTE* const oend = op + length; | |
546 | do | |
547 | COPY8(op, ip) | |
548 | while (op < oend); | |
549 | } | |
550 | ||
551 | ||
552 | ||
553 | /*-******************************************* | |
554 | * Private interfaces | |
555 | *********************************************/ | |
556 | typedef struct { | |
557 | U32 off; | |
558 | U32 len; | |
559 | } ZSTDv06_match_t; | |
560 | ||
561 | typedef struct { | |
562 | U32 price; | |
563 | U32 off; | |
564 | U32 mlen; | |
565 | U32 litlen; | |
566 | U32 rep[ZSTDv06_REP_INIT]; | |
567 | } ZSTDv06_optimal_t; | |
568 | ||
569 | typedef struct { U32 unused; } ZSTDv06_stats_t; | |
570 | ||
571 | typedef struct { | |
572 | void* buffer; | |
573 | U32* offsetStart; | |
574 | U32* offset; | |
575 | BYTE* offCodeStart; | |
576 | BYTE* litStart; | |
577 | BYTE* lit; | |
578 | U16* litLengthStart; | |
579 | U16* litLength; | |
580 | BYTE* llCodeStart; | |
581 | U16* matchLengthStart; | |
582 | U16* matchLength; | |
583 | BYTE* mlCodeStart; | |
584 | U32 longLengthID; /* 0 == no longLength; 1 == Lit.longLength; 2 == Match.longLength; */ | |
585 | U32 longLengthPos; | |
586 | /* opt */ | |
587 | ZSTDv06_optimal_t* priceTable; | |
588 | ZSTDv06_match_t* matchTable; | |
589 | U32* matchLengthFreq; | |
590 | U32* litLengthFreq; | |
591 | U32* litFreq; | |
592 | U32* offCodeFreq; | |
593 | U32 matchLengthSum; | |
594 | U32 matchSum; | |
595 | U32 litLengthSum; | |
596 | U32 litSum; | |
597 | U32 offCodeSum; | |
598 | U32 log2matchLengthSum; | |
599 | U32 log2matchSum; | |
600 | U32 log2litLengthSum; | |
601 | U32 log2litSum; | |
602 | U32 log2offCodeSum; | |
603 | U32 factor; | |
604 | U32 cachedPrice; | |
605 | U32 cachedLitLength; | |
606 | const BYTE* cachedLiterals; | |
607 | ZSTDv06_stats_t stats; | |
608 | } seqStore_t; | |
609 | ||
610 | void ZSTDv06_seqToCodes(const seqStore_t* seqStorePtr, size_t const nbSeq); | |
611 | ||
612 | ||
613 | #endif /* ZSTDv06_CCOMMON_H_MODULE */ | |
614 | /* ****************************************************************** | |
615 | FSE : Finite State Entropy codec | |
616 | Public Prototypes declaration | |
617 | Copyright (C) 2013-2016, Yann Collet. | |
618 | ||
619 | BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) | |
620 | ||
621 | Redistribution and use in source and binary forms, with or without | |
622 | modification, are permitted provided that the following conditions are | |
623 | met: | |
624 | ||
625 | * Redistributions of source code must retain the above copyright | |
626 | notice, this list of conditions and the following disclaimer. | |
627 | * Redistributions in binary form must reproduce the above | |
628 | copyright notice, this list of conditions and the following disclaimer | |
629 | in the documentation and/or other materials provided with the | |
630 | distribution. | |
631 | ||
632 | THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
633 | "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
634 | LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | |
635 | A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | |
636 | OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
637 | SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | |
638 | LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
639 | DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |
640 | THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
641 | (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
642 | OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
643 | ||
644 | You can contact the author at : | |
645 | - Source repository : https://github.com/Cyan4973/FiniteStateEntropy | |
646 | ****************************************************************** */ | |
647 | #ifndef FSEv06_H | |
648 | #define FSEv06_H | |
649 | ||
650 | #if defined (__cplusplus) | |
651 | extern "C" { | |
652 | #endif | |
653 | ||
654 | ||
655 | ||
656 | /*-**************************************** | |
657 | * FSE simple functions | |
658 | ******************************************/ | |
659 | /*! FSEv06_decompress(): | |
660 | Decompress FSE data from buffer 'cSrc', of size 'cSrcSize', | |
661 | into already allocated destination buffer 'dst', of size 'dstCapacity'. | |
662 | @return : size of regenerated data (<= maxDstSize), | |
663 | or an error code, which can be tested using FSEv06_isError() . | |
664 | ||
665 | ** Important ** : FSEv06_decompress() does not decompress non-compressible nor RLE data !!! | |
666 | Why ? : making this distinction requires a header. | |
667 | Header management is intentionally delegated to the user layer, which can better manage special cases. | |
668 | */ | |
669 | size_t FSEv06_decompress(void* dst, size_t dstCapacity, | |
670 | const void* cSrc, size_t cSrcSize); | |
671 | ||
672 | ||
673 | /*-***************************************** | |
674 | * Tool functions | |
675 | ******************************************/ | |
676 | size_t FSEv06_compressBound(size_t size); /* maximum compressed size */ | |
677 | ||
678 | /* Error Management */ | |
679 | unsigned FSEv06_isError(size_t code); /* tells if a return value is an error code */ | |
680 | const char* FSEv06_getErrorName(size_t code); /* provides error code string (useful for debugging) */ | |
681 | ||
682 | ||
683 | ||
684 | /*-***************************************** | |
685 | * FSE detailed API | |
686 | ******************************************/ | |
687 | /*! | |
688 | ||
689 | FSEv06_decompress() does the following: | |
690 | 1. read normalized counters with readNCount() | |
691 | 2. build decoding table 'DTable' from normalized counters | |
692 | 3. decode the data stream using decoding table 'DTable' | |
693 | ||
694 | The following API allows targeting specific sub-functions for advanced tasks. | |
695 | For example, it's possible to compress several blocks using the same 'CTable', | |
696 | or to save and provide normalized distribution using external method. | |
697 | */ | |
698 | ||
699 | ||
700 | /* *** DECOMPRESSION *** */ | |
701 | ||
702 | /*! FSEv06_readNCount(): | |
703 | Read compactly saved 'normalizedCounter' from 'rBuffer'. | |
704 | @return : size read from 'rBuffer', | |
705 | or an errorCode, which can be tested using FSEv06_isError(). | |
706 | maxSymbolValuePtr[0] and tableLogPtr[0] will also be updated with their respective values */ | |
707 | size_t FSEv06_readNCount (short* normalizedCounter, unsigned* maxSymbolValuePtr, unsigned* tableLogPtr, const void* rBuffer, size_t rBuffSize); | |
708 | ||
709 | /*! Constructor and Destructor of FSEv06_DTable. | |
710 | Note that its size depends on 'tableLog' */ | |
711 | typedef unsigned FSEv06_DTable; /* don't allocate that. It's just a way to be more restrictive than void* */ | |
712 | FSEv06_DTable* FSEv06_createDTable(unsigned tableLog); | |
713 | void FSEv06_freeDTable(FSEv06_DTable* dt); | |
714 | ||
715 | /*! FSEv06_buildDTable(): | |
716 | Builds 'dt', which must be already allocated, using FSEv06_createDTable(). | |
717 | return : 0, or an errorCode, which can be tested using FSEv06_isError() */ | |
718 | size_t FSEv06_buildDTable (FSEv06_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog); | |
719 | ||
720 | /*! FSEv06_decompress_usingDTable(): | |
721 | Decompress compressed source `cSrc` of size `cSrcSize` using `dt` | |
722 | into `dst` which must be already allocated. | |
723 | @return : size of regenerated data (necessarily <= `dstCapacity`), | |
724 | or an errorCode, which can be tested using FSEv06_isError() */ | |
725 | size_t FSEv06_decompress_usingDTable(void* dst, size_t dstCapacity, const void* cSrc, size_t cSrcSize, const FSEv06_DTable* dt); | |
726 | ||
727 | /*! | |
728 | Tutorial : | |
729 | ---------- | |
730 | (Note : these functions only decompress FSE-compressed blocks. | |
731 | If block is uncompressed, use memcpy() instead | |
732 | If block is a single repeated byte, use memset() instead ) | |
733 | ||
734 | The first step is to obtain the normalized frequencies of symbols. | |
735 | This can be performed by FSEv06_readNCount() if it was saved using FSEv06_writeNCount(). | |
736 | 'normalizedCounter' must be already allocated, and have at least 'maxSymbolValuePtr[0]+1' cells of signed short. | |
737 | In practice, that means it's necessary to know 'maxSymbolValue' beforehand, | |
738 | or size the table to handle worst case situations (typically 256). | |
739 | FSEv06_readNCount() will provide 'tableLog' and 'maxSymbolValue'. | |
740 | The result of FSEv06_readNCount() is the number of bytes read from 'rBuffer'. | |
741 | Note that 'rBufferSize' must be at least 4 bytes, even if useful information is less than that. | |
742 | If there is an error, the function will return an error code, which can be tested using FSEv06_isError(). | |
743 | ||
744 | The next step is to build the decompression tables 'FSEv06_DTable' from 'normalizedCounter'. | |
745 | This is performed by the function FSEv06_buildDTable(). | |
746 | The space required by 'FSEv06_DTable' must be already allocated using FSEv06_createDTable(). | |
747 | If there is an error, the function will return an error code, which can be tested using FSEv06_isError(). | |
748 | ||
749 | `FSEv06_DTable` can then be used to decompress `cSrc`, with FSEv06_decompress_usingDTable(). | |
750 | `cSrcSize` must be strictly correct, otherwise decompression will fail. | |
751 | FSEv06_decompress_usingDTable() result will tell how many bytes were regenerated (<=`dstCapacity`). | |
752 | If there is an error, the function will return an error code, which can be tested using FSEv06_isError(). (ex: dst buffer too small) | |
753 | */ | |
754 | ||
755 | ||
756 | #if defined (__cplusplus) | |
757 | } | |
758 | #endif | |
759 | ||
760 | #endif /* FSEv06_H */ | |
761 | /* ****************************************************************** | |
762 | bitstream | |
763 | Part of FSE library | |
764 | header file (to include) | |
765 | Copyright (C) 2013-2016, Yann Collet. | |
766 | ||
767 | BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) | |
768 | ||
769 | Redistribution and use in source and binary forms, with or without | |
770 | modification, are permitted provided that the following conditions are | |
771 | met: | |
772 | ||
773 | * Redistributions of source code must retain the above copyright | |
774 | notice, this list of conditions and the following disclaimer. | |
775 | * Redistributions in binary form must reproduce the above | |
776 | copyright notice, this list of conditions and the following disclaimer | |
777 | in the documentation and/or other materials provided with the | |
778 | distribution. | |
779 | ||
780 | THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
781 | "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
782 | LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | |
783 | A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | |
784 | OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
785 | SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | |
786 | LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
787 | DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |
788 | THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
789 | (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
790 | OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
791 | ||
792 | You can contact the author at : | |
793 | - Source repository : https://github.com/Cyan4973/FiniteStateEntropy | |
794 | ****************************************************************** */ | |
795 | #ifndef BITSTREAM_H_MODULE | |
796 | #define BITSTREAM_H_MODULE | |
797 | ||
798 | #if defined (__cplusplus) | |
799 | extern "C" { | |
800 | #endif | |
801 | ||
802 | ||
803 | /* | |
804 | * This API consists of small unitary functions, which must be inlined for best performance. | |
805 | * Since link-time-optimization is not available for all compilers, | |
806 | * these functions are defined into a .h to be included. | |
807 | */ | |
808 | ||
809 | ||
810 | /*========================================= | |
811 | * Target specific | |
812 | =========================================*/ | |
813 | #if defined(__BMI__) && defined(__GNUC__) | |
814 | # include <immintrin.h> /* support for bextr (experimental) */ | |
815 | #endif | |
816 | ||
817 | ||
818 | ||
819 | /*-******************************************** | |
820 | * bitStream decoding API (read backward) | |
821 | **********************************************/ | |
822 | typedef struct | |
823 | { | |
824 | size_t bitContainer; | |
825 | unsigned bitsConsumed; | |
826 | const char* ptr; | |
827 | const char* start; | |
828 | } BITv06_DStream_t; | |
829 | ||
830 | typedef enum { BITv06_DStream_unfinished = 0, | |
831 | BITv06_DStream_endOfBuffer = 1, | |
832 | BITv06_DStream_completed = 2, | |
833 | BITv06_DStream_overflow = 3 } BITv06_DStream_status; /* result of BITv06_reloadDStream() */ | |
834 | /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */ | |
835 | ||
836 | MEM_STATIC size_t BITv06_initDStream(BITv06_DStream_t* bitD, const void* srcBuffer, size_t srcSize); | |
837 | MEM_STATIC size_t BITv06_readBits(BITv06_DStream_t* bitD, unsigned nbBits); | |
838 | MEM_STATIC BITv06_DStream_status BITv06_reloadDStream(BITv06_DStream_t* bitD); | |
839 | MEM_STATIC unsigned BITv06_endOfDStream(const BITv06_DStream_t* bitD); | |
840 | ||
841 | ||
842 | /* Start by invoking BITv06_initDStream(). | |
843 | * A chunk of the bitStream is then stored into a local register. | |
844 | * Local register size is 64-bits on 64-bits systems, 32-bits on 32-bits systems (size_t). | |
845 | * You can then retrieve bitFields stored into the local register, **in reverse order**. | |
846 | * Local register is explicitly reloaded from memory by the BITv06_reloadDStream() method. | |
847 | * A reload guarantee a minimum of ((8*sizeof(bitD->bitContainer))-7) bits when its result is BITv06_DStream_unfinished. | |
848 | * Otherwise, it can be less than that, so proceed accordingly. | |
849 | * Checking if DStream has reached its end can be performed with BITv06_endOfDStream(). | |
850 | */ | |
851 | ||
852 | ||
853 | /*-**************************************** | |
854 | * unsafe API | |
855 | ******************************************/ | |
856 | MEM_STATIC size_t BITv06_readBitsFast(BITv06_DStream_t* bitD, unsigned nbBits); | |
857 | /* faster, but works only if nbBits >= 1 */ | |
858 | ||
859 | ||
860 | ||
861 | /*-************************************************************** | |
862 | * Internal functions | |
863 | ****************************************************************/ | |
864 | MEM_STATIC unsigned BITv06_highbit32 (register U32 val) | |
865 | { | |
866 | # if defined(_MSC_VER) /* Visual */ | |
867 | unsigned long r=0; | |
868 | _BitScanReverse ( &r, val ); | |
869 | return (unsigned) r; | |
870 | # elif defined(__GNUC__) && (__GNUC__ >= 3) /* Use GCC Intrinsic */ | |
871 | return 31 - __builtin_clz (val); | |
872 | # else /* Software version */ | |
873 | static const unsigned 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 }; | |
874 | U32 v = val; | |
875 | unsigned r; | |
876 | v |= v >> 1; | |
877 | v |= v >> 2; | |
878 | v |= v >> 4; | |
879 | v |= v >> 8; | |
880 | v |= v >> 16; | |
881 | r = DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27]; | |
882 | return r; | |
883 | # endif | |
884 | } | |
885 | ||
886 | ||
887 | ||
888 | /*-******************************************************** | |
889 | * bitStream decoding | |
890 | **********************************************************/ | |
891 | /*! BITv06_initDStream() : | |
892 | * Initialize a BITv06_DStream_t. | |
893 | * `bitD` : a pointer to an already allocated BITv06_DStream_t structure. | |
894 | * `srcSize` must be the *exact* size of the bitStream, in bytes. | |
895 | * @return : size of stream (== srcSize) or an errorCode if a problem is detected | |
896 | */ | |
897 | MEM_STATIC size_t BITv06_initDStream(BITv06_DStream_t* bitD, const void* srcBuffer, size_t srcSize) | |
898 | { | |
899 | if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); } | |
900 | ||
901 | if (srcSize >= sizeof(bitD->bitContainer)) { /* normal case */ | |
902 | bitD->start = (const char*)srcBuffer; | |
903 | bitD->ptr = (const char*)srcBuffer + srcSize - sizeof(bitD->bitContainer); | |
904 | bitD->bitContainer = MEM_readLEST(bitD->ptr); | |
905 | { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1]; | |
906 | if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */ | |
907 | bitD->bitsConsumed = 8 - BITv06_highbit32(lastByte); } | |
908 | } else { | |
909 | bitD->start = (const char*)srcBuffer; | |
910 | bitD->ptr = bitD->start; | |
911 | bitD->bitContainer = *(const BYTE*)(bitD->start); | |
912 | switch(srcSize) | |
913 | { | |
11fdf7f2 TL |
914 | case 7: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[6]) << (sizeof(bitD->bitContainer)*8 - 16);/* fall-through */ |
915 | case 6: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[5]) << (sizeof(bitD->bitContainer)*8 - 24);/* fall-through */ | |
916 | case 5: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[4]) << (sizeof(bitD->bitContainer)*8 - 32);/* fall-through */ | |
917 | case 4: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[3]) << 24; /* fall-through */ | |
918 | case 3: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[2]) << 16; /* fall-through */ | |
919 | case 2: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[1]) << 8; /* fall-through */ | |
920 | default: break; | |
7c673cae FG |
921 | } |
922 | { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1]; | |
923 | if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */ | |
924 | bitD->bitsConsumed = 8 - BITv06_highbit32(lastByte); } | |
925 | bitD->bitsConsumed += (U32)(sizeof(bitD->bitContainer) - srcSize)*8; | |
926 | } | |
927 | ||
928 | return srcSize; | |
929 | } | |
930 | ||
931 | ||
932 | /*! BITv06_lookBits() : | |
933 | * Provides next n bits from local register. | |
934 | * local register is not modified. | |
935 | * On 32-bits, maxNbBits==24. | |
936 | * On 64-bits, maxNbBits==56. | |
937 | * @return : value extracted | |
938 | */ | |
939 | MEM_STATIC size_t BITv06_lookBits(const BITv06_DStream_t* bitD, U32 nbBits) | |
940 | { | |
941 | U32 const bitMask = sizeof(bitD->bitContainer)*8 - 1; | |
942 | return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask-nbBits) & bitMask); | |
943 | } | |
944 | ||
945 | /*! BITv06_lookBitsFast() : | |
946 | * unsafe version; only works only if nbBits >= 1 */ | |
947 | MEM_STATIC size_t BITv06_lookBitsFast(const BITv06_DStream_t* bitD, U32 nbBits) | |
948 | { | |
949 | U32 const bitMask = sizeof(bitD->bitContainer)*8 - 1; | |
950 | return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask+1)-nbBits) & bitMask); | |
951 | } | |
952 | ||
953 | MEM_STATIC void BITv06_skipBits(BITv06_DStream_t* bitD, U32 nbBits) | |
954 | { | |
955 | bitD->bitsConsumed += nbBits; | |
956 | } | |
957 | ||
958 | /*! BITv06_readBits() : | |
959 | * Read (consume) next n bits from local register and update. | |
960 | * Pay attention to not read more than nbBits contained into local register. | |
961 | * @return : extracted value. | |
962 | */ | |
963 | MEM_STATIC size_t BITv06_readBits(BITv06_DStream_t* bitD, U32 nbBits) | |
964 | { | |
965 | size_t const value = BITv06_lookBits(bitD, nbBits); | |
966 | BITv06_skipBits(bitD, nbBits); | |
967 | return value; | |
968 | } | |
969 | ||
970 | /*! BITv06_readBitsFast() : | |
971 | * unsafe version; only works only if nbBits >= 1 */ | |
972 | MEM_STATIC size_t BITv06_readBitsFast(BITv06_DStream_t* bitD, U32 nbBits) | |
973 | { | |
974 | size_t const value = BITv06_lookBitsFast(bitD, nbBits); | |
975 | BITv06_skipBits(bitD, nbBits); | |
976 | return value; | |
977 | } | |
978 | ||
979 | /*! BITv06_reloadDStream() : | |
980 | * Refill `BITv06_DStream_t` from src buffer previously defined (see BITv06_initDStream() ). | |
981 | * This function is safe, it guarantees it will not read beyond src buffer. | |
982 | * @return : status of `BITv06_DStream_t` internal register. | |
983 | if status == unfinished, internal register is filled with >= (sizeof(bitD->bitContainer)*8 - 7) bits */ | |
984 | MEM_STATIC BITv06_DStream_status BITv06_reloadDStream(BITv06_DStream_t* bitD) | |
985 | { | |
11fdf7f2 TL |
986 | if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8)) /* should never happen */ |
987 | return BITv06_DStream_overflow; | |
7c673cae FG |
988 | |
989 | if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer)) { | |
990 | bitD->ptr -= bitD->bitsConsumed >> 3; | |
991 | bitD->bitsConsumed &= 7; | |
992 | bitD->bitContainer = MEM_readLEST(bitD->ptr); | |
993 | return BITv06_DStream_unfinished; | |
994 | } | |
995 | if (bitD->ptr == bitD->start) { | |
996 | if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BITv06_DStream_endOfBuffer; | |
997 | return BITv06_DStream_completed; | |
998 | } | |
999 | { U32 nbBytes = bitD->bitsConsumed >> 3; | |
1000 | BITv06_DStream_status result = BITv06_DStream_unfinished; | |
1001 | if (bitD->ptr - nbBytes < bitD->start) { | |
1002 | nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */ | |
1003 | result = BITv06_DStream_endOfBuffer; | |
1004 | } | |
1005 | bitD->ptr -= nbBytes; | |
1006 | bitD->bitsConsumed -= nbBytes*8; | |
1007 | bitD->bitContainer = MEM_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD) */ | |
1008 | return result; | |
1009 | } | |
1010 | } | |
1011 | ||
1012 | /*! BITv06_endOfDStream() : | |
1013 | * @return Tells if DStream has exactly reached its end (all bits consumed). | |
1014 | */ | |
1015 | MEM_STATIC unsigned BITv06_endOfDStream(const BITv06_DStream_t* DStream) | |
1016 | { | |
1017 | return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8)); | |
1018 | } | |
1019 | ||
1020 | #if defined (__cplusplus) | |
1021 | } | |
1022 | #endif | |
1023 | ||
1024 | #endif /* BITSTREAM_H_MODULE */ | |
1025 | /* ****************************************************************** | |
1026 | FSE : Finite State Entropy coder | |
1027 | header file for static linking (only) | |
1028 | Copyright (C) 2013-2015, Yann Collet | |
1029 | ||
1030 | BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) | |
1031 | ||
1032 | Redistribution and use in source and binary forms, with or without | |
1033 | modification, are permitted provided that the following conditions are | |
1034 | met: | |
1035 | ||
1036 | * Redistributions of source code must retain the above copyright | |
1037 | notice, this list of conditions and the following disclaimer. | |
1038 | * Redistributions in binary form must reproduce the above | |
1039 | copyright notice, this list of conditions and the following disclaimer | |
1040 | in the documentation and/or other materials provided with the | |
1041 | distribution. | |
1042 | ||
1043 | THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
1044 | "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
1045 | LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | |
1046 | A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | |
1047 | OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
1048 | SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | |
1049 | LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
1050 | DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |
1051 | THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
1052 | (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
1053 | OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
1054 | ||
1055 | You can contact the author at : | |
1056 | - Source repository : https://github.com/Cyan4973/FiniteStateEntropy | |
1057 | - Public forum : https://groups.google.com/forum/#!forum/lz4c | |
1058 | ****************************************************************** */ | |
1059 | #ifndef FSEv06_STATIC_H | |
1060 | #define FSEv06_STATIC_H | |
1061 | ||
1062 | #if defined (__cplusplus) | |
1063 | extern "C" { | |
1064 | #endif | |
1065 | ||
1066 | ||
1067 | /* ***************************************** | |
1068 | * Static allocation | |
1069 | *******************************************/ | |
1070 | /* FSE buffer bounds */ | |
1071 | #define FSEv06_NCOUNTBOUND 512 | |
1072 | #define FSEv06_BLOCKBOUND(size) (size + (size>>7)) | |
1073 | #define FSEv06_COMPRESSBOUND(size) (FSEv06_NCOUNTBOUND + FSEv06_BLOCKBOUND(size)) /* Macro version, useful for static allocation */ | |
1074 | ||
1075 | /* It is possible to statically allocate FSE CTable/DTable as a table of unsigned using below macros */ | |
1076 | #define FSEv06_DTABLE_SIZE_U32(maxTableLog) (1 + (1<<maxTableLog)) | |
1077 | ||
1078 | ||
1079 | /* ***************************************** | |
1080 | * FSE advanced API | |
1081 | *******************************************/ | |
1082 | size_t FSEv06_countFast(unsigned* count, unsigned* maxSymbolValuePtr, const void* src, size_t srcSize); | |
1083 | /* same as FSEv06_count(), but blindly trusts that all byte values within src are <= *maxSymbolValuePtr */ | |
1084 | ||
1085 | size_t FSEv06_buildDTable_raw (FSEv06_DTable* dt, unsigned nbBits); | |
1086 | /* build a fake FSEv06_DTable, designed to read an uncompressed bitstream where each symbol uses nbBits */ | |
1087 | ||
1088 | size_t FSEv06_buildDTable_rle (FSEv06_DTable* dt, unsigned char symbolValue); | |
1089 | /* build a fake FSEv06_DTable, designed to always generate the same symbolValue */ | |
1090 | ||
1091 | ||
1092 | /* ***************************************** | |
1093 | * FSE symbol decompression API | |
1094 | *******************************************/ | |
1095 | typedef struct | |
1096 | { | |
1097 | size_t state; | |
1098 | const void* table; /* precise table may vary, depending on U16 */ | |
1099 | } FSEv06_DState_t; | |
1100 | ||
1101 | ||
1102 | static void FSEv06_initDState(FSEv06_DState_t* DStatePtr, BITv06_DStream_t* bitD, const FSEv06_DTable* dt); | |
1103 | ||
1104 | static unsigned char FSEv06_decodeSymbol(FSEv06_DState_t* DStatePtr, BITv06_DStream_t* bitD); | |
1105 | ||
1106 | /*! | |
1107 | Let's now decompose FSEv06_decompress_usingDTable() into its unitary components. | |
1108 | You will decode FSE-encoded symbols from the bitStream, | |
1109 | and also any other bitFields you put in, **in reverse order**. | |
1110 | ||
1111 | You will need a few variables to track your bitStream. They are : | |
1112 | ||
1113 | BITv06_DStream_t DStream; // Stream context | |
1114 | FSEv06_DState_t DState; // State context. Multiple ones are possible | |
1115 | FSEv06_DTable* DTablePtr; // Decoding table, provided by FSEv06_buildDTable() | |
1116 | ||
1117 | The first thing to do is to init the bitStream. | |
1118 | errorCode = BITv06_initDStream(&DStream, srcBuffer, srcSize); | |
1119 | ||
1120 | You should then retrieve your initial state(s) | |
1121 | (in reverse flushing order if you have several ones) : | |
1122 | errorCode = FSEv06_initDState(&DState, &DStream, DTablePtr); | |
1123 | ||
1124 | You can then decode your data, symbol after symbol. | |
1125 | For information the maximum number of bits read by FSEv06_decodeSymbol() is 'tableLog'. | |
1126 | Keep in mind that symbols are decoded in reverse order, like a LIFO stack (last in, first out). | |
1127 | unsigned char symbol = FSEv06_decodeSymbol(&DState, &DStream); | |
1128 | ||
1129 | You can retrieve any bitfield you eventually stored into the bitStream (in reverse order) | |
1130 | Note : maximum allowed nbBits is 25, for 32-bits compatibility | |
1131 | size_t bitField = BITv06_readBits(&DStream, nbBits); | |
1132 | ||
1133 | All above operations only read from local register (which size depends on size_t). | |
1134 | Refueling the register from memory is manually performed by the reload method. | |
1135 | endSignal = FSEv06_reloadDStream(&DStream); | |
1136 | ||
1137 | BITv06_reloadDStream() result tells if there is still some more data to read from DStream. | |
1138 | BITv06_DStream_unfinished : there is still some data left into the DStream. | |
1139 | BITv06_DStream_endOfBuffer : Dstream reached end of buffer. Its container may no longer be completely filled. | |
1140 | BITv06_DStream_completed : Dstream reached its exact end, corresponding in general to decompression completed. | |
1141 | BITv06_DStream_tooFar : Dstream went too far. Decompression result is corrupted. | |
1142 | ||
1143 | When reaching end of buffer (BITv06_DStream_endOfBuffer), progress slowly, notably if you decode multiple symbols per loop, | |
1144 | to properly detect the exact end of stream. | |
1145 | After each decoded symbol, check if DStream is fully consumed using this simple test : | |
1146 | BITv06_reloadDStream(&DStream) >= BITv06_DStream_completed | |
1147 | ||
1148 | When it's done, verify decompression is fully completed, by checking both DStream and the relevant states. | |
1149 | Checking if DStream has reached its end is performed by : | |
1150 | BITv06_endOfDStream(&DStream); | |
1151 | Check also the states. There might be some symbols left there, if some high probability ones (>50%) are possible. | |
1152 | FSEv06_endOfDState(&DState); | |
1153 | */ | |
1154 | ||
1155 | ||
1156 | /* ***************************************** | |
1157 | * FSE unsafe API | |
1158 | *******************************************/ | |
1159 | static unsigned char FSEv06_decodeSymbolFast(FSEv06_DState_t* DStatePtr, BITv06_DStream_t* bitD); | |
1160 | /* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */ | |
1161 | ||
1162 | ||
1163 | /* ***************************************** | |
1164 | * Implementation of inlined functions | |
1165 | *******************************************/ | |
1166 | ||
1167 | ||
1168 | /* ====== Decompression ====== */ | |
1169 | ||
1170 | typedef struct { | |
1171 | U16 tableLog; | |
1172 | U16 fastMode; | |
1173 | } FSEv06_DTableHeader; /* sizeof U32 */ | |
1174 | ||
1175 | typedef struct | |
1176 | { | |
1177 | unsigned short newState; | |
1178 | unsigned char symbol; | |
1179 | unsigned char nbBits; | |
1180 | } FSEv06_decode_t; /* size == U32 */ | |
1181 | ||
1182 | MEM_STATIC void FSEv06_initDState(FSEv06_DState_t* DStatePtr, BITv06_DStream_t* bitD, const FSEv06_DTable* dt) | |
1183 | { | |
1184 | const void* ptr = dt; | |
1185 | const FSEv06_DTableHeader* const DTableH = (const FSEv06_DTableHeader*)ptr; | |
1186 | DStatePtr->state = BITv06_readBits(bitD, DTableH->tableLog); | |
1187 | BITv06_reloadDStream(bitD); | |
1188 | DStatePtr->table = dt + 1; | |
1189 | } | |
1190 | ||
1191 | MEM_STATIC BYTE FSEv06_peekSymbol(const FSEv06_DState_t* DStatePtr) | |
1192 | { | |
1193 | FSEv06_decode_t const DInfo = ((const FSEv06_decode_t*)(DStatePtr->table))[DStatePtr->state]; | |
1194 | return DInfo.symbol; | |
1195 | } | |
1196 | ||
1197 | MEM_STATIC void FSEv06_updateState(FSEv06_DState_t* DStatePtr, BITv06_DStream_t* bitD) | |
1198 | { | |
1199 | FSEv06_decode_t const DInfo = ((const FSEv06_decode_t*)(DStatePtr->table))[DStatePtr->state]; | |
1200 | U32 const nbBits = DInfo.nbBits; | |
1201 | size_t const lowBits = BITv06_readBits(bitD, nbBits); | |
1202 | DStatePtr->state = DInfo.newState + lowBits; | |
1203 | } | |
1204 | ||
1205 | MEM_STATIC BYTE FSEv06_decodeSymbol(FSEv06_DState_t* DStatePtr, BITv06_DStream_t* bitD) | |
1206 | { | |
1207 | FSEv06_decode_t const DInfo = ((const FSEv06_decode_t*)(DStatePtr->table))[DStatePtr->state]; | |
1208 | U32 const nbBits = DInfo.nbBits; | |
1209 | BYTE const symbol = DInfo.symbol; | |
1210 | size_t const lowBits = BITv06_readBits(bitD, nbBits); | |
1211 | ||
1212 | DStatePtr->state = DInfo.newState + lowBits; | |
1213 | return symbol; | |
1214 | } | |
1215 | ||
1216 | /*! FSEv06_decodeSymbolFast() : | |
1217 | unsafe, only works if no symbol has a probability > 50% */ | |
1218 | MEM_STATIC BYTE FSEv06_decodeSymbolFast(FSEv06_DState_t* DStatePtr, BITv06_DStream_t* bitD) | |
1219 | { | |
1220 | FSEv06_decode_t const DInfo = ((const FSEv06_decode_t*)(DStatePtr->table))[DStatePtr->state]; | |
1221 | U32 const nbBits = DInfo.nbBits; | |
1222 | BYTE const symbol = DInfo.symbol; | |
1223 | size_t const lowBits = BITv06_readBitsFast(bitD, nbBits); | |
1224 | ||
1225 | DStatePtr->state = DInfo.newState + lowBits; | |
1226 | return symbol; | |
1227 | } | |
1228 | ||
1229 | ||
1230 | ||
1231 | #ifndef FSEv06_COMMONDEFS_ONLY | |
1232 | ||
1233 | /* ************************************************************** | |
1234 | * Tuning parameters | |
1235 | ****************************************************************/ | |
1236 | /*!MEMORY_USAGE : | |
1237 | * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.) | |
1238 | * Increasing memory usage improves compression ratio | |
1239 | * Reduced memory usage can improve speed, due to cache effect | |
1240 | * Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */ | |
1241 | #define FSEv06_MAX_MEMORY_USAGE 14 | |
1242 | #define FSEv06_DEFAULT_MEMORY_USAGE 13 | |
1243 | ||
1244 | /*!FSEv06_MAX_SYMBOL_VALUE : | |
1245 | * Maximum symbol value authorized. | |
1246 | * Required for proper stack allocation */ | |
1247 | #define FSEv06_MAX_SYMBOL_VALUE 255 | |
1248 | ||
1249 | ||
1250 | /* ************************************************************** | |
1251 | * template functions type & suffix | |
1252 | ****************************************************************/ | |
1253 | #define FSEv06_FUNCTION_TYPE BYTE | |
1254 | #define FSEv06_FUNCTION_EXTENSION | |
1255 | #define FSEv06_DECODE_TYPE FSEv06_decode_t | |
1256 | ||
1257 | ||
1258 | #endif /* !FSEv06_COMMONDEFS_ONLY */ | |
1259 | ||
1260 | ||
1261 | /* *************************************************************** | |
1262 | * Constants | |
1263 | *****************************************************************/ | |
1264 | #define FSEv06_MAX_TABLELOG (FSEv06_MAX_MEMORY_USAGE-2) | |
1265 | #define FSEv06_MAX_TABLESIZE (1U<<FSEv06_MAX_TABLELOG) | |
1266 | #define FSEv06_MAXTABLESIZE_MASK (FSEv06_MAX_TABLESIZE-1) | |
1267 | #define FSEv06_DEFAULT_TABLELOG (FSEv06_DEFAULT_MEMORY_USAGE-2) | |
1268 | #define FSEv06_MIN_TABLELOG 5 | |
1269 | ||
1270 | #define FSEv06_TABLELOG_ABSOLUTE_MAX 15 | |
1271 | #if FSEv06_MAX_TABLELOG > FSEv06_TABLELOG_ABSOLUTE_MAX | |
1272 | #error "FSEv06_MAX_TABLELOG > FSEv06_TABLELOG_ABSOLUTE_MAX is not supported" | |
1273 | #endif | |
1274 | ||
1275 | #define FSEv06_TABLESTEP(tableSize) ((tableSize>>1) + (tableSize>>3) + 3) | |
1276 | ||
1277 | ||
1278 | #if defined (__cplusplus) | |
1279 | } | |
1280 | #endif | |
1281 | ||
1282 | #endif /* FSEv06_STATIC_H */ | |
1283 | /* | |
1284 | Common functions of New Generation Entropy library | |
1285 | Copyright (C) 2016, Yann Collet. | |
1286 | ||
1287 | BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) | |
1288 | ||
1289 | Redistribution and use in source and binary forms, with or without | |
1290 | modification, are permitted provided that the following conditions are | |
1291 | met: | |
1292 | ||
1293 | * Redistributions of source code must retain the above copyright | |
1294 | notice, this list of conditions and the following disclaimer. | |
1295 | * Redistributions in binary form must reproduce the above | |
1296 | copyright notice, this list of conditions and the following disclaimer | |
1297 | in the documentation and/or other materials provided with the | |
1298 | distribution. | |
1299 | ||
1300 | THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
1301 | "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
1302 | LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | |
1303 | A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | |
1304 | OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
1305 | SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | |
1306 | LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
1307 | DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |
1308 | THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
1309 | (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
1310 | OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
1311 | ||
1312 | You can contact the author at : | |
1313 | - FSE+HUF source repository : https://github.com/Cyan4973/FiniteStateEntropy | |
1314 | - Public forum : https://groups.google.com/forum/#!forum/lz4c | |
1315 | *************************************************************************** */ | |
1316 | ||
1317 | ||
1318 | /*-**************************************** | |
1319 | * FSE Error Management | |
1320 | ******************************************/ | |
1321 | unsigned FSEv06_isError(size_t code) { return ERR_isError(code); } | |
1322 | ||
1323 | const char* FSEv06_getErrorName(size_t code) { return ERR_getErrorName(code); } | |
1324 | ||
1325 | ||
1326 | /* ************************************************************** | |
1327 | * HUF Error Management | |
1328 | ****************************************************************/ | |
1329 | unsigned HUFv06_isError(size_t code) { return ERR_isError(code); } | |
1330 | ||
1331 | const char* HUFv06_getErrorName(size_t code) { return ERR_getErrorName(code); } | |
1332 | ||
1333 | ||
1334 | /*-************************************************************** | |
1335 | * FSE NCount encoding-decoding | |
1336 | ****************************************************************/ | |
1337 | static short FSEv06_abs(short a) { return a<0 ? -a : a; } | |
1338 | ||
1339 | size_t FSEv06_readNCount (short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr, | |
1340 | const void* headerBuffer, size_t hbSize) | |
1341 | { | |
1342 | const BYTE* const istart = (const BYTE*) headerBuffer; | |
1343 | const BYTE* const iend = istart + hbSize; | |
1344 | const BYTE* ip = istart; | |
1345 | int nbBits; | |
1346 | int remaining; | |
1347 | int threshold; | |
1348 | U32 bitStream; | |
1349 | int bitCount; | |
1350 | unsigned charnum = 0; | |
1351 | int previous0 = 0; | |
1352 | ||
1353 | if (hbSize < 4) return ERROR(srcSize_wrong); | |
1354 | bitStream = MEM_readLE32(ip); | |
1355 | nbBits = (bitStream & 0xF) + FSEv06_MIN_TABLELOG; /* extract tableLog */ | |
1356 | if (nbBits > FSEv06_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge); | |
1357 | bitStream >>= 4; | |
1358 | bitCount = 4; | |
1359 | *tableLogPtr = nbBits; | |
1360 | remaining = (1<<nbBits)+1; | |
1361 | threshold = 1<<nbBits; | |
1362 | nbBits++; | |
1363 | ||
1364 | while ((remaining>1) && (charnum<=*maxSVPtr)) { | |
1365 | if (previous0) { | |
1366 | unsigned n0 = charnum; | |
1367 | while ((bitStream & 0xFFFF) == 0xFFFF) { | |
1368 | n0+=24; | |
1369 | if (ip < iend-5) { | |
1370 | ip+=2; | |
1371 | bitStream = MEM_readLE32(ip) >> bitCount; | |
1372 | } else { | |
1373 | bitStream >>= 16; | |
1374 | bitCount+=16; | |
1375 | } } | |
1376 | while ((bitStream & 3) == 3) { | |
1377 | n0+=3; | |
1378 | bitStream>>=2; | |
1379 | bitCount+=2; | |
1380 | } | |
1381 | n0 += bitStream & 3; | |
1382 | bitCount += 2; | |
1383 | if (n0 > *maxSVPtr) return ERROR(maxSymbolValue_tooSmall); | |
1384 | while (charnum < n0) normalizedCounter[charnum++] = 0; | |
1385 | if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) { | |
1386 | ip += bitCount>>3; | |
1387 | bitCount &= 7; | |
1388 | bitStream = MEM_readLE32(ip) >> bitCount; | |
1389 | } | |
1390 | else | |
1391 | bitStream >>= 2; | |
1392 | } | |
1393 | { short const max = (short)((2*threshold-1)-remaining); | |
1394 | short count; | |
1395 | ||
1396 | if ((bitStream & (threshold-1)) < (U32)max) { | |
1397 | count = (short)(bitStream & (threshold-1)); | |
1398 | bitCount += nbBits-1; | |
1399 | } else { | |
1400 | count = (short)(bitStream & (2*threshold-1)); | |
1401 | if (count >= threshold) count -= max; | |
1402 | bitCount += nbBits; | |
1403 | } | |
1404 | ||
1405 | count--; /* extra accuracy */ | |
1406 | remaining -= FSEv06_abs(count); | |
1407 | normalizedCounter[charnum++] = count; | |
1408 | previous0 = !count; | |
1409 | while (remaining < threshold) { | |
1410 | nbBits--; | |
1411 | threshold >>= 1; | |
1412 | } | |
1413 | ||
1414 | if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) { | |
1415 | ip += bitCount>>3; | |
1416 | bitCount &= 7; | |
1417 | } else { | |
1418 | bitCount -= (int)(8 * (iend - 4 - ip)); | |
1419 | ip = iend - 4; | |
1420 | } | |
1421 | bitStream = MEM_readLE32(ip) >> (bitCount & 31); | |
1422 | } } /* while ((remaining>1) && (charnum<=*maxSVPtr)) */ | |
1423 | if (remaining != 1) return ERROR(GENERIC); | |
1424 | *maxSVPtr = charnum-1; | |
1425 | ||
1426 | ip += (bitCount+7)>>3; | |
1427 | if ((size_t)(ip-istart) > hbSize) return ERROR(srcSize_wrong); | |
1428 | return ip-istart; | |
1429 | } | |
1430 | /* ****************************************************************** | |
1431 | FSE : Finite State Entropy decoder | |
1432 | Copyright (C) 2013-2015, Yann Collet. | |
1433 | ||
1434 | BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) | |
1435 | ||
1436 | Redistribution and use in source and binary forms, with or without | |
1437 | modification, are permitted provided that the following conditions are | |
1438 | met: | |
1439 | ||
1440 | * Redistributions of source code must retain the above copyright | |
1441 | notice, this list of conditions and the following disclaimer. | |
1442 | * Redistributions in binary form must reproduce the above | |
1443 | copyright notice, this list of conditions and the following disclaimer | |
1444 | in the documentation and/or other materials provided with the | |
1445 | distribution. | |
1446 | ||
1447 | THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
1448 | "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
1449 | LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | |
1450 | A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | |
1451 | OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
1452 | SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | |
1453 | LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
1454 | DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |
1455 | THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
1456 | (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
1457 | OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
1458 | ||
1459 | You can contact the author at : | |
1460 | - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy | |
1461 | - Public forum : https://groups.google.com/forum/#!forum/lz4c | |
1462 | ****************************************************************** */ | |
1463 | ||
1464 | ||
1465 | /* ************************************************************** | |
1466 | * Compiler specifics | |
1467 | ****************************************************************/ | |
1468 | #ifdef _MSC_VER /* Visual Studio */ | |
1469 | # define FORCE_INLINE static __forceinline | |
1470 | # include <intrin.h> /* For Visual 2005 */ | |
1471 | # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ | |
1472 | # pragma warning(disable : 4214) /* disable: C4214: non-int bitfields */ | |
1473 | #else | |
1474 | # if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */ | |
1475 | # ifdef __GNUC__ | |
1476 | # define FORCE_INLINE static inline __attribute__((always_inline)) | |
1477 | # else | |
1478 | # define FORCE_INLINE static inline | |
1479 | # endif | |
1480 | # else | |
1481 | # define FORCE_INLINE static | |
1482 | # endif /* __STDC_VERSION__ */ | |
1483 | #endif | |
1484 | ||
1485 | ||
1486 | /* ************************************************************** | |
1487 | * Error Management | |
1488 | ****************************************************************/ | |
1489 | #define FSEv06_isError ERR_isError | |
1490 | #define FSEv06_STATIC_ASSERT(c) { enum { FSEv06_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */ | |
1491 | ||
1492 | ||
1493 | /* ************************************************************** | |
1494 | * Complex types | |
1495 | ****************************************************************/ | |
1496 | typedef U32 DTable_max_t[FSEv06_DTABLE_SIZE_U32(FSEv06_MAX_TABLELOG)]; | |
1497 | ||
1498 | ||
1499 | /* ************************************************************** | |
1500 | * Templates | |
1501 | ****************************************************************/ | |
1502 | /* | |
1503 | designed to be included | |
1504 | for type-specific functions (template emulation in C) | |
1505 | Objective is to write these functions only once, for improved maintenance | |
1506 | */ | |
1507 | ||
1508 | /* safety checks */ | |
1509 | #ifndef FSEv06_FUNCTION_EXTENSION | |
1510 | # error "FSEv06_FUNCTION_EXTENSION must be defined" | |
1511 | #endif | |
1512 | #ifndef FSEv06_FUNCTION_TYPE | |
1513 | # error "FSEv06_FUNCTION_TYPE must be defined" | |
1514 | #endif | |
1515 | ||
1516 | /* Function names */ | |
1517 | #define FSEv06_CAT(X,Y) X##Y | |
1518 | #define FSEv06_FUNCTION_NAME(X,Y) FSEv06_CAT(X,Y) | |
1519 | #define FSEv06_TYPE_NAME(X,Y) FSEv06_CAT(X,Y) | |
1520 | ||
1521 | ||
1522 | /* Function templates */ | |
1523 | FSEv06_DTable* FSEv06_createDTable (unsigned tableLog) | |
1524 | { | |
1525 | if (tableLog > FSEv06_TABLELOG_ABSOLUTE_MAX) tableLog = FSEv06_TABLELOG_ABSOLUTE_MAX; | |
1526 | return (FSEv06_DTable*)malloc( FSEv06_DTABLE_SIZE_U32(tableLog) * sizeof (U32) ); | |
1527 | } | |
1528 | ||
1529 | void FSEv06_freeDTable (FSEv06_DTable* dt) | |
1530 | { | |
1531 | free(dt); | |
1532 | } | |
1533 | ||
1534 | size_t FSEv06_buildDTable(FSEv06_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog) | |
1535 | { | |
1536 | void* const tdPtr = dt+1; /* because *dt is unsigned, 32-bits aligned on 32-bits */ | |
1537 | FSEv06_DECODE_TYPE* const tableDecode = (FSEv06_DECODE_TYPE*) (tdPtr); | |
1538 | U16 symbolNext[FSEv06_MAX_SYMBOL_VALUE+1]; | |
1539 | ||
1540 | U32 const maxSV1 = maxSymbolValue + 1; | |
1541 | U32 const tableSize = 1 << tableLog; | |
1542 | U32 highThreshold = tableSize-1; | |
1543 | ||
1544 | /* Sanity Checks */ | |
1545 | if (maxSymbolValue > FSEv06_MAX_SYMBOL_VALUE) return ERROR(maxSymbolValue_tooLarge); | |
1546 | if (tableLog > FSEv06_MAX_TABLELOG) return ERROR(tableLog_tooLarge); | |
1547 | ||
1548 | /* Init, lay down lowprob symbols */ | |
1549 | { FSEv06_DTableHeader DTableH; | |
1550 | DTableH.tableLog = (U16)tableLog; | |
1551 | DTableH.fastMode = 1; | |
1552 | { S16 const largeLimit= (S16)(1 << (tableLog-1)); | |
1553 | U32 s; | |
1554 | for (s=0; s<maxSV1; s++) { | |
1555 | if (normalizedCounter[s]==-1) { | |
1556 | tableDecode[highThreshold--].symbol = (FSEv06_FUNCTION_TYPE)s; | |
1557 | symbolNext[s] = 1; | |
1558 | } else { | |
1559 | if (normalizedCounter[s] >= largeLimit) DTableH.fastMode=0; | |
1560 | symbolNext[s] = normalizedCounter[s]; | |
1561 | } } } | |
1562 | memcpy(dt, &DTableH, sizeof(DTableH)); | |
1563 | } | |
1564 | ||
1565 | /* Spread symbols */ | |
1566 | { U32 const tableMask = tableSize-1; | |
1567 | U32 const step = FSEv06_TABLESTEP(tableSize); | |
1568 | U32 s, position = 0; | |
1569 | for (s=0; s<maxSV1; s++) { | |
1570 | int i; | |
1571 | for (i=0; i<normalizedCounter[s]; i++) { | |
1572 | tableDecode[position].symbol = (FSEv06_FUNCTION_TYPE)s; | |
1573 | position = (position + step) & tableMask; | |
1574 | while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */ | |
1575 | } } | |
1576 | ||
1577 | if (position!=0) return ERROR(GENERIC); /* position must reach all cells once, otherwise normalizedCounter is incorrect */ | |
1578 | } | |
1579 | ||
1580 | /* Build Decoding table */ | |
1581 | { U32 u; | |
1582 | for (u=0; u<tableSize; u++) { | |
1583 | FSEv06_FUNCTION_TYPE const symbol = (FSEv06_FUNCTION_TYPE)(tableDecode[u].symbol); | |
1584 | U16 nextState = symbolNext[symbol]++; | |
1585 | tableDecode[u].nbBits = (BYTE) (tableLog - BITv06_highbit32 ((U32)nextState) ); | |
1586 | tableDecode[u].newState = (U16) ( (nextState << tableDecode[u].nbBits) - tableSize); | |
1587 | } } | |
1588 | ||
1589 | return 0; | |
1590 | } | |
1591 | ||
1592 | ||
1593 | ||
1594 | #ifndef FSEv06_COMMONDEFS_ONLY | |
1595 | ||
1596 | /*-******************************************************* | |
1597 | * Decompression (Byte symbols) | |
1598 | *********************************************************/ | |
1599 | size_t FSEv06_buildDTable_rle (FSEv06_DTable* dt, BYTE symbolValue) | |
1600 | { | |
1601 | void* ptr = dt; | |
1602 | FSEv06_DTableHeader* const DTableH = (FSEv06_DTableHeader*)ptr; | |
1603 | void* dPtr = dt + 1; | |
1604 | FSEv06_decode_t* const cell = (FSEv06_decode_t*)dPtr; | |
1605 | ||
1606 | DTableH->tableLog = 0; | |
1607 | DTableH->fastMode = 0; | |
1608 | ||
1609 | cell->newState = 0; | |
1610 | cell->symbol = symbolValue; | |
1611 | cell->nbBits = 0; | |
1612 | ||
1613 | return 0; | |
1614 | } | |
1615 | ||
1616 | ||
1617 | size_t FSEv06_buildDTable_raw (FSEv06_DTable* dt, unsigned nbBits) | |
1618 | { | |
1619 | void* ptr = dt; | |
1620 | FSEv06_DTableHeader* const DTableH = (FSEv06_DTableHeader*)ptr; | |
1621 | void* dPtr = dt + 1; | |
1622 | FSEv06_decode_t* const dinfo = (FSEv06_decode_t*)dPtr; | |
1623 | const unsigned tableSize = 1 << nbBits; | |
1624 | const unsigned tableMask = tableSize - 1; | |
1625 | const unsigned maxSV1 = tableMask+1; | |
1626 | unsigned s; | |
1627 | ||
1628 | /* Sanity checks */ | |
1629 | if (nbBits < 1) return ERROR(GENERIC); /* min size */ | |
1630 | ||
1631 | /* Build Decoding Table */ | |
1632 | DTableH->tableLog = (U16)nbBits; | |
1633 | DTableH->fastMode = 1; | |
1634 | for (s=0; s<maxSV1; s++) { | |
1635 | dinfo[s].newState = 0; | |
1636 | dinfo[s].symbol = (BYTE)s; | |
1637 | dinfo[s].nbBits = (BYTE)nbBits; | |
1638 | } | |
1639 | ||
1640 | return 0; | |
1641 | } | |
1642 | ||
1643 | FORCE_INLINE size_t FSEv06_decompress_usingDTable_generic( | |
1644 | void* dst, size_t maxDstSize, | |
1645 | const void* cSrc, size_t cSrcSize, | |
1646 | const FSEv06_DTable* dt, const unsigned fast) | |
1647 | { | |
1648 | BYTE* const ostart = (BYTE*) dst; | |
1649 | BYTE* op = ostart; | |
1650 | BYTE* const omax = op + maxDstSize; | |
1651 | BYTE* const olimit = omax-3; | |
1652 | ||
1653 | BITv06_DStream_t bitD; | |
1654 | FSEv06_DState_t state1; | |
1655 | FSEv06_DState_t state2; | |
1656 | ||
1657 | /* Init */ | |
1658 | { size_t const errorCode = BITv06_initDStream(&bitD, cSrc, cSrcSize); /* replaced last arg by maxCompressed Size */ | |
1659 | if (FSEv06_isError(errorCode)) return errorCode; } | |
1660 | ||
1661 | FSEv06_initDState(&state1, &bitD, dt); | |
1662 | FSEv06_initDState(&state2, &bitD, dt); | |
1663 | ||
1664 | #define FSEv06_GETSYMBOL(statePtr) fast ? FSEv06_decodeSymbolFast(statePtr, &bitD) : FSEv06_decodeSymbol(statePtr, &bitD) | |
1665 | ||
1666 | /* 4 symbols per loop */ | |
1667 | for ( ; (BITv06_reloadDStream(&bitD)==BITv06_DStream_unfinished) && (op<olimit) ; op+=4) { | |
1668 | op[0] = FSEv06_GETSYMBOL(&state1); | |
1669 | ||
1670 | if (FSEv06_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */ | |
1671 | BITv06_reloadDStream(&bitD); | |
1672 | ||
1673 | op[1] = FSEv06_GETSYMBOL(&state2); | |
1674 | ||
1675 | if (FSEv06_MAX_TABLELOG*4+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */ | |
1676 | { if (BITv06_reloadDStream(&bitD) > BITv06_DStream_unfinished) { op+=2; break; } } | |
1677 | ||
1678 | op[2] = FSEv06_GETSYMBOL(&state1); | |
1679 | ||
1680 | if (FSEv06_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */ | |
1681 | BITv06_reloadDStream(&bitD); | |
1682 | ||
1683 | op[3] = FSEv06_GETSYMBOL(&state2); | |
1684 | } | |
1685 | ||
1686 | /* tail */ | |
1687 | /* note : BITv06_reloadDStream(&bitD) >= FSEv06_DStream_partiallyFilled; Ends at exactly BITv06_DStream_completed */ | |
1688 | while (1) { | |
1689 | if (op>(omax-2)) return ERROR(dstSize_tooSmall); | |
1690 | ||
1691 | *op++ = FSEv06_GETSYMBOL(&state1); | |
1692 | ||
1693 | if (BITv06_reloadDStream(&bitD)==BITv06_DStream_overflow) { | |
1694 | *op++ = FSEv06_GETSYMBOL(&state2); | |
1695 | break; | |
1696 | } | |
1697 | ||
1698 | if (op>(omax-2)) return ERROR(dstSize_tooSmall); | |
1699 | ||
1700 | *op++ = FSEv06_GETSYMBOL(&state2); | |
1701 | ||
1702 | if (BITv06_reloadDStream(&bitD)==BITv06_DStream_overflow) { | |
1703 | *op++ = FSEv06_GETSYMBOL(&state1); | |
1704 | break; | |
1705 | } } | |
1706 | ||
1707 | return op-ostart; | |
1708 | } | |
1709 | ||
1710 | ||
1711 | size_t FSEv06_decompress_usingDTable(void* dst, size_t originalSize, | |
1712 | const void* cSrc, size_t cSrcSize, | |
1713 | const FSEv06_DTable* dt) | |
1714 | { | |
1715 | const void* ptr = dt; | |
1716 | const FSEv06_DTableHeader* DTableH = (const FSEv06_DTableHeader*)ptr; | |
1717 | const U32 fastMode = DTableH->fastMode; | |
1718 | ||
1719 | /* select fast mode (static) */ | |
1720 | if (fastMode) return FSEv06_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1); | |
1721 | return FSEv06_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0); | |
1722 | } | |
1723 | ||
1724 | ||
1725 | size_t FSEv06_decompress(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize) | |
1726 | { | |
1727 | const BYTE* const istart = (const BYTE*)cSrc; | |
1728 | const BYTE* ip = istart; | |
1729 | short counting[FSEv06_MAX_SYMBOL_VALUE+1]; | |
1730 | DTable_max_t dt; /* Static analyzer seems unable to understand this table will be properly initialized later */ | |
1731 | unsigned tableLog; | |
1732 | unsigned maxSymbolValue = FSEv06_MAX_SYMBOL_VALUE; | |
1733 | ||
1734 | if (cSrcSize<2) return ERROR(srcSize_wrong); /* too small input size */ | |
1735 | ||
1736 | /* normal FSE decoding mode */ | |
1737 | { size_t const NCountLength = FSEv06_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize); | |
1738 | if (FSEv06_isError(NCountLength)) return NCountLength; | |
1739 | if (NCountLength >= cSrcSize) return ERROR(srcSize_wrong); /* too small input size */ | |
1740 | ip += NCountLength; | |
1741 | cSrcSize -= NCountLength; | |
1742 | } | |
1743 | ||
1744 | { size_t const errorCode = FSEv06_buildDTable (dt, counting, maxSymbolValue, tableLog); | |
1745 | if (FSEv06_isError(errorCode)) return errorCode; } | |
1746 | ||
1747 | return FSEv06_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, dt); /* always return, even if it is an error code */ | |
1748 | } | |
1749 | ||
1750 | ||
1751 | ||
1752 | #endif /* FSEv06_COMMONDEFS_ONLY */ | |
1753 | /* ****************************************************************** | |
1754 | Huffman coder, part of New Generation Entropy library | |
1755 | header file | |
1756 | Copyright (C) 2013-2016, Yann Collet. | |
1757 | ||
1758 | BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) | |
1759 | ||
1760 | Redistribution and use in source and binary forms, with or without | |
1761 | modification, are permitted provided that the following conditions are | |
1762 | met: | |
1763 | ||
1764 | * Redistributions of source code must retain the above copyright | |
1765 | notice, this list of conditions and the following disclaimer. | |
1766 | * Redistributions in binary form must reproduce the above | |
1767 | copyright notice, this list of conditions and the following disclaimer | |
1768 | in the documentation and/or other materials provided with the | |
1769 | distribution. | |
1770 | ||
1771 | THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
1772 | "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
1773 | LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | |
1774 | A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | |
1775 | OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
1776 | SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | |
1777 | LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
1778 | DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |
1779 | THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
1780 | (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
1781 | OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
1782 | ||
1783 | You can contact the author at : | |
1784 | - Source repository : https://github.com/Cyan4973/FiniteStateEntropy | |
1785 | ****************************************************************** */ | |
1786 | #ifndef HUFv06_H | |
1787 | #define HUFv06_H | |
1788 | ||
1789 | #if defined (__cplusplus) | |
1790 | extern "C" { | |
1791 | #endif | |
1792 | ||
1793 | ||
1794 | /* **************************************** | |
1795 | * HUF simple functions | |
1796 | ******************************************/ | |
1797 | size_t HUFv06_decompress(void* dst, size_t dstSize, | |
1798 | const void* cSrc, size_t cSrcSize); | |
1799 | /* | |
1800 | HUFv06_decompress() : | |
1801 | Decompress HUF data from buffer 'cSrc', of size 'cSrcSize', | |
1802 | into already allocated destination buffer 'dst', of size 'dstSize'. | |
1803 | `dstSize` : must be the **exact** size of original (uncompressed) data. | |
1804 | Note : in contrast with FSE, HUFv06_decompress can regenerate | |
1805 | RLE (cSrcSize==1) and uncompressed (cSrcSize==dstSize) data, | |
1806 | because it knows size to regenerate. | |
1807 | @return : size of regenerated data (== dstSize) | |
1808 | or an error code, which can be tested using HUFv06_isError() | |
1809 | */ | |
1810 | ||
1811 | ||
1812 | /* **************************************** | |
1813 | * Tool functions | |
1814 | ******************************************/ | |
1815 | size_t HUFv06_compressBound(size_t size); /**< maximum compressed size */ | |
1816 | ||
1817 | ||
1818 | #if defined (__cplusplus) | |
1819 | } | |
1820 | #endif | |
1821 | ||
1822 | #endif /* HUFv06_H */ | |
1823 | /* ****************************************************************** | |
1824 | Huffman codec, part of New Generation Entropy library | |
1825 | header file, for static linking only | |
1826 | Copyright (C) 2013-2016, Yann Collet | |
1827 | ||
1828 | BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) | |
1829 | ||
1830 | Redistribution and use in source and binary forms, with or without | |
1831 | modification, are permitted provided that the following conditions are | |
1832 | met: | |
1833 | ||
1834 | * Redistributions of source code must retain the above copyright | |
1835 | notice, this list of conditions and the following disclaimer. | |
1836 | * Redistributions in binary form must reproduce the above | |
1837 | copyright notice, this list of conditions and the following disclaimer | |
1838 | in the documentation and/or other materials provided with the | |
1839 | distribution. | |
1840 | ||
1841 | THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
1842 | "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
1843 | LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | |
1844 | A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | |
1845 | OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
1846 | SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | |
1847 | LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
1848 | DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |
1849 | THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
1850 | (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
1851 | OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
1852 | ||
1853 | You can contact the author at : | |
1854 | - Source repository : https://github.com/Cyan4973/FiniteStateEntropy | |
1855 | ****************************************************************** */ | |
1856 | #ifndef HUFv06_STATIC_H | |
1857 | #define HUFv06_STATIC_H | |
1858 | ||
1859 | #if defined (__cplusplus) | |
1860 | extern "C" { | |
1861 | #endif | |
1862 | ||
1863 | ||
1864 | /* **************************************** | |
1865 | * Static allocation | |
1866 | ******************************************/ | |
1867 | /* HUF buffer bounds */ | |
1868 | #define HUFv06_CTABLEBOUND 129 | |
1869 | #define HUFv06_BLOCKBOUND(size) (size + (size>>8) + 8) /* only true if incompressible pre-filtered with fast heuristic */ | |
1870 | #define HUFv06_COMPRESSBOUND(size) (HUFv06_CTABLEBOUND + HUFv06_BLOCKBOUND(size)) /* Macro version, useful for static allocation */ | |
1871 | ||
1872 | /* static allocation of HUF's DTable */ | |
1873 | #define HUFv06_DTABLE_SIZE(maxTableLog) (1 + (1<<maxTableLog)) | |
1874 | #define HUFv06_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \ | |
1875 | unsigned short DTable[HUFv06_DTABLE_SIZE(maxTableLog)] = { maxTableLog } | |
1876 | #define HUFv06_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \ | |
1877 | unsigned int DTable[HUFv06_DTABLE_SIZE(maxTableLog)] = { maxTableLog } | |
1878 | #define HUFv06_CREATE_STATIC_DTABLEX6(DTable, maxTableLog) \ | |
1879 | unsigned int DTable[HUFv06_DTABLE_SIZE(maxTableLog) * 3 / 2] = { maxTableLog } | |
1880 | ||
1881 | ||
1882 | /* **************************************** | |
1883 | * Advanced decompression functions | |
1884 | ******************************************/ | |
1885 | size_t HUFv06_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* single-symbol decoder */ | |
1886 | size_t HUFv06_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* double-symbols decoder */ | |
1887 | ||
1888 | ||
1889 | ||
1890 | /*! | |
1891 | HUFv06_decompress() does the following: | |
1892 | 1. select the decompression algorithm (X2, X4, X6) based on pre-computed heuristics | |
1893 | 2. build Huffman table from save, using HUFv06_readDTableXn() | |
1894 | 3. decode 1 or 4 segments in parallel using HUFv06_decompressSXn_usingDTable | |
1895 | */ | |
1896 | size_t HUFv06_readDTableX2 (unsigned short* DTable, const void* src, size_t srcSize); | |
1897 | size_t HUFv06_readDTableX4 (unsigned* DTable, const void* src, size_t srcSize); | |
1898 | ||
1899 | size_t HUFv06_decompress4X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned short* DTable); | |
1900 | size_t HUFv06_decompress4X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned* DTable); | |
1901 | ||
1902 | ||
1903 | /* single stream variants */ | |
1904 | size_t HUFv06_decompress1X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* single-symbol decoder */ | |
1905 | size_t HUFv06_decompress1X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* double-symbol decoder */ | |
1906 | ||
1907 | size_t HUFv06_decompress1X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned short* DTable); | |
1908 | size_t HUFv06_decompress1X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned* DTable); | |
1909 | ||
1910 | ||
1911 | ||
1912 | /* ************************************************************** | |
1913 | * Constants | |
1914 | ****************************************************************/ | |
1915 | #define HUFv06_ABSOLUTEMAX_TABLELOG 16 /* absolute limit of HUFv06_MAX_TABLELOG. Beyond that value, code does not work */ | |
1916 | #define HUFv06_MAX_TABLELOG 12 /* max configured tableLog (for static allocation); can be modified up to HUFv06_ABSOLUTEMAX_TABLELOG */ | |
1917 | #define HUFv06_DEFAULT_TABLELOG HUFv06_MAX_TABLELOG /* tableLog by default, when not specified */ | |
1918 | #define HUFv06_MAX_SYMBOL_VALUE 255 | |
1919 | #if (HUFv06_MAX_TABLELOG > HUFv06_ABSOLUTEMAX_TABLELOG) | |
1920 | # error "HUFv06_MAX_TABLELOG is too large !" | |
1921 | #endif | |
1922 | ||
1923 | ||
1924 | ||
1925 | /*! HUFv06_readStats() : | |
1926 | Read compact Huffman tree, saved by HUFv06_writeCTable(). | |
1927 | `huffWeight` is destination buffer. | |
1928 | @return : size read from `src` | |
1929 | */ | |
1930 | MEM_STATIC size_t HUFv06_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats, | |
1931 | U32* nbSymbolsPtr, U32* tableLogPtr, | |
1932 | const void* src, size_t srcSize) | |
1933 | { | |
1934 | U32 weightTotal; | |
1935 | const BYTE* ip = (const BYTE*) src; | |
1936 | size_t iSize; | |
1937 | size_t oSize; | |
1938 | ||
1939 | if (!srcSize) return ERROR(srcSize_wrong); | |
1940 | iSize = ip[0]; | |
1941 | //memset(huffWeight, 0, hwSize); /* is not necessary, even though some analyzer complain ... */ | |
1942 | ||
1943 | if (iSize >= 128) { /* special header */ | |
1944 | if (iSize >= (242)) { /* RLE */ | |
1945 | static U32 l[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 }; | |
1946 | oSize = l[iSize-242]; | |
1947 | memset(huffWeight, 1, hwSize); | |
1948 | iSize = 0; | |
1949 | } | |
1950 | else { /* Incompressible */ | |
1951 | oSize = iSize - 127; | |
1952 | iSize = ((oSize+1)/2); | |
1953 | if (iSize+1 > srcSize) return ERROR(srcSize_wrong); | |
1954 | if (oSize >= hwSize) return ERROR(corruption_detected); | |
1955 | ip += 1; | |
1956 | { U32 n; | |
1957 | for (n=0; n<oSize; n+=2) { | |
1958 | huffWeight[n] = ip[n/2] >> 4; | |
1959 | huffWeight[n+1] = ip[n/2] & 15; | |
1960 | } } } } | |
1961 | else { /* header compressed with FSE (normal case) */ | |
1962 | if (iSize+1 > srcSize) return ERROR(srcSize_wrong); | |
1963 | oSize = FSEv06_decompress(huffWeight, hwSize-1, ip+1, iSize); /* max (hwSize-1) values decoded, as last one is implied */ | |
1964 | if (FSEv06_isError(oSize)) return oSize; | |
1965 | } | |
1966 | ||
1967 | /* collect weight stats */ | |
1968 | memset(rankStats, 0, (HUFv06_ABSOLUTEMAX_TABLELOG + 1) * sizeof(U32)); | |
1969 | weightTotal = 0; | |
1970 | { U32 n; for (n=0; n<oSize; n++) { | |
1971 | if (huffWeight[n] >= HUFv06_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected); | |
1972 | rankStats[huffWeight[n]]++; | |
1973 | weightTotal += (1 << huffWeight[n]) >> 1; | |
1974 | } } | |
1975 | if (weightTotal == 0) return ERROR(corruption_detected); | |
1976 | ||
1977 | /* get last non-null symbol weight (implied, total must be 2^n) */ | |
1978 | { U32 const tableLog = BITv06_highbit32(weightTotal) + 1; | |
1979 | if (tableLog > HUFv06_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected); | |
1980 | *tableLogPtr = tableLog; | |
1981 | /* determine last weight */ | |
1982 | { U32 const total = 1 << tableLog; | |
1983 | U32 const rest = total - weightTotal; | |
1984 | U32 const verif = 1 << BITv06_highbit32(rest); | |
1985 | U32 const lastWeight = BITv06_highbit32(rest) + 1; | |
1986 | if (verif != rest) return ERROR(corruption_detected); /* last value must be a clean power of 2 */ | |
1987 | huffWeight[oSize] = (BYTE)lastWeight; | |
1988 | rankStats[lastWeight]++; | |
1989 | } } | |
1990 | ||
1991 | /* check tree construction validity */ | |
1992 | if ((rankStats[1] < 2) || (rankStats[1] & 1)) return ERROR(corruption_detected); /* by construction : at least 2 elts of rank 1, must be even */ | |
1993 | ||
1994 | /* results */ | |
1995 | *nbSymbolsPtr = (U32)(oSize+1); | |
1996 | return iSize+1; | |
1997 | } | |
1998 | ||
1999 | ||
2000 | ||
2001 | #if defined (__cplusplus) | |
2002 | } | |
2003 | #endif | |
2004 | ||
2005 | #endif /* HUFv06_STATIC_H */ | |
2006 | /* ****************************************************************** | |
2007 | Huffman decoder, part of New Generation Entropy library | |
2008 | Copyright (C) 2013-2016, Yann Collet. | |
2009 | ||
2010 | BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) | |
2011 | ||
2012 | Redistribution and use in source and binary forms, with or without | |
2013 | modification, are permitted provided that the following conditions are | |
2014 | met: | |
2015 | ||
2016 | * Redistributions of source code must retain the above copyright | |
2017 | notice, this list of conditions and the following disclaimer. | |
2018 | * Redistributions in binary form must reproduce the above | |
2019 | copyright notice, this list of conditions and the following disclaimer | |
2020 | in the documentation and/or other materials provided with the | |
2021 | distribution. | |
2022 | ||
2023 | THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
2024 | "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
2025 | LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | |
2026 | A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | |
2027 | OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
2028 | SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | |
2029 | LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
2030 | DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |
2031 | THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
2032 | (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
2033 | OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
2034 | ||
2035 | You can contact the author at : | |
2036 | - FSE+HUF source repository : https://github.com/Cyan4973/FiniteStateEntropy | |
2037 | - Public forum : https://groups.google.com/forum/#!forum/lz4c | |
2038 | ****************************************************************** */ | |
2039 | ||
2040 | /* ************************************************************** | |
2041 | * Compiler specifics | |
2042 | ****************************************************************/ | |
2043 | #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) | |
2044 | /* inline is defined */ | |
2045 | #elif defined(_MSC_VER) | |
2046 | # define inline __inline | |
2047 | #else | |
2048 | # define inline /* disable inline */ | |
2049 | #endif | |
2050 | ||
2051 | ||
2052 | #ifdef _MSC_VER /* Visual Studio */ | |
2053 | # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ | |
2054 | #endif | |
2055 | ||
2056 | ||
2057 | ||
2058 | /* ************************************************************** | |
2059 | * Error Management | |
2060 | ****************************************************************/ | |
2061 | #define HUFv06_STATIC_ASSERT(c) { enum { HUFv06_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */ | |
2062 | ||
2063 | ||
2064 | ||
2065 | /* ******************************************************* | |
2066 | * HUF : Huffman block decompression | |
2067 | *********************************************************/ | |
2068 | typedef struct { BYTE byte; BYTE nbBits; } HUFv06_DEltX2; /* single-symbol decoding */ | |
2069 | ||
2070 | typedef struct { U16 sequence; BYTE nbBits; BYTE length; } HUFv06_DEltX4; /* double-symbols decoding */ | |
2071 | ||
2072 | typedef struct { BYTE symbol; BYTE weight; } sortedSymbol_t; | |
2073 | ||
2074 | ||
2075 | ||
2076 | /*-***************************/ | |
2077 | /* single-symbol decoding */ | |
2078 | /*-***************************/ | |
2079 | ||
2080 | size_t HUFv06_readDTableX2 (U16* DTable, const void* src, size_t srcSize) | |
2081 | { | |
2082 | BYTE huffWeight[HUFv06_MAX_SYMBOL_VALUE + 1]; | |
2083 | U32 rankVal[HUFv06_ABSOLUTEMAX_TABLELOG + 1]; /* large enough for values from 0 to 16 */ | |
2084 | U32 tableLog = 0; | |
2085 | size_t iSize; | |
2086 | U32 nbSymbols = 0; | |
2087 | U32 n; | |
2088 | U32 nextRankStart; | |
2089 | void* const dtPtr = DTable + 1; | |
2090 | HUFv06_DEltX2* const dt = (HUFv06_DEltX2*)dtPtr; | |
2091 | ||
2092 | HUFv06_STATIC_ASSERT(sizeof(HUFv06_DEltX2) == sizeof(U16)); /* if compilation fails here, assertion is false */ | |
2093 | //memset(huffWeight, 0, sizeof(huffWeight)); /* is not necessary, even though some analyzer complain ... */ | |
2094 | ||
2095 | iSize = HUFv06_readStats(huffWeight, HUFv06_MAX_SYMBOL_VALUE + 1, rankVal, &nbSymbols, &tableLog, src, srcSize); | |
2096 | if (HUFv06_isError(iSize)) return iSize; | |
2097 | ||
2098 | /* check result */ | |
2099 | if (tableLog > DTable[0]) return ERROR(tableLog_tooLarge); /* DTable is too small */ | |
2100 | DTable[0] = (U16)tableLog; /* maybe should separate sizeof allocated DTable, from used size of DTable, in case of re-use */ | |
2101 | ||
2102 | /* Prepare ranks */ | |
2103 | nextRankStart = 0; | |
2104 | for (n=1; n<tableLog+1; n++) { | |
2105 | U32 current = nextRankStart; | |
2106 | nextRankStart += (rankVal[n] << (n-1)); | |
2107 | rankVal[n] = current; | |
2108 | } | |
2109 | ||
2110 | /* fill DTable */ | |
2111 | for (n=0; n<nbSymbols; n++) { | |
2112 | const U32 w = huffWeight[n]; | |
2113 | const U32 length = (1 << w) >> 1; | |
2114 | U32 i; | |
2115 | HUFv06_DEltX2 D; | |
2116 | D.byte = (BYTE)n; D.nbBits = (BYTE)(tableLog + 1 - w); | |
2117 | for (i = rankVal[w]; i < rankVal[w] + length; i++) | |
2118 | dt[i] = D; | |
2119 | rankVal[w] += length; | |
2120 | } | |
2121 | ||
2122 | return iSize; | |
2123 | } | |
2124 | ||
2125 | ||
2126 | static BYTE HUFv06_decodeSymbolX2(BITv06_DStream_t* Dstream, const HUFv06_DEltX2* dt, const U32 dtLog) | |
2127 | { | |
2128 | const size_t val = BITv06_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */ | |
2129 | const BYTE c = dt[val].byte; | |
2130 | BITv06_skipBits(Dstream, dt[val].nbBits); | |
2131 | return c; | |
2132 | } | |
2133 | ||
2134 | #define HUFv06_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \ | |
2135 | *ptr++ = HUFv06_decodeSymbolX2(DStreamPtr, dt, dtLog) | |
2136 | ||
2137 | #define HUFv06_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \ | |
2138 | if (MEM_64bits() || (HUFv06_MAX_TABLELOG<=12)) \ | |
2139 | HUFv06_DECODE_SYMBOLX2_0(ptr, DStreamPtr) | |
2140 | ||
2141 | #define HUFv06_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \ | |
2142 | if (MEM_64bits()) \ | |
2143 | HUFv06_DECODE_SYMBOLX2_0(ptr, DStreamPtr) | |
2144 | ||
2145 | static inline size_t HUFv06_decodeStreamX2(BYTE* p, BITv06_DStream_t* const bitDPtr, BYTE* const pEnd, const HUFv06_DEltX2* const dt, const U32 dtLog) | |
2146 | { | |
2147 | BYTE* const pStart = p; | |
2148 | ||
2149 | /* up to 4 symbols at a time */ | |
2150 | while ((BITv06_reloadDStream(bitDPtr) == BITv06_DStream_unfinished) && (p <= pEnd-4)) { | |
2151 | HUFv06_DECODE_SYMBOLX2_2(p, bitDPtr); | |
2152 | HUFv06_DECODE_SYMBOLX2_1(p, bitDPtr); | |
2153 | HUFv06_DECODE_SYMBOLX2_2(p, bitDPtr); | |
2154 | HUFv06_DECODE_SYMBOLX2_0(p, bitDPtr); | |
2155 | } | |
2156 | ||
2157 | /* closer to the end */ | |
2158 | while ((BITv06_reloadDStream(bitDPtr) == BITv06_DStream_unfinished) && (p < pEnd)) | |
2159 | HUFv06_DECODE_SYMBOLX2_0(p, bitDPtr); | |
2160 | ||
2161 | /* no more data to retrieve from bitstream, hence no need to reload */ | |
2162 | while (p < pEnd) | |
2163 | HUFv06_DECODE_SYMBOLX2_0(p, bitDPtr); | |
2164 | ||
2165 | return pEnd-pStart; | |
2166 | } | |
2167 | ||
2168 | size_t HUFv06_decompress1X2_usingDTable( | |
2169 | void* dst, size_t dstSize, | |
2170 | const void* cSrc, size_t cSrcSize, | |
2171 | const U16* DTable) | |
2172 | { | |
2173 | BYTE* op = (BYTE*)dst; | |
2174 | BYTE* const oend = op + dstSize; | |
2175 | const U32 dtLog = DTable[0]; | |
2176 | const void* dtPtr = DTable; | |
2177 | const HUFv06_DEltX2* const dt = ((const HUFv06_DEltX2*)dtPtr)+1; | |
2178 | BITv06_DStream_t bitD; | |
2179 | ||
2180 | { size_t const errorCode = BITv06_initDStream(&bitD, cSrc, cSrcSize); | |
2181 | if (HUFv06_isError(errorCode)) return errorCode; } | |
2182 | ||
2183 | HUFv06_decodeStreamX2(op, &bitD, oend, dt, dtLog); | |
2184 | ||
2185 | /* check */ | |
2186 | if (!BITv06_endOfDStream(&bitD)) return ERROR(corruption_detected); | |
2187 | ||
2188 | return dstSize; | |
2189 | } | |
2190 | ||
2191 | size_t HUFv06_decompress1X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) | |
2192 | { | |
2193 | HUFv06_CREATE_STATIC_DTABLEX2(DTable, HUFv06_MAX_TABLELOG); | |
2194 | const BYTE* ip = (const BYTE*) cSrc; | |
2195 | ||
2196 | size_t const errorCode = HUFv06_readDTableX2 (DTable, cSrc, cSrcSize); | |
2197 | if (HUFv06_isError(errorCode)) return errorCode; | |
2198 | if (errorCode >= cSrcSize) return ERROR(srcSize_wrong); | |
2199 | ip += errorCode; | |
2200 | cSrcSize -= errorCode; | |
2201 | ||
2202 | return HUFv06_decompress1X2_usingDTable (dst, dstSize, ip, cSrcSize, DTable); | |
2203 | } | |
2204 | ||
2205 | ||
2206 | size_t HUFv06_decompress4X2_usingDTable( | |
2207 | void* dst, size_t dstSize, | |
2208 | const void* cSrc, size_t cSrcSize, | |
2209 | const U16* DTable) | |
2210 | { | |
2211 | /* Check */ | |
2212 | if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */ | |
2213 | ||
2214 | { const BYTE* const istart = (const BYTE*) cSrc; | |
2215 | BYTE* const ostart = (BYTE*) dst; | |
2216 | BYTE* const oend = ostart + dstSize; | |
2217 | const void* const dtPtr = DTable; | |
2218 | const HUFv06_DEltX2* const dt = ((const HUFv06_DEltX2*)dtPtr) +1; | |
2219 | const U32 dtLog = DTable[0]; | |
2220 | size_t errorCode; | |
2221 | ||
2222 | /* Init */ | |
2223 | BITv06_DStream_t bitD1; | |
2224 | BITv06_DStream_t bitD2; | |
2225 | BITv06_DStream_t bitD3; | |
2226 | BITv06_DStream_t bitD4; | |
2227 | const size_t length1 = MEM_readLE16(istart); | |
2228 | const size_t length2 = MEM_readLE16(istart+2); | |
2229 | const size_t length3 = MEM_readLE16(istart+4); | |
2230 | size_t length4; | |
2231 | const BYTE* const istart1 = istart + 6; /* jumpTable */ | |
2232 | const BYTE* const istart2 = istart1 + length1; | |
2233 | const BYTE* const istart3 = istart2 + length2; | |
2234 | const BYTE* const istart4 = istart3 + length3; | |
2235 | const size_t segmentSize = (dstSize+3) / 4; | |
2236 | BYTE* const opStart2 = ostart + segmentSize; | |
2237 | BYTE* const opStart3 = opStart2 + segmentSize; | |
2238 | BYTE* const opStart4 = opStart3 + segmentSize; | |
2239 | BYTE* op1 = ostart; | |
2240 | BYTE* op2 = opStart2; | |
2241 | BYTE* op3 = opStart3; | |
2242 | BYTE* op4 = opStart4; | |
2243 | U32 endSignal; | |
2244 | ||
2245 | length4 = cSrcSize - (length1 + length2 + length3 + 6); | |
2246 | if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */ | |
2247 | errorCode = BITv06_initDStream(&bitD1, istart1, length1); | |
2248 | if (HUFv06_isError(errorCode)) return errorCode; | |
2249 | errorCode = BITv06_initDStream(&bitD2, istart2, length2); | |
2250 | if (HUFv06_isError(errorCode)) return errorCode; | |
2251 | errorCode = BITv06_initDStream(&bitD3, istart3, length3); | |
2252 | if (HUFv06_isError(errorCode)) return errorCode; | |
2253 | errorCode = BITv06_initDStream(&bitD4, istart4, length4); | |
2254 | if (HUFv06_isError(errorCode)) return errorCode; | |
2255 | ||
2256 | /* 16-32 symbols per loop (4-8 symbols per stream) */ | |
2257 | endSignal = BITv06_reloadDStream(&bitD1) | BITv06_reloadDStream(&bitD2) | BITv06_reloadDStream(&bitD3) | BITv06_reloadDStream(&bitD4); | |
2258 | for ( ; (endSignal==BITv06_DStream_unfinished) && (op4<(oend-7)) ; ) { | |
2259 | HUFv06_DECODE_SYMBOLX2_2(op1, &bitD1); | |
2260 | HUFv06_DECODE_SYMBOLX2_2(op2, &bitD2); | |
2261 | HUFv06_DECODE_SYMBOLX2_2(op3, &bitD3); | |
2262 | HUFv06_DECODE_SYMBOLX2_2(op4, &bitD4); | |
2263 | HUFv06_DECODE_SYMBOLX2_1(op1, &bitD1); | |
2264 | HUFv06_DECODE_SYMBOLX2_1(op2, &bitD2); | |
2265 | HUFv06_DECODE_SYMBOLX2_1(op3, &bitD3); | |
2266 | HUFv06_DECODE_SYMBOLX2_1(op4, &bitD4); | |
2267 | HUFv06_DECODE_SYMBOLX2_2(op1, &bitD1); | |
2268 | HUFv06_DECODE_SYMBOLX2_2(op2, &bitD2); | |
2269 | HUFv06_DECODE_SYMBOLX2_2(op3, &bitD3); | |
2270 | HUFv06_DECODE_SYMBOLX2_2(op4, &bitD4); | |
2271 | HUFv06_DECODE_SYMBOLX2_0(op1, &bitD1); | |
2272 | HUFv06_DECODE_SYMBOLX2_0(op2, &bitD2); | |
2273 | HUFv06_DECODE_SYMBOLX2_0(op3, &bitD3); | |
2274 | HUFv06_DECODE_SYMBOLX2_0(op4, &bitD4); | |
2275 | endSignal = BITv06_reloadDStream(&bitD1) | BITv06_reloadDStream(&bitD2) | BITv06_reloadDStream(&bitD3) | BITv06_reloadDStream(&bitD4); | |
2276 | } | |
2277 | ||
2278 | /* check corruption */ | |
2279 | if (op1 > opStart2) return ERROR(corruption_detected); | |
2280 | if (op2 > opStart3) return ERROR(corruption_detected); | |
2281 | if (op3 > opStart4) return ERROR(corruption_detected); | |
2282 | /* note : op4 supposed already verified within main loop */ | |
2283 | ||
2284 | /* finish bitStreams one by one */ | |
2285 | HUFv06_decodeStreamX2(op1, &bitD1, opStart2, dt, dtLog); | |
2286 | HUFv06_decodeStreamX2(op2, &bitD2, opStart3, dt, dtLog); | |
2287 | HUFv06_decodeStreamX2(op3, &bitD3, opStart4, dt, dtLog); | |
2288 | HUFv06_decodeStreamX2(op4, &bitD4, oend, dt, dtLog); | |
2289 | ||
2290 | /* check */ | |
2291 | endSignal = BITv06_endOfDStream(&bitD1) & BITv06_endOfDStream(&bitD2) & BITv06_endOfDStream(&bitD3) & BITv06_endOfDStream(&bitD4); | |
2292 | if (!endSignal) return ERROR(corruption_detected); | |
2293 | ||
2294 | /* decoded size */ | |
2295 | return dstSize; | |
2296 | } | |
2297 | } | |
2298 | ||
2299 | ||
2300 | size_t HUFv06_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) | |
2301 | { | |
2302 | HUFv06_CREATE_STATIC_DTABLEX2(DTable, HUFv06_MAX_TABLELOG); | |
2303 | const BYTE* ip = (const BYTE*) cSrc; | |
2304 | ||
2305 | size_t const errorCode = HUFv06_readDTableX2 (DTable, cSrc, cSrcSize); | |
2306 | if (HUFv06_isError(errorCode)) return errorCode; | |
2307 | if (errorCode >= cSrcSize) return ERROR(srcSize_wrong); | |
2308 | ip += errorCode; | |
2309 | cSrcSize -= errorCode; | |
2310 | ||
2311 | return HUFv06_decompress4X2_usingDTable (dst, dstSize, ip, cSrcSize, DTable); | |
2312 | } | |
2313 | ||
2314 | ||
2315 | /* *************************/ | |
2316 | /* double-symbols decoding */ | |
2317 | /* *************************/ | |
2318 | ||
2319 | static void HUFv06_fillDTableX4Level2(HUFv06_DEltX4* DTable, U32 sizeLog, const U32 consumed, | |
2320 | const U32* rankValOrigin, const int minWeight, | |
2321 | const sortedSymbol_t* sortedSymbols, const U32 sortedListSize, | |
2322 | U32 nbBitsBaseline, U16 baseSeq) | |
2323 | { | |
2324 | HUFv06_DEltX4 DElt; | |
2325 | U32 rankVal[HUFv06_ABSOLUTEMAX_TABLELOG + 1]; | |
2326 | ||
2327 | /* get pre-calculated rankVal */ | |
2328 | memcpy(rankVal, rankValOrigin, sizeof(rankVal)); | |
2329 | ||
2330 | /* fill skipped values */ | |
2331 | if (minWeight>1) { | |
2332 | U32 i, skipSize = rankVal[minWeight]; | |
2333 | MEM_writeLE16(&(DElt.sequence), baseSeq); | |
2334 | DElt.nbBits = (BYTE)(consumed); | |
2335 | DElt.length = 1; | |
2336 | for (i = 0; i < skipSize; i++) | |
2337 | DTable[i] = DElt; | |
2338 | } | |
2339 | ||
2340 | /* fill DTable */ | |
2341 | { U32 s; for (s=0; s<sortedListSize; s++) { /* note : sortedSymbols already skipped */ | |
2342 | const U32 symbol = sortedSymbols[s].symbol; | |
2343 | const U32 weight = sortedSymbols[s].weight; | |
2344 | const U32 nbBits = nbBitsBaseline - weight; | |
2345 | const U32 length = 1 << (sizeLog-nbBits); | |
2346 | const U32 start = rankVal[weight]; | |
2347 | U32 i = start; | |
2348 | const U32 end = start + length; | |
2349 | ||
2350 | MEM_writeLE16(&(DElt.sequence), (U16)(baseSeq + (symbol << 8))); | |
2351 | DElt.nbBits = (BYTE)(nbBits + consumed); | |
2352 | DElt.length = 2; | |
2353 | do { DTable[i++] = DElt; } while (i<end); /* since length >= 1 */ | |
2354 | ||
2355 | rankVal[weight] += length; | |
2356 | }} | |
2357 | } | |
2358 | ||
2359 | typedef U32 rankVal_t[HUFv06_ABSOLUTEMAX_TABLELOG][HUFv06_ABSOLUTEMAX_TABLELOG + 1]; | |
2360 | ||
2361 | static void HUFv06_fillDTableX4(HUFv06_DEltX4* DTable, const U32 targetLog, | |
2362 | const sortedSymbol_t* sortedList, const U32 sortedListSize, | |
2363 | const U32* rankStart, rankVal_t rankValOrigin, const U32 maxWeight, | |
2364 | const U32 nbBitsBaseline) | |
2365 | { | |
2366 | U32 rankVal[HUFv06_ABSOLUTEMAX_TABLELOG + 1]; | |
2367 | const int scaleLog = nbBitsBaseline - targetLog; /* note : targetLog >= srcLog, hence scaleLog <= 1 */ | |
2368 | const U32 minBits = nbBitsBaseline - maxWeight; | |
2369 | U32 s; | |
2370 | ||
2371 | memcpy(rankVal, rankValOrigin, sizeof(rankVal)); | |
2372 | ||
2373 | /* fill DTable */ | |
2374 | for (s=0; s<sortedListSize; s++) { | |
2375 | const U16 symbol = sortedList[s].symbol; | |
2376 | const U32 weight = sortedList[s].weight; | |
2377 | const U32 nbBits = nbBitsBaseline - weight; | |
2378 | const U32 start = rankVal[weight]; | |
2379 | const U32 length = 1 << (targetLog-nbBits); | |
2380 | ||
2381 | if (targetLog-nbBits >= minBits) { /* enough room for a second symbol */ | |
2382 | U32 sortedRank; | |
2383 | int minWeight = nbBits + scaleLog; | |
2384 | if (minWeight < 1) minWeight = 1; | |
2385 | sortedRank = rankStart[minWeight]; | |
2386 | HUFv06_fillDTableX4Level2(DTable+start, targetLog-nbBits, nbBits, | |
2387 | rankValOrigin[nbBits], minWeight, | |
2388 | sortedList+sortedRank, sortedListSize-sortedRank, | |
2389 | nbBitsBaseline, symbol); | |
2390 | } else { | |
2391 | HUFv06_DEltX4 DElt; | |
2392 | MEM_writeLE16(&(DElt.sequence), symbol); | |
2393 | DElt.nbBits = (BYTE)(nbBits); | |
2394 | DElt.length = 1; | |
2395 | { U32 u; | |
2396 | const U32 end = start + length; | |
2397 | for (u = start; u < end; u++) DTable[u] = DElt; | |
2398 | } } | |
2399 | rankVal[weight] += length; | |
2400 | } | |
2401 | } | |
2402 | ||
2403 | size_t HUFv06_readDTableX4 (U32* DTable, const void* src, size_t srcSize) | |
2404 | { | |
2405 | BYTE weightList[HUFv06_MAX_SYMBOL_VALUE + 1]; | |
2406 | sortedSymbol_t sortedSymbol[HUFv06_MAX_SYMBOL_VALUE + 1]; | |
2407 | U32 rankStats[HUFv06_ABSOLUTEMAX_TABLELOG + 1] = { 0 }; | |
2408 | U32 rankStart0[HUFv06_ABSOLUTEMAX_TABLELOG + 2] = { 0 }; | |
2409 | U32* const rankStart = rankStart0+1; | |
2410 | rankVal_t rankVal; | |
2411 | U32 tableLog, maxW, sizeOfSort, nbSymbols; | |
2412 | const U32 memLog = DTable[0]; | |
2413 | size_t iSize; | |
2414 | void* dtPtr = DTable; | |
2415 | HUFv06_DEltX4* const dt = ((HUFv06_DEltX4*)dtPtr) + 1; | |
2416 | ||
2417 | HUFv06_STATIC_ASSERT(sizeof(HUFv06_DEltX4) == sizeof(U32)); /* if compilation fails here, assertion is false */ | |
2418 | if (memLog > HUFv06_ABSOLUTEMAX_TABLELOG) return ERROR(tableLog_tooLarge); | |
2419 | //memset(weightList, 0, sizeof(weightList)); /* is not necessary, even though some analyzer complain ... */ | |
2420 | ||
2421 | iSize = HUFv06_readStats(weightList, HUFv06_MAX_SYMBOL_VALUE + 1, rankStats, &nbSymbols, &tableLog, src, srcSize); | |
2422 | if (HUFv06_isError(iSize)) return iSize; | |
2423 | ||
2424 | /* check result */ | |
2425 | if (tableLog > memLog) return ERROR(tableLog_tooLarge); /* DTable can't fit code depth */ | |
2426 | ||
2427 | /* find maxWeight */ | |
2428 | for (maxW = tableLog; rankStats[maxW]==0; maxW--) {} /* necessarily finds a solution before 0 */ | |
2429 | ||
2430 | /* Get start index of each weight */ | |
2431 | { U32 w, nextRankStart = 0; | |
2432 | for (w=1; w<maxW+1; w++) { | |
2433 | U32 current = nextRankStart; | |
2434 | nextRankStart += rankStats[w]; | |
2435 | rankStart[w] = current; | |
2436 | } | |
2437 | rankStart[0] = nextRankStart; /* put all 0w symbols at the end of sorted list*/ | |
2438 | sizeOfSort = nextRankStart; | |
2439 | } | |
2440 | ||
2441 | /* sort symbols by weight */ | |
2442 | { U32 s; | |
2443 | for (s=0; s<nbSymbols; s++) { | |
2444 | U32 const w = weightList[s]; | |
2445 | U32 const r = rankStart[w]++; | |
2446 | sortedSymbol[r].symbol = (BYTE)s; | |
2447 | sortedSymbol[r].weight = (BYTE)w; | |
2448 | } | |
2449 | rankStart[0] = 0; /* forget 0w symbols; this is beginning of weight(1) */ | |
2450 | } | |
2451 | ||
2452 | /* Build rankVal */ | |
2453 | { U32* const rankVal0 = rankVal[0]; | |
2454 | { int const rescale = (memLog-tableLog) - 1; /* tableLog <= memLog */ | |
2455 | U32 nextRankVal = 0; | |
2456 | U32 w; | |
2457 | for (w=1; w<maxW+1; w++) { | |
2458 | U32 current = nextRankVal; | |
2459 | nextRankVal += rankStats[w] << (w+rescale); | |
2460 | rankVal0[w] = current; | |
2461 | } } | |
2462 | { U32 const minBits = tableLog+1 - maxW; | |
2463 | U32 consumed; | |
2464 | for (consumed = minBits; consumed < memLog - minBits + 1; consumed++) { | |
2465 | U32* const rankValPtr = rankVal[consumed]; | |
2466 | U32 w; | |
2467 | for (w = 1; w < maxW+1; w++) { | |
2468 | rankValPtr[w] = rankVal0[w] >> consumed; | |
2469 | } } } } | |
2470 | ||
2471 | HUFv06_fillDTableX4(dt, memLog, | |
2472 | sortedSymbol, sizeOfSort, | |
2473 | rankStart0, rankVal, maxW, | |
2474 | tableLog+1); | |
2475 | ||
2476 | return iSize; | |
2477 | } | |
2478 | ||
2479 | ||
2480 | static U32 HUFv06_decodeSymbolX4(void* op, BITv06_DStream_t* DStream, const HUFv06_DEltX4* dt, const U32 dtLog) | |
2481 | { | |
2482 | const size_t val = BITv06_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */ | |
2483 | memcpy(op, dt+val, 2); | |
2484 | BITv06_skipBits(DStream, dt[val].nbBits); | |
2485 | return dt[val].length; | |
2486 | } | |
2487 | ||
2488 | static U32 HUFv06_decodeLastSymbolX4(void* op, BITv06_DStream_t* DStream, const HUFv06_DEltX4* dt, const U32 dtLog) | |
2489 | { | |
2490 | const size_t val = BITv06_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */ | |
2491 | memcpy(op, dt+val, 1); | |
2492 | if (dt[val].length==1) BITv06_skipBits(DStream, dt[val].nbBits); | |
2493 | else { | |
2494 | if (DStream->bitsConsumed < (sizeof(DStream->bitContainer)*8)) { | |
2495 | BITv06_skipBits(DStream, dt[val].nbBits); | |
2496 | if (DStream->bitsConsumed > (sizeof(DStream->bitContainer)*8)) | |
2497 | DStream->bitsConsumed = (sizeof(DStream->bitContainer)*8); /* ugly hack; works only because it's the last symbol. Note : can't easily extract nbBits from just this symbol */ | |
2498 | } } | |
2499 | return 1; | |
2500 | } | |
2501 | ||
2502 | ||
2503 | #define HUFv06_DECODE_SYMBOLX4_0(ptr, DStreamPtr) \ | |
2504 | ptr += HUFv06_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog) | |
2505 | ||
2506 | #define HUFv06_DECODE_SYMBOLX4_1(ptr, DStreamPtr) \ | |
2507 | if (MEM_64bits() || (HUFv06_MAX_TABLELOG<=12)) \ | |
2508 | ptr += HUFv06_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog) | |
2509 | ||
2510 | #define HUFv06_DECODE_SYMBOLX4_2(ptr, DStreamPtr) \ | |
2511 | if (MEM_64bits()) \ | |
2512 | ptr += HUFv06_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog) | |
2513 | ||
2514 | static inline size_t HUFv06_decodeStreamX4(BYTE* p, BITv06_DStream_t* bitDPtr, BYTE* const pEnd, const HUFv06_DEltX4* const dt, const U32 dtLog) | |
2515 | { | |
2516 | BYTE* const pStart = p; | |
2517 | ||
2518 | /* up to 8 symbols at a time */ | |
2519 | while ((BITv06_reloadDStream(bitDPtr) == BITv06_DStream_unfinished) && (p < pEnd-7)) { | |
2520 | HUFv06_DECODE_SYMBOLX4_2(p, bitDPtr); | |
2521 | HUFv06_DECODE_SYMBOLX4_1(p, bitDPtr); | |
2522 | HUFv06_DECODE_SYMBOLX4_2(p, bitDPtr); | |
2523 | HUFv06_DECODE_SYMBOLX4_0(p, bitDPtr); | |
2524 | } | |
2525 | ||
2526 | /* closer to the end */ | |
2527 | while ((BITv06_reloadDStream(bitDPtr) == BITv06_DStream_unfinished) && (p <= pEnd-2)) | |
2528 | HUFv06_DECODE_SYMBOLX4_0(p, bitDPtr); | |
2529 | ||
2530 | while (p <= pEnd-2) | |
2531 | HUFv06_DECODE_SYMBOLX4_0(p, bitDPtr); /* no need to reload : reached the end of DStream */ | |
2532 | ||
2533 | if (p < pEnd) | |
2534 | p += HUFv06_decodeLastSymbolX4(p, bitDPtr, dt, dtLog); | |
2535 | ||
2536 | return p-pStart; | |
2537 | } | |
2538 | ||
2539 | ||
2540 | size_t HUFv06_decompress1X4_usingDTable( | |
2541 | void* dst, size_t dstSize, | |
2542 | const void* cSrc, size_t cSrcSize, | |
2543 | const U32* DTable) | |
2544 | { | |
2545 | const BYTE* const istart = (const BYTE*) cSrc; | |
2546 | BYTE* const ostart = (BYTE*) dst; | |
2547 | BYTE* const oend = ostart + dstSize; | |
2548 | ||
2549 | const U32 dtLog = DTable[0]; | |
2550 | const void* const dtPtr = DTable; | |
2551 | const HUFv06_DEltX4* const dt = ((const HUFv06_DEltX4*)dtPtr) +1; | |
2552 | ||
2553 | /* Init */ | |
2554 | BITv06_DStream_t bitD; | |
2555 | { size_t const errorCode = BITv06_initDStream(&bitD, istart, cSrcSize); | |
2556 | if (HUFv06_isError(errorCode)) return errorCode; } | |
2557 | ||
2558 | /* decode */ | |
2559 | HUFv06_decodeStreamX4(ostart, &bitD, oend, dt, dtLog); | |
2560 | ||
2561 | /* check */ | |
2562 | if (!BITv06_endOfDStream(&bitD)) return ERROR(corruption_detected); | |
2563 | ||
2564 | /* decoded size */ | |
2565 | return dstSize; | |
2566 | } | |
2567 | ||
2568 | size_t HUFv06_decompress1X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) | |
2569 | { | |
2570 | HUFv06_CREATE_STATIC_DTABLEX4(DTable, HUFv06_MAX_TABLELOG); | |
2571 | const BYTE* ip = (const BYTE*) cSrc; | |
2572 | ||
2573 | size_t const hSize = HUFv06_readDTableX4 (DTable, cSrc, cSrcSize); | |
2574 | if (HUFv06_isError(hSize)) return hSize; | |
2575 | if (hSize >= cSrcSize) return ERROR(srcSize_wrong); | |
2576 | ip += hSize; | |
2577 | cSrcSize -= hSize; | |
2578 | ||
2579 | return HUFv06_decompress1X4_usingDTable (dst, dstSize, ip, cSrcSize, DTable); | |
2580 | } | |
2581 | ||
2582 | size_t HUFv06_decompress4X4_usingDTable( | |
2583 | void* dst, size_t dstSize, | |
2584 | const void* cSrc, size_t cSrcSize, | |
2585 | const U32* DTable) | |
2586 | { | |
2587 | if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */ | |
2588 | ||
2589 | { const BYTE* const istart = (const BYTE*) cSrc; | |
2590 | BYTE* const ostart = (BYTE*) dst; | |
2591 | BYTE* const oend = ostart + dstSize; | |
2592 | const void* const dtPtr = DTable; | |
2593 | const HUFv06_DEltX4* const dt = ((const HUFv06_DEltX4*)dtPtr) +1; | |
2594 | const U32 dtLog = DTable[0]; | |
2595 | size_t errorCode; | |
2596 | ||
2597 | /* Init */ | |
2598 | BITv06_DStream_t bitD1; | |
2599 | BITv06_DStream_t bitD2; | |
2600 | BITv06_DStream_t bitD3; | |
2601 | BITv06_DStream_t bitD4; | |
2602 | const size_t length1 = MEM_readLE16(istart); | |
2603 | const size_t length2 = MEM_readLE16(istart+2); | |
2604 | const size_t length3 = MEM_readLE16(istart+4); | |
2605 | size_t length4; | |
2606 | const BYTE* const istart1 = istart + 6; /* jumpTable */ | |
2607 | const BYTE* const istart2 = istart1 + length1; | |
2608 | const BYTE* const istart3 = istart2 + length2; | |
2609 | const BYTE* const istart4 = istart3 + length3; | |
2610 | const size_t segmentSize = (dstSize+3) / 4; | |
2611 | BYTE* const opStart2 = ostart + segmentSize; | |
2612 | BYTE* const opStart3 = opStart2 + segmentSize; | |
2613 | BYTE* const opStart4 = opStart3 + segmentSize; | |
2614 | BYTE* op1 = ostart; | |
2615 | BYTE* op2 = opStart2; | |
2616 | BYTE* op3 = opStart3; | |
2617 | BYTE* op4 = opStart4; | |
2618 | U32 endSignal; | |
2619 | ||
2620 | length4 = cSrcSize - (length1 + length2 + length3 + 6); | |
2621 | if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */ | |
2622 | errorCode = BITv06_initDStream(&bitD1, istart1, length1); | |
2623 | if (HUFv06_isError(errorCode)) return errorCode; | |
2624 | errorCode = BITv06_initDStream(&bitD2, istart2, length2); | |
2625 | if (HUFv06_isError(errorCode)) return errorCode; | |
2626 | errorCode = BITv06_initDStream(&bitD3, istart3, length3); | |
2627 | if (HUFv06_isError(errorCode)) return errorCode; | |
2628 | errorCode = BITv06_initDStream(&bitD4, istart4, length4); | |
2629 | if (HUFv06_isError(errorCode)) return errorCode; | |
2630 | ||
2631 | /* 16-32 symbols per loop (4-8 symbols per stream) */ | |
2632 | endSignal = BITv06_reloadDStream(&bitD1) | BITv06_reloadDStream(&bitD2) | BITv06_reloadDStream(&bitD3) | BITv06_reloadDStream(&bitD4); | |
2633 | for ( ; (endSignal==BITv06_DStream_unfinished) && (op4<(oend-7)) ; ) { | |
2634 | HUFv06_DECODE_SYMBOLX4_2(op1, &bitD1); | |
2635 | HUFv06_DECODE_SYMBOLX4_2(op2, &bitD2); | |
2636 | HUFv06_DECODE_SYMBOLX4_2(op3, &bitD3); | |
2637 | HUFv06_DECODE_SYMBOLX4_2(op4, &bitD4); | |
2638 | HUFv06_DECODE_SYMBOLX4_1(op1, &bitD1); | |
2639 | HUFv06_DECODE_SYMBOLX4_1(op2, &bitD2); | |
2640 | HUFv06_DECODE_SYMBOLX4_1(op3, &bitD3); | |
2641 | HUFv06_DECODE_SYMBOLX4_1(op4, &bitD4); | |
2642 | HUFv06_DECODE_SYMBOLX4_2(op1, &bitD1); | |
2643 | HUFv06_DECODE_SYMBOLX4_2(op2, &bitD2); | |
2644 | HUFv06_DECODE_SYMBOLX4_2(op3, &bitD3); | |
2645 | HUFv06_DECODE_SYMBOLX4_2(op4, &bitD4); | |
2646 | HUFv06_DECODE_SYMBOLX4_0(op1, &bitD1); | |
2647 | HUFv06_DECODE_SYMBOLX4_0(op2, &bitD2); | |
2648 | HUFv06_DECODE_SYMBOLX4_0(op3, &bitD3); | |
2649 | HUFv06_DECODE_SYMBOLX4_0(op4, &bitD4); | |
2650 | ||
2651 | endSignal = BITv06_reloadDStream(&bitD1) | BITv06_reloadDStream(&bitD2) | BITv06_reloadDStream(&bitD3) | BITv06_reloadDStream(&bitD4); | |
2652 | } | |
2653 | ||
2654 | /* check corruption */ | |
2655 | if (op1 > opStart2) return ERROR(corruption_detected); | |
2656 | if (op2 > opStart3) return ERROR(corruption_detected); | |
2657 | if (op3 > opStart4) return ERROR(corruption_detected); | |
2658 | /* note : op4 supposed already verified within main loop */ | |
2659 | ||
2660 | /* finish bitStreams one by one */ | |
2661 | HUFv06_decodeStreamX4(op1, &bitD1, opStart2, dt, dtLog); | |
2662 | HUFv06_decodeStreamX4(op2, &bitD2, opStart3, dt, dtLog); | |
2663 | HUFv06_decodeStreamX4(op3, &bitD3, opStart4, dt, dtLog); | |
2664 | HUFv06_decodeStreamX4(op4, &bitD4, oend, dt, dtLog); | |
2665 | ||
2666 | /* check */ | |
2667 | endSignal = BITv06_endOfDStream(&bitD1) & BITv06_endOfDStream(&bitD2) & BITv06_endOfDStream(&bitD3) & BITv06_endOfDStream(&bitD4); | |
2668 | if (!endSignal) return ERROR(corruption_detected); | |
2669 | ||
2670 | /* decoded size */ | |
2671 | return dstSize; | |
2672 | } | |
2673 | } | |
2674 | ||
2675 | ||
2676 | size_t HUFv06_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) | |
2677 | { | |
2678 | HUFv06_CREATE_STATIC_DTABLEX4(DTable, HUFv06_MAX_TABLELOG); | |
2679 | const BYTE* ip = (const BYTE*) cSrc; | |
2680 | ||
2681 | size_t hSize = HUFv06_readDTableX4 (DTable, cSrc, cSrcSize); | |
2682 | if (HUFv06_isError(hSize)) return hSize; | |
2683 | if (hSize >= cSrcSize) return ERROR(srcSize_wrong); | |
2684 | ip += hSize; | |
2685 | cSrcSize -= hSize; | |
2686 | ||
2687 | return HUFv06_decompress4X4_usingDTable (dst, dstSize, ip, cSrcSize, DTable); | |
2688 | } | |
2689 | ||
2690 | ||
2691 | ||
2692 | ||
2693 | /* ********************************/ | |
2694 | /* Generic decompression selector */ | |
2695 | /* ********************************/ | |
2696 | ||
2697 | typedef struct { U32 tableTime; U32 decode256Time; } algo_time_t; | |
2698 | static const algo_time_t algoTime[16 /* Quantization */][3 /* single, double, quad */] = | |
2699 | { | |
2700 | /* single, double, quad */ | |
2701 | {{0,0}, {1,1}, {2,2}}, /* Q==0 : impossible */ | |
2702 | {{0,0}, {1,1}, {2,2}}, /* Q==1 : impossible */ | |
2703 | {{ 38,130}, {1313, 74}, {2151, 38}}, /* Q == 2 : 12-18% */ | |
2704 | {{ 448,128}, {1353, 74}, {2238, 41}}, /* Q == 3 : 18-25% */ | |
2705 | {{ 556,128}, {1353, 74}, {2238, 47}}, /* Q == 4 : 25-32% */ | |
2706 | {{ 714,128}, {1418, 74}, {2436, 53}}, /* Q == 5 : 32-38% */ | |
2707 | {{ 883,128}, {1437, 74}, {2464, 61}}, /* Q == 6 : 38-44% */ | |
2708 | {{ 897,128}, {1515, 75}, {2622, 68}}, /* Q == 7 : 44-50% */ | |
2709 | {{ 926,128}, {1613, 75}, {2730, 75}}, /* Q == 8 : 50-56% */ | |
2710 | {{ 947,128}, {1729, 77}, {3359, 77}}, /* Q == 9 : 56-62% */ | |
2711 | {{1107,128}, {2083, 81}, {4006, 84}}, /* Q ==10 : 62-69% */ | |
2712 | {{1177,128}, {2379, 87}, {4785, 88}}, /* Q ==11 : 69-75% */ | |
2713 | {{1242,128}, {2415, 93}, {5155, 84}}, /* Q ==12 : 75-81% */ | |
2714 | {{1349,128}, {2644,106}, {5260,106}}, /* Q ==13 : 81-87% */ | |
2715 | {{1455,128}, {2422,124}, {4174,124}}, /* Q ==14 : 87-93% */ | |
2716 | {{ 722,128}, {1891,145}, {1936,146}}, /* Q ==15 : 93-99% */ | |
2717 | }; | |
2718 | ||
2719 | typedef size_t (*decompressionAlgo)(void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); | |
2720 | ||
2721 | size_t HUFv06_decompress (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize) | |
2722 | { | |
2723 | static const decompressionAlgo decompress[3] = { HUFv06_decompress4X2, HUFv06_decompress4X4, NULL }; | |
2724 | U32 Dtime[3]; /* decompression time estimation */ | |
2725 | ||
2726 | /* validation checks */ | |
2727 | if (dstSize == 0) return ERROR(dstSize_tooSmall); | |
2728 | if (cSrcSize > dstSize) return ERROR(corruption_detected); /* invalid */ | |
2729 | if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; } /* not compressed */ | |
2730 | if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */ | |
2731 | ||
2732 | /* decoder timing evaluation */ | |
2733 | { U32 const Q = (U32)(cSrcSize * 16 / dstSize); /* Q < 16 since dstSize > cSrcSize */ | |
2734 | U32 const D256 = (U32)(dstSize >> 8); | |
2735 | U32 n; for (n=0; n<3; n++) | |
2736 | Dtime[n] = algoTime[Q][n].tableTime + (algoTime[Q][n].decode256Time * D256); | |
2737 | } | |
2738 | ||
2739 | Dtime[1] += Dtime[1] >> 4; Dtime[2] += Dtime[2] >> 3; /* advantage to algorithms using less memory, for cache eviction */ | |
2740 | ||
2741 | { U32 algoNb = 0; | |
2742 | if (Dtime[1] < Dtime[0]) algoNb = 1; | |
2743 | // if (Dtime[2] < Dtime[algoNb]) algoNb = 2; /* current speed of HUFv06_decompress4X6 is not good */ | |
2744 | return decompress[algoNb](dst, dstSize, cSrc, cSrcSize); | |
2745 | } | |
2746 | ||
2747 | //return HUFv06_decompress4X2(dst, dstSize, cSrc, cSrcSize); /* multi-streams single-symbol decoding */ | |
2748 | //return HUFv06_decompress4X4(dst, dstSize, cSrc, cSrcSize); /* multi-streams double-symbols decoding */ | |
2749 | //return HUFv06_decompress4X6(dst, dstSize, cSrc, cSrcSize); /* multi-streams quad-symbols decoding */ | |
2750 | } | |
2751 | /* | |
2752 | Common functions of Zstd compression library | |
2753 | Copyright (C) 2015-2016, Yann Collet. | |
2754 | ||
2755 | BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) | |
2756 | ||
2757 | Redistribution and use in source and binary forms, with or without | |
2758 | modification, are permitted provided that the following conditions are | |
2759 | met: | |
2760 | * Redistributions of source code must retain the above copyright | |
2761 | notice, this list of conditions and the following disclaimer. | |
2762 | * Redistributions in binary form must reproduce the above | |
2763 | copyright notice, this list of conditions and the following disclaimer | |
2764 | in the documentation and/or other materials provided with the | |
2765 | distribution. | |
2766 | THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
2767 | "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
2768 | LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | |
2769 | A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | |
2770 | OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
2771 | SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | |
2772 | LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
2773 | DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |
2774 | THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
2775 | (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
2776 | OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
2777 | ||
2778 | You can contact the author at : | |
2779 | - zstd homepage : http://www.zstd.net/ | |
2780 | */ | |
2781 | ||
2782 | ||
2783 | /*-**************************************** | |
2784 | * Version | |
2785 | ******************************************/ | |
2786 | ||
2787 | /*-**************************************** | |
2788 | * ZSTD Error Management | |
2789 | ******************************************/ | |
2790 | /*! ZSTDv06_isError() : | |
2791 | * tells if a return value is an error code */ | |
2792 | unsigned ZSTDv06_isError(size_t code) { return ERR_isError(code); } | |
2793 | ||
2794 | /*! ZSTDv06_getErrorName() : | |
2795 | * provides error code string from function result (useful for debugging) */ | |
2796 | const char* ZSTDv06_getErrorName(size_t code) { return ERR_getErrorName(code); } | |
2797 | ||
2798 | ||
2799 | /* ************************************************************** | |
2800 | * ZBUFF Error Management | |
2801 | ****************************************************************/ | |
2802 | unsigned ZBUFFv06_isError(size_t errorCode) { return ERR_isError(errorCode); } | |
2803 | ||
2804 | const char* ZBUFFv06_getErrorName(size_t errorCode) { return ERR_getErrorName(errorCode); } | |
2805 | /* | |
2806 | zstd - standard compression library | |
2807 | Copyright (C) 2014-2016, Yann Collet. | |
2808 | ||
2809 | BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) | |
2810 | ||
2811 | Redistribution and use in source and binary forms, with or without | |
2812 | modification, are permitted provided that the following conditions are | |
2813 | met: | |
2814 | * Redistributions of source code must retain the above copyright | |
2815 | notice, this list of conditions and the following disclaimer. | |
2816 | * Redistributions in binary form must reproduce the above | |
2817 | copyright notice, this list of conditions and the following disclaimer | |
2818 | in the documentation and/or other materials provided with the | |
2819 | distribution. | |
2820 | THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
2821 | "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
2822 | LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | |
2823 | A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | |
2824 | OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
2825 | SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | |
2826 | LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
2827 | DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |
2828 | THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
2829 | (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
2830 | OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
2831 | ||
2832 | You can contact the author at : | |
2833 | - zstd homepage : http://www.zstd.net | |
2834 | */ | |
2835 | ||
2836 | /* *************************************************************** | |
2837 | * Tuning parameters | |
2838 | *****************************************************************/ | |
2839 | /*! | |
2840 | * HEAPMODE : | |
2841 | * Select how default decompression function ZSTDv06_decompress() will allocate memory, | |
2842 | * in memory stack (0), or in memory heap (1, requires malloc()) | |
2843 | */ | |
2844 | #ifndef ZSTDv06_HEAPMODE | |
2845 | # define ZSTDv06_HEAPMODE 1 | |
2846 | #endif | |
2847 | ||
2848 | ||
2849 | ||
2850 | /*-******************************************************* | |
2851 | * Compiler specifics | |
2852 | *********************************************************/ | |
2853 | #ifdef _MSC_VER /* Visual Studio */ | |
2854 | # include <intrin.h> /* For Visual 2005 */ | |
2855 | # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ | |
2856 | # pragma warning(disable : 4324) /* disable: C4324: padded structure */ | |
2857 | #endif | |
2858 | ||
2859 | ||
2860 | /*-************************************* | |
2861 | * Macros | |
2862 | ***************************************/ | |
2863 | #define ZSTDv06_isError ERR_isError /* for inlining */ | |
2864 | #define FSEv06_isError ERR_isError | |
2865 | #define HUFv06_isError ERR_isError | |
2866 | ||
2867 | ||
2868 | /*_******************************************************* | |
2869 | * Memory operations | |
2870 | **********************************************************/ | |
2871 | static void ZSTDv06_copy4(void* dst, const void* src) { memcpy(dst, src, 4); } | |
2872 | ||
2873 | ||
2874 | /*-************************************************************* | |
2875 | * Context management | |
2876 | ***************************************************************/ | |
2877 | typedef enum { ZSTDds_getFrameHeaderSize, ZSTDds_decodeFrameHeader, | |
2878 | ZSTDds_decodeBlockHeader, ZSTDds_decompressBlock } ZSTDv06_dStage; | |
2879 | ||
2880 | struct ZSTDv06_DCtx_s | |
2881 | { | |
2882 | FSEv06_DTable LLTable[FSEv06_DTABLE_SIZE_U32(LLFSELog)]; | |
2883 | FSEv06_DTable OffTable[FSEv06_DTABLE_SIZE_U32(OffFSELog)]; | |
2884 | FSEv06_DTable MLTable[FSEv06_DTABLE_SIZE_U32(MLFSELog)]; | |
2885 | unsigned hufTableX4[HUFv06_DTABLE_SIZE(HufLog)]; | |
2886 | const void* previousDstEnd; | |
2887 | const void* base; | |
2888 | const void* vBase; | |
2889 | const void* dictEnd; | |
2890 | size_t expected; | |
2891 | size_t headerSize; | |
2892 | ZSTDv06_frameParams fParams; | |
2893 | blockType_t bType; /* used in ZSTDv06_decompressContinue(), to transfer blockType between header decoding and block decoding stages */ | |
2894 | ZSTDv06_dStage stage; | |
2895 | U32 flagRepeatTable; | |
2896 | const BYTE* litPtr; | |
2897 | size_t litSize; | |
2898 | BYTE litBuffer[ZSTDv06_BLOCKSIZE_MAX + WILDCOPY_OVERLENGTH]; | |
2899 | BYTE headerBuffer[ZSTDv06_FRAMEHEADERSIZE_MAX]; | |
2900 | }; /* typedef'd to ZSTDv06_DCtx within "zstd_static.h" */ | |
2901 | ||
2902 | size_t ZSTDv06_sizeofDCtx (void) { return sizeof(ZSTDv06_DCtx); } /* non published interface */ | |
2903 | ||
2904 | size_t ZSTDv06_decompressBegin(ZSTDv06_DCtx* dctx) | |
2905 | { | |
2906 | dctx->expected = ZSTDv06_frameHeaderSize_min; | |
2907 | dctx->stage = ZSTDds_getFrameHeaderSize; | |
2908 | dctx->previousDstEnd = NULL; | |
2909 | dctx->base = NULL; | |
2910 | dctx->vBase = NULL; | |
2911 | dctx->dictEnd = NULL; | |
2912 | dctx->hufTableX4[0] = HufLog; | |
2913 | dctx->flagRepeatTable = 0; | |
2914 | return 0; | |
2915 | } | |
2916 | ||
2917 | ZSTDv06_DCtx* ZSTDv06_createDCtx(void) | |
2918 | { | |
2919 | ZSTDv06_DCtx* dctx = (ZSTDv06_DCtx*)malloc(sizeof(ZSTDv06_DCtx)); | |
2920 | if (dctx==NULL) return NULL; | |
2921 | ZSTDv06_decompressBegin(dctx); | |
2922 | return dctx; | |
2923 | } | |
2924 | ||
2925 | size_t ZSTDv06_freeDCtx(ZSTDv06_DCtx* dctx) | |
2926 | { | |
2927 | free(dctx); | |
2928 | return 0; /* reserved as a potential error code in the future */ | |
2929 | } | |
2930 | ||
2931 | void ZSTDv06_copyDCtx(ZSTDv06_DCtx* dstDCtx, const ZSTDv06_DCtx* srcDCtx) | |
2932 | { | |
2933 | memcpy(dstDCtx, srcDCtx, | |
2934 | sizeof(ZSTDv06_DCtx) - (ZSTDv06_BLOCKSIZE_MAX+WILDCOPY_OVERLENGTH + ZSTDv06_frameHeaderSize_max)); /* no need to copy workspace */ | |
2935 | } | |
2936 | ||
2937 | ||
2938 | /*-************************************************************* | |
2939 | * Decompression section | |
2940 | ***************************************************************/ | |
2941 | ||
2942 | /* Frame format description | |
2943 | Frame Header - [ Block Header - Block ] - Frame End | |
2944 | 1) Frame Header | |
2945 | - 4 bytes - Magic Number : ZSTDv06_MAGICNUMBER (defined within zstd_static.h) | |
2946 | - 1 byte - Frame Descriptor | |
2947 | 2) Block Header | |
2948 | - 3 bytes, starting with a 2-bits descriptor | |
2949 | Uncompressed, Compressed, Frame End, unused | |
2950 | 3) Block | |
2951 | See Block Format Description | |
2952 | 4) Frame End | |
2953 | - 3 bytes, compatible with Block Header | |
2954 | */ | |
2955 | ||
2956 | ||
2957 | /* Frame descriptor | |
2958 | ||
2959 | 1 byte, using : | |
2960 | bit 0-3 : windowLog - ZSTDv06_WINDOWLOG_ABSOLUTEMIN (see zstd_internal.h) | |
2961 | bit 4 : minmatch 4(0) or 3(1) | |
2962 | bit 5 : reserved (must be zero) | |
2963 | bit 6-7 : Frame content size : unknown, 1 byte, 2 bytes, 8 bytes | |
2964 | ||
2965 | Optional : content size (0, 1, 2 or 8 bytes) | |
2966 | 0 : unknown | |
2967 | 1 : 0-255 bytes | |
2968 | 2 : 256 - 65535+256 | |
2969 | 8 : up to 16 exa | |
2970 | */ | |
2971 | ||
2972 | ||
2973 | /* Compressed Block, format description | |
2974 | ||
2975 | Block = Literal Section - Sequences Section | |
2976 | Prerequisite : size of (compressed) block, maximum size of regenerated data | |
2977 | ||
2978 | 1) Literal Section | |
2979 | ||
2980 | 1.1) Header : 1-5 bytes | |
2981 | flags: 2 bits | |
2982 | 00 compressed by Huff0 | |
2983 | 01 unused | |
2984 | 10 is Raw (uncompressed) | |
2985 | 11 is Rle | |
2986 | Note : using 01 => Huff0 with precomputed table ? | |
2987 | Note : delta map ? => compressed ? | |
2988 | ||
2989 | 1.1.1) Huff0-compressed literal block : 3-5 bytes | |
2990 | srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream | |
2991 | srcSize < 1 KB => 3 bytes (2-2-10-10) | |
2992 | srcSize < 16KB => 4 bytes (2-2-14-14) | |
2993 | else => 5 bytes (2-2-18-18) | |
2994 | big endian convention | |
2995 | ||
2996 | 1.1.2) Raw (uncompressed) literal block header : 1-3 bytes | |
2997 | size : 5 bits: (IS_RAW<<6) + (0<<4) + size | |
2998 | 12 bits: (IS_RAW<<6) + (2<<4) + (size>>8) | |
2999 | size&255 | |
3000 | 20 bits: (IS_RAW<<6) + (3<<4) + (size>>16) | |
3001 | size>>8&255 | |
3002 | size&255 | |
3003 | ||
3004 | 1.1.3) Rle (repeated single byte) literal block header : 1-3 bytes | |
3005 | size : 5 bits: (IS_RLE<<6) + (0<<4) + size | |
3006 | 12 bits: (IS_RLE<<6) + (2<<4) + (size>>8) | |
3007 | size&255 | |
3008 | 20 bits: (IS_RLE<<6) + (3<<4) + (size>>16) | |
3009 | size>>8&255 | |
3010 | size&255 | |
3011 | ||
3012 | 1.1.4) Huff0-compressed literal block, using precomputed CTables : 3-5 bytes | |
3013 | srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream | |
3014 | srcSize < 1 KB => 3 bytes (2-2-10-10) | |
3015 | srcSize < 16KB => 4 bytes (2-2-14-14) | |
3016 | else => 5 bytes (2-2-18-18) | |
3017 | big endian convention | |
3018 | ||
3019 | 1- CTable available (stored into workspace ?) | |
3020 | 2- Small input (fast heuristic ? Full comparison ? depend on clevel ?) | |
3021 | ||
3022 | ||
3023 | 1.2) Literal block content | |
3024 | ||
3025 | 1.2.1) Huff0 block, using sizes from header | |
3026 | See Huff0 format | |
3027 | ||
3028 | 1.2.2) Huff0 block, using prepared table | |
3029 | ||
3030 | 1.2.3) Raw content | |
3031 | ||
3032 | 1.2.4) single byte | |
3033 | ||
3034 | ||
3035 | 2) Sequences section | |
3036 | TO DO | |
3037 | */ | |
3038 | ||
3039 | /** ZSTDv06_frameHeaderSize() : | |
3040 | * srcSize must be >= ZSTDv06_frameHeaderSize_min. | |
3041 | * @return : size of the Frame Header */ | |
3042 | static size_t ZSTDv06_frameHeaderSize(const void* src, size_t srcSize) | |
3043 | { | |
3044 | if (srcSize < ZSTDv06_frameHeaderSize_min) return ERROR(srcSize_wrong); | |
3045 | { U32 const fcsId = (((const BYTE*)src)[4]) >> 6; | |
3046 | return ZSTDv06_frameHeaderSize_min + ZSTDv06_fcs_fieldSize[fcsId]; } | |
3047 | } | |
3048 | ||
3049 | ||
3050 | /** ZSTDv06_getFrameParams() : | |
3051 | * decode Frame Header, or provide expected `srcSize`. | |
3052 | * @return : 0, `fparamsPtr` is correctly filled, | |
3053 | * >0, `srcSize` is too small, result is expected `srcSize`, | |
3054 | * or an error code, which can be tested using ZSTDv06_isError() */ | |
3055 | size_t ZSTDv06_getFrameParams(ZSTDv06_frameParams* fparamsPtr, const void* src, size_t srcSize) | |
3056 | { | |
3057 | const BYTE* ip = (const BYTE*)src; | |
3058 | ||
3059 | if (srcSize < ZSTDv06_frameHeaderSize_min) return ZSTDv06_frameHeaderSize_min; | |
3060 | if (MEM_readLE32(src) != ZSTDv06_MAGICNUMBER) return ERROR(prefix_unknown); | |
3061 | ||
3062 | /* ensure there is enough `srcSize` to fully read/decode frame header */ | |
3063 | { size_t const fhsize = ZSTDv06_frameHeaderSize(src, srcSize); | |
3064 | if (srcSize < fhsize) return fhsize; } | |
3065 | ||
3066 | memset(fparamsPtr, 0, sizeof(*fparamsPtr)); | |
3067 | { BYTE const frameDesc = ip[4]; | |
3068 | fparamsPtr->windowLog = (frameDesc & 0xF) + ZSTDv06_WINDOWLOG_ABSOLUTEMIN; | |
3069 | if ((frameDesc & 0x20) != 0) return ERROR(frameParameter_unsupported); /* reserved 1 bit */ | |
3070 | switch(frameDesc >> 6) /* fcsId */ | |
3071 | { | |
3072 | default: /* impossible */ | |
3073 | case 0 : fparamsPtr->frameContentSize = 0; break; | |
3074 | case 1 : fparamsPtr->frameContentSize = ip[5]; break; | |
3075 | case 2 : fparamsPtr->frameContentSize = MEM_readLE16(ip+5)+256; break; | |
3076 | case 3 : fparamsPtr->frameContentSize = MEM_readLE64(ip+5); break; | |
3077 | } } | |
3078 | return 0; | |
3079 | } | |
3080 | ||
3081 | ||
3082 | /** ZSTDv06_decodeFrameHeader() : | |
3083 | * `srcSize` must be the size provided by ZSTDv06_frameHeaderSize(). | |
3084 | * @return : 0 if success, or an error code, which can be tested using ZSTDv06_isError() */ | |
3085 | static size_t ZSTDv06_decodeFrameHeader(ZSTDv06_DCtx* zc, const void* src, size_t srcSize) | |
3086 | { | |
3087 | size_t const result = ZSTDv06_getFrameParams(&(zc->fParams), src, srcSize); | |
11fdf7f2 | 3088 | if ((MEM_32bits()) && (zc->fParams.windowLog > 25)) return ERROR(frameParameter_unsupported); |
7c673cae FG |
3089 | return result; |
3090 | } | |
3091 | ||
3092 | ||
3093 | typedef struct | |
3094 | { | |
3095 | blockType_t blockType; | |
3096 | U32 origSize; | |
3097 | } blockProperties_t; | |
3098 | ||
3099 | /*! ZSTDv06_getcBlockSize() : | |
3100 | * Provides the size of compressed block from block header `src` */ | |
3101 | size_t ZSTDv06_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr) | |
3102 | { | |
3103 | const BYTE* const in = (const BYTE* const)src; | |
3104 | U32 cSize; | |
3105 | ||
3106 | if (srcSize < ZSTDv06_blockHeaderSize) return ERROR(srcSize_wrong); | |
3107 | ||
3108 | bpPtr->blockType = (blockType_t)((*in) >> 6); | |
3109 | cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16); | |
3110 | bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0; | |
3111 | ||
3112 | if (bpPtr->blockType == bt_end) return 0; | |
3113 | if (bpPtr->blockType == bt_rle) return 1; | |
3114 | return cSize; | |
3115 | } | |
3116 | ||
3117 | ||
3118 | static size_t ZSTDv06_copyRawBlock(void* dst, size_t dstCapacity, const void* src, size_t srcSize) | |
3119 | { | |
3120 | if (srcSize > dstCapacity) return ERROR(dstSize_tooSmall); | |
3121 | memcpy(dst, src, srcSize); | |
3122 | return srcSize; | |
3123 | } | |
3124 | ||
3125 | ||
3126 | /*! ZSTDv06_decodeLiteralsBlock() : | |
3127 | @return : nb of bytes read from src (< srcSize ) */ | |
3128 | size_t ZSTDv06_decodeLiteralsBlock(ZSTDv06_DCtx* dctx, | |
3129 | const void* src, size_t srcSize) /* note : srcSize < BLOCKSIZE */ | |
3130 | { | |
3131 | const BYTE* const istart = (const BYTE*) src; | |
3132 | ||
3133 | /* any compressed block with literals segment must be at least this size */ | |
3134 | if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected); | |
3135 | ||
3136 | switch(istart[0]>> 6) | |
3137 | { | |
3138 | case IS_HUF: | |
3139 | { size_t litSize, litCSize, singleStream=0; | |
3140 | U32 lhSize = ((istart[0]) >> 4) & 3; | |
3141 | if (srcSize < 5) return ERROR(corruption_detected); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need up to 5 for lhSize, + cSize (+nbSeq) */ | |
3142 | switch(lhSize) | |
3143 | { | |
3144 | case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */ | |
3145 | /* 2 - 2 - 10 - 10 */ | |
3146 | lhSize=3; | |
3147 | singleStream = istart[0] & 16; | |
3148 | litSize = ((istart[0] & 15) << 6) + (istart[1] >> 2); | |
3149 | litCSize = ((istart[1] & 3) << 8) + istart[2]; | |
3150 | break; | |
3151 | case 2: | |
3152 | /* 2 - 2 - 14 - 14 */ | |
3153 | lhSize=4; | |
3154 | litSize = ((istart[0] & 15) << 10) + (istart[1] << 2) + (istart[2] >> 6); | |
3155 | litCSize = ((istart[2] & 63) << 8) + istart[3]; | |
3156 | break; | |
3157 | case 3: | |
3158 | /* 2 - 2 - 18 - 18 */ | |
3159 | lhSize=5; | |
3160 | litSize = ((istart[0] & 15) << 14) + (istart[1] << 6) + (istart[2] >> 2); | |
3161 | litCSize = ((istart[2] & 3) << 16) + (istart[3] << 8) + istart[4]; | |
3162 | break; | |
3163 | } | |
3164 | if (litSize > ZSTDv06_BLOCKSIZE_MAX) return ERROR(corruption_detected); | |
3165 | if (litCSize + lhSize > srcSize) return ERROR(corruption_detected); | |
3166 | ||
3167 | if (HUFv06_isError(singleStream ? | |
3168 | HUFv06_decompress1X2(dctx->litBuffer, litSize, istart+lhSize, litCSize) : | |
3169 | HUFv06_decompress (dctx->litBuffer, litSize, istart+lhSize, litCSize) )) | |
3170 | return ERROR(corruption_detected); | |
3171 | ||
3172 | dctx->litPtr = dctx->litBuffer; | |
3173 | dctx->litSize = litSize; | |
3174 | memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH); | |
3175 | return litCSize + lhSize; | |
3176 | } | |
3177 | case IS_PCH: | |
3178 | { size_t litSize, litCSize; | |
3179 | U32 lhSize = ((istart[0]) >> 4) & 3; | |
3180 | if (lhSize != 1) /* only case supported for now : small litSize, single stream */ | |
3181 | return ERROR(corruption_detected); | |
3182 | if (!dctx->flagRepeatTable) | |
3183 | return ERROR(dictionary_corrupted); | |
3184 | ||
3185 | /* 2 - 2 - 10 - 10 */ | |
3186 | lhSize=3; | |
3187 | litSize = ((istart[0] & 15) << 6) + (istart[1] >> 2); | |
3188 | litCSize = ((istart[1] & 3) << 8) + istart[2]; | |
3189 | if (litCSize + lhSize > srcSize) return ERROR(corruption_detected); | |
3190 | ||
3191 | { size_t const errorCode = HUFv06_decompress1X4_usingDTable(dctx->litBuffer, litSize, istart+lhSize, litCSize, dctx->hufTableX4); | |
3192 | if (HUFv06_isError(errorCode)) return ERROR(corruption_detected); | |
3193 | } | |
3194 | dctx->litPtr = dctx->litBuffer; | |
3195 | dctx->litSize = litSize; | |
3196 | memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH); | |
3197 | return litCSize + lhSize; | |
3198 | } | |
3199 | case IS_RAW: | |
3200 | { size_t litSize; | |
3201 | U32 lhSize = ((istart[0]) >> 4) & 3; | |
3202 | switch(lhSize) | |
3203 | { | |
3204 | case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */ | |
3205 | lhSize=1; | |
3206 | litSize = istart[0] & 31; | |
3207 | break; | |
3208 | case 2: | |
3209 | litSize = ((istart[0] & 15) << 8) + istart[1]; | |
3210 | break; | |
3211 | case 3: | |
3212 | litSize = ((istart[0] & 15) << 16) + (istart[1] << 8) + istart[2]; | |
3213 | break; | |
3214 | } | |
3215 | ||
3216 | if (lhSize+litSize+WILDCOPY_OVERLENGTH > srcSize) { /* risk reading beyond src buffer with wildcopy */ | |
3217 | if (litSize+lhSize > srcSize) return ERROR(corruption_detected); | |
3218 | memcpy(dctx->litBuffer, istart+lhSize, litSize); | |
3219 | dctx->litPtr = dctx->litBuffer; | |
3220 | dctx->litSize = litSize; | |
3221 | memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH); | |
3222 | return lhSize+litSize; | |
3223 | } | |
3224 | /* direct reference into compressed stream */ | |
3225 | dctx->litPtr = istart+lhSize; | |
3226 | dctx->litSize = litSize; | |
3227 | return lhSize+litSize; | |
3228 | } | |
3229 | case IS_RLE: | |
3230 | { size_t litSize; | |
3231 | U32 lhSize = ((istart[0]) >> 4) & 3; | |
3232 | switch(lhSize) | |
3233 | { | |
3234 | case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */ | |
3235 | lhSize = 1; | |
3236 | litSize = istart[0] & 31; | |
3237 | break; | |
3238 | case 2: | |
3239 | litSize = ((istart[0] & 15) << 8) + istart[1]; | |
3240 | break; | |
3241 | case 3: | |
3242 | litSize = ((istart[0] & 15) << 16) + (istart[1] << 8) + istart[2]; | |
3243 | if (srcSize<4) return ERROR(corruption_detected); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need lhSize+1 = 4 */ | |
3244 | break; | |
3245 | } | |
3246 | if (litSize > ZSTDv06_BLOCKSIZE_MAX) return ERROR(corruption_detected); | |
3247 | memset(dctx->litBuffer, istart[lhSize], litSize + WILDCOPY_OVERLENGTH); | |
3248 | dctx->litPtr = dctx->litBuffer; | |
3249 | dctx->litSize = litSize; | |
3250 | return lhSize+1; | |
3251 | } | |
3252 | default: | |
3253 | return ERROR(corruption_detected); /* impossible */ | |
3254 | } | |
3255 | } | |
3256 | ||
3257 | ||
3258 | /*! ZSTDv06_buildSeqTable() : | |
3259 | @return : nb bytes read from src, | |
3260 | or an error code if it fails, testable with ZSTDv06_isError() | |
3261 | */ | |
3262 | size_t ZSTDv06_buildSeqTable(FSEv06_DTable* DTable, U32 type, U32 max, U32 maxLog, | |
3263 | const void* src, size_t srcSize, | |
3264 | const S16* defaultNorm, U32 defaultLog, U32 flagRepeatTable) | |
3265 | { | |
3266 | switch(type) | |
3267 | { | |
3268 | case FSEv06_ENCODING_RLE : | |
3269 | if (!srcSize) return ERROR(srcSize_wrong); | |
3270 | if ( (*(const BYTE*)src) > max) return ERROR(corruption_detected); | |
3271 | FSEv06_buildDTable_rle(DTable, *(const BYTE*)src); /* if *src > max, data is corrupted */ | |
3272 | return 1; | |
3273 | case FSEv06_ENCODING_RAW : | |
3274 | FSEv06_buildDTable(DTable, defaultNorm, max, defaultLog); | |
3275 | return 0; | |
3276 | case FSEv06_ENCODING_STATIC: | |
3277 | if (!flagRepeatTable) return ERROR(corruption_detected); | |
3278 | return 0; | |
3279 | default : /* impossible */ | |
3280 | case FSEv06_ENCODING_DYNAMIC : | |
3281 | { U32 tableLog; | |
3282 | S16 norm[MaxSeq+1]; | |
3283 | size_t const headerSize = FSEv06_readNCount(norm, &max, &tableLog, src, srcSize); | |
3284 | if (FSEv06_isError(headerSize)) return ERROR(corruption_detected); | |
3285 | if (tableLog > maxLog) return ERROR(corruption_detected); | |
3286 | FSEv06_buildDTable(DTable, norm, max, tableLog); | |
3287 | return headerSize; | |
3288 | } } | |
3289 | } | |
3290 | ||
3291 | ||
3292 | size_t ZSTDv06_decodeSeqHeaders(int* nbSeqPtr, | |
3293 | FSEv06_DTable* DTableLL, FSEv06_DTable* DTableML, FSEv06_DTable* DTableOffb, U32 flagRepeatTable, | |
3294 | const void* src, size_t srcSize) | |
3295 | { | |
3296 | const BYTE* const istart = (const BYTE* const)src; | |
3297 | const BYTE* const iend = istart + srcSize; | |
3298 | const BYTE* ip = istart; | |
3299 | ||
3300 | /* check */ | |
3301 | if (srcSize < MIN_SEQUENCES_SIZE) return ERROR(srcSize_wrong); | |
3302 | ||
3303 | /* SeqHead */ | |
3304 | { int nbSeq = *ip++; | |
3305 | if (!nbSeq) { *nbSeqPtr=0; return 1; } | |
3306 | if (nbSeq > 0x7F) { | |
3307 | if (nbSeq == 0xFF) { | |
3308 | if (ip+2 > iend) return ERROR(srcSize_wrong); | |
3309 | nbSeq = MEM_readLE16(ip) + LONGNBSEQ, ip+=2; | |
3310 | } else { | |
3311 | if (ip >= iend) return ERROR(srcSize_wrong); | |
3312 | nbSeq = ((nbSeq-0x80)<<8) + *ip++; | |
3313 | } | |
3314 | } | |
3315 | *nbSeqPtr = nbSeq; | |
3316 | } | |
3317 | ||
3318 | /* FSE table descriptors */ | |
3319 | { U32 const LLtype = *ip >> 6; | |
3320 | U32 const Offtype = (*ip >> 4) & 3; | |
3321 | U32 const MLtype = (*ip >> 2) & 3; | |
3322 | ip++; | |
3323 | ||
3324 | /* check */ | |
3325 | if (ip > iend-3) return ERROR(srcSize_wrong); /* min : all 3 are "raw", hence no header, but at least xxLog bits per type */ | |
3326 | ||
3327 | /* Build DTables */ | |
3328 | { size_t const bhSize = ZSTDv06_buildSeqTable(DTableLL, LLtype, MaxLL, LLFSELog, ip, iend-ip, LL_defaultNorm, LL_defaultNormLog, flagRepeatTable); | |
3329 | if (ZSTDv06_isError(bhSize)) return ERROR(corruption_detected); | |
3330 | ip += bhSize; | |
3331 | } | |
3332 | { size_t const bhSize = ZSTDv06_buildSeqTable(DTableOffb, Offtype, MaxOff, OffFSELog, ip, iend-ip, OF_defaultNorm, OF_defaultNormLog, flagRepeatTable); | |
3333 | if (ZSTDv06_isError(bhSize)) return ERROR(corruption_detected); | |
3334 | ip += bhSize; | |
3335 | } | |
3336 | { size_t const bhSize = ZSTDv06_buildSeqTable(DTableML, MLtype, MaxML, MLFSELog, ip, iend-ip, ML_defaultNorm, ML_defaultNormLog, flagRepeatTable); | |
3337 | if (ZSTDv06_isError(bhSize)) return ERROR(corruption_detected); | |
3338 | ip += bhSize; | |
3339 | } } | |
3340 | ||
3341 | return ip-istart; | |
3342 | } | |
3343 | ||
3344 | ||
3345 | typedef struct { | |
3346 | size_t litLength; | |
3347 | size_t matchLength; | |
3348 | size_t offset; | |
3349 | } seq_t; | |
3350 | ||
3351 | typedef struct { | |
3352 | BITv06_DStream_t DStream; | |
3353 | FSEv06_DState_t stateLL; | |
3354 | FSEv06_DState_t stateOffb; | |
3355 | FSEv06_DState_t stateML; | |
3356 | size_t prevOffset[ZSTDv06_REP_INIT]; | |
3357 | } seqState_t; | |
3358 | ||
3359 | ||
3360 | ||
3361 | static void ZSTDv06_decodeSequence(seq_t* seq, seqState_t* seqState) | |
3362 | { | |
3363 | /* Literal length */ | |
3364 | U32 const llCode = FSEv06_peekSymbol(&(seqState->stateLL)); | |
3365 | U32 const mlCode = FSEv06_peekSymbol(&(seqState->stateML)); | |
3366 | U32 const ofCode = FSEv06_peekSymbol(&(seqState->stateOffb)); /* <= maxOff, by table construction */ | |
3367 | ||
3368 | U32 const llBits = LL_bits[llCode]; | |
3369 | U32 const mlBits = ML_bits[mlCode]; | |
3370 | U32 const ofBits = ofCode; | |
3371 | U32 const totalBits = llBits+mlBits+ofBits; | |
3372 | ||
3373 | static const U32 LL_base[MaxLL+1] = { | |
3374 | 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, | |
3375 | 16, 18, 20, 22, 24, 28, 32, 40, 48, 64, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000, | |
3376 | 0x2000, 0x4000, 0x8000, 0x10000 }; | |
3377 | ||
3378 | static const U32 ML_base[MaxML+1] = { | |
3379 | 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, | |
3380 | 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, | |
3381 | 32, 34, 36, 38, 40, 44, 48, 56, 64, 80, 96, 0x80, 0x100, 0x200, 0x400, 0x800, | |
3382 | 0x1000, 0x2000, 0x4000, 0x8000, 0x10000 }; | |
3383 | ||
3384 | static const U32 OF_base[MaxOff+1] = { | |
3385 | 0, 1, 3, 7, 0xF, 0x1F, 0x3F, 0x7F, | |
3386 | 0xFF, 0x1FF, 0x3FF, 0x7FF, 0xFFF, 0x1FFF, 0x3FFF, 0x7FFF, | |
3387 | 0xFFFF, 0x1FFFF, 0x3FFFF, 0x7FFFF, 0xFFFFF, 0x1FFFFF, 0x3FFFFF, 0x7FFFFF, | |
3388 | 0xFFFFFF, 0x1FFFFFF, 0x3FFFFFF, /*fake*/ 1, 1 }; | |
3389 | ||
3390 | /* sequence */ | |
3391 | { size_t offset; | |
3392 | if (!ofCode) | |
3393 | offset = 0; | |
3394 | else { | |
3395 | offset = OF_base[ofCode] + BITv06_readBits(&(seqState->DStream), ofBits); /* <= 26 bits */ | |
3396 | if (MEM_32bits()) BITv06_reloadDStream(&(seqState->DStream)); | |
3397 | } | |
3398 | ||
3399 | if (offset < ZSTDv06_REP_NUM) { | |
3400 | if (llCode == 0 && offset <= 1) offset = 1-offset; | |
3401 | ||
3402 | if (offset != 0) { | |
3403 | size_t temp = seqState->prevOffset[offset]; | |
3404 | if (offset != 1) { | |
3405 | seqState->prevOffset[2] = seqState->prevOffset[1]; | |
3406 | } | |
3407 | seqState->prevOffset[1] = seqState->prevOffset[0]; | |
3408 | seqState->prevOffset[0] = offset = temp; | |
3409 | ||
3410 | } else { | |
3411 | offset = seqState->prevOffset[0]; | |
3412 | } | |
3413 | } else { | |
3414 | offset -= ZSTDv06_REP_MOVE; | |
3415 | seqState->prevOffset[2] = seqState->prevOffset[1]; | |
3416 | seqState->prevOffset[1] = seqState->prevOffset[0]; | |
3417 | seqState->prevOffset[0] = offset; | |
3418 | } | |
3419 | seq->offset = offset; | |
3420 | } | |
3421 | ||
3422 | seq->matchLength = ML_base[mlCode] + MINMATCH + ((mlCode>31) ? BITv06_readBits(&(seqState->DStream), mlBits) : 0); /* <= 16 bits */ | |
3423 | if (MEM_32bits() && (mlBits+llBits>24)) BITv06_reloadDStream(&(seqState->DStream)); | |
3424 | ||
3425 | seq->litLength = LL_base[llCode] + ((llCode>15) ? BITv06_readBits(&(seqState->DStream), llBits) : 0); /* <= 16 bits */ | |
3426 | if (MEM_32bits() || | |
3427 | (totalBits > 64 - 7 - (LLFSELog+MLFSELog+OffFSELog)) ) BITv06_reloadDStream(&(seqState->DStream)); | |
3428 | ||
3429 | /* ANS state update */ | |
3430 | FSEv06_updateState(&(seqState->stateLL), &(seqState->DStream)); /* <= 9 bits */ | |
3431 | FSEv06_updateState(&(seqState->stateML), &(seqState->DStream)); /* <= 9 bits */ | |
3432 | if (MEM_32bits()) BITv06_reloadDStream(&(seqState->DStream)); /* <= 18 bits */ | |
3433 | FSEv06_updateState(&(seqState->stateOffb), &(seqState->DStream)); /* <= 8 bits */ | |
3434 | } | |
3435 | ||
3436 | ||
3437 | size_t ZSTDv06_execSequence(BYTE* op, | |
3438 | BYTE* const oend, seq_t sequence, | |
3439 | const BYTE** litPtr, const BYTE* const litLimit, | |
3440 | const BYTE* const base, const BYTE* const vBase, const BYTE* const dictEnd) | |
3441 | { | |
3442 | BYTE* const oLitEnd = op + sequence.litLength; | |
3443 | size_t const sequenceLength = sequence.litLength + sequence.matchLength; | |
3444 | BYTE* const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */ | |
3445 | BYTE* const oend_8 = oend-8; | |
3446 | const BYTE* const iLitEnd = *litPtr + sequence.litLength; | |
3447 | const BYTE* match = oLitEnd - sequence.offset; | |
3448 | ||
3449 | /* check */ | |
3450 | if (oLitEnd > oend_8) return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of 8 from oend */ | |
3451 | if (oMatchEnd > oend) return ERROR(dstSize_tooSmall); /* overwrite beyond dst buffer */ | |
3452 | if (iLitEnd > litLimit) return ERROR(corruption_detected); /* over-read beyond lit buffer */ | |
3453 | ||
3454 | /* copy Literals */ | |
3455 | ZSTDv06_wildcopy(op, *litPtr, sequence.litLength); /* note : oLitEnd <= oend-8 : no risk of overwrite beyond oend */ | |
3456 | op = oLitEnd; | |
3457 | *litPtr = iLitEnd; /* update for next sequence */ | |
3458 | ||
3459 | /* copy Match */ | |
3460 | if (sequence.offset > (size_t)(oLitEnd - base)) { | |
3461 | /* offset beyond prefix */ | |
3462 | if (sequence.offset > (size_t)(oLitEnd - vBase)) return ERROR(corruption_detected); | |
3463 | match = dictEnd - (base-match); | |
3464 | if (match + sequence.matchLength <= dictEnd) { | |
3465 | memmove(oLitEnd, match, sequence.matchLength); | |
3466 | return sequenceLength; | |
3467 | } | |
3468 | /* span extDict & currentPrefixSegment */ | |
3469 | { size_t const length1 = dictEnd - match; | |
3470 | memmove(oLitEnd, match, length1); | |
3471 | op = oLitEnd + length1; | |
3472 | sequence.matchLength -= length1; | |
3473 | match = base; | |
3474 | if (op > oend_8 || sequence.matchLength < MINMATCH) { | |
3475 | while (op < oMatchEnd) *op++ = *match++; | |
3476 | return sequenceLength; | |
3477 | } | |
3478 | } } | |
3479 | /* Requirement: op <= oend_8 */ | |
3480 | ||
3481 | /* match within prefix */ | |
3482 | if (sequence.offset < 8) { | |
3483 | /* close range match, overlap */ | |
3484 | static const U32 dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 }; /* added */ | |
3485 | static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 }; /* substracted */ | |
3486 | int const sub2 = dec64table[sequence.offset]; | |
3487 | op[0] = match[0]; | |
3488 | op[1] = match[1]; | |
3489 | op[2] = match[2]; | |
3490 | op[3] = match[3]; | |
3491 | match += dec32table[sequence.offset]; | |
3492 | ZSTDv06_copy4(op+4, match); | |
3493 | match -= sub2; | |
3494 | } else { | |
3495 | ZSTDv06_copy8(op, match); | |
3496 | } | |
3497 | op += 8; match += 8; | |
3498 | ||
3499 | if (oMatchEnd > oend-(16-MINMATCH)) { | |
3500 | if (op < oend_8) { | |
3501 | ZSTDv06_wildcopy(op, match, oend_8 - op); | |
3502 | match += oend_8 - op; | |
3503 | op = oend_8; | |
3504 | } | |
3505 | while (op < oMatchEnd) *op++ = *match++; | |
3506 | } else { | |
3507 | ZSTDv06_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8); /* works even if matchLength < 8 */ | |
3508 | } | |
3509 | return sequenceLength; | |
3510 | } | |
3511 | ||
3512 | ||
3513 | static size_t ZSTDv06_decompressSequences( | |
3514 | ZSTDv06_DCtx* dctx, | |
3515 | void* dst, size_t maxDstSize, | |
3516 | const void* seqStart, size_t seqSize) | |
3517 | { | |
3518 | const BYTE* ip = (const BYTE*)seqStart; | |
3519 | const BYTE* const iend = ip + seqSize; | |
3520 | BYTE* const ostart = (BYTE* const)dst; | |
3521 | BYTE* const oend = ostart + maxDstSize; | |
3522 | BYTE* op = ostart; | |
3523 | const BYTE* litPtr = dctx->litPtr; | |
3524 | const BYTE* const litEnd = litPtr + dctx->litSize; | |
3525 | FSEv06_DTable* DTableLL = dctx->LLTable; | |
3526 | FSEv06_DTable* DTableML = dctx->MLTable; | |
3527 | FSEv06_DTable* DTableOffb = dctx->OffTable; | |
3528 | const BYTE* const base = (const BYTE*) (dctx->base); | |
3529 | const BYTE* const vBase = (const BYTE*) (dctx->vBase); | |
3530 | const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd); | |
3531 | int nbSeq; | |
3532 | ||
3533 | /* Build Decoding Tables */ | |
3534 | { size_t const seqHSize = ZSTDv06_decodeSeqHeaders(&nbSeq, DTableLL, DTableML, DTableOffb, dctx->flagRepeatTable, ip, seqSize); | |
3535 | if (ZSTDv06_isError(seqHSize)) return seqHSize; | |
3536 | ip += seqHSize; | |
3537 | dctx->flagRepeatTable = 0; | |
3538 | } | |
3539 | ||
3540 | /* Regen sequences */ | |
3541 | if (nbSeq) { | |
3542 | seq_t sequence; | |
3543 | seqState_t seqState; | |
3544 | ||
3545 | memset(&sequence, 0, sizeof(sequence)); | |
3546 | sequence.offset = REPCODE_STARTVALUE; | |
3547 | { U32 i; for (i=0; i<ZSTDv06_REP_INIT; i++) seqState.prevOffset[i] = REPCODE_STARTVALUE; } | |
3548 | { size_t const errorCode = BITv06_initDStream(&(seqState.DStream), ip, iend-ip); | |
3549 | if (ERR_isError(errorCode)) return ERROR(corruption_detected); } | |
3550 | FSEv06_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL); | |
3551 | FSEv06_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb); | |
3552 | FSEv06_initDState(&(seqState.stateML), &(seqState.DStream), DTableML); | |
3553 | ||
3554 | for ( ; (BITv06_reloadDStream(&(seqState.DStream)) <= BITv06_DStream_completed) && nbSeq ; ) { | |
3555 | nbSeq--; | |
3556 | ZSTDv06_decodeSequence(&sequence, &seqState); | |
3557 | ||
3558 | #if 0 /* debug */ | |
3559 | static BYTE* start = NULL; | |
3560 | if (start==NULL) start = op; | |
3561 | size_t pos = (size_t)(op-start); | |
3562 | if ((pos >= 5810037) && (pos < 5810400)) | |
3563 | printf("Dpos %6u :%5u literals & match %3u bytes at distance %6u \n", | |
3564 | pos, (U32)sequence.litLength, (U32)sequence.matchLength, (U32)sequence.offset); | |
3565 | #endif | |
3566 | ||
3567 | { size_t const oneSeqSize = ZSTDv06_execSequence(op, oend, sequence, &litPtr, litEnd, base, vBase, dictEnd); | |
3568 | if (ZSTDv06_isError(oneSeqSize)) return oneSeqSize; | |
3569 | op += oneSeqSize; | |
3570 | } } | |
3571 | ||
3572 | /* check if reached exact end */ | |
3573 | if (nbSeq) return ERROR(corruption_detected); | |
3574 | } | |
3575 | ||
3576 | /* last literal segment */ | |
3577 | { size_t const lastLLSize = litEnd - litPtr; | |
3578 | if (litPtr > litEnd) return ERROR(corruption_detected); /* too many literals already used */ | |
3579 | if (op+lastLLSize > oend) return ERROR(dstSize_tooSmall); | |
3580 | memcpy(op, litPtr, lastLLSize); | |
3581 | op += lastLLSize; | |
3582 | } | |
3583 | ||
3584 | return op-ostart; | |
3585 | } | |
3586 | ||
3587 | ||
3588 | static void ZSTDv06_checkContinuity(ZSTDv06_DCtx* dctx, const void* dst) | |
3589 | { | |
3590 | if (dst != dctx->previousDstEnd) { /* not contiguous */ | |
3591 | dctx->dictEnd = dctx->previousDstEnd; | |
3592 | dctx->vBase = (const char*)dst - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base)); | |
3593 | dctx->base = dst; | |
3594 | dctx->previousDstEnd = dst; | |
3595 | } | |
3596 | } | |
3597 | ||
3598 | ||
3599 | static size_t ZSTDv06_decompressBlock_internal(ZSTDv06_DCtx* dctx, | |
3600 | void* dst, size_t dstCapacity, | |
3601 | const void* src, size_t srcSize) | |
3602 | { /* blockType == blockCompressed */ | |
3603 | const BYTE* ip = (const BYTE*)src; | |
3604 | ||
3605 | if (srcSize >= ZSTDv06_BLOCKSIZE_MAX) return ERROR(srcSize_wrong); | |
3606 | ||
3607 | /* Decode literals sub-block */ | |
3608 | { size_t const litCSize = ZSTDv06_decodeLiteralsBlock(dctx, src, srcSize); | |
3609 | if (ZSTDv06_isError(litCSize)) return litCSize; | |
3610 | ip += litCSize; | |
3611 | srcSize -= litCSize; | |
3612 | } | |
3613 | return ZSTDv06_decompressSequences(dctx, dst, dstCapacity, ip, srcSize); | |
3614 | } | |
3615 | ||
3616 | ||
3617 | size_t ZSTDv06_decompressBlock(ZSTDv06_DCtx* dctx, | |
3618 | void* dst, size_t dstCapacity, | |
3619 | const void* src, size_t srcSize) | |
3620 | { | |
3621 | ZSTDv06_checkContinuity(dctx, dst); | |
3622 | return ZSTDv06_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize); | |
3623 | } | |
3624 | ||
3625 | ||
3626 | /*! ZSTDv06_decompressFrame() : | |
3627 | * `dctx` must be properly initialized */ | |
3628 | static size_t ZSTDv06_decompressFrame(ZSTDv06_DCtx* dctx, | |
3629 | void* dst, size_t dstCapacity, | |
3630 | const void* src, size_t srcSize) | |
3631 | { | |
3632 | const BYTE* ip = (const BYTE*)src; | |
3633 | const BYTE* const iend = ip + srcSize; | |
3634 | BYTE* const ostart = (BYTE* const)dst; | |
3635 | BYTE* op = ostart; | |
3636 | BYTE* const oend = ostart + dstCapacity; | |
3637 | size_t remainingSize = srcSize; | |
3638 | blockProperties_t blockProperties = { bt_compressed, 0 }; | |
3639 | ||
3640 | /* check */ | |
3641 | if (srcSize < ZSTDv06_frameHeaderSize_min+ZSTDv06_blockHeaderSize) return ERROR(srcSize_wrong); | |
3642 | ||
3643 | /* Frame Header */ | |
3644 | { size_t const frameHeaderSize = ZSTDv06_frameHeaderSize(src, ZSTDv06_frameHeaderSize_min); | |
3645 | if (ZSTDv06_isError(frameHeaderSize)) return frameHeaderSize; | |
3646 | if (srcSize < frameHeaderSize+ZSTDv06_blockHeaderSize) return ERROR(srcSize_wrong); | |
3647 | if (ZSTDv06_decodeFrameHeader(dctx, src, frameHeaderSize)) return ERROR(corruption_detected); | |
3648 | ip += frameHeaderSize; remainingSize -= frameHeaderSize; | |
3649 | } | |
3650 | ||
3651 | /* Loop on each block */ | |
3652 | while (1) { | |
3653 | size_t decodedSize=0; | |
3654 | size_t const cBlockSize = ZSTDv06_getcBlockSize(ip, iend-ip, &blockProperties); | |
3655 | if (ZSTDv06_isError(cBlockSize)) return cBlockSize; | |
3656 | ||
3657 | ip += ZSTDv06_blockHeaderSize; | |
3658 | remainingSize -= ZSTDv06_blockHeaderSize; | |
3659 | if (cBlockSize > remainingSize) return ERROR(srcSize_wrong); | |
3660 | ||
3661 | switch(blockProperties.blockType) | |
3662 | { | |
3663 | case bt_compressed: | |
3664 | decodedSize = ZSTDv06_decompressBlock_internal(dctx, op, oend-op, ip, cBlockSize); | |
3665 | break; | |
3666 | case bt_raw : | |
3667 | decodedSize = ZSTDv06_copyRawBlock(op, oend-op, ip, cBlockSize); | |
3668 | break; | |
3669 | case bt_rle : | |
3670 | return ERROR(GENERIC); /* not yet supported */ | |
3671 | break; | |
3672 | case bt_end : | |
3673 | /* end of frame */ | |
3674 | if (remainingSize) return ERROR(srcSize_wrong); | |
3675 | break; | |
3676 | default: | |
3677 | return ERROR(GENERIC); /* impossible */ | |
3678 | } | |
3679 | if (cBlockSize == 0) break; /* bt_end */ | |
3680 | ||
3681 | if (ZSTDv06_isError(decodedSize)) return decodedSize; | |
3682 | op += decodedSize; | |
3683 | ip += cBlockSize; | |
3684 | remainingSize -= cBlockSize; | |
3685 | } | |
3686 | ||
3687 | return op-ostart; | |
3688 | } | |
3689 | ||
3690 | ||
3691 | size_t ZSTDv06_decompress_usingPreparedDCtx(ZSTDv06_DCtx* dctx, const ZSTDv06_DCtx* refDCtx, | |
3692 | void* dst, size_t dstCapacity, | |
3693 | const void* src, size_t srcSize) | |
3694 | { | |
3695 | ZSTDv06_copyDCtx(dctx, refDCtx); | |
3696 | ZSTDv06_checkContinuity(dctx, dst); | |
3697 | return ZSTDv06_decompressFrame(dctx, dst, dstCapacity, src, srcSize); | |
3698 | } | |
3699 | ||
3700 | ||
3701 | size_t ZSTDv06_decompress_usingDict(ZSTDv06_DCtx* dctx, | |
3702 | void* dst, size_t dstCapacity, | |
3703 | const void* src, size_t srcSize, | |
3704 | const void* dict, size_t dictSize) | |
3705 | { | |
3706 | ZSTDv06_decompressBegin_usingDict(dctx, dict, dictSize); | |
3707 | ZSTDv06_checkContinuity(dctx, dst); | |
3708 | return ZSTDv06_decompressFrame(dctx, dst, dstCapacity, src, srcSize); | |
3709 | } | |
3710 | ||
3711 | ||
3712 | size_t ZSTDv06_decompressDCtx(ZSTDv06_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize) | |
3713 | { | |
3714 | return ZSTDv06_decompress_usingDict(dctx, dst, dstCapacity, src, srcSize, NULL, 0); | |
3715 | } | |
3716 | ||
3717 | ||
3718 | size_t ZSTDv06_decompress(void* dst, size_t dstCapacity, const void* src, size_t srcSize) | |
3719 | { | |
3720 | #if defined(ZSTDv06_HEAPMODE) && (ZSTDv06_HEAPMODE==1) | |
3721 | size_t regenSize; | |
3722 | ZSTDv06_DCtx* dctx = ZSTDv06_createDCtx(); | |
3723 | if (dctx==NULL) return ERROR(memory_allocation); | |
3724 | regenSize = ZSTDv06_decompressDCtx(dctx, dst, dstCapacity, src, srcSize); | |
3725 | ZSTDv06_freeDCtx(dctx); | |
3726 | return regenSize; | |
3727 | #else /* stack mode */ | |
3728 | ZSTDv06_DCtx dctx; | |
3729 | return ZSTDv06_decompressDCtx(&dctx, dst, dstCapacity, src, srcSize); | |
3730 | #endif | |
3731 | } | |
3732 | ||
11fdf7f2 TL |
3733 | size_t ZSTDv06_findFrameCompressedSize(const void* src, size_t srcSize) |
3734 | { | |
3735 | const BYTE* ip = (const BYTE*)src; | |
3736 | size_t remainingSize = srcSize; | |
3737 | blockProperties_t blockProperties = { bt_compressed, 0 }; | |
3738 | ||
3739 | /* Frame Header */ | |
3740 | { size_t const frameHeaderSize = ZSTDv06_frameHeaderSize(src, ZSTDv06_frameHeaderSize_min); | |
3741 | if (ZSTDv06_isError(frameHeaderSize)) return frameHeaderSize; | |
3742 | if (MEM_readLE32(src) != ZSTDv06_MAGICNUMBER) return ERROR(prefix_unknown); | |
3743 | if (srcSize < frameHeaderSize+ZSTDv06_blockHeaderSize) return ERROR(srcSize_wrong); | |
3744 | ip += frameHeaderSize; remainingSize -= frameHeaderSize; | |
3745 | } | |
3746 | ||
3747 | /* Loop on each block */ | |
3748 | while (1) { | |
3749 | size_t const cBlockSize = ZSTDv06_getcBlockSize(ip, remainingSize, &blockProperties); | |
3750 | if (ZSTDv06_isError(cBlockSize)) return cBlockSize; | |
3751 | ||
3752 | ip += ZSTDv06_blockHeaderSize; | |
3753 | remainingSize -= ZSTDv06_blockHeaderSize; | |
3754 | if (cBlockSize > remainingSize) return ERROR(srcSize_wrong); | |
3755 | ||
3756 | if (cBlockSize == 0) break; /* bt_end */ | |
3757 | ||
3758 | ip += cBlockSize; | |
3759 | remainingSize -= cBlockSize; | |
3760 | } | |
3761 | ||
3762 | return ip - (const BYTE*)src; | |
3763 | } | |
7c673cae FG |
3764 | |
3765 | /*_****************************** | |
3766 | * Streaming Decompression API | |
3767 | ********************************/ | |
3768 | size_t ZSTDv06_nextSrcSizeToDecompress(ZSTDv06_DCtx* dctx) | |
3769 | { | |
3770 | return dctx->expected; | |
3771 | } | |
3772 | ||
3773 | size_t ZSTDv06_decompressContinue(ZSTDv06_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize) | |
3774 | { | |
3775 | /* Sanity check */ | |
3776 | if (srcSize != dctx->expected) return ERROR(srcSize_wrong); | |
3777 | if (dstCapacity) ZSTDv06_checkContinuity(dctx, dst); | |
3778 | ||
3779 | /* Decompress : frame header; part 1 */ | |
3780 | switch (dctx->stage) | |
3781 | { | |
3782 | case ZSTDds_getFrameHeaderSize : | |
3783 | if (srcSize != ZSTDv06_frameHeaderSize_min) return ERROR(srcSize_wrong); /* impossible */ | |
3784 | dctx->headerSize = ZSTDv06_frameHeaderSize(src, ZSTDv06_frameHeaderSize_min); | |
3785 | if (ZSTDv06_isError(dctx->headerSize)) return dctx->headerSize; | |
3786 | memcpy(dctx->headerBuffer, src, ZSTDv06_frameHeaderSize_min); | |
3787 | if (dctx->headerSize > ZSTDv06_frameHeaderSize_min) { | |
3788 | dctx->expected = dctx->headerSize - ZSTDv06_frameHeaderSize_min; | |
3789 | dctx->stage = ZSTDds_decodeFrameHeader; | |
3790 | return 0; | |
3791 | } | |
3792 | dctx->expected = 0; /* not necessary to copy more */ | |
11fdf7f2 | 3793 | /* fall-through */ |
7c673cae FG |
3794 | case ZSTDds_decodeFrameHeader: |
3795 | { size_t result; | |
3796 | memcpy(dctx->headerBuffer + ZSTDv06_frameHeaderSize_min, src, dctx->expected); | |
3797 | result = ZSTDv06_decodeFrameHeader(dctx, dctx->headerBuffer, dctx->headerSize); | |
3798 | if (ZSTDv06_isError(result)) return result; | |
3799 | dctx->expected = ZSTDv06_blockHeaderSize; | |
3800 | dctx->stage = ZSTDds_decodeBlockHeader; | |
3801 | return 0; | |
3802 | } | |
3803 | case ZSTDds_decodeBlockHeader: | |
3804 | { blockProperties_t bp; | |
3805 | size_t const cBlockSize = ZSTDv06_getcBlockSize(src, ZSTDv06_blockHeaderSize, &bp); | |
3806 | if (ZSTDv06_isError(cBlockSize)) return cBlockSize; | |
3807 | if (bp.blockType == bt_end) { | |
3808 | dctx->expected = 0; | |
3809 | dctx->stage = ZSTDds_getFrameHeaderSize; | |
3810 | } else { | |
3811 | dctx->expected = cBlockSize; | |
3812 | dctx->bType = bp.blockType; | |
3813 | dctx->stage = ZSTDds_decompressBlock; | |
3814 | } | |
3815 | return 0; | |
3816 | } | |
3817 | case ZSTDds_decompressBlock: | |
3818 | { size_t rSize; | |
3819 | switch(dctx->bType) | |
3820 | { | |
3821 | case bt_compressed: | |
3822 | rSize = ZSTDv06_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize); | |
3823 | break; | |
3824 | case bt_raw : | |
3825 | rSize = ZSTDv06_copyRawBlock(dst, dstCapacity, src, srcSize); | |
3826 | break; | |
3827 | case bt_rle : | |
3828 | return ERROR(GENERIC); /* not yet handled */ | |
3829 | break; | |
3830 | case bt_end : /* should never happen (filtered at phase 1) */ | |
3831 | rSize = 0; | |
3832 | break; | |
3833 | default: | |
3834 | return ERROR(GENERIC); /* impossible */ | |
3835 | } | |
3836 | dctx->stage = ZSTDds_decodeBlockHeader; | |
3837 | dctx->expected = ZSTDv06_blockHeaderSize; | |
3838 | dctx->previousDstEnd = (char*)dst + rSize; | |
3839 | return rSize; | |
3840 | } | |
3841 | default: | |
3842 | return ERROR(GENERIC); /* impossible */ | |
3843 | } | |
3844 | } | |
3845 | ||
3846 | ||
3847 | static void ZSTDv06_refDictContent(ZSTDv06_DCtx* dctx, const void* dict, size_t dictSize) | |
3848 | { | |
3849 | dctx->dictEnd = dctx->previousDstEnd; | |
3850 | dctx->vBase = (const char*)dict - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base)); | |
3851 | dctx->base = dict; | |
3852 | dctx->previousDstEnd = (const char*)dict + dictSize; | |
3853 | } | |
3854 | ||
3855 | static size_t ZSTDv06_loadEntropy(ZSTDv06_DCtx* dctx, const void* dict, size_t dictSize) | |
3856 | { | |
3857 | size_t hSize, offcodeHeaderSize, matchlengthHeaderSize, litlengthHeaderSize; | |
3858 | ||
3859 | hSize = HUFv06_readDTableX4(dctx->hufTableX4, dict, dictSize); | |
3860 | if (HUFv06_isError(hSize)) return ERROR(dictionary_corrupted); | |
3861 | dict = (const char*)dict + hSize; | |
3862 | dictSize -= hSize; | |
3863 | ||
3864 | { short offcodeNCount[MaxOff+1]; | |
3865 | U32 offcodeMaxValue=MaxOff, offcodeLog; | |
3866 | offcodeHeaderSize = FSEv06_readNCount(offcodeNCount, &offcodeMaxValue, &offcodeLog, dict, dictSize); | |
3867 | if (FSEv06_isError(offcodeHeaderSize)) return ERROR(dictionary_corrupted); | |
3868 | if (offcodeLog > OffFSELog) return ERROR(dictionary_corrupted); | |
3869 | { size_t const errorCode = FSEv06_buildDTable(dctx->OffTable, offcodeNCount, offcodeMaxValue, offcodeLog); | |
3870 | if (FSEv06_isError(errorCode)) return ERROR(dictionary_corrupted); } | |
3871 | dict = (const char*)dict + offcodeHeaderSize; | |
3872 | dictSize -= offcodeHeaderSize; | |
3873 | } | |
3874 | ||
3875 | { short matchlengthNCount[MaxML+1]; | |
3876 | unsigned matchlengthMaxValue = MaxML, matchlengthLog; | |
3877 | matchlengthHeaderSize = FSEv06_readNCount(matchlengthNCount, &matchlengthMaxValue, &matchlengthLog, dict, dictSize); | |
3878 | if (FSEv06_isError(matchlengthHeaderSize)) return ERROR(dictionary_corrupted); | |
3879 | if (matchlengthLog > MLFSELog) return ERROR(dictionary_corrupted); | |
3880 | { size_t const errorCode = FSEv06_buildDTable(dctx->MLTable, matchlengthNCount, matchlengthMaxValue, matchlengthLog); | |
3881 | if (FSEv06_isError(errorCode)) return ERROR(dictionary_corrupted); } | |
3882 | dict = (const char*)dict + matchlengthHeaderSize; | |
3883 | dictSize -= matchlengthHeaderSize; | |
3884 | } | |
3885 | ||
3886 | { short litlengthNCount[MaxLL+1]; | |
3887 | unsigned litlengthMaxValue = MaxLL, litlengthLog; | |
3888 | litlengthHeaderSize = FSEv06_readNCount(litlengthNCount, &litlengthMaxValue, &litlengthLog, dict, dictSize); | |
3889 | if (FSEv06_isError(litlengthHeaderSize)) return ERROR(dictionary_corrupted); | |
3890 | if (litlengthLog > LLFSELog) return ERROR(dictionary_corrupted); | |
3891 | { size_t const errorCode = FSEv06_buildDTable(dctx->LLTable, litlengthNCount, litlengthMaxValue, litlengthLog); | |
3892 | if (FSEv06_isError(errorCode)) return ERROR(dictionary_corrupted); } | |
3893 | } | |
3894 | ||
3895 | dctx->flagRepeatTable = 1; | |
3896 | return hSize + offcodeHeaderSize + matchlengthHeaderSize + litlengthHeaderSize; | |
3897 | } | |
3898 | ||
3899 | static size_t ZSTDv06_decompress_insertDictionary(ZSTDv06_DCtx* dctx, const void* dict, size_t dictSize) | |
3900 | { | |
3901 | size_t eSize; | |
3902 | U32 const magic = MEM_readLE32(dict); | |
3903 | if (magic != ZSTDv06_DICT_MAGIC) { | |
3904 | /* pure content mode */ | |
3905 | ZSTDv06_refDictContent(dctx, dict, dictSize); | |
3906 | return 0; | |
3907 | } | |
3908 | /* load entropy tables */ | |
3909 | dict = (const char*)dict + 4; | |
3910 | dictSize -= 4; | |
3911 | eSize = ZSTDv06_loadEntropy(dctx, dict, dictSize); | |
3912 | if (ZSTDv06_isError(eSize)) return ERROR(dictionary_corrupted); | |
3913 | ||
3914 | /* reference dictionary content */ | |
3915 | dict = (const char*)dict + eSize; | |
3916 | dictSize -= eSize; | |
3917 | ZSTDv06_refDictContent(dctx, dict, dictSize); | |
3918 | ||
3919 | return 0; | |
3920 | } | |
3921 | ||
3922 | ||
3923 | size_t ZSTDv06_decompressBegin_usingDict(ZSTDv06_DCtx* dctx, const void* dict, size_t dictSize) | |
3924 | { | |
3925 | { size_t const errorCode = ZSTDv06_decompressBegin(dctx); | |
3926 | if (ZSTDv06_isError(errorCode)) return errorCode; } | |
3927 | ||
3928 | if (dict && dictSize) { | |
3929 | size_t const errorCode = ZSTDv06_decompress_insertDictionary(dctx, dict, dictSize); | |
3930 | if (ZSTDv06_isError(errorCode)) return ERROR(dictionary_corrupted); | |
3931 | } | |
3932 | ||
3933 | return 0; | |
3934 | } | |
3935 | ||
3936 | /* | |
3937 | Buffered version of Zstd compression library | |
3938 | Copyright (C) 2015-2016, Yann Collet. | |
3939 | ||
3940 | BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) | |
3941 | ||
3942 | Redistribution and use in source and binary forms, with or without | |
3943 | modification, are permitted provided that the following conditions are | |
3944 | met: | |
3945 | * Redistributions of source code must retain the above copyright | |
3946 | notice, this list of conditions and the following disclaimer. | |
3947 | * Redistributions in binary form must reproduce the above | |
3948 | copyright notice, this list of conditions and the following disclaimer | |
3949 | in the documentation and/or other materials provided with the | |
3950 | distribution. | |
3951 | THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
3952 | "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
3953 | LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | |
3954 | A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | |
3955 | OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
3956 | SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | |
3957 | LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
3958 | DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |
3959 | THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
3960 | (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
3961 | OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
3962 | ||
3963 | You can contact the author at : | |
3964 | - zstd homepage : http://www.zstd.net/ | |
3965 | */ | |
3966 | ||
3967 | ||
3968 | /*-*************************************************************************** | |
3969 | * Streaming decompression howto | |
3970 | * | |
3971 | * A ZBUFFv06_DCtx object is required to track streaming operations. | |
3972 | * Use ZBUFFv06_createDCtx() and ZBUFFv06_freeDCtx() to create/release resources. | |
3973 | * Use ZBUFFv06_decompressInit() to start a new decompression operation, | |
3974 | * or ZBUFFv06_decompressInitDictionary() if decompression requires a dictionary. | |
3975 | * Note that ZBUFFv06_DCtx objects can be re-init multiple times. | |
3976 | * | |
3977 | * Use ZBUFFv06_decompressContinue() repetitively to consume your input. | |
3978 | * *srcSizePtr and *dstCapacityPtr can be any size. | |
3979 | * The function will report how many bytes were read or written by modifying *srcSizePtr and *dstCapacityPtr. | |
3980 | * Note that it may not consume the entire input, in which case it's up to the caller to present remaining input again. | |
3981 | * The content of @dst will be overwritten (up to *dstCapacityPtr) at each function call, so save its content if it matters, or change @dst. | |
3982 | * @return : a hint to preferred nb of bytes to use as input for next function call (it's only a hint, to help latency), | |
3983 | * or 0 when a frame is completely decoded, | |
3984 | * or an error code, which can be tested using ZBUFFv06_isError(). | |
3985 | * | |
3986 | * Hint : recommended buffer sizes (not compulsory) : ZBUFFv06_recommendedDInSize() and ZBUFFv06_recommendedDOutSize() | |
3987 | * output : ZBUFFv06_recommendedDOutSize==128 KB block size is the internal unit, it ensures it's always possible to write a full block when decoded. | |
3988 | * input : ZBUFFv06_recommendedDInSize == 128KB + 3; | |
3989 | * just follow indications from ZBUFFv06_decompressContinue() to minimize latency. It should always be <= 128 KB + 3 . | |
3990 | * *******************************************************************************/ | |
3991 | ||
3992 | typedef enum { ZBUFFds_init, ZBUFFds_loadHeader, | |
3993 | ZBUFFds_read, ZBUFFds_load, ZBUFFds_flush } ZBUFFv06_dStage; | |
3994 | ||
3995 | /* *** Resource management *** */ | |
3996 | struct ZBUFFv06_DCtx_s { | |
3997 | ZSTDv06_DCtx* zd; | |
3998 | ZSTDv06_frameParams fParams; | |
3999 | ZBUFFv06_dStage stage; | |
4000 | char* inBuff; | |
4001 | size_t inBuffSize; | |
4002 | size_t inPos; | |
4003 | char* outBuff; | |
4004 | size_t outBuffSize; | |
4005 | size_t outStart; | |
4006 | size_t outEnd; | |
4007 | size_t blockSize; | |
4008 | BYTE headerBuffer[ZSTDv06_FRAMEHEADERSIZE_MAX]; | |
4009 | size_t lhSize; | |
4010 | }; /* typedef'd to ZBUFFv06_DCtx within "zstd_buffered.h" */ | |
4011 | ||
4012 | ||
4013 | ZBUFFv06_DCtx* ZBUFFv06_createDCtx(void) | |
4014 | { | |
4015 | ZBUFFv06_DCtx* zbd = (ZBUFFv06_DCtx*)malloc(sizeof(ZBUFFv06_DCtx)); | |
4016 | if (zbd==NULL) return NULL; | |
4017 | memset(zbd, 0, sizeof(*zbd)); | |
4018 | zbd->zd = ZSTDv06_createDCtx(); | |
4019 | zbd->stage = ZBUFFds_init; | |
4020 | return zbd; | |
4021 | } | |
4022 | ||
4023 | size_t ZBUFFv06_freeDCtx(ZBUFFv06_DCtx* zbd) | |
4024 | { | |
4025 | if (zbd==NULL) return 0; /* support free on null */ | |
4026 | ZSTDv06_freeDCtx(zbd->zd); | |
4027 | free(zbd->inBuff); | |
4028 | free(zbd->outBuff); | |
4029 | free(zbd); | |
4030 | return 0; | |
4031 | } | |
4032 | ||
4033 | ||
4034 | /* *** Initialization *** */ | |
4035 | ||
4036 | size_t ZBUFFv06_decompressInitDictionary(ZBUFFv06_DCtx* zbd, const void* dict, size_t dictSize) | |
4037 | { | |
4038 | zbd->stage = ZBUFFds_loadHeader; | |
4039 | zbd->lhSize = zbd->inPos = zbd->outStart = zbd->outEnd = 0; | |
4040 | return ZSTDv06_decompressBegin_usingDict(zbd->zd, dict, dictSize); | |
4041 | } | |
4042 | ||
4043 | size_t ZBUFFv06_decompressInit(ZBUFFv06_DCtx* zbd) | |
4044 | { | |
4045 | return ZBUFFv06_decompressInitDictionary(zbd, NULL, 0); | |
4046 | } | |
4047 | ||
4048 | ||
4049 | ||
4050 | MEM_STATIC size_t ZBUFFv06_limitCopy(void* dst, size_t dstCapacity, const void* src, size_t srcSize) | |
4051 | { | |
4052 | size_t length = MIN(dstCapacity, srcSize); | |
4053 | memcpy(dst, src, length); | |
4054 | return length; | |
4055 | } | |
4056 | ||
4057 | ||
4058 | /* *** Decompression *** */ | |
4059 | ||
4060 | size_t ZBUFFv06_decompressContinue(ZBUFFv06_DCtx* zbd, | |
4061 | void* dst, size_t* dstCapacityPtr, | |
4062 | const void* src, size_t* srcSizePtr) | |
4063 | { | |
4064 | const char* const istart = (const char*)src; | |
4065 | const char* const iend = istart + *srcSizePtr; | |
4066 | const char* ip = istart; | |
4067 | char* const ostart = (char*)dst; | |
4068 | char* const oend = ostart + *dstCapacityPtr; | |
4069 | char* op = ostart; | |
4070 | U32 notDone = 1; | |
4071 | ||
4072 | while (notDone) { | |
4073 | switch(zbd->stage) | |
4074 | { | |
4075 | case ZBUFFds_init : | |
4076 | return ERROR(init_missing); | |
4077 | ||
4078 | case ZBUFFds_loadHeader : | |
4079 | { size_t const hSize = ZSTDv06_getFrameParams(&(zbd->fParams), zbd->headerBuffer, zbd->lhSize); | |
4080 | if (hSize != 0) { | |
4081 | size_t const toLoad = hSize - zbd->lhSize; /* if hSize!=0, hSize > zbd->lhSize */ | |
4082 | if (ZSTDv06_isError(hSize)) return hSize; | |
4083 | if (toLoad > (size_t)(iend-ip)) { /* not enough input to load full header */ | |
4084 | memcpy(zbd->headerBuffer + zbd->lhSize, ip, iend-ip); | |
4085 | zbd->lhSize += iend-ip; ip = iend; notDone = 0; | |
4086 | *dstCapacityPtr = 0; | |
4087 | return (hSize - zbd->lhSize) + ZSTDv06_blockHeaderSize; /* remaining header bytes + next block header */ | |
4088 | } | |
4089 | memcpy(zbd->headerBuffer + zbd->lhSize, ip, toLoad); zbd->lhSize = hSize; ip += toLoad; | |
4090 | break; | |
4091 | } } | |
4092 | ||
4093 | /* Consume header */ | |
4094 | { size_t const h1Size = ZSTDv06_nextSrcSizeToDecompress(zbd->zd); /* == ZSTDv06_frameHeaderSize_min */ | |
4095 | size_t const h1Result = ZSTDv06_decompressContinue(zbd->zd, NULL, 0, zbd->headerBuffer, h1Size); | |
4096 | if (ZSTDv06_isError(h1Result)) return h1Result; | |
4097 | if (h1Size < zbd->lhSize) { /* long header */ | |
4098 | size_t const h2Size = ZSTDv06_nextSrcSizeToDecompress(zbd->zd); | |
4099 | size_t const h2Result = ZSTDv06_decompressContinue(zbd->zd, NULL, 0, zbd->headerBuffer+h1Size, h2Size); | |
4100 | if (ZSTDv06_isError(h2Result)) return h2Result; | |
4101 | } } | |
4102 | ||
4103 | /* Frame header instruct buffer sizes */ | |
4104 | { size_t const blockSize = MIN(1 << zbd->fParams.windowLog, ZSTDv06_BLOCKSIZE_MAX); | |
4105 | zbd->blockSize = blockSize; | |
4106 | if (zbd->inBuffSize < blockSize) { | |
4107 | free(zbd->inBuff); | |
4108 | zbd->inBuffSize = blockSize; | |
4109 | zbd->inBuff = (char*)malloc(blockSize); | |
4110 | if (zbd->inBuff == NULL) return ERROR(memory_allocation); | |
4111 | } | |
11fdf7f2 | 4112 | { size_t const neededOutSize = ((size_t)1 << zbd->fParams.windowLog) + blockSize + WILDCOPY_OVERLENGTH * 2; |
7c673cae FG |
4113 | if (zbd->outBuffSize < neededOutSize) { |
4114 | free(zbd->outBuff); | |
4115 | zbd->outBuffSize = neededOutSize; | |
4116 | zbd->outBuff = (char*)malloc(neededOutSize); | |
4117 | if (zbd->outBuff == NULL) return ERROR(memory_allocation); | |
4118 | } } } | |
4119 | zbd->stage = ZBUFFds_read; | |
11fdf7f2 | 4120 | /* fall-through */ |
7c673cae FG |
4121 | case ZBUFFds_read: |
4122 | { size_t const neededInSize = ZSTDv06_nextSrcSizeToDecompress(zbd->zd); | |
4123 | if (neededInSize==0) { /* end of frame */ | |
4124 | zbd->stage = ZBUFFds_init; | |
4125 | notDone = 0; | |
4126 | break; | |
4127 | } | |
4128 | if ((size_t)(iend-ip) >= neededInSize) { /* decode directly from src */ | |
4129 | size_t const decodedSize = ZSTDv06_decompressContinue(zbd->zd, | |
4130 | zbd->outBuff + zbd->outStart, zbd->outBuffSize - zbd->outStart, | |
4131 | ip, neededInSize); | |
4132 | if (ZSTDv06_isError(decodedSize)) return decodedSize; | |
4133 | ip += neededInSize; | |
4134 | if (!decodedSize) break; /* this was just a header */ | |
4135 | zbd->outEnd = zbd->outStart + decodedSize; | |
4136 | zbd->stage = ZBUFFds_flush; | |
4137 | break; | |
4138 | } | |
4139 | if (ip==iend) { notDone = 0; break; } /* no more input */ | |
4140 | zbd->stage = ZBUFFds_load; | |
4141 | } | |
11fdf7f2 | 4142 | /* fall-through */ |
7c673cae FG |
4143 | case ZBUFFds_load: |
4144 | { size_t const neededInSize = ZSTDv06_nextSrcSizeToDecompress(zbd->zd); | |
4145 | size_t const toLoad = neededInSize - zbd->inPos; /* should always be <= remaining space within inBuff */ | |
4146 | size_t loadedSize; | |
4147 | if (toLoad > zbd->inBuffSize - zbd->inPos) return ERROR(corruption_detected); /* should never happen */ | |
4148 | loadedSize = ZBUFFv06_limitCopy(zbd->inBuff + zbd->inPos, toLoad, ip, iend-ip); | |
4149 | ip += loadedSize; | |
4150 | zbd->inPos += loadedSize; | |
4151 | if (loadedSize < toLoad) { notDone = 0; break; } /* not enough input, wait for more */ | |
4152 | ||
4153 | /* decode loaded input */ | |
4154 | { size_t const decodedSize = ZSTDv06_decompressContinue(zbd->zd, | |
4155 | zbd->outBuff + zbd->outStart, zbd->outBuffSize - zbd->outStart, | |
4156 | zbd->inBuff, neededInSize); | |
4157 | if (ZSTDv06_isError(decodedSize)) return decodedSize; | |
4158 | zbd->inPos = 0; /* input is consumed */ | |
4159 | if (!decodedSize) { zbd->stage = ZBUFFds_read; break; } /* this was just a header */ | |
4160 | zbd->outEnd = zbd->outStart + decodedSize; | |
4161 | zbd->stage = ZBUFFds_flush; | |
4162 | // break; /* ZBUFFds_flush follows */ | |
11fdf7f2 TL |
4163 | } |
4164 | } | |
4165 | /* fall-through */ | |
7c673cae FG |
4166 | case ZBUFFds_flush: |
4167 | { size_t const toFlushSize = zbd->outEnd - zbd->outStart; | |
4168 | size_t const flushedSize = ZBUFFv06_limitCopy(op, oend-op, zbd->outBuff + zbd->outStart, toFlushSize); | |
4169 | op += flushedSize; | |
4170 | zbd->outStart += flushedSize; | |
4171 | if (flushedSize == toFlushSize) { | |
4172 | zbd->stage = ZBUFFds_read; | |
4173 | if (zbd->outStart + zbd->blockSize > zbd->outBuffSize) | |
4174 | zbd->outStart = zbd->outEnd = 0; | |
4175 | break; | |
4176 | } | |
4177 | /* cannot flush everything */ | |
4178 | notDone = 0; | |
4179 | break; | |
4180 | } | |
4181 | default: return ERROR(GENERIC); /* impossible */ | |
4182 | } } | |
4183 | ||
4184 | /* result */ | |
4185 | *srcSizePtr = ip-istart; | |
4186 | *dstCapacityPtr = op-ostart; | |
4187 | { size_t nextSrcSizeHint = ZSTDv06_nextSrcSizeToDecompress(zbd->zd); | |
4188 | if (nextSrcSizeHint > ZSTDv06_blockHeaderSize) nextSrcSizeHint+= ZSTDv06_blockHeaderSize; /* get following block header too */ | |
4189 | nextSrcSizeHint -= zbd->inPos; /* already loaded*/ | |
4190 | return nextSrcSizeHint; | |
4191 | } | |
4192 | } | |
4193 | ||
4194 | ||
4195 | ||
4196 | /* ************************************* | |
4197 | * Tool functions | |
4198 | ***************************************/ | |
4199 | size_t ZBUFFv06_recommendedDInSize(void) { return ZSTDv06_BLOCKSIZE_MAX + ZSTDv06_blockHeaderSize /* block header size*/ ; } | |
4200 | size_t ZBUFFv06_recommendedDOutSize(void) { return ZSTDv06_BLOCKSIZE_MAX; } |