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