DBPF/Compression

From SimsWiki
< DBPF(Redirected from DBPF Compression)
Jump to: navigation, search

Contents

Overview

The idea behind the compression is to reuse previously decoded strings. For example, if the word "heureka" occurs twice in a file, the second occurrence would be encoded by pointing to the first, thus lowering the size of the file. Please note that while this compression is most commonly found in DBPF archives, it is used by The Sims Online in FAR (version 3) archives.

The compression is done by defining control characters that tell three things:

  1. How many characters of plain text that follow should be appended to the output.
  2. How many characters should be read from the already decoded text (and appended to the output)
  3. Where to read the characters from in the already decoded text.

Thus, the algorithm to decompress these files goes like this:

Read the 9 byte header, which is formatted like so:

Offset 00 - Compressed Size of file
Offset 04 - Compression ID (0x10FB) (QFS Compression.)
Offset 06 - Uncompressed Size of file

Offset 09 is the start of the actual compressed file data, which is handled like so:

{ 
	- Read the next control character. 
	- Depending on the control character, read 0-3 more bytes that are a part of the control character.
	- Inspect the control character.  From this, find out how many characters should be read and where from.
	- Read 0-n characters from source and append them to the output. (n being the "how many" data from above)
	- Copy 0-n characters from somewhere in the output to the end of the output. (n in this case is the 
} 

Control Characters

There are 4 types of control characters. These are used with different restrictions on how many characters that can be read and from how far behind these can be read. The following conventions are used to describe them:

CC length
Length of control character.
Num plain text
Number of characters immediately after the control character that should be read and appended to output.
Num to copy
Number of chars that should be copied from somewhere in the already decoded output and added to the end of the output.
Copy offset
Where to start reading characters when copying from somewhere in the already decoded output.
This is given as an offset from the current end of the output buffer, i.e. an offset of 0 means that you should copy the last character in the output and append it to the output. And offset of 1 means that you should copy the second-to-last character.
byte0
first byte of control character.
Bits
Bits of the control character.
  • p - num plain text
  • c - num to copy
  • o - copy offset
  • i - identifier.

Note: It can sometimes be confusing when a control character states that you should copy for example 10 characters 5 steps from the end of the output. Clearly, you cannot read more than 5 characters before you reach the end of the buffer. The solution is to read and write one character at the time. Each time you read a character you copy it to the end thereby increasing the size of the output. By doing this, even offset 0 is possible and would result in duplicating the last character a number of times. This is utilized by the compression to recreate repeating text, for example bars of repeating dashes.

This is the simplest form of control character. The only thing it does is tell how many plain text characters follow. The formula for this is: (C - 0x7F) * 4. Thus a value of 0xE0 means that you should read 4 characters of plain text and append to the output.

0x00 - 0x7F

CC length: 2 bytes
Num plain text: byte0 & 0x03
Num to copy: ( (byte0 & 0x1C) > > 2) + 3
Copy offset: ( (byte0 & 0x60) < < 3) + byte1 + 1
Bits: 0oocccpp oooooooo
Num plain text limit: 0-3
Num to copy limit: 3-11
Maximum Offset: 1023


0x80 - 0xBF

CC length: 3 bytes
Num plain text: ((byte1 & 0xC0) > > 6 ) & 0x03
Num to copy: (byte0 & 0x3F) + 4
Copy offset: ( (byte1 & 0x3F) < < 8 ) + byte2 + 1
Bits: 10cccccc ppoooooo oooooooo
Num plain text limit: 0-3
Num to copy limit: 4-67
Maximum Offset: 16383


0xC0 - 0xDF

This format differs depending on the game.

Sims 2 and The Sims Online

CC length: 4 bytes
Num plain text: byte0 & 0x03
Num to copy: ( (byte0 & 0x0C) < < 6 )  + byte3 + 5
Copy offset: ((byte0 & 0x10) < < 12 ) + (byte1 < < 8 ) + byte2 + 1
Bits: 110occpp oooooooo oooooooo cccccccc
Num plain text limit: 0-3
Num to copy limit: 5-1028
Maximum Offset: 131072

SimCity 4

CC length: 4 bytes
Num plain text: byte0 & 0x03
Num to copy: ( (byte0 & 0x1C) < < 6 )  + byte3 + 5
Copy offset: (byte1 < < 8) + byte2
Bits: 110cccpp oooooooo oooooooo cccccccc
Num plain text limit: 0-3
Num to copy limit: 5-2047
Maximum Offset: 65535

0xE0 - 0xFC

CC length: 1 byte 
Num plain text: ((byte0 & 0x1F) < < 2 )
Num to copy: 0 
Copy offset: - 
Bits: 111ppppp 
Num plain text limit: 4-128 
Num to copy limit: 0 
Maximum Offset: - 

0xFD - 0xFF

CC length: 1 byte 
Num plain text: (byte0 & 0x03)
Num to copy: 0 
Copy offset: - 
Bits: 111ppppp 
Num plain text limit: 4-128 
Num to copy limit: 0 
Maximum Offset: - 

Example Code

This is written in PHP, converted from Perl code by dmchess [1]

// First, we read in the length of the total compressed data
// read_UL4 is a php function in my DBPF class that grabs the next 4 bytes and uses unpack to convert to a integer
$len = $this->read_UL4($handle);
// Read the next 5 bytes (they are useless afaik)
$garbagedata = fread($handle, 5);
// Decompress the chunk
// We do $len - 9 here becuase we are ignoring the first 9 bytes of the chunk (4 for the length value itself, 5 for other data)
// See later for a description of $this->decompress
$data = $this->decompress($handle, $len - 9);
// ** Internally used I/O functions
// Reads a 4 byte unsigned integer
/*
       Used internally by the class to read a C/C++
       "unsigned long" (a 4 byte unsigned integer)
       from an open file
       $fh - the file handle from which to read
       returns - returns the value read; has no error return
*/
function read_UL4($fh)
{
       $d = fread($fh, 4);
       $a = unpack("Vn", $d);
       return $a["n"];
}
// Reads a 2 byte unsigned integer
/*
        Used internally by the class to read a C/C++
       "unsigned short" (a 2 byte unsigned integer)
       from an open file
       $fh - the file handle from which to read
       returns - returns the value read; has no error return
*/
function read_UL2($fh)
{
       $d = fread($fh, 2);
       $a = unpack("vn", $d);
       return $a["n"];
}
// Reads a 1 byte unsigned integer
/*
       Used internally by the class to read a C/C++
       "unsigned char" (a 1 byte unsigned integer)
       from an open file
       $fh - the file handle from which to read
       returns - returns the value read; has no error return
*/
function read_UL1($fh)
{
       $d = fread($fh, 1);
       $a = unpack("Cn", $d);
       return $a["n"];
}
       // Decompresses string
       /*
               PHP DBPF decompression by Delphy
               Thanks to dmchess (http://hullabaloo.simshost.com/forum/viewtopic.php?t=6578&postdays=0&postorder=asc)
               for the Perl code that I used for this
               $handle - file handle for reading
               $len - length of compressed string
       */
       function decompress($handle, $len) {
               $buf = ;
               $answer = "";
               $answerlen = 0;
               $numplain = "";
               $numcopy = "";
               $offset = "";

Main loop:

               for (;$len>0;) {
                       $cc = $this->read_UL1($handle);
                       $len -= 1;
               //      printf("      Control char is %02x, len remaining is %08x. \n",$cc,$len);
                       if ($cc >= 252): // 0xFC
                               $numplain = $cc & 0x03;
                               if ($numplain > $len) { $numplain = $len; }
                               $numcopy = 0;
                               $offset = 0;
                       elseif ($cc >= 224): // 0xE0
                               $numplain = ($cc - 0xdf) << 2;
                               $numcopy = 0;
                               $offset = 0;
                       elseif ($cc >= 192): // 0xC0
                               $len -= 3;
                               $byte1 = $this->read_UL1($handle);
                               $byte2 = $this->read_UL1($handle);
                               $byte3 = $this->read_UL1($handle);
                               $numplain = $cc & 0x03;
                               $numcopy = (($cc & 0x0c) <<6) + 5 + $byte3;
                               $offset = (($cc & 0x10) << 12 ) + ($byte1 << 8) + $byte2;
                       elseif ($cc >= 128): // 0x80
                               $len -= 2;
                               $byte1 = $this->read_UL1($handle);
                               $byte2 = $this->read_UL1($handle);
                               $numplain = ($byte1 & 0xc0) >> 6;
                               $numcopy = ($cc & 0x3f) + 4;
                               $offset = (($byte1 & 0x3f) << 8) + $byte2;
                       else:
                               $len -= 1;
                               $byte1 = $this->read_UL1($handle);
                               $numplain = ($cc & 0x03);
                               $numcopy = (($cc & 0x1c) >> 2) + 3;
                               $offset = (($cc & 0x60) << 3) + $byte1;
                       endif;
                       $len -= $numplain;

This section basically copies the parts of the string to the end of the buffer:

                       if ($numplain > 0) {
                               $buf = fread($handle, $numplain);
                               $answer = $answer.$buf;
                       }
                       $fromoffset = strlen($answer) - ($offset + 1);  # 0 == last char
                       for ($i=0;$i<$numcopy;$i++) {
                               $answer = $answer.substr($answer,$fromoffset+$i,1);
                       }
                       $answerlen += $numplain;
                       $answerlen += $numcopy;
               }

Return the decompressed string back:

               return $answer;
       }

Commented code (C#) from Project Dollhouse, ported from DBPF4J;

   public class Decompresser
   {
       private long m_CompressedSize = 0;
       private long m_DecompressedSize = 0;
       private bool m_Compressed = false;
       public long DecompressedSize
       {
           get { return m_DecompressedSize; }
           set { m_DecompressedSize = value; }
       }
       public long CompressedSize
       {
           get { return m_CompressedSize; }
           set { m_CompressedSize = value; }
       }
       /// <summary>
       ///  Copies data from source to destination array.
/// The copy is byte by byte from srcPos to destPos and given length. /// </summary> /// <param name="Src">The source array.</param> /// <param name="SrcPos">The source Position.</param> /// <param name="Dest">The destination array.</param> /// <param name="DestPos">The destination Position.</param> /// <param name="Length">The length.</param> private void ArrayCopy2(byte[] Src, int SrcPos, ref byte[] Dest, int DestPos, long Length) { if (Dest.Length < DestPos + Length) { byte[] DestExt = new byte[(int)(DestPos + Length)]; Array.Copy(Dest, 0, DestExt, 0, Dest.Length); Dest = DestExt; }
           for (int i = 0; i < Length/* - 1*/; i++)
           {
               /*if (SrcPos == Src.Length || (SrcPos + i) == Src.Length)
                   break;*/
               Dest[DestPos + i] = Src[SrcPos + i];
           }
       }
       /// <summary>
       /// Copies data from array at destPos-srcPos to array at destPos.
       /// </summary>
       /// <param name="array">The array.</param>
       /// <param name="srcPos">The Position to copy from (reverse from end of array!)</param>
       /// <param name="destPos">The Position to copy to.</param>
       /// <param name="length">The length of data to copy.</param>
       private void OffsetCopy(ref byte[] array, int srcPos, int destPos, long length)
       {
           srcPos = destPos - srcPos;
           if (array.Length < destPos + length)
           {
               byte[] NewArray = new byte[(int)(destPos + length)];
               Array.Copy(array, 0, NewArray, 0, array.Length);
               array = NewArray;
           }
           for (int i = 0; i < length /*- 1*/; i++)
           {
               array[destPos + i] = array[srcPos + i];
           }
       }
       public byte[] Decompress(byte[] Data)
       {
           m_Compressed = false;
           MemoryStream MemData = new MemoryStream(Data);
           BinaryReader Reader = new BinaryReader(MemData);
           if (Data.Length > 6)
           {
               /*m_CompressedSize = Reader.ReadUInt32();
               int Signature = Reader.ReadUInt16();
               //If the data isn't compressed.
               m_DecompressedSize = m_CompressedSize;
               if (Signature == 0xFB10)
               {
                   short A = (short)Reader.ReadByte();
                   short B = (short)Reader.ReadByte();
                   short C = (short)Reader.ReadByte();
                   m_DecompressedSize = A * 65536 + B * 256 + C;*/
               byte[] DecompressedData = new byte[(int)m_DecompressedSize];
               int DataPos = 0;
               m_Compressed = true;
               //int Pos = 9;
               int Pos = 0;
               long Control1 = 0;
               while (Control1 != 0xFC && Pos < Data.Length)
               {
                   Control1 = Data[Pos];
                   Pos++;
                   if (Pos == Data.Length)
                       break;
                   if (Control1 >= 0 && Control1 <= 127)
                   {
                       // 0x00 - 0x7F
                       long control2 = Data[Pos];
                       Pos++;
                       long numberOfPlainText = (Control1 & 0x03);
                       ArrayCopy2(Data, Pos, ref DecompressedData, DataPos, numberOfPlainText);
                       DataPos += (int)numberOfPlainText;
                       Pos += (int)numberOfPlainText;
                       if (DataPos == (DecompressedData.Length))
                           break;
                       int offset = (int)(((Control1 & 0x60) << 3) + (control2) + 1);
                       long numberToCopyFromOffset = ((Control1 & 0x1C) >> 2) + 3;
                       OffsetCopy(ref DecompressedData, offset, DataPos, numberToCopyFromOffset);
                       DataPos += (int)numberToCopyFromOffset;
                       if (DataPos == (DecompressedData.Length))
                           break;
                   }
                   else if ((Control1 >= 128 && Control1 <= 191))
                   {
                       // 0x80 - 0xBF
                       long control2 = Data[Pos];
                       Pos++;
                       long control3 = Data[Pos];
                       Pos++;
                       long numberOfPlainText = (control2 >> 6) & 0x03;
                       ArrayCopy2(Data, Pos, ref DecompressedData, DataPos, numberOfPlainText);
                       DataPos += (int)numberOfPlainText;
                       Pos += (int)numberOfPlainText;
                       if (DataPos == (DecompressedData.Length))
                           break;
                       int offset = (int)(((control2 & 0x3F) << 8) + (control3) + 1);
                       long numberToCopyFromOffset = (Control1 & 0x3F) + 4;
                       OffsetCopy(ref DecompressedData, offset, DataPos, numberToCopyFromOffset);
                       DataPos += (int)numberToCopyFromOffset;
                       if (DataPos == (DecompressedData.Length))
                           break;
                   }
                   else if (Control1 >= 192 && Control1 <= 223)
                   {
                       // 0xC0 - 0xDF
                       long numberOfPlainText = (Control1 & 0x03);
                       long control2 = Data[Pos];
                       Pos++;
                       long control3 = Data[Pos];
                       Pos++;
                       long control4 = Data[Pos];
                       Pos++;
                       ArrayCopy2(Data, Pos, ref DecompressedData, DataPos, numberOfPlainText);
                       DataPos += (int)numberOfPlainText;
                       Pos += (int)numberOfPlainText;
                       if (DataPos == (DecompressedData.Length))
                           break;
                       int offset = (int)(((Control1 & 0x10) << 12) + (control2 << 8) + (control3) + 1);
                       long numberToCopyFromOffset = ((Control1 & 0x0C) << 6) + (control4) + 5;
                       OffsetCopy(ref DecompressedData, offset, DataPos, numberToCopyFromOffset);
                       DataPos += (int)numberToCopyFromOffset;
                       if (DataPos == (DecompressedData.Length))
                           break;
                   }
                   else if (Control1 >= 224 && Control1 <= 251)
                   {
                       // 0xE0 - 0xFB
                       long numberOfPlainText = ((Control1 & 0x1F) << 2) + 4;
                       ArrayCopy2(Data, Pos, ref DecompressedData, DataPos, numberOfPlainText);
                       DataPos += (int)numberOfPlainText;
                       Pos += (int)numberOfPlainText;
                       if (DataPos == (DecompressedData.Length))
                           break;
                   }
                   else
                   {
                       long numberOfPlainText = (Control1 & 0x03);
                       ArrayCopy2(Data, Pos, ref DecompressedData, DataPos, numberOfPlainText);
                       DataPos += (int)numberOfPlainText;
                       Pos += (int)numberOfPlainText;
                       if (DataPos == (DecompressedData.Length))
                           break;
                   }
               }
               return DecompressedData;
           }
           //}
           //No data to decompress
           return Data;
       }
   }

See Also

Personal tools
Namespaces

Variants
Actions
Navigation
game select
Toolbox