lzo1x_d.c 9.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422
  1. /* implementation of the LZO1X decompression algorithm
  2. This file is part of the LZO real-time data compression library.
  3. Copyright (C) 1996..2008 Markus Franz Xaver Johannes Oberhumer
  4. All Rights Reserved.
  5. Markus F.X.J. Oberhumer <markus@oberhumer.com>
  6. http://www.oberhumer.com/opensource/lzo/
  7. The LZO library is free software; you can redistribute it and/or
  8. modify it under the terms of the GNU General Public License as
  9. published by the Free Software Foundation; either version 2 of
  10. the License, or (at your option) any later version.
  11. The LZO library is distributed in the hope that it will be useful,
  12. but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  14. GNU General Public License for more details.
  15. You should have received a copy of the GNU General Public License
  16. along with the LZO library; see the file COPYING.
  17. If not, write to the Free Software Foundation, Inc.,
  18. 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  19. */
  20. #include "libbb.h"
  21. #include "liblzo.h"
  22. /***********************************************************************
  23. // decompress a block of data.
  24. ************************************************************************/
  25. /* safe decompression with overrun testing */
  26. int lzo1x_decompress_safe(const uint8_t* in, unsigned in_len,
  27. uint8_t* out, unsigned* out_len /*, void* wrkmem */)
  28. {
  29. register uint8_t* op;
  30. register const uint8_t* ip;
  31. register unsigned t;
  32. #if defined(COPY_DICT)
  33. unsigned m_off;
  34. const uint8_t* dict_end;
  35. #else
  36. register const uint8_t* m_pos = NULL; /* possibly not needed */
  37. #endif
  38. const uint8_t* const ip_end = in + in_len;
  39. #if defined(HAVE_ANY_OP)
  40. uint8_t* const op_end = out + *out_len;
  41. #endif
  42. #if defined(LZO1Z)
  43. unsigned last_m_off = 0;
  44. #endif
  45. // LZO_UNUSED(wrkmem);
  46. #if defined(COPY_DICT)
  47. if (dict) {
  48. if (dict_len > M4_MAX_OFFSET) {
  49. dict += dict_len - M4_MAX_OFFSET;
  50. dict_len = M4_MAX_OFFSET;
  51. }
  52. dict_end = dict + dict_len;
  53. } else {
  54. dict_len = 0;
  55. dict_end = NULL;
  56. }
  57. #endif /* COPY_DICT */
  58. *out_len = 0;
  59. op = out;
  60. ip = in;
  61. if (*ip > 17) {
  62. t = *ip++ - 17;
  63. if (t < 4)
  64. goto match_next;
  65. assert(t > 0); NEED_OP(t); NEED_IP(t+1);
  66. do *op++ = *ip++; while (--t > 0);
  67. goto first_literal_run;
  68. }
  69. while (TEST_IP && TEST_OP) {
  70. t = *ip++;
  71. if (t >= 16)
  72. goto match;
  73. /* a literal run */
  74. if (t == 0) {
  75. NEED_IP(1);
  76. while (*ip == 0) {
  77. t += 255;
  78. ip++;
  79. NEED_IP(1);
  80. }
  81. TEST_IV(t);
  82. t += 15 + *ip++;
  83. }
  84. /* copy literals */
  85. assert(t > 0);
  86. NEED_OP(t+3);
  87. NEED_IP(t+4);
  88. #if defined(LZO_UNALIGNED_OK_4) || defined(LZO_ALIGNED_OK_4)
  89. # if !defined(LZO_UNALIGNED_OK_4)
  90. if (PTR_ALIGNED2_4(op, ip))
  91. # endif
  92. {
  93. COPY4(op, ip);
  94. op += 4;
  95. ip += 4;
  96. if (--t > 0) {
  97. if (t >= 4) {
  98. do {
  99. COPY4(op, ip);
  100. op += 4;
  101. ip += 4;
  102. t -= 4;
  103. } while (t >= 4);
  104. if (t > 0)
  105. do *op++ = *ip++; while (--t > 0);
  106. } else {
  107. do *op++ = *ip++; while (--t > 0);
  108. }
  109. }
  110. }
  111. # if !defined(LZO_UNALIGNED_OK_4)
  112. else
  113. # endif
  114. #endif
  115. #if !defined(LZO_UNALIGNED_OK_4)
  116. {
  117. *op++ = *ip++;
  118. *op++ = *ip++;
  119. *op++ = *ip++;
  120. do *op++ = *ip++; while (--t > 0);
  121. }
  122. #endif
  123. first_literal_run:
  124. t = *ip++;
  125. if (t >= 16)
  126. goto match;
  127. #if defined(COPY_DICT)
  128. #if defined(LZO1Z)
  129. m_off = (1 + M2_MAX_OFFSET) + (t << 6) + (*ip++ >> 2);
  130. last_m_off = m_off;
  131. #else
  132. m_off = (1 + M2_MAX_OFFSET) + (t >> 2) + (*ip++ << 2);
  133. #endif
  134. NEED_OP(3);
  135. t = 3; COPY_DICT(t,m_off)
  136. #else /* !COPY_DICT */
  137. #if defined(LZO1Z)
  138. t = (1 + M2_MAX_OFFSET) + (t << 6) + (*ip++ >> 2);
  139. m_pos = op - t;
  140. last_m_off = t;
  141. #else
  142. m_pos = op - (1 + M2_MAX_OFFSET);
  143. m_pos -= t >> 2;
  144. m_pos -= *ip++ << 2;
  145. #endif
  146. TEST_LB(m_pos); NEED_OP(3);
  147. *op++ = *m_pos++;
  148. *op++ = *m_pos++;
  149. *op++ = *m_pos;
  150. #endif /* COPY_DICT */
  151. goto match_done;
  152. /* handle matches */
  153. do {
  154. match:
  155. if (t >= 64) { /* a M2 match */
  156. #if defined(COPY_DICT)
  157. #if defined(LZO1X)
  158. m_off = 1 + ((t >> 2) & 7) + (*ip++ << 3);
  159. t = (t >> 5) - 1;
  160. #elif defined(LZO1Y)
  161. m_off = 1 + ((t >> 2) & 3) + (*ip++ << 2);
  162. t = (t >> 4) - 3;
  163. #elif defined(LZO1Z)
  164. m_off = t & 0x1f;
  165. if (m_off >= 0x1c)
  166. m_off = last_m_off;
  167. else {
  168. m_off = 1 + (m_off << 6) + (*ip++ >> 2);
  169. last_m_off = m_off;
  170. }
  171. t = (t >> 5) - 1;
  172. #endif
  173. #else /* !COPY_DICT */
  174. #if defined(LZO1X)
  175. m_pos = op - 1;
  176. m_pos -= (t >> 2) & 7;
  177. m_pos -= *ip++ << 3;
  178. t = (t >> 5) - 1;
  179. #elif defined(LZO1Y)
  180. m_pos = op - 1;
  181. m_pos -= (t >> 2) & 3;
  182. m_pos -= *ip++ << 2;
  183. t = (t >> 4) - 3;
  184. #elif defined(LZO1Z)
  185. {
  186. unsigned off = t & 0x1f;
  187. m_pos = op;
  188. if (off >= 0x1c) {
  189. assert(last_m_off > 0);
  190. m_pos -= last_m_off;
  191. } else {
  192. off = 1 + (off << 6) + (*ip++ >> 2);
  193. m_pos -= off;
  194. last_m_off = off;
  195. }
  196. }
  197. t = (t >> 5) - 1;
  198. #endif
  199. TEST_LB(m_pos); assert(t > 0); NEED_OP(t+3-1);
  200. goto copy_match;
  201. #endif /* COPY_DICT */
  202. }
  203. else if (t >= 32) { /* a M3 match */
  204. t &= 31;
  205. if (t == 0) {
  206. NEED_IP(1);
  207. while (*ip == 0) {
  208. t += 255;
  209. ip++;
  210. NEED_IP(1);
  211. }
  212. TEST_IV(t);
  213. t += 31 + *ip++;
  214. }
  215. #if defined(COPY_DICT)
  216. #if defined(LZO1Z)
  217. m_off = 1 + (ip[0] << 6) + (ip[1] >> 2);
  218. last_m_off = m_off;
  219. #else
  220. m_off = 1 + (ip[0] >> 2) + (ip[1] << 6);
  221. #endif
  222. #else /* !COPY_DICT */
  223. #if defined(LZO1Z)
  224. {
  225. unsigned off = 1 + (ip[0] << 6) + (ip[1] >> 2);
  226. m_pos = op - off;
  227. last_m_off = off;
  228. }
  229. #elif defined(LZO_UNALIGNED_OK_2) && defined(LZO_ABI_LITTLE_ENDIAN)
  230. m_pos = op - 1;
  231. m_pos -= (* (const lzo_ushortp) ip) >> 2;
  232. #else
  233. m_pos = op - 1;
  234. m_pos -= (ip[0] >> 2) + (ip[1] << 6);
  235. #endif
  236. #endif /* COPY_DICT */
  237. ip += 2;
  238. }
  239. else if (t >= 16) { /* a M4 match */
  240. #if defined(COPY_DICT)
  241. m_off = (t & 8) << 11;
  242. #else /* !COPY_DICT */
  243. m_pos = op;
  244. m_pos -= (t & 8) << 11;
  245. #endif /* COPY_DICT */
  246. t &= 7;
  247. if (t == 0) {
  248. NEED_IP(1);
  249. while (*ip == 0) {
  250. t += 255;
  251. ip++;
  252. NEED_IP(1);
  253. }
  254. TEST_IV(t);
  255. t += 7 + *ip++;
  256. }
  257. #if defined(COPY_DICT)
  258. #if defined(LZO1Z)
  259. m_off += (ip[0] << 6) + (ip[1] >> 2);
  260. #else
  261. m_off += (ip[0] >> 2) + (ip[1] << 6);
  262. #endif
  263. ip += 2;
  264. if (m_off == 0)
  265. goto eof_found;
  266. m_off += 0x4000;
  267. #if defined(LZO1Z)
  268. last_m_off = m_off;
  269. #endif
  270. #else /* !COPY_DICT */
  271. #if defined(LZO1Z)
  272. m_pos -= (ip[0] << 6) + (ip[1] >> 2);
  273. #elif defined(LZO_UNALIGNED_OK_2) && defined(LZO_ABI_LITTLE_ENDIAN)
  274. m_pos -= (* (const lzo_ushortp) ip) >> 2;
  275. #else
  276. m_pos -= (ip[0] >> 2) + (ip[1] << 6);
  277. #endif
  278. ip += 2;
  279. if (m_pos == op)
  280. goto eof_found;
  281. m_pos -= 0x4000;
  282. #if defined(LZO1Z)
  283. last_m_off = pd((const uint8_t*)op, m_pos);
  284. #endif
  285. #endif /* COPY_DICT */
  286. }
  287. else { /* a M1 match */
  288. #if defined(COPY_DICT)
  289. #if defined(LZO1Z)
  290. m_off = 1 + (t << 6) + (*ip++ >> 2);
  291. last_m_off = m_off;
  292. #else
  293. m_off = 1 + (t >> 2) + (*ip++ << 2);
  294. #endif
  295. NEED_OP(2);
  296. t = 2; COPY_DICT(t,m_off)
  297. #else /* !COPY_DICT */
  298. #if defined(LZO1Z)
  299. t = 1 + (t << 6) + (*ip++ >> 2);
  300. m_pos = op - t;
  301. last_m_off = t;
  302. #else
  303. m_pos = op - 1;
  304. m_pos -= t >> 2;
  305. m_pos -= *ip++ << 2;
  306. #endif
  307. TEST_LB(m_pos); NEED_OP(2);
  308. *op++ = *m_pos++;
  309. *op++ = *m_pos;
  310. #endif /* COPY_DICT */
  311. goto match_done;
  312. }
  313. /* copy match */
  314. #if defined(COPY_DICT)
  315. NEED_OP(t+3-1);
  316. t += 3-1; COPY_DICT(t,m_off)
  317. #else /* !COPY_DICT */
  318. TEST_LB(m_pos); assert(t > 0); NEED_OP(t+3-1);
  319. #if defined(LZO_UNALIGNED_OK_4) || defined(LZO_ALIGNED_OK_4)
  320. # if !defined(LZO_UNALIGNED_OK_4)
  321. if (t >= 2 * 4 - (3 - 1) && PTR_ALIGNED2_4(op,m_pos)) {
  322. assert((op - m_pos) >= 4); /* both pointers are aligned */
  323. # else
  324. if (t >= 2 * 4 - (3 - 1) && (op - m_pos) >= 4) {
  325. # endif
  326. COPY4(op,m_pos);
  327. op += 4; m_pos += 4; t -= 4 - (3 - 1);
  328. do {
  329. COPY4(op,m_pos);
  330. op += 4; m_pos += 4; t -= 4;
  331. } while (t >= 4);
  332. if (t > 0)
  333. do *op++ = *m_pos++; while (--t > 0);
  334. }
  335. else
  336. #endif
  337. {
  338. copy_match:
  339. *op++ = *m_pos++; *op++ = *m_pos++;
  340. do *op++ = *m_pos++; while (--t > 0);
  341. }
  342. #endif /* COPY_DICT */
  343. match_done:
  344. #if defined(LZO1Z)
  345. t = ip[-1] & 3;
  346. #else
  347. t = ip[-2] & 3;
  348. #endif
  349. if (t == 0)
  350. break;
  351. /* copy literals */
  352. match_next:
  353. assert(t > 0);
  354. assert(t < 4);
  355. NEED_OP(t);
  356. NEED_IP(t+1);
  357. #if 0
  358. do *op++ = *ip++; while (--t > 0);
  359. #else
  360. *op++ = *ip++;
  361. if (t > 1) {
  362. *op++ = *ip++;
  363. if (t > 2)
  364. *op++ = *ip++;
  365. }
  366. #endif
  367. t = *ip++;
  368. } while (TEST_IP && TEST_OP);
  369. }
  370. //#if defined(HAVE_TEST_IP) || defined(HAVE_TEST_OP)
  371. /* no EOF code was found */
  372. *out_len = pd(op, out);
  373. return LZO_E_EOF_NOT_FOUND;
  374. //#endif
  375. eof_found:
  376. assert(t == 1);
  377. *out_len = pd(op, out);
  378. return (ip == ip_end ? LZO_E_OK :
  379. (ip < ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));
  380. //#if defined(HAVE_NEED_IP)
  381. input_overrun:
  382. *out_len = pd(op, out);
  383. return LZO_E_INPUT_OVERRUN;
  384. //#endif
  385. //#if defined(HAVE_NEED_OP)
  386. output_overrun:
  387. *out_len = pd(op, out);
  388. return LZO_E_OUTPUT_OVERRUN;
  389. //#endif
  390. //#if defined(LZO_TEST_OVERRUN_LOOKBEHIND)
  391. lookbehind_overrun:
  392. *out_len = pd(op, out);
  393. return LZO_E_LOOKBEHIND_OVERRUN;
  394. //#endif
  395. }