Talk:Key Compression

From Second Life Wiki
Revision as of 17:04, 5 February 2015 by Pedro Oval (talk | contribs) (Nitpick and sign)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Recommending the following for base64 example for compatibility:

string keyToBase64(string s) {
   s = llDumpList2String(llParseString2List(s, ["-"], []), "");
   return
      llGetSubString(llIntegerToBase64((integer)("0x"+llGetSubString(s,0,5))<<8),0,3) +
      llGetSubString(llIntegerToBase64((integer)("0x"+llGetSubString(s,6,11))<<8),0,3) +
      llGetSubString(llIntegerToBase64((integer)("0x"+llGetSubString(s,12,17))<<8),0,3) +
      llGetSubString(llIntegerToBase64((integer)("0x"+llGetSubString(s,18,23))<<8),0,3) +
      llGetSubString(llIntegerToBase64((integer)("0x"+llGetSubString(s,24,29))<<8),0,3) +
      llGetSubString(llIntegerToBase64((integer)("0x"+llGetSubString(s,30,31))<<24),0,1);
}

string integer2hex(integer in) {
   string s = "0123456789abcdef";
   string ret = "";
   integer i;
   in = in >> 8;
   for (i = 0; i < 6; i++) {
      ret = llGetSubString(s, in & 0xF, in & 0xF) + ret;
      in = in >> 4;
   }
   return ret;
}

string pad_dash(string s) {
   return
      llGetSubString(s, 0, 7) + "-" +
      llGetSubString(s, 8,11) + "-" +
      llGetSubString(s,12,15) + "-" +
      llGetSubString(s,16,19) + "-" +
      llGetSubString(s,20,31);
}

key base64ToKey(string s) {
   return (key) pad_dash(
      integer2hex(llBase64ToInteger(llGetSubString(s,0,3))) +
      integer2hex(llBase64ToInteger(llGetSubString(s,4,7))) +
      integer2hex(llBase64ToInteger(llGetSubString(s,8,11))) +
      integer2hex(llBase64ToInteger(llGetSubString(s,12,15))) +
      integer2hex(llBase64ToInteger(llGetSubString(s,16,19))) +
      integer2hex(llBase64ToInteger(llGetSubString(s,20,21)+"AA")));
}

Base 32768 optimized for size in Mono

// Copyright (C) 2009 Adam Wozniak and Doran Zemlja
// Copyright (C) 2015 Pedro Oval
// Released into the public domain.
// Free for anyone to use for any purpose they like.
//
// INTERNALLY, strings are represented as UTF-16, and internal memory
// is what we actually care about
//
// going for maximum compression, we should be able to get a 128 bit key
// down to 8 x 16 bit characters
//
// we'll do this by encoding integers as UTF-8 URL escaped characters,
// and calling llUnescapeURL to convert them to strings.
//
// unfortunately, UTF-16 has some unallowed codepoints.  In particular,
// llEscapeURL/llUnescapeURL fails on the following code points:
//
// 0000, D800-DFFF, FDD0-FDEF, FFFE, FFFF
//
// Let's just make our lives easy and go with 15 bits per character.
// We'll encode 0000-7FFF as 0100-8100 to avoid null characters and leave
// all ASCII characters available as serialisation seperators.
// Also, let's go easy and just save up the 8 MSB as a final character at
// the end.
//
// this gives us a quick and easy 9 character key

// MOD: To make life even easier, use the range 0x800-0x87FF as they all
// start with the same UTF-8 range and there are no bits to test.
// (range is %E0-%EF)

string bhex(integer in)
{
    return llGetSubString("0123456789abcdef", (in>>4) & 0xF, (in>>4) & 0xF)
         + llGetSubString("0123456789abcdef", in & 0xF, in & 0xF);
}

integer utf2i(string c)
{
    integer ret = (integer)("0x" + (string)llParseString2List(llEscapeURL(c), (list)"%", []));
    return ((ret & 0x0F0000) >> 4) + ((ret & 0x3F00) >> 2) + (ret & 0x3F) + (integer)-0x800;
}

string i2url(integer i)
{
    i += 0x800;

    return "%" + bhex(0xE0 | (i >> 12))
         + "%" + bhex(0x80 | ((i >> 6) & 0x3F))
         + "%" + bhex(0x80 | (i & 0x3F))
         ;
}

string compress_key(string k)
{
    k = (string)llParseString2List(k, (list)"-", []);
    string ret;
    integer i = (integer)-9;
    integer msbs;
    integer word;

    while (++i)
    {
        word = (integer) ("0x" + llGetSubString(k, 4*i, ~(4*~i)));
        msbs = (msbs | (word & 0x8000)) >> 1;
        ret += i2url(word & 0x7FFF);
    }
    return llUnescapeURL(i2url(msbs) + ret);
}

string uncompress_key(string s)
{
    integer i = (integer)-9;
    integer value;
    integer msbs = utf2i(llGetSubString(s, value, value));
    string ret;
    while (++i)
    {
        value = utf2i(llGetSubString(s, i, i)) + ((msbs << (-i)) & 0x8000);
        ret += bhex(value>>8) + bhex(value);
    }
    i = 24;
    while ((i += (integer)-4) & (integer)-8)
        ret = llInsertString(ret, i, "-");
    return ret;
}

// Example usage: generate a key, compress, uncompress, and check if it matches.
default
{
    state_entry()
    {
        string k = llGenerateKey();
        string s = uncompress_key(compress_key(k));
        llOwnerSay((string)(k==s)+"\n"+k + "\n" + s);
    }
}

--Pedro Oval (talk) 16:04, 5 February 2015 (PST)