BTLT

From Second Life Wiki
Jump to: navigation, search

BTLT isn't anything special, it's just a combination of a couple very complicated libraries, FUIST-STIUF and TLT (FUIST-STIUF is an extension of FUIS-SIUF which is an extension of FUI-IUF). It encodes lists into strings and back into lists with care to restore the types but not degrade the contents while using a basic compression scheme.

History

Please excuse any slight errors in the timeline. In the beginning there was a scripter who wanted to be able to store floats in a lossless string format. The first attempt at solving this problem was Float to Scientific Notation and was terribly slow. Soon after that the scripter embarked upon a project to write an LSL bytecode interpretor written in LSL. Around this time the scripter discovered by accident that LSL supported HexFloats, and set about writing the encoder Float2Hex in the style of Float2Sci. To store the floats for the interpretor the FUI-IUF functions were written. During the writing of those functions the scripter realized two things, 1) that the process for encoding floats for FUI could be applied to Float2Hex and 2) that writing an interpretor in LSL wasn't worth the work. The process of matching the techniques of each function pushed the thinking forwards to the benefit of both Float2Hex and FUI-IUF. For grins the scripter modified FUI-IUF into FUIS-SIUF and found that it encoded and decoded floats faster then Hex2Float. Time passes and the scripter returns to a mothballed project: Hierarchical linking. This project had a couple of problems, how to store rotations in a tight format in notecards and ugly quaternion math. The problem with notecards is that if a script is going to read them, the lines can be no longer then 255 characters. This is problematic. One solution was FUIST-STIUF, it added trimming to FUIS-SIUF and was designed to be dropped into TLT. Before Float2Sci was even in the works the scripter was looking for a list-string transport functions. Not finding any satisfactory solutions the scripter laid out the TightList standard. It was integral part of the Strife Combat System and the functions were given the names "parse" and "dump". It wasn't until the development of TLTP and TLML did TightList become the official name of the functions. During the development of TLML did there become a need for a version of TL that could restore the type informations. After much thought TLT was created. Because of the memory restrictions of TLML(TLML's extensive feature set and tight syntax resulted in huge amounts of bytecode), TLT had to support drop-in encoders at compile time. Consequently TLT was written with ESL in mind (everything the scripter was writing at that time was written and still is written in ESL). The extension of TLT into BTLT while against the TLT standard is reasonable and to be expected.

Why Use BTLT?

BTLT was designed to be a tight format to be used for mostly float based datatypes. It wasn't intended to be particularly fast but it won't be unreasonably slow.

How It Works

Encoder:

  • A TLT encoder outfitted with the FUIST family of functions gets first crack at the values.
    • FUIST family of functions encode floats, vectors and rotations to strings.
      1. The float is converted to an integer with the FUI technique.
        • If you took the memory representation of a float and read it as an integer you would have the same output as FUI.
      2. Then the integer is turned into a Base64 string.
      3. Then the any trailing A's and ='s are trimmed off the end of that string.
      4. For Vectors and Rotations a size field is attached to the front. Vectors use a 1 char field, rotations 2 chars.

Decoder:

  • A TLT decoder outfitted with the STIUF family of functions.
    • STIUF family of functions do the inverse of FUIST.

Notes:

  • The FUIST-STIUF functions used are revision 2 of the library. R1 was intended as standalone functions from TLT, R2 was optimized to take advantage of TLT, allowing for the stripping of a character from the vector size field.

Code

//BTLT is part of the Combined Library.
//BTLT Version 0.1 beta
 
//===================================================//
//                 Combined Library                  //
//             "Nov  5 2007", "04:00:34"             //
//  Copyright (C) 2004-2007, Strife Onizuka (cc-by)  //
//    http://creativecommons.org/licenses/by/3.0/    //
//===================================================//
//{
 
rotation stiufr(string in)		//Mono Unsafe, LSO Safe, Double Unsafe
{	//--XXXXYYYYZZZZSSSS
    integer     raw = llBase64ToInteger(llGetSubString("AAA" + in + "AAA", 0, 5)) >> 2;
    integer     offset = 1;
    integer     len = raw & 7;
    return <stiuf(llDeleteSubString(in, len + 2, 1)),
        stiuf(llDeleteSubString(in, (len = (7 & (raw >> 3))) - ~(offset += len), offset)),
        stiuf(llDeleteSubString(in, (len = (7 & (raw >> 6))) - ~(offset += len), offset)),
        stiuf(llDeleteSubString(in, 0, offset + len)) >;
}
 
vector stiufv(string in)		//Mono Unsafe, LSO Safe, Double Unsafe
{	//-XXXXYYYYZZZZ
    integer     raw = llBase64ToInteger(llGetSubString("AAAA" + in + "AA", 0, 5)) >> 2;
    integer     offset = 0;
    integer     len = raw & 7;
    return <stiuf(llDeleteSubString(in, -~len, 0)),
        stiuf(llDeleteSubString(in, (len = (7 & (raw >> 3))) - ~(offset += len), offset)),
        stiuf(llDeleteSubString(in, 0, offset + len)) >;
}
 
string vfuist(vector in)		//Mono Unsafe, LSO Safe, Double Unsafe
{
    string      buf = fuist(in.y);
    integer     len = llStringLength(buf);
    return llGetSubString(llIntegerToBase64(((len << 3) + llStringLength(buf)) << 2), 4, 4) + (buf = fuist(in.x)) + buf + fuist(in.z);
}	//-XXXXYYYYZZZZ
 
string rfuist(rotation in)		//Mono Unsafe, LSO Safe, Double Unsafe
{
    string      z = fuist(in.z);
    string      buf = fuist(in.y);
    integer     len = (llStringLength(z) << 3) | llStringLength(buf);
    return llGetSubString(llIntegerToBase64(((len << 3) | llStringLength(buf)) << 2), 3, 4) + (buf = fuist(in.x)) + buf + z + fuist(in.s);
}	//--XXXXYYYYZZZZSSSS
 
string ist(integer b)			//Mono Safe, LSO Safe, Double Unsafe
{
    return llDumpList2String(llParseStringKeepNulls(llStringTrim(llDumpList2String(llParseStringKeepNulls(llIntegerToBase64(b),["A","="],[])," "),STRING_TRIM_TAIL),[" "],[]),"A");
}
 
string fuist(float a){//float union to base64ed integer
    if((a)){//is it greater than or less than zero?
        integer b = (a < 0) * 0x80000000;//the sign
        if((a = llFabs(a)) < 2.3509887016445750159374730744445e-38)//Denormalized range check & last stride of normalized range
            b = b | (integer)(a / 1.4012984643248170709237295832899e-45);//the math overlaps; saves cpu time.
        else if(a > 3.4028234663852885981170418348452e+38)//Round up to infinity
            b = b | 0x7F800000;//Positive or negative infinity
        else if(a > 1.4012984643248170709237295832899e-45){//It should at this point, except if it's NaN
            integer c = ~-llFloor(llLog(a) * 1.4426950408889634073599246810019);//extremes will error towards extremes. following yuch corrects it
            b = b | (0x7FFFFF & (integer)(a * (0x1000000 >> c))) | ((126 + (c = ((integer)a - (3 <= (a *= llPow(2, -c))))) + c) * 0x800000);
        }//the previous requires a lot of unwinding to understand it.
        else 
            b =  0x7FC00000;//NaN time! We have no way to tell NaN's apart so lets just choose one.
        return ist(b);
    }//for grins, detect the sign on zero. it's not pretty but it works. the previous requires a lot of unwinding to understand it.
    if((string)a == "-0.000000")
        return "g";
    return "";
}
 
float stiuf(string b)
{//base64ed integer union to float
    integer a = llBase64ToInteger(llGetSubString(b + "AAAAAA", 0, 5));
    if(!(0x7F800000 & ~a))
        return (float)llGetSubString("-infnan", 3 * ~!(a & 0x7FFFFF), ~a >> 31);
    return llPow(2, (a | !a) - 150) * (((!!(a = (0xff & (a >> 23)))) * 0x800000) | (a & 0x7fffff)) * (1 | (a >> 31));
}
 
list BTLTParse(string input)
{
    list        partial;
    if (llStringLength(input) > 6) {
        string      seperators = llGetSubString(input, (0), 6);
        integer     pos =
            ([] !=
             (partial =
              llList2List(input +
                          llParseStringKeepNulls(llDeleteSubString(input, (0), 5),[],
                                                 [input =
                                                  llGetSubString(seperators, (0), (0)), llGetSubString(seperators, 1, 1),
                                                  llGetSubString(seperators, 2, 2), llGetSubString(seperators, 3, 3),
                                                  llGetSubString(seperators, 4, 4), llGetSubString(seperators, 5, 5)]),
                          (llSubStringIndex(seperators, llGetSubString(seperators, 6, 6)) < 6) << 1, -1)));
        integer     type = (0);
        integer     sub_pos = (0);
        do {
            list        current = (list) (input = llList2String(partial, sub_pos = -~pos));	//TYPE_STRING || TYPE_INVALID (though we don't care about invalid)
            if (!(type = llSubStringIndex(seperators, llList2String(partial, pos))))	//TYPE_INTEGER
                current = (list) (llBase64ToInteger(llGetSubString(input + "AAAAAA", 0, 5)));
            else if (type == 1)	//TYPE_FLOAT
                current = (list) (stiuf(input));
            else if (type == 3)	//TYPE_KEY
                current = (list) ((key) (input));
            else if (type == 4)	//TYPE_VECTOR
                current = (list) (stiufv(input));
            else if (type == 5)	//TYPE_ROTATION
                current = (list) (stiufr(input));
            partial = llListReplaceList(partial, current, pos, sub_pos);
        } while ((pos = -~sub_pos) & 0x80000000);
    }
    return partial;
}
 
string BTLTDump(list input, string seperators)
{	//This function is dangerous
    seperators += "|/?!@#$%^&*()_=:;~`'<>{}[],.\n\" qQxXzZ\\"; //"//Buggy highlighter fix
    string      cumulator = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/" + (string) (input);
    integer     counter = (0);
    do
        if (~llSubStringIndex(cumulator, llGetSubString(seperators, counter, counter)))
            seperators = llDeleteSubString(seperators, counter, counter);
        else
            counter = -~counter;
    while (counter < 6);
    seperators = llGetSubString(seperators, (0), 5);
 
    string      buffer = cumulator = "";
 
    if ((counter = (input !=[]))) {
        do {
            integer     type = ~-llGetListEntryType(input, counter = ~-counter);
 
            if (type == 4)	//TYPE_VECTOR - 1
                buffer = vfuist(llList2Vector(input, counter));
            else
             if (type == 5)	//TYPE_ROTATION - 1
                buffer = rfuist(llList2Rot(input, counter));
            else
             if (type == 1)	//TYPE_FLOAT - 1
                buffer = fuist(llList2Float(input, counter));
            else
             if (!type)	//TYPE_INTEGER - 1
            {
                buffer = ist(llList2Integer(input, counter));
            } else
 
                buffer = llList2String(input, counter);
 
            cumulator = (cumulator = llGetSubString(seperators, type, type)) + buffer + cumulator;
        } while (counter);
    }
    return seperators + cumulator;
}
 
//} Combined Library