3
0

lzo1x_9x.c 21 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921
  1. /* lzo1x_9x.c -- implementation of the LZO1X-999 compression algorithm
  2. This file is part of the LZO real-time data compression library.
  3. Copyright (C) 2008 Markus Franz Xaver Johannes Oberhumer
  4. Copyright (C) 2007 Markus Franz Xaver Johannes Oberhumer
  5. Copyright (C) 2006 Markus Franz Xaver Johannes Oberhumer
  6. Copyright (C) 2005 Markus Franz Xaver Johannes Oberhumer
  7. Copyright (C) 2004 Markus Franz Xaver Johannes Oberhumer
  8. Copyright (C) 2003 Markus Franz Xaver Johannes Oberhumer
  9. Copyright (C) 2002 Markus Franz Xaver Johannes Oberhumer
  10. Copyright (C) 2001 Markus Franz Xaver Johannes Oberhumer
  11. Copyright (C) 2000 Markus Franz Xaver Johannes Oberhumer
  12. Copyright (C) 1999 Markus Franz Xaver Johannes Oberhumer
  13. Copyright (C) 1998 Markus Franz Xaver Johannes Oberhumer
  14. Copyright (C) 1997 Markus Franz Xaver Johannes Oberhumer
  15. Copyright (C) 1996 Markus Franz Xaver Johannes Oberhumer
  16. All Rights Reserved.
  17. The LZO library is free software; you can redistribute it and/or
  18. modify it under the terms of the GNU General Public License as
  19. published by the Free Software Foundation; either version 2 of
  20. the License, or (at your option) any later version.
  21. The LZO library is distributed in the hope that it will be useful,
  22. but WITHOUT ANY WARRANTY; without even the implied warranty of
  23. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  24. GNU General Public License for more details.
  25. You should have received a copy of the GNU General Public License
  26. along with the LZO library; see the file COPYING.
  27. If not, write to the Free Software Foundation, Inc.,
  28. 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  29. Markus F.X.J. Oberhumer
  30. <markus@oberhumer.com>
  31. http://www.oberhumer.com/opensource/lzo/
  32. */
  33. #include "libbb.h"
  34. /* The following is probably only safe on Intel-compatible processors ... */
  35. #define LZO_UNALIGNED_OK_2
  36. #define LZO_UNALIGNED_OK_4
  37. #include "liblzo.h"
  38. #define LZO_MAX(a,b) ((a) >= (b) ? (a) : (b))
  39. #define LZO_MIN(a,b) ((a) <= (b) ? (a) : (b))
  40. #define LZO_MAX3(a,b,c) ((a) >= (b) ? LZO_MAX(a,c) : LZO_MAX(b,c))
  41. /***********************************************************************
  42. //
  43. ************************************************************************/
  44. #define SWD_N M4_MAX_OFFSET /* size of ring buffer */
  45. #define SWD_F 2048 /* upper limit for match length */
  46. #define SWD_BEST_OFF (LZO_MAX3(M2_MAX_LEN, M3_MAX_LEN, M4_MAX_LEN) + 1)
  47. typedef struct {
  48. int init;
  49. unsigned look; /* bytes in lookahead buffer */
  50. unsigned m_len;
  51. unsigned m_off;
  52. const uint8_t *bp;
  53. const uint8_t *ip;
  54. const uint8_t *in;
  55. const uint8_t *in_end;
  56. uint8_t *out;
  57. unsigned r1_lit;
  58. } lzo1x_999_t;
  59. #define getbyte(c) ((c).ip < (c).in_end ? *((c).ip)++ : (-1))
  60. /* lzo_swd.c -- sliding window dictionary */
  61. /***********************************************************************
  62. //
  63. ************************************************************************/
  64. #define SWD_UINT_MAX USHRT_MAX
  65. #ifndef SWD_HSIZE
  66. # define SWD_HSIZE 16384
  67. #endif
  68. #ifndef SWD_MAX_CHAIN
  69. # define SWD_MAX_CHAIN 2048
  70. #endif
  71. #define HEAD3(b, p) \
  72. ( ((0x9f5f * ((((b[p]<<5)^b[p+1])<<5) ^ b[p+2])) >> 5) & (SWD_HSIZE-1) )
  73. #if defined(LZO_UNALIGNED_OK_2)
  74. # define HEAD2(b,p) (* (uint16_t *) &(b[p]))
  75. #else
  76. # define HEAD2(b,p) (b[p] ^ ((unsigned)b[p+1]<<8))
  77. #endif
  78. #define NIL2 SWD_UINT_MAX
  79. typedef struct lzo_swd {
  80. /* public - "built-in" */
  81. /* public - configuration */
  82. unsigned max_chain;
  83. int use_best_off;
  84. /* public - output */
  85. unsigned m_len;
  86. unsigned m_off;
  87. unsigned look;
  88. int b_char;
  89. #if defined(SWD_BEST_OFF)
  90. unsigned best_off[SWD_BEST_OFF];
  91. #endif
  92. /* semi public */
  93. lzo1x_999_t *c;
  94. unsigned m_pos;
  95. #if defined(SWD_BEST_OFF)
  96. unsigned best_pos[SWD_BEST_OFF];
  97. #endif
  98. /* private */
  99. unsigned ip; /* input pointer (lookahead) */
  100. unsigned bp; /* buffer pointer */
  101. unsigned rp; /* remove pointer */
  102. unsigned node_count;
  103. unsigned first_rp;
  104. uint8_t b[SWD_N + SWD_F];
  105. uint8_t b_wrap[SWD_F]; /* must follow b */
  106. uint16_t head3[SWD_HSIZE];
  107. uint16_t succ3[SWD_N + SWD_F];
  108. uint16_t best3[SWD_N + SWD_F];
  109. uint16_t llen3[SWD_HSIZE];
  110. #ifdef HEAD2
  111. uint16_t head2[65536L];
  112. #endif
  113. } lzo_swd_t, *lzo_swd_p;
  114. #define SIZEOF_LZO_SWD_T (sizeof(lzo_swd_t))
  115. /* Access macro for head3.
  116. * head3[key] may be uninitialized, but then its value will never be used.
  117. */
  118. #define s_get_head3(s,key) s->head3[key]
  119. /***********************************************************************
  120. //
  121. ************************************************************************/
  122. #define B_SIZE (SWD_N + SWD_F)
  123. static int swd_init(lzo_swd_p s)
  124. {
  125. /* defaults */
  126. s->node_count = SWD_N;
  127. memset(s->llen3, 0, sizeof(s->llen3[0]) * (unsigned)SWD_HSIZE);
  128. #ifdef HEAD2
  129. memset(s->head2, 0xff, sizeof(s->head2[0]) * 65536L);
  130. assert(s->head2[0] == NIL2);
  131. #endif
  132. s->ip = 0;
  133. s->bp = s->ip;
  134. s->first_rp = s->ip;
  135. assert(s->ip + SWD_F <= B_SIZE);
  136. s->look = (unsigned) (s->c->in_end - s->c->ip);
  137. if (s->look > 0) {
  138. if (s->look > SWD_F)
  139. s->look = SWD_F;
  140. memcpy(&s->b[s->ip], s->c->ip, s->look);
  141. s->c->ip += s->look;
  142. s->ip += s->look;
  143. }
  144. if (s->ip == B_SIZE)
  145. s->ip = 0;
  146. s->rp = s->first_rp;
  147. if (s->rp >= s->node_count)
  148. s->rp -= s->node_count;
  149. else
  150. s->rp += B_SIZE - s->node_count;
  151. return LZO_E_OK;
  152. }
  153. #define swd_pos2off(s,pos) \
  154. (s->bp > (pos) ? s->bp - (pos) : B_SIZE - ((pos) - s->bp))
  155. /***********************************************************************
  156. //
  157. ************************************************************************/
  158. static void swd_getbyte(lzo_swd_p s)
  159. {
  160. int c;
  161. if ((c = getbyte(*(s->c))) < 0) {
  162. if (s->look > 0)
  163. --s->look;
  164. } else {
  165. s->b[s->ip] = c;
  166. if (s->ip < SWD_F)
  167. s->b_wrap[s->ip] = c;
  168. }
  169. if (++s->ip == B_SIZE)
  170. s->ip = 0;
  171. if (++s->bp == B_SIZE)
  172. s->bp = 0;
  173. if (++s->rp == B_SIZE)
  174. s->rp = 0;
  175. }
  176. /***********************************************************************
  177. // remove node from lists
  178. ************************************************************************/
  179. static void swd_remove_node(lzo_swd_p s, unsigned node)
  180. {
  181. if (s->node_count == 0) {
  182. unsigned key;
  183. key = HEAD3(s->b,node);
  184. assert(s->llen3[key] > 0);
  185. --s->llen3[key];
  186. #ifdef HEAD2
  187. key = HEAD2(s->b,node);
  188. assert(s->head2[key] != NIL2);
  189. if ((unsigned) s->head2[key] == node)
  190. s->head2[key] = NIL2;
  191. #endif
  192. } else
  193. --s->node_count;
  194. }
  195. /***********************************************************************
  196. //
  197. ************************************************************************/
  198. static void swd_accept(lzo_swd_p s, unsigned n)
  199. {
  200. assert(n <= s->look);
  201. while (n--) {
  202. unsigned key;
  203. swd_remove_node(s,s->rp);
  204. /* add bp into HEAD3 */
  205. key = HEAD3(s->b, s->bp);
  206. s->succ3[s->bp] = s_get_head3(s, key);
  207. s->head3[key] = s->bp;
  208. s->best3[s->bp] = SWD_F + 1;
  209. s->llen3[key]++;
  210. assert(s->llen3[key] <= SWD_N);
  211. #ifdef HEAD2
  212. /* add bp into HEAD2 */
  213. key = HEAD2(s->b, s->bp);
  214. s->head2[key] = s->bp;
  215. #endif
  216. swd_getbyte(s);
  217. }
  218. }
  219. /***********************************************************************
  220. //
  221. ************************************************************************/
  222. static void swd_search(lzo_swd_p s, unsigned node, unsigned cnt)
  223. {
  224. const uint8_t *p1;
  225. const uint8_t *p2;
  226. const uint8_t *px;
  227. unsigned m_len = s->m_len;
  228. const uint8_t *b = s->b;
  229. const uint8_t *bp = s->b + s->bp;
  230. const uint8_t *bx = s->b + s->bp + s->look;
  231. unsigned char scan_end1;
  232. assert(s->m_len > 0);
  233. scan_end1 = bp[m_len - 1];
  234. for ( ; cnt-- > 0; node = s->succ3[node]) {
  235. p1 = bp;
  236. p2 = b + node;
  237. px = bx;
  238. assert(m_len < s->look);
  239. if (p2[m_len - 1] == scan_end1
  240. && p2[m_len] == p1[m_len]
  241. && p2[0] == p1[0]
  242. && p2[1] == p1[1]
  243. ) {
  244. unsigned i;
  245. assert(lzo_memcmp(bp, &b[node], 3) == 0);
  246. p1 += 2; p2 += 2;
  247. do {} while (++p1 < px && *p1 == *++p2);
  248. i = p1-bp;
  249. assert(lzo_memcmp(bp, &b[node], i) == 0);
  250. #if defined(SWD_BEST_OFF)
  251. if (i < SWD_BEST_OFF) {
  252. if (s->best_pos[i] == 0)
  253. s->best_pos[i] = node + 1;
  254. }
  255. #endif
  256. if (i > m_len) {
  257. s->m_len = m_len = i;
  258. s->m_pos = node;
  259. if (m_len == s->look)
  260. return;
  261. if (m_len >= SWD_F)
  262. return;
  263. if (m_len > (unsigned) s->best3[node])
  264. return;
  265. scan_end1 = bp[m_len - 1];
  266. }
  267. }
  268. }
  269. }
  270. /***********************************************************************
  271. //
  272. ************************************************************************/
  273. #ifdef HEAD2
  274. static int swd_search2(lzo_swd_p s)
  275. {
  276. unsigned key;
  277. assert(s->look >= 2);
  278. assert(s->m_len > 0);
  279. key = s->head2[HEAD2(s->b, s->bp)];
  280. if (key == NIL2)
  281. return 0;
  282. assert(lzo_memcmp(&s->b[s->bp], &s->b[key], 2) == 0);
  283. #if defined(SWD_BEST_OFF)
  284. if (s->best_pos[2] == 0)
  285. s->best_pos[2] = key + 1;
  286. #endif
  287. if (s->m_len < 2) {
  288. s->m_len = 2;
  289. s->m_pos = key;
  290. }
  291. return 1;
  292. }
  293. #endif
  294. /***********************************************************************
  295. //
  296. ************************************************************************/
  297. static void swd_findbest(lzo_swd_p s)
  298. {
  299. unsigned key;
  300. unsigned cnt, node;
  301. unsigned len;
  302. assert(s->m_len > 0);
  303. /* get current head, add bp into HEAD3 */
  304. key = HEAD3(s->b,s->bp);
  305. node = s->succ3[s->bp] = s_get_head3(s, key);
  306. cnt = s->llen3[key]++;
  307. assert(s->llen3[key] <= SWD_N + SWD_F);
  308. if (cnt > s->max_chain)
  309. cnt = s->max_chain;
  310. s->head3[key] = s->bp;
  311. s->b_char = s->b[s->bp];
  312. len = s->m_len;
  313. if (s->m_len >= s->look) {
  314. if (s->look == 0)
  315. s->b_char = -1;
  316. s->m_off = 0;
  317. s->best3[s->bp] = SWD_F + 1;
  318. } else {
  319. #ifdef HEAD2
  320. if (swd_search2(s))
  321. #endif
  322. if (s->look >= 3)
  323. swd_search(s, node, cnt);
  324. if (s->m_len > len)
  325. s->m_off = swd_pos2off(s,s->m_pos);
  326. s->best3[s->bp] = s->m_len;
  327. #if defined(SWD_BEST_OFF)
  328. if (s->use_best_off) {
  329. int i;
  330. for (i = 2; i < SWD_BEST_OFF; i++) {
  331. if (s->best_pos[i] > 0)
  332. s->best_off[i] = swd_pos2off(s, s->best_pos[i]-1);
  333. else
  334. s->best_off[i] = 0;
  335. }
  336. }
  337. #endif
  338. }
  339. swd_remove_node(s,s->rp);
  340. #ifdef HEAD2
  341. /* add bp into HEAD2 */
  342. key = HEAD2(s->b, s->bp);
  343. s->head2[key] = s->bp;
  344. #endif
  345. }
  346. #undef HEAD3
  347. #undef HEAD2
  348. #undef s_get_head3
  349. /***********************************************************************
  350. //
  351. ************************************************************************/
  352. static int init_match(lzo1x_999_t *c, lzo_swd_p s, uint32_t use_best_off)
  353. {
  354. int r;
  355. assert(!c->init);
  356. c->init = 1;
  357. s->c = c;
  358. r = swd_init(s);
  359. if (r != 0)
  360. return r;
  361. s->use_best_off = use_best_off;
  362. return r;
  363. }
  364. /***********************************************************************
  365. //
  366. ************************************************************************/
  367. static int find_match(lzo1x_999_t *c, lzo_swd_p s,
  368. unsigned this_len, unsigned skip)
  369. {
  370. assert(c->init);
  371. if (skip > 0) {
  372. assert(this_len >= skip);
  373. swd_accept(s, this_len - skip);
  374. } else {
  375. assert(this_len <= 1);
  376. }
  377. s->m_len = 1;
  378. s->m_len = 1;
  379. #ifdef SWD_BEST_OFF
  380. if (s->use_best_off)
  381. memset(s->best_pos, 0, sizeof(s->best_pos));
  382. #endif
  383. swd_findbest(s);
  384. c->m_len = s->m_len;
  385. c->m_off = s->m_off;
  386. swd_getbyte(s);
  387. if (s->b_char < 0) {
  388. c->look = 0;
  389. c->m_len = 0;
  390. } else {
  391. c->look = s->look + 1;
  392. }
  393. c->bp = c->ip - c->look;
  394. return LZO_E_OK;
  395. }
  396. /* this is a public functions, but there is no prototype in a header file */
  397. static int lzo1x_999_compress_internal(const uint8_t *in , unsigned in_len,
  398. uint8_t *out, unsigned *out_len,
  399. void *wrkmem,
  400. unsigned good_length,
  401. unsigned max_lazy,
  402. unsigned max_chain,
  403. uint32_t use_best_off);
  404. /***********************************************************************
  405. //
  406. ************************************************************************/
  407. static uint8_t *code_match(lzo1x_999_t *c,
  408. uint8_t *op, unsigned m_len, unsigned m_off)
  409. {
  410. assert(op > c->out);
  411. if (m_len == 2) {
  412. assert(m_off <= M1_MAX_OFFSET);
  413. assert(c->r1_lit > 0);
  414. assert(c->r1_lit < 4);
  415. m_off -= 1;
  416. *op++ = M1_MARKER | ((m_off & 3) << 2);
  417. *op++ = m_off >> 2;
  418. } else if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET) {
  419. assert(m_len >= 3);
  420. m_off -= 1;
  421. *op++ = ((m_len - 1) << 5) | ((m_off & 7) << 2);
  422. *op++ = m_off >> 3;
  423. assert(op[-2] >= M2_MARKER);
  424. } else if (m_len == M2_MIN_LEN && m_off <= MX_MAX_OFFSET && c->r1_lit >= 4) {
  425. assert(m_len == 3);
  426. assert(m_off > M2_MAX_OFFSET);
  427. m_off -= 1 + M2_MAX_OFFSET;
  428. *op++ = M1_MARKER | ((m_off & 3) << 2);
  429. *op++ = m_off >> 2;
  430. } else if (m_off <= M3_MAX_OFFSET) {
  431. assert(m_len >= 3);
  432. m_off -= 1;
  433. if (m_len <= M3_MAX_LEN)
  434. *op++ = M3_MARKER | (m_len - 2);
  435. else {
  436. m_len -= M3_MAX_LEN;
  437. *op++ = M3_MARKER | 0;
  438. while (m_len > 255) {
  439. m_len -= 255;
  440. *op++ = 0;
  441. }
  442. assert(m_len > 0);
  443. *op++ = m_len;
  444. }
  445. *op++ = m_off << 2;
  446. *op++ = m_off >> 6;
  447. } else {
  448. unsigned k;
  449. assert(m_len >= 3);
  450. assert(m_off > 0x4000);
  451. assert(m_off <= 0xbfff);
  452. m_off -= 0x4000;
  453. k = (m_off & 0x4000) >> 11;
  454. if (m_len <= M4_MAX_LEN)
  455. *op++ = M4_MARKER | k | (m_len - 2);
  456. else {
  457. m_len -= M4_MAX_LEN;
  458. *op++ = M4_MARKER | k | 0;
  459. while (m_len > 255) {
  460. m_len -= 255;
  461. *op++ = 0;
  462. }
  463. assert(m_len > 0);
  464. *op++ = m_len;
  465. }
  466. *op++ = m_off << 2;
  467. *op++ = m_off >> 6;
  468. }
  469. return op;
  470. }
  471. static uint8_t *STORE_RUN(lzo1x_999_t *c, uint8_t *op,
  472. const uint8_t *ii, unsigned t)
  473. {
  474. if (op == c->out && t <= 238) {
  475. *op++ = 17 + t;
  476. } else if (t <= 3) {
  477. op[-2] |= t;
  478. } else if (t <= 18) {
  479. *op++ = t - 3;
  480. } else {
  481. unsigned tt = t - 18;
  482. *op++ = 0;
  483. while (tt > 255) {
  484. tt -= 255;
  485. *op++ = 0;
  486. }
  487. assert(tt > 0);
  488. *op++ = tt;
  489. }
  490. do *op++ = *ii++; while (--t > 0);
  491. return op;
  492. }
  493. static uint8_t *code_run(lzo1x_999_t *c, uint8_t *op, const uint8_t *ii,
  494. unsigned lit)
  495. {
  496. if (lit > 0) {
  497. assert(m_len >= 2);
  498. op = STORE_RUN(c, op, ii, lit);
  499. } else {
  500. assert(m_len >= 3);
  501. }
  502. c->r1_lit = lit;
  503. return op;
  504. }
  505. /***********************************************************************
  506. //
  507. ************************************************************************/
  508. static int len_of_coded_match(unsigned m_len, unsigned m_off, unsigned lit)
  509. {
  510. int n = 4;
  511. if (m_len < 2)
  512. return -1;
  513. if (m_len == 2)
  514. return (m_off <= M1_MAX_OFFSET && lit > 0 && lit < 4) ? 2 : -1;
  515. if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET)
  516. return 2;
  517. if (m_len == M2_MIN_LEN && m_off <= MX_MAX_OFFSET && lit >= 4)
  518. return 2;
  519. if (m_off <= M3_MAX_OFFSET) {
  520. if (m_len <= M3_MAX_LEN)
  521. return 3;
  522. m_len -= M3_MAX_LEN;
  523. } else if (m_off <= M4_MAX_OFFSET) {
  524. if (m_len <= M4_MAX_LEN)
  525. return 3;
  526. m_len -= M4_MAX_LEN;
  527. } else
  528. return -1;
  529. while (m_len > 255) {
  530. m_len -= 255;
  531. n++;
  532. }
  533. return n;
  534. }
  535. static int min_gain(unsigned ahead, unsigned lit1,
  536. unsigned lit2, int l1, int l2, int l3)
  537. {
  538. int lazy_match_min_gain = 0;
  539. assert (ahead >= 1);
  540. lazy_match_min_gain += ahead;
  541. if (lit1 <= 3)
  542. lazy_match_min_gain += (lit2 <= 3) ? 0 : 2;
  543. else if (lit1 <= 18)
  544. lazy_match_min_gain += (lit2 <= 18) ? 0 : 1;
  545. lazy_match_min_gain += (l2 - l1) * 2;
  546. if (l3 > 0)
  547. lazy_match_min_gain -= (ahead - l3) * 2;
  548. if (lazy_match_min_gain < 0)
  549. lazy_match_min_gain = 0;
  550. return lazy_match_min_gain;
  551. }
  552. /***********************************************************************
  553. //
  554. ************************************************************************/
  555. #if defined(SWD_BEST_OFF)
  556. static void better_match(const lzo_swd_p swd,
  557. unsigned *m_len, unsigned *m_off)
  558. {
  559. if (*m_len <= M2_MIN_LEN)
  560. return;
  561. if (*m_off <= M2_MAX_OFFSET)
  562. return;
  563. /* M3/M4 -> M2 */
  564. if (*m_off > M2_MAX_OFFSET
  565. && *m_len >= M2_MIN_LEN + 1 && *m_len <= M2_MAX_LEN + 1
  566. && swd->best_off[*m_len-1] && swd->best_off[*m_len-1] <= M2_MAX_OFFSET
  567. ) {
  568. *m_len = *m_len - 1;
  569. *m_off = swd->best_off[*m_len];
  570. return;
  571. }
  572. /* M4 -> M2 */
  573. if (*m_off > M3_MAX_OFFSET
  574. && *m_len >= M4_MAX_LEN + 1 && *m_len <= M2_MAX_LEN + 2
  575. && swd->best_off[*m_len-2] && swd->best_off[*m_len-2] <= M2_MAX_OFFSET
  576. ) {
  577. *m_len = *m_len - 2;
  578. *m_off = swd->best_off[*m_len];
  579. return;
  580. }
  581. /* M4 -> M3 */
  582. if (*m_off > M3_MAX_OFFSET
  583. && *m_len >= M4_MAX_LEN + 1 && *m_len <= M3_MAX_LEN + 1
  584. && swd->best_off[*m_len-1] && swd->best_off[*m_len-1] <= M3_MAX_OFFSET
  585. ) {
  586. *m_len = *m_len - 1;
  587. *m_off = swd->best_off[*m_len];
  588. }
  589. }
  590. #endif
  591. /***********************************************************************
  592. //
  593. ************************************************************************/
  594. static int lzo1x_999_compress_internal(const uint8_t *in, unsigned in_len,
  595. uint8_t *out, unsigned *out_len,
  596. void *wrkmem,
  597. unsigned good_length,
  598. unsigned max_lazy,
  599. unsigned max_chain,
  600. uint32_t use_best_off)
  601. {
  602. uint8_t *op;
  603. const uint8_t *ii;
  604. unsigned lit;
  605. unsigned m_len, m_off;
  606. lzo1x_999_t cc;
  607. lzo1x_999_t *const c = &cc;
  608. const lzo_swd_p swd = (lzo_swd_p) wrkmem;
  609. int r;
  610. c->init = 0;
  611. c->ip = c->in = in;
  612. c->in_end = in + in_len;
  613. c->out = out;
  614. op = out;
  615. ii = c->ip; /* point to start of literal run */
  616. lit = 0;
  617. c->r1_lit = 0;
  618. r = init_match(c, swd, use_best_off);
  619. if (r != 0)
  620. return r;
  621. swd->max_chain = max_chain;
  622. r = find_match(c, swd, 0, 0);
  623. if (r != 0)
  624. return r;
  625. while (c->look > 0) {
  626. unsigned ahead;
  627. unsigned max_ahead;
  628. int l1, l2, l3;
  629. m_len = c->m_len;
  630. m_off = c->m_off;
  631. assert(c->bp == c->ip - c->look);
  632. assert(c->bp >= in);
  633. if (lit == 0)
  634. ii = c->bp;
  635. assert(ii + lit == c->bp);
  636. assert(swd->b_char == *(c->bp));
  637. if (m_len < 2
  638. || (m_len == 2 && (m_off > M1_MAX_OFFSET || lit == 0 || lit >= 4))
  639. /* Do not accept this match for compressed-data compatibility
  640. * with LZO v1.01 and before
  641. * [ might be a problem for decompress() and optimize() ]
  642. */
  643. || (m_len == 2 && op == out)
  644. || (op == out && lit == 0)
  645. ) {
  646. /* a literal */
  647. m_len = 0;
  648. }
  649. else if (m_len == M2_MIN_LEN) {
  650. /* compression ratio improves if we code a literal in some cases */
  651. if (m_off > MX_MAX_OFFSET && lit >= 4)
  652. m_len = 0;
  653. }
  654. if (m_len == 0) {
  655. /* a literal */
  656. lit++;
  657. swd->max_chain = max_chain;
  658. r = find_match(c, swd, 1, 0);
  659. assert(r == 0);
  660. continue;
  661. }
  662. /* a match */
  663. #if defined(SWD_BEST_OFF)
  664. if (swd->use_best_off)
  665. better_match(swd, &m_len, &m_off);
  666. #endif
  667. /* shall we try a lazy match ? */
  668. ahead = 0;
  669. if (m_len >= max_lazy) {
  670. /* no */
  671. l1 = 0;
  672. max_ahead = 0;
  673. } else {
  674. /* yes, try a lazy match */
  675. l1 = len_of_coded_match(m_len, m_off, lit);
  676. assert(l1 > 0);
  677. max_ahead = LZO_MIN(2, (unsigned)l1 - 1);
  678. }
  679. while (ahead < max_ahead && c->look > m_len) {
  680. int lazy_match_min_gain;
  681. if (m_len >= good_length)
  682. swd->max_chain = max_chain >> 2;
  683. else
  684. swd->max_chain = max_chain;
  685. r = find_match(c, swd, 1, 0);
  686. ahead++;
  687. assert(r == 0);
  688. assert(c->look > 0);
  689. assert(ii + lit + ahead == c->bp);
  690. if (c->m_len < m_len)
  691. continue;
  692. if (c->m_len == m_len && c->m_off >= m_off)
  693. continue;
  694. #if defined(SWD_BEST_OFF)
  695. if (swd->use_best_off)
  696. better_match(swd, &c->m_len, &c->m_off);
  697. #endif
  698. l2 = len_of_coded_match(c->m_len, c->m_off, lit+ahead);
  699. if (l2 < 0)
  700. continue;
  701. /* compressed-data compatibility [see above] */
  702. l3 = (op == out) ? -1 : len_of_coded_match(ahead, m_off, lit);
  703. lazy_match_min_gain = min_gain(ahead, lit, lit+ahead, l1, l2, l3);
  704. if (c->m_len >= m_len + lazy_match_min_gain) {
  705. if (l3 > 0) {
  706. /* code previous run */
  707. op = code_run(c, op, ii, lit);
  708. lit = 0;
  709. /* code shortened match */
  710. op = code_match(c, op, ahead, m_off);
  711. } else {
  712. lit += ahead;
  713. assert(ii + lit == c->bp);
  714. }
  715. goto lazy_match_done;
  716. }
  717. }
  718. assert(ii + lit + ahead == c->bp);
  719. /* 1 - code run */
  720. op = code_run(c, op, ii, lit);
  721. lit = 0;
  722. /* 2 - code match */
  723. op = code_match(c, op, m_len, m_off);
  724. swd->max_chain = max_chain;
  725. r = find_match(c, swd, m_len, 1+ahead);
  726. assert(r == 0);
  727. lazy_match_done: ;
  728. }
  729. /* store final run */
  730. if (lit > 0)
  731. op = STORE_RUN(c, op, ii, lit);
  732. #if defined(LZO_EOF_CODE)
  733. *op++ = M4_MARKER | 1;
  734. *op++ = 0;
  735. *op++ = 0;
  736. #endif
  737. *out_len = op - out;
  738. return LZO_E_OK;
  739. }
  740. /***********************************************************************
  741. //
  742. ************************************************************************/
  743. int lzo1x_999_compress_level(const uint8_t *in, unsigned in_len,
  744. uint8_t *out, unsigned *out_len,
  745. void *wrkmem,
  746. int compression_level)
  747. {
  748. static const struct {
  749. uint16_t good_length;
  750. uint16_t max_lazy;
  751. uint16_t max_chain;
  752. uint16_t use_best_off;
  753. } c[3] = {
  754. { 8, 32, 256, 0 },
  755. { 32, 128, 2048, 1 },
  756. { SWD_F, SWD_F, 4096, 1 } /* max. compression */
  757. };
  758. if (compression_level < 7 || compression_level > 9)
  759. return LZO_E_ERROR;
  760. compression_level -= 7;
  761. return lzo1x_999_compress_internal(in, in_len, out, out_len, wrkmem,
  762. c[compression_level].good_length,
  763. c[compression_level].max_lazy,
  764. c[compression_level].max_chain,
  765. c[compression_level].use_best_off);
  766. }