LXR linux/lib/zstd/huf

   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
  67typedef struct {
  68        BYTE maxTableLog;
  69        BYTE tableType;
  70        BYTE tableLog;
  71        BYTE reserved;
  72} DTableDesc;
  73
  74static 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
  85typedef struct {
  86        BYTE byte;
  87        BYTE nbBits;
  88} HUF_DEltX2; /* single-symbol decoding */
  89
  90size_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
 158static 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
 176FORCE_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
 199static 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
 224size_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
 232size_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
 247static 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
 355size_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
 363size_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/* *************************/
 381typedef struct {
 382        U16 sequence;
 383        BYTE nbBits;
 384        BYTE length;
 385} HUF_DEltX4; /* double-symbols decoding */
 386
 387typedef 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 */
 394static 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
 437typedef U32 rankVal_t[HUF_TABLELOG_MAX][HUF_TABLELOG_MAX + 1];
 438typedef U32 rankValCol_t[HUF_TABLELOG_MAX + 1];
 439
 440static 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
 482size_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
 595static 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
 603static 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
 630FORCE_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
 655static 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
 684size_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
 692size_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
 707static 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
 817size_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
 825size_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
 844size_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
 851size_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
 858typedef struct {
 859        U32 tableTime;
 860        U32 decode256Time;
 861} algo_time_t;
 862static 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 */
 887U32 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
 899typedef size_t (*decompressionAlgo)(void *dst, size_t dstSize, const void *cSrc, size_t cSrcSize);
 900
 901size_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
 924size_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
 939size_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