huf_decompress.c 32 KB

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