lz4.c 8.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242
  1. // SPDX-License-Identifier: BSD-2-Clause
  2. /*
  3. LZ4 - Fast LZ compression algorithm
  4. Copyright (C) 2011-2015, Yann Collet.
  5. You can contact the author at :
  6. - LZ4 source repository : https://github.com/Cyan4973/lz4
  7. - LZ4 public forum : https://groups.google.com/forum/#!forum/lz4c
  8. */
  9. /**************************************
  10. * Reading and writing into memory
  11. **************************************/
  12. /* customized version of memcpy, which may overwrite up to 7 bytes beyond dstEnd */
  13. static void LZ4_wildCopy(void* dstPtr, const void* srcPtr, void* dstEnd)
  14. {
  15. BYTE* d = (BYTE*)dstPtr;
  16. const BYTE* s = (const BYTE*)srcPtr;
  17. BYTE* e = (BYTE*)dstEnd;
  18. do { LZ4_copy8(d,s); d+=8; s+=8; } while (d<e);
  19. }
  20. /**************************************
  21. * Common Constants
  22. **************************************/
  23. #define MINMATCH 4
  24. #define COPYLENGTH 8
  25. #define LASTLITERALS 5
  26. #define MFLIMIT (COPYLENGTH+MINMATCH)
  27. static const int LZ4_minLength = (MFLIMIT+1);
  28. #define KB *(1 <<10)
  29. #define MB *(1 <<20)
  30. #define GB *(1U<<30)
  31. #define MAXD_LOG 16
  32. #define MAX_DISTANCE ((1 << MAXD_LOG) - 1)
  33. #define ML_BITS 4
  34. #define ML_MASK ((1U<<ML_BITS)-1)
  35. #define RUN_BITS (8-ML_BITS)
  36. #define RUN_MASK ((1U<<RUN_BITS)-1)
  37. /**************************************
  38. * Local Structures and types
  39. **************************************/
  40. typedef enum { noDict = 0, withPrefix64k, usingExtDict } dict_directive;
  41. typedef enum { endOnOutputSize = 0, endOnInputSize = 1 } endCondition_directive;
  42. typedef enum { full = 0, partial = 1 } earlyEnd_directive;
  43. /*******************************
  44. * Decompression functions
  45. *******************************/
  46. /*
  47. * This generic decompression function cover all use cases.
  48. * It shall be instantiated several times, using different sets of directives
  49. * Note that it is essential this generic function is really inlined,
  50. * in order to remove useless branches during compilation optimization.
  51. */
  52. FORCE_INLINE int LZ4_decompress_generic(
  53. const char* const source,
  54. char* const dest,
  55. int inputSize,
  56. int outputSize, /* If endOnInput==endOnInputSize, this value is the max size of Output Buffer. */
  57. int endOnInput, /* endOnOutputSize, endOnInputSize */
  58. int partialDecoding, /* full, partial */
  59. int targetOutputSize, /* only used if partialDecoding==partial */
  60. int dict, /* noDict, withPrefix64k, usingExtDict */
  61. const BYTE* const lowPrefix, /* == dest if dict == noDict */
  62. const BYTE* const dictStart, /* only if dict==usingExtDict */
  63. const size_t dictSize /* note : = 0 if noDict */
  64. )
  65. {
  66. /* Local Variables */
  67. const BYTE* ip = (const BYTE*) source;
  68. const BYTE* const iend = ip + inputSize;
  69. BYTE* op = (BYTE*) dest;
  70. BYTE* const oend = op + outputSize;
  71. BYTE* cpy;
  72. BYTE* oexit = op + targetOutputSize;
  73. const BYTE* const lowLimit = lowPrefix - dictSize;
  74. const BYTE* const dictEnd = (const BYTE*)dictStart + dictSize;
  75. const size_t dec32table[] = {4, 1, 2, 1, 4, 4, 4, 4};
  76. const size_t dec64table[] = {0, 0, 0, (size_t)-1, 0, 1, 2, 3};
  77. const int safeDecode = (endOnInput==endOnInputSize);
  78. const int checkOffset = ((safeDecode) && (dictSize < (int)(64 KB)));
  79. /* Special cases */
  80. if ((partialDecoding) && (oexit> oend-MFLIMIT)) oexit = oend-MFLIMIT; /* targetOutputSize too high => decode everything */
  81. if ((endOnInput) && (unlikely(outputSize==0))) return ((inputSize==1) && (*ip==0)) ? 0 : -1; /* Empty output buffer */
  82. if ((!endOnInput) && (unlikely(outputSize==0))) return (*ip==0?1:-1);
  83. /* Main Loop */
  84. while (1)
  85. {
  86. unsigned token;
  87. size_t length;
  88. const BYTE* match;
  89. /* get literal length */
  90. token = *ip++;
  91. if ((length=(token>>ML_BITS)) == RUN_MASK)
  92. {
  93. unsigned s;
  94. do
  95. {
  96. s = *ip++;
  97. length += s;
  98. }
  99. while (likely((endOnInput)?ip<iend-RUN_MASK:1) && (s==255));
  100. if ((safeDecode) && unlikely((size_t)(op+length)<(size_t)(op))) goto _output_error; /* overflow detection */
  101. if ((safeDecode) && unlikely((size_t)(ip+length)<(size_t)(ip))) goto _output_error; /* overflow detection */
  102. }
  103. /* copy literals */
  104. cpy = op+length;
  105. if (((endOnInput) && ((cpy>(partialDecoding?oexit:oend-MFLIMIT)) || (ip+length>iend-(2+1+LASTLITERALS))) )
  106. || ((!endOnInput) && (cpy>oend-COPYLENGTH)))
  107. {
  108. if (partialDecoding)
  109. {
  110. if (cpy > oend) goto _output_error; /* Error : write attempt beyond end of output buffer */
  111. if ((endOnInput) && (ip+length > iend)) goto _output_error; /* Error : read attempt beyond end of input buffer */
  112. }
  113. else
  114. {
  115. if ((!endOnInput) && (cpy != oend)) goto _output_error; /* Error : block decoding must stop exactly there */
  116. if ((endOnInput) && ((ip+length != iend) || (cpy > oend))) goto _output_error; /* Error : input must be consumed */
  117. }
  118. memcpy(op, ip, length);
  119. ip += length;
  120. op += length;
  121. break; /* Necessarily EOF, due to parsing restrictions */
  122. }
  123. LZ4_wildCopy(op, ip, cpy);
  124. ip += length; op = cpy;
  125. /* get offset */
  126. match = cpy - LZ4_readLE16(ip); ip+=2;
  127. if ((checkOffset) && (unlikely(match < lowLimit))) goto _output_error; /* Error : offset outside destination buffer */
  128. /* get matchlength */
  129. length = token & ML_MASK;
  130. if (length == ML_MASK)
  131. {
  132. unsigned s;
  133. do
  134. {
  135. if ((endOnInput) && (ip > iend-LASTLITERALS)) goto _output_error;
  136. s = *ip++;
  137. length += s;
  138. } while (s==255);
  139. if ((safeDecode) && unlikely((size_t)(op+length)<(size_t)op)) goto _output_error; /* overflow detection */
  140. }
  141. length += MINMATCH;
  142. /* check external dictionary */
  143. if ((dict==usingExtDict) && (match < lowPrefix))
  144. {
  145. if (unlikely(op+length > oend-LASTLITERALS)) goto _output_error; /* doesn't respect parsing restriction */
  146. if (length <= (size_t)(lowPrefix-match))
  147. {
  148. /* match can be copied as a single segment from external dictionary */
  149. match = dictEnd - (lowPrefix-match);
  150. memmove(op, match, length); op += length;
  151. }
  152. else
  153. {
  154. /* match encompass external dictionary and current segment */
  155. size_t copySize = (size_t)(lowPrefix-match);
  156. memcpy(op, dictEnd - copySize, copySize);
  157. op += copySize;
  158. copySize = length - copySize;
  159. if (copySize > (size_t)(op-lowPrefix)) /* overlap within current segment */
  160. {
  161. BYTE* const endOfMatch = op + copySize;
  162. const BYTE* copyFrom = lowPrefix;
  163. while (op < endOfMatch) *op++ = *copyFrom++;
  164. }
  165. else
  166. {
  167. memcpy(op, lowPrefix, copySize);
  168. op += copySize;
  169. }
  170. }
  171. continue;
  172. }
  173. /* copy repeated sequence */
  174. cpy = op + length;
  175. if (unlikely((op-match)<8))
  176. {
  177. const size_t dec64 = dec64table[op-match];
  178. op[0] = match[0];
  179. op[1] = match[1];
  180. op[2] = match[2];
  181. op[3] = match[3];
  182. match += dec32table[op-match];
  183. LZ4_copy4(op+4, match);
  184. op += 8; match -= dec64;
  185. } else { LZ4_copy8(op, match); op+=8; match+=8; }
  186. if (unlikely(cpy>oend-12))
  187. {
  188. if (cpy > oend-LASTLITERALS) goto _output_error; /* Error : last LASTLITERALS bytes must be literals */
  189. if (op < oend-8)
  190. {
  191. LZ4_wildCopy(op, match, oend-8);
  192. match += (oend-8) - op;
  193. op = oend-8;
  194. }
  195. while (op<cpy) *op++ = *match++;
  196. }
  197. else
  198. LZ4_wildCopy(op, match, cpy);
  199. op=cpy; /* correction */
  200. }
  201. /* end of decoding */
  202. if (endOnInput)
  203. return (int) (((char*)op)-dest); /* Nb of output bytes decoded */
  204. else
  205. return (int) (((const char*)ip)-source); /* Nb of input bytes read */
  206. /* Overflow error detected */
  207. _output_error:
  208. return (int) (-(((const char*)ip)-source))-1;
  209. }