lib/zstd/huf_decompress.c

   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 }