diff options
Diffstat (limited to 'indra/llmessage/llzerocode.h')
| -rw-r--r-- | indra/llmessage/llzerocode.h | 211 |
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 |