Falcon 4.0 Forum, Falcon 4 Home, Falcon 4 Campaign, Falcon 4 Cockpits, Falcon 4 Database, Falcon 4 File Formats, Falcon 4 SRTM Terrain, Falcon 4 Terrain, Falcon 4 Textures, Falcon 4 Tools

Lempel-Ziv-Storer-Szymanski (LZSS) is a lossless data compression algorithm, a derivative of LZ77, that was created in 1982 by James Storer and Thomas Szymanski. LZSS was described in article “Data compression via textual substitution” published in Journal of the ACM (pp. 928-951).

LZSS is a dictionary encoding technique. It attempts to replace a string of symbols with a reference to a dictionary location of the same string.

The main difference between LZ77 and LZSS is that in LZ77 the dictionary reference could actually be longer than the string it was replacing. In LZSS, such references are omitted if the length is less than the “break even” point. Furthermore, LZSS uses one-bit flags to indicate whether the next chunk of data is a literal (byte) or a reference to an offset/length pair.

For more information and links, consult:

http://en.wikipedia.org/wiki/Lempel-Ziv-Storer-Szymanski

The following code provides an example implementation in C# that matches the algorithm's implementation details that are used in Falcon.

The code below is intended to be utilitarian, not instructional, and is deliberately obfuscated to mitigate any possible legal concerns. The example code contains two public methods, CompressContent() and UncompressContent(), which will compress or uncompress byte arrays to/from the compressed format that Falcon uses, per the .CAM/.TRN/.TAC file format documentation.

This example implementation relies on the use of unmanged pointers from within the .NET managed environment, and is therefore decorated with “unsafe” keywords on the relevant methods. The use of this code in a Visual Studio project therefore requires the build attributes for the project to be set to “allow unsafe code”.

using System;
using System.Runtime.InteropServices;
 
public static class Lzss
{
    private const int a = 12;
    private const int b = 4;
    private const int c = 0x1000;
    private const int d = 0x10;
    private const int e = 1;
    private const int f = 0x11;
    private const int g = 0x1000;
    private const int h = 0;
    private const int i = 0;
 
    private static int a(int A_0)
    {
        return (A_0 & 0xfff);
    }
 
    private static void a(ref Lzss.a A_0)
    {
        A_0.c[0] = 0;
        A_0.d = 1;
        A_0.f = A_0.e;
        A_0.e = 1;
    }
 
    private static unsafe int a(byte* A_0, ref Lzss.a A_1)
    {
        A_1.i = 0;
        if (A_1.d == 0x100)
        {
            b(A_0, ref A_1);
            A_1.i = 1;
        }
        A_1.d = A_1.d << 1;
        return (A_1.c[0] & (A_1.d >> 1));
    }
 
    private static void a(int A_0, ref Lzss.a A_1)
    {
        if (A_1.b[A_0].a != 0)
        {
            if (A_1.b[A_0].c == 0)
            {
                b(A_0, A_1.b[A_0].b, ref A_1);
            }
            else if (A_1.b[A_0].b == 0)
            {
                b(A_0, A_1.b[A_0].c, ref A_1);
            }
            else
            {
                int num = b(A_0, ref A_1);
                a(num, ref A_1);
                a(A_0, num, ref A_1);
            }
        }
    }
 
    private static int a(int A_0, ref int A_1, ref Lzss.a A_2)
    {
        int num = 0;
        int c = 0;
        int num3 = 0;
        int num4 = 0;
        int b = 0;
        if (A_0 == 0)
        {
            return 0;
        }
        c = A_2.b[0x1000].c;
        num4 = 0;
        while (true)
        {
            for (num = 0; num < 0x11; num++)
            {
                num3 = A_2.a[a((int) (A_0 + num))] - A_2.a[a((int) (c + num))];
                if (num3 != 0)
                {
                    break;
                }
            }
            if (num >= num4)
            {
                num4 = num;
                A_1 = c;
                if (num4 >= 0x11)
                {
                    a(c, A_0, ref A_2);
                    return num4;
                }
            }
            if (num3 >= 0)
            {
                b = A_2.b[c].c;
            }
            else
            {
                b = A_2.b[c].b;
            }
            if (b == 0)
            {
                b = A_0;
                A_2.b[A_0].a = c;
                A_2.b[A_0].c = 0;
                A_2.b[A_0].b = 0;
                return num4;
            }
            c = b;
        }
    }
 
    private static void a(int A_0, int A_1, ref Lzss.a A_2)
    {
        int a = A_2.b[A_0].a;
        if (A_2.b[a].b == A_0)
        {
            A_2.b[a].b = A_1;
        }
        else
        {
            A_2.b[a].c = A_1;
        }
        A_2.b[A_1] = A_2.b[A_0];
        A_2.b[A_2.b[A_1].b].a = A_1;
        A_2.b[A_2.b[A_1].c].a = A_1;
        A_2.b[A_0].a = 0;
    }
 
    private static unsafe int a(int A_0, byte* A_1, ref Lzss.a A_2)
    {
        A_2.c[A_2.e++] = (byte) A_0;
        A_2.c[0] = (byte) (A_2.c[0] | ((byte) A_2.d));
        A_2.d = A_2.d << 1;
        A_2.j = 0;
        if (A_2.d == 0x100)
        {
            A_2.j = 1;
            return c(A_1, ref A_2);
        }
        return 1;
    }
 
    private static unsafe int a(byte* A_0, byte* A_1, int A_2)
    {
        Lzss.a a = new Lzss.a();
        a.a();
        byte* numPtr = A_0;
        b(A_0, ref a);
        A_0++;
        int index = 1;
        while (A_2 != 0)
        {
            byte num3;
            if (Lzss.a(A_0, ref a) != 0)
            {
                if (a.i == 1)
                {
                    A_0++;
                }
                num3 = A_0[0];
                A_0++;
                A_1[0] = num3;
                A_1++;
                A_2--;
                a.a[index] = num3;
                index = Lzss.a((int) (index + 1));
            }
            else
            {
                if (a.i == 1)
                {
                    A_0++;
                }
                int num4 = A_0[0];
                A_0++;
                int num5 = A_0[0];
                A_0++;
                num5 |= (num4 & 15) << 8;
                num4 = num4 >> 4;
                num4++;
                if (num4 < A_2)
                {
                    A_2 -= num4 + 1;
                }
                else
                {
                    A_2 = 0;
                    num4 = A_2 - 1;
                }
                for (int i = 0; i <= num4; i++)
                {
                    num3 = a.a[Lzss.a((int) (num5 + i))];
                    A_1[0] = num3;
                    A_1++;
                    a.a[index] = num3;
                    index = Lzss.a((int) (index + 1));
                }
            }
        }
        ulong num6 = (ulong) ((long) ((A_0 - numPtr) / 1));
        return (int) num6;
    }
 
    private static unsafe int a(int A_0, int A_1, byte* A_2, ref Lzss.a A_3)
    {
        A_3.c[A_3.e] = (byte) (A_1 << 4);
        A_3.c[A_3.e++] = (byte) (A_3.c[A_3.e++] | ((byte) (A_0 >> 8)));
        A_3.c[A_3.e++] = (byte) (A_0 & 0xff);
        A_3.d = A_3.d << 1;
        A_3.j = 0;
        if (A_3.d == 0x100)
        {
            A_3.j = 1;
            return c(A_2, ref A_3);
        }
        return 1;
    }
 
    private static int b(int A_0, ref Lzss.a A_1)
    {
        int b = A_1.b[A_0].b;
        while (A_1.b[b].c != 0)
        {
            b = A_1.b[b].c;
        }
        return b;
    }
 
    private static unsafe void b(byte* A_0, ref Lzss.a A_1)
    {
        A_1.d = 1;
        A_1.c[0] = A_0[0];
    }
 
    private static void b(int A_0, int A_1, ref Lzss.a A_2)
    {
        A_2.b[A_1].a = A_2.b[A_0].a;
        if (A_2.b[A_2.b[A_0].a].c == A_0)
        {
            A_2.b[A_2.b[A_0].a].c = A_1;
        }
        else
        {
            A_2.b[A_2.b[A_0].a].b = A_1;
        }
        A_2.b[A_0].a = 0;
    }
 
    private static unsafe int b(byte* A_0, byte* A_1, int A_2)
    {
        byte num2;
        Lzss.a a = new Lzss.a();
        a.a();
        a.h = 0;
        a.g = A_2;
        Lzss.a(ref a);
        int num4 = 1;
        int num = 0;
        while (num < 0x11)
        {
            num2 = A_0[0];
            A_0++;
            A_2--;
            if (A_2 < 0)
            {
                break;
            }
            a.a[num4 + num] = num2;
            num++;
        }
        int num3 = num;
        c(num4, ref a);
        int num6 = 0;
        int num7 = 0;
        while (num3 > 0)
        {
            int num5;
            if (num6 > num3)
            {
                num6 = num3;
            }
            if (num6 <= 1)
            {
                num5 = 1;
                if (Lzss.a(a.a[num4], A_1, ref a) == 0)
                {
                    return 0;
                }
                if (a.j != 0)
                {
                    A_1 += (byte*) a.f;
                }
            }
            else
            {
                if (Lzss.a(num7, num6 - 2, A_1, ref a) == 0)
                {
                    return 0;
                }
                if (a.j != 0)
                {
                    A_1 += (byte*) a.f;
                }
                num5 = num6;
            }
            for (num = 0; num < num5; num++)
            {
                Lzss.a(Lzss.a((int) (num4 + 0x11)), ref a);
                num2 = A_0[0];
                A_2--;
                if (A_2 < 0)
                {
                    num3--;
                }
                else
                {
                    A_0++;
                    a.a[Lzss.a((int) (num4 + 0x11))] = num2;
                }
                num4 = Lzss.a((int) (num4 + 1));
                if (num3 != 0)
                {
                    num6 = Lzss.a(num4, ref num7, ref a);
                }
            }
        }
        if (a.j == 0)
        {
            c(A_1, ref a);
        }
        return a.h;
    }
 
    private static void c(int A_0, ref Lzss.a A_1)
    {
        for (int i = 0; i < 0x1001; i++)
        {
            A_1.b[i].a = 0;
            A_1.b[i].c = 0;
            A_1.b[i].b = 0;
        }
        A_1.b[0x1000].c = A_0;
        A_1.b[A_0].a = 0x1000;
        A_1.b[A_0].c = 0;
        A_1.b[A_0].b = 0;
    }
 
    private static unsafe int c(byte* A_0, ref Lzss.a A_1)
    {
        if (A_1.e != 1)
        {
            for (int i = 0; i < A_1.e; i++)
            {
                A_0[i] = A_1.c[i];
            }
            A_1.h += (int) A_1.e;
            a(ref A_1);
        }
        return 1;
    }
 
    public static unsafe byte[] CompressContent(byte[] uncompressedContent)
    {
        byte[] destinationArray = new byte[uncompressedContent.Length + 100];
        Array.Copy(uncompressedContent, destinationArray, uncompressedContent.Length);
        int length = 0;
        fixed (byte* numRef = uncompressedContent)
        {
            fixed (byte* numRef2 = destinationArray)
            {
                length = b(numRef, numRef2, uncompressedContent.Length);
            }
        }
        byte[] buffer2 = new byte[length];
        Array.Copy(destinationArray, buffer2, length);
        return buffer2;
    }
 
    public static unsafe byte[] UncompressContent(byte[] compressedContent, int uncompressedSize)
    {
        byte[] destinationArray = new byte[compressedContent.Length + 100];
        Array.Copy(compressedContent, destinationArray, compressedContent.Length);
        byte[] sourceArray = new byte[uncompressedSize + 0x400];
        fixed (byte* numRef = sourceArray)
        {
            fixed (byte* numRef2 = destinationArray)
            {
                int num = a(numRef2, numRef, uncompressedSize);
            }
        }
        byte[] buffer3 = new byte[uncompressedSize];
        Array.Copy(sourceArray, buffer3, uncompressedSize);
        return buffer3;
    }
 
    [StructLayout(LayoutKind.Sequential)]
    private struct a
    {
        public byte[] a;
        public Lzss.b[] b;
        public byte[] c;
        public int d;
        public uint e;
        public uint f;
        public int g;
        public int h;
        public int i;
        public int j;
        public void a()
        {
            this.a = new byte[0x1000];
            this.b = new Lzss.b[0x1001];
            this.c = new byte[0x11];
        }
    }
 
    [StructLayout(LayoutKind.Sequential)]
    private struct b
    {
        public int a;
        public int b;
        public int c;
    }
}