(another) key packing method.

[Quistess Alpha]

I've used @Mollymews's key packing functions in a few projects now and they're quite great.

For a lot of use cases though, it's only necessary to go one way: compress the key, store it in a list, then later compress a new key and see if it was already in the list. 

With the limited arithmetic LL gives us, it is possible to losslessly compress a key into a rotation, but I don't think it is possible to undo this operation without an accurate log base 2 function.

rotation key2pack(key k)
{   string s = (string)k;
    integer a = (integer)("0x"+s);
    integer b = (integer)("0x"+llGetSubString(s,9,12)+llGetSubString(s,14,17));
    integer c = (integer)("0x"+llGetSubString(s,19,22)+llGetSubString(s,24,27));
    integer d = (integer)("0x"+llGetSubString(s,-8,-1));
    return <(float)(a&0xFFFFFF) * llPow(2,a>>24),
            (float)(b&0xFFFFFF) * llPow(2,b>>24),
            (float)(c&0xFFFFFF) * llPow(2,c>>24),
            (float)(d&0xFFFFFF) * llPow(2,d>>24) >;
}
list l;
default
{   state_entry()
    {   integer reps = 2001; // actually 2000: +1 to make the loop slightly faster by not using '~'
        while(--reps)
        {   rotation packed = key2pack(llGenerateKey());
            integer index = llListFindList(l,[packed]);
            if(index==-1)
            {   l+=packed;
            }else
            {   llSay(0,"Improbable collision!!!");
            }
            if(!(reps%200))
            {   llSay(0,(string)llGetFreeMemory());
            }
        }
        llSay(0,(string)llGetFreeMemory());
        llSay(0,"Done.");
    }
}

(as an example)

[Coffee Pancake]

If you're only going one way then just hash, If you're really memory tight, truncating the hash is also feasible depending on your scripts use case.

This has the advantage that you can use a stock LSL command and don't need to burn 512bytes declaring your own function.

[Quistess Alpha]

1 hour ago, Coffee Pancake said:

If you're only going one way then just hash, If you're really memory tight, truncating the hash is also feasible depending on your scripts use case.

This has the advantage that you can use a stock LSL command and don't need to burn 512bytes declaring your own function.

I agree, although it obviously depends on how "important" it is to avoid collisions.

[Coffee Pancake]

9 hours ago, Quistess Alpha said:

I agree, although it obviously depends on how "important" it is to avoid collisions.

It's also not even nearly as much fun.

Edited March 27, 2022 by Coffee Pancake

[Quistess Alpha]

Dumping these here; more key packing ideas for use in utf-8 (I.E. LinksetData)

base 95 was a bit harder than I thought it would be, because I forgot negative numbers are a thing. I've not thoroughly checked edge-cases, nor unwrapped function calls, nor pre-calculated powers of 95.

string KeyToB64(string s)
{   integer a = (integer)("0x"+s);
    integer b = (integer)("0x"+llGetSubString(s,9,12)+llGetSubString(s,14,17));
    integer c = (integer)("0x"+llGetSubString(s,19,22)+llGetSubString(s,24,27));
    integer d = (integer)("0x"+llGetSubString(s,-8,-1));

    return llDeleteSubString(llIntegerToBase64(a),-2,-1)+
           llDeleteSubString(llIntegerToBase64(b),-2,-1)+
           llDeleteSubString(llIntegerToBase64(c),-2,-1)+
           llDeleteSubString(llIntegerToBase64(d),-2,-1);
}
key B64ToKey(string s)
{   return FourInts2Key(
        llBase64ToInteger(llGetSubString(s, 0, 5)),
        llBase64ToInteger(llGetSubString(s, 6,11)),
        llBase64ToInteger(llGetSubString(s,12,17)),
        llBase64ToInteger(llGetSubString(s,18,23))
    );
}
string KeyToB95(string s)
{   integer a = (integer)("0x"+s);
    integer b = (integer)("0x"+llGetSubString(s,9,12)+llGetSubString(s,14,17));
    integer c = (integer)("0x"+llGetSubString(s,19,22)+llGetSubString(s,24,27));
    integer d = (integer)("0x"+llGetSubString(s,-8,-1));
    return IntegerToB95(a)+
           IntegerToB95(b)+
           IntegerToB95(c)+
           IntegerToB95(d);
}
key B95ToKey(string s)
{   return FourInts2Key(
        B95ToInteger(llGetSubString(s, 0, 4)),
        B95ToInteger(llGetSubString(s, 5, 9)),
        B95ToInteger(llGetSubString(s,10,14)),
        B95ToInteger(llGetSubString(s,15,19))
    );
}
string IntegerToB95(integer X)
{   string ret;
    integer i; // intermediate values.
    integer delta = 32;
    if(X<0) delta = 127; // 32+95

    X = X-(i=(X/(95*95*95*95)))*95*95*95*95;
    ret+=llChar(i+delta);
    //llOwnerSay((string)i);
    X = X-(i=(X/(95*95*95)))*95*95*95;
    ret+=llChar(i+delta);
    //llOwnerSay((string)i);
    X = X-(i=(X/(95*95)))*95*95;
    ret+=llChar(i+delta);
    //llOwnerSay((string)i);
    X = X-(i=(X/95))*95;
    ret+=llChar(i+delta)+llChar(X+delta);
    //llOwnerSay((string)i);
    return ret;
}
integer B95ToInteger(string s)
{   integer delta = 32;
    if(llOrd(s,0)>=80) delta = 127; // 80 = 32+ 95/2
    return
    (95*95*95*95*(llOrd(s,0)-delta))+
       (95*95*95*(llOrd(s,1)-delta))+
          (95*95*(llOrd(s,2)-delta))+
             (95*(llOrd(s,3)-delta))+
                 (llOrd(s,4)-delta);
}
key FourInts2Key(integer a, integer b, integer c, integer d)
{       // convert to key format.
    string ret = int2hex(a)+int2hex(b)+int2hex(c)+int2hex(d);
    ret=llInsertString(ret,20,"-");
    ret=llInsertString(ret,16,"-");
    ret=llInsertString(ret,12,"-");
    ret=llInsertString(ret,8,"-");
    return ret; // automatic string to key conversion.
}
string int2hex(integer i)
{   // lowercase. replace all 39's with 7's for UPPERCASE.
    string ret;
    integer w;
    w = (i&0x70000000)>>28;
    w+= 8*(i<0); // correct for LSL 'arithmetic shift'.
    ret += llChar(0x30+w+39*(w>=10));
    w = (i&0x0F000000)>>24;
    ret += llChar(0x30+w+39*(w>=10));
    w = (i&0x00F00000)>>20;
    ret += llChar(0x30+w+39*(w>=10));
    w = (i&0x000F0000)>>16;
    ret += llChar(0x30+w+39*(w>=10));
    w = (i&0x0000F000)>>12;
    ret += llChar(0x30+w+39*(w>=10));
    w = (i&0x00000F00)>>8;
    ret += llChar(0x30+w+39*(w>=10));
    w = (i&0x000000F0)>>4;
    ret += llChar(0x30+w+39*(w>=10));
    w = (i&0x0000000F);
    ret += llChar(0x30+w+39*(w>=10));
    return ret;
}


default
{
    state_entry()
    {
        key k = llGenerateKey();
        string b64 = KeyToB64(k);
        key after = B64ToKey(b64);
        llOwnerSay(llList2CSV([k,b64,after]));
        
        string b95 = KeyToB95(k);
        after = B95ToKey(b95);
        llOwnerSay(llList2CSV([k,b95,after]));
        
        /* // sanity check for negative numbers.
        integer rand = (integer)llFrand(1000000000)-2000000000;
        string b95 = IntegerToB95(rand);
        integer aft = B95ToInteger(b95);
        llOwnerSay(llList2CSV([rand,b95,aft]));
        */
        
    }
}

 

Edited January 16, 2023 by Quistess Alpha