Jazz Jackrabbit RLE compression

From ModdingWiki
Jump to: navigation, search
Jazz Jackrabbit RLE compression
Format typeCompression algorithm
TypeStream
I/O unit size1-byte
Games

Jazz Jackrabbit heavily uses RLE Compression, or Run Length Encoding, which is explained here.

The RLE loading routine takes two parameters, a file pointer and a length.

  • Set position to 0
  • Create an empty buffer
  • Read one byte
  • Read one byte, shift left 8 positions and add to first byte

This value gives the position the file pointer should return to after RLE decompression.

  • While position < length
    • Read one byte as foo
    • Is foo > 127?
      • Read one byte as bar
      • Fill the buffer with (foo & 127) bytes of bar
    • Or is foo > 1?
      • Read foo bytes and put these in the buffer
    • foo == 0
      • Read one more byte
  • Move file pointer to value determined at the start of the routine


Another way to look at it is as follows: the size of the compressed data is given by the first two bytes of the block, but is only needed by Jazz. Decompression starts at the next byte after this and follows these rules:

1.) Get a byte
2.) If this byte is zero, stop decompressing
3.) Is the value of this byte larger than 127?
    -> If yes, then:
       -> Get the next byte and copy it [Value - 127] times
       -> Move forward a byte and go to 1
    -> If no then:
       -> Get the next [Value] bytes
       -> Move forward [Value] bytes and go to 1

Source code

The following is code that will decompress\compress raw data into the Jazz RLE format.

QuickBasic

DECLARE SUB RLECOMPRESS ()
DIM SHARED x0 AS STRING, y0 AS STRING, z0 AS STRING
DIM SHARED x2 AS STRING * 2
DIM SHARED x4 AS STRING * 4
 
x0 = "Example data string"
RLECOMPRESS
END
 
SUB RLECOMPRESS '                                               Take string x0 and produce compressed string x0
y0 = "" '                                                       Clear string y0
FOR l1 = 0 TO 252 '                                             We'll need a 4-byte string to act as a flag for duplicate bytes;
 x4 = CHR$(l1) + CHR$(l1 + 1) + CHR$(l1 + 2) + CHR$(l1 + 3) '   x4, this string must NOT be found anywhere in the uncompressed data,
 IF INSTR(x0, x4) = 0 THEN EXIT FOR '                           so we check for it here. It is possible to have data that contains all
NEXT l1 '                                                       253 possible flags, but very unlikely.
FOR i = 1 TO LEN(x0) - 1
 IF MID$(x0, i, 1) = MID$(x0, i + 1, 1) THEN '                  Do we start a dupe byte run? (Check for dupe bytes)
  y0 = y0 + x4 '                                                Dupe byte flag added to y0
  count = 1 '                                                   Start counting dupe bytes
  FOR j = i + 1 TO LEN(x0) - 1 '                                Do this until out of data
   count = count + 1 '                                          Count dupe bytes
   IF MID$(x0, j, 1) <> MID$(x0, j + 1, 1) THEN EXIT FOR '      If end of dupe bytes, stop
  NEXT j
  y0 = y0 + MKI$(count) + MID$(x0, i, 1) '                      Add count and dupe byte to string
  i = j '                                                       Move to position j in string
 ELSE
  y0 = y0 + MID$(x0, i, 1) '                                    If nonrepeating byte, just add to y0
 END IF
NEXT i
x2 = CHR$(0) + RIGHT$(x0, 1) '                                  Store last byte of string as JJ endstring format
 
 
'                                                               Next take string y0 and convert it to JJ type compression as x0
x0 = "" '                                                       Clear uncompressed string for output
z0 = "" '                                                       Here z0 is used to store a string on non-dupe bytes
FOR i = 1 TO LEN(y0)
 IF MID$(y0, i, 4) = x4 THEN '                                  Check for dupe byte flag
  IF LEN(z0) > 0 THEN x0 = x0 + CHR$(LEN(z0)) + z0 '            If we have non-dupe bytes stored, write them
  count = CVI(MID$(y0, i + 4, 2)) '                             Get number of dupe bytes
  FOR j = 1 TO FIX(count / 127) '                               Divide long dupes into max 127 chunks
   x0 = x0 + CHR$(255) + MID$(y0, i + 6, 1) '                   Add $FF $xx for every 127 dupe bytes
  NEXT j
  IF count MOD 127 > 0 THEN x0 = x0 + CHR$((count MOD 127) + 128) + MID$(y0, i + 4, 1)
  i = i + 6 '                                                   Move past flag, etc bytes
  z0 = "" '                                                     Clear z0 to record non-dupe bytes
 ELSE
  z0 = z0 + MID$(y0, i, 1)
  IF LEN(z0) = 127 THEN '                                       If z0 reaches max length
   x0 = x0 + CHR$(127) + z0 '                                   Add it to output
   z0 = "" '                                                    And reset z0
  END IF
 END IF
NEXT i
IF LEN(z0) > 0 THEN x0 = x0 + CHR$(LEN(z0)) + z0 '              If we have non-dupe bytes stored, write them
x0 = x0 + x2 '                                                  Add end of string
x0 = MKI$(LEN(x0)) + x0 '                                       Add RLE block size word to block start
END SUB
'						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.)
 
SUB RLEDO ' 					Decompress RLE data x0 to the string y0
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);
	}
}