lzo1x_decompress.c 7.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359
  1. /*
  2. * LZO1X Decompressor from MiniLZO
  3. *
  4. * Copyright (C) 1996-2005 Markus F.X.J. Oberhumer <markus@oberhumer.com>
  5. *
  6. * The full LZO package can be found at:
  7. * http://www.oberhumer.com/opensource/lzo/
  8. *
  9. * Changed for kernel use by:
  10. * Nitin Gupta <nitingupta910@gmail.com>
  11. * Richard Purdie <rpurdie@openedhand.com>
  12. */
  13. #include <common.h>
  14. #include <linux/lzo.h>
  15. #include <asm/byteorder.h>
  16. #include <asm/unaligned.h>
  17. #include "lzodefs.h"
  18. #define HAVE_IP(x, ip_end, ip) ((size_t)(ip_end - ip) < (x))
  19. #define HAVE_OP(x, op_end, op) ((size_t)(op_end - op) < (x))
  20. #define HAVE_LB(m_pos, out, op) (m_pos < out || m_pos >= op)
  21. #define COPY4(dst, src) \
  22. put_unaligned(get_unaligned((const u32 *)(src)), (u32 *)(dst))
  23. static const unsigned char lzop_magic[] = {
  24. 0x89, 0x4c, 0x5a, 0x4f, 0x00, 0x0d, 0x0a, 0x1a, 0x0a
  25. };
  26. #define HEADER_HAS_FILTER 0x00000800L
  27. bool lzop_is_valid_header(const unsigned char *src)
  28. {
  29. int i;
  30. /* read magic: 9 first bytes */
  31. for (i = 0; i < ARRAY_SIZE(lzop_magic); i++) {
  32. if (*src++ != lzop_magic[i])
  33. return false;
  34. }
  35. return true;
  36. }
  37. static inline const unsigned char *parse_header(const unsigned char *src)
  38. {
  39. u16 version;
  40. int i;
  41. if (!lzop_is_valid_header(src))
  42. return NULL;
  43. /* skip header */
  44. src += 9;
  45. /* get version (2bytes), skip library version (2),
  46. * 'need to be extracted' version (2) and
  47. * method (1) */
  48. version = get_unaligned_be16(src);
  49. src += 7;
  50. if (version >= 0x0940)
  51. src++;
  52. if (get_unaligned_be32(src) & HEADER_HAS_FILTER)
  53. src += 4; /* filter info */
  54. /* skip flags, mode and mtime_low */
  55. src += 12;
  56. if (version >= 0x0940)
  57. src += 4; /* skip mtime_high */
  58. i = *src++;
  59. /* don't care about the file name, and skip checksum */
  60. src += i + 4;
  61. return src;
  62. }
  63. int lzop_decompress(const unsigned char *src, size_t src_len,
  64. unsigned char *dst, size_t *dst_len)
  65. {
  66. unsigned char *start = dst;
  67. const unsigned char *send = src + src_len;
  68. u32 slen, dlen;
  69. size_t tmp, remaining;
  70. int r;
  71. src = parse_header(src);
  72. if (!src)
  73. return LZO_E_ERROR;
  74. remaining = *dst_len;
  75. while (src < send) {
  76. /* read uncompressed block size */
  77. dlen = get_unaligned_be32(src);
  78. src += 4;
  79. /* exit if last block */
  80. if (dlen == 0) {
  81. *dst_len = dst - start;
  82. return LZO_E_OK;
  83. }
  84. /* read compressed block size, and skip block checksum info */
  85. slen = get_unaligned_be32(src);
  86. src += 8;
  87. if (slen <= 0 || slen > dlen)
  88. return LZO_E_ERROR;
  89. /* abort if buffer ran out of room */
  90. if (dlen > remaining)
  91. return LZO_E_OUTPUT_OVERRUN;
  92. /* When the input data is not compressed at all,
  93. * lzo1x_decompress_safe will fail, so call memcpy()
  94. * instead */
  95. if (dlen == slen) {
  96. memcpy(dst, src, slen);
  97. } else {
  98. /* decompress */
  99. tmp = dlen;
  100. r = lzo1x_decompress_safe((u8 *)src, slen, dst, &tmp);
  101. if (r != LZO_E_OK) {
  102. *dst_len = dst - start;
  103. return r;
  104. }
  105. if (dlen != tmp)
  106. return LZO_E_ERROR;
  107. }
  108. src += slen;
  109. dst += dlen;
  110. remaining -= dlen;
  111. }
  112. return LZO_E_INPUT_OVERRUN;
  113. }
  114. int lzo1x_decompress_safe(const unsigned char *in, size_t in_len,
  115. unsigned char *out, size_t *out_len)
  116. {
  117. const unsigned char * const ip_end = in + in_len;
  118. unsigned char * const op_end = out + *out_len;
  119. const unsigned char *ip = in, *m_pos;
  120. unsigned char *op = out;
  121. size_t t;
  122. *out_len = 0;
  123. if (*ip > 17) {
  124. t = *ip++ - 17;
  125. if (t < 4)
  126. goto match_next;
  127. if (HAVE_OP(t, op_end, op))
  128. goto output_overrun;
  129. if (HAVE_IP(t + 1, ip_end, ip))
  130. goto input_overrun;
  131. do {
  132. *op++ = *ip++;
  133. } while (--t > 0);
  134. goto first_literal_run;
  135. }
  136. while ((ip < ip_end)) {
  137. t = *ip++;
  138. if (t >= 16)
  139. goto match;
  140. if (t == 0) {
  141. if (HAVE_IP(1, ip_end, ip))
  142. goto input_overrun;
  143. while (*ip == 0) {
  144. t += 255;
  145. ip++;
  146. if (HAVE_IP(1, ip_end, ip))
  147. goto input_overrun;
  148. }
  149. t += 15 + *ip++;
  150. }
  151. if (HAVE_OP(t + 3, op_end, op))
  152. goto output_overrun;
  153. if (HAVE_IP(t + 4, ip_end, ip))
  154. goto input_overrun;
  155. COPY4(op, ip);
  156. op += 4;
  157. ip += 4;
  158. if (--t > 0) {
  159. if (t >= 4) {
  160. do {
  161. COPY4(op, ip);
  162. op += 4;
  163. ip += 4;
  164. t -= 4;
  165. } while (t >= 4);
  166. if (t > 0) {
  167. do {
  168. *op++ = *ip++;
  169. } while (--t > 0);
  170. }
  171. } else {
  172. do {
  173. *op++ = *ip++;
  174. } while (--t > 0);
  175. }
  176. }
  177. first_literal_run:
  178. t = *ip++;
  179. if (t >= 16)
  180. goto match;
  181. m_pos = op - (1 + M2_MAX_OFFSET);
  182. m_pos -= t >> 2;
  183. m_pos -= *ip++ << 2;
  184. if (HAVE_LB(m_pos, out, op))
  185. goto lookbehind_overrun;
  186. if (HAVE_OP(3, op_end, op))
  187. goto output_overrun;
  188. *op++ = *m_pos++;
  189. *op++ = *m_pos++;
  190. *op++ = *m_pos;
  191. goto match_done;
  192. do {
  193. match:
  194. if (t >= 64) {
  195. m_pos = op - 1;
  196. m_pos -= (t >> 2) & 7;
  197. m_pos -= *ip++ << 3;
  198. t = (t >> 5) - 1;
  199. if (HAVE_LB(m_pos, out, op))
  200. goto lookbehind_overrun;
  201. if (HAVE_OP(t + 3 - 1, op_end, op))
  202. goto output_overrun;
  203. goto copy_match;
  204. } else if (t >= 32) {
  205. t &= 31;
  206. if (t == 0) {
  207. if (HAVE_IP(1, ip_end, ip))
  208. goto input_overrun;
  209. while (*ip == 0) {
  210. t += 255;
  211. ip++;
  212. if (HAVE_IP(1, ip_end, ip))
  213. goto input_overrun;
  214. }
  215. t += 31 + *ip++;
  216. }
  217. m_pos = op - 1;
  218. m_pos -= get_unaligned_le16(ip) >> 2;
  219. ip += 2;
  220. } else if (t >= 16) {
  221. m_pos = op;
  222. m_pos -= (t & 8) << 11;
  223. t &= 7;
  224. if (t == 0) {
  225. if (HAVE_IP(1, ip_end, ip))
  226. goto input_overrun;
  227. while (*ip == 0) {
  228. t += 255;
  229. ip++;
  230. if (HAVE_IP(1, ip_end, ip))
  231. goto input_overrun;
  232. }
  233. t += 7 + *ip++;
  234. }
  235. m_pos -= get_unaligned_le16(ip) >> 2;
  236. ip += 2;
  237. if (m_pos == op)
  238. goto eof_found;
  239. m_pos -= 0x4000;
  240. } else {
  241. m_pos = op - 1;
  242. m_pos -= t >> 2;
  243. m_pos -= *ip++ << 2;
  244. if (HAVE_LB(m_pos, out, op))
  245. goto lookbehind_overrun;
  246. if (HAVE_OP(2, op_end, op))
  247. goto output_overrun;
  248. *op++ = *m_pos++;
  249. *op++ = *m_pos;
  250. goto match_done;
  251. }
  252. if (HAVE_LB(m_pos, out, op))
  253. goto lookbehind_overrun;
  254. if (HAVE_OP(t + 3 - 1, op_end, op))
  255. goto output_overrun;
  256. if (t >= 2 * 4 - (3 - 1) && (op - m_pos) >= 4) {
  257. COPY4(op, m_pos);
  258. op += 4;
  259. m_pos += 4;
  260. t -= 4 - (3 - 1);
  261. do {
  262. COPY4(op, m_pos);
  263. op += 4;
  264. m_pos += 4;
  265. t -= 4;
  266. } while (t >= 4);
  267. if (t > 0)
  268. do {
  269. *op++ = *m_pos++;
  270. } while (--t > 0);
  271. } else {
  272. copy_match:
  273. *op++ = *m_pos++;
  274. *op++ = *m_pos++;
  275. do {
  276. *op++ = *m_pos++;
  277. } while (--t > 0);
  278. }
  279. match_done:
  280. t = ip[-2] & 3;
  281. if (t == 0)
  282. break;
  283. match_next:
  284. if (HAVE_OP(t, op_end, op))
  285. goto output_overrun;
  286. if (HAVE_IP(t + 1, ip_end, ip))
  287. goto input_overrun;
  288. *op++ = *ip++;
  289. if (t > 1) {
  290. *op++ = *ip++;
  291. if (t > 2)
  292. *op++ = *ip++;
  293. }
  294. t = *ip++;
  295. } while (ip < ip_end);
  296. }
  297. *out_len = op - out;
  298. return LZO_E_EOF_NOT_FOUND;
  299. eof_found:
  300. *out_len = op - out;
  301. return (ip == ip_end ? LZO_E_OK :
  302. (ip < ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));
  303. input_overrun:
  304. *out_len = op - out;
  305. return LZO_E_INPUT_OVERRUN;
  306. output_overrun:
  307. *out_len = op - out;
  308. return LZO_E_OUTPUT_OVERRUN;
  309. lookbehind_overrun:
  310. *out_len = op - out;
  311. return LZO_E_LOOKBEHIND_OVERRUN;
  312. }