NBZ.java

package libsidplay.components.c1541;

import java.io.IOException;
import java.io.ByteArrayOutputStream;
import java.io.RandomAccessFile;
import java.nio.charset.StandardCharsets;
import java.util.Arrays;

/** Bounded codec for the Marcus Geelnard LZ77 wire format used by NIBTools. */
public final class NBZ extends NIB {
    public NBZ(GCR gcr, String fileName, RandomAccessFile fd, boolean readOnly) {
        super(gcr, fileName, fd, readOnly);
    }

    @Override
    public Format getFormat() {
        return Format.NBZ;
    }

    static boolean matches(RandomAccessFile input) throws IOException {
        byte[] prefix = new byte[(int) Math.min(input.length(), 256)];
        input.seek(0);
        input.readFully(prefix);
        input.seek(0);
        try {
            byte[] header = decode(prefix, 14, true);
            return header.length == 14 && new String(header, 0, 13, StandardCharsets.US_ASCII).equals(IMAGE_HEADER);
        } catch (IOException invalid) {
            return false;
        }
    }

    @Override
    protected byte[] readImageData() throws IOException {
        if (fd.length() > 2L * MAX_NB2_SIZE + 1) throw new IOException("Oversized NBZ stream");
        byte[] encoded = new byte[(int) fd.length()];
        fd.seek(0);
        fd.readFully(encoded);
        return decode(encoded, MAX_NB2_SIZE, false);
    }

    @Override
    protected byte[] encodeImageData(byte[] image) throws IOException {
        return encode(image);
    }

    /** Greedy LZ77 with a bounded 64 KiB history; tokens follow the original NIBTools codec. */
    static byte[] encode(byte[] plain) throws IOException {
        if (plain.length == 0 || plain.length > MAX_NB2_SIZE) throw new IOException("Unsupported NBZ input size");
        int[] frequencies = new int[256];
        for (byte value : plain) frequencies[value & 255]++;
        int marker = 0;
        for (int i = 1; i < frequencies.length; i++) if (frequencies[i] < frequencies[marker]) marker = i;
        ByteArrayOutputStream output = new ByteArrayOutputStream(Math.min(plain.length, 65536));
        output.write(marker);
        int[] heads = new int[65536], previous = new int[65536];
        Arrays.fill(heads, -1);
        Arrays.fill(previous, -1);
        for (int position = 0; position < plain.length;) {
            int length = 1, distance = 0, candidate = insert(plain, position, heads, previous);
            for (int probes = 0; candidate >= 0 && candidate < position && position - candidate <= 65535 && probes < 32; probes++) {
                int matched = 0;
                while (position + matched < plain.length && plain[candidate + matched] == plain[position + matched]) matched++;
                if (matched > length) {
                    length = matched;
                    distance = position - candidate;
                    if (position + length == plain.length) break;
                }
                int next = previous[candidate & 65535];
                if (next >= candidate) break;
                candidate = next;
            }
            if (length >= 4 && 1 + variableSize(length) + variableSize(distance) < length) {
                output.write(marker);
                variable(output, length);
                variable(output, distance);
                for (int i = 1; i < length; i++) insert(plain, position + i, heads, previous);
                position += length;
            } else {
                int value = plain[position++] & 255;
                output.write(value);
                if (value == marker) output.write(0);
            }
        }
        return output.toByteArray();
    }

    private static int insert(byte[] plain, int position, int[] heads, int[] previous) {
        if (position + 2 >= plain.length) return -1;
        int hash = (((plain[position] & 255) * 251 + (plain[position + 1] & 255)) * 251 + (plain[position + 2] & 255)) & 65535;
        int candidate = heads[hash];
        previous[position & 65535] = candidate;
        heads[hash] = position;
        return candidate;
    }

    private static int variableSize(int value) {
        int count = 1;
        while ((value >>>= 7) != 0) count++;
        return count;
    }

    private static void variable(ByteArrayOutputStream output, int value) {
        for (int shift = (variableSize(value) - 1) * 7; shift >= 0; shift -= 7)
            output.write(((value >>> shift) & 127) | (shift == 0 ? 0 : 128));
    }

    static byte[] decode(byte[] encoded, int limit, boolean prefixOnly) throws IOException {
        if (encoded.length < 2) throw new IOException("Truncated NBZ stream");
        Cursor input = new Cursor(encoded);
        int marker = input.read();
        byte[] output = new byte[Math.min(limit, 8192)];
        int count = 0;
        while (input.position < encoded.length && (!prefixOnly || count < limit)) {
            int symbol = input.read(), length = 1, offset = 0;
            if (symbol == marker) {
                if (input.peek() == 0) {
                    input.read();
                } else {
                    length = input.variable();
                    offset = input.variable();
                    if (length == 0 || offset == 0 || offset > count) throw new IOException("Invalid NBZ back-reference");
                }
            }
            if (prefixOnly) length = Math.min(length, limit - count);
            if (length > limit - count) throw new IOException("NBZ output exceeds supported image size");
            int required = count + length;
            if (required > output.length) output = Arrays.copyOf(output, Math.max(required, Math.min(limit, output.length * 2)));
            for (int i = 0; i < length; i++) {
                byte value = offset == 0 ? (byte) symbol : output[count - offset];
                output[count++] = value;
            }
        }
        return Arrays.copyOf(output, count);
    }

    private static final class Cursor {
        private final byte[] data;
        private int position;

        Cursor(byte[] data) {
            this.data = data;
        }

        int peek() throws IOException {
            if (position == data.length) throw new IOException("Truncated NBZ token");
            return data[position] & 255;
        }

        int read() throws IOException {
            int value = peek();
            position++;
            return value;
        }

        int variable() throws IOException {
            long value = 0;
            for (int i = 0; i < 5; i++) {
                int b = read();
                value = value << 7 | b & 127;
                if (value > Integer.MAX_VALUE) throw new IOException("Oversized NBZ integer");
                if ((b & 128) == 0) return (int) value;
            }
            throw new IOException("Invalid NBZ integer");
        }
    }
}