compr_lzo.c 8.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401
  1. /*
  2. * JFFS2 -- Journalling Flash File System, Version 2.
  3. *
  4. * Copyright (C) 2004 Patrik Kluba,
  5. * University of Szeged, Hungary
  6. *
  7. * For licensing information, see the file 'LICENCE' in the
  8. * jffs2 directory.
  9. *
  10. * $Id: compr_lzo.c,v 1.3 2004/06/23 16:34:39 havasi Exp $
  11. *
  12. */
  13. /*
  14. LZO1X-1 (and -999) compression module for jffs2
  15. based on the original LZO sources
  16. */
  17. /* -*- Mode: C; indent-tabs-mode: t; c-basic-offset: 4; tab-width: 4 -*- */
  18. /*
  19. Original copyright notice follows:
  20. lzo1x_9x.c -- implementation of the LZO1X-999 compression algorithm
  21. lzo_ptr.h -- low-level pointer constructs
  22. lzo_swd.ch -- sliding window dictionary
  23. lzoconf.h -- configuration for the LZO real-time data compression library
  24. lzo_mchw.ch -- matching functions using a window
  25. minilzo.c -- mini subset of the LZO real-time data compression library
  26. config1x.h -- configuration for the LZO1X algorithm
  27. lzo1x.h -- public interface of the LZO1X compression algorithm
  28. These files are part of the LZO real-time data compression library.
  29. Copyright (C) 1996-2002 Markus Franz Xaver Johannes Oberhumer
  30. All Rights Reserved.
  31. The LZO library is free software; you can redistribute it and/or
  32. modify it under the terms of the GNU General Public License as
  33. published by the Free Software Foundation; either version 2 of
  34. the License, or (at your option) any later version.
  35. The LZO library is distributed in the hope that it will be useful,
  36. but WITHOUT ANY WARRANTY; without even the implied warranty of
  37. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  38. GNU General Public License for more details.
  39. You should have received a copy of the GNU General Public License
  40. along with the LZO library; see the file COPYING.
  41. If not, write to the Free Software Foundation, Inc.,
  42. 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  43. Markus F.X.J. Oberhumer
  44. <markus@oberhumer.com>
  45. */
  46. /*
  47. 2004-02-16 pajko <pajko(AT)halom(DOT)u-szeged(DOT)hu>
  48. Initial release
  49. -removed all 16 bit code
  50. -all sensitive data will be on 4 byte boundary
  51. -removed check parts for library use
  52. -removed all but LZO1X-* compression
  53. */
  54. #include <config.h>
  55. #include <linux/stddef.h>
  56. #include <jffs2/jffs2.h>
  57. #include <jffs2/compr_rubin.h>
  58. /* Integral types that have *exactly* the same number of bits as a lzo_voidp */
  59. typedef unsigned long lzo_ptr_t;
  60. typedef long lzo_sptr_t;
  61. /* data type definitions */
  62. #define U32 unsigned long
  63. #define S32 signed long
  64. #define I32 long
  65. #define U16 unsigned short
  66. #define S16 signed short
  67. #define I16 short
  68. #define U8 unsigned char
  69. #define S8 signed char
  70. #define I8 char
  71. #define M1_MAX_OFFSET 0x0400
  72. #define M2_MAX_OFFSET 0x0800
  73. #define M3_MAX_OFFSET 0x4000
  74. #define M4_MAX_OFFSET 0xbfff
  75. #define __COPY4(dst,src) * (lzo_uint32p)(dst) = * (const lzo_uint32p)(src)
  76. #define COPY4(dst,src) __COPY4((lzo_ptr_t)(dst),(lzo_ptr_t)(src))
  77. #define TEST_IP (ip < ip_end)
  78. #define TEST_OP (op <= op_end)
  79. #define NEED_IP(x) \
  80. if ((lzo_uint)(ip_end - ip) < (lzo_uint)(x)) goto input_overrun
  81. #define NEED_OP(x) \
  82. if ((lzo_uint)(op_end - op) < (lzo_uint)(x)) goto output_overrun
  83. #define TEST_LOOKBEHIND(m_pos,out) if (m_pos < out) goto lookbehind_overrun
  84. typedef U32 lzo_uint32;
  85. typedef I32 lzo_int32;
  86. typedef U32 lzo_uint;
  87. typedef I32 lzo_int;
  88. typedef int lzo_bool;
  89. #define lzo_byte U8
  90. #define lzo_bytep U8 *
  91. #define lzo_charp char *
  92. #define lzo_voidp void *
  93. #define lzo_shortp short *
  94. #define lzo_ushortp unsigned short *
  95. #define lzo_uint32p lzo_uint32 *
  96. #define lzo_int32p lzo_int32 *
  97. #define lzo_uintp lzo_uint *
  98. #define lzo_intp lzo_int *
  99. #define lzo_voidpp lzo_voidp *
  100. #define lzo_bytepp lzo_bytep *
  101. #define lzo_sizeof_dict_t sizeof(lzo_bytep)
  102. #define LZO_E_OK 0
  103. #define LZO_E_ERROR (-1)
  104. #define LZO_E_OUT_OF_MEMORY (-2) /* not used right now */
  105. #define LZO_E_NOT_COMPRESSIBLE (-3) /* not used right now */
  106. #define LZO_E_INPUT_OVERRUN (-4)
  107. #define LZO_E_OUTPUT_OVERRUN (-5)
  108. #define LZO_E_LOOKBEHIND_OVERRUN (-6)
  109. #define LZO_E_EOF_NOT_FOUND (-7)
  110. #define LZO_E_INPUT_NOT_CONSUMED (-8)
  111. #define PTR(a) ((lzo_ptr_t) (a))
  112. #define PTR_LINEAR(a) PTR(a)
  113. #define PTR_ALIGNED_4(a) ((PTR_LINEAR(a) & 3) == 0)
  114. #define PTR_ALIGNED_8(a) ((PTR_LINEAR(a) & 7) == 0)
  115. #define PTR_ALIGNED2_4(a,b) (((PTR_LINEAR(a) | PTR_LINEAR(b)) & 3) == 0)
  116. #define PTR_ALIGNED2_8(a,b) (((PTR_LINEAR(a) | PTR_LINEAR(b)) & 7) == 0)
  117. #define PTR_LT(a,b) (PTR(a) < PTR(b))
  118. #define PTR_GE(a,b) (PTR(a) >= PTR(b))
  119. #define PTR_DIFF(a,b) ((lzo_ptrdiff_t) (PTR(a) - PTR(b)))
  120. #define pd(a,b) ((lzo_uint) ((a)-(b)))
  121. typedef ptrdiff_t lzo_ptrdiff_t;
  122. static int
  123. lzo1x_decompress (const lzo_byte * in, lzo_uint in_len,
  124. lzo_byte * out, lzo_uintp out_len, lzo_voidp wrkmem)
  125. {
  126. register lzo_byte *op;
  127. register const lzo_byte *ip;
  128. register lzo_uint t;
  129. register const lzo_byte *m_pos;
  130. const lzo_byte *const ip_end = in + in_len;
  131. lzo_byte *const op_end = out + *out_len;
  132. *out_len = 0;
  133. op = out;
  134. ip = in;
  135. if (*ip > 17)
  136. {
  137. t = *ip++ - 17;
  138. if (t < 4)
  139. goto match_next;
  140. NEED_OP (t);
  141. NEED_IP (t + 1);
  142. do
  143. *op++ = *ip++;
  144. while (--t > 0);
  145. goto first_literal_run;
  146. }
  147. while (TEST_IP && TEST_OP)
  148. {
  149. t = *ip++;
  150. if (t >= 16)
  151. goto match;
  152. if (t == 0)
  153. {
  154. NEED_IP (1);
  155. while (*ip == 0)
  156. {
  157. t += 255;
  158. ip++;
  159. NEED_IP (1);
  160. }
  161. t += 15 + *ip++;
  162. }
  163. NEED_OP (t + 3);
  164. NEED_IP (t + 4);
  165. if (PTR_ALIGNED2_4 (op, ip))
  166. {
  167. COPY4 (op, ip);
  168. op += 4;
  169. ip += 4;
  170. if (--t > 0)
  171. {
  172. if (t >= 4)
  173. {
  174. do
  175. {
  176. COPY4 (op, ip);
  177. op += 4;
  178. ip += 4;
  179. t -= 4;
  180. }
  181. while (t >= 4);
  182. if (t > 0)
  183. do
  184. *op++ = *ip++;
  185. while (--t > 0);
  186. }
  187. else
  188. do
  189. *op++ = *ip++;
  190. while (--t > 0);
  191. }
  192. }
  193. else
  194. {
  195. *op++ = *ip++;
  196. *op++ = *ip++;
  197. *op++ = *ip++;
  198. do
  199. *op++ = *ip++;
  200. while (--t > 0);
  201. }
  202. first_literal_run:
  203. t = *ip++;
  204. if (t >= 16)
  205. goto match;
  206. m_pos = op - (1 + M2_MAX_OFFSET);
  207. m_pos -= t >> 2;
  208. m_pos -= *ip++ << 2;
  209. TEST_LOOKBEHIND (m_pos, out);
  210. NEED_OP (3);
  211. *op++ = *m_pos++;
  212. *op++ = *m_pos++;
  213. *op++ = *m_pos;
  214. goto match_done;
  215. while (TEST_IP && TEST_OP)
  216. {
  217. match:
  218. if (t >= 64)
  219. {
  220. m_pos = op - 1;
  221. m_pos -= (t >> 2) & 7;
  222. m_pos -= *ip++ << 3;
  223. t = (t >> 5) - 1;
  224. TEST_LOOKBEHIND (m_pos, out);
  225. NEED_OP (t + 3 - 1);
  226. goto copy_match;
  227. }
  228. else if (t >= 32)
  229. {
  230. t &= 31;
  231. if (t == 0)
  232. {
  233. NEED_IP (1);
  234. while (*ip == 0)
  235. {
  236. t += 255;
  237. ip++;
  238. NEED_IP (1);
  239. }
  240. t += 31 + *ip++;
  241. }
  242. m_pos = op - 1;
  243. m_pos -= (ip[0] >> 2) + (ip[1] << 6);
  244. ip += 2;
  245. }
  246. else if (t >= 16)
  247. {
  248. m_pos = op;
  249. m_pos -= (t & 8) << 11;
  250. t &= 7;
  251. if (t == 0)
  252. {
  253. NEED_IP (1);
  254. while (*ip == 0)
  255. {
  256. t += 255;
  257. ip++;
  258. NEED_IP (1);
  259. }
  260. t += 7 + *ip++;
  261. }
  262. m_pos -= (ip[0] >> 2) + (ip[1] << 6);
  263. ip += 2;
  264. if (m_pos == op)
  265. goto eof_found;
  266. m_pos -= 0x4000;
  267. }
  268. else
  269. {
  270. m_pos = op - 1;
  271. m_pos -= t >> 2;
  272. m_pos -= *ip++ << 2;
  273. TEST_LOOKBEHIND (m_pos, out);
  274. NEED_OP (2);
  275. *op++ = *m_pos++;
  276. *op++ = *m_pos;
  277. goto match_done;
  278. }
  279. TEST_LOOKBEHIND (m_pos, out);
  280. NEED_OP (t + 3 - 1);
  281. if (t >= 2 * 4 - (3 - 1)
  282. && PTR_ALIGNED2_4 (op, m_pos))
  283. {
  284. COPY4 (op, m_pos);
  285. op += 4;
  286. m_pos += 4;
  287. t -= 4 - (3 - 1);
  288. do
  289. {
  290. COPY4 (op, m_pos);
  291. op += 4;
  292. m_pos += 4;
  293. t -= 4;
  294. }
  295. while (t >= 4);
  296. if (t > 0)
  297. do
  298. *op++ = *m_pos++;
  299. while (--t > 0);
  300. }
  301. else
  302. {
  303. copy_match:
  304. *op++ = *m_pos++;
  305. *op++ = *m_pos++;
  306. do
  307. *op++ = *m_pos++;
  308. while (--t > 0);
  309. }
  310. match_done:
  311. t = ip[-2] & 3;
  312. if (t == 0)
  313. break;
  314. match_next:
  315. NEED_OP (t);
  316. NEED_IP (t + 1);
  317. do
  318. *op++ = *ip++;
  319. while (--t > 0);
  320. t = *ip++;
  321. }
  322. }
  323. *out_len = op - out;
  324. return LZO_E_EOF_NOT_FOUND;
  325. eof_found:
  326. *out_len = op - out;
  327. return (ip == ip_end ? LZO_E_OK :
  328. (ip <
  329. ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));
  330. input_overrun:
  331. *out_len = op - out;
  332. return LZO_E_INPUT_OVERRUN;
  333. output_overrun:
  334. *out_len = op - out;
  335. return LZO_E_OUTPUT_OVERRUN;
  336. lookbehind_overrun:
  337. *out_len = op - out;
  338. return LZO_E_LOOKBEHIND_OVERRUN;
  339. }
  340. int lzo_decompress(unsigned char *data_in, unsigned char *cpage_out,
  341. u32 srclen, u32 destlen)
  342. {
  343. lzo_uint outlen = destlen;
  344. return lzo1x_decompress (data_in, srclen, cpage_out, &outlen, NULL);
  345. }