Key Compression

Key Compression

One annoying issue with the current LSL language is its handling of keys. Keys are essentially stored as strings, 36 characters long, that is; 32 hexadecimal characters, plus four hyphens. This is a total of 36-bytes (UTF-8) or even 72-bytes (UTF-16), for a key, which in truth represents a 128-bit (16-byte) integer value. Pretty wasteful!

For this reason, scripts which store a lot of keys can run of out memory very quickly, or may find that they can't fit many keys into a message, especially when sending to a webiste. For this reason it may be beneficial to use key-compression, to reduce the size of keys.

Script

Description

The following script compresses keys into a more compact, base 256 representation of the key. The alphabet used for this is arbitrary, and you may substitute your own preferred 256 characters if you wish, but must make sure you use these for both compression and decompression!

The functions you will be interested in are compressKey() and decompressKey(), you do not need to add both to your script, indeed most scripts only require one of the two functions.

A compressed key will typically be a little smaller than 50% the size of the key it represents.

You should only use these functions in scripts where the number of compressions/decompressions is relatively low. Decompressions are much faster than compressions, but still add overhead. If however you are mainly just storing the keys, or only occasionally need the key itself for something, then compression can be ideal. Comparisons can actually benefit greatly from compression, as the shorter length of the strings means that the comparison can be performed a lot faster, not as quickly as comparing two 128-bit integers, but we don't have those =)

Serialisation

One important note when serialising compressed keys stored in lists is that llList2CSV() and llCSV2List() tend to introduce errors and may result in incorrectly decompressed keys. You are recommended to use the following:

<lsl>list compressedKeys = ...; string str = llDumpList2String(compressedKeys, ","); list lst = llParseStringKeepNulls(str, [","], []);</lsl>

In most cases these functions are actually faster (not sure why) and will ensure correct serialisation/de-serialisation of lists containing compressed keys. If you have lists containing vectors and/or rotations then you will already be using these, however you should ensure that any custom character you use for separating entries is NOT part of the base256 alphabet provided (if it is then you should either change to a comma, or place a different character into the base256 alphabet in your character's place).

Implementation

<lsl>string lslBase256Chars = "0123456789abcdefghijklmnopqrstuvwxyz!\"#$%&'()*+™-./:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`{|}~¡¢£¤¥¦§¨©ª«¬­®¯°±²³´µ¶·¸¹º»¼½¾¿ÀÁÂÃÄÅÆÇÈÉÊËÌÍÎÏÐÑÒÓÔÕÖ×ØÙÚÛÜÝÞßàáâãäåæçèéêëìíîïðñòóôõö÷øùúûüýþÿĀāĂ㥹ĆćĈĉĊċČčĎďĐđĒēĔĕĖėĘęĚěĜĝĞğĠġĢģĤĥĦħĨĩĪīĬĭĮįİıIJijĴĵĶķĸĹĺĻļĽľĿŀŁłŃńŅ"; string lslHexChars = "0123456789abcdef";

string compressKey(key _key) {

   string k = llToLower((string)llParseString2List((string)_key, ["-"], []));
   integer l = llStringLength(k);
   integer j;
   integer v;
   
   string out = "";
   integer i = 0;
   do {
       j = i + 1;
       v = (llSubStringIndex(lslHexChars, llGetSubString(k, i, i)) << 4) | 
           llSubStringIndex(lslHexChars, llGetSubString(k, j, j));
       out = (out = "") + out + llGetSubString(lslBase256Chars, v, v);
   } while ((i += 2) < l);
   
   return (out = k = "") + out;

}

key decompressKey(string k) {

   integer l = llStringLength(k);
   string out = "";
   integer v; integer j; integer x;
   integer i = 0;
   
   do {
       v = llSubStringIndex(lslBase256Chars, llGetSubString(k, i, i));
       j = v >> 4; x = v & 0xF;
       out = (out = "") + out + 
           llGetSubString(lslHexChars, j, j) + 
           llGetSubString(lslHexChars, x, x);
   } while ((++i) < l);
   
   return (key)llInsertString(
       llInsertString(
           llInsertString(
               llInsertString((out = "") + out, 8,"-"),
               13,
               "-"
           ),
           18,
           "-"
       ),
       23,
       "-"
   );

}</lsl>