Difference between revisions of "Kosinski compression"

From Sega Retro

old>ElFly
m (Forgot an important word.)
 
(31 intermediate revisions by 16 users not shown)
Line 1: Line 1:
−
{{cleanup1|Wikify the markup in the Compression Theory section}}
+
'''Kosinski compression''' is the name given to a compression format used in ''Sonic'' games for the [[Sega Genesis|Sega Genesis/Mega Drive]]. The name first showed up on [[sonic:SHaC|SHaC]] and was to pay tribute to the person who cracked the format, [[sonic:Brett Kosinski|Brett Kosinski]]. It is a variation of the [[LZSS]] algorithm.
−
'''Kosinski compression''' is the name given by the Sonic Community to a format used in ''Sonic'' games for the [[Sega Genesis|Sega Genesis/Megadrive]]. It is named after the person who cracked it, [[Brett Kosinski]]. It appears to be an extension/variation of the [[LZSS]] algorithm.
 
  
 
Kosinski compression is used to compress the following data types:
 
Kosinski compression is used to compress the following data types:
 
* ''[[Sonic the Hedgehog (Genesis)|Sonic the Hedgehog]]'' - 256x256 [[block mappings]].
 
* ''[[Sonic the Hedgehog (Genesis)|Sonic the Hedgehog]]'' - 256x256 [[block mappings]].
−
* ''[[Sonic the Hedgehog 2]]'' - level graphics, block mappings and level layouts.
+
* ''[[Sonic the Hedgehog 2 (Mega Drive)|Sonic the Hedgehog 2]]'' - level graphics, block mappings and level layouts.
 +
* ''[[Sega Mega-CD#BIOS|Mega CD]]'' - SUB-CPU [[BIOS#Sega Mega-CD|BIOS]] code and data.
 +
* ''[[Phantasy Star IV]]'' - Text.
 +
* ''[[QuackShot Starring Donald Duck]]'' - Text.{{ref|https://www.romhacking.net/translations/1320/}}
  
−
==Kosinski Compression Theory==
+
==Compression Theory==
−
(Document originally written by [[Sonic Hachelle-Bee]] and posted [http://www.sws2b.com/forums/index.php?showtopic=3482 here])
+
===Basic Format===
  
−
The aim of this topic is to explain how the famous Brett Kosinski format works. Reading this post, you will learn how to compress and decompress this compression format all in Hex editing, without utilities.
+
The Kosinski compression scheme is very powerful and includes support for both uncompressed data and three sizes for dictionary matches to optimally compress repeating patterns.
  
−
THEORY:First of all, you have to know that in all the Brett Kosinski format, there is some 16 bits value (2 bytes) whose tell the game which byte is uncompressed data or not.These 16 bits values (called bitfields by Brett Kosinski) begins at start, the first 2 bytes of the compressed data.
+
The compressed data follows the following format:
  
−
As an example, we have this begining of compressed data:
+
<pre>
 +
AA AA BB BB .. AA AA BB BB ..
 +
</pre>
  
 +
The A field is referred to as the description field. This is always 2 bytes in length, starting at the beginning of the compressed data, and is followed by the B field, which is referred to as the data field. This goes on for as long as is necessary to cover all the data described in the description field. After that, the pattern repeats until the end of compression sequence is encountered.
  
−
'''53 FB 01 23 FE 67 FF F8 0D 98 FF FD 65 98 75 FB B2 00 15...'''
+
===Description Field===
  
 +
The description field is made up of 16 bits in little endian bit (not byte) order, which means that the least significant bit is read first; in other words, the bytes are in the correct order, but each byte is read "backwards." So for example, if the description field is:
  
−
53 FB is this 16 bits value.
+
<pre>FF FE</pre>
  
−
Let's convert it into bits:
+
then the description field, in bits, in the correct order for interpretation, will be:
  
 +
<pre>[1111 1111] [0111 1111]</pre>
  
−
'''53 FB = 0101 0011 1111 1011'''
+
Now, going from left to right, each bit is interpreted in the following way:
  
 +
* If the bit is a 1, it indicates uncompressed data.
 +
* If the bit is a 0, followed by a 1, it indicates a full dictionary match.
 +
* If the bit is a 0, followed by a 0, it indicates an inline dictionary match. The two bits following this in the description field give the copy count - 2.
  
−
You have to read it carefully. Cut it into 2 parts in the middle, paste the left part after the right part, then read it from right to left, like this:
+
When the last bit from a description field is read, a new description field is read from the next 2 bytes of the data before processing the data, even if the last bit completes a valid "command". If the end of compression sequence occurs and there are still description field bits left, they are ignored.
  
 +
===Uncompressed Data===
  
−
'''0101 0011 1111 1011 --> 1111 1011 0101 0011 --> 1100 1010 1101 1111'''
+
If a 1 is read in the description field, the corresponding byte in the data field is already uncompressed and simply copied to the destination as-is.
  
 +
===Inline Dictionary Match===
  
−
Now, all bits of these 16 represent one byte and his status: uncompressed, compressed (format). There is 3 compression forms you can encounter into Brett Kosinski format. I will use the terms of Brett Kosinski himself to call them:
+
Inline dictionary matches are indicated by 00XX in the description field. The XX is incremented by 2 to get the number of bytes to copy, and the corresponding byte in the data field is added to -256 to get the offset from the current position in the uncompressed stream of the byte to start copying from.
  
−
1 --> Uncompressed byte (UB).
+
'''Note:''' Keep in mind that the repeat count in the description field is ''not'' how many times the pattern is repeated, but for how many bytes the pattern is repeated. Using a repeat count of 11 (3 + 2 = 5 bytes) and an offset of $FB (-$100 + $FB = -5) only repeats the pattern once. Note that anything farther back than the last 5 bytes cannot be repeated entirely using this method because the largest possible repeat count is 5. Anything that needs to be repeated for longer than 5 bytes needs to use separate dictionary matches.
−
01 --> Separate compression (SC).
 
−
00 XX --> Inline compression (IC).
 
  
−
In our example, we have this:
+
===Full Dictionary Matches===
  
 +
Full dictionary matches are indicated in the description field with a 01 and has 2 or 3 corresponding bytes in the data field, depending on the second byte. The format of these bytes is:
  
−
'''53 FB 01 23 FE 67 FF F8 0D 98 FF FD 65 98 75 FB B2 00 15...1100 1010 1101 1111 --> 1 (UB) / 1 (UB) / 00 10 (IC) / 1 (UB) / 01 (SC) / 1 (UB) / 01 (SC) / 1 (UB) / 1 (UB) / 1 (UB) / 1 (UB)'''
+
<pre>
 +
[LLLL LLLL] [HHHH HCCC]
 +
</pre>
 +
if there are two bytes or
 +
<pre>
 +
[LLLL LLLL] [HHHH H000] [CCCC CCCC]
 +
</pre>
 +
if there are three bytes. The three byte format is used when the C bits of the second byte are all unset.
  
−
Then:01 is an UB. Read it as it. 23 is another UB. FE is IC. I will explain it later. 67 is an UB. FF F8 0D is SC. I will explain it later. 98 is an UB. FF FD is SC. 65 is an UB. 98 is an UB. 75 is an UB. FB B2 is the next bitfield, before the last byte of the previous bitfield. 00 is an UB....After the end of this 16 bits bitfield, the game will check for another coming after. The next is before the last byte (or compression form) referred by the current bitfield. In this example, the next bitfield is FB B2. Convert it into bits again, and continue the code with 15...
+
In the two byte format, -8192 + HHHH * 256 + LLLLLLLL gives the offset from the current position in the uncompressed stream of the byte to start copying from, and CCC + 2 gives the number of bytes to copy. In the three byte format, the offset is calculated in the same way but the copy count is given by CCCCCCCC + 1. Therefore the maximum number of bytes that can be copied is 9 in the 2 byte format and 256 in the 3 byte format.
  
 +
So for example, in:
 +
<pre>
 +
F0 F8 40 = [1111 0000] [1111 1000] [0100 0000]
 +
</pre>
 +
the offset would be -16, or 16 bytes backward since -8192 + 31 * 256 + 240 = -16.  Also in this example, 65 bytes would be copied (CCCCCCCC + 1 where the value of the C bits is 64 [40]).
  
−
Inline compression: This is when you read something like this under the bitfield:
+
Two special cases occur when the three byte format is used and the third byte is either 0 or 1, and are described below.
  
−
00 XXXX is a value that tells how much bytes to copy after the current uncompressed byte:
+
====End of Compression sequence====
  
−
00 --> 2 bytes.01 --> 3 bytes.10 --> 4 bytes.11 --> 5 bytes.
+
The end of the compressed data is indicated by a three byte data field corresponding to full dictionary matches in which the third byte is 0.
  
−
The byte this 00 XX value refers to, is a negative value.In our previous example, it's FE = -2. The game will read all the previous bytes this negative value is telling, and will copy them for XX bytes.
+
====Read Next Description sequence====
  
−
In our example: 01 23 FE
+
Alternatively, if the third byte is 1 rather than 0 it indicates that the current description is to be discarded and a new one to be read.
  
−
And the bitfield value of the byte FE is 00 10, XX = 10.Then, 01 23 FE = 01 23 01 23 01 23. Writing FF instead of FE will make this: 01 23 FF = 01 23 23 23 23 23.
+
=== Examples ===
  
 +
====Uncompressed Data====
  
−
Separate compression: This is when there is 01 under the bitfield. The separate compression uses at least 2 bytes, and sometimes 3 (the last is optional).
+
The following Kosinski-compressed stream:
  
−
In a binary form: NN DC (CC) = NNNN NNNN DDDD DCCC (CCCC CCCC)NN is another negative value. Unlike IC, this one will tell the game where to read/copy the (uncompressed) data from.
+
<pre>FF 5F 00 01 02 03 04 05 06 07 08 09 0A 0B 0C 00 F0 00</pre>
  
−
Writing FF for NN will read/copy the previous byte only. Writing another value will read/copy the previous bytes this value refers to, until you have CC of them.
+
produces the following output:
  
−
DD is again a negative value on 5 bits. This is an addon to NN. Take NN and substract 256 (100 in hex) * |DD+1|. Take the result as your new NN value. DD = 11111 = -1 --> NN = NN - (256 * |-1+1|) = NN (Do nothing)DD = 11110 = -2 --> NN = NN - (256 * |-2+1|) = NN - 256DD = 11101 = -3 --> NN = NN - (256 * |-3+1|) = NN - 256 * 2 = NN - 512DD = 11100 = -4 --> NN = NN - (256 * |-4+1|) = NN - 256 * 3 = NN - 768...DD = 00000 = -32 --> NN = NN - (256 * |-32+1|) = NN - 256 * 31 = NN - 7936
+
<pre>00 01 02 03 04 05 06 07 08 09 0A 0B 0C</pre>
  
−
Example:66 67 FF F8 0D --> NN = -1 and DD = 11111 --> NN = -1, we are starting at 67.66 67 FE F8 0D --> NN = -2 and DD = 11111 --> NN = -2, we are starting at 66....66 67 FF F0 0D --> NN = -1 and DD = 11110 --> NN = -257, we are starting 257 bytes before.66 67 FD E7 --> NN = -3 and DD = 11100 --> NN = -771, we are starting 771 bytes before.
+
The first 2 bytes are a description field: [1111 1111][1111 1010]. The first 13 bits in the description field are 1, indicating that the next 13 bytes in the data field (00 through 0C) are already uncompressed. The next 2 bits are 0 and 1, which indicates a full dictionary match. The 3 lowest bits of the second byte are 0, so we have the 3-byte form. The last byte is 0, which indicates the end of the compressed stream.
  
−
CC: Count.If you have no more than 9 bytes to read/copy, then the last CC byte is useless.
+
====Inline Dictionary Match====
  
−
F0 --> Like F8, be careful of the DD value.
+
The following Kosinski-compressed stream:
  
−
F1 --> Copy the read data for 3 bytes, be careful of the DD value.
+
<pre>51 00 25 FF 00 F0 00</pre>
  
−
F2 --> Copy the read data for 4 bytes, be careful of the DD value.
+
produces the following output:
  
−
F3 --> Copy the read data for 5 bytes, be careful of the DD value.
+
<pre>25 25 25 25</pre>
  
−
F4 --> Copy the read data for 6 bytes, be careful of the DD value.
+
We start with the description field: [1000 1010][0000 0000]. The first bit is 1, indicating that the next byte is uncompressed. The next two bits are 00, indicating an inline dictionary match. We read the following 2 bits, 01, and add 2 to get a count of 3 bytes. Then, we read the next byte, which gives the offset to the pattern in the uncompressed stream. The value is FF (-$100 + $FF = -1), so the pattern starts 1 byte back. The source pattern overlaps the destination, but we will be completing the pattern as it is decoded. Therefore, we end up outputting 3 '25' bytes. The stream ends with the standard end-of-compression sequence.
  
−
F5 --> Copy the read data for 7 bytes, be careful of the DD value.
+
====Final Example====
  
−
F6 --> Copy the read data for 8 bytes, be careful of the DD value.
+
<pre>
  
−
F7 --> Copy the read data for 9 bytes, be careful of the DD value.
+
Compressed Data:
  
−
F8 --> Read next.
+
  FF 3F 54 3B C4 44 54 33 33 5B 2D 5C 44 5C C4 C5
 +
  FC 15 FE C3 44 78 88 98 44 30 FF FF 00 F8 00
  
−
F9 --> Copy the read data for 3 bytes.
+
Decompression process:
  
−
FA --> Copy the read data for 4 bytes.
+
  FF 3F translates to [1111 1111] [1111 1100]
 +
  First 14 data bytes are uncompressed (1111 1111 1111 11)
  
−
FB --> Copy the read data for 5 bytes.
+
      Output: 54 3B C4 44 54 33 33 5B 2D 5C 44 5C C4 C5
  
−
FC --> Copy the read data for 6 bytes.
+
  The next description (00) indicates an inline dictionary match but more description data is needed, so the next description field is read:
 +
  FC 15 translates to [0011 1111] [1010 1000]
  
−
FD --> Copy the read data for 7 bytes.
+
  2 bytes (00) are to be copied and the offset is -$100 + $FE = -2:
  
−
FE --> Copy the read data for 8 bytes.
+
      Output: 54 3B C4 44 54 33 33 5B 2D 5C 44 5C C4 C5 C4 C5
  
−
FF --> Copy the read data for 9 bytes.
+
  The next 7 data bytes are uncompressed (11 1111 1)
  
−
Else, write F8 = 1111 1000 (CCC = 000) for the first count, and use the last byte to actually write your count (-1).
+
      Output: 54 3B C4 44 54 33 33 5B 2D 5C 44 5C C4 C5 C4 C5 C3 44 78 88 98 44 30
  
−
F8 09 --> Copy the read data for 10 bytes.
+
  The next description (01) indicates a full dictionary match.  The corresponding data bytes (FF FF) translate to an offset of
 +
  -8192 + 31 * 256 + 255 = -1 and a copy count of 7 + 2 = 9 (i.e. the last 1 output byte repeated for 9 output bytes).
  
−
F8 0A --> Copy the read data for 11 bytes....Writing 00 F8 00 (NN = 00 and both counts are 00's) will end the compressed data.In our example:53 FB 01 23 FE 67 FF F8 0D 98 FF FD 65 98 75 FB B2 00 15...We have 2 SC: FF F8 0D and FF FD.67 FF F8 0D = 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 (67 + 0Ex67)98 FF FD = 98 98 98 98 98 98 98 98 (98 + 07x98)Another: 12 34 56 78 9A BC DE 10 FA F9 = 12 34 56 78 9A BC DE 10 56 78 9A
+
      Output: 54 3B C4 44 54 33 33 5B 2D 5C 44 5C C4 C5 C4 C5 C3 44 78 88 98 44 30
 +
              30 30 30 30 30 30 30 30 30
  
−
EXAMPLE:We have this compressed data:FF 3F 54 3B C4 44 54 33 33 5B 2D 5C 44 5C C4 C5FC 15 FE C3 44 78 88 98 44 30 FF FF 00 F8 00Bitfields:FF 3F = 1111 1111 0011 1111 --> 1111 1111 1111 1100FC 15 = 1111 1100 0001 0101 --> 0011 1111 1010 1000Green color: Uncompressed byte.Red color: Separate compression.Blue color: Inline compression.Uncompressed data:54 3B C4 44 54 33 33 5B 2D 5C 44 5C C4 C5 C4 C5C3 44 78 88 98 44 30 30 30 30 30 30 30 30 30 30I hope someone will understand something.
+
  The next description also indicates a full dictionary match. The three byte format is used and the third byte is 0, so
 +
  the rest of the description field is ignored and the compression is complete.
 +
 
 +
      Output: 54 3B C4 44 54 33 33 5B 2D 5C 44 5C C4 C5 C4 C5 C3 44 78 88 98 44 30
 +
              30 30 30 30 30 30 30 30 30
  
−
[[Category:Hacking Information]]
+
</pre>
 +
 
 +
==Kosinski Moduled compression==
 +
 
 +
Kosinski Moduled compression (KosM compression) is a variant of standard Kosinski compression, used by ''[[Sonic 3 & Knuckles]]''. KosM compressed data starts off with a 2-byte header. The upper nibble is the total number of modules minus 1, and the lower three nibbles are the uncompressed size of the last module in bytes (all other modules have a fixed uncompressed size of $1000 bytes). As a result, the entire header word can be read as the total uncompressed size of the data. The only special case occurs when the header is $A000, in which case the game reads it as $8000. After the header are the actual modules. Each module can be read as standard Kosinski-compressed data, and all modules but the last are padded out to a size which is a multiple of $10 bytes.
 +
 
 +
KosM can be thought of as an archival format for multiple pieces of Kosinski-compressed data, and is used as an alternative to [[Nemesis compression]] for compressing art. The maximum uncompressed module size was kept as $1000 bytes because the intermediate RAM buffer to which the data is decompressed before being DMAed to VRAM has a size of $1000 bytes.
 +
 
 +
==Origin==
 +
The compression format was created by Fabrice Bellard back in 1989 and 1990, who named it LZEXE.{{ref|https://bellard.org/lzexe.html}} It was derived from [https://web.archive.org/web/19990203141013/http://oak.oakland.edu/pub/simtelnet/msdos/arcutils/lz_comp2.zip Haruhiko Okumura's LZSS implementation]. Its intended use was as part of a program that would compress MSDOS executables and include the decompression engine in the result so they would self-extract after loading.
 +
 
 +
The program was shared with some friends, and then it was put on some BBSs. It went on to become the first widely known executable file compression format for PCs under MSDOS.
 +
 
 +
==Decompression code==
 +
 
 +
An annotated version of the Kosinski decompression code is provided below for reference. The code is taken from ''[[sonic:Sonic 3 & Knuckles|Sonic 3 & Knuckles]]'', but the same code is presumably used in all games which use the format. A few labels have been edited to correct terminology.
 +
 
 +
<pre>; ---------------------------------------------------------------------------
 +
; Kosinski decompression subroutine
 +
; Inputs:
 +
; a0 = compressed data location
 +
; a1 = destination
 +
; ---------------------------------------------------------------------------
 +
 
 +
; =============== S U B R O U T I N E =======================================
 +
 
 +
 
 +
Kos_Decomp:
 +
subq.l #2,sp ; make space for two bytes on the stack
 +
move.b (a0)+,1(sp)
 +
move.b (a0)+,(sp)
 +
move.w (sp),d5 ; copy first description field
 +
moveq #$F,d4 ; 16 bits in a byte
 +
 
 +
Kos_Decomp_Loop:
 +
lsr.w #1,d5 ; bit which is shifted out goes into C flag
 +
move sr,d6
 +
dbf d4,Kos_Decomp_ChkBit
 +
move.b (a0)+,1(sp)
 +
move.b (a0)+,(sp)
 +
move.w (sp),d5 ; get next description field if needed
 +
moveq #$F,d4 ; reset bit counter
 +
 
 +
Kos_Decomp_ChkBit:
 +
move d6,ccr ; was the bit set?
 +
bcc.s Kos_Decomp_Match ; if not, branch (C flag clear means bit was clear)
 +
move.b (a0)+,(a1)+ ; otherwise, copy byte as-is
 +
bra.s Kos_Decomp_Loop
 +
; ---------------------------------------------------------------------------
 +
 
 +
Kos_Decomp_Match:
 +
moveq #0,d3
 +
lsr.w #1,d5 ; get next bit
 +
move sr,d6
 +
dbf d4,Kos_Decomp_ChkBit2
 +
move.b (a0)+,1(sp)
 +
move.b (a0)+,(sp)
 +
move.w (sp),d5
 +
moveq #$F,d4
 +
 
 +
Kos_Decomp_ChkBit2:
 +
move d6,ccr ; was the bit set?
 +
bcs.s Kos_Decomp_FullMatch ; if it was, branch
 +
lsr.w #1,d5 ; bit which is shifted out goes into X flag
 +
dbf d4,+
 +
move.b (a0)+,1(sp)
 +
move.b (a0)+,(sp)
 +
move.w (sp),d5
 +
moveq #$F,d4
 +
+
 +
roxl.w #1,d3 ; get high repeat count bit (shift X flag in)
 +
lsr.w #1,d5
 +
dbf d4,+
 +
move.b (a0)+,1(sp)
 +
move.b (a0)+,(sp)
 +
move.w (sp),d5
 +
moveq #$F,d4
 +
+
 +
roxl.w #1,d3 ; get low repeat count bit
 +
addq.w #1,d3 ; increment repeat count
 +
moveq #-1,d2
 +
move.b (a0)+,d2 ; calculate offset
 +
bra.s Kos_Decomp_MatchLoop
 +
; ---------------------------------------------------------------------------
 +
 
 +
Kos_Decomp_FullMatch:
 +
move.b (a0)+,d0 ; get first byte
 +
move.b (a0)+,d1 ; get second byte
 +
moveq #-1,d2
 +
move.b d1,d2
 +
lsl.w #5,d2
 +
move.b d0,d2 ; calculate offset
 +
andi.w #7,d1 ; does a third byte need to be read?
 +
beq.s Kos_Decomp_FullMatch2 ; if it does, branch
 +
move.b d1,d3 ; copy repeat count
 +
addq.w #1,d3 ; and increment it
 +
 
 +
Kos_Decomp_MatchLoop:
 +
move.b (a1,d2.w),d0
 +
move.b d0,(a1)+ ; copy appropriate byte
 +
dbf d3,Kos_Decomp_MatchLoop ; and repeat the copying
 +
bra.s Kos_Decomp_Loop
 +
; ---------------------------------------------------------------------------
 +
 
 +
Kos_Decomp_FullMatch2:
 +
move.b (a0)+,d1
 +
beq.s Kos_Decomp_Done ; 0 indicates end of compressed data
 +
cmpi.b #1,d1
 +
beq.w Kos_Decomp_Loop ; 1 indicates a new description needs to be read
 +
move.b d1,d3 ; otherwise, copy repeat count
 +
bra.s Kos_Decomp_MatchLoop
 +
; ---------------------------------------------------------------------------
 +
 
 +
Kos_Decomp_Done:
 +
addq.l #2,sp ; restore stack pointer to original state
 +
rts
 +
; End of function Kos_Decomp</pre>
 +
[[Category:Data compression]]

Latest revision as of 13:37, 5 September 2024

Kosinski compression is the name given to a compression format used in Sonic games for the Sega Genesis/Mega Drive. The name first showed up on SHaC and was to pay tribute to the person who cracked the format, Brett Kosinski. It is a variation of the LZSS algorithm.

Kosinski compression is used to compress the following data types:

Compression Theory

Basic Format

The Kosinski compression scheme is very powerful and includes support for both uncompressed data and three sizes for dictionary matches to optimally compress repeating patterns.

The compressed data follows the following format: 

AA AA BB BB .. AA AA BB BB ..

The A field is referred to as the description field. This is always 2 bytes in length, starting at the beginning of the compressed data, and is followed by the B field, which is referred to as the data field. This goes on for as long as is necessary to cover all the data described in the description field. After that, the pattern repeats until the end of compression sequence is encountered.

Description Field

The description field is made up of 16 bits in little endian bit (not byte) order, which means that the least significant bit is read first; in other words, the bytes are in the correct order, but each byte is read "backwards." So for example, if the description field is: 

FF FE

then the description field, in bits, in the correct order for interpretation, will be: 

[1111 1111] [0111 1111]

Now, going from left to right, each bit is interpreted in the following way:

  • If the bit is a 1, it indicates uncompressed data.
  • If the bit is a 0, followed by a 1, it indicates a full dictionary match.
  • If the bit is a 0, followed by a 0, it indicates an inline dictionary match. The two bits following this in the description field give the copy count - 2.

When the last bit from a description field is read, a new description field is read from the next 2 bytes of the data before processing the data, even if the last bit completes a valid "command". If the end of compression sequence occurs and there are still description field bits left, they are ignored.

Uncompressed Data

If a 1 is read in the description field, the corresponding byte in the data field is already uncompressed and simply copied to the destination as-is.

Inline Dictionary Match

Inline dictionary matches are indicated by 00XX in the description field. The XX is incremented by 2 to get the number of bytes to copy, and the corresponding byte in the data field is added to -256 to get the offset from the current position in the uncompressed stream of the byte to start copying from.

Note: Keep in mind that the repeat count in the description field is not how many times the pattern is repeated, but for how many bytes the pattern is repeated. Using a repeat count of 11 (3 + 2 = 5 bytes) and an offset of $FB (-$100 + $FB = -5) only repeats the pattern once. Note that anything farther back than the last 5 bytes cannot be repeated entirely using this method because the largest possible repeat count is 5. Anything that needs to be repeated for longer than 5 bytes needs to use separate dictionary matches.

Full Dictionary Matches

Full dictionary matches are indicated in the description field with a 01 and has 2 or 3 corresponding bytes in the data field, depending on the second byte. The format of these bytes is: 

[LLLL LLLL] [HHHH HCCC]

if there are two bytes or 

[LLLL LLLL] [HHHH H000] [CCCC CCCC]

if there are three bytes. The three byte format is used when the C bits of the second byte are all unset.

In the two byte format, -8192 + HHHH * 256 + LLLLLLLL gives the offset from the current position in the uncompressed stream of the byte to start copying from, and CCC + 2 gives the number of bytes to copy. In the three byte format, the offset is calculated in the same way but the copy count is given by CCCCCCCC + 1. Therefore the maximum number of bytes that can be copied is 9 in the 2 byte format and 256 in the 3 byte format.

So for example, in: 

F0 F8 40 = [1111 0000] [1111 1000] [0100 0000]

the offset would be -16, or 16 bytes backward since -8192 + 31 * 256 + 240 = -16. Also in this example, 65 bytes would be copied (CCCCCCCC + 1 where the value of the C bits is 64 [40]).

Two special cases occur when the three byte format is used and the third byte is either 0 or 1, and are described below.

End of Compression sequence

The end of the compressed data is indicated by a three byte data field corresponding to full dictionary matches in which the third byte is 0.

Read Next Description sequence

Alternatively, if the third byte is 1 rather than 0 it indicates that the current description is to be discarded and a new one to be read.

Examples

Uncompressed Data

The following Kosinski-compressed stream: 

FF 5F 00 01 02 03 04 05 06 07 08 09 0A 0B 0C 00 F0 00

produces the following output: 

00 01 02 03 04 05 06 07 08 09 0A 0B 0C

The first 2 bytes are a description field: [1111 1111][1111 1010]. The first 13 bits in the description field are 1, indicating that the next 13 bytes in the data field (00 through 0C) are already uncompressed. The next 2 bits are 0 and 1, which indicates a full dictionary match. The 3 lowest bits of the second byte are 0, so we have the 3-byte form. The last byte is 0, which indicates the end of the compressed stream.

Inline Dictionary Match

The following Kosinski-compressed stream: 

51 00 25 FF 00 F0 00

produces the following output: 

25 25 25 25

We start with the description field: [1000 1010][0000 0000]. The first bit is 1, indicating that the next byte is uncompressed. The next two bits are 00, indicating an inline dictionary match. We read the following 2 bits, 01, and add 2 to get a count of 3 bytes. Then, we read the next byte, which gives the offset to the pattern in the uncompressed stream. The value is FF (-$100 + $FF = -1), so the pattern starts 1 byte back. The source pattern overlaps the destination, but we will be completing the pattern as it is decoded. Therefore, we end up outputting 3 '25' bytes. The stream ends with the standard end-of-compression sequence.

Final Example


Compressed Data:

  FF 3F 54 3B C4 44 54 33 33 5B 2D 5C 44 5C C4 C5
  FC 15 FE C3 44 78 88 98 44 30 FF FF 00 F8 00

Decompression process:

  FF 3F translates to [1111 1111] [1111 1100]
  First 14 data bytes are uncompressed (1111 1111 1111 11)

      Output: 54 3B C4 44 54 33 33 5B 2D 5C 44 5C C4 C5

  The next description (00) indicates an inline dictionary match but more description data is needed, so the next description field is read:
  FC 15 translates to [0011 1111] [1010 1000]

  2 bytes (00) are to be copied and the offset is -$100 + $FE = -2:

      Output: 54 3B C4 44 54 33 33 5B 2D 5C 44 5C C4 C5 C4 C5

  The next 7 data bytes are uncompressed (11 1111 1)

      Output: 54 3B C4 44 54 33 33 5B 2D 5C 44 5C C4 C5 C4 C5 C3 44 78 88 98 44 30

  The next description (01) indicates a full dictionary match.  The corresponding data bytes (FF FF) translate to an offset of 
  -8192 + 31 * 256 + 255 = -1 and a copy count of 7 + 2 = 9 (i.e. the last 1 output byte repeated for 9 output bytes).

      Output: 54 3B C4 44 54 33 33 5B 2D 5C 44 5C C4 C5 C4 C5 C3 44 78 88 98 44 30
              30 30 30 30 30 30 30 30 30

  The next description also indicates a full dictionary match. The three byte format is used and the third byte is 0, so
  the rest of the description field is ignored and the compression is complete.
  
      Output: 54 3B C4 44 54 33 33 5B 2D 5C 44 5C C4 C5 C4 C5 C3 44 78 88 98 44 30
              30 30 30 30 30 30 30 30 30

Kosinski Moduled compression

Kosinski Moduled compression (KosM compression) is a variant of standard Kosinski compression, used by Sonic 3 & Knuckles. KosM compressed data starts off with a 2-byte header. The upper nibble is the total number of modules minus 1, and the lower three nibbles are the uncompressed size of the last module in bytes (all other modules have a fixed uncompressed size of $1000 bytes). As a result, the entire header word can be read as the total uncompressed size of the data. The only special case occurs when the header is $A000, in which case the game reads it as $8000. After the header are the actual modules. Each module can be read as standard Kosinski-compressed data, and all modules but the last are padded out to a size which is a multiple of $10 bytes.

KosM can be thought of as an archival format for multiple pieces of Kosinski-compressed data, and is used as an alternative to Nemesis compression for compressing art. The maximum uncompressed module size was kept as $1000 bytes because the intermediate RAM buffer to which the data is decompressed before being DMAed to VRAM has a size of $1000 bytes.

Origin

The compression format was created by Fabrice Bellard back in 1989 and 1990, who named it LZEXE.[2] It was derived from Haruhiko Okumura's LZSS implementation. Its intended use was as part of a program that would compress MSDOS executables and include the decompression engine in the result so they would self-extract after loading.

The program was shared with some friends, and then it was put on some BBSs. It went on to become the first widely known executable file compression format for PCs under MSDOS.

Decompression code

An annotated version of the Kosinski decompression code is provided below for reference. The code is taken from Sonic 3 & Knuckles, but the same code is presumably used in all games which use the format. A few labels have been edited to correct terminology. 

; ---------------------------------------------------------------------------
; Kosinski decompression subroutine
; Inputs:
; a0 = compressed data location
; a1 = destination
; ---------------------------------------------------------------------------

; =============== S U B R O U T I N E =======================================


Kos_Decomp:
		subq.l	#2,sp	; make space for two bytes on the stack
		move.b	(a0)+,1(sp)
		move.b	(a0)+,(sp)
		move.w	(sp),d5	; copy first description field
		moveq	#$F,d4	; 16 bits in a byte

Kos_Decomp_Loop:
		lsr.w	#1,d5	; bit which is shifted out goes into C flag
		move	sr,d6
		dbf	d4,Kos_Decomp_ChkBit
		move.b	(a0)+,1(sp)
		move.b	(a0)+,(sp)
		move.w	(sp),d5	; get next description field if needed
		moveq	#$F,d4	; reset bit counter

Kos_Decomp_ChkBit:
		move	d6,ccr	; was the bit set?
		bcc.s	Kos_Decomp_Match	; if not, branch (C flag clear means bit was clear)
		move.b	(a0)+,(a1)+	; otherwise, copy byte as-is
		bra.s	Kos_Decomp_Loop
; ---------------------------------------------------------------------------

Kos_Decomp_Match:
		moveq	#0,d3
		lsr.w	#1,d5	; get next bit
		move	sr,d6
		dbf	d4,Kos_Decomp_ChkBit2
		move.b	(a0)+,1(sp)
		move.b	(a0)+,(sp)
		move.w	(sp),d5
		moveq	#$F,d4

Kos_Decomp_ChkBit2:
		move	d6,ccr	; was the bit set?
		bcs.s	Kos_Decomp_FullMatch	; if it was, branch
		lsr.w	#1,d5	; bit which is shifted out goes into X flag
		dbf	d4,+
		move.b	(a0)+,1(sp)
		move.b	(a0)+,(sp)
		move.w	(sp),d5
		moveq	#$F,d4
+
		roxl.w	#1,d3	; get high repeat count bit (shift X flag in)
		lsr.w	#1,d5
		dbf	d4,+
		move.b	(a0)+,1(sp)
		move.b	(a0)+,(sp)
		move.w	(sp),d5
		moveq	#$F,d4
+
		roxl.w	#1,d3	; get low repeat count bit
		addq.w	#1,d3	; increment repeat count
		moveq	#-1,d2
		move.b	(a0)+,d2	; calculate offset
		bra.s	Kos_Decomp_MatchLoop
; ---------------------------------------------------------------------------

Kos_Decomp_FullMatch:
		move.b	(a0)+,d0	; get first byte
		move.b	(a0)+,d1	; get second byte
		moveq	#-1,d2
		move.b	d1,d2
		lsl.w	#5,d2
		move.b	d0,d2	; calculate offset
		andi.w	#7,d1	; does a third byte need to be read?
		beq.s	Kos_Decomp_FullMatch2	; if it does, branch
		move.b	d1,d3	; copy repeat count
		addq.w	#1,d3	; and increment it

Kos_Decomp_MatchLoop:
		move.b	(a1,d2.w),d0
		move.b	d0,(a1)+	; copy appropriate byte
		dbf	d3,Kos_Decomp_MatchLoop	; and repeat the copying
		bra.s	Kos_Decomp_Loop
; ---------------------------------------------------------------------------

Kos_Decomp_FullMatch2:
		move.b	(a0)+,d1
		beq.s	Kos_Decomp_Done	; 0 indicates end of compressed data
		cmpi.b	#1,d1
		beq.w	Kos_Decomp_Loop	; 1 indicates a new description needs to be read
		move.b	d1,d3	; otherwise, copy repeat count
		bra.s	Kos_Decomp_MatchLoop
; ---------------------------------------------------------------------------

Kos_Decomp_Done:
		addq.l	#2,sp	; restore stack pointer to original state
		rts
; End of function Kos_Decomp
  1. ↑ https://www.romhacking.net/translations/1320/
  2. ↑ https://bellard.org/lzexe.html
Retrieved from "https://segaretro.org/index.php?title=Kosinski_compression&oldid=1004091"