lzo1x_decompress_safe.c 6.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296
  1. // SPDX-License-Identifier: GPL-2.0-only
  2. /*
  3. * LZO1X Decompressor from LZO
  4. *
  5. * Copyright (C) 1996-2012 Markus F.X.J. Oberhumer <markus@oberhumer.com>
  6. *
  7. * The full LZO package can be found at:
  8. * http://www.oberhumer.com/opensource/lzo/
  9. *
  10. * Changed for Linux kernel use by:
  11. * Nitin Gupta <nitingupta910@gmail.com>
  12. * Richard Purdie <rpurdie@openedhand.com>
  13. */
  14. #ifndef STATIC
  15. #include <linux/module.h>
  16. #include <linux/kernel.h>
  17. #endif
  18. #include <asm/unaligned.h>
  19. #include <linux/lzo.h>
  20. #include "lzodefs.h"
  21. #define HAVE_IP(x) ((size_t)(ip_end - ip) >= (size_t)(x))
  22. #define HAVE_OP(x) ((size_t)(op_end - op) >= (size_t)(x))
  23. #define NEED_IP(x) if (!HAVE_IP(x)) goto input_overrun
  24. #define NEED_OP(x) if (!HAVE_OP(x)) goto output_overrun
  25. #define TEST_LB(m_pos) if ((m_pos) < out) goto lookbehind_overrun
  26. /* This MAX_255_COUNT is the maximum number of times we can add 255 to a base
  27. * count without overflowing an integer. The multiply will overflow when
  28. * multiplying 255 by more than MAXINT/255. The sum will overflow earlier
  29. * depending on the base count. Since the base count is taken from a u8
  30. * and a few bits, it is safe to assume that it will always be lower than
  31. * or equal to 2*255, thus we can always prevent any overflow by accepting
  32. * two less 255 steps. See Documentation/staging/lzo.rst for more information.
  33. */
  34. #define MAX_255_COUNT ((((size_t)~0) / 255) - 2)
  35. int lzo1x_decompress_safe(const unsigned char *in, size_t in_len,
  36. unsigned char *out, size_t *out_len)
  37. {
  38. unsigned char *op;
  39. const unsigned char *ip;
  40. size_t t, next;
  41. size_t state = 0;
  42. const unsigned char *m_pos;
  43. const unsigned char * const ip_end = in + in_len;
  44. unsigned char * const op_end = out + *out_len;
  45. unsigned char bitstream_version;
  46. op = out;
  47. ip = in;
  48. if (unlikely(in_len < 3))
  49. goto input_overrun;
  50. if (likely(in_len >= 5) && likely(*ip == 17)) {
  51. bitstream_version = ip[1];
  52. ip += 2;
  53. } else {
  54. bitstream_version = 0;
  55. }
  56. if (*ip > 17) {
  57. t = *ip++ - 17;
  58. if (t < 4) {
  59. next = t;
  60. goto match_next;
  61. }
  62. goto copy_literal_run;
  63. }
  64. for (;;) {
  65. t = *ip++;
  66. if (t < 16) {
  67. if (likely(state == 0)) {
  68. if (unlikely(t == 0)) {
  69. size_t offset;
  70. const unsigned char *ip_last = ip;
  71. while (unlikely(*ip == 0)) {
  72. ip++;
  73. NEED_IP(1);
  74. }
  75. offset = ip - ip_last;
  76. if (unlikely(offset > MAX_255_COUNT))
  77. return LZO_E_ERROR;
  78. offset = (offset << 8) - offset;
  79. t += offset + 15 + *ip++;
  80. }
  81. t += 3;
  82. copy_literal_run:
  83. #if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS)
  84. if (likely(HAVE_IP(t + 15) && HAVE_OP(t + 15))) {
  85. const unsigned char *ie = ip + t;
  86. unsigned char *oe = op + t;
  87. do {
  88. COPY8(op, ip);
  89. op += 8;
  90. ip += 8;
  91. COPY8(op, ip);
  92. op += 8;
  93. ip += 8;
  94. } while (ip < ie);
  95. ip = ie;
  96. op = oe;
  97. } else
  98. #endif
  99. {
  100. NEED_OP(t);
  101. NEED_IP(t + 3);
  102. do {
  103. *op++ = *ip++;
  104. } while (--t > 0);
  105. }
  106. state = 4;
  107. continue;
  108. } else if (state != 4) {
  109. next = t & 3;
  110. m_pos = op - 1;
  111. m_pos -= t >> 2;
  112. m_pos -= *ip++ << 2;
  113. TEST_LB(m_pos);
  114. NEED_OP(2);
  115. op[0] = m_pos[0];
  116. op[1] = m_pos[1];
  117. op += 2;
  118. goto match_next;
  119. } else {
  120. next = t & 3;
  121. m_pos = op - (1 + M2_MAX_OFFSET);
  122. m_pos -= t >> 2;
  123. m_pos -= *ip++ << 2;
  124. t = 3;
  125. }
  126. } else if (t >= 64) {
  127. next = t & 3;
  128. m_pos = op - 1;
  129. m_pos -= (t >> 2) & 7;
  130. m_pos -= *ip++ << 3;
  131. t = (t >> 5) - 1 + (3 - 1);
  132. } else if (t >= 32) {
  133. t = (t & 31) + (3 - 1);
  134. if (unlikely(t == 2)) {
  135. size_t offset;
  136. const unsigned char *ip_last = ip;
  137. while (unlikely(*ip == 0)) {
  138. ip++;
  139. NEED_IP(1);
  140. }
  141. offset = ip - ip_last;
  142. if (unlikely(offset > MAX_255_COUNT))
  143. return LZO_E_ERROR;
  144. offset = (offset << 8) - offset;
  145. t += offset + 31 + *ip++;
  146. NEED_IP(2);
  147. }
  148. m_pos = op - 1;
  149. next = get_unaligned_le16(ip);
  150. ip += 2;
  151. m_pos -= next >> 2;
  152. next &= 3;
  153. } else {
  154. NEED_IP(2);
  155. next = get_unaligned_le16(ip);
  156. if (((next & 0xfffc) == 0xfffc) &&
  157. ((t & 0xf8) == 0x18) &&
  158. likely(bitstream_version)) {
  159. NEED_IP(3);
  160. t &= 7;
  161. t |= ip[2] << 3;
  162. t += MIN_ZERO_RUN_LENGTH;
  163. NEED_OP(t);
  164. memset(op, 0, t);
  165. op += t;
  166. next &= 3;
  167. ip += 3;
  168. goto match_next;
  169. } else {
  170. m_pos = op;
  171. m_pos -= (t & 8) << 11;
  172. t = (t & 7) + (3 - 1);
  173. if (unlikely(t == 2)) {
  174. size_t offset;
  175. const unsigned char *ip_last = ip;
  176. while (unlikely(*ip == 0)) {
  177. ip++;
  178. NEED_IP(1);
  179. }
  180. offset = ip - ip_last;
  181. if (unlikely(offset > MAX_255_COUNT))
  182. return LZO_E_ERROR;
  183. offset = (offset << 8) - offset;
  184. t += offset + 7 + *ip++;
  185. NEED_IP(2);
  186. next = get_unaligned_le16(ip);
  187. }
  188. ip += 2;
  189. m_pos -= next >> 2;
  190. next &= 3;
  191. if (m_pos == op)
  192. goto eof_found;
  193. m_pos -= 0x4000;
  194. }
  195. }
  196. TEST_LB(m_pos);
  197. #if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS)
  198. if (op - m_pos >= 8) {
  199. unsigned char *oe = op + t;
  200. if (likely(HAVE_OP(t + 15))) {
  201. do {
  202. COPY8(op, m_pos);
  203. op += 8;
  204. m_pos += 8;
  205. COPY8(op, m_pos);
  206. op += 8;
  207. m_pos += 8;
  208. } while (op < oe);
  209. op = oe;
  210. if (HAVE_IP(6)) {
  211. state = next;
  212. COPY4(op, ip);
  213. op += next;
  214. ip += next;
  215. continue;
  216. }
  217. } else {
  218. NEED_OP(t);
  219. do {
  220. *op++ = *m_pos++;
  221. } while (op < oe);
  222. }
  223. } else
  224. #endif
  225. {
  226. unsigned char *oe = op + t;
  227. NEED_OP(t);
  228. op[0] = m_pos[0];
  229. op[1] = m_pos[1];
  230. op += 2;
  231. m_pos += 2;
  232. do {
  233. *op++ = *m_pos++;
  234. } while (op < oe);
  235. }
  236. match_next:
  237. state = next;
  238. t = next;
  239. #if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS)
  240. if (likely(HAVE_IP(6) && HAVE_OP(4))) {
  241. COPY4(op, ip);
  242. op += t;
  243. ip += t;
  244. } else
  245. #endif
  246. {
  247. NEED_IP(t + 3);
  248. NEED_OP(t);
  249. while (t > 0) {
  250. *op++ = *ip++;
  251. t--;
  252. }
  253. }
  254. }
  255. eof_found:
  256. *out_len = op - out;
  257. return (t != 3 ? LZO_E_ERROR :
  258. ip == ip_end ? LZO_E_OK :
  259. ip < ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN);
  260. input_overrun:
  261. *out_len = op - out;
  262. return LZO_E_INPUT_OVERRUN;
  263. output_overrun:
  264. *out_len = op - out;
  265. return LZO_E_OUTPUT_OVERRUN;
  266. lookbehind_overrun:
  267. *out_len = op - out;
  268. return LZO_E_LOOKBEHIND_OVERRUN;
  269. }
  270. #ifndef STATIC
  271. EXPORT_SYMBOL_GPL(lzo1x_decompress_safe);
  272. MODULE_LICENSE("GPL");
  273. MODULE_DESCRIPTION("LZO1X Decompressor");
  274. #endif