Difference between revisions of "Rob Northen compression"

From Sega Retro

(Added info about what compression schemes this is based on.)
m (→‎External links: it's no longer possible to download the Pro Pack from the original page... only from the archived page...)
 
(26 intermediate revisions by 11 users not shown)
Line 1: Line 1:
−
{{stub}}
+
<!--{{stub}}-->
−
'''Rob Northen compression''' ('''RNC''') is a multi-platform compression format created by [[Rob Northen]] in 1991. It is a variant of [[LZSS]] and [[Huffman]]. Decompression libraries have been written for the PC, [[Mega Drive]], Game Boy, SNES and Atari Lynx. RNC is used in a number of games by UK developers (notably Bullfrog and [[Traveller's Tales]]), including ''[[Sonic 3D: Flickies' Island]]'', ''Dungeon Keeper 2'', ''[[Magic Carpet]]'', ''[[Syndicate]]'' and ''Syndicate Wars''.
+
'''Rob Northen compression''' ('''RNC''') is a multi-platform compression format created by [[Rob Northen]] in 1991. It is a variant of [[LZSS]] and [[Huffman Coding]]. Decompression libraries have been written for the PC, [[Mega Drive]], [[Game Boy]], [[SNES]] and Atari Lynx. RNC is used in a number of games by UK developers (notably Bullfrog and [[Traveller's Tales]]), including ''[[Sonic 3D: Flickies' Island]]'', ''[[Blam! Machinehead]]'', ''Dungeon Keeper 2'', ''[[Magic Carpet]]'', ''[[Syndicate]]'' and ''[[Syndicate Wars]]''. It generally yields a 3:1 compression ratio.{{ref|1=[https://www.youtube.com/watch?v=IehwV2K60r8 SONIC 3D's Intro Sequence Is Impossible To Fit On A Cartridge - Right?]}}
  
−
[[Category:Data Formats]]
+
==Header format==
 +
Most RNC compressed files come in a standard 18 byte header:
 +
 
 +
{| class="prettytable"
 +
|-
 +
!Data Type!!Description!!Size (in Bytes)
 +
|-
 +
|Signature||ASCII "RNC"||3
 +
|-
 +
|Compression Method||1 or 2 (In binary)||1
 +
|-
 +
|Uncompressed Size||Size of the original file||4
 +
|-
 +
|Compressed Size||Size of the RNC data (excluding header)||4
 +
|-
 +
|Uncompressed CRC||Checksum of the original file||2
 +
|-
 +
|Compressed CRC||Checksum of the RNC data||2
 +
|-
 +
|Leeway||Difference between compressed and uncompressed data in largest pack chunk (if larger than decompressed data)||1
 +
|-
 +
|Pack Chunks||Amount of pack chunks||1
 +
|}
 +
 
 +
Each multi-byte portion of the header is big endian.
 +
 
 +
==Method 1==
 +
RNC Method 1 consists of a bit stream and a byte stream. The bit stream is read from right to left, as little endian 16 bit words. The first two bits of the bit stream are ignored.
 +
 
 +
Each pack chunk contains the following:
 +
 
 +
* 3 Huffman trees (one for literal data sizes, one for distance values, and one for length values) in the bit stream. These consist of:
 +
** A 5 bit value for the amount of leaf nodes in the tree
 +
** 4 bit values for each node representing their bit depth.
 +
* One 16 bit value in the bitstream for the amount of subchunks in the pack chunk.
 +
* The subchunk data, which contains for each subchunk:
 +
** A Huffman code value from the first tree in the bit stream for the amount of literals in the byte stream.
 +
** Literals from the byte stream.
 +
** A Huffman code from the bit stream that represents the distance - 1 of a distance/length pair.
 +
** A Huffman code from the bit stream that represents the length - 2 of a distance/length pair.
 +
 
 +
==Method 2==
 +
Method two also consists of a bit stream and a byte stream. It also ignores the first two bits. However, the bit stream is read from left to right as bytes. Also, it does not contain Huffman trees or sub chunks. Instead, it uses a fixed prefix coding in the following format:
 +
 
 +
{| class="prettytable"
 +
|-
 +
!Bit Stream!!Byte Stream!!Description
 +
|-
 +
|0||X||Literal Byte X
 +
|-
 +
|10 + Length + Distance||X|| Move Length Bytes from (Distance * 256) + X + 1
 +
|-
 +
|10111XXXX ||XXXX * 4 + 12 Bytes|| Get XXXX * 4 + 12 Literal Bytes
 +
|-
 +
|110||X||Move 2 Bytes from X + 1
 +
|-
 +
|1110 + Distance||X||Get 3 bytes from (Distance * 256) + X + 1
 +
|-
 +
|1111 + Distance||X Y||If X != 0, Get Y + 8 Bytes from (Distance * 256) + X + 1
 +
|-
 +
|11110||0||End of File
 +
|-
 +
|11111||0||End of pack chunk
 +
|}
 +
 
 +
The Length and Distance Codes are the following:
 +
 
 +
Length:
 +
{| class="prettytable"
 +
|-
 +
!Code!!Value
 +
|-
 +
|00||4
 +
|-
 +
|10||5
 +
|-
 +
|010||6
 +
|-
 +
|011||7
 +
|-
 +
|110||8
 +
|}
 +
 
 +
Distance:
 +
{| class="prettytable"
 +
|-
 +
!Code!!Value
 +
|-
 +
|0||0
 +
|-
 +
|110||1
 +
|-
 +
|1000||2
 +
|-
 +
|1001||3
 +
|-
 +
|10101||4
 +
|-
 +
|10111||5
 +
|-
 +
|11101||6
 +
|-
 +
|11111||7
 +
|-
 +
|101000||8
 +
|-
 +
|101001||9
 +
|-
 +
|101100||10
 +
|-
 +
|101101||11
 +
|-
 +
|111000||12
 +
|-
 +
|111001||13
 +
|-
 +
|111100||14
 +
|-
 +
|111101||15
 +
|}
 +
 
 +
==Mega Drive games which use Rob Northen compression==
 +
:''This list is vastly incomplete; please help expand it.
 +
{{multicol|
 +
* ''[[3 Ninjas Kick Back]]''
 +
* ''[[Addams Family]]''
 +
* ''[[Addams Family Values]]''
 +
* ''[[The Adventures of Mighty Max]]''
 +
* ''[[Astérix and the Great Rescue]]''
 +
* ''[[Astérix and the Power of the Gods]]''
 +
* ''[[The Incredible Hulk]]''
 +
* ''[[The Itchy & Scratchy Game]]'' (unreleased)
 +
* ''[[Marsupilami]]''
 +
* ''[[Mortal Kombat]]''
 +
* ''[[Mr. Nutz]]''
 +
* ''[[Outlander]]''
 +
* ''[[The Pagemaster]]''
 +
* ''[[RoboCop 3]]''
 +
* ''[[Spirou]]''
 +
* ''[[Spot Goes to Hollywood]]''
 +
* ''[[Stargate]]''
 +
* ''[[Street Racer]]''
 +
* ''[[Tinhead]]''
 +
* ''[[Tintin in Tibet]]''
 +
* ''[[World Championship Soccer II]]''
 +
}}
 +
 
 +
==References==
 +
<references/>
 +
 
 +
==External links==
 +
*[https://github.com/lab313ru/rnc_propack_source rnc_propack_source] - fully decompiled RNC ProPack source code: RNC1, RNC2 (packing, unpacking).
 +
*[http://icculus.org/libsyndicate/ libsyndicate] - a library for running Bullfrog game Syndicate, which [http://icculus.org/libsyndicate/libsyndicate.html#htoc6 contains a description of RNC1 files].
 +
* [http://www.yoda.arachsys.com/dk/utils.html Dungeon Keeper Utilities] - Contains an RNC1 compressor/decompressor.
 +
* [https://web.archive.org/web/20240718045738/https://aminet.net/package/util/pack/RNC_ProPack Pro-Pack (archived)] - The official DOS/Amiga compressor/decompressor for the RNC format. Contains 68k assembly code for both formats.
 +
 
 +
[[Category:Data compression]]

Latest revision as of 17:38, 4 November 2024

Rob Northen compression (RNC) is a multi-platform compression format created by Rob Northen in 1991. It is a variant of LZSS and Huffman Coding. Decompression libraries have been written for the PC, Mega Drive, Game Boy, SNES and Atari Lynx. RNC is used in a number of games by UK developers (notably Bullfrog and Traveller's Tales), including Sonic 3D: Flickies' Island, Blam! Machinehead, Dungeon Keeper 2, Magic Carpet, Syndicate and Syndicate Wars. It generally yields a 3:1 compression ratio.[1]

Header format

Most RNC compressed files come in a standard 18 byte header:

Data Type Description Size (in Bytes)
Signature ASCII "RNC" 3
Compression Method 1 or 2 (In binary) 1
Uncompressed Size Size of the original file 4
Compressed Size Size of the RNC data (excluding header) 4
Uncompressed CRC Checksum of the original file 2
Compressed CRC Checksum of the RNC data 2
Leeway Difference between compressed and uncompressed data in largest pack chunk (if larger than decompressed data) 1
Pack Chunks Amount of pack chunks 1

Each multi-byte portion of the header is big endian.

Method 1

RNC Method 1 consists of a bit stream and a byte stream. The bit stream is read from right to left, as little endian 16 bit words. The first two bits of the bit stream are ignored.

Each pack chunk contains the following:

  • 3 Huffman trees (one for literal data sizes, one for distance values, and one for length values) in the bit stream. These consist of:
    • A 5 bit value for the amount of leaf nodes in the tree
    • 4 bit values for each node representing their bit depth.
  • One 16 bit value in the bitstream for the amount of subchunks in the pack chunk.
  • The subchunk data, which contains for each subchunk:
    • A Huffman code value from the first tree in the bit stream for the amount of literals in the byte stream.
    • Literals from the byte stream.
    • A Huffman code from the bit stream that represents the distance - 1 of a distance/length pair.
    • A Huffman code from the bit stream that represents the length - 2 of a distance/length pair.

Method 2

Method two also consists of a bit stream and a byte stream. It also ignores the first two bits. However, the bit stream is read from left to right as bytes. Also, it does not contain Huffman trees or sub chunks. Instead, it uses a fixed prefix coding in the following format:

Bit Stream Byte Stream Description
0 X Literal Byte X
10 + Length + Distance X Move Length Bytes from (Distance * 256) + X + 1
10111XXXX XXXX * 4 + 12 Bytes Get XXXX * 4 + 12 Literal Bytes
110 X Move 2 Bytes from X + 1
1110 + Distance X Get 3 bytes from (Distance * 256) + X + 1
1111 + Distance X Y If X != 0, Get Y + 8 Bytes from (Distance * 256) + X + 1
11110 0 End of File
11111 0 End of pack chunk

The Length and Distance Codes are the following:

Length:

Code Value
00 4
10 5
010 6
011 7
110 8

Distance:

Code Value
0 0
110 1
1000 2
1001 3
10101 4
10111 5
11101 6
11111 7
101000 8
101001 9
101100 10
101101 11
111000 12
111001 13
111100 14
111101 15

Mega Drive games which use Rob Northen compression

This list is vastly incomplete; please help expand it.

References

  1. ↑ SONIC 3D's Intro Sequence Is Impossible To Fit On A Cartridge - Right?

External links

Retrieved from "https://segaretro.org/index.php?title=Rob_Northen_compression&oldid=1031143"