RefPack

From Niotso Wiki
(Redirected from QFS compression)
Jump to: navigation, search
RefPack
Type of format Compression
First appeared Need For Speed II (1997)
Contained by Persist, FAR, DBPF
RefPack is an LZ77 compression algorithm developed by Frank Barchard of EA Canada for the inhouse Gimex library used across several games by EA. In The Sims Online, data compressed by RefPack is held within a Persist container. However, there is no standard to what container RefPack-compressed data may be held in. In Need For Speed II SE, the first game to use RefPack, this data is found in Gimex (GMX) containers, and in Command & Conquer 3, this data is found in BIG containers. Other games may keep such data in standalone files with no container.

The values for RefPack are occasionally tweaked on a per-game basis. The Sims Online uses the normal values defined in EA's default implementation of RefPack: it is these values that are described in this article.

Definitions and data structure[edit]

RefPack data is made up of a series of incoming opcodes (or control codes or control sequences or whatever you wish to call them), each directly followed by its proceeding data. The input buffer refers to the compressed RefPack data, and the output buffer refers to the resulting decompressed data.

Each opcode consists of three parameters:

  • Proceeding Data Length - The length of the binary data that follows the opcode and is to be printed to the output buffer. This data is called the proceeding data.
  • Referenced Data Length - The length of data to be copied from earlier in the output buffer and placed directly after the proceeding data that was inserted by this opcode. This data is called the referenced data.
  • Referenced Data Offset - The distance to the referenced data from the current position (after all proceeding data).

Reference overrunning[edit]

Like any other LZ77 algorithm, the referenced data source may overrun into its initial destination. This happens when Referenced Data Length is longer than Referenced Data Offset; the result is there will not be enough data available yet to do a direct copy and paste. This is legal, and in fact very helpful. In this case, if you copy one byte at a time, you will notice that the source will begin to point to the data you previously copied over. So in other words, you just copy and paste the referenced data repeatedly until it meets your length requirement.

For example,

Decompressed data

James while John had

Incoming compressed data

ProceedingDataLength=0, ReferencedDataLength=41, ReferencedDataOffset=4

Notice that Referenced Data Length is far larger than Referenced Data Offset. The decoder fills the decompressed buffer using those 4 available bytes (" had"), producing:

Decompressed data

James while John had had had had had had had had had had had 

We would then follow up with "a better effect on the teacher" to finish the sentence.

As visible in the example above, this feature of LZ77 algorithms is used to satisfy run-length compression.

Opcodes[edit]

There are 4 types of opcodes utilized by RefPack which each allot certain numbers of bits to denote each of the 3 numbers above. Though many games use the default values in EA's reference implementation, the values can be tweaked on a per-game basis. The Sims Online uses the default set of values, while SimCity 4 (released less than a month after) uses unique values for the 4-byte opcode. That is just something to keep in mind.


Key Notes
# Opcode identifier bit
P Proceeding Data Length bit
R Referenced Data Length bit
O Referenced Data Offset bit
To obtain the values of any opcode, just merge the bits associated with that value in the order that they appear, with exceptions where noted.

The opcode identifier bits use unary coding.


2-byte[edit]

Byte 1 Byte 2
0OORRRPP
OOOOOOOO
Value Range Expression Exception to simple merging
Proceeding Data Length 0 to 3 Byte1 & 0x03 None
Referenced Data Length 3 to 10 ((Byte1 & 0x1C) >> 2) + 3 Add 3 to the extracted value
Referenced Data Offset 1 to 1024 ((Byte1 & 0x60) << 3) + Byte2 + 1 Add 1 to the extracted value


3-byte[edit]

Byte 1 Byte 2 Byte 3
10RRRRRR
PPOOOOOO
OOOOOOOO
Value Range Expression Exception to simple merging
Proceeding Data Length 0 to 3 (Byte2 & 0xC0) >> 6 None
Referenced Data Length 4 to 67 (Byte1 & 0x3F) + 4 Add 4 to the extracted value
Referenced Data Offset 1 to 16384 ((Byte2 & 0x3F) << 8) + Byte3 + 1 Add 1 to the extracted value


4-byte[edit]

Byte 1 Byte 2 Byte 3 Byte 4
110ORRPP
OOOOOOOO
OOOOOOOO
RRRRRRRR
Value Range Expression Exception to simple merging
Proceeding Data Length 0 to 3 Byte1 & 0x03 None
Referenced Data Length 5 to 1028 ((Byte1 & 0x0C) << 6) + Byte4 + 5 Add 5 to the extracted value
Referenced Data Offset 1 to 131072 ((Byte1 & 0x10) << 12) + (Byte2 << 8) + Byte3 + 1 Add 1 to the extracted value


1-byte[edit]

Byte 1
111PPPPP

The 1-byte opcode has two different specifications: one for when it does not carry the stop flag, and one for when it does. The stop flag specifies when the last opcode in the stream has been reached. It is necessary and must appear exactly once in the stream.

Only 1-byte opcodes may carry the stop flag. The stop flag is attributed to this opcode when the numerical value of the opcode byte is greater than a specific value, called the Highest Non-Stop Value (HNSV). The value of this number can vary and can be specified along with the RefPack data. In The Sims Online, the HNSV is specified in the Persist container that holds the RefPack data. If this value is not specified, the decompressor defaults to its own preconfigured default value, which is implementation-defined and may be any one of the legal values. EA's reference implementation (and therefore also The Sims Online) uses 0xFB. This value can be tweaked per game. If the decompressor picks a different value than was picked by the compressor, the decompressed code will break.

The legal values for the HNSV are 0xFE, 0xFD, 0xFB, 0xF7, 0xEF, and 0xFF. If it was specified alongside the RefPack data as 0x00, or it was not specified at all (RefPack is not required to be in any container), the decompressor picks its default value. Note that 0xFF is a special case, which follows 2's complement behavior of clearing all less-significant bits; there are no 1-byte opcodes without the stop flag when it is set to that value.

In the following expression definitions,

  • let HNSV equal the "Highest Non-Stop Value" described above.
  • let StopFlagData equal the binary value to the right of the 0 in HNSV; if HNSV is equal to 0xFF, StopFlagData equals 0x1F.

Without stop flag[edit]

Value Range Expression Exception to simple merging
Proceeding Data Length 4 to (((HNSV & 0x1F) + 1) << 2) in steps of 4 ((Byte1 & 0x1F) + 1) << 2 Add 1 to the extracted value and then multiply by 4
Referenced Data Length 0 0 n/a
Referenced Data Offset 0 0 n/a

With stop flag[edit]

Value Range Expression Exception to simple merging
Proceeding Data Length 0 to StopFlagData Byte1 & StopFlagData None
Referenced Data Length 0 0 n/a
Referenced Data Offset 0 0 n/a


Highest Non-Stop Values (HNSVs)[edit]

The following table explains the bit counts of the 1-byte opcode for each of the 6 valid HNSVs.

Highest Non-Stop Value (HNSV) Bits used for Proceeding Data Length Range of Proceeding Data Length Opcodes attributed with the stop flag
0xFE With stop flag: 0 With stop flag: 0 Highest 1 (The highest 1-byte opcode: 0xFF)
Without stop flag: 5 Without stop flag: 4-124 (steps of 4)
0xFD With stop flag: 1 With stop flag: 0-1 Highest 2
Without stop flag: 4 Without stop flag: 4-120 (steps of 4)
0xFB With stop flag: 2 With stop flag: 0-3 Highest 4
Without stop flag: 3 Without stop flag: 4-112 (steps of 4)
0xF7 With stop flag: 3 With stop flag: 0-7 Highest 8
Without stop flag: 2 Without stop flag: 4-96 (steps of 4)
0xEF With stop flag: 4 With stop flag: 0-15 Highest 16
Without stop flag: 1 Without stop flag: 4-64 (steps of 4)
0xFF With stop flag: 5 With stop flag: 0-31 Highest 32 (All 1-byte opcodes)
Without stop flag: n/a: All 1-byte opcodes have the stop flag at this point


EA's reference implementation uses 0xFB by default, as does The Sims Online.

Reference[edit]

The original RefPack.cpp written by Frank Barchard: http://download.wcnews.com/files/documents/sourcecode/shadowforce/transfer/asommers/mfcapp_src/engine/compress/RefPack.cpp

In The Sims Online, this file was split into refencode.cpp and refdecode.cpp, according to TSOGimexD.dll, although these files have not been leaked.