Jump to content

Pack/Unpack a key/uuid with llChar and llOrd


Mollymews
 Share

You are about to reply to a thread that has been inactive for 885 days.

Please take a moment to consider if this thread is worth bumping.

Recommended Posts

i had a bit of time so I put this key packer together. It packs a key into 9 chars

// pack/unpack a key to 9 chars. 18 bytes

// we can only use the range [1..55295] of a 2-byte UTF-16 char and have it decodable
// if we go beyond this to the next decodable range then it would incur using 4-byte UTF-16 chars
//
// so we carry 1 bit from each 2-byte char into a 9th carry char. A carry method found in
// Key2UTF in the forum Scripting Library
 
string Key2Packed(string k)
{   // passing a keytype to string k will auto cast it as a string

    // get the ordinal of the substring
    // move the low bit of the ordinal to the carry
    // encode the ordinal adding 0x20 to avoid low control chars
    // finally,
    //    add 0x8020 to the carry so to uniquely identify a packed key string 
    //    from another packed key string. Packed key strings are unique
    // return the carry char with the encoded key appended
    
    integer ord = (integer)("0x" + llGetSubString(k, 0, 3));
    integer carry = ord & 1;
    string result = llChar((ord >> 1) + 0x20);
    ord = (integer)("0x" + llGetSubString(k, 4, 7));
    carry = (carry << 1) + (ord & 1);
    result += llChar((ord >> 1) + 0x20);
    ord = (integer)("0x" + llGetSubString(k, 9, 12));
    carry = (carry << 1) + (ord & 1);
    result += llChar((ord >> 1) + 0x20);
    ord = (integer)("0x" + llGetSubString(k, 14, 17));
    carry = (carry << 1) + (ord & 1);
    result += llChar((ord >> 1) + 0x20);
    ord = (integer)("0x" + llGetSubString(k, 19, 22));
    carry = (carry << 1) + (ord & 1);
    result += llChar((ord >> 1) + 0x20);
    ord = (integer)("0x" + llGetSubString(k, 24, 27));
    carry = (carry << 1) + (ord & 1);
    result += llChar((ord >> 1) + 0x20);
    ord = (integer)("0x" + llGetSubString(k, 28, 31));
    carry = (carry << 1) + (ord & 1);
    result += llChar((ord >> 1) + 0x20);
    ord = (integer)("0x" + llGetSubString(k, 32, 35));
    carry = (carry << 1) + (ord & 1);
    result += llChar((ord >> 1) + 0x20);
    return llChar(carry + 0x8020) + result; 
}    
     
key Packed2Key(string s)
{
    // list lookup is faster than string lookup
    list hex = ["0","1","2","3","4","5","6","7","8","9","a","b","c","d","e","f"];
    
    // get the carry bits
    integer carry = llOrd(s, 0) - 0x8020;
    
    // decode each encoded char of the key
    integer ord = ((llOrd(s, 1) - 0x20) << 1) + ((carry >> 7) & 1);  
    string result = llList2String(hex, (ord >> 12) & 0xF) + llList2String(hex, (ord >> 8) & 0xF) +
        llList2String(hex, (ord >> 4) & 0xF) + llList2String(hex, ord & 0xF);
    ord = ((llOrd(s, 2) - 0x20) << 1) + ((carry >> 6) & 1);                   ;
    result += llList2String(hex, (ord >> 12) & 0xF) + llList2String(hex, (ord >> 8) & 0xF) + 
        llList2String(hex, (ord >> 4) & 0xF) + llList2String(hex, ord & 0xF) + "-";
    ord = ((llOrd(s, 3) - 0x20) << 1) + ((carry >> 5) & 1);
    result += llList2String(hex, (ord >> 12) & 0xF) + llList2String(hex, (ord >> 8) & 0xF) +
        llList2String(hex, (ord >> 4) & 0xF) + llList2String(hex, ord & 0xF) + "-";
    ord = ((llOrd(s, 4) - 0x20) << 1) + ((carry >> 4) & 1);
    result += llList2String(hex, (ord >> 12) & 0xF) + llList2String(hex, (ord >> 8) & 0xF) +
        llList2String(hex, (ord >> 4) & 0xF) + llList2String(hex, ord & 0xF) + "-";
    ord = ((llOrd(s, 5) - 0x20) << 1) + ((carry >> 3) & 1);
    result += llList2String(hex, (ord >> 12) & 0xF) + llList2String(hex, (ord >> 8) & 0xF) +
        llList2String(hex, (ord >> 4) & 0xF) + llList2String(hex, ord & 0xF) + "-";
    ord = ((llOrd(s, 6) - 0x20) << 1) + ((carry >> 2) & 1);
    result += llList2String(hex, (ord >> 12) & 0xF) + llList2String(hex, (ord >> 8) & 0xF) +
        llList2String(hex, (ord >> 4) & 0xF) + llList2String(hex, ord & 0xF);
    ord = ((llOrd(s, 7) - 0x20) << 1) + ((carry >> 1) & 1);
    result += llList2String(hex, (ord >> 12) & 0xF) + llList2String(hex, (ord >> 8) & 0xF) +
        llList2String(hex, (ord >> 4) & 0xF) + llList2String(hex, ord & 0xF);
    ord = ((llOrd(s, 8) - 0x20) << 1) + (carry & 1);
    result += llList2String(hex, (ord >> 12) & 0xF) + llList2String(hex, (ord >> 8) & 0xF) +
        llList2String(hex, (ord >> 4) & 0xF) + llList2String(hex, ord & 0xF);
    return (key)result;
}   

default
{    
    touch_start(integer num)
    {
        key id = llGenerateKey();
        string s = Key2Packed(id);
        key unpacked = Packed2Key(s); 
        
        llOwnerSay("key= " + (string)id + "\npacked= " + s + "\nunpacked= " + (string)unpacked);       
    }
}

 

  • Like 1
  • Thanks 4
Link to comment
Share on other sites

here is a rolled version.  A caveat is that rolled code is typically slower than unrolled code. Typical trade off: size vs execution
 

// pack/unpack a key to 9 chars. 18 bytes

// we can only use the range [1..55295] of a 2-byte UTF-16 char and have it decodable
// if we go beyond this to the next decodable range then it would incur using 4-byte UTF-16 chars
//
// so we carry 1 bit from each 2-byte char into a 9th carry char. A carry method found in
// Key2UTF in the forum Scripting Library
 
string Key2Packed(string k)
{
    integer carry;
    string result;
    integer i;
    for (i = 0; i < 8; i++)
    {
        integer idx = (i * 4)  + ((0x44432100 >> (i * 4)) & 0xF);
        integer ord = (integer)("0x" + llGetSubString(k, idx, idx + 3));
        carry = (carry << 1) + (ord & 1);
        result += llChar((ord >> 1) + 0x20);
    }
    return llChar(carry + 0x8020) + result;
}
 
key Packed2Key(string s)
{
    list hex = ["0","1","2","3","4","5","6","7","8","9","a","b","c","d","e","f"];
    integer carry = llOrd(s, 0) - 0x8020;
    string result;
    integer i;
    for (i = 1; i < 9; i++)
    {
        integer ord = ((llOrd(s, i) - 0x20) << 1) + ((carry >> (8 - i)) & 1);
        result += llList2String(hex, (ord >> 12) & 0xF) + llList2String(hex, (ord >> 8) & 0xF) +
            llList2String(hex, (ord >> 4) & 0xF) + llList2String(hex, ord & 0xF);
        if (i > 1 && i < 6) result += "-";
    }
    return (key)result;
}

default
{    
    touch_start(integer num)
    {
        key id = llGenerateKey();
        string s = Key2Packed(id);
        key unpacked = Packed2Key(s);
        
        llOwnerSay("key= " + (string)id + "\npacked= " + s + "\nupk= " + (string)unpacked);       
    }
}

 

 

 

Edited by Mollymews
check for error that turned out to not be the case
  • Like 1
  • Thanks 3
Link to comment
Share on other sites

some tiny optimisations to the rolled version

Key2Packed.  Remove 2 multiplications and replace with 1 addition

Packed2Key. Replace (i > 1 && i < 6) with ((i > 1) & (i < 6)). & is a tiny bit more efficient than &&

// pack/unpack a key to 9 chars. 18 bytes
// rolled version with optimisations
 
string Key2Packed(string k)
{
    integer carry;
    string result;
    integer i;
    for (i = 0; i < 29; i += 4)
    {      
        integer idx = i + ((0x44432100 >> i) & 0xF);
        integer ord = (integer)("0x" + llGetSubString(k, idx, idx + 3));
        carry = (carry << 1) + (ord & 1);
        result += llChar((ord >> 1) + 0x20);
    }
    return llChar(carry + 0x8020) + result;
}
 
key Packed2Key(string s)
{
    list hex = ["0","1","2","3","4","5","6","7","8","9","a","b","c","d","e","f"];
    integer carry = llOrd(s, 0) - 0x8020;
    string result;
    integer i;
    for (i = 1; i < 9; i++)
    {
        integer ord = ((llOrd(s, i) - 0x20) << 1) + ((carry >> (8 - i)) & 1);
        result += llList2String(hex, (ord >> 12) & 0xF) + llList2String(hex, (ord >> 8) & 0xF) +
            llList2String(hex, (ord >> 4) & 0xF) + llList2String(hex, ord & 0xF);
        if ((i > 1) & (i < 6)) result += "-";
    }
    return (key)result;
}

default
{    
    touch_start(integer num)
    {
        key id = llGenerateKey();
        string s = Key2Packed(id);
        key unpacked = Packed2Key(s);
        
        llOwnerSay("key= " + (string)id + "\npacked= " + s + "\nupk= " + (string)unpacked);       
    }
}

 

Link to comment
Share on other sites

You absolute saint. :D I've been puzzling over how to update the advanced key packing algorithm on the wiki to use the new functions instead of the user-written hex/chr/ord functions for a few weeks now but it just wasn't clicking. I was able to fit 1800 keys into one script with that before it auto-halted due to having only one buffer's worth of memory left, but it was pretty noticeably slow given all the conversions going around. I bet this is like lightning in comparison. It's only two functions now. Gahd. Beyoutiful. 

Edit for addendum: Don't worry, I have no intention of storing that absurdly many keys. :b Just stress testing. 

Cheers! 

Edited by Clarity Toxx
  • Like 1
Link to comment
Share on other sites

  • 1 month later...

Not sure it's worth trying to make a fix for, but it doesn't gracefully handle NULL_KEY.  if i'm creating a table of keys and want to put in a NULL_KEY as a place holder, the pack routine reduces it to a single character and the unpack routine returns 'gibberish'.   

commenting more for people to be aware of the behavior more than anything else:   if a packed key in a list is a single char, don't try to unpack, just default it to NULL_KEY. 

(the single char on my screen is "耠").

PacTest: NULL KEY is: 00000000-0000-0000-0000-000000000000
PacTest: Packed Key is: 耠        
PacTest: Unpacked Key is: ffc0ffc0-ffc0-ffc0-ffc0-ffc0ffc0ffc0

Edited by Anna Salyx
add in test output for clarification of "gibberish"
  • Thanks 1
Link to comment
Share on other sites

On 10/21/2021 at 4:08 AM, Anna Salyx said:

(the single char on my screen is "耠").

PacTest: NULL KEY is: 00000000-0000-0000-0000-000000000000
PacTest: Packed Key is: 耠        
PacTest: Unpacked Key is: ffc0ffc0-ffc0-ffc0-ffc0-ffc0ffc0ffc0

as wrote, substring "0000" packs to a single space char " ". So does "0001"

(integer)"0000" = 0. 0 >> 1 = 0. 0 + 0x20 = 0x20. char(0x20) is " "

(integer)"0001' = 1. 1 >> 1 = 0. 0 + 0x20 = 0x20

we can see this with:

 touch_start(integer num)
    {
        key id = NULL_KEY;
        
        string s = Key2Packed(id);
        
        string ords;
        integer i;
        for (i = 0; i < 9; ++i)
        {
            ords += " " + (string)llOrd(s, i);
        }
        llOwnerSay("s = '" + s + "' ords = " + ords);
        // says: s = '耠        ' ords =  32800 32 32 32 32 32 32 32 32   
               
        key unpacked = Packed2Key(s);
        
        llOwnerSay("key= " + (string)id + "\npacked= " + s + "\nunpacked= " + (string)unpacked);       
    }

if this is disconcerting then can use another bottom value. Like 0x21 instead of 0x20. 0x8020 becomes 0x8021

or can use 0x800 as the bottom same as UTF2Key does. 0x20 becomes 0x800. 0x8020 becomes 0x8800

 

ps. if we want to store many packed keys then store them in a string for max. memory efficiency

adding 0x8020 to the carry means that every 9th char is greater than 0x801F. The other 8 chars in the packed key are less than 0x8000. Therefore llSubStringIndex will always correctly find a packed key in a string of packed keys

pcode example:

string pstore = pkey1 + pkey2 + pkey3 + ... + pkey2003 + ... + pkeyN
// pstore = "8012345678123456708234567018..."

integer index = llSubStringIndex(pstore, pkey3);

 

Edited by Mollymews
ps
Link to comment
Share on other sites

oh.   I didn't realize that it was a single visible char followed by a number of "blank" spaces.  I should have been more diligent in my investigation/commenting.    Your follow-up and examples of what was happening clarified it for me. 

As for it being disconcerting, it really isn't.  At least for me.  I was more trying to give a heads up of a somewhat unexpected behavior involving NULL_KEY place holders or spacers in a data set.  Now that I know it's a 9 char string (one leading visible char, 8 blank) it can be a constant to test for when extracting before unpacking.  And that is important considering I was originally thinking just looking for a single space character.  

Personally I'm glad I said something and got feedback because that might have become a point of debugging frustration for me later on.  So.  Thank you :)

  • Like 1
Link to comment
Share on other sites

17 hours ago, Anna Salyx said:

Personally I'm glad I said something and got feedback because that might have become a point of debugging frustration for me later on.  So.  Thank you :)

i am always happy to get feedback. So thanks you too :)

is always better to ask questions. As is true about debugging frustrations later on in life. It can drive us nuts getting conked on by a script thats been working perfect for ages, right up til the moment it doesn't. Oh! man I am sooo lucky, a 1 in a zillion chance of getting conked on and I won 😸

 

 

 

Link to comment
Share on other sites

You are about to reply to a thread that has been inactive for 885 days.

Please take a moment to consider if this thread is worth bumping.

Please sign in to comment

You will be able to leave a comment after signing in



Sign In Now
 Share

×
×
  • Create New...