annnd another Key2Lsd packer

[elleevelyn]

i had some time so had a play. Another 20 symbol key packer

/* pack/unpack a key into 20 7-bit symbols which should convert to 20 LSD-compatible UTF-8 bytes
   borrows the carry method found in Key2Packed from the forum Scripting Library

   i havent tested this at all with LSD, but should be ok according to the LSD docs to date (January 2023)   

   public domain
*/ 
            
string Key2Lsd(string k)
{   // encode high to low
    string result;
    integer carry;
    integer i;
    
    k = llDumpList2String(llParseString2List(k, ["-"], []), "");   
    for (i; i < 31; i += 2)
    {   // read in 2 hex symbols, add upto 2 high bits as needed to clear low control chars, encode low 7 bits into a 1 byte symbol
        integer ord = (integer)("0x" + llGetSubString(k, i, i+1));
        if (ord < 32) ord += 288;
        else if ((ord > 127) & (ord <160)) ord += 192;
        result += llChar(ord & 127);
        // 2 high bits of ord are in 00,01,10. So encode these into the carry as log2(3) bits
        carry = carry * 3 + (ord >> 7);
    }

    // carry is 16 * log2(3) = 25.36 (26) bits. So encode carry (signals) in 4 symbols. Modulo 96 + 32 to clear low control chars
    for (i = 0; i < 4; ++i)
    {
        result += llChar(carry % 96 + 32);
        carry /= 96;
    }  
    return result;
}

key Lsd2Key(string s)
{   // decode low to high
    integer dash = 0x550;
    list hex = ["0","1","2","3","4","5","6","7","8","9","a","b","c","d","e","f"];

    string result;
    integer carry;
    integer i; 

    // decode carry
    for(i = 19; i > 15; --i)
        carry = (carry * 96) + (llOrd(s, i) - 32);

    // decode symbols, add/sub bits as signalled by carry
    for (i = 15; ~i; --i)
    {
        integer ord = llOrd(s, i);
        integer car = carry % 3;
        if (car == 1) 
            ord += 128;
        else if (car == 2)
        {
            if (ord < 64) ord -= 32;
            else ord += 64;    
        }
        carry /= 3;
        result = (llList2String(hex, (ord >> 4) & 15) +
            llList2String(hex, ord & 15)) + result;
        if (dash & (1 << i)) result = "-" + result;
   } 
   return (key)result;
}

default
{
    state_entry()
    {
        key k = llGenerateKey();
   
        string e = Key2Lsd(k);
        string d = Lsd2Key(e);
        
        llOwnerSay("\nk: " + (string)k + "\nd: " + d + "\ne: " + e + "  len: " + (string)llStringLength(e));
    }
}

 

[elleevelyn]

i had a go at doing this optimally. Optimal meaning within the log2 space of decodeable LSD chars, which at this time (January 2023) is 19 chars

this version is not compatible with the above 20 char version

/* pack/unpack a key into 19 7-bit symbols which should convert to 19 LSD-compatible UTF-8 bytes
   borrows the carry method found in Key2Packed from the forum Scripting Library
   
   as wrote it allows a TAB char to be optionally appended, for 20 symbols
   appending TAB prevents cross-boundary collisions when searching a string of encoded keys  

   i havent tested this with LSD, but should be ok according to the LSD documentation to date (January 2023)   

   public domain
*/ 
            
string Key2LSD(string k, integer delimit)
{   // encode high to low
    string result;
    integer carry;
    integer sign;

    // strip dash chars
    k = llDumpList2String(llParseString2List(k, ["-"], []), "");
    
    // encode symbols. loop 4 times: 128 bits / 32 bits = 4
    integer i;
    for (i; i < 25; i += 8)
    {
        // read 8 hex symbols into 32-bit buffer
        // strip off the sign bit and save
        integer buffer = (integer)("0x" + llGetSubString(k, i, i+7));
        sign = (sign << 1) | ((buffer >> 31) & 1);
        buffer = buffer & 0x7FFFFFFF;    

        // encode remainder 31 bits        
        integer j;
        for (j; j < 4; ++j)
        {
            // undecodable values 00,01,08,0C,0E,1F
            // allow 09 (TAB) as a optional delimiter 
            // leaves 121 decodable values
            // poke base121 into base128 symbol             
            integer ord = buffer % 121;
            if (ord == 0x0) ord = 121;  
            else if (ord == 0x1) ord = 122;
            else if (ord == 0x8) ord = 123;
            else if (ord == 0x9) ord = 124;
            else if (ord == 0xC) ord = 125;
            else if (ord == 0xE) ord = 126;
            else if (ord == 0x1F) ord = 127;
            result += llChar(ord);
            buffer /= 121;
        }
        // carry is base11: log2(0x80000000) - (4 * log2(121)) = log2(11)
        carry = carry * 11 + buffer;
    }
    
    // encode carry
    // 4 * log2(11) + 4 (high bits) = 17.84 bits
    // encode as base96 = 3 symbols
    // note that encoding carry in base121 will also use 3 symbols
    // so go with the more simple base96 method 
    carry = (carry << 4) | sign;
    for (i = 0; i < 3; ++i)
    {
        result += llChar(carry % 96 + 32);
        carry /= 96;
    }
    
    // append delimiter when requested
    return result += llChar(delimit * 0x9);
}

key LSD2Key(string s)
{   // decode low to high
    // note: decoder ignores the 20th symbol (TAB) when appended

    integer dash = 0x3C;
    list hex = ["0","1","2","3","4","5","6","7","8","9","a","b","c","d","e","f"];
    
    string result;
    integer carry;
    integer sign;
        
    // decode carry and sign
    integer i;
    for (i = 18; i > 15; --i)
        carry = carry * 96 + (llOrd(s, i) - 32); 
    sign = carry & 0x1F;
    carry = carry >> 4;

    // decode symbols
    for (i = 12; i >= 0; i -= 4)
    {
        integer buffer = carry % 11;
        carry /= 11;
        integer j;  
        for (j = i + 3; j >= i; --j)
        {
            // depoke base128 to base121
            integer ord = llOrd(s, j);
            if (ord > 120)
            {
                if (ord == 121) ord = 0x0;  
                else if (ord == 122) ord = 0x1;
                else if (ord == 123) ord = 0x8;
                else if (ord == 124) ord = 0x9;
                else if (ord == 125) ord = 0xC;
                else if (ord == 126) ord = 0xE;
                else if (ord == 127) ord = 0x1F;
            }
            buffer = buffer * 121 + ord;         
        }

        // restore sign bit to buffer
        buffer = buffer | ((sign & 1) << 31);
        sign = sign >> 1;
      
        // buffer to hex symbols
        string h;
        if (dash & 1) h = "-";
        dash = dash >> 1;
        h += llList2String(hex, (buffer >> 28) & 0xF) +
            llList2String(hex, (buffer >> 24) & 0xF) +
            llList2String(hex, (buffer >> 20) & 0xF) +
            llList2String(hex, (buffer >> 16) & 0xF);
        if (dash & 1) h += "-";
        dash = dash >> 1;
        h += llList2String(hex, (buffer >> 12) & 0xF) +
            llList2String(hex, (buffer >> 8) & 0xF) +
            llList2String(hex, (buffer >> 4) & 0xF) +
            llList2String(hex, buffer & 0xF);
            
        result = h + result; 
    }
    return (key)result; 
}

default
{
    state_entry()
    {
        key k = llGenerateKey();
        string e = Key2LSD(k, FALSE);  // no delimiter
        string t = Key2LSD(k, TRUE); // delimited with TAB
        string d = LSD2Key(t);                   
        
        llOwnerSay("\nk: " + (string)k +
            "\nd: " + (string)d + 
            "\ne: " + e + "  len: " + (string)llStringLength(e) +
            "\nt: " + t + "  len: " + (string)llStringLength(t));       
    }   
}

 

 

 

[elleevelyn]

I notice Linden fixed the LSD UTF-8 to UTF-16 bug. Is best to not use code from this post going forward

the updated 19-char version is posted in Script Library \ Key2LSD packer/umpacker (optimal size 19 UTF-8 chars)

 

Edited March 18, 2023 by elleevelyn