|
namespace System.IO.Compression {
using System;
using System.Diagnostics;
internal class FastEncoderWindow {
private byte[] window; // complete bytes window
private int bufPos; // the start index of uncompressed bytes
private int bufEnd; // the end index of uncompressed bytes
// Be very careful about increasing the window size; the code tables will have to
// be updated, since they assume that extra_distance_bits is never larger than a
// certain size.
const int FastEncoderHashShift = 4;
const int FastEncoderHashtableSize = 2048;
const int FastEncoderHashMask = FastEncoderHashtableSize-1;
const int FastEncoderWindowSize = 8192;
const int FastEncoderWindowMask = FastEncoderWindowSize - 1;
const int FastEncoderMatch3DistThreshold = 16384;
internal const int MaxMatch = 258;
internal const int MinMatch = 3;
// Following constants affect the search,
// they should be modifiable if we support different compression levels in future.
const int SearchDepth = 32;
const int GoodLength = 4;
const int NiceLength = 32;
const int LazyMatchThreshold = 6;
// Hashtable structure
private ushort[] prev; // next most recent occurance of chars with same hash value
private ushort[] lookup; // hash table to find most recent occurance of chars with same hash value
public FastEncoderWindow() {
ResetWindow();
}
public int BytesAvailable { // uncompressed bytes
get {
Debug.Assert(bufEnd - bufPos >= 0, "Ending pointer can't be in front of starting pointer!");
return bufEnd - bufPos;
}
}
public DeflateInput UnprocessedInput {
get {
DeflateInput input = new DeflateInput();
input.Buffer = window;
input.StartIndex = bufPos;
input.Count = bufEnd - bufPos;
return input;
}
}
public void FlushWindow() {
ResetWindow();
}
private void ResetWindow() {
window = new byte[2 * FastEncoderWindowSize + MaxMatch + 4];
prev = new ushort[FastEncoderWindowSize + MaxMatch];
lookup = new ushort[FastEncoderHashtableSize];
bufPos = FastEncoderWindowSize;
bufEnd = bufPos;
}
public int FreeWindowSpace { // Free space in the window
get {
return 2 * FastEncoderWindowSize - bufEnd;
}
}
// copy bytes from input buffer into window
public void CopyBytes(byte[] inputBuffer, int startIndex, int count) {
Array.Copy(inputBuffer, startIndex, window, bufEnd, count);
bufEnd += count;
}
// slide the history window to the left by FastEncoderWindowSize bytes
public void MoveWindows() {
int i;
Debug.Assert(bufPos == 2*FastEncoderWindowSize, "only call this at the end of the window");
// verify that the hash table is correct
VerifyHashes(); // Debug only code
Array.Copy(window, bufPos - FastEncoderWindowSize, window, 0, FastEncoderWindowSize);
// move all the hash pointers back
for (i = 0; i < FastEncoderHashtableSize; i++) {
int val = ((int) lookup[i]) - FastEncoderWindowSize;
if (val <= 0) { // too far away now? then set to zero
lookup[i] = (ushort) 0;
} else {
lookup[i] = (ushort) val;
}
}
// prev[]'s are absolute pointers, not relative pointers, so we have to move them back too
// making prev[]'s into relative pointers poses problems of its own
for (i = 0; i < FastEncoderWindowSize; i++) {
long val = ((long) prev[i]) - FastEncoderWindowSize;
if (val <= 0) {
prev[i] = (ushort) 0;
} else {
prev[i] = (ushort) val;
}
}
#if DEBUG
// For debugging, wipe the window clean, so that if there is a bug in our hashing,
// the hash pointers will now point to locations which are not valid for the hash value
// (and will be caught by our ASSERTs).
Array.Clear(window, FastEncoderWindowSize, window.Length - FastEncoderWindowSize);
#endif
VerifyHashes(); // debug: verify hash table is correct
bufPos = FastEncoderWindowSize;
bufEnd = bufPos;
}
private uint HashValue(uint hash, byte b) {
return(hash << FastEncoderHashShift) ^ b;
}
// insert string into hash table and return most recent location of same hash value
private uint InsertString(ref uint hash) {
// Note we only use the lowest 11 bits of the hash vallue (hash table size is 11).
// This enables fast calculation of hash value for the input string.
// If we want to get the next hash code starting at next position,
// we can just increment bufPos and call this function.
hash = HashValue( hash, window[bufPos+2] );
// Need to assert the hash value
uint search = lookup[hash & FastEncoderHashMask];
lookup[hash & FastEncoderHashMask] = (ushort) bufPos;
prev[bufPos & FastEncoderWindowMask] = (ushort) search;
return search;
}
//
// insert strings into hashtable
// Arguments:
// hash : intial hash value
// matchLen : 1 + number of strings we need to insert.
//
private void InsertStrings(ref uint hash, int matchLen) {
Debug.Assert(matchLen > 0, "Invalid match Len!");
if (bufEnd - bufPos <= matchLen) {
bufPos += (matchLen-1);
}
else {
while (--matchLen > 0) {
InsertString(ref hash);
bufPos++;
}
}
}
//
// Find out what we should generate next. It can be a symbol, a distance/length pair
// or a symbol followed by distance/length pair
//
internal bool GetNextSymbolOrMatch(Match match) {
Debug.Assert(bufPos >= FastEncoderWindowSize && bufPos < (2*FastEncoderWindowSize), "Invalid Buffer Position!");
// initialise the value of the hash, no problem if locations bufPos, bufPos+1
// are invalid (not enough data), since we will never insert using that hash value
uint hash = HashValue( 0 , window[bufPos]);
hash = HashValue( hash , window[bufPos + 1]);
int matchLen;
int matchPos = 0;
VerifyHashes(); // Debug only code
if (bufEnd - bufPos <= 3) {
// The hash value becomes corrupt when we get within 3 characters of the end of the
// input window, since the hash value is based on 3 characters. We just stop
// inserting into the hash table at this point, and allow no matches.
matchLen = 0;
}
else {
// insert string into hash table and return most recent location of same hash value
int search = (int)InsertString(ref hash);
// did we find a recent location of this hash value?
if (search != 0) {
// yes, now find a match at what we'll call position X
matchLen = FindMatch(search, out matchPos, SearchDepth, NiceLength);
// truncate match if we're too close to the end of the input window
if (bufPos + matchLen > bufEnd)
matchLen = bufEnd - bufPos;
}
else {
// no most recent location found
matchLen = 0;
}
}
if (matchLen < MinMatch) {
// didn't find a match, so output unmatched char
match.State = MatchState.HasSymbol;
match.Symbol = window[bufPos];
bufPos++;
}
else {
// bufPos now points to X+1
bufPos++;
// is this match so good (long) that we should take it automatically without
// checking X+1 ?
if (matchLen <= LazyMatchThreshold) {
int nextMatchLen;
int nextMatchPos = 0;
// search at position X+1
int search = (int)InsertString(ref hash);
// no, so check for a better match at X+1
if (search != 0) {
nextMatchLen = FindMatch(search, out nextMatchPos,
matchLen < GoodLength ? SearchDepth : (SearchDepth >> 2),NiceLength);
// truncate match if we're too close to the end of the window
// note: nextMatchLen could now be < MinMatch
if (bufPos + nextMatchLen > bufEnd) {
nextMatchLen = bufEnd - bufPos;
}
} else {
nextMatchLen = 0;
}
// right now X and X+1 are both inserted into the search tree
if (nextMatchLen > matchLen) {
// since nextMatchLen > matchLen, it can't be < MinMatch here
// match at X+1 is better, so output unmatched char at X
match.State = MatchState.HasSymbolAndMatch;
match.Symbol = window[bufPos-1];
match.Position = nextMatchPos;
match.Length = nextMatchLen;
// insert remainder of second match into search tree
// example: (*=inserted already)
//
// X X+1 X+2 X+3 X+4
// * *
// nextmatchlen=3
// bufPos
//
// If nextMatchLen == 3, we want to perform 2
// insertions (at X+2 and X+3). However, first we must
// inc bufPos.
//
bufPos++; // now points to X+2
matchLen = nextMatchLen;
InsertStrings(ref hash, matchLen);
} else {
// match at X is better, so take it
match.State = MatchState.HasMatch;
match.Position = matchPos;
match.Length = matchLen;
// Insert remainder of first match into search tree, minus the first
// two locations, which were inserted by the FindMatch() calls.
//
// For example, if matchLen == 3, then we've inserted at X and X+1
// already (and bufPos is now pointing at X+1), and now we need to insert
// only at X+2.
//
matchLen--;
bufPos++; // now bufPos points to X+2
InsertStrings(ref hash, matchLen);
}
} else { // match_length >= good_match
// in assertion: bufPos points to X+1, location X inserted already
// first match is so good that we're not even going to check at X+1
match.State = MatchState.HasMatch;
match.Position = matchPos;
match.Length = matchLen;
// insert remainder of match at X into search tree
InsertStrings(ref hash, matchLen);
}
}
if (bufPos == 2*FastEncoderWindowSize) {
MoveWindows();
}
return true;
}
//
// Find a match starting at specified position and return length of match
// Arguments:
// search : where to start searching
// matchPos : return match position here
// searchDepth : # links to traverse
// NiceLength : stop immediately if we find a match >= NiceLength
//
int FindMatch(int search, out int matchPos, int searchDepth, int niceLength ) {
Debug.Assert(bufPos >= 0 && bufPos < 2*FastEncoderWindowSize, "Invalid Buffer position!");
Debug.Assert(search < bufPos, "Invalid starting search point!");
Debug.Assert(RecalculateHash((int)search) == RecalculateHash(bufPos));
int bestMatch = 0; // best match length found so far
int bestMatchPos = 0; // absolute match position of best match found
// the earliest we can look
int earliest = bufPos - FastEncoderWindowSize;
Debug.Assert(earliest >= 0, "bufPos is less than FastEncoderWindowSize!");
byte wantChar = window[bufPos];
while (search > earliest) {
// make sure all our hash links are valid
Debug.Assert(RecalculateHash((int)search) == RecalculateHash(bufPos), "Corrupted hash link!");
// Start by checking the character that would allow us to increase the match
// length by one. This improves performance quite a bit.
if (window[search + bestMatch] == wantChar) {
int j;
// Now make sure that all the other characters are correct
for (j = 0; j < MaxMatch; j++) {
if (window[bufPos+j] != window[search+j])
break;
}
if (j > bestMatch) {
bestMatch = j;
bestMatchPos = search; // absolute position
if (j > NiceLength) break;
wantChar = window[bufPos+j];
}
}
if (--searchDepth == 0) {
break;
}
Debug.Assert(prev[search & FastEncoderWindowMask] < search, "we should always go backwards!");
search = prev[search & FastEncoderWindowMask];
}
// doesn't necessarily mean we found a match; bestMatch could be > 0 and < MinMatch
matchPos = bufPos - bestMatchPos - 1; // convert absolute to relative position
// don't allow match length 3's which are too far away to be worthwhile
if (bestMatch == 3 && matchPos >= FastEncoderMatch3DistThreshold) {
return 0;
}
Debug.Assert(bestMatch < MinMatch || matchPos < FastEncoderWindowSize, "Only find match inside FastEncoderWindowSize");
return bestMatch;
}
[Conditional("DEBUG")]
void VerifyHashes() {
for (int i = 0; i < FastEncoderHashtableSize; i++) {
ushort where = lookup[i];
ushort nextWhere;
while (where != 0 && bufPos - where < FastEncoderWindowSize) {
Debug.Assert(RecalculateHash(where) == i, "Incorrect Hashcode!");
nextWhere = prev[where & FastEncoderWindowMask];
if (bufPos - nextWhere >= FastEncoderWindowSize) {
break;
}
Debug.Assert(nextWhere < where, "pointer is messed up!");
where = nextWhere;
}
}
}
// can't use conditional attribute here.
uint RecalculateHash(int position) {
return (uint)(((window[position] << (2*FastEncoderHashShift)) ^
(window[position+1] << FastEncoderHashShift) ^
(window[position+2])) & FastEncoderHashMask);
}
}
}
|