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.

 
/**********************************************************
  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 MD5 hash of the key
        and converted to UTF-16 characters 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);
    }
}

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.

 
/**
  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, "");
            }
        }
    }
}