176 |
if (s->look > 0) { |
if (s->look > 0) { |
177 |
if (s->look > SWD_F) |
if (s->look > SWD_F) |
178 |
s->look = SWD_F; |
s->look = SWD_F; |
179 |
memcpy(&s->b[s->ip],s->c->ip,s->look); |
memcpy(&s->b[s->ip], s->c->ip, s->look); |
180 |
s->c->ip += s->look; |
s->c->ip += s->look; |
181 |
s->ip += s->look; |
s->ip += s->look; |
182 |
} |
} |
256 |
swd_remove_node(s,s->rp); |
swd_remove_node(s,s->rp); |
257 |
|
|
258 |
/* add bp into HEAD3 */ |
/* add bp into HEAD3 */ |
259 |
key = HEAD3(s->b,s->bp); |
key = HEAD3(s->b, s->bp); |
260 |
s->succ3[s->bp] = s_get_head3(s,key); |
s->succ3[s->bp] = s_get_head3(s, key); |
261 |
s->head3[key] = s->bp; |
s->head3[key] = s->bp; |
262 |
s->best3[s->bp] = SWD_F + 1; |
s->best3[s->bp] = SWD_F + 1; |
263 |
s->llen3[key]++; |
s->llen3[key]++; |
265 |
|
|
266 |
#ifdef HEAD2 |
#ifdef HEAD2 |
267 |
/* add bp into HEAD2 */ |
/* add bp into HEAD2 */ |
268 |
key = HEAD2(s->b,s->bp); |
key = HEAD2(s->b, s->bp); |
269 |
s->head2[key] = s->bp; |
s->head2[key] = s->bp; |
270 |
#endif |
#endif |
271 |
|
|
298 |
|
|
299 |
assert(m_len < s->look); |
assert(m_len < s->look); |
300 |
|
|
301 |
if (p2[m_len - 1] == scan_end1 && |
if (p2[m_len - 1] == scan_end1 |
302 |
p2[m_len] == p1[m_len] && |
&& p2[m_len] == p1[m_len] |
303 |
p2[0] == p1[0] && |
&& p2[0] == p1[0] |
304 |
p2[1] == p1[1]) { |
&& p2[1] == p1[1] |
305 |
|
) { |
306 |
unsigned i; |
unsigned i; |
307 |
assert(lzo_memcmp(bp,&b[node],3) == 0); |
assert(lzo_memcmp(bp, &b[node], 3) == 0); |
308 |
|
|
309 |
p1 += 2; p2 += 2; |
p1 += 2; p2 += 2; |
310 |
do {} while (++p1 < px && *p1 == *++p2); |
do {} while (++p1 < px && *p1 == *++p2); |
311 |
i = p1-bp; |
i = p1-bp; |
312 |
|
|
313 |
assert(lzo_memcmp(bp,&b[node],i) == 0); |
assert(lzo_memcmp(bp, &b[node], i) == 0); |
314 |
|
|
315 |
#if defined(SWD_BEST_OFF) |
#if defined(SWD_BEST_OFF) |
316 |
if (i < SWD_BEST_OFF) { |
if (i < SWD_BEST_OFF) { |
346 |
assert(s->look >= 2); |
assert(s->look >= 2); |
347 |
assert(s->m_len > 0); |
assert(s->m_len > 0); |
348 |
|
|
349 |
key = s->head2[ HEAD2(s->b,s->bp) ]; |
key = s->head2[HEAD2(s->b, s->bp)]; |
350 |
if (key == NIL2) |
if (key == NIL2) |
351 |
return 0; |
return 0; |
352 |
assert(lzo_memcmp(&s->b[s->bp],&s->b[key],2) == 0); |
assert(lzo_memcmp(&s->b[s->bp], &s->b[key], 2) == 0); |
353 |
#if defined(SWD_BEST_OFF) |
#if defined(SWD_BEST_OFF) |
354 |
if (s->best_pos[2] == 0) |
if (s->best_pos[2] == 0) |
355 |
s->best_pos[2] = key + 1; |
s->best_pos[2] = key + 1; |
378 |
|
|
379 |
/* get current head, add bp into HEAD3 */ |
/* get current head, add bp into HEAD3 */ |
380 |
key = HEAD3(s->b,s->bp); |
key = HEAD3(s->b,s->bp); |
381 |
node = s->succ3[s->bp] = s_get_head3(s,key); |
node = s->succ3[s->bp] = s_get_head3(s, key); |
382 |
cnt = s->llen3[key]++; |
cnt = s->llen3[key]++; |
383 |
assert(s->llen3[key] <= SWD_N + SWD_F); |
assert(s->llen3[key] <= SWD_N + SWD_F); |
384 |
if (cnt > s->max_chain) |
if (cnt > s->max_chain) |
397 |
if (swd_search2(s)) |
if (swd_search2(s)) |
398 |
#endif |
#endif |
399 |
if (s->look >= 3) |
if (s->look >= 3) |
400 |
swd_search(s,node,cnt); |
swd_search(s, node, cnt); |
401 |
if (s->m_len > len) |
if (s->m_len > len) |
402 |
s->m_off = swd_pos2off(s,s->m_pos); |
s->m_off = swd_pos2off(s,s->m_pos); |
403 |
s->best3[s->bp] = s->m_len; |
s->best3[s->bp] = s->m_len; |
405 |
#if defined(SWD_BEST_OFF) |
#if defined(SWD_BEST_OFF) |
406 |
if (s->use_best_off) { |
if (s->use_best_off) { |
407 |
int i; |
int i; |
408 |
for (i = 2; i < SWD_BEST_OFF; i++) |
for (i = 2; i < SWD_BEST_OFF; i++) { |
409 |
if (s->best_pos[i] > 0) |
if (s->best_pos[i] > 0) |
410 |
s->best_off[i] = swd_pos2off(s,s->best_pos[i]-1); |
s->best_off[i] = swd_pos2off(s, s->best_pos[i]-1); |
411 |
else |
else |
412 |
s->best_off[i] = 0; |
s->best_off[i] = 0; |
413 |
|
} |
414 |
} |
} |
415 |
#endif |
#endif |
416 |
} |
} |
419 |
|
|
420 |
#ifdef HEAD2 |
#ifdef HEAD2 |
421 |
/* add bp into HEAD2 */ |
/* add bp into HEAD2 */ |
422 |
key = HEAD2(s->b,s->bp); |
key = HEAD2(s->b, s->bp); |
423 |
s->head2[key] = s->bp; |
s->head2[key] = s->bp; |
424 |
#endif |
#endif |
425 |
} |
} |
469 |
s->m_len = 1; |
s->m_len = 1; |
470 |
#ifdef SWD_BEST_OFF |
#ifdef SWD_BEST_OFF |
471 |
if (s->use_best_off) |
if (s->use_best_off) |
472 |
memset(s->best_pos,0,sizeof(s->best_pos)); |
memset(s->best_pos, 0, sizeof(s->best_pos)); |
473 |
#endif |
#endif |
474 |
swd_findbest(s); |
swd_findbest(s); |
475 |
c->m_len = s->m_len; |
c->m_len = s->m_len; |
507 |
assert(op > c->out); |
assert(op > c->out); |
508 |
if (m_len == 2) { |
if (m_len == 2) { |
509 |
assert(m_off <= M1_MAX_OFFSET); |
assert(m_off <= M1_MAX_OFFSET); |
510 |
assert(c->r1_lit > 0); assert(c->r1_lit < 4); |
assert(c->r1_lit > 0); |
511 |
|
assert(c->r1_lit < 4); |
512 |
m_off -= 1; |
m_off -= 1; |
513 |
*op++ = M1_MARKER | ((m_off & 3) << 2); |
*op++ = M1_MARKER | ((m_off & 3) << 2); |
514 |
*op++ = m_off >> 2; |
*op++ = m_off >> 2; |
532 |
else { |
else { |
533 |
m_len -= M3_MAX_LEN; |
m_len -= M3_MAX_LEN; |
534 |
*op++ = M3_MARKER | 0; |
*op++ = M3_MARKER | 0; |
535 |
while (m_len > 255) |
while (m_len > 255) { |
536 |
{ |
m_len -= 255; |
537 |
m_len -= 255; |
*op++ = 0; |
538 |
*op++ = 0; |
} |
|
} |
|
539 |
assert(m_len > 0); |
assert(m_len > 0); |
540 |
*op++ = m_len; |
*op++ = m_len; |
541 |
} |
} |
545 |
unsigned k; |
unsigned k; |
546 |
|
|
547 |
assert(m_len >= 3); |
assert(m_len >= 3); |
548 |
assert(m_off > 0x4000); assert(m_off <= 0xbfff); |
assert(m_off > 0x4000); |
549 |
|
assert(m_off <= 0xbfff); |
550 |
m_off -= 0x4000; |
m_off -= 0x4000; |
551 |
k = (m_off & 0x4000) >> 11; |
k = (m_off & 0x4000) >> 11; |
552 |
if (m_len <= M4_MAX_LEN) |
if (m_len <= M4_MAX_LEN) |
554 |
else { |
else { |
555 |
m_len -= M4_MAX_LEN; |
m_len -= M4_MAX_LEN; |
556 |
*op++ = M4_MARKER | k | 0; |
*op++ = M4_MARKER | k | 0; |
557 |
while (m_len > 255) |
while (m_len > 255) { |
558 |
{ |
m_len -= 255; |
559 |
m_len -= 255; |
*op++ = 0; |
560 |
*op++ = 0; |
} |
|
} |
|
561 |
assert(m_len > 0); |
assert(m_len > 0); |
562 |
*op++ = m_len; |
*op++ = m_len; |
563 |
} |
} |
600 |
{ |
{ |
601 |
if (lit > 0) { |
if (lit > 0) { |
602 |
assert(m_len >= 2); |
assert(m_len >= 2); |
603 |
op = STORE_RUN(c,op,ii,lit); |
op = STORE_RUN(c, op, ii, lit); |
604 |
} else { |
} else { |
605 |
assert(m_len >= 3); |
assert(m_len >= 3); |
606 |
} |
} |
683 |
return; |
return; |
684 |
|
|
685 |
/* M3/M4 -> M2 */ |
/* M3/M4 -> M2 */ |
686 |
if (*m_off > M2_MAX_OFFSET && |
if (*m_off > M2_MAX_OFFSET |
687 |
*m_len >= M2_MIN_LEN + 1 && *m_len <= M2_MAX_LEN + 1 && |
&& *m_len >= M2_MIN_LEN + 1 && *m_len <= M2_MAX_LEN + 1 |
688 |
swd->best_off[*m_len-1] && swd->best_off[*m_len-1] <= M2_MAX_OFFSET) |
&& swd->best_off[*m_len-1] && swd->best_off[*m_len-1] <= M2_MAX_OFFSET |
689 |
{ |
) { |
690 |
*m_len = *m_len - 1; |
*m_len = *m_len - 1; |
691 |
*m_off = swd->best_off[*m_len]; |
*m_off = swd->best_off[*m_len]; |
692 |
return; |
return; |
693 |
} |
} |
694 |
|
|
695 |
/* M4 -> M2 */ |
/* M4 -> M2 */ |
696 |
if (*m_off > M3_MAX_OFFSET && |
if (*m_off > M3_MAX_OFFSET |
697 |
*m_len >= M4_MAX_LEN + 1 && *m_len <= M2_MAX_LEN + 2 && |
&& *m_len >= M4_MAX_LEN + 1 && *m_len <= M2_MAX_LEN + 2 |
698 |
swd->best_off[*m_len-2] && swd->best_off[*m_len-2] <= M2_MAX_OFFSET) |
&& swd->best_off[*m_len-2] && swd->best_off[*m_len-2] <= M2_MAX_OFFSET |
699 |
{ |
) { |
700 |
*m_len = *m_len - 2; |
*m_len = *m_len - 2; |
701 |
*m_off = swd->best_off[*m_len]; |
*m_off = swd->best_off[*m_len]; |
702 |
return; |
return; |
703 |
} |
} |
704 |
/* M4 -> M3 */ |
/* M4 -> M3 */ |
705 |
if (*m_off > M3_MAX_OFFSET && |
if (*m_off > M3_MAX_OFFSET |
706 |
*m_len >= M4_MAX_LEN + 1 && *m_len <= M3_MAX_LEN + 1 && |
&& *m_len >= M4_MAX_LEN + 1 && *m_len <= M3_MAX_LEN + 1 |
707 |
swd->best_off[*m_len-1] && swd->best_off[*m_len-1] <= M3_MAX_OFFSET) |
&& swd->best_off[*m_len-1] && swd->best_off[*m_len-1] <= M3_MAX_OFFSET |
708 |
{ |
) { |
709 |
*m_len = *m_len - 1; |
*m_len = *m_len - 1; |
710 |
*m_off = swd->best_off[*m_len]; |
*m_off = swd->best_off[*m_len]; |
711 |
} |
} |
712 |
} |
} |
713 |
|
|
714 |
#endif |
#endif |
730 |
unsigned lit; |
unsigned lit; |
731 |
unsigned m_len, m_off; |
unsigned m_len, m_off; |
732 |
lzo1x_999_t cc; |
lzo1x_999_t cc; |
733 |
lzo1x_999_t * const c = &cc; |
lzo1x_999_t *const c = &cc; |
734 |
lzo_swd_p const swd = (lzo_swd_p) wrkmem; |
const lzo_swd_p swd = (lzo_swd_p) wrkmem; |
735 |
int r; |
int r; |
736 |
|
|
737 |
c->init = 0; |
c->init = 0; |
768 |
assert(ii + lit == c->bp); |
assert(ii + lit == c->bp); |
769 |
assert(swd->b_char == *(c->bp)); |
assert(swd->b_char == *(c->bp)); |
770 |
|
|
771 |
if ( m_len < 2 || |
if (m_len < 2 |
772 |
(m_len == 2 && (m_off > M1_MAX_OFFSET || lit == 0 || lit >= 4)) || |
|| (m_len == 2 && (m_off > M1_MAX_OFFSET || lit == 0 || lit >= 4)) |
773 |
/* Do not accept this match for compressed-data compatibility |
/* Do not accept this match for compressed-data compatibility |
774 |
* with LZO v1.01 and before |
* with LZO v1.01 and before |
775 |
* [ might be a problem for decompress() and optimize() ] |
* [ might be a problem for decompress() and optimize() ] |
776 |
*/ |
*/ |
777 |
(m_len == 2 && op == out) || |
|| (m_len == 2 && op == out) |
778 |
(op == out && lit == 0)) |
|| (op == out && lit == 0) |
779 |
{ |
) { |
780 |
/* a literal */ |
/* a literal */ |
781 |
m_len = 0; |
m_len = 0; |
782 |
} |
} |
783 |
else if (m_len == M2_MIN_LEN) { |
else if (m_len == M2_MIN_LEN) { |
784 |
/* compression ratio improves if we code a literal in some cases */ |
/* compression ratio improves if we code a literal in some cases */ |
785 |
if (m_off > MX_MAX_OFFSET && lit >= 4) |
if (m_off > MX_MAX_OFFSET && lit >= 4) |
790 |
/* a literal */ |
/* a literal */ |
791 |
lit++; |
lit++; |
792 |
swd->max_chain = max_chain; |
swd->max_chain = max_chain; |
793 |
r = find_match(c,swd,1,0); |
r = find_match(c, swd, 1, 0); |
794 |
assert(r == 0); |
assert(r == 0); |
795 |
continue; |
continue; |
796 |
} |
} |
798 |
/* a match */ |
/* a match */ |
799 |
#if defined(SWD_BEST_OFF) |
#if defined(SWD_BEST_OFF) |
800 |
if (swd->use_best_off) |
if (swd->use_best_off) |
801 |
better_match(swd,&m_len,&m_off); |
better_match(swd, &m_len, &m_off); |
802 |
#endif |
#endif |
803 |
|
|
804 |
/* shall we try a lazy match ? */ |
/* shall we try a lazy match ? */ |
809 |
max_ahead = 0; |
max_ahead = 0; |
810 |
} else { |
} else { |
811 |
/* yes, try a lazy match */ |
/* yes, try a lazy match */ |
812 |
l1 = len_of_coded_match(m_len,m_off,lit); |
l1 = len_of_coded_match(m_len, m_off, lit); |
813 |
assert(l1 > 0); |
assert(l1 > 0); |
814 |
max_ahead = LZO_MIN(2, (unsigned)l1 - 1); |
max_ahead = LZO_MIN(2, (unsigned)l1 - 1); |
815 |
} |
} |
822 |
swd->max_chain = max_chain >> 2; |
swd->max_chain = max_chain >> 2; |
823 |
else |
else |
824 |
swd->max_chain = max_chain; |
swd->max_chain = max_chain; |
825 |
r = find_match(c,swd,1,0); |
r = find_match(c, swd, 1, 0); |
826 |
ahead++; |
ahead++; |
827 |
|
|
828 |
assert(r == 0); |
assert(r == 0); |
835 |
continue; |
continue; |
836 |
#if defined(SWD_BEST_OFF) |
#if defined(SWD_BEST_OFF) |
837 |
if (swd->use_best_off) |
if (swd->use_best_off) |
838 |
better_match(swd,&c->m_len,&c->m_off); |
better_match(swd, &c->m_len, &c->m_off); |
839 |
#endif |
#endif |
840 |
l2 = len_of_coded_match(c->m_len,c->m_off,lit+ahead); |
l2 = len_of_coded_match(c->m_len, c->m_off, lit+ahead); |
841 |
if (l2 < 0) |
if (l2 < 0) |
842 |
continue; |
continue; |
843 |
|
|
844 |
/* compressed-data compatibility [see above] */ |
/* compressed-data compatibility [see above] */ |
845 |
l3 = (op == out) ? -1 : len_of_coded_match(ahead,m_off,lit); |
l3 = (op == out) ? -1 : len_of_coded_match(ahead, m_off, lit); |
846 |
|
|
847 |
lazy_match_min_gain = min_gain(ahead,lit,lit+ahead,l1,l2,l3); |
lazy_match_min_gain = min_gain(ahead, lit, lit+ahead, l1, l2, l3); |
848 |
if (c->m_len >= m_len + lazy_match_min_gain) { |
if (c->m_len >= m_len + lazy_match_min_gain) { |
849 |
if (l3 > 0) { |
if (l3 > 0) { |
850 |
/* code previous run */ |
/* code previous run */ |
851 |
op = code_run(c,op,ii,lit); |
op = code_run(c, op, ii, lit); |
852 |
lit = 0; |
lit = 0; |
853 |
/* code shortened match */ |
/* code shortened match */ |
854 |
op = code_match(c,op,ahead,m_off); |
op = code_match(c, op, ahead, m_off); |
855 |
} else { |
} else { |
856 |
lit += ahead; |
lit += ahead; |
857 |
assert(ii + lit == c->bp); |
assert(ii + lit == c->bp); |
863 |
assert(ii + lit + ahead == c->bp); |
assert(ii + lit + ahead == c->bp); |
864 |
|
|
865 |
/* 1 - code run */ |
/* 1 - code run */ |
866 |
op = code_run(c,op,ii,lit); |
op = code_run(c, op, ii, lit); |
867 |
lit = 0; |
lit = 0; |
868 |
|
|
869 |
/* 2 - code match */ |
/* 2 - code match */ |
870 |
op = code_match(c,op,m_len,m_off); |
op = code_match(c, op, m_len, m_off); |
871 |
swd->max_chain = max_chain; |
swd->max_chain = max_chain; |
872 |
r = find_match(c,swd,m_len,1+ahead); |
r = find_match(c, swd, m_len, 1+ahead); |
873 |
assert(r == 0); |
assert(r == 0); |
874 |
|
|
875 |
lazy_match_done: ; |
lazy_match_done: ; |
877 |
|
|
878 |
/* store final run */ |
/* store final run */ |
879 |
if (lit > 0) |
if (lit > 0) |
880 |
op = STORE_RUN(c,op,ii,lit); |
op = STORE_RUN(c, op, ii, lit); |
881 |
|
|
882 |
#if defined(LZO_EOF_CODE) |
#if defined(LZO_EOF_CODE) |
883 |
*op++ = M4_MARKER | 1; |
*op++ = M4_MARKER | 1; |