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