Merge remote-tracking branch 'secondlife/release/26.4' into 26.4

1 files changed, 211 insertions, 0 deletions

diff --git a/indra/llmessage/llzerocode.h b/indra/llmessage/llzerocode.h
new file mode 100644
index 0000000000..7246c9d946
--- /dev/null
+++ b/indra/llmessage/llzerocode.h
@@ -0,0 +1,211 @@
+/**
+ * @file llzerocode.h
+ * @brief Zero-code run-length compression used by the LLMessageSystem UDP protocol.
+ *
+ * $LicenseInfo:firstyear=2001&license=viewerlgpl$
+ * Second Life Viewer Source Code
+ * Copyright (C) 2010, Linden Research, Inc.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation;
+ * version 2.1 of the License only.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
+ *
+ * Linden Research, Inc., 945 Battery Street, San Francisco, CA  94111  USA
+ * $/LicenseInfo$
+ */
+
+#ifndef LL_LLZEROCODE_H
+#define LL_LLZEROCODE_H
+
+#include <cstring>
+
+#include "stdtypes.h"
+
+// Zero-coding compresses runs of zero bytes in a packet body, leaving the
+// first header_size bytes of the buffer (the packet header - flags,
+// sequence number, offset, etc.) untouched aside from the flag bit below.
+//
+//   Runs of zero bytes in the body are replaced by a two-byte token:
+//     0x00 N        - represents N zero bytes, for N in 1..254
+//     0x00 0x00 N   - represents (255 + N) zero bytes (wrap/overflow case,
+//                     produced by decode()'s wire format but never emitted
+//                     by encode(), which instead starts a fresh 0x00 token
+//                     every 255 zero bytes)
+namespace LLZeroCode
+{
+    // High bit of the first header byte: set by encode() and cleared by
+    // decode() to indicate whether the body that follows is zero-coded.
+    const U8 FLAG = 0x80;
+
+    // Zero-codes src (src_size bytes, the first header_size of which are the
+    // packet header and are copied verbatim) into dst.
+    //
+    // dst_capacity must be at least 2 * src_size: a pathological body of
+    // isolated zero bytes can nearly double in size when encoded.
+    //
+    // Returns the encoded size (with FLAG set in dst[0]) if doing so made the
+    // packet smaller. Returns -1 if compression would not help (or the
+    // arguments are invalid), in which case dst is left untouched and the
+    // caller should keep using the original, uncompressed buffer.
+    inline S32 encode(const U8* src, U32 src_size, U8* dst, U32 dst_capacity, U32 header_size)
+    {
+        if (src_size < header_size || dst_capacity < 2 * src_size)
+        {
+            return -1;
+        }
+
+        S32 count = (S32)(src_size - header_size);
+        S32 net_gain = 0;
+        U8 num_zeroes = 0;
+
+        const U8* inptr = src;
+        U8* outptr = dst;
+
+        // copy the header verbatim
+        for (U32 ii = 0; ii < header_size; ++ii)
+        {
+            *outptr++ = *inptr++;
+        }
+
+        // sequential zero bytes are encoded as 0 [U8 count]; a run longer
+        // than 254 bytes is split into consecutive 0 [U8 count] tokens.
+        while (count--)
+        {
+            if (!(*inptr))   // in a zero count
+            {
+                if (num_zeroes)
+                {
+                    if (++num_zeroes > 254)
+                    {
+                        *outptr++ = num_zeroes;
+                        num_zeroes = 0;
+                    }
+                    net_gain--;   // subsequent zeroes save one
+                }
+                else
+                {
+                    *outptr++ = 0;
+                    net_gain++;  // starting a zero count adds one
+                    num_zeroes = 1;
+                }
+                inptr++;
+            }
+            else
+            {
+                if (num_zeroes)
+                {
+                    *outptr++ = num_zeroes;
+                    num_zeroes = 0;
+                }
+                *outptr++ = *inptr++;
+            }
+        }
+
+        if (num_zeroes)
+        {
+            *outptr++ = num_zeroes;
+        }
+
+        if (net_gain >= 0)
+        {
+            // compression did not shrink the packet; caller should keep the original
+            return -1;
+        }
+
+        dst[0] |= FLAG;
+        return (S32)src_size + net_gain;
+    }
+
+    // Expands a zero-coded src (src_size bytes) into dst.
+    //
+    // If FLAG is not set in src[0], the body is not zero-coded: no work is
+    // done and the function returns 0.
+    //
+    // On success, returns the number of bytes written to dst (always includes
+    // the header_size header bytes, copied verbatim except for FLAG being
+    // cleared from dst[0]).
+    //
+    // If expansion would write past dst_capacity - which only a malformed or
+    // malicious packet should cause - decoding is aborted, *overflow is set
+    // true, and the returned size reflects however much (if anything) was
+    // salvaged; the caller should treat the packet as invalid.
+    inline U32 decode(const U8* src, U32 src_size, U8* dst, U32 dst_capacity, U32 header_size, bool& overflow)
+    {
+        overflow = false;
+
+        if (src_size < header_size || !(src[0] & FLAG))
+        {
+            return 0;
+        }
+
+        S32 count = (S32)(src_size - header_size);
+
+        const U8* inptr = src;
+        U8* outptr = dst;
+
+        for (U32 ii = 0; ii < header_size; ++ii)
+        {
+            *outptr++ = *inptr++;
+        }
+        dst[0] &= ~FLAG;
+
+        // reconstruct the body: a 0x00 byte starts a run; the byte(s) that
+        // follow give its length (see the wire format described above).
+        while (count--)
+        {
+            if (outptr > &dst[dst_capacity - 1])
+            {
+                overflow = true;
+                outptr = dst;
+                break;
+            }
+
+            if (!((*outptr++ = *inptr++)))
+            {
+                while ((count--) && (!(*inptr)))
+                {
+                    if (outptr > &dst[dst_capacity - 256])
+                    {
+                        overflow = true;
+                        outptr = dst;
+                        count = -1;
+                        break;
+                    }
+                    *outptr++ = *inptr++;
+                    memset(outptr, 0, 255);
+                    outptr += 255;
+                }
+
+                if (count < 0)
+                {
+                    break;
+                }
+                else
+                {
+                    if (outptr > &dst[dst_capacity - (*inptr)])
+                    {
+                        overflow = true;
+                        outptr = dst;
+                    }
+                    memset(outptr, 0, (*inptr) - 1);
+                    outptr += ((*inptr) - 1);
+                    inptr++;
+                }
+            }
+        }
+
+        return (U32)(outptr - dst);
+    }
+}
+
+#endif // LL_LLZEROCODE_H