Add FST library

1 files changed, 528 insertions, 0 deletions

diff --git a/libs/fst/fastlz.cc b/libs/fst/fastlz.cc
new file mode 100644
index 000000000..68bda3346
--- /dev/null
+++ b/libs/fst/fastlz.cc
@@ -0,0 +1,528 @@
+/*
+  FastLZ - lightning-fast lossless compression library
+
+  Copyright (C) 2007 Ariya Hidayat (ariya@kde.org)
+  Copyright (C) 2006 Ariya Hidayat (ariya@kde.org)
+  Copyright (C) 2005 Ariya Hidayat (ariya@kde.org)
+
+  Permission is hereby granted, free of charge, to any person obtaining a copy
+  of this software and associated documentation files (the "Software"), to deal
+  in the Software without restriction, including without limitation the rights
+  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+  copies of the Software, and to permit persons to whom the Software is
+  furnished to do so, subject to the following conditions:
+
+  The above copyright notice and this permission notice shall be included in
+  all copies or substantial portions of the Software.
+
+  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+  THE SOFTWARE.
+
+  SPDX-License-Identifier: MIT
+*/
+
+#include "fastlz.h"
+
+#if !defined(FASTLZ__COMPRESSOR) && !defined(FASTLZ_DECOMPRESSOR)
+
+/*
+ * Always check for bound when decompressing.
+ * Generally it is best to leave it defined.
+ */
+#define FASTLZ_SAFE
+
+/*
+ * Give hints to the compiler for branch prediction optimization.
+ */
+#if defined(__GNUC__) && (__GNUC__ > 2)
+#define FASTLZ_EXPECT_CONDITIONAL(c) (__builtin_expect((c), 1))
+#define FASTLZ_UNEXPECT_CONDITIONAL(c) (__builtin_expect((c), 0))
+#else
+#define FASTLZ_EXPECT_CONDITIONAL(c) (c)
+#define FASTLZ_UNEXPECT_CONDITIONAL(c) (c)
+#endif
+
+/*
+ * Use inlined functions for supported systems.
+ */
+#if defined(__GNUC__) || defined(__DMC__) || defined(__POCC__) || defined(__WATCOMC__) || defined(__SUNPRO_C)
+#define FASTLZ_INLINE inline
+#elif defined(__BORLANDC__) || defined(_MSC_VER) || defined(__LCC__)
+#define FASTLZ_INLINE __inline
+#else
+#define FASTLZ_INLINE
+#endif
+
+/*
+ * Prevent accessing more than 8-bit at once, except on x86 architectures.
+ */
+#if !defined(FASTLZ_STRICT_ALIGN)
+#define FASTLZ_STRICT_ALIGN
+#if defined(__i386__) || defined(__386) /* GNU C, Sun Studio */
+#undef FASTLZ_STRICT_ALIGN
+#elif defined(__i486__) || defined(__i586__) || defined(__i686__) || defined(__amd64) /* GNU C */
+#undef FASTLZ_STRICT_ALIGN
+#elif defined(_M_IX86) /* Intel, MSVC */
+#undef FASTLZ_STRICT_ALIGN
+#elif defined(__386)
+#undef FASTLZ_STRICT_ALIGN
+#elif defined(_X86_) /* MinGW */
+#undef FASTLZ_STRICT_ALIGN
+#elif defined(__I86__) /* Digital Mars */
+#undef FASTLZ_STRICT_ALIGN
+#endif
+#endif
+
+/* prototypes */
+int fastlz_compress(const void *input, int length, void *output);
+int fastlz_compress_level(int level, const void *input, int length, void *output);
+int fastlz_decompress(const void *input, int length, void *output, int maxout);
+
+#define MAX_COPY 32
+#define MAX_LEN 264 /* 256 + 8 */
+#define MAX_DISTANCE 8192
+
+#if !defined(FASTLZ_STRICT_ALIGN)
+#define FASTLZ_READU16(p) *((const flzuint16 *)(p))
+#else
+#define FASTLZ_READU16(p) ((p)[0] | (p)[1] << 8)
+#endif
+
+#define HASH_LOG 13
+#define HASH_SIZE (1 << HASH_LOG)
+#define HASH_MASK (HASH_SIZE - 1)
+#define HASH_FUNCTION(v, p)                                                                                            \
+    {                                                                                                                  \
+        v = FASTLZ_READU16(p);                                                                                         \
+        v ^= FASTLZ_READU16(p + 1) ^ (v >> (16 - HASH_LOG));                                                           \
+        v &= HASH_MASK;                                                                                                \
+    }
+
+#undef FASTLZ_LEVEL
+#define FASTLZ_LEVEL 1
+
+#undef FASTLZ_COMPRESSOR
+#undef FASTLZ_DECOMPRESSOR
+#define FASTLZ_COMPRESSOR fastlz1_compress
+#define FASTLZ_DECOMPRESSOR fastlz1_decompress
+static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void *input, int length, void *output);
+static FASTLZ_INLINE int FASTLZ_DECOMPRESSOR(const void *input, int length, void *output, int maxout);
+#include "fastlz.cc"
+
+#undef FASTLZ_LEVEL
+#define FASTLZ_LEVEL 2
+
+#undef MAX_DISTANCE
+#define MAX_DISTANCE 8191
+#define MAX_FARDISTANCE (65535 + MAX_DISTANCE - 1)
+
+#undef FASTLZ_COMPRESSOR
+#undef FASTLZ_DECOMPRESSOR
+#define FASTLZ_COMPRESSOR fastlz2_compress
+#define FASTLZ_DECOMPRESSOR fastlz2_decompress
+static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void *input, int length, void *output);
+static FASTLZ_INLINE int FASTLZ_DECOMPRESSOR(const void *input, int length, void *output, int maxout);
+#include "fastlz.cc"
+
+int fastlz_compress(const void *input, int length, void *output)
+{
+    /* for short block, choose fastlz1 */
+    if (length < 65536)
+        return fastlz1_compress(input, length, output);
+
+    /* else... */
+    return fastlz2_compress(input, length, output);
+}
+
+int fastlz_decompress(const void *input, int length, void *output, int maxout)
+{
+    /* magic identifier for compression level */
+    int level = ((*(const flzuint8 *)input) >> 5) + 1;
+
+    if (level == 1)
+        return fastlz1_decompress(input, length, output, maxout);
+    if (level == 2)
+        return fastlz2_decompress(input, length, output, maxout);
+
+    /* unknown level, trigger error */
+    return 0;
+}
+
+int fastlz_compress_level(int level, const void *input, int length, void *output)
+{
+    if (level == 1)
+        return fastlz1_compress(input, length, output);
+    if (level == 2)
+        return fastlz2_compress(input, length, output);
+
+    return 0;
+}
+
+#else /* !defined(FASTLZ_COMPRESSOR) && !defined(FASTLZ_DECOMPRESSOR) */
+
+static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void *input, int length, void *output)
+{
+    const flzuint8 *ip = (const flzuint8 *)input;
+    const flzuint8 *ip_bound = ip + length - 2;
+    const flzuint8 *ip_limit = ip + length - 12;
+    flzuint8 *op = (flzuint8 *)output;
+
+    const flzuint8 *htab[HASH_SIZE];
+    const flzuint8 **hslot;
+    flzuint32 hval;
+
+    flzuint32 copy;
+
+    /* sanity check */
+    if (FASTLZ_UNEXPECT_CONDITIONAL(length < 4)) {
+        if (length) {
+            /* create literal copy only */
+            *op++ = length - 1;
+            ip_bound++;
+            while (ip <= ip_bound)
+                *op++ = *ip++;
+            return length + 1;
+        } else
+            return 0;
+    }
+
+    /* initializes hash table */
+    for (hslot = htab; hslot < htab + HASH_SIZE; hslot++)
+        *hslot = ip;
+
+    /* we start with literal copy */
+    copy = 2;
+    *op++ = MAX_COPY - 1;
+    *op++ = *ip++;
+    *op++ = *ip++;
+
+    /* main loop */
+    while (FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit)) {
+        const flzuint8 *ref;
+        flzuint32 distance;
+
+        /* minimum match length */
+        flzuint32 len = 3;
+
+        /* comparison starting-point */
+        const flzuint8 *anchor = ip;
+
+        /* check for a run */
+#if FASTLZ_LEVEL == 2
+        if (ip[0] == ip[-1] && FASTLZ_READU16(ip - 1) == FASTLZ_READU16(ip + 1)) {
+            distance = 1;
+            /* ip += 3; */ /* scan-build, never used */
+            ref = anchor - 1 + 3;
+            goto match;
+        }
+#endif
+
+        /* find potential match */
+        HASH_FUNCTION(hval, ip);
+        hslot = htab + hval;
+        ref = htab[hval];
+
+        /* calculate distance to the match */
+        distance = anchor - ref;
+
+        /* update hash table */
+        *hslot = anchor;
+
+        /* is this a match? check the first 3 bytes */
+        if (distance == 0 ||
+#if FASTLZ_LEVEL == 1
+            (distance >= MAX_DISTANCE) ||
+#else
+            (distance >= MAX_FARDISTANCE) ||
+#endif
+            *ref++ != *ip++ || *ref++ != *ip++ || *ref++ != *ip++)
+            goto literal;
+
+#if FASTLZ_LEVEL == 2
+        /* far, needs at least 5-byte match */
+        if (distance >= MAX_DISTANCE) {
+            if (*ip++ != *ref++ || *ip++ != *ref++)
+                goto literal;
+            len += 2;
+        }
+
+    match:
+#endif
+
+        /* last matched byte */
+        ip = anchor + len;
+
+        /* distance is biased */
+        distance--;
+
+        if (!distance) {
+            /* zero distance means a run */
+            flzuint8 x = ip[-1];
+            while (ip < ip_bound)
+                if (*ref++ != x)
+                    break;
+                else
+                    ip++;
+        } else
+            for (;;) {
+                /* safe because the outer check against ip limit */
+                if (*ref++ != *ip++)
+                    break;
+                if (*ref++ != *ip++)
+                    break;
+                if (*ref++ != *ip++)
+                    break;
+                if (*ref++ != *ip++)
+                    break;
+                if (*ref++ != *ip++)
+                    break;
+                if (*ref++ != *ip++)
+                    break;
+                if (*ref++ != *ip++)
+                    break;
+                if (*ref++ != *ip++)
+                    break;
+                while (ip < ip_bound)
+                    if (*ref++ != *ip++)
+                        break;
+                break;
+            }
+
+        /* if we have copied something, adjust the copy count */
+        if (copy)
+            /* copy is biased, '0' means 1 byte copy */
+            *(op - copy - 1) = copy - 1;
+        else
+            /* back, to overwrite the copy count */
+            op--;
+
+        /* reset literal counter */
+        copy = 0;
+
+        /* length is biased, '1' means a match of 3 bytes */
+        ip -= 3;
+        len = ip - anchor;
+
+        /* encode the match */
+#if FASTLZ_LEVEL == 2
+        if (distance < MAX_DISTANCE) {
+            if (len < 7) {
+                *op++ = (len << 5) + (distance >> 8);
+                *op++ = (distance & 255);
+            } else {
+                *op++ = (7 << 5) + (distance >> 8);
+                for (len -= 7; len >= 255; len -= 255)
+                    *op++ = 255;
+                *op++ = len;
+                *op++ = (distance & 255);
+            }
+        } else {
+            /* far away, but not yet in the another galaxy... */
+            if (len < 7) {
+                distance -= MAX_DISTANCE;
+                *op++ = (len << 5) + 31;
+                *op++ = 255;
+                *op++ = distance >> 8;
+                *op++ = distance & 255;
+            } else {
+                distance -= MAX_DISTANCE;
+                *op++ = (7 << 5) + 31;
+                for (len -= 7; len >= 255; len -= 255)
+                    *op++ = 255;
+                *op++ = len;
+                *op++ = 255;
+                *op++ = distance >> 8;
+                *op++ = distance & 255;
+            }
+        }
+#else
+
+        if (FASTLZ_UNEXPECT_CONDITIONAL(len > MAX_LEN - 2))
+            while (len > MAX_LEN - 2) {
+                *op++ = (7 << 5) + (distance >> 8);
+                *op++ = MAX_LEN - 2 - 7 - 2;
+                *op++ = (distance & 255);
+                len -= MAX_LEN - 2;
+            }
+
+        if (len < 7) {
+            *op++ = (len << 5) + (distance >> 8);
+            *op++ = (distance & 255);
+        } else {
+            *op++ = (7 << 5) + (distance >> 8);
+            *op++ = len - 7;
+            *op++ = (distance & 255);
+        }
+#endif
+
+        /* update the hash at match boundary */
+        HASH_FUNCTION(hval, ip);
+        htab[hval] = ip++;
+        HASH_FUNCTION(hval, ip);
+        htab[hval] = ip++;
+
+        /* assuming literal copy */
+        *op++ = MAX_COPY - 1;
+
+        continue;
+
+    literal:
+        *op++ = *anchor++;
+        ip = anchor;
+        copy++;
+        if (FASTLZ_UNEXPECT_CONDITIONAL(copy == MAX_COPY)) {
+            copy = 0;
+            *op++ = MAX_COPY - 1;
+        }
+    }
+
+    /* left-over as literal copy */
+    ip_bound++;
+    while (ip <= ip_bound) {
+        *op++ = *ip++;
+        copy++;
+        if (copy == MAX_COPY) {
+            copy = 0;
+            *op++ = MAX_COPY - 1;
+        }
+    }
+
+    /* if we have copied something, adjust the copy length */
+    if (copy)
+        *(op - copy - 1) = copy - 1;
+    else
+        op--;
+
+#if FASTLZ_LEVEL == 2
+    /* marker for fastlz2 */
+    *(flzuint8 *)output |= (1 << 5);
+#endif
+
+    return op - (flzuint8 *)output;
+}
+
+static FASTLZ_INLINE int FASTLZ_DECOMPRESSOR(const void *input, int length, void *output, int maxout)
+{
+    const flzuint8 *ip = (const flzuint8 *)input;
+    const flzuint8 *ip_limit = ip + length;
+    flzuint8 *op = (flzuint8 *)output;
+    flzuint8 *op_limit = op + maxout;
+    flzuint32 ctrl = (*ip++) & 31;
+    int loop = 1;
+
+    do {
+        const flzuint8 *ref = op;
+        flzuint32 len = ctrl >> 5;
+        flzuint32 ofs = (ctrl & 31) << 8;
+
+        if (ctrl >= 32) {
+#if FASTLZ_LEVEL == 2
+            flzuint8 code;
+#endif
+            len--;
+            ref -= ofs;
+            if (len == 7 - 1)
+#if FASTLZ_LEVEL == 1
+                len += *ip++;
+            ref -= *ip++;
+#else
+                do {
+                    code = *ip++;
+                    len += code;
+                } while (code == 255);
+            code = *ip++;
+            ref -= code;
+
+            /* match from 16-bit distance */
+            if (FASTLZ_UNEXPECT_CONDITIONAL(code == 255))
+                if (FASTLZ_EXPECT_CONDITIONAL(ofs == (31 << 8))) {
+                    ofs = (*ip++) << 8;
+                    ofs += *ip++;
+                    ref = op - ofs - MAX_DISTANCE;
+                }
+#endif
+
+#ifdef FASTLZ_SAFE
+            if (FASTLZ_UNEXPECT_CONDITIONAL(op + len + 3 > op_limit))
+                return 0;
+
+            if (FASTLZ_UNEXPECT_CONDITIONAL(ref - 1 < (flzuint8 *)output))
+                return 0;
+#endif
+
+            if (FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit))
+                ctrl = *ip++;
+            else
+                loop = 0;
+
+            if (ref == op) {
+                /* optimize copy for a run */
+                flzuint8 b = ref[-1];
+                *op++ = b;
+                *op++ = b;
+                *op++ = b;
+                for (; len; --len)
+                    *op++ = b;
+            } else {
+#if !defined(FASTLZ_STRICT_ALIGN)
+                const flzuint16 *p;
+                flzuint16 *q;
+#endif
+                /* copy from reference */
+                ref--;
+                *op++ = *ref++;
+                *op++ = *ref++;
+                *op++ = *ref++;
+
+#if !defined(FASTLZ_STRICT_ALIGN)
+                /* copy a byte, so that now it's word aligned */
+                if (len & 1) {
+                    *op++ = *ref++;
+                    len--;
+                }
+
+                /* copy 16-bit at once */
+                q = (flzuint16 *)op;
+                op += len;
+                p = (const flzuint16 *)ref;
+                for (len >>= 1; len > 4; len -= 4) {
+                    *q++ = *p++;
+                    *q++ = *p++;
+                    *q++ = *p++;
+                    *q++ = *p++;
+                }
+                for (; len; --len)
+                    *q++ = *p++;
+#else
+                for (; len; --len)
+                    *op++ = *ref++;
+#endif
+            }
+        } else {
+            ctrl++;
+#ifdef FASTLZ_SAFE
+            if (FASTLZ_UNEXPECT_CONDITIONAL(op + ctrl > op_limit))
+                return 0;
+            if (FASTLZ_UNEXPECT_CONDITIONAL(ip + ctrl > ip_limit))
+                return 0;
+#endif
+
+            *op++ = *ip++;
+            for (--ctrl; ctrl; ctrl--)
+                *op++ = *ip++;
+
+            loop = FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit);
+            if (loop)
+                ctrl = *ip++;
+        }
+    } while (FASTLZ_EXPECT_CONDITIONAL(loop));
+
+    return op - (flzuint8 *)output;
+}
+
+#endif /* !defined(FASTLZ_COMPRESSOR) && !defined(FASTLZ_DECOMPRESSOR) */