xz/lz/BT4.java

/*
 * Binary Tree match finder with 2-, 3-, and 4-byte hashing
 *
 * Authors: Lasse Collin <lasse.collin (at) tukaani.org>
 *          Igor Pavlov <http://7-zip.org/>
 *
 * This file has been put into the public domain.
 * You can do whatever you want with this file.
 */

package org.tukaani.xz.lz;

final class BT4 extends LZEncoder {
    private final Hash234 hash;
    private final int[] tree;
    private final Matches matches;
    private final int depthLimit;

    private final int cyclicSize;
    private int cyclicPos = -1;
    private int lzPos;

    static int getMemoryUsage(int dictSize) {
        return Hash234.getMemoryUsage(dictSize) + dictSize / (1024 / 8) + 10;
    }

    BT4(int dictSize, int beforeSizeMin, int readAheadMax,
            int niceLen, int matchLenMax, int depthLimit) {
        super(dictSize, beforeSizeMin, readAheadMax, niceLen, matchLenMax);

        cyclicSize = dictSize + 1;
        lzPos = cyclicSize;

        hash = new Hash234(dictSize);
        tree = new int[cyclicSize * 2];

        // Substracting 1 because the shortest match that this match
        // finder can find is 2 bytes, so there's no need to reserve
        // space for one-byte matches.
        matches = new Matches(niceLen - 1);

        this.depthLimit = depthLimit > 0 ? depthLimit : 16 + niceLen / 2;
    }

    private int movePos() {
        int avail = movePos(niceLen, 4);

        if (avail != 0) {
            if (++lzPos == Integer.MAX_VALUE) {
                int normalizationOffset = Integer.MAX_VALUE - cyclicSize;
                hash.normalize(normalizationOffset);
                normalize(tree, normalizationOffset);
                lzPos -= normalizationOffset;
            }

            if (++cyclicPos == cyclicSize)
                cyclicPos = 0;
        }

        return avail;
    }

    public Matches getMatches() {
        matches.count = 0;

        int matchLenLimit = matchLenMax;
        int niceLenLimit = niceLen;
        int avail = movePos();

        if (avail < matchLenLimit) {
            if (avail == 0)
                return matches;

            matchLenLimit = avail;
            if (niceLenLimit > avail)
                niceLenLimit = avail;
        }

        hash.calcHashes(buf, readPos);
        int delta2 = lzPos - hash.getHash2Pos();
        int delta3 = lzPos - hash.getHash3Pos();
        int currentMatch = hash.getHash4Pos();
        hash.updateTables(lzPos);

        int lenBest = 0;

        // See if the hash from the first two bytes found a match.
        // The hashing algorithm guarantees that if the first byte
        // matches, also the second byte does, so there's no need to
        // test the second byte.
        if (delta2 < cyclicSize && buf[readPos - delta2] == buf[readPos]) {
            lenBest = 2;
            matches.len[0] = 2;
            matches.dist[0] = delta2 - 1;
            matches.count = 1;
        }

        // See if the hash from the first three bytes found a match that
        // is different from the match possibly found by the two-byte hash.
        // Also here the hashing algorithm guarantees that if the first byte
        // matches, also the next two bytes do.
        if (delta2 != delta3 && delta3 < cyclicSize
                && buf[readPos - delta3] == buf[readPos]) {
            lenBest = 3;
            matches.dist[matches.count++] = delta3 - 1;
            delta2 = delta3;
        }

        // If a match was found, see how long it is.
        if (matches.count > 0) {
            while (lenBest < matchLenLimit && buf[readPos + lenBest - delta2]
                                              == buf[readPos + lenBest])
                ++lenBest;

            matches.len[matches.count - 1] = lenBest;

            // Return if it is long enough (niceLen or reached the end of
            // the dictionary).
            if (lenBest >= niceLenLimit) {
                skip(niceLenLimit, currentMatch);
                return matches;
            }
        }

        // Long enough match wasn't found so easily. Look for better matches
        // from the binary tree.
        if (lenBest < 3)
            lenBest = 3;

        int depth = depthLimit;

        int ptr0 = (cyclicPos << 1) + 1;
        int ptr1 = cyclicPos << 1;
        int len0 = 0;
        int len1 = 0;

        while (true) {
            int delta = lzPos - currentMatch;

            // Return if the search depth limit has been reached or
            // if the distance of the potential match exceeds the
            // dictionary size.
            if (depth-- == 0 || delta >= cyclicSize) {
                tree[ptr0] = 0;
                tree[ptr1] = 0;
                return matches;
            }

            int pair = (cyclicPos - delta
                        + (delta > cyclicPos ? cyclicSize : 0)) << 1;
            int len = Math.min(len0, len1);

            if (buf[readPos + len - delta] == buf[readPos + len]) {
                while (++len < matchLenLimit)
                    if (buf[readPos + len - delta] != buf[readPos + len])
                        break;

                if (len > lenBest) {
                    lenBest = len;
                    matches.len[matches.count] = len;
                    matches.dist[matches.count] = delta - 1;
                    ++matches.count;

                    if (len >= niceLenLimit) {
                        tree[ptr1] = tree[pair];
                        tree[ptr0] = tree[pair + 1];
                        return matches;
                    }
                }
            }

            if ((buf[readPos + len - delta] & 0xFF)
                    < (buf[readPos + len] & 0xFF)) {
                tree[ptr1] = currentMatch;
                ptr1 = pair + 1;
                currentMatch = tree[ptr1];
                len1 = len;
            } else {
                tree[ptr0] = currentMatch;
                ptr0 = pair;
                currentMatch = tree[ptr0];
                len0 = len;
            }
        }
    }

    private void skip(int niceLenLimit, int currentMatch) {
        int depth = depthLimit;

        int ptr0 = (cyclicPos << 1) + 1;
        int ptr1 = cyclicPos << 1;
        int len0 = 0;
        int len1 = 0;

        while (true) {
            int delta = lzPos - currentMatch;

            if (depth-- == 0 || delta >= cyclicSize) {
                tree[ptr0] = 0;
                tree[ptr1] = 0;
                return;
            }

            int pair = (cyclicPos - delta
                        + (delta > cyclicPos ? cyclicSize : 0)) << 1;
            int len = Math.min(len0, len1);

            if (buf[readPos + len - delta] == buf[readPos + len]) {
                // No need to look for longer matches than niceLenLimit
                // because we only are updating the tree, not returning
                // matches found to the caller.
                do {
                    if (++len == niceLenLimit) {
                        tree[ptr1] = tree[pair];
                        tree[ptr0] = tree[pair + 1];
                        return;
                    }
                } while (buf[readPos + len - delta] == buf[readPos + len]);
            }

            if ((buf[readPos + len - delta] & 0xFF)
                    < (buf[readPos + len] & 0xFF)) {
                tree[ptr1] = currentMatch;
                ptr1 = pair + 1;
                currentMatch = tree[ptr1];
                len1 = len;
            } else {
                tree[ptr0] = currentMatch;
                ptr0 = pair;
                currentMatch = tree[ptr0];
                len0 = len;
            }
        }
    }

    public void skip(int len) {
        while (len-- > 0) {
            int niceLenLimit = niceLen;
            int avail = movePos();

            if (avail < niceLenLimit) {
                if (avail == 0)
                    continue;

                niceLenLimit = avail;
            }

            hash.calcHashes(buf, readPos);
            int currentMatch = hash.getHash4Pos();
            hash.updateTables(lzPos);

            skip(niceLenLimit, currentMatch);
        }
    }
}