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");
}
}
}