decompress.c 80 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098209921002101210221032104210521062107210821092110211121122113211421152116211721182119212021212122212321242125212621272128212921302131213221332134213521362137213821392140214121422143214421452146214721482149215021512152215321542155215621572158215921602161216221632164216521662167216821692170217121722173217421752176217721782179218021812182218321842185218621872188218921902191219221932194219521962197219821992200220122022203220422052206220722082209221022112212221322142215221622172218221922202221222222232224222522262227222822292230223122322233223422352236223722382239224022412242224322442245224622472248224922502251225222532254225522562257225822592260226122622263226422652266226722682269227022712272227322742275227622772278227922802281228222832284228522862287228822892290229122922293229422952296229722982299230023012302230323042305230623072308230923102311231223132314231523162317231823192320232123222323232423252326232723282329233023312332233323342335233623372338233923402341234223432344234523462347234823492350235123522353235423552356235723582359236023612362236323642365236623672368236923702371237223732374237523762377237823792380238123822383238423852386238723882389239023912392239323942395239623972398239924002401240224032404240524062407240824092410241124122413241424152416241724182419242024212422242324242425242624272428242924302431243224332434243524362437243824392440244124422443244424452446244724482449245024512452245324542455245624572458245924602461246224632464246524662467246824692470247124722473247424752476247724782479248024812482248324842485248624872488248924902491249224932494249524962497249824992500250125022503250425052506250725082509251025112512251325142515
  1. // SPDX-License-Identifier: (GPL-2.0 or BSD-3-Clause-Clear)
  2. /**
  3. * Copyright (c) 2016-present, Yann Collet, Facebook, Inc.
  4. * All rights reserved.
  5. */
  6. /* ***************************************************************
  7. * Tuning parameters
  8. *****************************************************************/
  9. /*!
  10. * MAXWINDOWSIZE_DEFAULT :
  11. * maximum window size accepted by DStream, by default.
  12. * Frames requiring more memory will be rejected.
  13. */
  14. #ifndef ZSTD_MAXWINDOWSIZE_DEFAULT
  15. #define ZSTD_MAXWINDOWSIZE_DEFAULT ((1 << ZSTD_WINDOWLOG_MAX) + 1) /* defined within zstd.h */
  16. #endif
  17. /*-*******************************************************
  18. * Dependencies
  19. *********************************************************/
  20. #include "fse.h"
  21. #include "huf.h"
  22. #include "mem.h" /* low level memory routines */
  23. #include "zstd_internal.h"
  24. #include <linux/kernel.h>
  25. #include <linux/compat.h>
  26. #include <linux/string.h> /* memcpy, memmove, memset */
  27. #define ZSTD_PREFETCH(ptr) __builtin_prefetch(ptr, 0, 0)
  28. /*-*************************************
  29. * Macros
  30. ***************************************/
  31. #define ZSTD_isError ERR_isError /* for inlining */
  32. #define FSE_isError ERR_isError
  33. #define HUF_isError ERR_isError
  34. /*_*******************************************************
  35. * Memory operations
  36. **********************************************************/
  37. static void ZSTD_copy4(void *dst, const void *src) { memcpy(dst, src, 4); }
  38. /*-*************************************************************
  39. * Context management
  40. ***************************************************************/
  41. typedef enum {
  42. ZSTDds_getFrameHeaderSize,
  43. ZSTDds_decodeFrameHeader,
  44. ZSTDds_decodeBlockHeader,
  45. ZSTDds_decompressBlock,
  46. ZSTDds_decompressLastBlock,
  47. ZSTDds_checkChecksum,
  48. ZSTDds_decodeSkippableHeader,
  49. ZSTDds_skipFrame
  50. } ZSTD_dStage;
  51. typedef struct {
  52. FSE_DTable LLTable[FSE_DTABLE_SIZE_U32(LLFSELog)];
  53. FSE_DTable OFTable[FSE_DTABLE_SIZE_U32(OffFSELog)];
  54. FSE_DTable MLTable[FSE_DTABLE_SIZE_U32(MLFSELog)];
  55. HUF_DTable hufTable[HUF_DTABLE_SIZE(HufLog)]; /* can accommodate HUF_decompress4X */
  56. U64 workspace[HUF_DECOMPRESS_WORKSPACE_SIZE_U32 / 2];
  57. U32 rep[ZSTD_REP_NUM];
  58. } ZSTD_entropyTables_t;
  59. struct ZSTD_DCtx_s {
  60. const FSE_DTable *LLTptr;
  61. const FSE_DTable *MLTptr;
  62. const FSE_DTable *OFTptr;
  63. const HUF_DTable *HUFptr;
  64. ZSTD_entropyTables_t entropy;
  65. const void *previousDstEnd; /* detect continuity */
  66. const void *base; /* start of curr segment */
  67. const void *vBase; /* virtual start of previous segment if it was just before curr one */
  68. const void *dictEnd; /* end of previous segment */
  69. size_t expected;
  70. ZSTD_frameParams fParams;
  71. blockType_e bType; /* used in ZSTD_decompressContinue(), to transfer blockType between header decoding and block decoding stages */
  72. ZSTD_dStage stage;
  73. U32 litEntropy;
  74. U32 fseEntropy;
  75. struct xxh64_state xxhState;
  76. size_t headerSize;
  77. U32 dictID;
  78. const BYTE *litPtr;
  79. ZSTD_customMem customMem;
  80. size_t litSize;
  81. size_t rleSize;
  82. BYTE litBuffer[ZSTD_BLOCKSIZE_ABSOLUTEMAX + WILDCOPY_OVERLENGTH];
  83. BYTE headerBuffer[ZSTD_FRAMEHEADERSIZE_MAX];
  84. }; /* typedef'd to ZSTD_DCtx within "zstd.h" */
  85. size_t ZSTD_DCtxWorkspaceBound(void) { return ZSTD_ALIGN(sizeof(ZSTD_stack)) + ZSTD_ALIGN(sizeof(ZSTD_DCtx)); }
  86. size_t ZSTD_decompressBegin(ZSTD_DCtx *dctx)
  87. {
  88. dctx->expected = ZSTD_frameHeaderSize_prefix;
  89. dctx->stage = ZSTDds_getFrameHeaderSize;
  90. dctx->previousDstEnd = NULL;
  91. dctx->base = NULL;
  92. dctx->vBase = NULL;
  93. dctx->dictEnd = NULL;
  94. dctx->entropy.hufTable[0] = (HUF_DTable)((HufLog)*0x1000001); /* cover both little and big endian */
  95. dctx->litEntropy = dctx->fseEntropy = 0;
  96. dctx->dictID = 0;
  97. ZSTD_STATIC_ASSERT(sizeof(dctx->entropy.rep) == sizeof(repStartValue));
  98. memcpy(dctx->entropy.rep, repStartValue, sizeof(repStartValue)); /* initial repcodes */
  99. dctx->LLTptr = dctx->entropy.LLTable;
  100. dctx->MLTptr = dctx->entropy.MLTable;
  101. dctx->OFTptr = dctx->entropy.OFTable;
  102. dctx->HUFptr = dctx->entropy.hufTable;
  103. return 0;
  104. }
  105. ZSTD_DCtx *ZSTD_createDCtx_advanced(ZSTD_customMem customMem)
  106. {
  107. ZSTD_DCtx *dctx;
  108. if (!customMem.customAlloc || !customMem.customFree)
  109. return NULL;
  110. dctx = (ZSTD_DCtx *)ZSTD_malloc(sizeof(ZSTD_DCtx), customMem);
  111. if (!dctx)
  112. return NULL;
  113. memcpy(&dctx->customMem, &customMem, sizeof(customMem));
  114. ZSTD_decompressBegin(dctx);
  115. return dctx;
  116. }
  117. ZSTD_DCtx *ZSTD_initDCtx(void *workspace, size_t workspaceSize)
  118. {
  119. ZSTD_customMem const stackMem = ZSTD_initStack(workspace, workspaceSize);
  120. return ZSTD_createDCtx_advanced(stackMem);
  121. }
  122. size_t ZSTD_freeDCtx(ZSTD_DCtx *dctx)
  123. {
  124. if (dctx == NULL)
  125. return 0; /* support free on NULL */
  126. ZSTD_free(dctx, dctx->customMem);
  127. return 0; /* reserved as a potential error code in the future */
  128. }
  129. void ZSTD_copyDCtx(ZSTD_DCtx *dstDCtx, const ZSTD_DCtx *srcDCtx)
  130. {
  131. size_t const workSpaceSize = (ZSTD_BLOCKSIZE_ABSOLUTEMAX + WILDCOPY_OVERLENGTH) + ZSTD_frameHeaderSize_max;
  132. memcpy(dstDCtx, srcDCtx, sizeof(ZSTD_DCtx) - workSpaceSize); /* no need to copy workspace */
  133. }
  134. static void ZSTD_refDDict(ZSTD_DCtx *dstDCtx, const ZSTD_DDict *ddict);
  135. /*-*************************************************************
  136. * Decompression section
  137. ***************************************************************/
  138. /*! ZSTD_isFrame() :
  139. * Tells if the content of `buffer` starts with a valid Frame Identifier.
  140. * Note : Frame Identifier is 4 bytes. If `size < 4`, @return will always be 0.
  141. * Note 2 : Legacy Frame Identifiers are considered valid only if Legacy Support is enabled.
  142. * Note 3 : Skippable Frame Identifiers are considered valid. */
  143. unsigned ZSTD_isFrame(const void *buffer, size_t size)
  144. {
  145. if (size < 4)
  146. return 0;
  147. {
  148. U32 const magic = ZSTD_readLE32(buffer);
  149. if (magic == ZSTD_MAGICNUMBER)
  150. return 1;
  151. if ((magic & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START)
  152. return 1;
  153. }
  154. return 0;
  155. }
  156. /** ZSTD_frameHeaderSize() :
  157. * srcSize must be >= ZSTD_frameHeaderSize_prefix.
  158. * @return : size of the Frame Header */
  159. static size_t ZSTD_frameHeaderSize(const void *src, size_t srcSize)
  160. {
  161. if (srcSize < ZSTD_frameHeaderSize_prefix)
  162. return ERROR(srcSize_wrong);
  163. {
  164. BYTE const fhd = ((const BYTE *)src)[4];
  165. U32 const dictID = fhd & 3;
  166. U32 const singleSegment = (fhd >> 5) & 1;
  167. U32 const fcsId = fhd >> 6;
  168. return ZSTD_frameHeaderSize_prefix + !singleSegment + ZSTD_did_fieldSize[dictID] + ZSTD_fcs_fieldSize[fcsId] + (singleSegment && !fcsId);
  169. }
  170. }
  171. /** ZSTD_getFrameParams() :
  172. * decode Frame Header, or require larger `srcSize`.
  173. * @return : 0, `fparamsPtr` is correctly filled,
  174. * >0, `srcSize` is too small, result is expected `srcSize`,
  175. * or an error code, which can be tested using ZSTD_isError() */
  176. size_t ZSTD_getFrameParams(ZSTD_frameParams *fparamsPtr, const void *src, size_t srcSize)
  177. {
  178. const BYTE *ip = (const BYTE *)src;
  179. if (srcSize < ZSTD_frameHeaderSize_prefix)
  180. return ZSTD_frameHeaderSize_prefix;
  181. if (ZSTD_readLE32(src) != ZSTD_MAGICNUMBER) {
  182. if ((ZSTD_readLE32(src) & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START) {
  183. if (srcSize < ZSTD_skippableHeaderSize)
  184. return ZSTD_skippableHeaderSize; /* magic number + skippable frame length */
  185. memset(fparamsPtr, 0, sizeof(*fparamsPtr));
  186. fparamsPtr->frameContentSize = ZSTD_readLE32((const char *)src + 4);
  187. fparamsPtr->windowSize = 0; /* windowSize==0 means a frame is skippable */
  188. return 0;
  189. }
  190. return ERROR(prefix_unknown);
  191. }
  192. /* ensure there is enough `srcSize` to fully read/decode frame header */
  193. {
  194. size_t const fhsize = ZSTD_frameHeaderSize(src, srcSize);
  195. if (srcSize < fhsize)
  196. return fhsize;
  197. }
  198. {
  199. BYTE const fhdByte = ip[4];
  200. size_t pos = 5;
  201. U32 const dictIDSizeCode = fhdByte & 3;
  202. U32 const checksumFlag = (fhdByte >> 2) & 1;
  203. U32 const singleSegment = (fhdByte >> 5) & 1;
  204. U32 const fcsID = fhdByte >> 6;
  205. U32 const windowSizeMax = 1U << ZSTD_WINDOWLOG_MAX;
  206. U32 windowSize = 0;
  207. U32 dictID = 0;
  208. U64 frameContentSize = 0;
  209. if ((fhdByte & 0x08) != 0)
  210. return ERROR(frameParameter_unsupported); /* reserved bits, which must be zero */
  211. if (!singleSegment) {
  212. BYTE const wlByte = ip[pos++];
  213. U32 const windowLog = (wlByte >> 3) + ZSTD_WINDOWLOG_ABSOLUTEMIN;
  214. if (windowLog > ZSTD_WINDOWLOG_MAX)
  215. return ERROR(frameParameter_windowTooLarge); /* avoids issue with 1 << windowLog */
  216. windowSize = (1U << windowLog);
  217. windowSize += (windowSize >> 3) * (wlByte & 7);
  218. }
  219. switch (dictIDSizeCode) {
  220. default: /* impossible */
  221. case 0: break;
  222. case 1:
  223. dictID = ip[pos];
  224. pos++;
  225. break;
  226. case 2:
  227. dictID = ZSTD_readLE16(ip + pos);
  228. pos += 2;
  229. break;
  230. case 3:
  231. dictID = ZSTD_readLE32(ip + pos);
  232. pos += 4;
  233. break;
  234. }
  235. switch (fcsID) {
  236. default: /* impossible */
  237. case 0:
  238. if (singleSegment)
  239. frameContentSize = ip[pos];
  240. break;
  241. case 1: frameContentSize = ZSTD_readLE16(ip + pos) + 256; break;
  242. case 2: frameContentSize = ZSTD_readLE32(ip + pos); break;
  243. case 3: frameContentSize = ZSTD_readLE64(ip + pos); break;
  244. }
  245. if (!windowSize)
  246. windowSize = (U32)frameContentSize;
  247. if (windowSize > windowSizeMax)
  248. return ERROR(frameParameter_windowTooLarge);
  249. fparamsPtr->frameContentSize = frameContentSize;
  250. fparamsPtr->windowSize = windowSize;
  251. fparamsPtr->dictID = dictID;
  252. fparamsPtr->checksumFlag = checksumFlag;
  253. }
  254. return 0;
  255. }
  256. /** ZSTD_getFrameContentSize() :
  257. * compatible with legacy mode
  258. * @return : decompressed size of the single frame pointed to be `src` if known, otherwise
  259. * - ZSTD_CONTENTSIZE_UNKNOWN if the size cannot be determined
  260. * - ZSTD_CONTENTSIZE_ERROR if an error occurred (e.g. invalid magic number, srcSize too small) */
  261. unsigned long long ZSTD_getFrameContentSize(const void *src, size_t srcSize)
  262. {
  263. {
  264. ZSTD_frameParams fParams;
  265. if (ZSTD_getFrameParams(&fParams, src, srcSize) != 0)
  266. return ZSTD_CONTENTSIZE_ERROR;
  267. if (fParams.windowSize == 0) {
  268. /* Either skippable or empty frame, size == 0 either way */
  269. return 0;
  270. } else if (fParams.frameContentSize != 0) {
  271. return fParams.frameContentSize;
  272. } else {
  273. return ZSTD_CONTENTSIZE_UNKNOWN;
  274. }
  275. }
  276. }
  277. /** ZSTD_findDecompressedSize() :
  278. * compatible with legacy mode
  279. * `srcSize` must be the exact length of some number of ZSTD compressed and/or
  280. * skippable frames
  281. * @return : decompressed size of the frames contained */
  282. unsigned long long ZSTD_findDecompressedSize(const void *src, size_t srcSize)
  283. {
  284. {
  285. unsigned long long totalDstSize = 0;
  286. while (srcSize >= ZSTD_frameHeaderSize_prefix) {
  287. const U32 magicNumber = ZSTD_readLE32(src);
  288. if ((magicNumber & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START) {
  289. size_t skippableSize;
  290. if (srcSize < ZSTD_skippableHeaderSize)
  291. return ERROR(srcSize_wrong);
  292. skippableSize = ZSTD_readLE32((const BYTE *)src + 4) + ZSTD_skippableHeaderSize;
  293. if (srcSize < skippableSize) {
  294. return ZSTD_CONTENTSIZE_ERROR;
  295. }
  296. src = (const BYTE *)src + skippableSize;
  297. srcSize -= skippableSize;
  298. continue;
  299. }
  300. {
  301. unsigned long long const ret = ZSTD_getFrameContentSize(src, srcSize);
  302. if (ret >= ZSTD_CONTENTSIZE_ERROR)
  303. return ret;
  304. /* check for overflow */
  305. if (totalDstSize + ret < totalDstSize)
  306. return ZSTD_CONTENTSIZE_ERROR;
  307. totalDstSize += ret;
  308. }
  309. {
  310. size_t const frameSrcSize = ZSTD_findFrameCompressedSize(src, srcSize);
  311. if (ZSTD_isError(frameSrcSize)) {
  312. return ZSTD_CONTENTSIZE_ERROR;
  313. }
  314. src = (const BYTE *)src + frameSrcSize;
  315. srcSize -= frameSrcSize;
  316. }
  317. }
  318. if (srcSize) {
  319. return ZSTD_CONTENTSIZE_ERROR;
  320. }
  321. return totalDstSize;
  322. }
  323. }
  324. /** ZSTD_decodeFrameHeader() :
  325. * `headerSize` must be the size provided by ZSTD_frameHeaderSize().
  326. * @return : 0 if success, or an error code, which can be tested using ZSTD_isError() */
  327. static size_t ZSTD_decodeFrameHeader(ZSTD_DCtx *dctx, const void *src, size_t headerSize)
  328. {
  329. size_t const result = ZSTD_getFrameParams(&(dctx->fParams), src, headerSize);
  330. if (ZSTD_isError(result))
  331. return result; /* invalid header */
  332. if (result > 0)
  333. return ERROR(srcSize_wrong); /* headerSize too small */
  334. if (dctx->fParams.dictID && (dctx->dictID != dctx->fParams.dictID))
  335. return ERROR(dictionary_wrong);
  336. if (dctx->fParams.checksumFlag)
  337. xxh64_reset(&dctx->xxhState, 0);
  338. return 0;
  339. }
  340. typedef struct {
  341. blockType_e blockType;
  342. U32 lastBlock;
  343. U32 origSize;
  344. } blockProperties_t;
  345. /*! ZSTD_getcBlockSize() :
  346. * Provides the size of compressed block from block header `src` */
  347. size_t ZSTD_getcBlockSize(const void *src, size_t srcSize, blockProperties_t *bpPtr)
  348. {
  349. if (srcSize < ZSTD_blockHeaderSize)
  350. return ERROR(srcSize_wrong);
  351. {
  352. U32 const cBlockHeader = ZSTD_readLE24(src);
  353. U32 const cSize = cBlockHeader >> 3;
  354. bpPtr->lastBlock = cBlockHeader & 1;
  355. bpPtr->blockType = (blockType_e)((cBlockHeader >> 1) & 3);
  356. bpPtr->origSize = cSize; /* only useful for RLE */
  357. if (bpPtr->blockType == bt_rle)
  358. return 1;
  359. if (bpPtr->blockType == bt_reserved)
  360. return ERROR(corruption_detected);
  361. return cSize;
  362. }
  363. }
  364. static size_t ZSTD_copyRawBlock(void *dst, size_t dstCapacity, const void *src, size_t srcSize)
  365. {
  366. if (srcSize > dstCapacity)
  367. return ERROR(dstSize_tooSmall);
  368. memcpy(dst, src, srcSize);
  369. return srcSize;
  370. }
  371. static size_t ZSTD_setRleBlock(void *dst, size_t dstCapacity, const void *src, size_t srcSize, size_t regenSize)
  372. {
  373. if (srcSize != 1)
  374. return ERROR(srcSize_wrong);
  375. if (regenSize > dstCapacity)
  376. return ERROR(dstSize_tooSmall);
  377. memset(dst, *(const BYTE *)src, regenSize);
  378. return regenSize;
  379. }
  380. /*! ZSTD_decodeLiteralsBlock() :
  381. @return : nb of bytes read from src (< srcSize ) */
  382. size_t ZSTD_decodeLiteralsBlock(ZSTD_DCtx *dctx, const void *src, size_t srcSize) /* note : srcSize < BLOCKSIZE */
  383. {
  384. if (srcSize < MIN_CBLOCK_SIZE)
  385. return ERROR(corruption_detected);
  386. {
  387. const BYTE *const istart = (const BYTE *)src;
  388. symbolEncodingType_e const litEncType = (symbolEncodingType_e)(istart[0] & 3);
  389. switch (litEncType) {
  390. case set_repeat:
  391. if (dctx->litEntropy == 0)
  392. return ERROR(dictionary_corrupted);
  393. /* fall-through */
  394. case set_compressed:
  395. if (srcSize < 5)
  396. return ERROR(corruption_detected); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need up to 5 for case 3 */
  397. {
  398. size_t lhSize, litSize, litCSize;
  399. U32 singleStream = 0;
  400. U32 const lhlCode = (istart[0] >> 2) & 3;
  401. U32 const lhc = ZSTD_readLE32(istart);
  402. switch (lhlCode) {
  403. case 0:
  404. case 1:
  405. default: /* note : default is impossible, since lhlCode into [0..3] */
  406. /* 2 - 2 - 10 - 10 */
  407. singleStream = !lhlCode;
  408. lhSize = 3;
  409. litSize = (lhc >> 4) & 0x3FF;
  410. litCSize = (lhc >> 14) & 0x3FF;
  411. break;
  412. case 2:
  413. /* 2 - 2 - 14 - 14 */
  414. lhSize = 4;
  415. litSize = (lhc >> 4) & 0x3FFF;
  416. litCSize = lhc >> 18;
  417. break;
  418. case 3:
  419. /* 2 - 2 - 18 - 18 */
  420. lhSize = 5;
  421. litSize = (lhc >> 4) & 0x3FFFF;
  422. litCSize = (lhc >> 22) + (istart[4] << 10);
  423. break;
  424. }
  425. if (litSize > ZSTD_BLOCKSIZE_ABSOLUTEMAX)
  426. return ERROR(corruption_detected);
  427. if (litCSize + lhSize > srcSize)
  428. return ERROR(corruption_detected);
  429. if (HUF_isError(
  430. (litEncType == set_repeat)
  431. ? (singleStream ? HUF_decompress1X_usingDTable(dctx->litBuffer, litSize, istart + lhSize, litCSize, dctx->HUFptr)
  432. : HUF_decompress4X_usingDTable(dctx->litBuffer, litSize, istart + lhSize, litCSize, dctx->HUFptr))
  433. : (singleStream
  434. ? HUF_decompress1X2_DCtx_wksp(dctx->entropy.hufTable, dctx->litBuffer, litSize, istart + lhSize, litCSize,
  435. dctx->entropy.workspace, sizeof(dctx->entropy.workspace))
  436. : HUF_decompress4X_hufOnly_wksp(dctx->entropy.hufTable, dctx->litBuffer, litSize, istart + lhSize, litCSize,
  437. dctx->entropy.workspace, sizeof(dctx->entropy.workspace)))))
  438. return ERROR(corruption_detected);
  439. dctx->litPtr = dctx->litBuffer;
  440. dctx->litSize = litSize;
  441. dctx->litEntropy = 1;
  442. if (litEncType == set_compressed)
  443. dctx->HUFptr = dctx->entropy.hufTable;
  444. memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
  445. return litCSize + lhSize;
  446. }
  447. case set_basic: {
  448. size_t litSize, lhSize;
  449. U32 const lhlCode = ((istart[0]) >> 2) & 3;
  450. switch (lhlCode) {
  451. case 0:
  452. case 2:
  453. default: /* note : default is impossible, since lhlCode into [0..3] */
  454. lhSize = 1;
  455. litSize = istart[0] >> 3;
  456. break;
  457. case 1:
  458. lhSize = 2;
  459. litSize = ZSTD_readLE16(istart) >> 4;
  460. break;
  461. case 3:
  462. lhSize = 3;
  463. litSize = ZSTD_readLE24(istart) >> 4;
  464. break;
  465. }
  466. if (lhSize + litSize + WILDCOPY_OVERLENGTH > srcSize) { /* risk reading beyond src buffer with wildcopy */
  467. if (litSize + lhSize > srcSize)
  468. return ERROR(corruption_detected);
  469. memcpy(dctx->litBuffer, istart + lhSize, litSize);
  470. dctx->litPtr = dctx->litBuffer;
  471. dctx->litSize = litSize;
  472. memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
  473. return lhSize + litSize;
  474. }
  475. /* direct reference into compressed stream */
  476. dctx->litPtr = istart + lhSize;
  477. dctx->litSize = litSize;
  478. return lhSize + litSize;
  479. }
  480. case set_rle: {
  481. U32 const lhlCode = ((istart[0]) >> 2) & 3;
  482. size_t litSize, lhSize;
  483. switch (lhlCode) {
  484. case 0:
  485. case 2:
  486. default: /* note : default is impossible, since lhlCode into [0..3] */
  487. lhSize = 1;
  488. litSize = istart[0] >> 3;
  489. break;
  490. case 1:
  491. lhSize = 2;
  492. litSize = ZSTD_readLE16(istart) >> 4;
  493. break;
  494. case 3:
  495. lhSize = 3;
  496. litSize = ZSTD_readLE24(istart) >> 4;
  497. if (srcSize < 4)
  498. return ERROR(corruption_detected); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need lhSize+1 = 4 */
  499. break;
  500. }
  501. if (litSize > ZSTD_BLOCKSIZE_ABSOLUTEMAX)
  502. return ERROR(corruption_detected);
  503. memset(dctx->litBuffer, istart[lhSize], litSize + WILDCOPY_OVERLENGTH);
  504. dctx->litPtr = dctx->litBuffer;
  505. dctx->litSize = litSize;
  506. return lhSize + 1;
  507. }
  508. default:
  509. return ERROR(corruption_detected); /* impossible */
  510. }
  511. }
  512. }
  513. typedef union {
  514. FSE_decode_t realData;
  515. U32 alignedBy4;
  516. } FSE_decode_t4;
  517. static const FSE_decode_t4 LL_defaultDTable[(1 << LL_DEFAULTNORMLOG) + 1] = {
  518. {{LL_DEFAULTNORMLOG, 1, 1}}, /* header : tableLog, fastMode, fastMode */
  519. {{0, 0, 4}}, /* 0 : base, symbol, bits */
  520. {{16, 0, 4}},
  521. {{32, 1, 5}},
  522. {{0, 3, 5}},
  523. {{0, 4, 5}},
  524. {{0, 6, 5}},
  525. {{0, 7, 5}},
  526. {{0, 9, 5}},
  527. {{0, 10, 5}},
  528. {{0, 12, 5}},
  529. {{0, 14, 6}},
  530. {{0, 16, 5}},
  531. {{0, 18, 5}},
  532. {{0, 19, 5}},
  533. {{0, 21, 5}},
  534. {{0, 22, 5}},
  535. {{0, 24, 5}},
  536. {{32, 25, 5}},
  537. {{0, 26, 5}},
  538. {{0, 27, 6}},
  539. {{0, 29, 6}},
  540. {{0, 31, 6}},
  541. {{32, 0, 4}},
  542. {{0, 1, 4}},
  543. {{0, 2, 5}},
  544. {{32, 4, 5}},
  545. {{0, 5, 5}},
  546. {{32, 7, 5}},
  547. {{0, 8, 5}},
  548. {{32, 10, 5}},
  549. {{0, 11, 5}},
  550. {{0, 13, 6}},
  551. {{32, 16, 5}},
  552. {{0, 17, 5}},
  553. {{32, 19, 5}},
  554. {{0, 20, 5}},
  555. {{32, 22, 5}},
  556. {{0, 23, 5}},
  557. {{0, 25, 4}},
  558. {{16, 25, 4}},
  559. {{32, 26, 5}},
  560. {{0, 28, 6}},
  561. {{0, 30, 6}},
  562. {{48, 0, 4}},
  563. {{16, 1, 4}},
  564. {{32, 2, 5}},
  565. {{32, 3, 5}},
  566. {{32, 5, 5}},
  567. {{32, 6, 5}},
  568. {{32, 8, 5}},
  569. {{32, 9, 5}},
  570. {{32, 11, 5}},
  571. {{32, 12, 5}},
  572. {{0, 15, 6}},
  573. {{32, 17, 5}},
  574. {{32, 18, 5}},
  575. {{32, 20, 5}},
  576. {{32, 21, 5}},
  577. {{32, 23, 5}},
  578. {{32, 24, 5}},
  579. {{0, 35, 6}},
  580. {{0, 34, 6}},
  581. {{0, 33, 6}},
  582. {{0, 32, 6}},
  583. }; /* LL_defaultDTable */
  584. static const FSE_decode_t4 ML_defaultDTable[(1 << ML_DEFAULTNORMLOG) + 1] = {
  585. {{ML_DEFAULTNORMLOG, 1, 1}}, /* header : tableLog, fastMode, fastMode */
  586. {{0, 0, 6}}, /* 0 : base, symbol, bits */
  587. {{0, 1, 4}},
  588. {{32, 2, 5}},
  589. {{0, 3, 5}},
  590. {{0, 5, 5}},
  591. {{0, 6, 5}},
  592. {{0, 8, 5}},
  593. {{0, 10, 6}},
  594. {{0, 13, 6}},
  595. {{0, 16, 6}},
  596. {{0, 19, 6}},
  597. {{0, 22, 6}},
  598. {{0, 25, 6}},
  599. {{0, 28, 6}},
  600. {{0, 31, 6}},
  601. {{0, 33, 6}},
  602. {{0, 35, 6}},
  603. {{0, 37, 6}},
  604. {{0, 39, 6}},
  605. {{0, 41, 6}},
  606. {{0, 43, 6}},
  607. {{0, 45, 6}},
  608. {{16, 1, 4}},
  609. {{0, 2, 4}},
  610. {{32, 3, 5}},
  611. {{0, 4, 5}},
  612. {{32, 6, 5}},
  613. {{0, 7, 5}},
  614. {{0, 9, 6}},
  615. {{0, 12, 6}},
  616. {{0, 15, 6}},
  617. {{0, 18, 6}},
  618. {{0, 21, 6}},
  619. {{0, 24, 6}},
  620. {{0, 27, 6}},
  621. {{0, 30, 6}},
  622. {{0, 32, 6}},
  623. {{0, 34, 6}},
  624. {{0, 36, 6}},
  625. {{0, 38, 6}},
  626. {{0, 40, 6}},
  627. {{0, 42, 6}},
  628. {{0, 44, 6}},
  629. {{32, 1, 4}},
  630. {{48, 1, 4}},
  631. {{16, 2, 4}},
  632. {{32, 4, 5}},
  633. {{32, 5, 5}},
  634. {{32, 7, 5}},
  635. {{32, 8, 5}},
  636. {{0, 11, 6}},
  637. {{0, 14, 6}},
  638. {{0, 17, 6}},
  639. {{0, 20, 6}},
  640. {{0, 23, 6}},
  641. {{0, 26, 6}},
  642. {{0, 29, 6}},
  643. {{0, 52, 6}},
  644. {{0, 51, 6}},
  645. {{0, 50, 6}},
  646. {{0, 49, 6}},
  647. {{0, 48, 6}},
  648. {{0, 47, 6}},
  649. {{0, 46, 6}},
  650. }; /* ML_defaultDTable */
  651. static const FSE_decode_t4 OF_defaultDTable[(1 << OF_DEFAULTNORMLOG) + 1] = {
  652. {{OF_DEFAULTNORMLOG, 1, 1}}, /* header : tableLog, fastMode, fastMode */
  653. {{0, 0, 5}}, /* 0 : base, symbol, bits */
  654. {{0, 6, 4}},
  655. {{0, 9, 5}},
  656. {{0, 15, 5}},
  657. {{0, 21, 5}},
  658. {{0, 3, 5}},
  659. {{0, 7, 4}},
  660. {{0, 12, 5}},
  661. {{0, 18, 5}},
  662. {{0, 23, 5}},
  663. {{0, 5, 5}},
  664. {{0, 8, 4}},
  665. {{0, 14, 5}},
  666. {{0, 20, 5}},
  667. {{0, 2, 5}},
  668. {{16, 7, 4}},
  669. {{0, 11, 5}},
  670. {{0, 17, 5}},
  671. {{0, 22, 5}},
  672. {{0, 4, 5}},
  673. {{16, 8, 4}},
  674. {{0, 13, 5}},
  675. {{0, 19, 5}},
  676. {{0, 1, 5}},
  677. {{16, 6, 4}},
  678. {{0, 10, 5}},
  679. {{0, 16, 5}},
  680. {{0, 28, 5}},
  681. {{0, 27, 5}},
  682. {{0, 26, 5}},
  683. {{0, 25, 5}},
  684. {{0, 24, 5}},
  685. }; /* OF_defaultDTable */
  686. /*! ZSTD_buildSeqTable() :
  687. @return : nb bytes read from src,
  688. or an error code if it fails, testable with ZSTD_isError()
  689. */
  690. static size_t ZSTD_buildSeqTable(FSE_DTable *DTableSpace, const FSE_DTable **DTablePtr, symbolEncodingType_e type, U32 max, U32 maxLog, const void *src,
  691. size_t srcSize, const FSE_decode_t4 *defaultTable, U32 flagRepeatTable, void *workspace, size_t workspaceSize)
  692. {
  693. const void *const tmpPtr = defaultTable; /* bypass strict aliasing */
  694. switch (type) {
  695. case set_rle:
  696. if (!srcSize)
  697. return ERROR(srcSize_wrong);
  698. if ((*(const BYTE *)src) > max)
  699. return ERROR(corruption_detected);
  700. FSE_buildDTable_rle(DTableSpace, *(const BYTE *)src);
  701. *DTablePtr = DTableSpace;
  702. return 1;
  703. case set_basic: *DTablePtr = (const FSE_DTable *)tmpPtr; return 0;
  704. case set_repeat:
  705. if (!flagRepeatTable)
  706. return ERROR(corruption_detected);
  707. return 0;
  708. default: /* impossible */
  709. case set_compressed: {
  710. U32 tableLog;
  711. S16 *norm = (S16 *)workspace;
  712. size_t const spaceUsed32 = ALIGN(sizeof(S16) * (MaxSeq + 1), sizeof(U32)) >> 2;
  713. if ((spaceUsed32 << 2) > workspaceSize)
  714. return ERROR(GENERIC);
  715. workspace = (U32 *)workspace + spaceUsed32;
  716. workspaceSize -= (spaceUsed32 << 2);
  717. {
  718. size_t const headerSize = FSE_readNCount(norm, &max, &tableLog, src, srcSize);
  719. if (FSE_isError(headerSize))
  720. return ERROR(corruption_detected);
  721. if (tableLog > maxLog)
  722. return ERROR(corruption_detected);
  723. FSE_buildDTable_wksp(DTableSpace, norm, max, tableLog, workspace, workspaceSize);
  724. *DTablePtr = DTableSpace;
  725. return headerSize;
  726. }
  727. }
  728. }
  729. }
  730. size_t ZSTD_decodeSeqHeaders(ZSTD_DCtx *dctx, int *nbSeqPtr, const void *src, size_t srcSize)
  731. {
  732. const BYTE *const istart = (const BYTE *const)src;
  733. const BYTE *const iend = istart + srcSize;
  734. const BYTE *ip = istart;
  735. /* check */
  736. if (srcSize < MIN_SEQUENCES_SIZE)
  737. return ERROR(srcSize_wrong);
  738. /* SeqHead */
  739. {
  740. int nbSeq = *ip++;
  741. if (!nbSeq) {
  742. *nbSeqPtr = 0;
  743. return 1;
  744. }
  745. if (nbSeq > 0x7F) {
  746. if (nbSeq == 0xFF) {
  747. if (ip + 2 > iend)
  748. return ERROR(srcSize_wrong);
  749. nbSeq = ZSTD_readLE16(ip) + LONGNBSEQ, ip += 2;
  750. } else {
  751. if (ip >= iend)
  752. return ERROR(srcSize_wrong);
  753. nbSeq = ((nbSeq - 0x80) << 8) + *ip++;
  754. }
  755. }
  756. *nbSeqPtr = nbSeq;
  757. }
  758. /* FSE table descriptors */
  759. if (ip + 4 > iend)
  760. return ERROR(srcSize_wrong); /* minimum possible size */
  761. {
  762. symbolEncodingType_e const LLtype = (symbolEncodingType_e)(*ip >> 6);
  763. symbolEncodingType_e const OFtype = (symbolEncodingType_e)((*ip >> 4) & 3);
  764. symbolEncodingType_e const MLtype = (symbolEncodingType_e)((*ip >> 2) & 3);
  765. ip++;
  766. /* Build DTables */
  767. {
  768. size_t const llhSize = ZSTD_buildSeqTable(dctx->entropy.LLTable, &dctx->LLTptr, LLtype, MaxLL, LLFSELog, ip, iend - ip,
  769. LL_defaultDTable, dctx->fseEntropy, dctx->entropy.workspace, sizeof(dctx->entropy.workspace));
  770. if (ZSTD_isError(llhSize))
  771. return ERROR(corruption_detected);
  772. ip += llhSize;
  773. }
  774. {
  775. size_t const ofhSize = ZSTD_buildSeqTable(dctx->entropy.OFTable, &dctx->OFTptr, OFtype, MaxOff, OffFSELog, ip, iend - ip,
  776. OF_defaultDTable, dctx->fseEntropy, dctx->entropy.workspace, sizeof(dctx->entropy.workspace));
  777. if (ZSTD_isError(ofhSize))
  778. return ERROR(corruption_detected);
  779. ip += ofhSize;
  780. }
  781. {
  782. size_t const mlhSize = ZSTD_buildSeqTable(dctx->entropy.MLTable, &dctx->MLTptr, MLtype, MaxML, MLFSELog, ip, iend - ip,
  783. ML_defaultDTable, dctx->fseEntropy, dctx->entropy.workspace, sizeof(dctx->entropy.workspace));
  784. if (ZSTD_isError(mlhSize))
  785. return ERROR(corruption_detected);
  786. ip += mlhSize;
  787. }
  788. }
  789. return ip - istart;
  790. }
  791. typedef struct {
  792. size_t litLength;
  793. size_t matchLength;
  794. size_t offset;
  795. const BYTE *match;
  796. } seq_t;
  797. typedef struct {
  798. BIT_DStream_t DStream;
  799. FSE_DState_t stateLL;
  800. FSE_DState_t stateOffb;
  801. FSE_DState_t stateML;
  802. size_t prevOffset[ZSTD_REP_NUM];
  803. const BYTE *base;
  804. size_t pos;
  805. uPtrDiff gotoDict;
  806. } seqState_t;
  807. FORCE_NOINLINE
  808. size_t ZSTD_execSequenceLast7(BYTE *op, BYTE *const oend, seq_t sequence, const BYTE **litPtr, const BYTE *const litLimit, const BYTE *const base,
  809. const BYTE *const vBase, const BYTE *const dictEnd)
  810. {
  811. BYTE *const oLitEnd = op + sequence.litLength;
  812. size_t const sequenceLength = sequence.litLength + sequence.matchLength;
  813. BYTE *const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */
  814. BYTE *const oend_w = oend - WILDCOPY_OVERLENGTH;
  815. const BYTE *const iLitEnd = *litPtr + sequence.litLength;
  816. const BYTE *match = oLitEnd - sequence.offset;
  817. /* check */
  818. if (oMatchEnd > oend)
  819. return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of WILDCOPY_OVERLENGTH from oend */
  820. if (iLitEnd > litLimit)
  821. return ERROR(corruption_detected); /* over-read beyond lit buffer */
  822. if (oLitEnd <= oend_w)
  823. return ERROR(GENERIC); /* Precondition */
  824. /* copy literals */
  825. if (op < oend_w) {
  826. ZSTD_wildcopy(op, *litPtr, oend_w - op);
  827. *litPtr += oend_w - op;
  828. op = oend_w;
  829. }
  830. while (op < oLitEnd)
  831. *op++ = *(*litPtr)++;
  832. /* copy Match */
  833. if (sequence.offset > (size_t)(oLitEnd - base)) {
  834. /* offset beyond prefix */
  835. if (sequence.offset > (size_t)(oLitEnd - vBase))
  836. return ERROR(corruption_detected);
  837. match = dictEnd - (base - match);
  838. if (match + sequence.matchLength <= dictEnd) {
  839. memmove(oLitEnd, match, sequence.matchLength);
  840. return sequenceLength;
  841. }
  842. /* span extDict & currPrefixSegment */
  843. {
  844. size_t const length1 = dictEnd - match;
  845. memmove(oLitEnd, match, length1);
  846. op = oLitEnd + length1;
  847. sequence.matchLength -= length1;
  848. match = base;
  849. }
  850. }
  851. while (op < oMatchEnd)
  852. *op++ = *match++;
  853. return sequenceLength;
  854. }
  855. static seq_t ZSTD_decodeSequence(seqState_t *seqState)
  856. {
  857. seq_t seq;
  858. U32 const llCode = FSE_peekSymbol(&seqState->stateLL);
  859. U32 const mlCode = FSE_peekSymbol(&seqState->stateML);
  860. U32 const ofCode = FSE_peekSymbol(&seqState->stateOffb); /* <= maxOff, by table construction */
  861. U32 const llBits = LL_bits[llCode];
  862. U32 const mlBits = ML_bits[mlCode];
  863. U32 const ofBits = ofCode;
  864. U32 const totalBits = llBits + mlBits + ofBits;
  865. static const U32 LL_base[MaxLL + 1] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18,
  866. 20, 22, 24, 28, 32, 40, 48, 64, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000, 0x2000, 0x4000, 0x8000, 0x10000};
  867. static const U32 ML_base[MaxML + 1] = {3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
  868. 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 37, 39, 41,
  869. 43, 47, 51, 59, 67, 83, 99, 0x83, 0x103, 0x203, 0x403, 0x803, 0x1003, 0x2003, 0x4003, 0x8003, 0x10003};
  870. static const U32 OF_base[MaxOff + 1] = {0, 1, 1, 5, 0xD, 0x1D, 0x3D, 0x7D, 0xFD, 0x1FD,
  871. 0x3FD, 0x7FD, 0xFFD, 0x1FFD, 0x3FFD, 0x7FFD, 0xFFFD, 0x1FFFD, 0x3FFFD, 0x7FFFD,
  872. 0xFFFFD, 0x1FFFFD, 0x3FFFFD, 0x7FFFFD, 0xFFFFFD, 0x1FFFFFD, 0x3FFFFFD, 0x7FFFFFD, 0xFFFFFFD};
  873. /* sequence */
  874. {
  875. size_t offset;
  876. if (!ofCode)
  877. offset = 0;
  878. else {
  879. offset = OF_base[ofCode] + BIT_readBitsFast(&seqState->DStream, ofBits); /* <= (ZSTD_WINDOWLOG_MAX-1) bits */
  880. if (ZSTD_32bits())
  881. BIT_reloadDStream(&seqState->DStream);
  882. }
  883. if (ofCode <= 1) {
  884. offset += (llCode == 0);
  885. if (offset) {
  886. size_t temp = (offset == 3) ? seqState->prevOffset[0] - 1 : seqState->prevOffset[offset];
  887. temp += !temp; /* 0 is not valid; input is corrupted; force offset to 1 */
  888. if (offset != 1)
  889. seqState->prevOffset[2] = seqState->prevOffset[1];
  890. seqState->prevOffset[1] = seqState->prevOffset[0];
  891. seqState->prevOffset[0] = offset = temp;
  892. } else {
  893. offset = seqState->prevOffset[0];
  894. }
  895. } else {
  896. seqState->prevOffset[2] = seqState->prevOffset[1];
  897. seqState->prevOffset[1] = seqState->prevOffset[0];
  898. seqState->prevOffset[0] = offset;
  899. }
  900. seq.offset = offset;
  901. }
  902. seq.matchLength = ML_base[mlCode] + ((mlCode > 31) ? BIT_readBitsFast(&seqState->DStream, mlBits) : 0); /* <= 16 bits */
  903. if (ZSTD_32bits() && (mlBits + llBits > 24))
  904. BIT_reloadDStream(&seqState->DStream);
  905. seq.litLength = LL_base[llCode] + ((llCode > 15) ? BIT_readBitsFast(&seqState->DStream, llBits) : 0); /* <= 16 bits */
  906. if (ZSTD_32bits() || (totalBits > 64 - 7 - (LLFSELog + MLFSELog + OffFSELog)))
  907. BIT_reloadDStream(&seqState->DStream);
  908. /* ANS state update */
  909. FSE_updateState(&seqState->stateLL, &seqState->DStream); /* <= 9 bits */
  910. FSE_updateState(&seqState->stateML, &seqState->DStream); /* <= 9 bits */
  911. if (ZSTD_32bits())
  912. BIT_reloadDStream(&seqState->DStream); /* <= 18 bits */
  913. FSE_updateState(&seqState->stateOffb, &seqState->DStream); /* <= 8 bits */
  914. seq.match = NULL;
  915. return seq;
  916. }
  917. FORCE_INLINE
  918. size_t ZSTD_execSequence(BYTE *op, BYTE *const oend, seq_t sequence, const BYTE **litPtr, const BYTE *const litLimit, const BYTE *const base,
  919. const BYTE *const vBase, const BYTE *const dictEnd)
  920. {
  921. BYTE *const oLitEnd = op + sequence.litLength;
  922. size_t const sequenceLength = sequence.litLength + sequence.matchLength;
  923. BYTE *const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */
  924. BYTE *const oend_w = oend - WILDCOPY_OVERLENGTH;
  925. const BYTE *const iLitEnd = *litPtr + sequence.litLength;
  926. const BYTE *match = oLitEnd - sequence.offset;
  927. /* check */
  928. if (oMatchEnd > oend)
  929. return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of WILDCOPY_OVERLENGTH from oend */
  930. if (iLitEnd > litLimit)
  931. return ERROR(corruption_detected); /* over-read beyond lit buffer */
  932. if (oLitEnd > oend_w)
  933. return ZSTD_execSequenceLast7(op, oend, sequence, litPtr, litLimit, base, vBase, dictEnd);
  934. /* copy Literals */
  935. ZSTD_copy8(op, *litPtr);
  936. if (sequence.litLength > 8)
  937. ZSTD_wildcopy(op + 8, (*litPtr) + 8,
  938. sequence.litLength - 8); /* note : since oLitEnd <= oend-WILDCOPY_OVERLENGTH, no risk of overwrite beyond oend */
  939. op = oLitEnd;
  940. *litPtr = iLitEnd; /* update for next sequence */
  941. /* copy Match */
  942. if (sequence.offset > (size_t)(oLitEnd - base)) {
  943. /* offset beyond prefix */
  944. if (sequence.offset > (size_t)(oLitEnd - vBase))
  945. return ERROR(corruption_detected);
  946. match = dictEnd + (match - base);
  947. if (match + sequence.matchLength <= dictEnd) {
  948. memmove(oLitEnd, match, sequence.matchLength);
  949. return sequenceLength;
  950. }
  951. /* span extDict & currPrefixSegment */
  952. {
  953. size_t const length1 = dictEnd - match;
  954. memmove(oLitEnd, match, length1);
  955. op = oLitEnd + length1;
  956. sequence.matchLength -= length1;
  957. match = base;
  958. if (op > oend_w || sequence.matchLength < MINMATCH) {
  959. U32 i;
  960. for (i = 0; i < sequence.matchLength; ++i)
  961. op[i] = match[i];
  962. return sequenceLength;
  963. }
  964. }
  965. }
  966. /* Requirement: op <= oend_w && sequence.matchLength >= MINMATCH */
  967. /* match within prefix */
  968. if (sequence.offset < 8) {
  969. /* close range match, overlap */
  970. static const U32 dec32table[] = {0, 1, 2, 1, 4, 4, 4, 4}; /* added */
  971. static const int dec64table[] = {8, 8, 8, 7, 8, 9, 10, 11}; /* subtracted */
  972. int const sub2 = dec64table[sequence.offset];
  973. op[0] = match[0];
  974. op[1] = match[1];
  975. op[2] = match[2];
  976. op[3] = match[3];
  977. match += dec32table[sequence.offset];
  978. ZSTD_copy4(op + 4, match);
  979. match -= sub2;
  980. } else {
  981. ZSTD_copy8(op, match);
  982. }
  983. op += 8;
  984. match += 8;
  985. if (oMatchEnd > oend - (16 - MINMATCH)) {
  986. if (op < oend_w) {
  987. ZSTD_wildcopy(op, match, oend_w - op);
  988. match += oend_w - op;
  989. op = oend_w;
  990. }
  991. while (op < oMatchEnd)
  992. *op++ = *match++;
  993. } else {
  994. ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength - 8); /* works even if matchLength < 8 */
  995. }
  996. return sequenceLength;
  997. }
  998. static size_t ZSTD_decompressSequences(ZSTD_DCtx *dctx, void *dst, size_t maxDstSize, const void *seqStart, size_t seqSize)
  999. {
  1000. const BYTE *ip = (const BYTE *)seqStart;
  1001. const BYTE *const iend = ip + seqSize;
  1002. BYTE *const ostart = (BYTE * const)dst;
  1003. BYTE *const oend = ostart + maxDstSize;
  1004. BYTE *op = ostart;
  1005. const BYTE *litPtr = dctx->litPtr;
  1006. const BYTE *const litEnd = litPtr + dctx->litSize;
  1007. const BYTE *const base = (const BYTE *)(dctx->base);
  1008. const BYTE *const vBase = (const BYTE *)(dctx->vBase);
  1009. const BYTE *const dictEnd = (const BYTE *)(dctx->dictEnd);
  1010. int nbSeq;
  1011. /* Build Decoding Tables */
  1012. {
  1013. size_t const seqHSize = ZSTD_decodeSeqHeaders(dctx, &nbSeq, ip, seqSize);
  1014. if (ZSTD_isError(seqHSize))
  1015. return seqHSize;
  1016. ip += seqHSize;
  1017. }
  1018. /* Regen sequences */
  1019. if (nbSeq) {
  1020. seqState_t seqState;
  1021. dctx->fseEntropy = 1;
  1022. {
  1023. U32 i;
  1024. for (i = 0; i < ZSTD_REP_NUM; i++)
  1025. seqState.prevOffset[i] = dctx->entropy.rep[i];
  1026. }
  1027. CHECK_E(BIT_initDStream(&seqState.DStream, ip, iend - ip), corruption_detected);
  1028. FSE_initDState(&seqState.stateLL, &seqState.DStream, dctx->LLTptr);
  1029. FSE_initDState(&seqState.stateOffb, &seqState.DStream, dctx->OFTptr);
  1030. FSE_initDState(&seqState.stateML, &seqState.DStream, dctx->MLTptr);
  1031. for (; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && nbSeq;) {
  1032. nbSeq--;
  1033. {
  1034. seq_t const sequence = ZSTD_decodeSequence(&seqState);
  1035. size_t const oneSeqSize = ZSTD_execSequence(op, oend, sequence, &litPtr, litEnd, base, vBase, dictEnd);
  1036. if (ZSTD_isError(oneSeqSize))
  1037. return oneSeqSize;
  1038. op += oneSeqSize;
  1039. }
  1040. }
  1041. /* check if reached exact end */
  1042. if (nbSeq)
  1043. return ERROR(corruption_detected);
  1044. /* save reps for next block */
  1045. {
  1046. U32 i;
  1047. for (i = 0; i < ZSTD_REP_NUM; i++)
  1048. dctx->entropy.rep[i] = (U32)(seqState.prevOffset[i]);
  1049. }
  1050. }
  1051. /* last literal segment */
  1052. {
  1053. size_t const lastLLSize = litEnd - litPtr;
  1054. if (lastLLSize > (size_t)(oend - op))
  1055. return ERROR(dstSize_tooSmall);
  1056. memcpy(op, litPtr, lastLLSize);
  1057. op += lastLLSize;
  1058. }
  1059. return op - ostart;
  1060. }
  1061. FORCE_INLINE seq_t ZSTD_decodeSequenceLong_generic(seqState_t *seqState, int const longOffsets)
  1062. {
  1063. seq_t seq;
  1064. U32 const llCode = FSE_peekSymbol(&seqState->stateLL);
  1065. U32 const mlCode = FSE_peekSymbol(&seqState->stateML);
  1066. U32 const ofCode = FSE_peekSymbol(&seqState->stateOffb); /* <= maxOff, by table construction */
  1067. U32 const llBits = LL_bits[llCode];
  1068. U32 const mlBits = ML_bits[mlCode];
  1069. U32 const ofBits = ofCode;
  1070. U32 const totalBits = llBits + mlBits + ofBits;
  1071. static const U32 LL_base[MaxLL + 1] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18,
  1072. 20, 22, 24, 28, 32, 40, 48, 64, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000, 0x2000, 0x4000, 0x8000, 0x10000};
  1073. static const U32 ML_base[MaxML + 1] = {3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
  1074. 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 37, 39, 41,
  1075. 43, 47, 51, 59, 67, 83, 99, 0x83, 0x103, 0x203, 0x403, 0x803, 0x1003, 0x2003, 0x4003, 0x8003, 0x10003};
  1076. static const U32 OF_base[MaxOff + 1] = {0, 1, 1, 5, 0xD, 0x1D, 0x3D, 0x7D, 0xFD, 0x1FD,
  1077. 0x3FD, 0x7FD, 0xFFD, 0x1FFD, 0x3FFD, 0x7FFD, 0xFFFD, 0x1FFFD, 0x3FFFD, 0x7FFFD,
  1078. 0xFFFFD, 0x1FFFFD, 0x3FFFFD, 0x7FFFFD, 0xFFFFFD, 0x1FFFFFD, 0x3FFFFFD, 0x7FFFFFD, 0xFFFFFFD};
  1079. /* sequence */
  1080. {
  1081. size_t offset;
  1082. if (!ofCode)
  1083. offset = 0;
  1084. else {
  1085. if (longOffsets) {
  1086. int const extraBits = ofBits - MIN(ofBits, STREAM_ACCUMULATOR_MIN);
  1087. offset = OF_base[ofCode] + (BIT_readBitsFast(&seqState->DStream, ofBits - extraBits) << extraBits);
  1088. if (ZSTD_32bits() || extraBits)
  1089. BIT_reloadDStream(&seqState->DStream);
  1090. if (extraBits)
  1091. offset += BIT_readBitsFast(&seqState->DStream, extraBits);
  1092. } else {
  1093. offset = OF_base[ofCode] + BIT_readBitsFast(&seqState->DStream, ofBits); /* <= (ZSTD_WINDOWLOG_MAX-1) bits */
  1094. if (ZSTD_32bits())
  1095. BIT_reloadDStream(&seqState->DStream);
  1096. }
  1097. }
  1098. if (ofCode <= 1) {
  1099. offset += (llCode == 0);
  1100. if (offset) {
  1101. size_t temp = (offset == 3) ? seqState->prevOffset[0] - 1 : seqState->prevOffset[offset];
  1102. temp += !temp; /* 0 is not valid; input is corrupted; force offset to 1 */
  1103. if (offset != 1)
  1104. seqState->prevOffset[2] = seqState->prevOffset[1];
  1105. seqState->prevOffset[1] = seqState->prevOffset[0];
  1106. seqState->prevOffset[0] = offset = temp;
  1107. } else {
  1108. offset = seqState->prevOffset[0];
  1109. }
  1110. } else {
  1111. seqState->prevOffset[2] = seqState->prevOffset[1];
  1112. seqState->prevOffset[1] = seqState->prevOffset[0];
  1113. seqState->prevOffset[0] = offset;
  1114. }
  1115. seq.offset = offset;
  1116. }
  1117. seq.matchLength = ML_base[mlCode] + ((mlCode > 31) ? BIT_readBitsFast(&seqState->DStream, mlBits) : 0); /* <= 16 bits */
  1118. if (ZSTD_32bits() && (mlBits + llBits > 24))
  1119. BIT_reloadDStream(&seqState->DStream);
  1120. seq.litLength = LL_base[llCode] + ((llCode > 15) ? BIT_readBitsFast(&seqState->DStream, llBits) : 0); /* <= 16 bits */
  1121. if (ZSTD_32bits() || (totalBits > 64 - 7 - (LLFSELog + MLFSELog + OffFSELog)))
  1122. BIT_reloadDStream(&seqState->DStream);
  1123. {
  1124. size_t const pos = seqState->pos + seq.litLength;
  1125. seq.match = seqState->base + pos - seq.offset; /* single memory segment */
  1126. if (seq.offset > pos)
  1127. seq.match += seqState->gotoDict; /* separate memory segment */
  1128. seqState->pos = pos + seq.matchLength;
  1129. }
  1130. /* ANS state update */
  1131. FSE_updateState(&seqState->stateLL, &seqState->DStream); /* <= 9 bits */
  1132. FSE_updateState(&seqState->stateML, &seqState->DStream); /* <= 9 bits */
  1133. if (ZSTD_32bits())
  1134. BIT_reloadDStream(&seqState->DStream); /* <= 18 bits */
  1135. FSE_updateState(&seqState->stateOffb, &seqState->DStream); /* <= 8 bits */
  1136. return seq;
  1137. }
  1138. static seq_t ZSTD_decodeSequenceLong(seqState_t *seqState, unsigned const windowSize)
  1139. {
  1140. if (ZSTD_highbit32(windowSize) > STREAM_ACCUMULATOR_MIN) {
  1141. return ZSTD_decodeSequenceLong_generic(seqState, 1);
  1142. } else {
  1143. return ZSTD_decodeSequenceLong_generic(seqState, 0);
  1144. }
  1145. }
  1146. FORCE_INLINE
  1147. size_t ZSTD_execSequenceLong(BYTE *op, BYTE *const oend, seq_t sequence, const BYTE **litPtr, const BYTE *const litLimit, const BYTE *const base,
  1148. const BYTE *const vBase, const BYTE *const dictEnd)
  1149. {
  1150. BYTE *const oLitEnd = op + sequence.litLength;
  1151. size_t const sequenceLength = sequence.litLength + sequence.matchLength;
  1152. BYTE *const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */
  1153. BYTE *const oend_w = oend - WILDCOPY_OVERLENGTH;
  1154. const BYTE *const iLitEnd = *litPtr + sequence.litLength;
  1155. const BYTE *match = sequence.match;
  1156. /* check */
  1157. if (oMatchEnd > oend)
  1158. return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of WILDCOPY_OVERLENGTH from oend */
  1159. if (iLitEnd > litLimit)
  1160. return ERROR(corruption_detected); /* over-read beyond lit buffer */
  1161. if (oLitEnd > oend_w)
  1162. return ZSTD_execSequenceLast7(op, oend, sequence, litPtr, litLimit, base, vBase, dictEnd);
  1163. /* copy Literals */
  1164. ZSTD_copy8(op, *litPtr);
  1165. if (sequence.litLength > 8)
  1166. ZSTD_wildcopy(op + 8, (*litPtr) + 8,
  1167. sequence.litLength - 8); /* note : since oLitEnd <= oend-WILDCOPY_OVERLENGTH, no risk of overwrite beyond oend */
  1168. op = oLitEnd;
  1169. *litPtr = iLitEnd; /* update for next sequence */
  1170. /* copy Match */
  1171. if (sequence.offset > (size_t)(oLitEnd - base)) {
  1172. /* offset beyond prefix */
  1173. if (sequence.offset > (size_t)(oLitEnd - vBase))
  1174. return ERROR(corruption_detected);
  1175. if (match + sequence.matchLength <= dictEnd) {
  1176. memmove(oLitEnd, match, sequence.matchLength);
  1177. return sequenceLength;
  1178. }
  1179. /* span extDict & currPrefixSegment */
  1180. {
  1181. size_t const length1 = dictEnd - match;
  1182. memmove(oLitEnd, match, length1);
  1183. op = oLitEnd + length1;
  1184. sequence.matchLength -= length1;
  1185. match = base;
  1186. if (op > oend_w || sequence.matchLength < MINMATCH) {
  1187. U32 i;
  1188. for (i = 0; i < sequence.matchLength; ++i)
  1189. op[i] = match[i];
  1190. return sequenceLength;
  1191. }
  1192. }
  1193. }
  1194. /* Requirement: op <= oend_w && sequence.matchLength >= MINMATCH */
  1195. /* match within prefix */
  1196. if (sequence.offset < 8) {
  1197. /* close range match, overlap */
  1198. static const U32 dec32table[] = {0, 1, 2, 1, 4, 4, 4, 4}; /* added */
  1199. static const int dec64table[] = {8, 8, 8, 7, 8, 9, 10, 11}; /* subtracted */
  1200. int const sub2 = dec64table[sequence.offset];
  1201. op[0] = match[0];
  1202. op[1] = match[1];
  1203. op[2] = match[2];
  1204. op[3] = match[3];
  1205. match += dec32table[sequence.offset];
  1206. ZSTD_copy4(op + 4, match);
  1207. match -= sub2;
  1208. } else {
  1209. ZSTD_copy8(op, match);
  1210. }
  1211. op += 8;
  1212. match += 8;
  1213. if (oMatchEnd > oend - (16 - MINMATCH)) {
  1214. if (op < oend_w) {
  1215. ZSTD_wildcopy(op, match, oend_w - op);
  1216. match += oend_w - op;
  1217. op = oend_w;
  1218. }
  1219. while (op < oMatchEnd)
  1220. *op++ = *match++;
  1221. } else {
  1222. ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength - 8); /* works even if matchLength < 8 */
  1223. }
  1224. return sequenceLength;
  1225. }
  1226. static size_t ZSTD_decompressSequencesLong(ZSTD_DCtx *dctx, void *dst, size_t maxDstSize, const void *seqStart, size_t seqSize)
  1227. {
  1228. const BYTE *ip = (const BYTE *)seqStart;
  1229. const BYTE *const iend = ip + seqSize;
  1230. BYTE *const ostart = (BYTE * const)dst;
  1231. BYTE *const oend = ostart + maxDstSize;
  1232. BYTE *op = ostart;
  1233. const BYTE *litPtr = dctx->litPtr;
  1234. const BYTE *const litEnd = litPtr + dctx->litSize;
  1235. const BYTE *const base = (const BYTE *)(dctx->base);
  1236. const BYTE *const vBase = (const BYTE *)(dctx->vBase);
  1237. const BYTE *const dictEnd = (const BYTE *)(dctx->dictEnd);
  1238. unsigned const windowSize = dctx->fParams.windowSize;
  1239. int nbSeq;
  1240. /* Build Decoding Tables */
  1241. {
  1242. size_t const seqHSize = ZSTD_decodeSeqHeaders(dctx, &nbSeq, ip, seqSize);
  1243. if (ZSTD_isError(seqHSize))
  1244. return seqHSize;
  1245. ip += seqHSize;
  1246. }
  1247. /* Regen sequences */
  1248. if (nbSeq) {
  1249. #define STORED_SEQS 4
  1250. #define STOSEQ_MASK (STORED_SEQS - 1)
  1251. #define ADVANCED_SEQS 4
  1252. seq_t *sequences = (seq_t *)dctx->entropy.workspace;
  1253. int const seqAdvance = MIN(nbSeq, ADVANCED_SEQS);
  1254. seqState_t seqState;
  1255. int seqNb;
  1256. ZSTD_STATIC_ASSERT(sizeof(dctx->entropy.workspace) >= sizeof(seq_t) * STORED_SEQS);
  1257. dctx->fseEntropy = 1;
  1258. {
  1259. U32 i;
  1260. for (i = 0; i < ZSTD_REP_NUM; i++)
  1261. seqState.prevOffset[i] = dctx->entropy.rep[i];
  1262. }
  1263. seqState.base = base;
  1264. seqState.pos = (size_t)(op - base);
  1265. seqState.gotoDict = (uPtrDiff)dictEnd - (uPtrDiff)base; /* cast to avoid undefined behaviour */
  1266. CHECK_E(BIT_initDStream(&seqState.DStream, ip, iend - ip), corruption_detected);
  1267. FSE_initDState(&seqState.stateLL, &seqState.DStream, dctx->LLTptr);
  1268. FSE_initDState(&seqState.stateOffb, &seqState.DStream, dctx->OFTptr);
  1269. FSE_initDState(&seqState.stateML, &seqState.DStream, dctx->MLTptr);
  1270. /* prepare in advance */
  1271. for (seqNb = 0; (BIT_reloadDStream(&seqState.DStream) <= BIT_DStream_completed) && seqNb < seqAdvance; seqNb++) {
  1272. sequences[seqNb] = ZSTD_decodeSequenceLong(&seqState, windowSize);
  1273. }
  1274. if (seqNb < seqAdvance)
  1275. return ERROR(corruption_detected);
  1276. /* decode and decompress */
  1277. for (; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && seqNb < nbSeq; seqNb++) {
  1278. seq_t const sequence = ZSTD_decodeSequenceLong(&seqState, windowSize);
  1279. size_t const oneSeqSize =
  1280. ZSTD_execSequenceLong(op, oend, sequences[(seqNb - ADVANCED_SEQS) & STOSEQ_MASK], &litPtr, litEnd, base, vBase, dictEnd);
  1281. if (ZSTD_isError(oneSeqSize))
  1282. return oneSeqSize;
  1283. ZSTD_PREFETCH(sequence.match);
  1284. sequences[seqNb & STOSEQ_MASK] = sequence;
  1285. op += oneSeqSize;
  1286. }
  1287. if (seqNb < nbSeq)
  1288. return ERROR(corruption_detected);
  1289. /* finish queue */
  1290. seqNb -= seqAdvance;
  1291. for (; seqNb < nbSeq; seqNb++) {
  1292. size_t const oneSeqSize = ZSTD_execSequenceLong(op, oend, sequences[seqNb & STOSEQ_MASK], &litPtr, litEnd, base, vBase, dictEnd);
  1293. if (ZSTD_isError(oneSeqSize))
  1294. return oneSeqSize;
  1295. op += oneSeqSize;
  1296. }
  1297. /* save reps for next block */
  1298. {
  1299. U32 i;
  1300. for (i = 0; i < ZSTD_REP_NUM; i++)
  1301. dctx->entropy.rep[i] = (U32)(seqState.prevOffset[i]);
  1302. }
  1303. }
  1304. /* last literal segment */
  1305. {
  1306. size_t const lastLLSize = litEnd - litPtr;
  1307. if (lastLLSize > (size_t)(oend - op))
  1308. return ERROR(dstSize_tooSmall);
  1309. memcpy(op, litPtr, lastLLSize);
  1310. op += lastLLSize;
  1311. }
  1312. return op - ostart;
  1313. }
  1314. static size_t ZSTD_decompressBlock_internal(ZSTD_DCtx *dctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize)
  1315. { /* blockType == blockCompressed */
  1316. const BYTE *ip = (const BYTE *)src;
  1317. if (srcSize >= ZSTD_BLOCKSIZE_ABSOLUTEMAX)
  1318. return ERROR(srcSize_wrong);
  1319. /* Decode literals section */
  1320. {
  1321. size_t const litCSize = ZSTD_decodeLiteralsBlock(dctx, src, srcSize);
  1322. if (ZSTD_isError(litCSize))
  1323. return litCSize;
  1324. ip += litCSize;
  1325. srcSize -= litCSize;
  1326. }
  1327. if (sizeof(size_t) > 4) /* do not enable prefetching on 32-bits x86, as it's performance detrimental */
  1328. /* likely because of register pressure */
  1329. /* if that's the correct cause, then 32-bits ARM should be affected differently */
  1330. /* it would be good to test this on ARM real hardware, to see if prefetch version improves speed */
  1331. if (dctx->fParams.windowSize > (1 << 23))
  1332. return ZSTD_decompressSequencesLong(dctx, dst, dstCapacity, ip, srcSize);
  1333. return ZSTD_decompressSequences(dctx, dst, dstCapacity, ip, srcSize);
  1334. }
  1335. static void ZSTD_checkContinuity(ZSTD_DCtx *dctx, const void *dst)
  1336. {
  1337. if (dst != dctx->previousDstEnd) { /* not contiguous */
  1338. dctx->dictEnd = dctx->previousDstEnd;
  1339. dctx->vBase = (const char *)dst - ((const char *)(dctx->previousDstEnd) - (const char *)(dctx->base));
  1340. dctx->base = dst;
  1341. dctx->previousDstEnd = dst;
  1342. }
  1343. }
  1344. size_t ZSTD_decompressBlock(ZSTD_DCtx *dctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize)
  1345. {
  1346. size_t dSize;
  1347. ZSTD_checkContinuity(dctx, dst);
  1348. dSize = ZSTD_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize);
  1349. dctx->previousDstEnd = (char *)dst + dSize;
  1350. return dSize;
  1351. }
  1352. /** ZSTD_insertBlock() :
  1353. insert `src` block into `dctx` history. Useful to track uncompressed blocks. */
  1354. size_t ZSTD_insertBlock(ZSTD_DCtx *dctx, const void *blockStart, size_t blockSize)
  1355. {
  1356. ZSTD_checkContinuity(dctx, blockStart);
  1357. dctx->previousDstEnd = (const char *)blockStart + blockSize;
  1358. return blockSize;
  1359. }
  1360. size_t ZSTD_generateNxBytes(void *dst, size_t dstCapacity, BYTE byte, size_t length)
  1361. {
  1362. if (length > dstCapacity)
  1363. return ERROR(dstSize_tooSmall);
  1364. memset(dst, byte, length);
  1365. return length;
  1366. }
  1367. /** ZSTD_findFrameCompressedSize() :
  1368. * compatible with legacy mode
  1369. * `src` must point to the start of a ZSTD frame, ZSTD legacy frame, or skippable frame
  1370. * `srcSize` must be at least as large as the frame contained
  1371. * @return : the compressed size of the frame starting at `src` */
  1372. size_t ZSTD_findFrameCompressedSize(const void *src, size_t srcSize)
  1373. {
  1374. if (srcSize >= ZSTD_skippableHeaderSize && (ZSTD_readLE32(src) & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START) {
  1375. return ZSTD_skippableHeaderSize + ZSTD_readLE32((const BYTE *)src + 4);
  1376. } else {
  1377. const BYTE *ip = (const BYTE *)src;
  1378. const BYTE *const ipstart = ip;
  1379. size_t remainingSize = srcSize;
  1380. ZSTD_frameParams fParams;
  1381. size_t const headerSize = ZSTD_frameHeaderSize(ip, remainingSize);
  1382. if (ZSTD_isError(headerSize))
  1383. return headerSize;
  1384. /* Frame Header */
  1385. {
  1386. size_t const ret = ZSTD_getFrameParams(&fParams, ip, remainingSize);
  1387. if (ZSTD_isError(ret))
  1388. return ret;
  1389. if (ret > 0)
  1390. return ERROR(srcSize_wrong);
  1391. }
  1392. ip += headerSize;
  1393. remainingSize -= headerSize;
  1394. /* Loop on each block */
  1395. while (1) {
  1396. blockProperties_t blockProperties;
  1397. size_t const cBlockSize = ZSTD_getcBlockSize(ip, remainingSize, &blockProperties);
  1398. if (ZSTD_isError(cBlockSize))
  1399. return cBlockSize;
  1400. if (ZSTD_blockHeaderSize + cBlockSize > remainingSize)
  1401. return ERROR(srcSize_wrong);
  1402. ip += ZSTD_blockHeaderSize + cBlockSize;
  1403. remainingSize -= ZSTD_blockHeaderSize + cBlockSize;
  1404. if (blockProperties.lastBlock)
  1405. break;
  1406. }
  1407. if (fParams.checksumFlag) { /* Frame content checksum */
  1408. if (remainingSize < 4)
  1409. return ERROR(srcSize_wrong);
  1410. ip += 4;
  1411. remainingSize -= 4;
  1412. }
  1413. return ip - ipstart;
  1414. }
  1415. }
  1416. /*! ZSTD_decompressFrame() :
  1417. * @dctx must be properly initialized */
  1418. static size_t ZSTD_decompressFrame(ZSTD_DCtx *dctx, void *dst, size_t dstCapacity, const void **srcPtr, size_t *srcSizePtr)
  1419. {
  1420. const BYTE *ip = (const BYTE *)(*srcPtr);
  1421. BYTE *const ostart = (BYTE * const)dst;
  1422. BYTE *const oend = ostart + dstCapacity;
  1423. BYTE *op = ostart;
  1424. size_t remainingSize = *srcSizePtr;
  1425. /* check */
  1426. if (remainingSize < ZSTD_frameHeaderSize_min + ZSTD_blockHeaderSize)
  1427. return ERROR(srcSize_wrong);
  1428. /* Frame Header */
  1429. {
  1430. size_t const frameHeaderSize = ZSTD_frameHeaderSize(ip, ZSTD_frameHeaderSize_prefix);
  1431. if (ZSTD_isError(frameHeaderSize))
  1432. return frameHeaderSize;
  1433. if (remainingSize < frameHeaderSize + ZSTD_blockHeaderSize)
  1434. return ERROR(srcSize_wrong);
  1435. CHECK_F(ZSTD_decodeFrameHeader(dctx, ip, frameHeaderSize));
  1436. ip += frameHeaderSize;
  1437. remainingSize -= frameHeaderSize;
  1438. }
  1439. /* Loop on each block */
  1440. while (1) {
  1441. size_t decodedSize;
  1442. blockProperties_t blockProperties;
  1443. size_t const cBlockSize = ZSTD_getcBlockSize(ip, remainingSize, &blockProperties);
  1444. if (ZSTD_isError(cBlockSize))
  1445. return cBlockSize;
  1446. ip += ZSTD_blockHeaderSize;
  1447. remainingSize -= ZSTD_blockHeaderSize;
  1448. if (cBlockSize > remainingSize)
  1449. return ERROR(srcSize_wrong);
  1450. switch (blockProperties.blockType) {
  1451. case bt_compressed: decodedSize = ZSTD_decompressBlock_internal(dctx, op, oend - op, ip, cBlockSize); break;
  1452. case bt_raw: decodedSize = ZSTD_copyRawBlock(op, oend - op, ip, cBlockSize); break;
  1453. case bt_rle: decodedSize = ZSTD_generateNxBytes(op, oend - op, *ip, blockProperties.origSize); break;
  1454. case bt_reserved:
  1455. default: return ERROR(corruption_detected);
  1456. }
  1457. if (ZSTD_isError(decodedSize))
  1458. return decodedSize;
  1459. if (dctx->fParams.checksumFlag)
  1460. xxh64_update(&dctx->xxhState, op, decodedSize);
  1461. op += decodedSize;
  1462. ip += cBlockSize;
  1463. remainingSize -= cBlockSize;
  1464. if (blockProperties.lastBlock)
  1465. break;
  1466. }
  1467. if (dctx->fParams.checksumFlag) { /* Frame content checksum verification */
  1468. U32 const checkCalc = (U32)xxh64_digest(&dctx->xxhState);
  1469. U32 checkRead;
  1470. if (remainingSize < 4)
  1471. return ERROR(checksum_wrong);
  1472. checkRead = ZSTD_readLE32(ip);
  1473. if (checkRead != checkCalc)
  1474. return ERROR(checksum_wrong);
  1475. ip += 4;
  1476. remainingSize -= 4;
  1477. }
  1478. /* Allow caller to get size read */
  1479. *srcPtr = ip;
  1480. *srcSizePtr = remainingSize;
  1481. return op - ostart;
  1482. }
  1483. static const void *ZSTD_DDictDictContent(const ZSTD_DDict *ddict);
  1484. static size_t ZSTD_DDictDictSize(const ZSTD_DDict *ddict);
  1485. static size_t ZSTD_decompressMultiFrame(ZSTD_DCtx *dctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize, const void *dict, size_t dictSize,
  1486. const ZSTD_DDict *ddict)
  1487. {
  1488. void *const dststart = dst;
  1489. if (ddict) {
  1490. if (dict) {
  1491. /* programmer error, these two cases should be mutually exclusive */
  1492. return ERROR(GENERIC);
  1493. }
  1494. dict = ZSTD_DDictDictContent(ddict);
  1495. dictSize = ZSTD_DDictDictSize(ddict);
  1496. }
  1497. while (srcSize >= ZSTD_frameHeaderSize_prefix) {
  1498. U32 magicNumber;
  1499. magicNumber = ZSTD_readLE32(src);
  1500. if (magicNumber != ZSTD_MAGICNUMBER) {
  1501. if ((magicNumber & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START) {
  1502. size_t skippableSize;
  1503. if (srcSize < ZSTD_skippableHeaderSize)
  1504. return ERROR(srcSize_wrong);
  1505. skippableSize = ZSTD_readLE32((const BYTE *)src + 4) + ZSTD_skippableHeaderSize;
  1506. if (srcSize < skippableSize) {
  1507. return ERROR(srcSize_wrong);
  1508. }
  1509. src = (const BYTE *)src + skippableSize;
  1510. srcSize -= skippableSize;
  1511. continue;
  1512. } else {
  1513. return ERROR(prefix_unknown);
  1514. }
  1515. }
  1516. if (ddict) {
  1517. /* we were called from ZSTD_decompress_usingDDict */
  1518. ZSTD_refDDict(dctx, ddict);
  1519. } else {
  1520. /* this will initialize correctly with no dict if dict == NULL, so
  1521. * use this in all cases but ddict */
  1522. CHECK_F(ZSTD_decompressBegin_usingDict(dctx, dict, dictSize));
  1523. }
  1524. ZSTD_checkContinuity(dctx, dst);
  1525. {
  1526. const size_t res = ZSTD_decompressFrame(dctx, dst, dstCapacity, &src, &srcSize);
  1527. if (ZSTD_isError(res))
  1528. return res;
  1529. /* don't need to bounds check this, ZSTD_decompressFrame will have
  1530. * already */
  1531. dst = (BYTE *)dst + res;
  1532. dstCapacity -= res;
  1533. }
  1534. }
  1535. if (srcSize)
  1536. return ERROR(srcSize_wrong); /* input not entirely consumed */
  1537. return (BYTE *)dst - (BYTE *)dststart;
  1538. }
  1539. size_t ZSTD_decompress_usingDict(ZSTD_DCtx *dctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize, const void *dict, size_t dictSize)
  1540. {
  1541. return ZSTD_decompressMultiFrame(dctx, dst, dstCapacity, src, srcSize, dict, dictSize, NULL);
  1542. }
  1543. size_t ZSTD_decompressDCtx(ZSTD_DCtx *dctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize)
  1544. {
  1545. return ZSTD_decompress_usingDict(dctx, dst, dstCapacity, src, srcSize, NULL, 0);
  1546. }
  1547. /*-**************************************
  1548. * Advanced Streaming Decompression API
  1549. * Bufferless and synchronous
  1550. ****************************************/
  1551. size_t ZSTD_nextSrcSizeToDecompress(ZSTD_DCtx *dctx) { return dctx->expected; }
  1552. ZSTD_nextInputType_e ZSTD_nextInputType(ZSTD_DCtx *dctx)
  1553. {
  1554. switch (dctx->stage) {
  1555. default: /* should not happen */
  1556. case ZSTDds_getFrameHeaderSize:
  1557. case ZSTDds_decodeFrameHeader: return ZSTDnit_frameHeader;
  1558. case ZSTDds_decodeBlockHeader: return ZSTDnit_blockHeader;
  1559. case ZSTDds_decompressBlock: return ZSTDnit_block;
  1560. case ZSTDds_decompressLastBlock: return ZSTDnit_lastBlock;
  1561. case ZSTDds_checkChecksum: return ZSTDnit_checksum;
  1562. case ZSTDds_decodeSkippableHeader:
  1563. case ZSTDds_skipFrame: return ZSTDnit_skippableFrame;
  1564. }
  1565. }
  1566. int ZSTD_isSkipFrame(ZSTD_DCtx *dctx) { return dctx->stage == ZSTDds_skipFrame; } /* for zbuff */
  1567. /** ZSTD_decompressContinue() :
  1568. * @return : nb of bytes generated into `dst` (necessarily <= `dstCapacity)
  1569. * or an error code, which can be tested using ZSTD_isError() */
  1570. size_t ZSTD_decompressContinue(ZSTD_DCtx *dctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize)
  1571. {
  1572. /* Sanity check */
  1573. if (srcSize != dctx->expected)
  1574. return ERROR(srcSize_wrong);
  1575. if (dstCapacity)
  1576. ZSTD_checkContinuity(dctx, dst);
  1577. switch (dctx->stage) {
  1578. case ZSTDds_getFrameHeaderSize:
  1579. if (srcSize != ZSTD_frameHeaderSize_prefix)
  1580. return ERROR(srcSize_wrong); /* impossible */
  1581. if ((ZSTD_readLE32(src) & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START) { /* skippable frame */
  1582. memcpy(dctx->headerBuffer, src, ZSTD_frameHeaderSize_prefix);
  1583. dctx->expected = ZSTD_skippableHeaderSize - ZSTD_frameHeaderSize_prefix; /* magic number + skippable frame length */
  1584. dctx->stage = ZSTDds_decodeSkippableHeader;
  1585. return 0;
  1586. }
  1587. dctx->headerSize = ZSTD_frameHeaderSize(src, ZSTD_frameHeaderSize_prefix);
  1588. if (ZSTD_isError(dctx->headerSize))
  1589. return dctx->headerSize;
  1590. memcpy(dctx->headerBuffer, src, ZSTD_frameHeaderSize_prefix);
  1591. if (dctx->headerSize > ZSTD_frameHeaderSize_prefix) {
  1592. dctx->expected = dctx->headerSize - ZSTD_frameHeaderSize_prefix;
  1593. dctx->stage = ZSTDds_decodeFrameHeader;
  1594. return 0;
  1595. }
  1596. dctx->expected = 0; /* not necessary to copy more */
  1597. case ZSTDds_decodeFrameHeader:
  1598. memcpy(dctx->headerBuffer + ZSTD_frameHeaderSize_prefix, src, dctx->expected);
  1599. CHECK_F(ZSTD_decodeFrameHeader(dctx, dctx->headerBuffer, dctx->headerSize));
  1600. dctx->expected = ZSTD_blockHeaderSize;
  1601. dctx->stage = ZSTDds_decodeBlockHeader;
  1602. return 0;
  1603. case ZSTDds_decodeBlockHeader: {
  1604. blockProperties_t bp;
  1605. size_t const cBlockSize = ZSTD_getcBlockSize(src, ZSTD_blockHeaderSize, &bp);
  1606. if (ZSTD_isError(cBlockSize))
  1607. return cBlockSize;
  1608. dctx->expected = cBlockSize;
  1609. dctx->bType = bp.blockType;
  1610. dctx->rleSize = bp.origSize;
  1611. if (cBlockSize) {
  1612. dctx->stage = bp.lastBlock ? ZSTDds_decompressLastBlock : ZSTDds_decompressBlock;
  1613. return 0;
  1614. }
  1615. /* empty block */
  1616. if (bp.lastBlock) {
  1617. if (dctx->fParams.checksumFlag) {
  1618. dctx->expected = 4;
  1619. dctx->stage = ZSTDds_checkChecksum;
  1620. } else {
  1621. dctx->expected = 0; /* end of frame */
  1622. dctx->stage = ZSTDds_getFrameHeaderSize;
  1623. }
  1624. } else {
  1625. dctx->expected = 3; /* go directly to next header */
  1626. dctx->stage = ZSTDds_decodeBlockHeader;
  1627. }
  1628. return 0;
  1629. }
  1630. case ZSTDds_decompressLastBlock:
  1631. case ZSTDds_decompressBlock: {
  1632. size_t rSize;
  1633. switch (dctx->bType) {
  1634. case bt_compressed: rSize = ZSTD_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize); break;
  1635. case bt_raw: rSize = ZSTD_copyRawBlock(dst, dstCapacity, src, srcSize); break;
  1636. case bt_rle: rSize = ZSTD_setRleBlock(dst, dstCapacity, src, srcSize, dctx->rleSize); break;
  1637. case bt_reserved: /* should never happen */
  1638. default: return ERROR(corruption_detected);
  1639. }
  1640. if (ZSTD_isError(rSize))
  1641. return rSize;
  1642. if (dctx->fParams.checksumFlag)
  1643. xxh64_update(&dctx->xxhState, dst, rSize);
  1644. if (dctx->stage == ZSTDds_decompressLastBlock) { /* end of frame */
  1645. if (dctx->fParams.checksumFlag) { /* another round for frame checksum */
  1646. dctx->expected = 4;
  1647. dctx->stage = ZSTDds_checkChecksum;
  1648. } else {
  1649. dctx->expected = 0; /* ends here */
  1650. dctx->stage = ZSTDds_getFrameHeaderSize;
  1651. }
  1652. } else {
  1653. dctx->stage = ZSTDds_decodeBlockHeader;
  1654. dctx->expected = ZSTD_blockHeaderSize;
  1655. dctx->previousDstEnd = (char *)dst + rSize;
  1656. }
  1657. return rSize;
  1658. }
  1659. case ZSTDds_checkChecksum: {
  1660. U32 const h32 = (U32)xxh64_digest(&dctx->xxhState);
  1661. U32 const check32 = ZSTD_readLE32(src); /* srcSize == 4, guaranteed by dctx->expected */
  1662. if (check32 != h32)
  1663. return ERROR(checksum_wrong);
  1664. dctx->expected = 0;
  1665. dctx->stage = ZSTDds_getFrameHeaderSize;
  1666. return 0;
  1667. }
  1668. case ZSTDds_decodeSkippableHeader: {
  1669. memcpy(dctx->headerBuffer + ZSTD_frameHeaderSize_prefix, src, dctx->expected);
  1670. dctx->expected = ZSTD_readLE32(dctx->headerBuffer + 4);
  1671. dctx->stage = ZSTDds_skipFrame;
  1672. return 0;
  1673. }
  1674. case ZSTDds_skipFrame: {
  1675. dctx->expected = 0;
  1676. dctx->stage = ZSTDds_getFrameHeaderSize;
  1677. return 0;
  1678. }
  1679. default:
  1680. return ERROR(GENERIC); /* impossible */
  1681. }
  1682. }
  1683. static size_t ZSTD_refDictContent(ZSTD_DCtx *dctx, const void *dict, size_t dictSize)
  1684. {
  1685. dctx->dictEnd = dctx->previousDstEnd;
  1686. dctx->vBase = (const char *)dict - ((const char *)(dctx->previousDstEnd) - (const char *)(dctx->base));
  1687. dctx->base = dict;
  1688. dctx->previousDstEnd = (const char *)dict + dictSize;
  1689. return 0;
  1690. }
  1691. /* ZSTD_loadEntropy() :
  1692. * dict : must point at beginning of a valid zstd dictionary
  1693. * @return : size of entropy tables read */
  1694. static size_t ZSTD_loadEntropy(ZSTD_entropyTables_t *entropy, const void *const dict, size_t const dictSize)
  1695. {
  1696. const BYTE *dictPtr = (const BYTE *)dict;
  1697. const BYTE *const dictEnd = dictPtr + dictSize;
  1698. if (dictSize <= 8)
  1699. return ERROR(dictionary_corrupted);
  1700. dictPtr += 8; /* skip header = magic + dictID */
  1701. {
  1702. size_t const hSize = HUF_readDTableX4_wksp(entropy->hufTable, dictPtr, dictEnd - dictPtr, entropy->workspace, sizeof(entropy->workspace));
  1703. if (HUF_isError(hSize))
  1704. return ERROR(dictionary_corrupted);
  1705. dictPtr += hSize;
  1706. }
  1707. {
  1708. short offcodeNCount[MaxOff + 1];
  1709. U32 offcodeMaxValue = MaxOff, offcodeLog;
  1710. size_t const offcodeHeaderSize = FSE_readNCount(offcodeNCount, &offcodeMaxValue, &offcodeLog, dictPtr, dictEnd - dictPtr);
  1711. if (FSE_isError(offcodeHeaderSize))
  1712. return ERROR(dictionary_corrupted);
  1713. if (offcodeLog > OffFSELog)
  1714. return ERROR(dictionary_corrupted);
  1715. CHECK_E(FSE_buildDTable_wksp(entropy->OFTable, offcodeNCount, offcodeMaxValue, offcodeLog, entropy->workspace, sizeof(entropy->workspace)), dictionary_corrupted);
  1716. dictPtr += offcodeHeaderSize;
  1717. }
  1718. {
  1719. short matchlengthNCount[MaxML + 1];
  1720. unsigned matchlengthMaxValue = MaxML, matchlengthLog;
  1721. size_t const matchlengthHeaderSize = FSE_readNCount(matchlengthNCount, &matchlengthMaxValue, &matchlengthLog, dictPtr, dictEnd - dictPtr);
  1722. if (FSE_isError(matchlengthHeaderSize))
  1723. return ERROR(dictionary_corrupted);
  1724. if (matchlengthLog > MLFSELog)
  1725. return ERROR(dictionary_corrupted);
  1726. CHECK_E(FSE_buildDTable_wksp(entropy->MLTable, matchlengthNCount, matchlengthMaxValue, matchlengthLog, entropy->workspace, sizeof(entropy->workspace)), dictionary_corrupted);
  1727. dictPtr += matchlengthHeaderSize;
  1728. }
  1729. {
  1730. short litlengthNCount[MaxLL + 1];
  1731. unsigned litlengthMaxValue = MaxLL, litlengthLog;
  1732. size_t const litlengthHeaderSize = FSE_readNCount(litlengthNCount, &litlengthMaxValue, &litlengthLog, dictPtr, dictEnd - dictPtr);
  1733. if (FSE_isError(litlengthHeaderSize))
  1734. return ERROR(dictionary_corrupted);
  1735. if (litlengthLog > LLFSELog)
  1736. return ERROR(dictionary_corrupted);
  1737. CHECK_E(FSE_buildDTable_wksp(entropy->LLTable, litlengthNCount, litlengthMaxValue, litlengthLog, entropy->workspace, sizeof(entropy->workspace)), dictionary_corrupted);
  1738. dictPtr += litlengthHeaderSize;
  1739. }
  1740. if (dictPtr + 12 > dictEnd)
  1741. return ERROR(dictionary_corrupted);
  1742. {
  1743. int i;
  1744. size_t const dictContentSize = (size_t)(dictEnd - (dictPtr + 12));
  1745. for (i = 0; i < 3; i++) {
  1746. U32 const rep = ZSTD_readLE32(dictPtr);
  1747. dictPtr += 4;
  1748. if (rep == 0 || rep >= dictContentSize)
  1749. return ERROR(dictionary_corrupted);
  1750. entropy->rep[i] = rep;
  1751. }
  1752. }
  1753. return dictPtr - (const BYTE *)dict;
  1754. }
  1755. static size_t ZSTD_decompress_insertDictionary(ZSTD_DCtx *dctx, const void *dict, size_t dictSize)
  1756. {
  1757. if (dictSize < 8)
  1758. return ZSTD_refDictContent(dctx, dict, dictSize);
  1759. {
  1760. U32 const magic = ZSTD_readLE32(dict);
  1761. if (magic != ZSTD_DICT_MAGIC) {
  1762. return ZSTD_refDictContent(dctx, dict, dictSize); /* pure content mode */
  1763. }
  1764. }
  1765. dctx->dictID = ZSTD_readLE32((const char *)dict + 4);
  1766. /* load entropy tables */
  1767. {
  1768. size_t const eSize = ZSTD_loadEntropy(&dctx->entropy, dict, dictSize);
  1769. if (ZSTD_isError(eSize))
  1770. return ERROR(dictionary_corrupted);
  1771. dict = (const char *)dict + eSize;
  1772. dictSize -= eSize;
  1773. }
  1774. dctx->litEntropy = dctx->fseEntropy = 1;
  1775. /* reference dictionary content */
  1776. return ZSTD_refDictContent(dctx, dict, dictSize);
  1777. }
  1778. size_t ZSTD_decompressBegin_usingDict(ZSTD_DCtx *dctx, const void *dict, size_t dictSize)
  1779. {
  1780. CHECK_F(ZSTD_decompressBegin(dctx));
  1781. if (dict && dictSize)
  1782. CHECK_E(ZSTD_decompress_insertDictionary(dctx, dict, dictSize), dictionary_corrupted);
  1783. return 0;
  1784. }
  1785. /* ====== ZSTD_DDict ====== */
  1786. struct ZSTD_DDict_s {
  1787. void *dictBuffer;
  1788. const void *dictContent;
  1789. size_t dictSize;
  1790. ZSTD_entropyTables_t entropy;
  1791. U32 dictID;
  1792. U32 entropyPresent;
  1793. ZSTD_customMem cMem;
  1794. }; /* typedef'd to ZSTD_DDict within "zstd.h" */
  1795. size_t ZSTD_DDictWorkspaceBound(void) { return ZSTD_ALIGN(sizeof(ZSTD_stack)) + ZSTD_ALIGN(sizeof(ZSTD_DDict)); }
  1796. static const void *ZSTD_DDictDictContent(const ZSTD_DDict *ddict) { return ddict->dictContent; }
  1797. static size_t ZSTD_DDictDictSize(const ZSTD_DDict *ddict) { return ddict->dictSize; }
  1798. static void ZSTD_refDDict(ZSTD_DCtx *dstDCtx, const ZSTD_DDict *ddict)
  1799. {
  1800. ZSTD_decompressBegin(dstDCtx); /* init */
  1801. if (ddict) { /* support refDDict on NULL */
  1802. dstDCtx->dictID = ddict->dictID;
  1803. dstDCtx->base = ddict->dictContent;
  1804. dstDCtx->vBase = ddict->dictContent;
  1805. dstDCtx->dictEnd = (const BYTE *)ddict->dictContent + ddict->dictSize;
  1806. dstDCtx->previousDstEnd = dstDCtx->dictEnd;
  1807. if (ddict->entropyPresent) {
  1808. dstDCtx->litEntropy = 1;
  1809. dstDCtx->fseEntropy = 1;
  1810. dstDCtx->LLTptr = ddict->entropy.LLTable;
  1811. dstDCtx->MLTptr = ddict->entropy.MLTable;
  1812. dstDCtx->OFTptr = ddict->entropy.OFTable;
  1813. dstDCtx->HUFptr = ddict->entropy.hufTable;
  1814. dstDCtx->entropy.rep[0] = ddict->entropy.rep[0];
  1815. dstDCtx->entropy.rep[1] = ddict->entropy.rep[1];
  1816. dstDCtx->entropy.rep[2] = ddict->entropy.rep[2];
  1817. } else {
  1818. dstDCtx->litEntropy = 0;
  1819. dstDCtx->fseEntropy = 0;
  1820. }
  1821. }
  1822. }
  1823. static size_t ZSTD_loadEntropy_inDDict(ZSTD_DDict *ddict)
  1824. {
  1825. ddict->dictID = 0;
  1826. ddict->entropyPresent = 0;
  1827. if (ddict->dictSize < 8)
  1828. return 0;
  1829. {
  1830. U32 const magic = ZSTD_readLE32(ddict->dictContent);
  1831. if (magic != ZSTD_DICT_MAGIC)
  1832. return 0; /* pure content mode */
  1833. }
  1834. ddict->dictID = ZSTD_readLE32((const char *)ddict->dictContent + 4);
  1835. /* load entropy tables */
  1836. CHECK_E(ZSTD_loadEntropy(&ddict->entropy, ddict->dictContent, ddict->dictSize), dictionary_corrupted);
  1837. ddict->entropyPresent = 1;
  1838. return 0;
  1839. }
  1840. static ZSTD_DDict *ZSTD_createDDict_advanced(const void *dict, size_t dictSize, unsigned byReference, ZSTD_customMem customMem)
  1841. {
  1842. if (!customMem.customAlloc || !customMem.customFree)
  1843. return NULL;
  1844. {
  1845. ZSTD_DDict *const ddict = (ZSTD_DDict *)ZSTD_malloc(sizeof(ZSTD_DDict), customMem);
  1846. if (!ddict)
  1847. return NULL;
  1848. ddict->cMem = customMem;
  1849. if ((byReference) || (!dict) || (!dictSize)) {
  1850. ddict->dictBuffer = NULL;
  1851. ddict->dictContent = dict;
  1852. } else {
  1853. void *const internalBuffer = ZSTD_malloc(dictSize, customMem);
  1854. if (!internalBuffer) {
  1855. ZSTD_freeDDict(ddict);
  1856. return NULL;
  1857. }
  1858. memcpy(internalBuffer, dict, dictSize);
  1859. ddict->dictBuffer = internalBuffer;
  1860. ddict->dictContent = internalBuffer;
  1861. }
  1862. ddict->dictSize = dictSize;
  1863. ddict->entropy.hufTable[0] = (HUF_DTable)((HufLog)*0x1000001); /* cover both little and big endian */
  1864. /* parse dictionary content */
  1865. {
  1866. size_t const errorCode = ZSTD_loadEntropy_inDDict(ddict);
  1867. if (ZSTD_isError(errorCode)) {
  1868. ZSTD_freeDDict(ddict);
  1869. return NULL;
  1870. }
  1871. }
  1872. return ddict;
  1873. }
  1874. }
  1875. /*! ZSTD_initDDict() :
  1876. * Create a digested dictionary, to start decompression without startup delay.
  1877. * `dict` content is copied inside DDict.
  1878. * Consequently, `dict` can be released after `ZSTD_DDict` creation */
  1879. ZSTD_DDict *ZSTD_initDDict(const void *dict, size_t dictSize, void *workspace, size_t workspaceSize)
  1880. {
  1881. ZSTD_customMem const stackMem = ZSTD_initStack(workspace, workspaceSize);
  1882. return ZSTD_createDDict_advanced(dict, dictSize, 1, stackMem);
  1883. }
  1884. size_t ZSTD_freeDDict(ZSTD_DDict *ddict)
  1885. {
  1886. if (ddict == NULL)
  1887. return 0; /* support free on NULL */
  1888. {
  1889. ZSTD_customMem const cMem = ddict->cMem;
  1890. ZSTD_free(ddict->dictBuffer, cMem);
  1891. ZSTD_free(ddict, cMem);
  1892. return 0;
  1893. }
  1894. }
  1895. /*! ZSTD_getDictID_fromDict() :
  1896. * Provides the dictID stored within dictionary.
  1897. * if @return == 0, the dictionary is not conformant with Zstandard specification.
  1898. * It can still be loaded, but as a content-only dictionary. */
  1899. unsigned ZSTD_getDictID_fromDict(const void *dict, size_t dictSize)
  1900. {
  1901. if (dictSize < 8)
  1902. return 0;
  1903. if (ZSTD_readLE32(dict) != ZSTD_DICT_MAGIC)
  1904. return 0;
  1905. return ZSTD_readLE32((const char *)dict + 4);
  1906. }
  1907. /*! ZSTD_getDictID_fromDDict() :
  1908. * Provides the dictID of the dictionary loaded into `ddict`.
  1909. * If @return == 0, the dictionary is not conformant to Zstandard specification, or empty.
  1910. * Non-conformant dictionaries can still be loaded, but as content-only dictionaries. */
  1911. unsigned ZSTD_getDictID_fromDDict(const ZSTD_DDict *ddict)
  1912. {
  1913. if (ddict == NULL)
  1914. return 0;
  1915. return ZSTD_getDictID_fromDict(ddict->dictContent, ddict->dictSize);
  1916. }
  1917. /*! ZSTD_getDictID_fromFrame() :
  1918. * Provides the dictID required to decompressed the frame stored within `src`.
  1919. * If @return == 0, the dictID could not be decoded.
  1920. * This could for one of the following reasons :
  1921. * - The frame does not require a dictionary to be decoded (most common case).
  1922. * - The frame was built with dictID intentionally removed. Whatever dictionary is necessary is a hidden information.
  1923. * Note : this use case also happens when using a non-conformant dictionary.
  1924. * - `srcSize` is too small, and as a result, the frame header could not be decoded (only possible if `srcSize < ZSTD_FRAMEHEADERSIZE_MAX`).
  1925. * - This is not a Zstandard frame.
  1926. * When identifying the exact failure cause, it's possible to used ZSTD_getFrameParams(), which will provide a more precise error code. */
  1927. unsigned ZSTD_getDictID_fromFrame(const void *src, size_t srcSize)
  1928. {
  1929. ZSTD_frameParams zfp = {0, 0, 0, 0};
  1930. size_t const hError = ZSTD_getFrameParams(&zfp, src, srcSize);
  1931. if (ZSTD_isError(hError))
  1932. return 0;
  1933. return zfp.dictID;
  1934. }
  1935. /*! ZSTD_decompress_usingDDict() :
  1936. * Decompression using a pre-digested Dictionary
  1937. * Use dictionary without significant overhead. */
  1938. size_t ZSTD_decompress_usingDDict(ZSTD_DCtx *dctx, void *dst, size_t dstCapacity, const void *src, size_t srcSize, const ZSTD_DDict *ddict)
  1939. {
  1940. /* pass content and size in case legacy frames are encountered */
  1941. return ZSTD_decompressMultiFrame(dctx, dst, dstCapacity, src, srcSize, NULL, 0, ddict);
  1942. }
  1943. /*=====================================
  1944. * Streaming decompression
  1945. *====================================*/
  1946. typedef enum { zdss_init, zdss_loadHeader, zdss_read, zdss_load, zdss_flush } ZSTD_dStreamStage;
  1947. /* *** Resource management *** */
  1948. struct ZSTD_DStream_s {
  1949. ZSTD_DCtx *dctx;
  1950. ZSTD_DDict *ddictLocal;
  1951. const ZSTD_DDict *ddict;
  1952. ZSTD_frameParams fParams;
  1953. ZSTD_dStreamStage stage;
  1954. char *inBuff;
  1955. size_t inBuffSize;
  1956. size_t inPos;
  1957. size_t maxWindowSize;
  1958. char *outBuff;
  1959. size_t outBuffSize;
  1960. size_t outStart;
  1961. size_t outEnd;
  1962. size_t blockSize;
  1963. BYTE headerBuffer[ZSTD_FRAMEHEADERSIZE_MAX]; /* tmp buffer to store frame header */
  1964. size_t lhSize;
  1965. ZSTD_customMem customMem;
  1966. void *legacyContext;
  1967. U32 previousLegacyVersion;
  1968. U32 legacyVersion;
  1969. U32 hostageByte;
  1970. }; /* typedef'd to ZSTD_DStream within "zstd.h" */
  1971. size_t ZSTD_DStreamWorkspaceBound(size_t maxWindowSize)
  1972. {
  1973. size_t const blockSize = MIN(maxWindowSize, ZSTD_BLOCKSIZE_ABSOLUTEMAX);
  1974. size_t const inBuffSize = blockSize;
  1975. size_t const outBuffSize = maxWindowSize + blockSize + WILDCOPY_OVERLENGTH * 2;
  1976. return ZSTD_DCtxWorkspaceBound() + ZSTD_ALIGN(sizeof(ZSTD_DStream)) + ZSTD_ALIGN(inBuffSize) + ZSTD_ALIGN(outBuffSize);
  1977. }
  1978. static ZSTD_DStream *ZSTD_createDStream_advanced(ZSTD_customMem customMem)
  1979. {
  1980. ZSTD_DStream *zds;
  1981. if (!customMem.customAlloc || !customMem.customFree)
  1982. return NULL;
  1983. zds = (ZSTD_DStream *)ZSTD_malloc(sizeof(ZSTD_DStream), customMem);
  1984. if (zds == NULL)
  1985. return NULL;
  1986. memset(zds, 0, sizeof(ZSTD_DStream));
  1987. memcpy(&zds->customMem, &customMem, sizeof(ZSTD_customMem));
  1988. zds->dctx = ZSTD_createDCtx_advanced(customMem);
  1989. if (zds->dctx == NULL) {
  1990. ZSTD_freeDStream(zds);
  1991. return NULL;
  1992. }
  1993. zds->stage = zdss_init;
  1994. zds->maxWindowSize = ZSTD_MAXWINDOWSIZE_DEFAULT;
  1995. return zds;
  1996. }
  1997. ZSTD_DStream *ZSTD_initDStream(size_t maxWindowSize, void *workspace, size_t workspaceSize)
  1998. {
  1999. ZSTD_customMem const stackMem = ZSTD_initStack(workspace, workspaceSize);
  2000. ZSTD_DStream *zds = ZSTD_createDStream_advanced(stackMem);
  2001. if (!zds) {
  2002. return NULL;
  2003. }
  2004. zds->maxWindowSize = maxWindowSize;
  2005. zds->stage = zdss_loadHeader;
  2006. zds->lhSize = zds->inPos = zds->outStart = zds->outEnd = 0;
  2007. ZSTD_freeDDict(zds->ddictLocal);
  2008. zds->ddictLocal = NULL;
  2009. zds->ddict = zds->ddictLocal;
  2010. zds->legacyVersion = 0;
  2011. zds->hostageByte = 0;
  2012. {
  2013. size_t const blockSize = MIN(zds->maxWindowSize, ZSTD_BLOCKSIZE_ABSOLUTEMAX);
  2014. size_t const neededOutSize = zds->maxWindowSize + blockSize + WILDCOPY_OVERLENGTH * 2;
  2015. zds->inBuff = (char *)ZSTD_malloc(blockSize, zds->customMem);
  2016. zds->inBuffSize = blockSize;
  2017. zds->outBuff = (char *)ZSTD_malloc(neededOutSize, zds->customMem);
  2018. zds->outBuffSize = neededOutSize;
  2019. if (zds->inBuff == NULL || zds->outBuff == NULL) {
  2020. ZSTD_freeDStream(zds);
  2021. return NULL;
  2022. }
  2023. }
  2024. return zds;
  2025. }
  2026. ZSTD_DStream *ZSTD_initDStream_usingDDict(size_t maxWindowSize, const ZSTD_DDict *ddict, void *workspace, size_t workspaceSize)
  2027. {
  2028. ZSTD_DStream *zds = ZSTD_initDStream(maxWindowSize, workspace, workspaceSize);
  2029. if (zds) {
  2030. zds->ddict = ddict;
  2031. }
  2032. return zds;
  2033. }
  2034. size_t ZSTD_freeDStream(ZSTD_DStream *zds)
  2035. {
  2036. if (zds == NULL)
  2037. return 0; /* support free on null */
  2038. {
  2039. ZSTD_customMem const cMem = zds->customMem;
  2040. ZSTD_freeDCtx(zds->dctx);
  2041. zds->dctx = NULL;
  2042. ZSTD_freeDDict(zds->ddictLocal);
  2043. zds->ddictLocal = NULL;
  2044. ZSTD_free(zds->inBuff, cMem);
  2045. zds->inBuff = NULL;
  2046. ZSTD_free(zds->outBuff, cMem);
  2047. zds->outBuff = NULL;
  2048. ZSTD_free(zds, cMem);
  2049. return 0;
  2050. }
  2051. }
  2052. /* *** Initialization *** */
  2053. size_t ZSTD_DStreamInSize(void) { return ZSTD_BLOCKSIZE_ABSOLUTEMAX + ZSTD_blockHeaderSize; }
  2054. size_t ZSTD_DStreamOutSize(void) { return ZSTD_BLOCKSIZE_ABSOLUTEMAX; }
  2055. size_t ZSTD_resetDStream(ZSTD_DStream *zds)
  2056. {
  2057. zds->stage = zdss_loadHeader;
  2058. zds->lhSize = zds->inPos = zds->outStart = zds->outEnd = 0;
  2059. zds->legacyVersion = 0;
  2060. zds->hostageByte = 0;
  2061. return ZSTD_frameHeaderSize_prefix;
  2062. }
  2063. /* ***** Decompression ***** */
  2064. ZSTD_STATIC size_t ZSTD_limitCopy(void *dst, size_t dstCapacity, const void *src, size_t srcSize)
  2065. {
  2066. size_t const length = MIN(dstCapacity, srcSize);
  2067. memcpy(dst, src, length);
  2068. return length;
  2069. }
  2070. size_t ZSTD_decompressStream(ZSTD_DStream *zds, ZSTD_outBuffer *output, ZSTD_inBuffer *input)
  2071. {
  2072. const char *const istart = (const char *)(input->src) + input->pos;
  2073. const char *const iend = (const char *)(input->src) + input->size;
  2074. const char *ip = istart;
  2075. char *const ostart = (char *)(output->dst) + output->pos;
  2076. char *const oend = (char *)(output->dst) + output->size;
  2077. char *op = ostart;
  2078. U32 someMoreWork = 1;
  2079. while (someMoreWork) {
  2080. switch (zds->stage) {
  2081. case zdss_init:
  2082. ZSTD_resetDStream(zds); /* transparent reset on starting decoding a new frame */
  2083. /* fall-through */
  2084. case zdss_loadHeader: {
  2085. size_t const hSize = ZSTD_getFrameParams(&zds->fParams, zds->headerBuffer, zds->lhSize);
  2086. if (ZSTD_isError(hSize))
  2087. return hSize;
  2088. if (hSize != 0) { /* need more input */
  2089. size_t const toLoad = hSize - zds->lhSize; /* if hSize!=0, hSize > zds->lhSize */
  2090. if (toLoad > (size_t)(iend - ip)) { /* not enough input to load full header */
  2091. memcpy(zds->headerBuffer + zds->lhSize, ip, iend - ip);
  2092. zds->lhSize += iend - ip;
  2093. input->pos = input->size;
  2094. return (MAX(ZSTD_frameHeaderSize_min, hSize) - zds->lhSize) +
  2095. ZSTD_blockHeaderSize; /* remaining header bytes + next block header */
  2096. }
  2097. memcpy(zds->headerBuffer + zds->lhSize, ip, toLoad);
  2098. zds->lhSize = hSize;
  2099. ip += toLoad;
  2100. break;
  2101. }
  2102. /* check for single-pass mode opportunity */
  2103. if (zds->fParams.frameContentSize && zds->fParams.windowSize /* skippable frame if == 0 */
  2104. && (U64)(size_t)(oend - op) >= zds->fParams.frameContentSize) {
  2105. size_t const cSize = ZSTD_findFrameCompressedSize(istart, iend - istart);
  2106. if (cSize <= (size_t)(iend - istart)) {
  2107. size_t const decompressedSize = ZSTD_decompress_usingDDict(zds->dctx, op, oend - op, istart, cSize, zds->ddict);
  2108. if (ZSTD_isError(decompressedSize))
  2109. return decompressedSize;
  2110. ip = istart + cSize;
  2111. op += decompressedSize;
  2112. zds->dctx->expected = 0;
  2113. zds->stage = zdss_init;
  2114. someMoreWork = 0;
  2115. break;
  2116. }
  2117. }
  2118. /* Consume header */
  2119. ZSTD_refDDict(zds->dctx, zds->ddict);
  2120. {
  2121. size_t const h1Size = ZSTD_nextSrcSizeToDecompress(zds->dctx); /* == ZSTD_frameHeaderSize_prefix */
  2122. CHECK_F(ZSTD_decompressContinue(zds->dctx, NULL, 0, zds->headerBuffer, h1Size));
  2123. {
  2124. size_t const h2Size = ZSTD_nextSrcSizeToDecompress(zds->dctx);
  2125. CHECK_F(ZSTD_decompressContinue(zds->dctx, NULL, 0, zds->headerBuffer + h1Size, h2Size));
  2126. }
  2127. }
  2128. zds->fParams.windowSize = MAX(zds->fParams.windowSize, 1U << ZSTD_WINDOWLOG_ABSOLUTEMIN);
  2129. if (zds->fParams.windowSize > zds->maxWindowSize)
  2130. return ERROR(frameParameter_windowTooLarge);
  2131. /* Buffers are preallocated, but double check */
  2132. {
  2133. size_t const blockSize = MIN(zds->maxWindowSize, ZSTD_BLOCKSIZE_ABSOLUTEMAX);
  2134. size_t const neededOutSize = zds->maxWindowSize + blockSize + WILDCOPY_OVERLENGTH * 2;
  2135. if (zds->inBuffSize < blockSize) {
  2136. return ERROR(GENERIC);
  2137. }
  2138. if (zds->outBuffSize < neededOutSize) {
  2139. return ERROR(GENERIC);
  2140. }
  2141. zds->blockSize = blockSize;
  2142. }
  2143. zds->stage = zdss_read;
  2144. }
  2145. /* pass-through */
  2146. case zdss_read: {
  2147. size_t const neededInSize = ZSTD_nextSrcSizeToDecompress(zds->dctx);
  2148. if (neededInSize == 0) { /* end of frame */
  2149. zds->stage = zdss_init;
  2150. someMoreWork = 0;
  2151. break;
  2152. }
  2153. if ((size_t)(iend - ip) >= neededInSize) { /* decode directly from src */
  2154. const int isSkipFrame = ZSTD_isSkipFrame(zds->dctx);
  2155. size_t const decodedSize = ZSTD_decompressContinue(zds->dctx, zds->outBuff + zds->outStart,
  2156. (isSkipFrame ? 0 : zds->outBuffSize - zds->outStart), ip, neededInSize);
  2157. if (ZSTD_isError(decodedSize))
  2158. return decodedSize;
  2159. ip += neededInSize;
  2160. if (!decodedSize && !isSkipFrame)
  2161. break; /* this was just a header */
  2162. zds->outEnd = zds->outStart + decodedSize;
  2163. zds->stage = zdss_flush;
  2164. break;
  2165. }
  2166. if (ip == iend) {
  2167. someMoreWork = 0;
  2168. break;
  2169. } /* no more input */
  2170. zds->stage = zdss_load;
  2171. /* pass-through */
  2172. }
  2173. case zdss_load: {
  2174. size_t const neededInSize = ZSTD_nextSrcSizeToDecompress(zds->dctx);
  2175. size_t const toLoad = neededInSize - zds->inPos; /* should always be <= remaining space within inBuff */
  2176. size_t loadedSize;
  2177. if (toLoad > zds->inBuffSize - zds->inPos)
  2178. return ERROR(corruption_detected); /* should never happen */
  2179. loadedSize = ZSTD_limitCopy(zds->inBuff + zds->inPos, toLoad, ip, iend - ip);
  2180. ip += loadedSize;
  2181. zds->inPos += loadedSize;
  2182. if (loadedSize < toLoad) {
  2183. someMoreWork = 0;
  2184. break;
  2185. } /* not enough input, wait for more */
  2186. /* decode loaded input */
  2187. {
  2188. const int isSkipFrame = ZSTD_isSkipFrame(zds->dctx);
  2189. size_t const decodedSize = ZSTD_decompressContinue(zds->dctx, zds->outBuff + zds->outStart, zds->outBuffSize - zds->outStart,
  2190. zds->inBuff, neededInSize);
  2191. if (ZSTD_isError(decodedSize))
  2192. return decodedSize;
  2193. zds->inPos = 0; /* input is consumed */
  2194. if (!decodedSize && !isSkipFrame) {
  2195. zds->stage = zdss_read;
  2196. break;
  2197. } /* this was just a header */
  2198. zds->outEnd = zds->outStart + decodedSize;
  2199. zds->stage = zdss_flush;
  2200. /* pass-through */
  2201. }
  2202. }
  2203. case zdss_flush: {
  2204. size_t const toFlushSize = zds->outEnd - zds->outStart;
  2205. size_t const flushedSize = ZSTD_limitCopy(op, oend - op, zds->outBuff + zds->outStart, toFlushSize);
  2206. op += flushedSize;
  2207. zds->outStart += flushedSize;
  2208. if (flushedSize == toFlushSize) { /* flush completed */
  2209. zds->stage = zdss_read;
  2210. if (zds->outStart + zds->blockSize > zds->outBuffSize)
  2211. zds->outStart = zds->outEnd = 0;
  2212. break;
  2213. }
  2214. /* cannot complete flush */
  2215. someMoreWork = 0;
  2216. break;
  2217. }
  2218. default:
  2219. return ERROR(GENERIC); /* impossible */
  2220. }
  2221. }
  2222. /* result */
  2223. input->pos += (size_t)(ip - istart);
  2224. output->pos += (size_t)(op - ostart);
  2225. {
  2226. size_t nextSrcSizeHint = ZSTD_nextSrcSizeToDecompress(zds->dctx);
  2227. if (!nextSrcSizeHint) { /* frame fully decoded */
  2228. if (zds->outEnd == zds->outStart) { /* output fully flushed */
  2229. if (zds->hostageByte) {
  2230. if (input->pos >= input->size) {
  2231. zds->stage = zdss_read;
  2232. return 1;
  2233. } /* can't release hostage (not present) */
  2234. input->pos++; /* release hostage */
  2235. }
  2236. return 0;
  2237. }
  2238. if (!zds->hostageByte) { /* output not fully flushed; keep last byte as hostage; will be released when all output is flushed */
  2239. input->pos--; /* note : pos > 0, otherwise, impossible to finish reading last block */
  2240. zds->hostageByte = 1;
  2241. }
  2242. return 1;
  2243. }
  2244. nextSrcSizeHint += ZSTD_blockHeaderSize * (ZSTD_nextInputType(zds->dctx) == ZSTDnit_block); /* preload header of next block */
  2245. if (zds->inPos > nextSrcSizeHint)
  2246. return ERROR(GENERIC); /* should never happen */
  2247. nextSrcSizeHint -= zds->inPos; /* already loaded*/
  2248. return nextSrcSizeHint;
  2249. }
  2250. }
  2251. EXPORT_SYMBOL(ZSTD_DCtxWorkspaceBound);
  2252. EXPORT_SYMBOL(ZSTD_initDCtx);
  2253. EXPORT_SYMBOL(ZSTD_decompressDCtx);
  2254. EXPORT_SYMBOL(ZSTD_decompress_usingDict);
  2255. EXPORT_SYMBOL(ZSTD_DDictWorkspaceBound);
  2256. EXPORT_SYMBOL(ZSTD_initDDict);
  2257. EXPORT_SYMBOL(ZSTD_decompress_usingDDict);
  2258. EXPORT_SYMBOL(ZSTD_DStreamWorkspaceBound);
  2259. EXPORT_SYMBOL(ZSTD_initDStream);
  2260. EXPORT_SYMBOL(ZSTD_initDStream_usingDDict);
  2261. EXPORT_SYMBOL(ZSTD_resetDStream);
  2262. EXPORT_SYMBOL(ZSTD_decompressStream);
  2263. EXPORT_SYMBOL(ZSTD_DStreamInSize);
  2264. EXPORT_SYMBOL(ZSTD_DStreamOutSize);
  2265. EXPORT_SYMBOL(ZSTD_findFrameCompressedSize);
  2266. EXPORT_SYMBOL(ZSTD_getFrameContentSize);
  2267. EXPORT_SYMBOL(ZSTD_findDecompressedSize);
  2268. EXPORT_SYMBOL(ZSTD_isFrame);
  2269. EXPORT_SYMBOL(ZSTD_getDictID_fromDict);
  2270. EXPORT_SYMBOL(ZSTD_getDictID_fromDDict);
  2271. EXPORT_SYMBOL(ZSTD_getDictID_fromFrame);
  2272. EXPORT_SYMBOL(ZSTD_getFrameParams);
  2273. EXPORT_SYMBOL(ZSTD_decompressBegin);
  2274. EXPORT_SYMBOL(ZSTD_decompressBegin_usingDict);
  2275. EXPORT_SYMBOL(ZSTD_copyDCtx);
  2276. EXPORT_SYMBOL(ZSTD_nextSrcSizeToDecompress);
  2277. EXPORT_SYMBOL(ZSTD_decompressContinue);
  2278. EXPORT_SYMBOL(ZSTD_nextInputType);
  2279. EXPORT_SYMBOL(ZSTD_decompressBlock);
  2280. EXPORT_SYMBOL(ZSTD_insertBlock);