User:LindaB Helendale/keyStore

Script to store keys in order to check if a given key is in the storage.

(c) LindaB Helendale

Permission to use this script freely granted but please retain the copyright info.

Suitable for applications like visitor counters, gift givers, etc.

Not suitable for applications where you need to fetch the key from the storage, as the whole key is not stored. For such applications, see http://wiki.secondlife.com/wiki/Key_compression

Capacity of the script is more than 9200 keys.

The keys are stored by hash codes, which means that there's a possibility of a key search matching to a different key. (That is technically possible with the full UUID keys too but very unlikely).

In this script the clash probability (at least one duplicate) for 9000 stored keys is about 1 out of 100 000. That is, if this script is used in 100 000 applications with full capacity in each,

there's probably one where two keys get mapped to the same hash value.

<lsl> /**********************************************************

 Container script to store a list of keys as 42 bit hash codes 
 (c) LindaB Helendale
 Permission to use this script freely granted
 but please retain the copyright info.

 Usage via link messages.
   Request:  llMessageLinked(LINK_THIS, num, tag, uuid)
   Response: link_message(integer sender_num, integer num, string message, key id) 
 Arguments:
   tag     "LBHreq"  request to this script (denoted by > in the list of requests below)
           "LBHresp" response back to the calling script (denoted by < below)
   num: Identifier of the request or response
     > 2 : check if the key in argument uuid exists in the storage
     > 3 : check and save if not found 
     > 4 : reset the storage
     > 5 : request stats of the memory usage, see < 6
     < 0,1 : boolean response to check/save request, 1: key found, 0: key not found
     < 6   : response to stat request containing the following data in the key field 
               "Keys:9235,FreeMem:594,UsedMem:64942,Full:0"
           Keys:    number of keys in the storage
           FreeMem: free memory in bytes
           UsedMem: used memory (byte code + storage) 
           Full:    flag that is 1 if the memory has been full and oldest entries removed

 Capacity: more than 9200 keys.
   Clash probability (at least one duplicate) for 9000 keys is about 1 out of 100 000.
   (That is, if this script is used in 100 000 applications with full capacity in each,
   there's probably one where two keys get mapped to the same hash value).
            
   When the max capasity is reached, the oldest entries are removed.
   
   Techie stuff: three 14 bit fields are masked from the first and last two 16 bit words
       in the key, and converted to UTF-16 character to form a 3-character (6 byte) hash.
       The first character has the 15th bit set to 1 to avoid substring match with wrong
       alignment.

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • /

// Memory reserved for stack/heap usage on top of the byte code and static variables integer MEM_FREE_MARGIN = 200; string KEYHASH_REQUEST = "LBHreq"; string KEYHASH_RESPONSE = "LBHresp";

// ====================================================================== // encode/decode from http://wiki.secondlife.com/wiki/User:Becky_Pippen/Numeric_Storage string hexChar2(integer n)

{
    string hexChars = "0123456789abcdef";
    return llGetSubString(hexChars, n >> 4, n >> 4) +
           llGetSubString(hexChars, n & 0xf, n & 0xf);
}

string encode15BitsToChar(integer num)
{
    // Check the incoming range
    if (num < 0 || num >= 0x8000) {
        // illegal input -- do whatever is appropriate
        return "?";
    }
    // Bias the incoming numeric value by 0x1000 to avoid illegal Unicode codes:
    num += 0x1000;
    // construct an escaped hex UTF-8 representation:
    string utf8 = "%" + hexChar2(0xe0 + (num >> 12)) +
                  "%" + hexChar2(0x80 + ((num >> 6) & 0x3f)) +
                  "%" + hexChar2(0x80 + (num & 0x3f));
    // Convert the UTF-8 into a 16-bit Unicode character:
    return llUnescapeURL(utf8);
}

// This is the inverse of encode15BitsToChar(), supra, q.v.
// This expects a single 16-bit Unicode character that was created by
// encode15BitsToChar() and returns the numeric value used to create it.
// The 15-bit return value will always be in the range 0x0000 - 0x7fff.
//
integer decodeCharTo15Bits(string ch)
{
    integer retVal;
    string utf8 = llEscapeURL(ch); // convert to escaped hex UTF-8
    retVal =  (((integer)("0x" + llGetSubString(utf8, 1, 2)) & 0x1f) << 12) +
              (((integer)("0x" + llGetSubString(utf8, 4, 5)) & 0x3f) << 6) +
               ((integer)("0x" + llGetSubString(utf8, 7, 8)) & 0x3f);
    return retVal - 0x1000;
}

// =====================================================================

// Hash storage string gArray; integer gFullFlag=0;

string key2hash(key id) {

   string hash=llMD5String((string)id,1716);
   integer mask14b = 0x3FFF;
   return
       encode15BitsToChar( ((integer)("0x" + llGetSubString(hash,0,3)) & mask14b) | (1<<14) ) +
       encode15BitsToChar( ((integer)("0x" + llGetSubString(hash,4,7)) & mask14b) ) +
       encode15BitsToChar( ((integer)("0x" + llGetSubString(hash,8,11)) & mask14b) ) ;
   

}

integer get_free_mem() {

   return llGetMemoryLimit()-llGetUsedMemory();

}

default {

   link_message(integer sender_num, integer num, string message, key id) 
   {
       if (message != KEYHASH_REQUEST) return;
       
       integer response;
       if (num == 4) llResetScript();
       if (num == 5) {
           llMessageLinked(LINK_THIS, 6, KEYHASH_RESPONSE,
               "Keys:"+(string)(llStringLength(gArray)/3) +
               ",FreeMem:" + (string)get_free_mem() +
               ",UsedMem:" + (string)llGetUsedMemory() +
               ",Full:" + (string)gFullFlag);
           return;
       }
       
       if ( !( num == 2 || num == 3) )  return;
       string hash = key2hash(id);
       response = llSubStringIndex(gArray, hash) > -1 ;
       if (num == 3 && !response) {
           gArray += hash;
           // memory check
           integer freeMem=get_free_mem();
           if (freeMem < MEM_FREE_MARGIN) {
               // remove oldest entries... 120 is arbitrary amount to remove, chosen just
               // because divisible by 2,3,4,5,6 so it's robust against hash length changes
               gArray = llDeleteSubString(gArray,0,119);
               gFullFlag=1;
           }
       }
       llMessageLinked(LINK_THIS, response,KEYHASH_RESPONSE,id);
   }

} </lsl>

Example application script, that stores the keys of the avatars in the sim on click, and prints the avatar names for those that havn't been stored before.

<lsl> /**

 Demo script for 'lindalib container 42bit key hash'
 (c) LindaB Helendale, permission to use this script freely granted, but
       please retain the copyright info.
       
 When you click the object, it adds all avatars in the sim to the key storage
 and prints out all never seen people. 

• • /

string KEYHASH_REQUEST = "LBHreq"; string KEYHASH_RESPONSE = "LBHresp";

integer gAvInd=-1; list gAvList; integer gNewAvis;

add_avatars() {

   gAvList=llGetAgentList(AGENT_LIST_REGION , []);
   llOwnerSay("Checking " + (string)llGetListLength(gAvList) + " avatars in the sim...");
   gAvInd=0;
   gNewAvis=0;
   llMessageLinked(LINK_THIS, 3, KEYHASH_REQUEST, llList2Key(gAvList,gAvInd));            

}

default {

   state_entry()
   {
       // To reset the storage uncomment the following
       // llMessageLinked(LINK_THIS, 4, "", "");
   }
   
   changed( integer ch )
   {
       if (ch & CHANGED_OWNER) {
           // reset the key storage
           llMessageLinked(LINK_THIS, 4, KEYHASH_REQUEST, "");
           llResetScript();
       }
   }
       
   touch_start(integer num) {
       if (gAvInd != -1) {
           llOwnerSay("Processing previous command....");
           return;
       }
       add_avatars();
   }

   link_message(integer sender_num, integer num, string message, key id) 
   {
       if (message ==  KEYHASH_RESPONSE) {
           if (num==6) {
               //stats response
               llOwnerSay("Never seen avatars " + (string)gNewAvis +
                   " out of " + (string)llGetListLength(gAvList));
               llOwnerSay("Key storage stats: " + (string)id);
               return;
           }
           // response from checking/saving avatar # gAvInd
           if (num==0) {
               llOwnerSay("New av: " + llKey2Name(id));
               gNewAvis++;
           }
           gAvInd++;
           if (gAvInd<llGetListLength(gAvList)) {
               // next av
               llMessageLinked(LINK_THIS, 3, KEYHASH_REQUEST, llList2Key(gAvList,gAvInd));           
           }else{
               // all added, request stats
               gAvInd=-1;
               llMessageLinked(LINK_THIS, 5, KEYHASH_REQUEST, "");
           }
       }
   }

} </lsl>