User:Becky Pippen/Numeric Storage

A General Method of Encoding Binary Data in UTF-16 Unicode Strings in Mono

The problem and goal

A list in LSL incurs a large memory overhead for every list element (see LSL_Script_Memory ). A true array type in LSL would solve the problem, but LSL has no array type. Strings, however, have properties that are conceptually like an array where each element is a Unicode character. So, we'll use a string as a storage container, and encode any binary data we want as fixed-sized Unicode strings. Then you can use the usual string functions to access, set, or get any element. This page describes a general method of storing 15 bits of information in each 16-bit Unicode character for a memory efficiency of 15/16 = 93.75%.

Background and terminology

Unicode refers to a set of several thousand glyphs, where each glyph is assigned a numeric ID in the range from 0 through 0x10ffff. However, that says nothing about how those 21-bit ID numbers are stored in memory.

• UTF-8 refers to a way of storing the Unicode character codes in variable length byte sequences of one or more bytes. This is how text is stored in a classic LSO script.

• UTF-16 refers to a way of storing the Unicode character numbers as one or two 16-bit integers. This is how text is stored in Mono scripts.

Escaped hex refers to a way of showing a character code as hex digits for the human's benefit. For example, the Unicode character "á" corresponds to Unicode character number 225. In UTF-8 format, that's stored as two bytes (0xc3,0xa1). The escaped hex format for that would look like the string "%c3%a1".

For a summary of Unicode, UTF-8, and UTF-16, see: Unicode_In_5_Minutes.

Design considerations

In classic LSO, we could construct, store, and decode any Unicode character from U-00000000 through U-ffffffff, but in Mono the character range is limited to U-00000000 through U-0010fffd minus these codes that are not allowed to be used as characters:

0x0000
0xd800 - 0xdfff
0xfdd0 - 0xfdef
0xfffe - 0xffff
0x1fffe - 0x1ffff
0x2fffe - 0x2ffff

That's why we can't just use the entire range of character codes, so we'll use half. That means we must map the 32768 possible values of a 15-bit data item to a well-defined set of 32768 Unicode characters that are legal to use. And we must restrict our choices to the Unicode characters that can be represented with two bytes in UTF-16 format. The example code below uses Unicode characters U-001000 through U-008fff to store the data values 0 through 0x7fff. This could be called a base 32768 solution, and is very similar to the "Base 32768" solution for key storage described in Key_Compression.

Converting a 15-bit numeric value to a 16-bit Unicode character is as follows:

• Add 0x1000 to remap the 15-bit values from [0x0000..0x8000) to the character range [0x1000.. 0x9000).
• Convert the numeric value to an escaped UTF-8 string.
• Convert the escaped UTF-8 representation to a single UTF-16 Unicode character using llUnescapeURL().

For example, here are the steps to encode the 15-bit value 0x112b:

• Add 0x1000, resulting in 0x212b
• Convert 0x212b to UTF-8 represented in escaped hex form = "%e2%84%ab"
• Convert the escaped UTF-8 to a 16-bit Unicode char using llUnescapeURL("%e2%84%ab") (The resulting character is "Å")

The intermediate step of converting the 15-bit numeric value to variable-length UTF-8 depends on the number range:

bytes | bits | range      | representation
    1 |    7 | 0..7f      | 0vvvvvvv
    2 |   11 | 80..7ff    | 110vvvvv 10vvvvvv
    3 |   16 | 800..ffff  | 1110vvvv 10vvvvvv 10vvvvvv
    4 |   21 | 10000..    | 11110vvv 10vvvvvv 10vvvvvv 10vvvvvv

Because we're only encoding values in the range 0x1000 - 0x8fff, we only need to deal with the 3-byte form shown above, simplifying the code but also making these functions unsuitable for general character conversions.

Converting a Unicode character to its numeric code is the reverse process. For example, given the Angstrom character "Å", llEscapeURL("Å") returns "%E2%84%AB" which must be chopped up and converted in the reverse process to get 0x212b, then subtract the bias to get 0x112b.

A Mono script with a small amount of code dedicated to data storage could easily store 25,000 data items where each is an arbitrary 15-bit value. As long as you can combine or split your data to fit into 15-bit chunks, then you can use this technique. E.g, two such 15-bit items can hold a region positional vector with coordinates rounded off, or a 30-bit hash of an avatar name or UUID. This technique gives us 15/16 = 93.75% efficient utilization of memory, compared to about 20% efficiency if using global lists of integers or vectors.

Usage, Example, Properties:

<lsl> string DataBase; // some global string that holds all the elements

integer data15Bits = 0x1234; // an example 15-bit data item to store
. . .
DataBase += encode15BitsToChar(data15Bits); // append the new value to the DB
. . .
// Round-trip encoding/decoding is lossless. I.e., The following will always be true:
decodeCharTo15Bits(encode15BitsToChar(data15Bits)) == data15Bits </lsl>

Additional information can be found in the comments in the source code example below.

Source code example

<lsl> // Converts n = [0..0xff] to two hex characters

//
string hexChar2(integer n)
{
    string hexChars = "0123456789abcdef";
    return llGetSubString(hexChars, n >> 4, n >> 4) +
           llGetSubString(hexChars, n & 0xf, n & 0xf);
}

// This is a memory-savings technique for use with Mono-compiled LSL scripts.
// (It probably works in classic LSO too, but not as efficiently.) This technique
// stores 15 bits of information in each 16-bit Unicode character. Use the
// encode function below to convert any 15-bit data to a Unicode character, and
// use the decode function to convert it back to the original 15-bit data.
//
// This example maps the data values 0 through 0x7fff to the Unicode
// characters U-001000 through U-008fff.
//
// By Becky Pippen, 2009, contributed to Public Domain
// The technique used here is very similar to the technique used in the "Base 32768
// Script" in http://wiki.secondlife.com/wiki/Key_Compression .

// Return a single 16-bit Unicode character in UTF-16 two-byte form
//
string encode15BitsToChar(integer num)
{
    // Check the incoming range

    if (num < 0 || num >= 0x8000) {
        // illegal input -- do whatever is appropriate
        return "�";
    }

    // Bias the incoming numeric value by 0x1000 to avoid illegal Unicode codes:

    num += 0x1000;

    // construct an escaped hex UTF-8 representation:

    string utf8 = "%" + hexChar2(0xe0 + (num >> 12)) +
                  "%" + hexChar2(0x80 + ((num >> 6) & 0x3f)) +
                  "%" + hexChar2(0x80 + (num & 0x3f));

    // Convert the UTF-8 into a 16-bit Unicode character:

    return llUnescapeURL(utf8);
}


// This is the inverse of encode15BitsToChar(), supra, q.v.
// This expects a single 16-bit Unicode character that was created by
// encode15BitsToChar() and returns the numeric value used to create it.
// The 15-bit return value will always be in the range 0x0000 - 0x7fff.
//
integer decodeCharTo15Bits(string ch)
{
    integer retVal;
    string utf8 = llEscapeURL(ch); // convert to escaped hex UTF-8

    retVal =  (((integer)("0x" + llGetSubString(utf8, 1, 2)) & 0x1f) << 12) +
              (((integer)("0x" + llGetSubString(utf8, 4, 5)) & 0x3f) << 6) +
               ((integer)("0x" + llGetSubString(utf8, 7, 8)) & 0x3f);

    return retVal - 0x1000;
}

string Database; // think of this as an array of 15-bit values

default
{
    touch_start(integer num)
    {
        integer data15Bits = (integer)llFrand(32768.0); // [0..32767] pretend data
        string encodedChar = encode15BitsToChar(data15Bits);
        Database += encodedChar;

        llOwnerSay("Appended data value " + (string)data15Bits +
                " to database as character \"" + encodedChar + "\"");

        llOwnerSay("At " + (string)llStringLength(Database) +
                " items, free mem = " + (string)llGetFreeMemory());
    }
} </lsl>

Also See

Read more about script memory limits, and other ways to reduce script memory usage.