LZW LSL Implementation

= LZW LSL Implementation =
== Description ==
=== Overview ===
The following is an LSL implementation of the LZW light-weight compression algorithm. It gives modest compression (20-40% for natural language) with good performance and low memory consumption.
You will see little to no gain on small messages (only a hundred characters or so) with the default settings, which are intended for larger message (several hundred to a thousand characters) where the gains are quite good. If you wish to improve compression for smaller messages then you should tweak the LSLLZW_CODE_WIDTH value from the default 12-bits to a lower value no less than 9-bits. With the current memory limits you are not recommended to increase this value beyond 12-bits.
=== License ===
You may use the following code freely in your own work, provided you credit the author (Haravikk Mistral) and supply a link to this wiki article where feasible. You may use this implementation in commercial works. If you add enhanced support for alternate modes of operation, padding schemes or produce other enhancements to the engine, then you are asked to please contribute them to this wiki-article.
== Details ==
=== Basic usage ===
This script is designed to operate as a compression "server", in that you communicate with it using linked-messages to compress/decompress your text. To learn how to do this, you are perhaps best off looking at the helper functions and examples available for this script.
=== Script ===
// These variables are used to build communications. Commands are sent as 
// combined bits in the integer argument of a link-message, and are 
// recovered using masks, you may wish to read about bit-masks before 
// editing these values. These are used so the string argument is 
// kept free for data only.
//
// Commands take the following form (in hex):
// 0xFFMMIOvv
// Where the letters are:
// F Filter, used to quickly determine if a message is for us.
// C Command; encrypt/decrypt etc.
// I Type of data provided (hex, base64, etc.).
// O Desired type of data to be returned (hex, base64, etc.), 
// this is unused in replies as the reply's value for I will 
// be the request's value for O.
// v Variable, depends on mode.
// This mask allows the filter byte to be retrieved quickly
integer LSLLZW_FILTER_MASK = 0xFF000000;
// This mask allows the mask byte to be retrieved quickly
integer LSLLZW_COMMAND_MASK = 0x00FF0000;
// This mask allows the input type to be retrieved quickly
integer LSLLZW_INPUT_TYPE_MASK = 0x0000F000;
// This mask allows the output type to be retireved quickly
integer LSLLZW_OUTPUT_TYPE_MASK = 0x00000F00;
// This mask allows the variable to retrieved quickly
integer LSLLZW_VARIABLE_MASK = 0x000000FF;
// How many bits right variable must be shifted
integer LSLLZW_VARIABLE_SHIFT = 0;
// A request
integer LSLLZW_FILTER_REQUEST = 0x83000000;
// A reply
integer LSLLZW_FILTER_REPLY = 0x84000000;
// An error occurred
integer LSLLZW_COMMAND_ERROR = 0x00000000;
// Prime engine with key
integer LSLLZW_COMMAND_COMPRESS = 0x00010000;
// Encrypt message using expanded key
integer LSLLZW_COMMAND_DECOMPRESS = 0x00020000;
// Input type is hex
integer LSLLZW_INPUT_HEX = 0x00000000;
// Input type is base64
integer LSLLZW_INPUT_BASE64 = 0x00001000;
// Output type is hex
integer LSLLZW_OUTPUT_HEX = 0x00000000;
// Output type is base64
integer LSLLZW_OUTPUT_BASE64 = 0x00000100;
 
// Refuse any data longer than this many characters
integer LSLLZW_MAX_SIZE = 2304;
integer LSLLZW_CODE_WIDTH = 12; // Maximum code-width, restricts table
integer LSLLZW_MIN_DATA_SIZE = 32; // Data must be at least this many 
 // bits long or compression is 
 // pointless.
string LSLLZW_HEX_CHARS = "0123456789abcdef";
string LSLLZW_BASE64_CHARS = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
// Load value as integers from a base64 string
list lslLZWBase64ToBytes(string base64Data) {
 integer x = llSubStringIndex(base64Data, "=");
 if (x > 0) 
 base64Data = llDeleteSubString(
 (base64Data = "") + base64Data, 
 x,
 -1
 );
 return lslLZWStringToBytes(
 (base64Data = "") + base64Data, 
 6, 
 LSLLZW_BASE64_CHARS
 );
}
 
// Load value as integers from a hex string
list lslLZWHexToBytes(string hexData) {
 if (llGetSubString(hexData, 0, 1) == "0x") 
 hexData = llDeleteSubString((hexData = "") + hexData, 0, 1);
 return lslLZWStringToBytes(
 llToLower((hexData = "") + hexData), 
 4, 
 LSLLZW_HEX_CHARS
 );
}
// Loads a string as a list of integers, using the given bit <width> and 
// appropriate <alphabet> into Key
list lslLZWStringToBytes(string s, integer width, string alphabet) {
 integer l = llStringLength(s);
 
 list n = [l * width]; // Add bit-length
 integer bitbuf = 0;
 integer adjust = 32;
 
 integer i = 0;
 integer val;
 while (i < l) {
 val = llSubStringIndex(alphabet, llGetSubString(s, i, i));
 if (val < 0) {
 s = "";
 return (n = []) + 
 ["Invalid character at index "+(string)i];
 }
 
 if ((adjust -= width) <= 0) {
 bitbuf = bitbuf | (val >> -adjust);
 n = (n = []) + n + [bitbuf];
 
 adjust += 32;
 if (adjust < 32) bitbuf = (val << adjust);
 else bitbuf = 0;
 } else bitbuf = bitbuf | (val << adjust);
 
 ++i;
 }
 
 s = "";
 if (adjust < 32) 
 return (n = []) + n + [bitbuf];
 return (n = []) + n;
}
 
// Returns a hex string representing integers b, preceeded with "0x".
string lslLZWBytesToHex(list b) {
 return "0x" + lslLZWBytesToString((b = []) + b, 4, LSLLZW_HEX_CHARS);
}
 
// Returns a base64 string representing integers b, with padding equals signs
string lslLZWBytesToBase64(list b) {
 string s = lslLZWBytesToString((b = []) + b, 6, LSLLZW_BASE64_CHARS);
 integer l = llStringLength(s) % 4;
 if (l) {
 if (l == 2) return (s = "") + s + "==";
 return (s = "") + s + "=";
 }
 return (s = "") + s;
}
 
// Outputs integer data from b as characters representing width bits taken from 
// alphabet
string lslLZWBytesToString(list b, integer width, string alphabet) {
 integer bits = llList2Integer(b, 0);
 
 integer i = 0;
 integer mask = ~(-1 << width);
 integer shift = 32 - width;
 
 integer available = 0;
 integer prev = 0;
 integer buf;
 integer extra;
 integer value;
 
 string s = "";
 
 @lslLZWBytesToStringLoop;
 if((bits -= 32) > -32) {
 available += 32 + (bits * (0 > bits));
 buf = llList2Integer(b, ++i);
 if (available >= width) {
 if (prev) {
 s = (s = "") + s + 
 llGetSubString(
 alphabet, 
 value = (
 extra | 
 (
 (buf >> (shift + prev)) & 
 ~(-1 << (width - prev))
 )
 ), 
 value
 );
 buf = buf << (width - prev);
 available -= width;
 }
 while(available >= width) {
 s = (s = "") + s + 
 llGetSubString(
 alphabet, 
 value = ((buf >> shift) & mask),
 value
 );
 buf = buf << width;
 available -= width;
 }
 if (prev = available) // Update prev
 extra = (buf >> shift) & mask;
 jump lslLZWBytesToStringLoop;
 }
 }
 if(available) {
 mask = -1 << (width - prev);
 return (s = "") + s + 
 llGetSubString(
 alphabet, 
 value = ((extra & mask) | 
 (
 (buf >> (shift + prev)) & 
 ((-1 << (width - available)) ^ mask))
 ), 
 value
 );
 }
 return (s = "") + s;
}
// Compresses the binary data using LZW compression
list lslLZWCompress(list data) {
 integer dataBits = llList2Integer(data, 0);
 if (dataBits <= LSLLZW_MIN_DATA_SIZE) 
 return [
 "Data too short! Must be at least " + 
 (string)LSLLZW_MIN_DATA_SIZE + " bits long to compress"
 ];
 
 // Remove header
 data = llDeleteSubList((data = []) + data, 0, 0);
 
 // Set-up output
 integer outBits = 0;
 list output = [];
 integer outBuf = 0;
 integer outBit = 32;
 
 // Set-up dictionary
 list dictionary = [];
 integer nextCode = 256; // 0-255 are the basic codes
 integer maxCode = (1 << LSLLZW_CODE_WIDTH) - 1;
 
 // Set-up reading
 integer inBuf = llList2Integer(data, 0);
 integer inBit = 24;
 
 // Process characters
 integer code = (inBuf >> inBit) & 0xFF;
 integer char = 0;
 integer hash = 0;
 integer x = 0;
 
 while ((dataBits -= 8) > 0) {
 // Load more data as required
 if ((inBit -= 8) < 0) {
 data = llDeleteSubList((data = []) + data, 0, 0);
 inBuf = llList2Integer(data, 0);
 inBit = 24;
 }
 
 // Grab a new character
 char = (inBuf >> inBit) & 0xFF;
 
 // Create a hash and look-it up
 hash = (code << 8) | char;
 
 if ((x = llListFindList(dictionary, [hash])) >= 0) 
 code = 256 + x; // Entry exists, update code
 else { // Need to create a new entry
 if (nextCode <= maxCode) {
 dictionary = (dictionary = []) + dictionary + [hash];
 ++nextCode;
 }
 
 // Output the currently held code
 outBit -= LSLLZW_CODE_WIDTH;
 outBits += LSLLZW_CODE_WIDTH;
 
 if (outBit > 0) 
 outBuf = outBuf | (code << outBit);
 else {
 outBuf = outBuf | (code >> -outBit);
 output = (output = []) + output + [outBuf];
 
 outBit += 32;
 if (outBit >= 32) outBuf = 0;
 else outBuf = (code << outBit);
 }
 
 code = char;
 }
 }
 
 // Output final code(s)
 outBit -= LSLLZW_CODE_WIDTH;
 outBits += LSLLZW_CODE_WIDTH;
 list t = [];
 
 if (outBit >= 0) t = [outBuf | (code << outBit)];
 else {
 outBuf = outBuf | (code >> -outBit);
 outBit += 32;
 t = [(code << outBit), outBuf];
 }
 
 return (t = data = output = dictionary = []) + [outBits] + output + t;
}
list lslLZWDecompress(list data) {
 integer dataBits = llList2Integer(data, 0);
 if (dataBits <= LSLLZW_MIN_DATA_SIZE) 
 return [
 "Data too short! Must be at least " + 
 (string)LSLLZW_MIN_DATA_SIZE + " bits long to compress"
 ];
 
 // Remove header
 data = llDeleteSubList((data = []) + data, 0, 0);
 
 // Set-up dictionary
 list dictionary = [];
 list prefixes = [];
 integer nextCode = 256; // 0-255 are the basic codes
 integer maxCode = (1 << LSLLZW_CODE_WIDTH) - 1;
 
 // Set-up reading
 integer inBuf = llList2Integer(data, 0);
 integer inPrev = 0;
 integer inBit = 32 - LSLLZW_CODE_WIDTH;
 
 // Process characters
 integer oldCode = (inBuf >> inBit) & maxCode;
 integer code = 0;
 integer char = oldCode;
 list stack = [];
 integer x = 0;
 integer t = 0;
 
 // Set-up output
 integer outBits = 8;
 list output = [];
 integer outBuf = oldCode << 24;
 integer outBit = 24;
 
 integer DELETE = 0;
 
 while ((dataBits -= LSLLZW_CODE_WIDTH) > 0) {
 // Load more data as required
 if ((inBit -= LSLLZW_CODE_WIDTH) < 0) {
 inPrev = inBuf;
 data = llDeleteSubList((data = []) + data, 0, 0);
 inBuf = llList2Integer(data, 0);
 inBit += 32;
 }
 
 // Grab a new character
 if (!inBit || (inBit >= 32)) code = 0;
 else code = (inPrev << (32 - inBit)) & maxCode;
 
 x = 32 - LSLLZW_CODE_WIDTH;
 if (inBit > x) // Watch out for sign-bit carry distorting result!
 code = code | ((inBuf >> inBit) & ((1 << (32 - inBit)) - 1));
 else code = code | ((inBuf >> inBit) & maxCode);
 
 // Once we have the code we need to look-up it's contents
 if (code >= nextCode) {
 stack = [code];
 x = oldCode;
 } else x = code;
 
 // Produce a stack of codes and sub-codes
 while (x > 255) {
 x -= 256;
 stack = (stack = []) + stack + 
 llList2List(dictionary, x, x);
 x = llList2Integer(prefixes, x);
 }
 stack = (stack = []) + stack + [x];
 
 // Now we output the contents of the stack as the original 
 // characters
 x = stack != [];
 char = llList2Integer(stack, -1);
 while ((--x) >= 0) {
 t = llList2Integer(stack, x);
 
 outBit -= 8;
 outBits += 8;
 
 if (outBit > 0) outBuf = outBuf | (t << outBit);
 else {
 output = (output = []) + output + [outBuf | t];
 outBit = 32;
 outBuf = 0;
 }
 }
 stack = [];
 
 if (nextCode <= maxCode) {
 prefixes = (prefixes = []) + prefixes + [oldCode];
 dictionary = (dictionary = []) + dictionary + [char];
 ++nextCode;
 }
 
 oldCode = code;
 }
 
 // Output final code(s)
 if (outBit < 32) 
 output = (output = []) + output + [outBuf];
 
 return (data = stack = output = dictionary = []) + [outBits] + output;
}
error(integer link, string str, key id) {
 llMessageLinked(
 link,
 LSLLZW_FILTER_REPLY | LSLLZW_COMMAND_ERROR,
 str,
 id
 );
}
default { 
 link_message(integer x, integer y, string msg, key id) { 
 // Is the message for us?
 if ((y & LSLLZW_FILTER_MASK) == LSLLZW_FILTER_REQUEST) {
 // Refuse overly large messages
 if (llStringLength(msg) > LSLLZW_MAX_SIZE) {
 error(
 x, 
 "Maxmimum message length is " + 
 (string)LSLLZW_MAX_SIZE + 
 " characters", 
 id
 );
 return;
 }
 
 // What type of data do we have?
 integer type = y & LSLLZW_INPUT_TYPE_MASK;
 list data = [];
 if (type == LSLLZW_INPUT_HEX) 
 data = lslLZWHexToBytes((msg = "") + msg);
 else if (type == LSLLZW_INPUT_BASE64) 
 data = lslLZWBase64ToBytes((msg = "") + msg);
 else data = [(msg = "") + "Unsupported input-type"];
 
 // Was data parsed successfully?
 if (llGetListEntryType(data, 0) != TYPE_INTEGER) {
 error(x, llList2String((data = []) + data, 0), id);
 return;
 }
 
 // Now determine mode of operation
 type = y & LSLLZW_COMMAND_MASK;
 if (type == LSLLZW_COMMAND_COMPRESS) 
 data = lslLZWCompress((data = []) + data);
 else if (type == LSLLZW_COMMAND_DECOMPRESS) 
 data = lslLZWDecompress((data = []) + data);
 else data = ["Unsupported mode"];
 
 // Was mode executed successfully?
 if (llGetListEntryType(data, 0) != TYPE_INTEGER) {
 error(x, llList2String((data = []) + data, 0), id);
 return;
 }
 
 // Convert into requested output type
 integer output = y & LSLLZW_OUTPUT_TYPE_MASK;
 if (output == LSLLZW_OUTPUT_HEX) {
 msg = lslLZWBytesToHex((data = []) + data);
 output = LSLLZW_INPUT_HEX;
 } else if (output == LSLLZW_OUTPUT_BASE64) {
 msg = lslLZWBytesToBase64((data = []) + data);
 output = LSLLZW_INPUT_BASE64;
 } else {
 error(x, "Invalid output type", id);
 return;
 }
 
 // Construct reply
 llMessageLinked(
 x,
 LSLLZW_FILTER_REPLY | type | output,
 (msg = "") + msg,
 id
 );
 }
 }
}