matchAndAddHash

fn matchAndAddHash(c: *Compress, i: usize, h: Hash, gt: u16, max_chain: u16, good_: u16) struct

File

Code

fn matchAndAddHash(c: *Compress, i: usize, h: Hash, gt: u16, max_chain: u16, good_: u16) struct {
    dist: u16,
    len: u16,
} {
    const l = &c.lookup;
    const buffered = c.writer.buffered();

    var chain_limit = max_chain;
    var best_dist: u16 = undefined;
    var best_len = gt;
    const nice = @min(c.opts.nice, buffered[i..].len);
    var good = good_;

    search: {
        if (l.head[h].is_null) break :search;
        // Actually a u15, but LLVM 21 does not optimize that as well (it truncates it each use).
        var dist: u16 = l.chain_pos -% l.head[h].value;
        while (true) {
            chain_limit -= 1;

            const match_len = betterMatchLen(best_len, buffered[i - 1 - dist ..], buffered[i..]);
            if (match_len > best_len) {
                best_dist = dist;
                best_len = match_len;
                if (best_len >= nice) break;
                if (best_len >= good) {
                    chain_limit >>= 2;
                    good = math.maxInt(u8); // Reduce only once
                }
            }

            if (chain_limit == 0) break;
            const next_chain_index = l.chain_pos -% @as(u15, @intCast(dist));
            // Equivilent to the below, however LLVM 21 optimizes the below worse.
            // if (l.chain[next_chain_index].is_null) break;
            // dist, const out_of_window = @addWithOverflow(dist, l.chain[next_chain_index].value);
            // if (out_of_window == 1) break;
            dist +%= l.chain[next_chain_index].int(); // wrapping for potential null bit
            comptime assert(flate.history_len == PackedOptionalU15.int(.null_bit));
            // Also, doing >= flate.history_len gives worse codegen with LLVM 21.
            if ((dist | l.chain[next_chain_index].int()) & flate.history_len != 0) break;
        }
    }

    c.addHash(i, h);
    return .{ .dist = best_dist, .len = best_len };
}