huf_decompress.c 31 KB

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