~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/lib/zstd/huf_decompress.c

Version: ~ [ linux-5.1-rc2 ] ~ [ linux-5.0.4 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.31 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.108 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.165 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.177 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.137 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.63 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-3.9.11 ] ~ [ linux-3.8.13 ] ~ [ linux-3.7.10 ] ~ [ linux-3.6.11 ] ~ [ linux-3.5.7 ] ~ [ linux-3.4.113 ] ~ [ linux-3.3.8 ] ~ [ linux-3.2.102 ] ~ [ linux-3.1.10 ] ~ [ linux-3.0.101 ] ~ [ linux-2.6.39.4 ] ~ [ linux-2.6.38.8 ] ~ [ linux-2.6.37.6 ] ~ [ linux-2.6.36.4 ] ~ [ linux-2.6.35.14 ] ~ [ linux-2.6.34.15 ] ~ [ linux-2.6.33.20 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  1 /*
  2  * Huffman decoder, part of New Generation Entropy library
  3  * Copyright (C) 2013-2016, Yann Collet.
  4  *
  5  * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
  6  *
  7  * Redistribution and use in source and binary forms, with or without
  8  * modification, are permitted provided that the following conditions are
  9  * met:
 10  *
 11  *   * Redistributions of source code must retain the above copyright
 12  * notice, this list of conditions and the following disclaimer.
 13  *   * Redistributions in binary form must reproduce the above
 14  * copyright notice, this list of conditions and the following disclaimer
 15  * in the documentation and/or other materials provided with the
 16  * distribution.
 17  *
 18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 19  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 20  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 21  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 22  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 23  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 24  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 25  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 26  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 28  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 29  *
 30  * This program is free software; you can redistribute it and/or modify it under
 31  * the terms of the GNU General Public License version 2 as published by the
 32  * Free Software Foundation. This program is dual-licensed; you may select
 33  * either version 2 of the GNU General Public License ("GPL") or BSD license
 34  * ("BSD").
 35  *
 36  * You can contact the author at :
 37  * - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
 38  */
 39 
 40 /* **************************************************************
 41 *  Compiler specifics
 42 ****************************************************************/
 43 #define FORCE_INLINE static __always_inline
 44 
 45 /* **************************************************************
 46 *  Dependencies
 47 ****************************************************************/
 48 #include "bitstream.h" /* BIT_* */
 49 #include "fse.h"       /* header compression */
 50 #include "huf.h"
 51 #include <linux/compiler.h>
 52 #include <linux/kernel.h>
 53 #include <linux/string.h> /* memcpy, memset */
 54 
 55 /* **************************************************************
 56 *  Error Management
 57 ****************************************************************/
 58 #define HUF_STATIC_ASSERT(c)                                   \
 59         {                                                      \
 60                 enum { HUF_static_assert = 1 / (int)(!!(c)) }; \
 61         } /* use only *after* variable declarations */
 62 
 63 /*-***************************/
 64 /*  generic DTableDesc       */
 65 /*-***************************/
 66 
 67 typedef struct {
 68         BYTE maxTableLog;
 69         BYTE tableType;
 70         BYTE tableLog;
 71         BYTE reserved;
 72 } DTableDesc;
 73 
 74 static DTableDesc HUF_getDTableDesc(const HUF_DTable *table)
 75 {
 76         DTableDesc dtd;
 77         memcpy(&dtd, table, sizeof(dtd));
 78         return dtd;
 79 }
 80 
 81 /*-***************************/
 82 /*  single-symbol decoding   */
 83 /*-***************************/
 84 
 85 typedef struct {
 86         BYTE byte;
 87         BYTE nbBits;
 88 } HUF_DEltX2; /* single-symbol decoding */
 89 
 90 size_t HUF_readDTableX2_wksp(HUF_DTable *DTable, const void *src, size_t srcSize, void *workspace, size_t workspaceSize)
 91 {
 92         U32 tableLog = 0;
 93         U32 nbSymbols = 0;
 94         size_t iSize;
 95         void *const dtPtr = DTable + 1;
 96         HUF_DEltX2 *const dt = (HUF_DEltX2 *)dtPtr;
 97 
 98         U32 *rankVal;
 99         BYTE *huffWeight;
100         size_t spaceUsed32 = 0;
101 
102         rankVal = (U32 *)workspace + spaceUsed32;
103         spaceUsed32 += HUF_TABLELOG_ABSOLUTEMAX + 1;
104         huffWeight = (BYTE *)((U32 *)workspace + spaceUsed32);
105         spaceUsed32 += ALIGN(HUF_SYMBOLVALUE_MAX + 1, sizeof(U32)) >> 2;
106 
107         if ((spaceUsed32 << 2) > workspaceSize)
108                 return ERROR(tableLog_tooLarge);
109         workspace = (U32 *)workspace + spaceUsed32;
110         workspaceSize -= (spaceUsed32 << 2);
111 
112         HUF_STATIC_ASSERT(sizeof(DTableDesc) == sizeof(HUF_DTable));
113         /* memset(huffWeight, 0, sizeof(huffWeight)); */ /* is not necessary, even though some analyzer complain ... */
114 
115         iSize = HUF_readStats_wksp(huffWeight, HUF_SYMBOLVALUE_MAX + 1, rankVal, &nbSymbols, &tableLog, src, srcSize, workspace, workspaceSize);
116         if (HUF_isError(iSize))
117                 return iSize;
118 
119         /* Table header */
120         {
121                 DTableDesc dtd = HUF_getDTableDesc(DTable);
122                 if (tableLog > (U32)(dtd.maxTableLog + 1))
123                         return ERROR(tableLog_tooLarge); /* DTable too small, Huffman tree cannot fit in */
124                 dtd.tableType = 0;
125                 dtd.tableLog = (BYTE)tableLog;
126                 memcpy(DTable, &dtd, sizeof(dtd));
127         }
128 
129         /* Calculate starting value for each rank */
130         {
131                 U32 n, nextRankStart = 0;
132                 for (n = 1; n < tableLog + 1; n++) {
133                         U32 const curr = nextRankStart;
134                         nextRankStart += (rankVal[n] << (n - 1));
135                         rankVal[n] = curr;
136                 }
137         }
138 
139         /* fill DTable */
140         {
141                 U32 n;
142                 for (n = 0; n < nbSymbols; n++) {
143                         U32 const w = huffWeight[n];
144                         U32 const length = (1 << w) >> 1;
145                         U32 u;
146                         HUF_DEltX2 D;
147                         D.byte = (BYTE)n;
148                         D.nbBits = (BYTE)(tableLog + 1 - w);
149                         for (u = rankVal[w]; u < rankVal[w] + length; u++)
150                                 dt[u] = D;
151                         rankVal[w] += length;
152                 }
153         }
154 
155         return iSize;
156 }
157 
158 static BYTE HUF_decodeSymbolX2(BIT_DStream_t *Dstream, const HUF_DEltX2 *dt, const U32 dtLog)
159 {
160         size_t const val = BIT_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */
161         BYTE const c = dt[val].byte;
162         BIT_skipBits(Dstream, dt[val].nbBits);
163         return c;
164 }
165 
166 #define HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr) *ptr++ = HUF_decodeSymbolX2(DStreamPtr, dt, dtLog)
167 
168 #define HUF_DECODE_SYMBOLX2_1(ptr, DStreamPtr)         \
169         if (ZSTD_64bits() || (HUF_TABLELOG_MAX <= 12)) \
170         HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
171 
172 #define HUF_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \
173         if (ZSTD_64bits())                     \
174         HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
175 
176 FORCE_INLINE size_t HUF_decodeStreamX2(BYTE *p, BIT_DStream_t *const bitDPtr, BYTE *const pEnd, const HUF_DEltX2 *const dt, const U32 dtLog)
177 {
178         BYTE *const pStart = p;
179 
180         /* up to 4 symbols at a time */
181         while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd - 4)) {
182                 HUF_DECODE_SYMBOLX2_2(p, bitDPtr);
183                 HUF_DECODE_SYMBOLX2_1(p, bitDPtr);
184                 HUF_DECODE_SYMBOLX2_2(p, bitDPtr);
185                 HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
186         }
187 
188         /* closer to the end */
189         while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p < pEnd))
190                 HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
191 
192         /* no more data to retrieve from bitstream, hence no need to reload */
193         while (p < pEnd)
194                 HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
195 
196         return pEnd - pStart;
197 }
198 
199 static size_t HUF_decompress1X2_usingDTable_internal(void *dst, size_t dstSize, const void *cSrc, size_t cSrcSize, const HUF_DTable *DTable)
200 {
201         BYTE *op = (BYTE *)dst;
202         BYTE *const oend = op + dstSize;
203         const void *dtPtr = DTable + 1;
204         const HUF_DEltX2 *const dt = (const HUF_DEltX2 *)dtPtr;
205         BIT_DStream_t bitD;
206         DTableDesc const dtd = HUF_getDTableDesc(DTable);
207         U32 const dtLog = dtd.tableLog;
208 
209         {
210                 size_t const errorCode = BIT_initDStream(&bitD, cSrc, cSrcSize);
211                 if (HUF_isError(errorCode))
212                         return errorCode;
213         }
214 
215         HUF_decodeStreamX2(op, &bitD, oend, dt, dtLog);
216 
217         /* check */
218         if (!BIT_endOfDStream(&bitD))
219                 return ERROR(corruption_detected);
220 
221         return dstSize;
222 }
223 
224 size_t HUF_decompress1X2_usingDTable(void *dst, size_t dstSize, const void *cSrc, size_t cSrcSize, const HUF_DTable *DTable)
225 {
226         DTableDesc dtd = HUF_getDTableDesc(DTable);
227         if (dtd.tableType != 0)
228                 return ERROR(GENERIC);
229         return HUF_decompress1X2_usingDTable_internal(dst, dstSize, cSrc, cSrcSize, DTable);
230 }
231 
232 size_t HUF_decompress1X2_DCtx_wksp(HUF_DTable *DCtx, void *dst, size_t dstSize, const void *cSrc, size_t cSrcSize, void *workspace, size_t workspaceSize)
233 {
234         const BYTE *ip = (const BYTE *)cSrc;
235 
236         size_t const hSize = HUF_readDTableX2_wksp(DCtx, cSrc, cSrcSize, workspace, workspaceSize);
237         if (HUF_isError(hSize))
238                 return hSize;
239         if (hSize >= cSrcSize)
240                 return ERROR(srcSize_wrong);
241         ip += hSize;
242         cSrcSize -= hSize;
243 
244         return HUF_decompress1X2_usingDTable_internal(dst, dstSize, ip, cSrcSize, DCtx);
245 }
246 
247 static size_t HUF_decompress4X2_usingDTable_internal(void *dst, size_t dstSize, const void *cSrc, size_t cSrcSize, const HUF_DTable *DTable)
248 {
249         /* Check */
250         if (cSrcSize < 10)
251                 return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
252 
253         {
254                 const BYTE *const istart = (const BYTE *)cSrc;
255                 BYTE *const ostart = (BYTE *)dst;
256                 BYTE *const oend = ostart + dstSize;
257                 const void *const dtPtr = DTable + 1;
258                 const HUF_DEltX2 *const dt = (const HUF_DEltX2 *)dtPtr;
259 
260                 /* Init */
261                 BIT_DStream_t bitD1;
262                 BIT_DStream_t bitD2;
263                 BIT_DStream_t bitD3;
264                 BIT_DStream_t bitD4;
265                 size_t const length1 = ZSTD_readLE16(istart);
266                 size_t const length2 = ZSTD_readLE16(istart + 2);
267                 size_t const length3 = ZSTD_readLE16(istart + 4);
268                 size_t const length4 = cSrcSize - (length1 + length2 + length3 + 6);
269                 const BYTE *const istart1 = istart + 6; /* jumpTable */
270                 const BYTE *const istart2 = istart1 + length1;
271                 const BYTE *const istart3 = istart2 + length2;
272                 const BYTE *const istart4 = istart3 + length3;
273                 const size_t segmentSize = (dstSize + 3) / 4;
274                 BYTE *const opStart2 = ostart + segmentSize;
275                 BYTE *const opStart3 = opStart2 + segmentSize;
276                 BYTE *const opStart4 = opStart3 + segmentSize;
277                 BYTE *op1 = ostart;
278                 BYTE *op2 = opStart2;
279                 BYTE *op3 = opStart3;
280                 BYTE *op4 = opStart4;
281                 U32 endSignal;
282                 DTableDesc const dtd = HUF_getDTableDesc(DTable);
283                 U32 const dtLog = dtd.tableLog;
284 
285                 if (length4 > cSrcSize)
286                         return ERROR(corruption_detected); /* overflow */
287                 {
288                         size_t const errorCode = BIT_initDStream(&bitD1, istart1, length1);
289                         if (HUF_isError(errorCode))
290                                 return errorCode;
291                 }
292                 {
293                         size_t const errorCode = BIT_initDStream(&bitD2, istart2, length2);
294                         if (HUF_isError(errorCode))
295                                 return errorCode;
296                 }
297                 {
298                         size_t const errorCode = BIT_initDStream(&bitD3, istart3, length3);
299                         if (HUF_isError(errorCode))
300                                 return errorCode;
301                 }
302                 {
303                         size_t const errorCode = BIT_initDStream(&bitD4, istart4, length4);
304                         if (HUF_isError(errorCode))
305                                 return errorCode;
306                 }
307 
308                 /* 16-32 symbols per loop (4-8 symbols per stream) */
309                 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
310                 for (; (endSignal == BIT_DStream_unfinished) && (op4 < (oend - 7));) {
311                         HUF_DECODE_SYMBOLX2_2(op1, &bitD1);
312                         HUF_DECODE_SYMBOLX2_2(op2, &bitD2);
313                         HUF_DECODE_SYMBOLX2_2(op3, &bitD3);
314                         HUF_DECODE_SYMBOLX2_2(op4, &bitD4);
315                         HUF_DECODE_SYMBOLX2_1(op1, &bitD1);
316                         HUF_DECODE_SYMBOLX2_1(op2, &bitD2);
317                         HUF_DECODE_SYMBOLX2_1(op3, &bitD3);
318                         HUF_DECODE_SYMBOLX2_1(op4, &bitD4);
319                         HUF_DECODE_SYMBOLX2_2(op1, &bitD1);
320                         HUF_DECODE_SYMBOLX2_2(op2, &bitD2);
321                         HUF_DECODE_SYMBOLX2_2(op3, &bitD3);
322                         HUF_DECODE_SYMBOLX2_2(op4, &bitD4);
323                         HUF_DECODE_SYMBOLX2_0(op1, &bitD1);
324                         HUF_DECODE_SYMBOLX2_0(op2, &bitD2);
325                         HUF_DECODE_SYMBOLX2_0(op3, &bitD3);
326                         HUF_DECODE_SYMBOLX2_0(op4, &bitD4);
327                         endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
328                 }
329 
330                 /* check corruption */
331                 if (op1 > opStart2)
332                         return ERROR(corruption_detected);
333                 if (op2 > opStart3)
334                         return ERROR(corruption_detected);
335                 if (op3 > opStart4)
336                         return ERROR(corruption_detected);
337                 /* note : op4 supposed already verified within main loop */
338 
339                 /* finish bitStreams one by one */
340                 HUF_decodeStreamX2(op1, &bitD1, opStart2, dt, dtLog);
341                 HUF_decodeStreamX2(op2, &bitD2, opStart3, dt, dtLog);
342                 HUF_decodeStreamX2(op3, &bitD3, opStart4, dt, dtLog);
343                 HUF_decodeStreamX2(op4, &bitD4, oend, dt, dtLog);
344 
345                 /* check */
346                 endSignal = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4);
347                 if (!endSignal)
348                         return ERROR(corruption_detected);
349 
350                 /* decoded size */
351                 return dstSize;
352         }
353 }
354 
355 size_t HUF_decompress4X2_usingDTable(void *dst, size_t dstSize, const void *cSrc, size_t cSrcSize, const HUF_DTable *DTable)
356 {
357         DTableDesc dtd = HUF_getDTableDesc(DTable);
358         if (dtd.tableType != 0)
359                 return ERROR(GENERIC);
360         return HUF_decompress4X2_usingDTable_internal(dst, dstSize, cSrc, cSrcSize, DTable);
361 }
362 
363 size_t HUF_decompress4X2_DCtx_wksp(HUF_DTable *dctx, void *dst, size_t dstSize, const void *cSrc, size_t cSrcSize, void *workspace, size_t workspaceSize)
364 {
365         const BYTE *ip = (const BYTE *)cSrc;
366 
367         size_t const hSize = HUF_readDTableX2_wksp(dctx, cSrc, cSrcSize, workspace, workspaceSize);
368         if (HUF_isError(hSize))
369                 return hSize;
370         if (hSize >= cSrcSize)
371                 return ERROR(srcSize_wrong);
372         ip += hSize;
373         cSrcSize -= hSize;
374 
375         return HUF_decompress4X2_usingDTable_internal(dst, dstSize, ip, cSrcSize, dctx);
376 }
377 
378 /* *************************/
379 /* double-symbols decoding */
380 /* *************************/
381 typedef struct {
382         U16 sequence;
383         BYTE nbBits;
384         BYTE length;
385 } HUF_DEltX4; /* double-symbols decoding */
386 
387 typedef struct {
388         BYTE symbol;
389         BYTE weight;
390 } sortedSymbol_t;
391 
392 /* HUF_fillDTableX4Level2() :
393  * `rankValOrigin` must be a table of at least (HUF_TABLELOG_MAX + 1) U32 */
394 static void HUF_fillDTableX4Level2(HUF_DEltX4 *DTable, U32 sizeLog, const U32 consumed, const U32 *rankValOrigin, const int minWeight,
395                                    const sortedSymbol_t *sortedSymbols, const U32 sortedListSize, U32 nbBitsBaseline, U16 baseSeq)
396 {
397         HUF_DEltX4 DElt;
398         U32 rankVal[HUF_TABLELOG_MAX + 1];
399 
400         /* get pre-calculated rankVal */
401         memcpy(rankVal, rankValOrigin, sizeof(rankVal));
402 
403         /* fill skipped values */
404         if (minWeight > 1) {
405                 U32 i, skipSize = rankVal[minWeight];
406                 ZSTD_writeLE16(&(DElt.sequence), baseSeq);
407                 DElt.nbBits = (BYTE)(consumed);
408                 DElt.length = 1;
409                 for (i = 0; i < skipSize; i++)
410                         DTable[i] = DElt;
411         }
412 
413         /* fill DTable */
414         {
415                 U32 s;
416                 for (s = 0; s < sortedListSize; s++) { /* note : sortedSymbols already skipped */
417                         const U32 symbol = sortedSymbols[s].symbol;
418                         const U32 weight = sortedSymbols[s].weight;
419                         const U32 nbBits = nbBitsBaseline - weight;
420                         const U32 length = 1 << (sizeLog - nbBits);
421                         const U32 start = rankVal[weight];
422                         U32 i = start;
423                         const U32 end = start + length;
424 
425                         ZSTD_writeLE16(&(DElt.sequence), (U16)(baseSeq + (symbol << 8)));
426                         DElt.nbBits = (BYTE)(nbBits + consumed);
427                         DElt.length = 2;
428                         do {
429                                 DTable[i++] = DElt;
430                         } while (i < end); /* since length >= 1 */
431 
432                         rankVal[weight] += length;
433                 }
434         }
435 }
436 
437 typedef U32 rankVal_t[HUF_TABLELOG_MAX][HUF_TABLELOG_MAX + 1];
438 typedef U32 rankValCol_t[HUF_TABLELOG_MAX + 1];
439 
440 static void HUF_fillDTableX4(HUF_DEltX4 *DTable, const U32 targetLog, const sortedSymbol_t *sortedList, const U32 sortedListSize, const U32 *rankStart,
441                              rankVal_t rankValOrigin, const U32 maxWeight, const U32 nbBitsBaseline)
442 {
443         U32 rankVal[HUF_TABLELOG_MAX + 1];
444         const int scaleLog = nbBitsBaseline - targetLog; /* note : targetLog >= srcLog, hence scaleLog <= 1 */
445         const U32 minBits = nbBitsBaseline - maxWeight;
446         U32 s;
447 
448         memcpy(rankVal, rankValOrigin, sizeof(rankVal));
449 
450         /* fill DTable */
451         for (s = 0; s < sortedListSize; s++) {
452                 const U16 symbol = sortedList[s].symbol;
453                 const U32 weight = sortedList[s].weight;
454                 const U32 nbBits = nbBitsBaseline - weight;
455                 const U32 start = rankVal[weight];
456                 const U32 length = 1 << (targetLog - nbBits);
457 
458                 if (targetLog - nbBits >= minBits) { /* enough room for a second symbol */
459                         U32 sortedRank;
460                         int minWeight = nbBits + scaleLog;
461                         if (minWeight < 1)
462                                 minWeight = 1;
463                         sortedRank = rankStart[minWeight];
464                         HUF_fillDTableX4Level2(DTable + start, targetLog - nbBits, nbBits, rankValOrigin[nbBits], minWeight, sortedList + sortedRank,
465                                                sortedListSize - sortedRank, nbBitsBaseline, symbol);
466                 } else {
467                         HUF_DEltX4 DElt;
468                         ZSTD_writeLE16(&(DElt.sequence), symbol);
469                         DElt.nbBits = (BYTE)(nbBits);
470                         DElt.length = 1;
471                         {
472                                 U32 const end = start + length;
473                                 U32 u;
474                                 for (u = start; u < end; u++)
475                                         DTable[u] = DElt;
476                         }
477                 }
478                 rankVal[weight] += length;
479         }
480 }
481 
482 size_t HUF_readDTableX4_wksp(HUF_DTable *DTable, const void *src, size_t srcSize, void *workspace, size_t workspaceSize)
483 {
484         U32 tableLog, maxW, sizeOfSort, nbSymbols;
485         DTableDesc dtd = HUF_getDTableDesc(DTable);
486         U32 const maxTableLog = dtd.maxTableLog;
487         size_t iSize;
488         void *dtPtr = DTable + 1; /* force compiler to avoid strict-aliasing */
489         HUF_DEltX4 *const dt = (HUF_DEltX4 *)dtPtr;
490         U32 *rankStart;
491 
492         rankValCol_t *rankVal;
493         U32 *rankStats;
494         U32 *rankStart0;
495         sortedSymbol_t *sortedSymbol;
496         BYTE *weightList;
497         size_t spaceUsed32 = 0;
498 
499         HUF_STATIC_ASSERT((sizeof(rankValCol_t) & 3) == 0);
500 
501         rankVal = (rankValCol_t *)((U32 *)workspace + spaceUsed32);
502         spaceUsed32 += (sizeof(rankValCol_t) * HUF_TABLELOG_MAX) >> 2;
503         rankStats = (U32 *)workspace + spaceUsed32;
504         spaceUsed32 += HUF_TABLELOG_MAX + 1;
505         rankStart0 = (U32 *)workspace + spaceUsed32;
506         spaceUsed32 += HUF_TABLELOG_MAX + 2;
507         sortedSymbol = (sortedSymbol_t *)((U32 *)workspace + spaceUsed32);
508         spaceUsed32 += ALIGN(sizeof(sortedSymbol_t) * (HUF_SYMBOLVALUE_MAX + 1), sizeof(U32)) >> 2;
509         weightList = (BYTE *)((U32 *)workspace + spaceUsed32);
510         spaceUsed32 += ALIGN(HUF_SYMBOLVALUE_MAX + 1, sizeof(U32)) >> 2;
511 
512         if ((spaceUsed32 << 2) > workspaceSize)
513                 return ERROR(tableLog_tooLarge);
514         workspace = (U32 *)workspace + spaceUsed32;
515         workspaceSize -= (spaceUsed32 << 2);
516 
517         rankStart = rankStart0 + 1;
518         memset(rankStats, 0, sizeof(U32) * (2 * HUF_TABLELOG_MAX + 2 + 1));
519 
520         HUF_STATIC_ASSERT(sizeof(HUF_DEltX4) == sizeof(HUF_DTable)); /* if compiler fails here, assertion is wrong */
521         if (maxTableLog > HUF_TABLELOG_MAX)
522                 return ERROR(tableLog_tooLarge);
523         /* memset(weightList, 0, sizeof(weightList)); */ /* is not necessary, even though some analyzer complain ... */
524 
525         iSize = HUF_readStats_wksp(weightList, HUF_SYMBOLVALUE_MAX + 1, rankStats, &nbSymbols, &tableLog, src, srcSize, workspace, workspaceSize);
526         if (HUF_isError(iSize))
527                 return iSize;
528 
529         /* check result */
530         if (tableLog > maxTableLog)
531                 return ERROR(tableLog_tooLarge); /* DTable can't fit code depth */
532 
533         /* find maxWeight */
534         for (maxW = tableLog; rankStats[maxW] == 0; maxW--) {
535         } /* necessarily finds a solution before 0 */
536 
537         /* Get start index of each weight */
538         {
539                 U32 w, nextRankStart = 0;
540                 for (w = 1; w < maxW + 1; w++) {
541                         U32 curr = nextRankStart;
542                         nextRankStart += rankStats[w];
543                         rankStart[w] = curr;
544                 }
545                 rankStart[0] = nextRankStart; /* put all 0w symbols at the end of sorted list*/
546                 sizeOfSort = nextRankStart;
547         }
548 
549         /* sort symbols by weight */
550         {
551                 U32 s;
552                 for (s = 0; s < nbSymbols; s++) {
553                         U32 const w = weightList[s];
554                         U32 const r = rankStart[w]++;
555                         sortedSymbol[r].symbol = (BYTE)s;
556                         sortedSymbol[r].weight = (BYTE)w;
557                 }
558                 rankStart[0] = 0; /* forget 0w symbols; this is beginning of weight(1) */
559         }
560 
561         /* Build rankVal */
562         {
563                 U32 *const rankVal0 = rankVal[0];
564                 {
565                         int const rescale = (maxTableLog - tableLog) - 1; /* tableLog <= maxTableLog */
566                         U32 nextRankVal = 0;
567                         U32 w;
568                         for (w = 1; w < maxW + 1; w++) {
569                                 U32 curr = nextRankVal;
570                                 nextRankVal += rankStats[w] << (w + rescale);
571                                 rankVal0[w] = curr;
572                         }
573                 }
574                 {
575                         U32 const minBits = tableLog + 1 - maxW;
576                         U32 consumed;
577                         for (consumed = minBits; consumed < maxTableLog - minBits + 1; consumed++) {
578                                 U32 *const rankValPtr = rankVal[consumed];
579                                 U32 w;
580                                 for (w = 1; w < maxW + 1; w++) {
581                                         rankValPtr[w] = rankVal0[w] >> consumed;
582                                 }
583                         }
584                 }
585         }
586 
587         HUF_fillDTableX4(dt, maxTableLog, sortedSymbol, sizeOfSort, rankStart0, rankVal, maxW, tableLog + 1);
588 
589         dtd.tableLog = (BYTE)maxTableLog;
590         dtd.tableType = 1;
591         memcpy(DTable, &dtd, sizeof(dtd));
592         return iSize;
593 }
594 
595 static U32 HUF_decodeSymbolX4(void *op, BIT_DStream_t *DStream, const HUF_DEltX4 *dt, const U32 dtLog)
596 {
597         size_t const val = BIT_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
598         memcpy(op, dt + val, 2);
599         BIT_skipBits(DStream, dt[val].nbBits);
600         return dt[val].length;
601 }
602 
603 static U32 HUF_decodeLastSymbolX4(void *op, BIT_DStream_t *DStream, const HUF_DEltX4 *dt, const U32 dtLog)
604 {
605         size_t const val = BIT_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
606         memcpy(op, dt + val, 1);
607         if (dt[val].length == 1)
608                 BIT_skipBits(DStream, dt[val].nbBits);
609         else {
610                 if (DStream->bitsConsumed < (sizeof(DStream->bitContainer) * 8)) {
611                         BIT_skipBits(DStream, dt[val].nbBits);
612                         if (DStream->bitsConsumed > (sizeof(DStream->bitContainer) * 8))
613                                 /* ugly hack; works only because it's the last symbol. Note : can't easily extract nbBits from just this symbol */
614                                 DStream->bitsConsumed = (sizeof(DStream->bitContainer) * 8);
615                 }
616         }
617         return 1;
618 }
619 
620 #define HUF_DECODE_SYMBOLX4_0(ptr, DStreamPtr) ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
621 
622 #define HUF_DECODE_SYMBOLX4_1(ptr, DStreamPtr)         \
623         if (ZSTD_64bits() || (HUF_TABLELOG_MAX <= 12)) \
624         ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
625 
626 #define HUF_DECODE_SYMBOLX4_2(ptr, DStreamPtr) \
627         if (ZSTD_64bits())                     \
628         ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
629 
630 FORCE_INLINE size_t HUF_decodeStreamX4(BYTE *p, BIT_DStream_t *bitDPtr, BYTE *const pEnd, const HUF_DEltX4 *const dt, const U32 dtLog)
631 {
632         BYTE *const pStart = p;
633 
634         /* up to 8 symbols at a time */
635         while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) & (p < pEnd - (sizeof(bitDPtr->bitContainer) - 1))) {
636                 HUF_DECODE_SYMBOLX4_2(p, bitDPtr);
637                 HUF_DECODE_SYMBOLX4_1(p, bitDPtr);
638                 HUF_DECODE_SYMBOLX4_2(p, bitDPtr);
639                 HUF_DECODE_SYMBOLX4_0(p, bitDPtr);
640         }
641 
642         /* closer to end : up to 2 symbols at a time */
643         while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) & (p <= pEnd - 2))
644                 HUF_DECODE_SYMBOLX4_0(p, bitDPtr);
645 
646         while (p <= pEnd - 2)
647                 HUF_DECODE_SYMBOLX4_0(p, bitDPtr); /* no need to reload : reached the end of DStream */
648 
649         if (p < pEnd)
650                 p += HUF_decodeLastSymbolX4(p, bitDPtr, dt, dtLog);
651 
652         return p - pStart;
653 }
654 
655 static size_t HUF_decompress1X4_usingDTable_internal(void *dst, size_t dstSize, const void *cSrc, size_t cSrcSize, const HUF_DTable *DTable)
656 {
657         BIT_DStream_t bitD;
658 
659         /* Init */
660         {
661                 size_t const errorCode = BIT_initDStream(&bitD, cSrc, cSrcSize);
662                 if (HUF_isError(errorCode))
663                         return errorCode;
664         }
665 
666         /* decode */
667         {
668                 BYTE *const ostart = (BYTE *)dst;
669                 BYTE *const oend = ostart + dstSize;
670                 const void *const dtPtr = DTable + 1; /* force compiler to not use strict-aliasing */
671                 const HUF_DEltX4 *const dt = (const HUF_DEltX4 *)dtPtr;
672                 DTableDesc const dtd = HUF_getDTableDesc(DTable);
673                 HUF_decodeStreamX4(ostart, &bitD, oend, dt, dtd.tableLog);
674         }
675 
676         /* check */
677         if (!BIT_endOfDStream(&bitD))
678                 return ERROR(corruption_detected);
679 
680         /* decoded size */
681         return dstSize;
682 }
683 
684 size_t HUF_decompress1X4_usingDTable(void *dst, size_t dstSize, const void *cSrc, size_t cSrcSize, const HUF_DTable *DTable)
685 {
686         DTableDesc dtd = HUF_getDTableDesc(DTable);
687         if (dtd.tableType != 1)
688                 return ERROR(GENERIC);
689         return HUF_decompress1X4_usingDTable_internal(dst, dstSize, cSrc, cSrcSize, DTable);
690 }
691 
692 size_t HUF_decompress1X4_DCtx_wksp(HUF_DTable *DCtx, void *dst, size_t dstSize, const void *cSrc, size_t cSrcSize, void *workspace, size_t workspaceSize)
693 {
694         const BYTE *ip = (const BYTE *)cSrc;
695 
696         size_t const hSize = HUF_readDTableX4_wksp(DCtx, cSrc, cSrcSize, workspace, workspaceSize);
697         if (HUF_isError(hSize))
698                 return hSize;
699         if (hSize >= cSrcSize)
700                 return ERROR(srcSize_wrong);
701         ip += hSize;
702         cSrcSize -= hSize;
703 
704         return HUF_decompress1X4_usingDTable_internal(dst, dstSize, ip, cSrcSize, DCtx);
705 }
706 
707 static size_t HUF_decompress4X4_usingDTable_internal(void *dst, size_t dstSize, const void *cSrc, size_t cSrcSize, const HUF_DTable *DTable)
708 {
709         if (cSrcSize < 10)
710                 return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
711 
712         {
713                 const BYTE *const istart = (const BYTE *)cSrc;
714                 BYTE *const ostart = (BYTE *)dst;
715                 BYTE *const oend = ostart + dstSize;
716                 const void *const dtPtr = DTable + 1;
717                 const HUF_DEltX4 *const dt = (const HUF_DEltX4 *)dtPtr;
718 
719                 /* Init */
720                 BIT_DStream_t bitD1;
721                 BIT_DStream_t bitD2;
722                 BIT_DStream_t bitD3;
723                 BIT_DStream_t bitD4;
724                 size_t const length1 = ZSTD_readLE16(istart);
725                 size_t const length2 = ZSTD_readLE16(istart + 2);
726                 size_t const length3 = ZSTD_readLE16(istart + 4);
727                 size_t const length4 = cSrcSize - (length1 + length2 + length3 + 6);
728                 const BYTE *const istart1 = istart + 6; /* jumpTable */
729                 const BYTE *const istart2 = istart1 + length1;
730                 const BYTE *const istart3 = istart2 + length2;
731                 const BYTE *const istart4 = istart3 + length3;
732                 size_t const segmentSize = (dstSize + 3) / 4;
733                 BYTE *const opStart2 = ostart + segmentSize;
734                 BYTE *const opStart3 = opStart2 + segmentSize;
735                 BYTE *const opStart4 = opStart3 + segmentSize;
736                 BYTE *op1 = ostart;
737                 BYTE *op2 = opStart2;
738                 BYTE *op3 = opStart3;
739                 BYTE *op4 = opStart4;
740                 U32 endSignal;
741                 DTableDesc const dtd = HUF_getDTableDesc(DTable);
742                 U32 const dtLog = dtd.tableLog;
743 
744                 if (length4 > cSrcSize)
745                         return ERROR(corruption_detected); /* overflow */
746                 {
747                         size_t const errorCode = BIT_initDStream(&bitD1, istart1, length1);
748                         if (HUF_isError(errorCode))
749                                 return errorCode;
750                 }
751                 {
752                         size_t const errorCode = BIT_initDStream(&bitD2, istart2, length2);
753                         if (HUF_isError(errorCode))
754                                 return errorCode;
755                 }
756                 {
757                         size_t const errorCode = BIT_initDStream(&bitD3, istart3, length3);
758                         if (HUF_isError(errorCode))
759                                 return errorCode;
760                 }
761                 {
762                         size_t const errorCode = BIT_initDStream(&bitD4, istart4, length4);
763                         if (HUF_isError(errorCode))
764                                 return errorCode;
765                 }
766 
767                 /* 16-32 symbols per loop (4-8 symbols per stream) */
768                 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
769                 for (; (endSignal == BIT_DStream_unfinished) & (op4 < (oend - (sizeof(bitD4.bitContainer) - 1)));) {
770                         HUF_DECODE_SYMBOLX4_2(op1, &bitD1);
771                         HUF_DECODE_SYMBOLX4_2(op2, &bitD2);
772                         HUF_DECODE_SYMBOLX4_2(op3, &bitD3);
773                         HUF_DECODE_SYMBOLX4_2(op4, &bitD4);
774                         HUF_DECODE_SYMBOLX4_1(op1, &bitD1);
775                         HUF_DECODE_SYMBOLX4_1(op2, &bitD2);
776                         HUF_DECODE_SYMBOLX4_1(op3, &bitD3);
777                         HUF_DECODE_SYMBOLX4_1(op4, &bitD4);
778                         HUF_DECODE_SYMBOLX4_2(op1, &bitD1);
779                         HUF_DECODE_SYMBOLX4_2(op2, &bitD2);
780                         HUF_DECODE_SYMBOLX4_2(op3, &bitD3);
781                         HUF_DECODE_SYMBOLX4_2(op4, &bitD4);
782                         HUF_DECODE_SYMBOLX4_0(op1, &bitD1);
783                         HUF_DECODE_SYMBOLX4_0(op2, &bitD2);
784                         HUF_DECODE_SYMBOLX4_0(op3, &bitD3);
785                         HUF_DECODE_SYMBOLX4_0(op4, &bitD4);
786 
787                         endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
788                 }
789 
790                 /* check corruption */
791                 if (op1 > opStart2)
792                         return ERROR(corruption_detected);
793                 if (op2 > opStart3)
794                         return ERROR(corruption_detected);
795                 if (op3 > opStart4)
796                         return ERROR(corruption_detected);
797                 /* note : op4 already verified within main loop */
798 
799                 /* finish bitStreams one by one */
800                 HUF_decodeStreamX4(op1, &bitD1, opStart2, dt, dtLog);
801                 HUF_decodeStreamX4(op2, &bitD2, opStart3, dt, dtLog);
802                 HUF_decodeStreamX4(op3, &bitD3, opStart4, dt, dtLog);
803                 HUF_decodeStreamX4(op4, &bitD4, oend, dt, dtLog);
804 
805                 /* check */
806                 {
807                         U32 const endCheck = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4);
808                         if (!endCheck)
809                                 return ERROR(corruption_detected);
810                 }
811 
812                 /* decoded size */
813                 return dstSize;
814         }
815 }
816 
817 size_t HUF_decompress4X4_usingDTable(void *dst, size_t dstSize, const void *cSrc, size_t cSrcSize, const HUF_DTable *DTable)
818 {
819         DTableDesc dtd = HUF_getDTableDesc(DTable);
820         if (dtd.tableType != 1)
821                 return ERROR(GENERIC);
822         return HUF_decompress4X4_usingDTable_internal(dst, dstSize, cSrc, cSrcSize, DTable);
823 }
824 
825 size_t HUF_decompress4X4_DCtx_wksp(HUF_DTable *dctx, void *dst, size_t dstSize, const void *cSrc, size_t cSrcSize, void *workspace, size_t workspaceSize)
826 {
827         const BYTE *ip = (const BYTE *)cSrc;
828 
829         size_t hSize = HUF_readDTableX4_wksp(dctx, cSrc, cSrcSize, workspace, workspaceSize);
830         if (HUF_isError(hSize))
831                 return hSize;
832         if (hSize >= cSrcSize)
833                 return ERROR(srcSize_wrong);
834         ip += hSize;
835         cSrcSize -= hSize;
836 
837         return HUF_decompress4X4_usingDTable_internal(dst, dstSize, ip, cSrcSize, dctx);
838 }
839 
840 /* ********************************/
841 /* Generic decompression selector */
842 /* ********************************/
843 
844 size_t HUF_decompress1X_usingDTable(void *dst, size_t maxDstSize, const void *cSrc, size_t cSrcSize, const HUF_DTable *DTable)
845 {
846         DTableDesc const dtd = HUF_getDTableDesc(DTable);
847         return dtd.tableType ? HUF_decompress1X4_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable)
848                              : HUF_decompress1X2_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable);
849 }
850 
851 size_t HUF_decompress4X_usingDTable(void *dst, size_t maxDstSize, const void *cSrc, size_t cSrcSize, const HUF_DTable *DTable)
852 {
853         DTableDesc const dtd = HUF_getDTableDesc(DTable);
854         return dtd.tableType ? HUF_decompress4X4_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable)
855                              : HUF_decompress4X2_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable);
856 }
857 
858 typedef struct {
859         U32 tableTime;
860         U32 decode256Time;
861 } algo_time_t;
862 static const algo_time_t algoTime[16 /* Quantization */][3 /* single, double, quad */] = {
863     /* single, double, quad */
864     {{0, 0}, {1, 1}, {2, 2}},                /* Q==0 : impossible */
865     {{0, 0}, {1, 1}, {2, 2}},                /* Q==1 : impossible */
866     {{38, 130}, {1313, 74}, {2151, 38}},     /* Q == 2 : 12-18% */
867     {{448, 128}, {1353, 74}, {2238, 41}},    /* Q == 3 : 18-25% */
868     {{556, 128}, {1353, 74}, {2238, 47}},    /* Q == 4 : 25-32% */
869     {{714, 128}, {1418, 74}, {2436, 53}},    /* Q == 5 : 32-38% */
870     {{883, 128}, {1437, 74}, {2464, 61}},    /* Q == 6 : 38-44% */
871     {{897, 128}, {1515, 75}, {2622, 68}},    /* Q == 7 : 44-50% */
872     {{926, 128}, {1613, 75}, {2730, 75}},    /* Q == 8 : 50-56% */
873     {{947, 128}, {1729, 77}, {3359, 77}},    /* Q == 9 : 56-62% */
874     {{1107, 128}, {2083, 81}, {4006, 84}},   /* Q ==10 : 62-69% */
875     {{1177, 128}, {2379, 87}, {4785, 88}},   /* Q ==11 : 69-75% */
876     {{1242, 128}, {2415, 93}, {5155, 84}},   /* Q ==12 : 75-81% */
877     {{1349, 128}, {2644, 106}, {5260, 106}}, /* Q ==13 : 81-87% */
878     {{1455, 128}, {2422, 124}, {4174, 124}}, /* Q ==14 : 87-93% */
879     {{722, 128}, {1891, 145}, {1936, 146}},  /* Q ==15 : 93-99% */
880 };
881 
882 /** HUF_selectDecoder() :
883 *   Tells which decoder is likely to decode faster,
884 *   based on a set of pre-determined metrics.
885 *   @return : 0==HUF_decompress4X2, 1==HUF_decompress4X4 .
886 *   Assumption : 0 < cSrcSize < dstSize <= 128 KB */
887 U32 HUF_selectDecoder(size_t dstSize, size_t cSrcSize)
888 {
889         /* decoder timing evaluation */
890         U32 const Q = (U32)(cSrcSize * 16 / dstSize); /* Q < 16 since dstSize > cSrcSize */
891         U32 const D256 = (U32)(dstSize >> 8);
892         U32 const DTime0 = algoTime[Q][0].tableTime + (algoTime[Q][0].decode256Time * D256);
893         U32 DTime1 = algoTime[Q][1].tableTime + (algoTime[Q][1].decode256Time * D256);
894         DTime1 += DTime1 >> 3; /* advantage to algorithm using less memory, for cache eviction */
895 
896         return DTime1 < DTime0;
897 }
898 
899 typedef size_t (*decompressionAlgo)(void *dst, size_t dstSize, const void *cSrc, size_t cSrcSize);
900 
901 size_t HUF_decompress4X_DCtx_wksp(HUF_DTable *dctx, void *dst, size_t dstSize, const void *cSrc, size_t cSrcSize, void *workspace, size_t workspaceSize)
902 {
903         /* validation checks */
904         if (dstSize == 0)
905                 return ERROR(dstSize_tooSmall);
906         if (cSrcSize > dstSize)
907                 return ERROR(corruption_detected); /* invalid */
908         if (cSrcSize == dstSize) {
909                 memcpy(dst, cSrc, dstSize);
910                 return dstSize;
911         } /* not compressed */
912         if (cSrcSize == 1) {
913                 memset(dst, *(const BYTE *)cSrc, dstSize);
914                 return dstSize;
915         } /* RLE */
916 
917         {
918                 U32 const algoNb = HUF_selectDecoder(dstSize, cSrcSize);
919                 return algoNb ? HUF_decompress4X4_DCtx_wksp(dctx, dst, dstSize, cSrc, cSrcSize, workspace, workspaceSize)
920                               : HUF_decompress4X2_DCtx_wksp(dctx, dst, dstSize, cSrc, cSrcSize, workspace, workspaceSize);
921         }
922 }
923 
924 size_t HUF_decompress4X_hufOnly_wksp(HUF_DTable *dctx, void *dst, size_t dstSize, const void *cSrc, size_t cSrcSize, void *workspace, size_t workspaceSize)
925 {
926         /* validation checks */
927         if (dstSize == 0)
928                 return ERROR(dstSize_tooSmall);
929         if ((cSrcSize >= dstSize) || (cSrcSize <= 1))
930                 return ERROR(corruption_detected); /* invalid */
931 
932         {
933                 U32 const algoNb = HUF_selectDecoder(dstSize, cSrcSize);
934                 return algoNb ? HUF_decompress4X4_DCtx_wksp(dctx, dst, dstSize, cSrc, cSrcSize, workspace, workspaceSize)
935                               : HUF_decompress4X2_DCtx_wksp(dctx, dst, dstSize, cSrc, cSrcSize, workspace, workspaceSize);
936         }
937 }
938 
939 size_t HUF_decompress1X_DCtx_wksp(HUF_DTable *dctx, void *dst, size_t dstSize, const void *cSrc, size_t cSrcSize, void *workspace, size_t workspaceSize)
940 {
941         /* validation checks */
942         if (dstSize == 0)
943                 return ERROR(dstSize_tooSmall);
944         if (cSrcSize > dstSize)
945                 return ERROR(corruption_detected); /* invalid */
946         if (cSrcSize == dstSize) {
947                 memcpy(dst, cSrc, dstSize);
948                 return dstSize;
949         } /* not compressed */
950         if (cSrcSize == 1) {
951                 memset(dst, *(const BYTE *)cSrc, dstSize);
952                 return dstSize;
953         } /* RLE */
954 
955         {
956                 U32 const algoNb = HUF_selectDecoder(dstSize, cSrcSize);
957                 return algoNb ? HUF_decompress1X4_DCtx_wksp(dctx, dst, dstSize, cSrc, cSrcSize, workspace, workspaceSize)
958                               : HUF_decompress1X2_DCtx_wksp(dctx, dst, dstSize, cSrc, cSrcSize, workspace, workspaceSize);
959         }
960 }
961 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp