Welcome to the Second Life Forums Archive

These forums are CLOSED. Please visit the new forums HERE

Discussion: Key Compressor

Yumi Murakami
DoIt!AttachTheEarOfACat!
Join date: 27 Sep 2005
Posts: 6,860
11-16-2005 15:54
Cross-posted from tips: two functioms to compress keys to reduce the memory requirements if you need to make large lists of them. Reduces a key from 36 to 22 characters, so you can store roughly 40% more in the same memory. Yays!

Note that the forum may have inserted spaces in the strings near the start - there should be no spaces in them, and no returns or anything similar. Also - technically chref doesn't need to be that long, but I left those in for future expansion to maybe actually do some proper data compression. :)

CODE

// 4 bits per char, boo.
string hexchars = "0123456789abcdef";

// 6 bits per char, yay!

string chref = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!@#$%^&*()[]{}?+-_\|',.<>~`;:";

string crunchkey(key thekey) {
integer t;
string skey = (string)thekey;
integer buffbits = 0;
integer buffval = 0;
string outkey = "";

for (t=0; t<36; t++) {
string curchar = llGetSubString(skey,t,t);
if (curchar != "-") {
integer curval = llSubStringIndex(hexchars,curchar);

buffval+=(curval << buffbits);
buffbits+=4;
if (buffbits > 5) {
integer lval = buffval & 63;
outkey += llGetSubString(chref,lval,lval);
buffval = buffval >> 6;
buffbits -= 6;
}
}
}
outkey += llGetSubString(chref,buffval,buffval);
return outkey;
}

key uncrunchkey(string crunched) {
integer t;
string outkey;
integer buffbits = 0;
integer buffval = 0;
integer outchars = 0;

for (t=0; t<22; t++) {
string curchar = llGetSubString(crunched,t,t);
integer curval = llSubStringIndex(chref,curchar);
buffval += (curval << buffbits);
buffbits += 6;
while (buffbits > 3) {
integer lval = buffval & 15;
if (outchars < 32) outkey += llGetSubString(hexchars,lval,lval);
outchars++;
if (outchars == 8) outkey += "-";
if (outchars == 12) outkey += "-";
if (outchars == 16) outkey += "-";
if (outchars == 20) outkey += "-";
buffval = buffval >> 4;
buffbits -= 4;
}

}
return (key)outkey;
}
Nada Epoch
The Librarian
Join date: 4 Nov 2002
Posts: 1,423
Original Thread
11-17-2005 18:00
/15/84/72058/1.html
_____________________
i've got nothing. ;)
Bobbyb30 Zohari
SL Mentor Coach
Join date: 11 Nov 2006
Posts: 466
02-27-2008 16:35
Very useful.
_____________________
Void Singer
Int vSelf = Sing(void);
Join date: 24 Sep 2005
Posts: 6,973
02-28-2008 01:16
wouldn't base64 conversion be faster and achieve the same thing with a little less code and possible a little faster?
_____________________
|
| . "Cat-Like Typing Detected"
| . This post may contain errors in logic, spelling, and
| . grammar known to the SL populace to cause confusion
|
| - Please Use PHP tags when posting scripts/code, Thanks.
| - Can't See PHP or URL Tags Correctly? Check Out This Link...
| -
Imaze Rhiano
Registered User
Join date: 27 Dec 2007
Posts: 39
02-28-2008 09:49
How about using hashing functions like DJB...

CODE

// Customized DJBHash function - optimized for key hashing
integer KeyToDJBHash( key id )
{
string text = (string) id;
integer i = 35;
integer hash = 5381;

while( i >= 0 )
{
hash = ( ( hash << 5 ) + hash ) +
llSubStringIndex( " -0123456789abcdef", llGetSubString( text, i, i ) );
i--;
}

return hash;
}


Of course, there is small chance for hash collission - but I think that it is more likely to get stack overflow. If you want to be sure - you could get two hash values by different functions. Or just use better hashing function...

EDIT: Ops... and of course it would be impossible to uncompress hash value back to key :P
Yumi Murakami
DoIt!AttachTheEarOfACat!
Join date: 27 Sep 2005
Posts: 6,860
02-28-2008 09:53
From: Void Singer
wouldn't base64 conversion be faster and achieve the same thing with a little less code and possible a little faster?


The problem is that the base64 conversion functions don't "know" that a string is a key and that each character can only be one of 16 possibilities (0-f).
Void Singer
Int vSelf = Sing(void);
Join date: 24 Sep 2005
Posts: 6,973
02-28-2008 11:37
From: Yumi Murakami
The problem is that the base64 conversion functions don't "know" that a string is a key and that each character can only be one of 16 possibilities (0-f).

no, but you can break any key quickly into 4 integers (remove dashes, break into 4 blocks and append 0x to the front of each block, poof, integer) feed those to the base64 function, string them together. reverse the process to undo...

mind you it was a question... I'm only guessing the code might be lighter, it may not be.
_____________________
|
| . "Cat-Like Typing Detected"
| . This post may contain errors in logic, spelling, and
| . grammar known to the SL populace to cause confusion
|
| - Please Use PHP tags when posting scripts/code, Thanks.
| - Can't See PHP or URL Tags Correctly? Check Out This Link...
| -
Hewee Zetkin
Registered User
Join date: 20 Jul 2006
Posts: 2,702
02-28-2008 14:39
From: Void Singer
no, but you can break any key quickly into 4 integers (remove dashes, break into 4 blocks and append 0x to the front of each block, poof, integer) feed those to the base64 function, string them together. reverse the process to undo...

mind you it was a question... I'm only guessing the code might be lighter, it may not be.

Might want to implement a Base64 encoding of the binary bytes of the integers rather than their string values. I don't think the llStringToBase64() would be suitable for this. The implementation would look similar to the original poster's algorithm, so I'm not sure if it would be any more efficient in terms of performance.

If the dashes were stripped from the key, you could make it a general hexStringToBase64() function, which might also be useful for other binary data encoding. Something like the code below, which hasn't yet been compiled or tested (feel free to optimize to your heart's content; I prefer simplicity and readability).

(Hit the forum's quote button to see the correct script, with whitespace intact.)
CODE

String BASE64_CHARS = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
String HEX_CHARS = "0123456789abcdef";

// param hexStr
// A hexidecimal string containing the binary data bytes (in most
// significant nibble first order) to encode. Padded with zeros to a full
// byte's worth of data. If any character in this string is not a valid
// hexidecimal character, an empty string is returned.
// param withPadding
// If true, adds the Base64 padding character ('=') to the end of the string
// to fill the output to a multiple of four characters.
// returns
// The Base64 encoding of the binary data in the hexStr parameter.
string hexStringToBase64(string hexStr, integer withPadding)
{
if (hexStr == "")
{
return "";
}
integer nInputBytes = (llStringLength(hexStr)+1)/2;

// Ensure there's enough input to fill a whole 3 bytes worth of characters.
hexStr = llToLower(hexStr)+"00000";

string outputBuffer = "";
integer byteNum;
for (byteNum = 0; byteNum < nInputBytes; byteNum += 3)
{
integer i = 2*byteNum;
integer nibble1 =
llSubStringIndex(HEX_CHARS, llGetSubString(hexStr, i, i));
integer nibble2 =
llSubStringIndex(HEX_CHARS, llGetSubString(hexStr, i+1, i+1));
integer nibble3 =
llSubStringIndex(HEX_CHARS, llGetSubString(hexStr, i+2, i+2));
integer nibble4 =
llSubStringIndex(HEX_CHARS, llGetSubString(hexStr, i+3, i+3));
integer nibble5 =
llSubStringIndex(HEX_CHARS, llGetSubString(hexStr, i+4, i+4));
integer nibble6 =
llSubStringIndex(HEX_CHARS, llGetSubString(hexStr, i+5, i+5));
if (nibble1 < 0 || nibble2 < 0 || nibble3 < 0 ||
nibble4 < 0 || nibble5 < 0 || nibble6 < 0)
{
return "";
}

integer data =
nibble1 << 20 |
nibble2 << 16 |
nibble3 << 12 |
nibble4 << 8 |
nibble5 << 4 |
nibble6;
integer c1 = data >> 18;
integer c2 = 0x3f & (data >> 12);
integer c3 = 0x3f & (data >> 6);
integer c4 = 0x3f & data;

outputBuffer +=
llGetSubString(BASE64_CHARS, c1, c1)+
llGetSubString(BASE64_CHARS, c2, c2)+
llGetSubString(BASE64_CHARS, c3, c3)+
llGetSubString(BASE64_CHARS, c4, c4);
}

integer nExtraChars = nInputBytes%3;
if (nExtraChars > 0)
{
nExtraChars += 1;

integer nOutputChars = 4*(nInputBytes/3)+nExtraChars;
outputBuffer = llGetSubString(outputBuffer, 0, nOutputChars-1);

if (withPadding)
{
while (nExtraChars-- > 0)
{
outputBuffer += "=";
}
}
}

return outputBuffer;
}

// param base64Str
// A Base64 string containing the encoded data to decode. If any character
// in this string is not a valid Base64 character, an empty string is
// returned.
// returns
// The decoded binary data bytes as a hexidecimal string, with high nibbles
// first.
string base64ToHexString(string base64Str)
{
if (base64Str == "")
{
return "";
}

integer nInputChars = llSubStringIndex(base64Str, "=");
if (nInputChars < 0)
{
nInputChars = llStringLength(base64Str);
} else
{
base64Str = llGetSubString(base64Str, 0, nInputChars-1);
}

// Ensure there's enough input to fill up to a multiple of 4 characters.
base64Str += "AAA";

string outputBuffer = "";
integer i;
for (i = 0; i < nInputChars; i += 4)
{
integer field1 =
llSubStringIndex(BASE64_CHARS, llGetSubString(hexStr, i, i));
integer field2 =
llSubStringIndex(BASE64_CHARS, llGetSubString(hexStr, i+1, i+1));
integer field3 =
llSubStringIndex(BASE64_CHARS, llGetSubString(hexStr, i+2, i+2));
integer field4 =
llSubStringIndex(BASE64_CHARS, llGetSubString(hexStr, i+3, i+3));
if (field1 < 0 || field2 < 0 || field3 < 0 || field4 < 0)
{
return "";
}

integer data =
field1 << 18 |
field2 << 12 |
field3 << 6 |
field4;
integer nibble1 = data >> 20;
integer nibble2 = 0xf & (data >> 16);
integer nibble3 = 0xf & (data >> 12);
integer nibble4 = 0xf & (data >> 8);
integer nibble5 = 0xf & (data >> 4);
integer nibble6 = 0xf & data;

outputBuffer +=
llGetSubString(HEX_CHARS, nibble1, nibble1)+
llGetSubString(HEX_CHARS, nibble2, nibble2)+
llGetSubString(HEX_CHARS, nibble3, nibble3)+
llGetSubString(HEX_CHARS, nibble4, nibble4)+
llGetSubString(HEX_CHARS, nibble5, nibble5)+
llGetSubString(HEX_CHARS, nibble6, nibble6);
}

integer nExtraBytes = nInputChars%4;
if (nExtraBytes > 0)
{
if (nExtraBytes > 1)
{
nExtraBytes -= 1;
}

integer nOutputBytes = 3*(nInputChars/4)+nExtraBytes;
outputBuffer = llGetSubString(outputBuffer, 0, 2*nOutputBytes-1);
}

return outputBuffer;
}
Void Singer
Int vSelf = Sing(void);
Join date: 24 Sep 2005
Posts: 6,973
02-28-2008 23:30
kinda like I did here?


ok not exactly, since I didn't directly convert... and looking back I could speed up a few things.
_____________________
|
| . "Cat-Like Typing Detected"
| . This post may contain errors in logic, spelling, and
| . grammar known to the SL populace to cause confusion
|
| - Please Use PHP tags when posting scripts/code, Thanks.
| - Can't See PHP or URL Tags Correctly? Check Out This Link...
| -
Hewee Zetkin
Registered User
Join date: 20 Jul 2006
Posts: 2,702
02-28-2008 23:53
Oh. Yeah. Something like that. :-) More elegant than mine, I think.