decompress.c 80 KB

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