Jazz Jackrabbit RLE compression
Jump to navigation
Jump to search
Jazz Jackrabbit RLE compression
| Format type | Compression algorithm |
|---|---|
| Type | Stream |
| I/O unit size | 1-byte |
| Games |
Jazz Jackrabbit heavily uses RLE Compression, or Run Length Encoding.
Format
The Jazz Jackrabbit RLE compression is a Code-based RLE, with the highest bit in the code byte indicating a Repeat-command, and the amount stored in the remaining seven bits. The format differs from the standard implementation only in that a 0-byte, which would technically indicate copying 0 additional bytes, instead copies a single byte and then ends the decompression. This is the expected way for all compressed data to end.
The compressed data is always preceded by an UINT16LE indicating the data length. This is the length of the actual compressed block that follows, so it does not include these two preceding bytes. Very often, the full uncompressed size is also given, by the file format that contains the compressed data. If it is not given, using a buffer of 0xFFFF should probably be enough for any decompression, and the position of the write pointer at the end of the decompression can tell you the final size.
Decompression
The full decompression process:
- Create a Buffer, either of the known uncompressed length, or length 0xFFFF.
- Read two bytes, and interpret them as UINT16LE. This value, plus the current ReadPointer (after reading the value) indicates the ReadEnd point of the compressed data.
- While ReadPointer < ReadEnd (or WritePointer >= BufferSize):
- Read one byte as Code. If the highest bit in the byte is 1, this is a Repeat command. Otherwise, it is a Copy command. The Amount is found from the remaining seven bits;
Amount = Code & 0x7F - In case of a Repeat command:
- Read one byte as Value.
- Fill the Buffer with Amount bytes of Value.
- Else, if it is a Copy command:
- If Amount is 0, read one byte, put it in the Buffer, and end the decompression.
- Else, read Amount bytes and put them in the Buffer.
- Read one byte as Code. If the highest bit in the byte is 1, this is a Repeat command. Otherwise, it is a Copy command. The Amount is found from the remaining seven bits;
If a 0-byte ended the decompression, the ReadPointer may not match the ReadEnd (though normally it should), so make sure any further data reading will be based on the ReadEnd derived from the compressed length header.
If a Repeat command with Value 0 is found (so, Code 0x80), this always means there is an error in the compressed data. In-game, a 0-repeat will end the compression just like a 0-copy, but will often paint a random-coloured pixel behind it before ending, clearly showing that it was not intended to be used.
Source code
The following is code that will decompress\compress raw data into the Jazz RLE format.
QuickBasic
' NOTE: It is assumed that the data x0 has been read from a file. Also, this code stops
' decompressing at cntrlbyte = 0, not at the end of the block. (These should be the same.)
' Decompress RLE data x0 to the string y0
SUB RLEDO
y0 = "" ' Clear y0 for output
FOR i = 1 TO LEN(x0) STEP 2 ' Move byte + cntrlbyte each loop
c = ASC(MID$(x0, i, 1)) ' Get the control byte
SELECT CASE c
CASE 0
y0 = y0 + MID$(x0, i + 1, 1) ' Add next byte to output
EXIT SUB ' And stop decompressing
CASE 1 TO 128
y0 = y0 + MID$(x0, i + 1, c) ' Copy next c bytes to output
i = i + c - 1 ' Move over copied bytes
CASE 129 TO 255
y0 = y0 + STRING$(c - 128, MID$(x0, i + 1, 1)) 'Copy a string of next byte c - 128 bytes long to output
END SELECT
NEXT i
END SUB
Java code
import java.util.LinkedList;
import java.io.IOException;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.File;
/*
* RLE file reader. This class is based on FileInputStream and can be used to
* read and decompress parts of files that are RLE compressed. The focus of this
* decompressing mechanism is put on Jazz1 style compression.
*
* Please note that there is plenty of room for improvement here.
*/
public class RLEFileReader extends FileInputStream {
/*
* Constructor that can be used to open a file that already has a file object.
* @param f File object.
* @throws FileNotFoundException
*/
public RLEFileReader(File f) throws FileNotFoundException {
super(f);
}
/*
* Constructor that can be used to open a file by just giving it's path
* as the first parameter.
* @param s Path to the file containing RLE compression
* @throws FileNotFoundException
*/
public RLEFileReader(String s) throws FileNotFoundException {
super(s);
}
/*
* Decompress a block of RLE data.
* @return Linked list containing all bytes that were read.
* @throws IOException
*/
private LinkedList<Byte> decompressBlock() throws IOException {
// Determine the size of the RLE block
int size = read() | read() << 8;
// Make sure the block isn't too small, or if it even was a block at all.
if (size <= 0)
return null;
// Read the compressed size of the block in bytes
byte[] compressed = new byte[size];
read(compressed);
// Data buffer
LinkedList<Byte> data = new LinkedList<Byte>();
// Number of bytes read so far
int index = 0;
while (index < compressed.length) {
if ((compressed[index] & 0xff) > 128) {
// Repeat the next byte X times
for (int i = 0; i < (compressed[index] & 0xff) - 128; i++)
data.add(compressed[index + 1]);
index++;
}
else if ((compressed[index]) == 0) {
// Write the last remaining byte to the buffer
data.add(compressed[++index]);
break;
}
else {
// Read the next few bytes
int i;
for (i = 0; i < compressed[index]; i++)
data.add(compressed[index + i + 1]);
index += i;
}
index++;
}
// Check if the amount of bytes read is the same as the size of the block.
if (index != compressed.length - 1)
// In case the index counter is only 1. The data portion will be empty.
if (index == 1)
return null;
else
throw new IOException("Invalid RLE block");
return data;
}
/*
* Read an RLE compressed block from the file.
* @return Byte array of the read data
* @throws IOException
*/
public byte[] readBlock() throws IOException {
LinkedList<Byte> data = decompressBlock();
if (data != null) {
byte[] b = new byte[data.size()];
for (int c = 0; !data.isEmpty(); c++)
b[c] = data.pop();
return b;
}
return null;
}
/*
* Read an RLE compressed block from the file. Put it in an integer array so it can be used
* for some tasks that require unsigned data. Such as drawing. Convenience method.
* @return Integer array
* @throws IOException
*/
public int[] readBlockAsIntArray() throws IOException {
LinkedList<Byte> data = decompressBlock();
if (data != null) {
int[] i = new int[data.size()];
for (int c = 0; !data.isEmpty(); c++)
i[c] = data.pop() & 0xff;
return i;
}
return null;
}
/*
* Skip a block of RLE compressed data.
* @return Amount of bytes skipped
* @throws IOException
*/
public int skipBlock() throws IOException {
int len = read() | read() << 8;
if (len <= 0)
throw new IOException("RLE block could not be skipped.");
skip(len);
return len;
}
}
import java.util.LinkedList;
import java.io.IOException;
import java.io.FileOutputStream;
import java.io.FileNotFoundException;
import java.io.File;
/*
* RLE file writer. This class is based on FileOutputStream and can be used
* to compress data and write the end result to a file. The algorithm used
* is based on the way Jazz1 uses RLE. Please note that this class sucks but
* I am out of ideas on how to fix it right now.
*
* Please note that there is plenty of room for improvement here.
*/
class RLEFileWriter extends FileOutputStream {
/*
* Create an RLEFileWriter for an existing file object.
* @param f File object
* @throws FileNotFoundException
*/
public RLEFileWriter(File f) throws FileNotFoundException {
super(f);
}
/*
* Create an RLEFileWriter for the file at the specified path.
* @param s Path to a file
* @throws FileNotFoundException
*/
public RLEFileWriter(String s) throws FileNotFoundException {
super(s);
}
/*
* Compress and write the byte array to the file.
* @param b Byte array
* @throws IOException
*/
public void writeBlock(byte[] b) throws IOException {
compressBlock(b);
}
/*
* Compress and write a integer array to the file. This is usefull when writing some data such as
* data of graphical nature. Convenience method.
* @param i Integer array
* @throws IOException
*/
public void writeBlockFromIntArray(int[] i) throws IOException {
byte[] b = new byte[i.length];
for (int c = 0; c < b.length; c++)
b[c] = (byte)i[c];
compressBlock(b);
}
/*
* Compress raw data.
* @param raw Uncompressed data.
* @throws IOException
*/
private void compressBlock(byte[] raw) throws IOException {
// Fill a linkedlist with values
LinkedList<Byte> data = new LinkedList<Byte>();
for (int curPos = 0; curPos < raw.length - 1; curPos++) {
short control = 0;
// In case of repeating bytes
if (raw[curPos] == raw[curPos + 1]) {
// Check how many times the next byte is repeated
while (raw[curPos] == raw[curPos + 1]) {
control++;
curPos++;
// Stop at the end of the array
if (curPos == raw.length - 1)
{
// In case we're at the end, ignore the last byte
control--;
break;
}
// Stop in case a byte is repeated more than 127 bytes.
if (control == 126)
break;
}
// Add 129 to the control byte to get the right repeat value.
control += 129;
// Just 129 might just as well be 1
if (control == 129) control = 1;
// Add repeated compressed data
data.add((byte)control);
data.add(raw[curPos]);
}
// In case of unique bytes
else {
// Check how many of the next bytes are unique
int start = curPos;
while (raw[curPos] != raw[curPos + 1]) {
control++;
curPos++;
// Stop at the end of the array
if (curPos == raw.length - 1)
break;
// Stop in case there is more than 127 bytes of data
if (control == 126)
break;
}
// Add unique compressed data
data.add((byte)control);
for (int j = start; j < curPos; j++)
data.add(raw[j]);
// Take one step back to check the next couple of bytes.
curPos--;
}
}
// Add the last two bytes of the block
data.add((byte)0);
data.add(raw[raw.length - 1]);
// Write the block to the file
writeCompressedBlock(data);
}
/*
* Write the compressed data to the file.
* @param data Linked list containing compressed data.
* @throws IOException
*/
private void writeCompressedBlock(LinkedList<Byte> data) throws IOException {
// First write the two size bytes to the file
write(data.size() % 256);
write(data.size() / 256);
// Empty the linkedlist into the file
byte[] b = new byte[data.size()];
for (int i = 0; !data.isEmpty(); i++)
b[i] = data.pop();
write(b);
}
}