001package org.anarres.lzo;
002
003import java.util.Arrays;
004
005class Lzo1x999T {
006    int bp;
007    int ip;
008    int in_end;
009    int out_base;
010
011    int look;
012    int m_len;
013    int m_off;
014    int r1_lit;
015}
016
017class Lzo1x999SWD {
018
019    final byte[] b = new byte[0xCFFF];
020
021    final int[] best_off = new int[34];
022    final int[] best_pos = new int[34];
023    final int[] head3 = new int[0x4000];
024    final int[] succ3 = new int[0xC7FF];
025    final int[] best3 = new int[0xC7FF];
026    final int[] llen3 = new int[0x4000];
027    final int[] head2 = new int[0x10000];
028
029    boolean use_best_off;
030    boolean b_char;
031
032    static final int b_size = 0xC7FF;
033
034    int max_chain;
035    int m_len;
036    int look;
037    int m_off;
038    int m_pos;
039    int ip;
040    int bp;
041    int rp;
042    int node_count;
043}
044
045public class LzoCompressor1x_999 extends AbstractLzo1Compressor {
046
047    private int compression_level;
048
049    public LzoCompressor1x_999(int level) {
050        super(LzoAlgorithm.LZO1X, LzoConstraint.COMPRESSION);
051        if (level > 0 && level < 10)
052            compression_level = level - 1;
053        else
054            throw new IllegalArgumentException("compression level must be between 1 and 9");
055    }
056
057    private static int code_match(Lzo1x999T c, byte[] out, int op, int m_len, int m_off) {
058
059        if (m_len == 2) {
060            m_off -= 1;
061            out[op++] = (byte) ((m_off & 3) << 2);
062            out[op++] = (byte) (m_off >> 2);
063        } else if (m_len <= 8 && m_off <= 0x0800) {
064            m_off -= 1;
065            out[op++] = (byte) (((m_len - 1) << 5) | ((m_off & 7) << 2));
066            out[op++] = (byte) (m_off >> 3);
067        } else if (m_len == 3 && m_off <= 0x0C00 && c.r1_lit >= 4) {
068            m_off -= 0x0801;
069            out[op++] = (byte) ((m_off & 3) << 2);
070            out[op++] = (byte) (m_off >> 2);
071        } else if (m_off <= 0x4000) {
072            m_off -= 1;
073            if (m_len <= 33)
074                out[op++] = (byte) (32 | (m_len - 2));
075            else {
076                m_len -= 33;
077                out[op++] = 32;
078                while (m_len > 255) {
079                    m_len -= 255;
080                    out[op++] = 0;
081                }
082
083                out[op++] = (byte) m_len;
084            }
085            out[op++] = (byte) (m_off << 2);
086            out[op++] = (byte) (m_off >> 6);
087        } else {
088            m_off -= 0x4000;
089            int k = (m_off & 0x4000) >> 11;
090            if (m_len <= 9)
091                out[op++] = (byte) (16 | k | (m_len - 2));
092            else {
093                m_len -= 9;
094                out[op++] = (byte) (16 | k);
095                while (m_len > 255) {
096                    m_len -= 255;
097                    out[op++] = 0;
098                }
099                out[op++] = (byte) m_len;
100            }
101            out[op++] = (byte) (m_off << 2);
102            out[op++] = (byte) (m_off >> 6);
103        }
104
105        return op;
106    }
107
108    private static int store_run(Lzo1x999T c, byte[] in, byte[] out, int op, lzo_uintp ii, int t) {
109
110        if (op == c.out_base && t <= 238)
111            out[op++] = (byte) (17 + t);
112        else if (t <= 3)
113            out[op - 2] |= (byte) t;
114        else if (t <= 18)
115            out[op++] = (byte) (t - 3);
116        else {
117            int tt = t - 18;
118            out[op++] = 0;
119            while (tt > 255) {
120                tt -= 255;
121                out[op++] = 0;
122            }
123            out[op++] = (byte) tt;
124        }
125        do out[op++] = in[ii.value++]; while (--t > 0);
126
127        return op;
128    }
129
130    private static int code_run(Lzo1x999T c, byte[] in, byte[] out, int op, lzo_uintp ii, int lit) {
131        if (lit > 0) {
132            op = store_run(c, in, out, op, ii, lit);
133            c.r1_lit = lit;
134        } else
135            c.r1_lit = 0;
136        return op;
137    }
138
139    private static int min_gain(int ahead, int lit1, int lit2, int l1, int l2, int l3) {
140        int lazy_match_min_gain = ahead;
141
142        if (lit1 <= 3)
143            lazy_match_min_gain += (lit2 <= 3) ? 0 : 2;
144        else if (lit1 <= 18)
145            lazy_match_min_gain += (lit2 <= 18) ? 0 : 1;
146
147        lazy_match_min_gain += (l2 - l1) * 2;
148
149        if (l3 != 0)
150            lazy_match_min_gain -= (ahead - l3) * 2;
151
152        if (lazy_match_min_gain < 0)
153            lazy_match_min_gain = 0;
154
155        return lazy_match_min_gain;
156    }
157
158    private static int len_of_coded_match(int m_len, int m_off, int lit) {
159        int n = 4;
160
161        if (m_len < 2)
162            return 0;
163        if (m_len == 2)
164            return (m_off <= 0x0400 && lit > 0 && lit < 4) ? 2 : 0;
165        if (m_len <= 8 && m_off <= 0x0800)
166            return 2;
167        if (m_len == 3 && m_off <= (0x0400 + 0x0800) && lit >= 4)
168            return 2;
169        if (m_off <= 0x4000) {
170            if (m_len <= 33)
171                return 3;
172            m_len -= 33;
173            while (m_len > 255) {
174                m_len -= 255;
175                n++;
176            }
177            return n;
178        }
179        if (m_off <= 0xBFFF) {
180            if (m_len <= 9)
181                return 3;
182            m_len -= 9;
183            while (m_len > 255) {
184                m_len -= 255;
185                n++;
186            }
187            return n;
188        }
189        return 0;
190    }
191
192    private static void better_match(Lzo1x999SWD swd, lzo_uintp m_len, lzo_uintp m_off) {
193
194        if (m_len.value <= 3)
195            return;
196        if (m_off.value <= 0x0800)
197            return;
198
199        if (m_off.value > 0x0800 &&
200                m_len.value >= 4 && m_len.value <= 9 &&
201                swd.best_off[m_len.value - 1] != 0 && swd.best_off[m_len.value - 1] <= 0x0800) {
202            m_len.value = m_len.value - 1;
203            m_off.value = swd.best_off[m_len.value];
204            return;
205        }
206
207        if (m_off.value > 0x4000 &&
208                m_len.value == 10 &&
209                swd.best_off[m_len.value - 2] != 0 && swd.best_off[m_len.value - 2] <= 0x0800) {
210            m_len.value = m_len.value - 2;
211            m_off.value = swd.best_off[m_len.value];
212            return;
213        }
214
215        if (m_off.value > 0x4000 &&
216                m_len.value >= 10 && m_len.value <= 34 &&
217                swd.best_off[m_len.value - 1] != 0 && swd.best_off[m_len.value - 1] <= 0x4000) {
218            m_len.value = m_len.value - 1;
219            m_off.value = swd.best_off[m_len.value];
220        }
221    }
222
223    private static void swd_search(Lzo1x999SWD s, int node, int cnt) {
224        int p1;
225        int p2;
226        int m_len = s.m_len;
227        int bp = s.bp;
228        int bx = s.bp + s.look;
229        byte scan_end1 = s.b[s.bp + m_len - 1];
230
231        for (; cnt-- > 0; node = s.succ3[node]) {
232            p1 = bp;
233            p2 = node;
234
235            if (s.b[p2 + m_len - 1] == scan_end1 &&
236                    s.b[p2 + m_len] == s.b[p1 + m_len] &&
237                    s.b[p2] == s.b[p1] &&
238                    s.b[p2 + 1] == s.b[p1 + 1]) {
239
240                p1 += 2;
241                p2 += 2;
242                do {
243                } while (++p1 < bx && s.b[p1] == s.b[++p2]);
244
245                int i = p1 - bp;
246
247                if (i < 34) {
248                    if (s.best_pos[i] == 0)
249                        s.best_pos[i] = node + 1;
250                }
251
252                if (i > m_len) {
253                    s.m_len = m_len = i;
254                    s.m_pos = node;
255
256                    if (m_len == s.look || m_len >= 0x800 || m_len > s.best3[node])
257                        return;
258                    scan_end1 = s.b[bp + m_len - 1];
259                }
260            }
261        }
262    }
263
264    private static boolean swd_search2(Lzo1x999SWD s) {
265
266        int key = s.head2[(s.b[s.bp] & 0xFF) + ((s.b[s.bp + 1] & 0xFF) << 8)];
267        if (key == 0xFFFF)
268            return false;
269
270        if (s.best_pos[2] == 0)
271            s.best_pos[2] = key + 1;
272
273        if (s.m_len < 2) {
274            s.m_len = 2;
275            s.m_pos = key;
276        }
277        return true;
278    }
279
280    private static void swd_findbest(Lzo1x999SWD s) {
281
282        int key = ((0x9F5F * ((((s.b[s.bp] << 5) ^ s.b[s.bp + 1]) << 5) ^ s.b[s.bp + 2])) >> 5) & 0x3FFF;
283
284        int node = s.succ3[s.bp] = s.head3[key];
285        int cnt = s.llen3[key]++;
286
287        if (cnt > s.max_chain && s.max_chain > 0)
288            cnt = s.max_chain;
289        s.head3[key] = s.bp;
290
291        s.b_char = true;
292        int len = s.m_len;
293        if (s.m_len >= s.look) {
294            if (s.look == 0)
295                s.b_char = false;
296            s.best3[s.bp] = 0x801;
297        } else {
298            if (swd_search2(s) && s.look >= 3)
299                swd_search(s, node, cnt);
300
301            if (s.m_len > len)
302                s.m_off = (s.bp > s.m_pos ? s.bp - s.m_pos : Lzo1x999SWD.b_size - (s.m_pos - s.bp));
303            s.best3[s.bp] = s.m_len;
304
305            if (s.use_best_off) {
306                for (int i = 2; i < 34; i++)
307                    if (s.best_pos[i] > 0)
308                        s.best_off[i] = (s.bp > (s.best_pos[i] - 1) ? s.bp - (s.best_pos[i] - 1) : Lzo1x999SWD.b_size - ((s.best_pos[i] - 1) - s.bp));
309                    else
310                        s.best_off[i] = 0;
311            }
312        }
313        swd_remove_node(s, s.rp);
314
315        s.head2[(s.b[s.bp] & 0xFF) + ((s.b[s.bp + 1] & 0xFF) << 8)] = s.bp;
316    }
317
318    private static void swd_getbyte(Lzo1x999T c, Lzo1x999SWD s, byte[] in) {
319        int c1 = c.ip < c.in_end ? (in[c.ip++] & 0xFF) : -1;
320
321        if (c1 < 0) {
322            if (s.look > 0)
323                --s.look;
324        } else
325            s.b[s.ip] = (byte) c1;
326
327        if (++s.ip == Lzo1x999SWD.b_size)
328            s.ip = 0;
329        if (++s.bp == Lzo1x999SWD.b_size)
330            s.bp = 0;
331        if (++s.rp == Lzo1x999SWD.b_size)
332            s.rp = 0;
333    }
334
335    private static void swd_remove_node(Lzo1x999SWD s, int node) {
336        if (s.node_count == 0) {
337            int key = ((0x9F5F * ((((s.b[node] << 5) ^ s.b[node + 1]) << 5) ^ s.b[node + 2])) >> 5) & 0x3FFF;
338            --s.llen3[key];
339
340            key = (s.b[node] & 0xFF) + ((s.b[node + 1] & 0xFF) << 8);
341            if (s.head2[key] == node)
342                s.head2[key] = 0xFFFF;
343        } else
344            s.node_count--;
345    }
346
347    private static void swd_accept(Lzo1x999T c, Lzo1x999SWD s, byte[] in, int n) {
348        int key;
349        if (n > 0)
350            do {
351                swd_remove_node(s, s.rp);
352
353                key = ((0x9F5F * (((((s.b[s.bp] << 5) ^ s.b[s.bp + 1]) << 5) ^ s.b[s.bp + 2]))) >> 5) & 0x3FFF;
354
355                s.succ3[s.bp] = s.head3[key];
356                s.head3[key] = s.bp;
357                s.best3[s.bp] = 0x801;
358                s.llen3[key]++;
359                s.head2[(s.b[s.bp] & 0xFF) + ((s.b[s.bp + 1] & 0xFF) << 8)] = s.bp;
360
361                swd_getbyte(c, s, in);
362            } while (--n != 0);
363    }
364
365    private static void find_match(Lzo1x999T c, Lzo1x999SWD s, byte[] in, int this_len, int skip) {
366
367        if (skip > 0)
368            swd_accept(c, s, in, this_len - skip);
369
370        s.m_len = 1;
371        s.m_off = 0;
372
373        if (s.use_best_off)
374            Arrays.fill(s.best_pos, 0);
375
376        swd_findbest(s);
377
378        c.m_len = s.m_len;
379        c.m_off = s.m_off;
380
381        swd_getbyte(c, s, in);
382
383        if (!s.b_char) {
384            c.look = 0;
385            c.m_len = 0;
386        } else
387            c.look = s.look + 1;
388
389        c.bp = c.ip - c.look;
390    }
391
392    private static void swd_init(Lzo1x999T c, Lzo1x999SWD s, byte[] in) {
393
394        s.m_len = 0;
395        s.m_off = 0;
396
397        s.max_chain = 0x800;
398
399        s.use_best_off = false;
400
401        s.node_count = 0xBFFF;
402
403        Arrays.fill(s.head2, 0xFFFF);
404
405        s.rp = s.bp = s.ip = 0;
406
407        s.look = c.in_end - c.ip;
408        if (s.look > 0) {
409            if (s.look > 0x800)
410                s.look = 0x800;
411            System.arraycopy(in, c.ip, s.b, s.ip, s.look);
412            c.ip += s.look;
413            s.ip += s.look;
414        }
415        if (s.ip == Lzo1x999SWD.b_size)
416            s.ip = 0;
417
418        if (s.rp >= s.node_count)
419            s.rp -= s.node_count;
420        else
421            s.rp += Lzo1x999SWD.b_size - s.node_count;
422
423        if (s.look < 3) {
424            s.b[s.bp + s.look] = 0;
425            s.b[s.bp + s.look + 1] = 0;
426            s.b[s.bp + s.look + 2] = 0;
427        }
428    }
429
430    private static void compress_internal(byte[] in, int in_base, int in_len,
431                                          byte[] out, int out_base, lzo_uintp out_len,
432                                          int try_lazy_parm,
433                                          int good_length,
434                                          int max_lazy,
435                                          int max_chain,
436                                          int flags) {
437        int try_lazy = try_lazy_parm;
438        if (try_lazy_parm < 0)
439            try_lazy = 1;
440
441        if (good_length == 0)
442            good_length = 32;
443
444        if (max_lazy == 0)
445            max_lazy = 32;
446
447        if (max_chain == 0)
448            max_chain = 2048;
449
450        Lzo1x999T c = new Lzo1x999T();
451        Lzo1x999SWD swd = new Lzo1x999SWD();
452
453        c.ip = in_base;
454        c.in_end = in_base + in_len;
455
456        int op = c.out_base = out_base;
457
458        lzo_uintp ii = new lzo_uintp(c.ip);
459
460        int lit = c.r1_lit = 0;
461
462        swd_init(c, swd, in);
463        swd.use_best_off = (flags == 1);
464
465        if (max_chain > 0)
466            swd.max_chain = max_chain;
467
468        find_match(c, swd, in, 0, 0);
469
470        int m_len, m_off;
471
472        while (c.look > 0) {
473
474            int ahead;
475            int max_ahead;
476            int l1, l2, l3;
477
478            m_len = c.m_len;
479            m_off = c.m_off;
480
481            if (lit == 0)
482                ii.value = c.bp;
483
484            if (m_len < 2 ||
485                    (m_len == 2 && (m_off > 0x0400 || lit == 0 || lit >= 4)) ||
486                    (m_len == 2 && op == out_base) ||
487                    (op == out_base && lit == 0)) {
488                m_len = 0;
489            } else if (m_len == 3) {
490                if (m_off > (0x0400 + 0x0800) && lit >= 4)
491                    m_len = 0;
492            }
493
494            if (m_len == 0) {
495                lit++;
496                swd.max_chain = max_chain;
497                find_match(c, swd, in, 1, 0);
498                continue;
499            }
500
501            if (swd.use_best_off) {
502                lzo_uintp m_len_p = new lzo_uintp(m_len);
503                lzo_uintp m_off_p = new lzo_uintp(m_off);
504                better_match(swd, m_len_p, m_off_p);
505                m_len = m_len_p.value;
506                m_off = m_off_p.value;
507            }
508
509            ahead = 0;
510            if (try_lazy == 0 || m_len >= max_lazy) {
511                l1 = 0;
512                max_ahead = 0;
513            } else {
514                l1 = len_of_coded_match(m_len, m_off, lit);
515                max_ahead = (try_lazy <= (l1 - 1) ? try_lazy : (l1 - 1));
516            }
517
518            boolean lazy_match_done = false;
519
520            while (!lazy_match_done && ahead < max_ahead && c.look > m_len) {
521                if (m_len >= good_length)
522                    swd.max_chain = max_chain >> 2;
523                else
524                    swd.max_chain = max_chain;
525                find_match(c, swd, in, 1, 0);
526                ahead++;
527
528                if (c.m_len < m_len)
529                    continue;
530
531                if (c.m_len == m_len && c.m_off >= m_off)
532                    continue;
533
534                if (swd.use_best_off) {
535                    lzo_uintp m_len_p = new lzo_uintp(c.m_len);
536                    lzo_uintp m_off_p = new lzo_uintp(c.m_off);
537                    better_match(swd, m_len_p, m_off_p);
538                    c.m_len = m_len_p.value;
539                    c.m_off = m_off_p.value;
540                }
541
542                l2 = len_of_coded_match(c.m_len, c.m_off, lit + ahead);
543                if (l2 == 0)
544                    continue;
545                l3 = (op == out_base) ? 0 : len_of_coded_match(ahead, m_off, lit);
546
547                int lazy_match_min_gain = min_gain(ahead, lit, lit + ahead, l1, l2, l3);
548                if (c.m_len >= m_len + lazy_match_min_gain) {
549                    if (l3 != 0) {
550                        op = code_run(c, in, out, op, ii, lit);
551                        lit = 0;
552                        op = code_match(c, out, op, ahead, m_off);
553                    } else
554                        lit += ahead;
555                    lazy_match_done = true;
556                }
557            }
558            if (!lazy_match_done) {
559                op = code_run(c, in, out, op, ii, lit);
560                lit = 0;
561                op = code_match(c, out, op, m_len, m_off);
562                swd.max_chain = max_chain;
563                find_match(c, swd, in, m_len, 1 + ahead);
564            }
565        }
566
567        if (lit > 0)
568            op = store_run(c, in, out, op, ii, lit);
569
570        out[op++] = 17;
571        out[op++] = 0;
572        out[op++] = 0;
573
574        out_len.value = op - out_base;
575    }
576
577    public int getCompressionLevel() {
578        return compression_level + 1;
579    }
580
581    @Override 
582    public String toString() {
583        return "LZO1X999-" + getCompressionLevel();
584    }
585
586    public int compress(byte[] in, int in_base, int in_len,
587                        byte[] out, int out_base, lzo_uintp out_len) {
588        int[] try_lazy_parm = {0, 0, 0, 1, 1, 1, 2, 2, 2};
589        int[] good_length = {0, 0, 0, 4, 8, 8, 8, 32, 2048};
590        int[] max_lazy = {0, 0, 0, 4, 16, 16, 32, 128, 2048};
591        int[] max_chain = {4, 8, 16, 16, 32, 128, 256, 2048, 4096};
592        int[] flags = {0, 0, 0, 0, 0, 0, 0, 1, 1};
593
594        compress_internal(in, in_base, in_len,
595                out, out_base, out_len,
596                try_lazy_parm[compression_level],
597                good_length[compression_level],
598                max_lazy[compression_level],
599                max_chain[compression_level],
600                flags[compression_level]
601        );
602        return 0;
603    }
604}