• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * LZMAEncoderFast
3  *
4  * Authors: Lasse Collin <lasse.collin@tukaani.org>
5  *          Igor Pavlov <http://7-zip.org/>
6  *
7  * This file has been put into the public domain.
8  * You can do whatever you want with this file.
9  */
10 
11 package org.tukaani.xz.lzma;
12 
13 import org.tukaani.xz.ArrayCache;
14 import org.tukaani.xz.lz.LZEncoder;
15 import org.tukaani.xz.lz.Matches;
16 import org.tukaani.xz.rangecoder.RangeEncoder;
17 
18 final class LZMAEncoderFast extends LZMAEncoder {
19     private static final int EXTRA_SIZE_BEFORE = 1;
20     private static final int EXTRA_SIZE_AFTER = MATCH_LEN_MAX - 1;
21 
22     private Matches matches = null;
23 
getMemoryUsage(int dictSize, int extraSizeBefore, int mf)24     static int getMemoryUsage(int dictSize, int extraSizeBefore, int mf) {
25         return LZEncoder.getMemoryUsage(
26                 dictSize, Math.max(extraSizeBefore, EXTRA_SIZE_BEFORE),
27                 EXTRA_SIZE_AFTER, MATCH_LEN_MAX, mf);
28     }
29 
LZMAEncoderFast(RangeEncoder rc, int lc, int lp, int pb, int dictSize, int extraSizeBefore, int niceLen, int mf, int depthLimit, ArrayCache arrayCache)30     LZMAEncoderFast(RangeEncoder rc, int lc, int lp, int pb,
31                            int dictSize, int extraSizeBefore,
32                            int niceLen, int mf, int depthLimit,
33                            ArrayCache arrayCache) {
34         super(rc, LZEncoder.getInstance(dictSize,
35                                         Math.max(extraSizeBefore,
36                                                  EXTRA_SIZE_BEFORE),
37                                         EXTRA_SIZE_AFTER,
38                                         niceLen, MATCH_LEN_MAX,
39                                         mf, depthLimit, arrayCache),
40               lc, lp, pb, dictSize, niceLen);
41     }
42 
changePair(int smallDist, int bigDist)43     private boolean changePair(int smallDist, int bigDist) {
44         return smallDist < (bigDist >>> 7);
45     }
46 
getNextSymbol()47     int getNextSymbol() {
48         // Get the matches for the next byte unless readAhead indicates
49         // that we already got the new matches during the previous call
50         // to this function.
51         if (readAhead == -1)
52             matches = getMatches();
53 
54         back = -1;
55 
56         // Get the number of bytes available in the dictionary, but
57         // not more than the maximum match length. If there aren't
58         // enough bytes remaining to encode a match at all, return
59         // immediately to encode this byte as a literal.
60         int avail = Math.min(lz.getAvail(), MATCH_LEN_MAX);
61         if (avail < MATCH_LEN_MIN)
62             return 1;
63 
64         // Look for a match from the previous four match distances.
65         int bestRepLen = 0;
66         int bestRepIndex = 0;
67         for (int rep = 0; rep < REPS; ++rep) {
68             int len = lz.getMatchLen(reps[rep], avail);
69             if (len < MATCH_LEN_MIN)
70                 continue;
71 
72             // If it is long enough, return it.
73             if (len >= niceLen) {
74                 back = rep;
75                 skip(len - 1);
76                 return len;
77             }
78 
79             // Remember the index and length of the best repeated match.
80             if (len > bestRepLen) {
81                 bestRepIndex = rep;
82                 bestRepLen = len;
83             }
84         }
85 
86         int mainLen = 0;
87         int mainDist = 0;
88 
89         if (matches.count > 0) {
90             mainLen = matches.len[matches.count - 1];
91             mainDist = matches.dist[matches.count - 1];
92 
93             if (mainLen >= niceLen) {
94                 back = mainDist + REPS;
95                 skip(mainLen - 1);
96                 return mainLen;
97             }
98 
99             while (matches.count > 1
100                     && mainLen == matches.len[matches.count - 2] + 1) {
101                 if (!changePair(matches.dist[matches.count - 2], mainDist))
102                     break;
103 
104                 --matches.count;
105                 mainLen = matches.len[matches.count - 1];
106                 mainDist = matches.dist[matches.count - 1];
107             }
108 
109             if (mainLen == MATCH_LEN_MIN && mainDist >= 0x80)
110                 mainLen = 1;
111         }
112 
113         if (bestRepLen >= MATCH_LEN_MIN) {
114             if (bestRepLen + 1 >= mainLen
115                     || (bestRepLen + 2 >= mainLen && mainDist >= (1 << 9))
116                     || (bestRepLen + 3 >= mainLen && mainDist >= (1 << 15))) {
117                 back = bestRepIndex;
118                 skip(bestRepLen - 1);
119                 return bestRepLen;
120             }
121         }
122 
123         if (mainLen < MATCH_LEN_MIN || avail <= MATCH_LEN_MIN)
124             return 1;
125 
126         // Get the next match. Test if it is better than the current match.
127         // If so, encode the current byte as a literal.
128         matches = getMatches();
129 
130         if (matches.count > 0) {
131             int newLen = matches.len[matches.count - 1];
132             int newDist = matches.dist[matches.count - 1];
133 
134             if ((newLen >= mainLen && newDist < mainDist)
135                     || (newLen == mainLen + 1
136                         && !changePair(mainDist, newDist))
137                     || newLen > mainLen + 1
138                     || (newLen + 1 >= mainLen
139                         && mainLen >= MATCH_LEN_MIN + 1
140                         && changePair(newDist, mainDist)))
141                 return 1;
142         }
143 
144         int limit = Math.max(mainLen - 1, MATCH_LEN_MIN);
145         for (int rep = 0; rep < REPS; ++rep)
146             if (lz.getMatchLen(reps[rep], limit) == limit)
147                 return 1;
148 
149         back = mainDist + REPS;
150         skip(mainLen - 2);
151         return mainLen;
152     }
153 }
154