Modifying compression for Sim City 4

[Afro]

Hey guys!
I have some compression code I ported from Java. I think it is meant to compress in a manner like 'The Sims 2' does it, but I want it to compress like 'Sim City 4'. I know there are some subtle changes to the algorithm, but I'm not really that familiar with the algorithm.
Could anyone help me out?

Code:

        /// <summary>
        /// Copies data from source to destination array.<br>
    /// 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; 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; i++)
            {
                array[destPos + i] = array[srcPos + i];
            }
        }

        /// <summary>
        /// Writes a uint to a binary array.
        /// </summary>
        /// <param name="Data">The binary array.</param>
        /// <param name="Value">The uint value to write.</param>
        /// <param name="Position">The position to write to within the array.</param>
        private void WriteUInt(ref byte[] Data, uint Value, long Position)
        {
            MemoryStream MemStream = new MemoryStream(Data);
            BinaryWriter Writer = new BinaryWriter(MemStream);
           
            Writer.BaseStream.Seek(Position, SeekOrigin.Begin);
            Writer.Write(Value);
            Writer.Flush();

            Data = MemStream.ToArray();
            Writer.Close();
        }

        /// <summary>
        /// Writes a ushort to a binary array.
        /// </summary>
        /// <param name="Data">The binary array.</param>
        /// <param name="Value">The ushort value to write.</param>
        /// <param name="Position">The position to write to within the array.</param>
        private void WriteUShort(ref byte[] Data, ushort Value, long Position)
        {
            MemoryStream MemStream = new MemoryStream(Data);
            BinaryWriter Writer = new BinaryWriter(MemStream);

            Writer.BaseStream.Seek(Position, SeekOrigin.Begin);
            Writer.Write(Value);
            Writer.Flush();

            Data = MemStream.ToArray();
            Writer.Close();
        }

        private void WriteReversedArray(ref byte[] Data, byte[] Ar, long Position)
        {
            MemoryStream MemStream = new MemoryStream(Data);
            BinaryWriter Writer = new BinaryWriter(MemStream);

            Writer.BaseStream.Seek(Position, SeekOrigin.Begin);
            Array.Reverse(Ar);
            Writer.Write(Ar);
            Writer.Flush();

            Data = MemStream.ToArray();
            Writer.Close();
        }

        /// <summary>
        /// Writes the first 9 bytes of the RefPak header to the supplied
        /// array of compressed data.
        /// </summary>
        /// <param name="Data">The array to write to.</param>
        /// <param name="DecompressedSize">The decompressed size of the data.</param>
        /// <param name="CompressedSize">The compressed size of the data. Does NOT include header size.</param>
        private void WriteFirstHeader(ref byte[] Data, uint DecompressedSize, uint CompressedSize)
        {
            MemoryStream MemStream = new MemoryStream(Data);
            BinaryWriter Writer = new BinaryWriter(MemStream);

            Writer.Write((byte)0x01);       //Indicates this data is compressed.

            byte[] Decompressed = new byte[3];
            Decompressed = BitConverter.GetBytes(DecompressedSize);
           
            Writer.Write(Decompressed);
            Writer.Write((byte)0x00);       //Out Of Bounds character.
            Writer.Write(CompressedSize);   //Stream body size. Does NOT include size of RefPak header.
            Writer.Flush();

            Data = MemStream.ToArray();
            Writer.Close();
        }

        /// <summary>
        /// Gets a ushort from a binary array.
        /// </summary>
        /// <param name="Data">The binary array.</param>
        /// <returns>The ushort.</returns>
        ushort GetUShort(byte[] Data)
        {
            ushort Value;

            MemoryStream MemStream = new MemoryStream(Data);
            BinaryReader Reader = new BinaryReader(MemStream);

            Value = Reader.ReadUInt16();

            Reader.Close();

            return Value;
        }

        /// <summary>
        /// Compress the decompressed data.
        /// </summary>
        /// <param name="dData">The decompressed data.</param>
        /// <returns>The compressed data.</returns>
    public byte[] Compress(byte[] dData)
        {
    // if data is big enough for compress
            if (dData.Length > 6)
            {
                // check, if data already compressed
                uint signature = GetUShort(dData);//(uint)ToValue(dData, 0x04, 2, false);

                if (signature != m_MAGICNUMBER_QFS)
                {
                    // some Compression Data
                    const int MAX_OFFSET = 0x20000;
                    const int MAX_COPY_COUNT = 0x404;
                    // used to finetune the lookup (small values increase the
                    // compression for Big Files)
                    const int QFS_MAXITER = 0x80;

                    // contains the latest offset for a combination of two
                    // characters
                    Dictionary<int, ArrayList> CmpMap2 = new Dictionary<int, ArrayList>();

                    // will contain the compressed data (maximal size =
                    // uncompressedSize+MAX_COPY_COUNT)
                    byte[] cData = new byte[dData.Length + MAX_COPY_COUNT];

                    // init some vars
                    int writeIndex = 0;  // Header for FAR3 is twice as long as for DBPF
                    int lastReadIndex = 0;
                    ArrayList indexList = null;
                    int copyOffset = 0;
                    int copyCount = 0;
                    int index = -1;
                    bool end = false;

                    // begin main compression loop
                    while (index < dData.Length - 3)
                    {
                        // get all Compression Candidates (list of offsets for all
                        // occurances of the current 3 bytes)
                        do
                        {
                            index++;

                            if (index == dData.Length - 2)
                            {
                                end = true;
                                break;
                            }
                            int mapindex = (dData[index] + (dData[index + 1] << 8) + (dData[index + 2] << 16));

                            try
                            {
                                indexList = CmpMap2[mapindex];
                            }
                            catch (Exception)
                            {
                                if (indexList == null)
                                {
                                    indexList = new ArrayList();
                                    CmpMap2.Add(mapindex, indexList);
                                }
                            }

                            indexList.Add(index);
                        } while (index < lastReadIndex);

                        if (end)
                        {
                            break;
                        }

                        // find the longest repeating byte sequence in the index
                        // List (for offset copy)
                        int offsetCopyCount = 0;
                        int loopcount = 1;

                        while ((loopcount < indexList.Count) && (loopcount < QFS_MAXITER))
                        {
                            int foundindex = (int)indexList[(indexList.Count - 1) - loopcount];
                           
                            if ((index - foundindex) >= MAX_OFFSET)
                                break;
                           
                            loopcount++;
                            copyCount = 3;
                            while ((dData.Length > index + copyCount) && (dData[index + copyCount]
                                == dData[foundindex + copyCount]) && (copyCount < MAX_COPY_COUNT))
                            {
                                copyCount++;
                            }

                            if (copyCount > offsetCopyCount)
                            {
                                offsetCopyCount = copyCount;
                                copyOffset = index - foundindex;
                            }
                        }

                        // check if we can compress this
                        // In FSH Tool stand additionally this:
                        if (offsetCopyCount > dData.Length - index)
                        {
                            offsetCopyCount = index - dData.Length;
                        }
                        if (offsetCopyCount <= 2)
                        {
                            offsetCopyCount = 0;
                        }
                        else if ((offsetCopyCount == 3) && (copyOffset > 0x400))
                        { // 1024
                            offsetCopyCount = 0;
                        }
                        else if ((offsetCopyCount == 4) && (copyOffset > 0x4000))
                        { // 16384
                            offsetCopyCount = 0;
                        }

                        // this is offset-compressable? so do the compression
    if (offsetCopyCount > 0)
                        {
    // plaincopy

    // In FSH Tool stand this (A):
    while (index - lastReadIndex >= 4)
                            {
    copyCount = (index - lastReadIndex) / 4 - 1;
   
                                if (copyCount > 0x1B)
    copyCount = 0x1B;

    cData[writeIndex++] = (byte) (0xE0 + copyCount);
    copyCount = 4 * copyCount + 4;

    ArrayCopy2(dData, lastReadIndex, ref cData, writeIndex, copyCount);
    lastReadIndex += copyCount;
    writeIndex += copyCount;
    }
    // while ((index - lastReadIndex) > 3) {
    // copyCount = (index - lastReadIndex);
    // while (copyCount > 0x71) {
    // copyCount -= 0x71;
    // }
    // copyCount = copyCount & 0xfc;
    // int realCopyCount = (copyCount >> 2);
    // cData[writeIndex++] = (short) (0xdf + realCopyCount);
    // arrayCopy2(dData, lastReadIndex, cData, writeIndex,
    // copyCount);
    // writeIndex += copyCount;
    // lastReadIndex += copyCount;
    //
                        }

                        // offsetcopy
                        copyCount = index - lastReadIndex;
                        copyOffset--;

                        if ((offsetCopyCount <= 0x0A) && (copyOffset < 0x400))
                        {
                            cData[writeIndex++] = (byte)(((copyOffset >> 8) << 5)
                                    + ((offsetCopyCount - 3) << 2) + copyCount);
                            cData[writeIndex++] = (byte)(copyOffset & 0xff);
                        }
                        else if ((offsetCopyCount <= 0x43) && (copyOffset < 0x4000))
                        {
                            cData[writeIndex++] = (byte)(0x80 + (offsetCopyCount - 4));
                            cData[writeIndex++] = (byte)((copyCount << 6) + (copyOffset >> 8));
                            cData[writeIndex++] = (byte)(copyOffset & 0xff);
                        }
                        else if ((offsetCopyCount <= MAX_COPY_COUNT) && (copyOffset < MAX_OFFSET))
                        {
                            cData[writeIndex++] = (byte)(0xc0 + ((copyOffset >> 16) << 4)
                                + (((offsetCopyCount - 5) >> 8) << 2) + copyCount);
                            cData[writeIndex++] = (byte)((copyOffset >> 8) & 0xff);
                            cData[writeIndex++] = (byte)(copyOffset & 0xff);
                            cData[writeIndex++] = (byte)((offsetCopyCount - 5) & 0xff);
                        }
                        // else {
                        // copyCount = 0;
                        // offsetCopyCount = 0;
                        // }

                        // do the offset copy
                        ArrayCopy2(dData, lastReadIndex, ref cData, writeIndex, copyCount);
                        writeIndex += copyCount;
                        lastReadIndex += copyCount;
                        lastReadIndex += offsetCopyCount;
                    }

                    // add the End Record
                    index = dData.Length;
                    // in FSH Tool stand the same as above (A)
                    while (index - lastReadIndex >= 4)
                    {
                        copyCount = (index - lastReadIndex) / 4 - 1;
                       
                        if (copyCount > 0x1B)
                            copyCount = 0x1B;
                       
                        cData[writeIndex++] = (byte)(0xE0 + copyCount);
                        copyCount = 4 * copyCount + 4;

                        ArrayCopy2(dData, lastReadIndex, ref cData, writeIndex, copyCount);
                        lastReadIndex += copyCount;
                        writeIndex += copyCount;
                    }

                    // lastReadIndex = Math.min(index, lastReadIndex);
                    // while ((index - lastReadIndex) > 3) {
                    // copyCount = (index - lastReadIndex);
                    // while (copyCount > 0x71) {
                    // copyCount -= 0x71;
                    // }
                    // copyCount = copyCount & 0xfc;
                    // int realCopyCount = (copyCount >> 2);
                    // cData[writeIndex++] = (short) (0xdf + realCopyCount);
                    // arrayCopy2(dData, lastReadIndex, cData, writeIndex,
                    // copyCount);
                    // writeIndex += copyCount;
                    // lastReadIndex += copyCount;
                    // }
                    copyCount = index - lastReadIndex;
                    cData[writeIndex++] = (byte)(0xfc + copyCount);
                    ArrayCopy2(dData, lastReadIndex, ref cData, writeIndex, copyCount);
                    writeIndex += copyCount;
                    lastReadIndex += copyCount;

                    WriteFirstHeader(ref cData, (uint)dData.Length, (uint)(writeIndex));

                    // write the header for the compressed data
                    // set the compressed size
                    //ToArray(writeIndex, ref cData, 0x00, 4);
                    WriteUInt(ref cData, (uint)(writeIndex), 9);
                    m_CompressedSize = writeIndex;
                    // set the MAGICNUMBER
                    //ToArray(m_MAGICNUMBER_QFS, ref cData, 0x04, 2);
                    WriteUShort(ref cData, (ushort)m_MAGICNUMBER_QFS, 13);
                    // set the decompressed size
                    byte[] revData = new byte[3];
                    //ToArray(dData.Length, ref revData, 0x00, 3);

                    byte[] Tmp = BitConverter.GetBytes(dData.Length);
                    Buffer.BlockCopy(Tmp, 0, revData, 0, 3);

                    /*for (int j = 0; j < (revData.Length - 1); j++)
                        cData[j + 15] = revData[2 - j];*/
                    WriteReversedArray(ref cData, revData, 15);

                    this.m_DecompressedSize = dData.Length;
                    m_Compressed = false;
                   
                    if (m_CompressedSize < m_DecompressedSize)
                        m_Compressed = true;

                    byte[] retData = new byte[writeIndex + 18];
                    Array.Copy(cData, 0, retData, 0, writeIndex + 18);
                   
                    return retData;
                }
            }

            return dData;
        }

Here are the differences as stated by SimsWiki:

The Sims 2

Code:

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

Sim City 4

Code:

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

[J. M. Pescado]

I have no idea what this is from or what it does. Describe the original function of the program and what it is compressing.

[Afro]

This is RefPak/QFS compression, used by Sim City 4, The Sims 2, Spore and The Sims 3. Although the one used for Spore and The Sims 3 is modified, AFAIK.

I found out the first thing I had to change to make it comply with Sim City 4 were these values:

Code:

                    // some Compression Data
                    //const int MAX_OFFSET = 0x20000;
                    const int MAX_OFFSET = 65535;
                    //const int MAX_COPY_COUNT = 0x404;
                    const int MAX_COPY_COUNT = 2047;

But that's not enough. You have to change the compression code itself, too.

[J. M. Pescado]

What is a "RefPak"? What kind of files are these? If you're dealing with DBPF format and compression, look over here. I have no idea what that gobbledygook you're using is.

[Afro]

What you just gave me was written in C++. I also highly suspect that it was coded for 'The Sims 2'.
RefPak/QFS is the compression algorithm used by 'Sim City 4', 'The Sims 2', 'Spore' and 'The Sims 3' as explained in the original post (it is actually an internal EA algorithm, as it appears in some 'Need for Speed' and 'Command and Conquer' games too).

My code is written in C#. Honestly, why are you complaining? It is almost like straight C.
Would it be better if I posted the original Java code?

Just to emphasize the original problem: I'm looking for someone to help me recode my code so that it compresses in a way understood by 'Sim City 4', not 'The Sims 2'.

[J. M. Pescado]

What you just gave me was written in C++. I also highly suspect that it was coded for 'The Sims 2'.

Yes, yes it was. But I adapted it to TS3, so it may be the droid you're looking for. Yours, on the other hand, does godknowswhat.

My code is written in C#. Honestly, why are you complaining? It is almost like straight C.
Would it be better if I posted the original Java code?

Yes, but WHO MADE IT? WHERE DID IT COME FROM? WHAT DOES IT DO? The code I linked compresses packages. What does yours do?

Just to emphasize the original problem: I'm looking for someone to help me recode my code so that it compresses in a way understood by 'Sim City 4', not 'The Sims 2'.

Yes, but this is a Sims forum. We don't know much about SC4 and its formats. We do have example code pertaining to the general compression system of .package files, but I have no idea what the corresponding analogue in SC4 is. Maybe you should try an SC4 forum for this?