Jump to content

Store 700+ Unique UUIDs In World


LepreKhaun
 Share

You are about to reply to a thread that has been inactive for 3600 days.

Please take a moment to consider if this thread is worth bumping.

Recommended Posts

This is a simple, subordinate database storage program for a single prim object. As written it will store approximately 745 unique keys (when saved under Mono!) as well as alerting the calling program of an attempt to store a duplicated key in the data store. This would be useful for "One per Customer" offerings, "One User, One Vote", and such.

Usage is straight forward, llMessageLinked(LINK_THIS, -1, "", keyToBeStored); in the main program to check for duplication and store the key if not already in the key list. If already in list, the program sends a llMessageLinked(LINK_THIS, TRUE, "", id); ( where "id" is "keyToBeStored", so a global isn't required in the main program to keep track of this), otherwise, it stores the key and sends a llMessageLinked(LINK_THIS, FALSE, "", id); back. See the following example Harness Test script for exactly how this is used.

 

// "Store 700+ Unique UUIDs In World" by LepreKhaun 4/18/2014
//
// See http://community.secondlife.com/t5/LSL-Library/Store-700-Unique-UUIDs-In-World/td-p/2669408 for usage
// May be freely used, modified and distributed ONLY with this header intact!

list keysStored;

default
{
    link_message(integer sender_num, integer num, string str, key id)
    {
        if (~num) // abort unless num != -1
            return;
            
        // delete hyphens from key
        string str = (string)id;
        string shortKey = llDumpList2String(llParseStringKeepNulls((str = "") + str, ["-"], []), ""); 
    
        // see if the key is in list
        if(~llListFindList(keysStored, [shortKey]))
        {
            // it was found
            llMessageLinked(LINK_THIS, TRUE, "", id);
        } else {
            // it was not found, so
            // store it first
            keysStored += [shortKey];
            llMessageLinked(LINK_THIS, FALSE, "", id);
        }
    }
}

 

This Harness Test script illustrates how "Store 700+ Unique UUIDs In World" is called and how the response can be handled.

The touch_end() event handler starts an extended loop that continues in the llMessageLinked() calls within link_message(). This loop is set to stop when "Store ..." either hits a stack-heap error collision at 745 entries, or when a duplicated key is entered into the database. The second result is very unlikely using llGenerateKey() so there is a section one may uncomment to force a duplication after 100 entries.

 

// Main program "Harness Test" by LepreKhaun 4/18/2014
// for "Store 700+ Unique UUIDs In World"
//
// See http://community.secondlife.com/t5/LSL-Library/Store-700-Unique-UUIDs-In-World/td-p/2669408 for usage
// May be freely used, modified and distributed ONLY with this header intact!

integer counter;
key newKey;

default
{
    touch_end(integer num)
    {
        llMessageLinked(LINK_THIS, -1, "", llGenerateKey());
    }
    
    link_message(integer sender_num, integer num, string str, key id)
    {
        // increment counter and check for near capacity
        if(counter == 700)
        {
            llInstantMessage(llGetOwner(), "Warning Storage is at 700 keys!");
        }
        
        if(~num) // ignore if num == -1, we sent the message
        {
            if(num)
            {
                // The key was already in list
                llOwnerSay("Oh, Noooo!!! Duplicated Key!\n" + (string)id);
            } else {
                // The key was not in list but has been added
                llOwnerSay("Key #" + (string)(++counter) + " ==\n" + (string)id);
                
// comment next if statement for maximum storage test
// otherwise, remove "//" for duplicate key reaction
//              if (counter != 100)
                    newKey = llGenerateKey();
                
                llMessageLinked(LINK_THIS, -1, "", newKey);
            }
        }
    }
}

 

NOTES:

  1. Since both scripts are in the same prim, they both can "hear" their own link messages, so a means must be in place to differentiate between them. In this case, I am using "integer num", the second parameter of both llMessageLinked() and link_message(), and taking advantage of the fact that a bitwise NOT applied to -1 results in 0 (refer to usage of "if(~num){}" in both programs). There are other schemes one can use for this.
  2. For maximum storage, the 4 hyphens are stripped from each key before being stored as a string in the global list "keysStored". I've found only one other storage method that enables one to store more than this (by translating a key into a list of 4 integers), however the complexity of the supporting functions to handle this method precludes any easily modified versions.
  3. For repeated testing of the two scripts, both must be reset; one so the global list can be cleared, the other so that "counter" can be reset to 0.
  4. It might be noted that after about 300 iterations, the counter numbers appearing in chat will lose coherency and no longer appear in order. This is expected behavior and only another way of showing that LSL is asynchronous, always.
  5. For storage of much more than 700 UUID keys, off world storage should be considered.
  6. As always, any questions, comments, suggestions, corrections and constructive criticisms are welcome and appreciated.


[Edited for minor grammar corrections. Nit picking up to the last!]

  • Like 1
Link to comment
Share on other sites

If you need to store a LOT more, then you can accomplish this by first performing a hash of the UUID and then push a part of this to the list to store..

The chance of collision will be incredibly small and as long as that's not going to prove to be a statistically important issue, then you can store thousands of unique users.

  • Like 1
Link to comment
Share on other sites


Sassy Romano wrote:

If you need to store a LOT more, then you can accomplish this by first performing a hash of the UUID and then push a part of this to the list to store..

The chance of collision will be incredibly small and as long as that's not going to prove to be a statistically important issue, then you can store thousands of unique users.

Ahhh, I like!

 

Though that does raise the Birthday Paradox (where the possibilty isn't as small as one might think and Murphy's Law should always be considered in these things!) as well as precluding any further development that would require a lossless compression that I used to begin with.

 

// "Store 700+ Unique UUIDs In World" by LepreKhaun 4/18/2014// Modified 4/23/2014 using the suggestion of// Sassy Romano (thank you!) to use a hashing algorithm//// This version will store ***3,784*** keys! // BUT with a probability greater than 0.1% of a collision// (meaning- every so often, a key will be falsely said to be found).//// See http://community.secondlife.com/t5/LSL-Library/Store-700-Unique-UUIDs-In-World/td-p/2669408 for usage// May be freely used, modified and distributed ONLY with this header intact!//list keysStored;default{    link_message(integer sender_num, integer num, string str, key id)    {        if (~num) // abort unless num != -1            return;                    // delete hyphens from key        string str = (string)id;        str = llDumpList2String(llParseStringKeepNulls((str = "") + str, ["-"], []), "");         // form 4 integers from key and XOR them together into one        integer xorHash=(integer)("0x" + llGetSubString(str, 0, 7)) ^                         (integer)("0x" + llGetSubString(str, 8, 15)) ^                         (integer)("0x" + llGetSubString(str, 16, 23)) ^                        (integer)("0x" + llGetSubString(str, 24, -1));                // see if the key is in list        if(~llListFindList(keysStored, [xorHash]))        {            // it was found            llMessageLinked(LINK_THIS, TRUE, "", id);        } else {            // it was not found, so            // store it first            keysStored += [xorHash];            llMessageLinked(LINK_THIS, FALSE, "", id);        }    }}

 

[ ETA: Trivia bit- 820,000,000,000 of our 128-bit UUID keys have a risk of 0.0000000001% of colliding. Now THAT is what I call an incredibly small chance!]

Link to comment
Share on other sites

can maybe get a little performance gain by picking direct from str. example

 

integer xorHash =    (integer)("0x" + llGetSubString(str, 0, 7)) ^    (integer)("0x" + llGetSubString(str, 8, 11) + llGetSubString(str, 12, 15)) ^    (integer)("0x" + llGetSubString(str, 16, 19) + llGetSubString(str, 20, 23)) ^   (integer)("0x" + llGetSubString(str, 24, -1));

 

havent tested it tho so only maybe

 

eta: sorry the offsets wrong. should be 9,12. 14,17. etc

Link to comment
Share on other sites


LepreKhaun wrote:


 [
ETA: Trivia bit-
 820,000,000,000 of our 128-bit UUID keys have a risk of 0.0000000001% of colliding. Now
THAT
is what I call an incredibly small chance!]

have been puzzling over this as am not sure how you calc this

 as by pigeonhole

pow(2,128) / pow(2,32) = pow(2,96)

pow(2,96) keys will have the same pow(2,32) hashcode

simplify

pow(2,4) / pow(2,1)

4 / 1

xor table

0 1 2 3

1 0 3 2

2 3 0 1

3 2 1 0

+

if assume that no persons with same xorhash do use the device within the same period then by approximation:

pow(k,2) / (2 * pow(2,32))  where k = 3874. then collision is about 1 in 600

if factor in pigeonhole then 1 in 150 about

+

or i might be missing something else altogether. is why i am a bit puzzled

Link to comment
Share on other sites


irihapeti wrote:


LepreKhaun wrote:


 [
ETA: Trivia bit-
 820,000,000,000 of our 128-bit UUID keys have a risk of 0.0000000001% of colliding. Now
THAT
is what I call an incredibly small chance!]

have been puzzling over this as am not sure how you calc this

 as by pigeonhole

pow(2,128) / pow(2,32) = pow(2,96)

pow(2,96) keys will have the same pow(2,32) hashcode

simplify

pow(2,4) / pow(2,1)

4 / 1

xor table

0 1 2 3

1 0 3 2

2 3 0 1

3 2 1 0

+

if assume that no persons with same xorhash do use the device within the same period then by approximation:

pow(k,2) / (2 * pow(2,32))  where k = 3874. then collision is about 1 in 600

if factor in pigeonhole then 1 in 150 about

+

or i might be missing something else altogether. is why i am a bit puzzled

I just used the table I linked to in that fascinating read on a little-understood subject. Just go down the #bits column to 128 (which is what a UUID key uses) and then come out across.

 

But the article itself explains how the table is derived and I'll just leave it at that. I can't explain the paradox any better than it does. It is counter-intuitive though and has bitten many a person unaware of it. Hashes can be somewhat tricky that way...

Link to comment
Share on other sites

i do again using wikipedia example. (is the same as i did before but this time i use their formula notation)

(n*n) / (2*m)

where n = 3874 and m = 4294967296

(3874 * 3874) / (2 * 4294967296)

15007876 / 8589934592 = 0.00174715

+

ok if is just 1 value in the list and add a 2nd one then n = 1

(1 * 1) / (2 * 4294967296)

1 / 8589934592 = 0.0000000001164153218

which is what you show

+

i think what caused me to be puzzled is that this formula approximates the probability of 2 or more identical values in [0..4294967295] randomly-drawn appearing in the sets [2] .. [3874]

which is not what we want to know. We want to know:

how many collisions will occur when reduce the set of all 128bit keys down to 32bit hashes?

in practice tho, there has been nearly 40 million avatar keys issued. The question then becomes: How many of these keys will collide when hashed? approx. upperbound: 40000000 / 4294967296 = 0.009313226

of this number how many will potentially be added to the list. 0.009313226 / 3874 = 0.0000024040

1 in 415,967 approx. chance of collision. Assuming that the generation of avatar keys is truly random (which it isnt but close enough)

can lift this further if assume the potential addees is way less than 40 million. like 10,000,000 say. then

10000000 / 4294967296 / 3874 =  1 in 1,663,870

so pretty good odds i think

Link to comment
Share on other sites


irihapeti wrote:

i do again using wikipedia example. (is the same as i did before but this time i use their formula notation)

(n*n) / (2*m)

where n = 3874 and m = 4294967296

(3874 * 3874) / (2 * 4294967296)

15007876 / 8589934592 = 0.00174715

+

ok if is just 1 value in the list and add a 2nd one then n = 1

(1 * 1) / (2 * 4294967296)

1 / 8589934592 = 0.0000000001164153218

which is what you show

+

i think what caused me to be puzzled is that this formula approximates the probability of 2 or more identical values in [0..4294967295] randomly-drawn appearing in the sets [2] .. [3874]

which is not what we want to know. We want to know:

how many collisions will occur when reduce the set of all 128bit keys down to 32bit hashes?

in practice tho, there has been nearly 40 million avatar keys issued. The question then becomes: How many of these keys will collide when hashed? approx. upperbound: 40000000 / 4294967296 = 0.009313226

of this number how many will potentially be added to the list. 0.009313226 / 3874 = 0.0000024040

1 in 415,967 approx. chance of collision. Assuming that the generation of avatar keys is truly random (which it isnt but close enough)

can lift this further if assume the potential addees is way less than 40 million. like 10,000,000 say. then

10000000 / 4294967296 / 3874 =  1 in 1,663,870

so pretty good odds i think

Mmm, you've assumed the size of the set of 128 bit keys has some influence on this. It doesn't.

 

If one has 23 people in the same room, there is a 50% probability that two of them have the same birthday. And that would be true if there were only 23 people in the entire world or over 23 billion.

 

In other words, the only two factors to consider are the number of bins (365 in this case) and  how many you've dropped into them (23) but how big the bag is your pulling from has no bearing on the results. Unless, of course, it empties out at some point.

 

[ETA...]

It doesn't matter how the 32 bit hashes are arrived at, there are only 8,589,934,591 [Oops, I was off by a factor of two! LOL] 4,294,967,295 bins available. If you randomly placed nearly 4,000 objects (which is less than one millionth of the size of available bins, I'll point out) into those bins, one might assume the chances were "incredibly small" for two to occupy the same bin (collide). But the fact is, if you sold only 10,000 units relying on such, you'd most likely have around a dozen extremely irate customers. Not a very good approach to staying in business.

Link to comment
Share on other sites


LepreKhaun wrote:


 

[ETA...]

It doesn't matter how the 32 bit hashes are arrived at, there are only 
8,589,934,591
 [Oops, I was off by a factor of two! LOL]
4,294,967,295
 
bins available. If you randomly placed nearly 4,000 objects (which is
less than one millionth
of the size of available bins, I'll point out) into those bins, one might assume the chances were "incredibly small" for two to occupy the same bin (collide). But the fact is, if you sold only 10,000 units relying on such, you'd most likely have around a dozen extremely irate customers. Not a very good approach to staying in business.

we now moving on the same path so thats good

yes. was the 8,589,934,591? that threw me

1 / 0.0000000001164153218 = 1 in 8589934594. Is the probability this of collision of 2 numbers drawn randomly from 4294967296

+

is the xorhash algo that causes the collisions by pigeon hole. is of the form 128 % 32. Proof by counter example: stuffing unique numbers (128bit avatar keys) into a list will never cause a collision

need to factor this in when determining the collision probability in this case

Link to comment
Share on other sites

The algorithm used for hash making only contributes its entropy. In other words, the less random it is, the greater the chance of collision. Otherwise, it is just the two factors I mentioned earlier, the number of hash buckets available and the number of objects you're assigning to them.

 

My XOR algorithm is simply cramming 128 bits of information into a 32 bit space, there's other ways to do that but that's unimportant. Any and all hashing algorithms suffer from the Birthday Paradox- the point is the steepness of the curve at the lower end, the chances of a collision rises very rapidly at first as the number of objects are increased. The "gotcha!" is that smaller hash sizes allow more storage in the same space which ends up compounding the effect.

 

But this has gotten seriously off topic. Let's just leave it where hashes are not the way to go unless one has seriously studied the subject, know the risks involved and can make an informed decision on whether or not they're worth taking. As it is, there are much better approaches to the problem available to one in LSL, if simply because the original key cannot be recreated from its hash element (perhaps you'd like to IM all those avatar keys you have stored to date).

Link to comment
Share on other sites


irihapeti wrote:

can maybe get a little performance gain by picking direct from str. example

 
integer xorHash =    (integer)("0x" + llGetSubString(str, 0, 7)) ^    (integer)("0x" + llGetSubString(str, 8, 11) + llGetSubString(str, 12, 15)) ^    (integer)("0x" + llGetSubString(str, 16, 19) + llGetSubString(str, 20, 23)) ^   (integer)("0x" + llGetSubString(str, 24, -1));

 

havent tested it tho so only maybe

 

eta: sorry the offsets wrong. should be 9,12. 14,17. etc

Though that's certainly is "making a hash of it", I don't think that's quite what Sassy had in mind. :smileyvery-happy:

 

Seriously, this type of attempted optimization may be of benefit in tightening up a closed loop (such as a longish for() or while() construction) but when it comes to link messages, the message transport itself is the bottleneck. My experiments seem to point to a lower limit of 3 server frames (app. 0.066s) for an entire request & response sequence. Database manipulations in a shared use environment simply aren't going to be "time is of the essence".

 

Better to write concise, understandable and modular code and focus on memory footprint (the smaller the code size of your DBM, the more storage for data available).

Link to comment
Share on other sites

It's all about context and use case.

I want to detect avatars and maybe send them something later.  Whole UUID needed, I'd probably store those externally as they were detected.

I want to give a welcome notecard, venue rules etc. to visitors but ideally just once but if they don't get it at all or get it more than once, no issue. I can store hashed UUIDs

I am running a competition, the prize is L$1,000,000 per week but I only want guaranteed unique winners, I need the UUID.

Yes the thread digressed but illustrates other ways to address avatar keys without being fixated on the UUID.

Link to comment
Share on other sites


LepreKhaun wrote:

 

But this has gotten seriously off topic.

true (:

altho in my defense. it went off topic bc you put a probabilty number out there and I went hmm! dont think thats quite right

not in my defense tho is that I have history as a not very good train driver. Can derail anything me bc I am nosey (:

Link to comment
Share on other sites


LepreKhaun wrote:

irihapeti wrote:

can maybe get a little performance gain by picking direct from str. example

 
integer xorHash =    (integer)("0x" + llGetSubString(str, 0, 7)) ^    (integer)("0x" + llGetSubString(str, 8, 11) + llGetSubString(str, 12, 15)) ^    (integer)("0x" + llGetSubString(str, 16, 19) + llGetSubString(str, 20, 23)) ^   (integer)("0x" + llGetSubString(str, 24, -1));

 

havent tested it tho so only maybe

 

eta: sorry the offsets wrong. should be 9,12. 14,17. etc

Though that's certainly is "making a hash of it", I don't think that's quite what Sassy had in mind. :smileyvery-happy:

 

Seriously, this type of attempted optimization may be of benefit in tightening up a closed loop (such as a longish for() or while() construction) but when it comes to link messages, the message transport itself is the bottleneck. My experiments seem to point to a lower limit of 3 server frames (app. 0.066s) for an entire request & response sequence. Database manipulations in a shared use environment simply aren't going to be "time is of the essence".

 

Better to write concise, understandable and modular code and focus on memory footprint (the smaller the code size of your DBM, the more storage for data available).

can understand the wider point you making. just that like my train driving i have history in going brrmmm!!!

is not a biggie but I do again so not to make a hash of it this time. jejeje (:

is this code:

string str = (string)id;str = llDumpList2String(llParseStringKeepNulls((str = "") + str, ["-"], []), ""); integer xorHash=(integer)("0x" + llGetSubString(str, 0, 7)) ^    (integer)("0x" + llGetSubString(str, 8, 15)) ^    (integer)("0x" + llGetSubString(str, 16, 23)) ^   (integer)("0x" + llGetSubString(str, 24, -1));

 

is opt code

 

string str = (string)id;integer xorHash =    (integer)("0x" + llGetSubString(str, 0, 7)) ^    (integer)("0x" + llGetSubString(str, 9, 12) + llGetSubString(str, 14, 17)) ^    (integer)("0x" + llGetSubString(str, 19, 22) + llGetSubString(str, 24, 27)) ^   (integer)("0x" + llGetSubString(str, 28, -1));

 

+

i also just say that both versions of your key DB solution are pretty good. Lots of people will find good use for them. So thats good

Link to comment
Share on other sites

With danger to confuse the issue I like to point out that using Username over Userkey should take less room in most cases
Converted to a string the Username takes max 63 chars but much less in most cases, the Userkey takes 32 characters, when dashes are removed, always

  • The Username is unique for all agents in SL like the Userkey
  • The Username is not as convenient as the Userkey if you have to address agents not in the same region
  • The Username is just as suited as the key to identify agents in the same region
  • Hashed keys has been discussed much
    Hashed keys can not be used to recreate neither the full key nor the Username

It is hard to say how many unique Usernames can be stored in world in one script because of the dynamic size
My guess is twice the number of unique Userkeys, say 1400

:smileysurprised::):smileyvery-happy:

  • Like 1
Link to comment
Share on other sites


Dora Gustafson wrote:

With
danger
to
confuse the issue

seeing as how you taken over driving the train and I am only the passenger now then (:

can encode the keys into 18 bytes loselessly. so no collisions. (18bytes = 9 UTF16 chars. which is 2 more than native key of 16bytes)

as a guesstimate then if 64byte (32 UTF16 chars) strings = 700 approx. capacity. then about 3x something

 

Link to comment
Share on other sites


irihapeti wrote:


Dora Gustafson wrote:

With
danger
to
confuse the issue

seeing as how you taken over driving the train and I am only the passenger now then (:

can encode the keys into 18 bytes loselessly. so no collisions. (18bytes = 9 UTF16 chars. which is 2 more than native key of 16bytes)

as a guesstimate then if 64byte (32 UTF16 chars) strings = 700 approx. capacity. then about 3x something

 

Unsure what place a "guesstimate" has within LSL.

 

The code is already written, just write your algorithm in place of mine and see what results. I, for one, would be very interested to hear the results.

Link to comment
Share on other sites

according to the wiki entry you linked to below then  (in MONO) a 9-char UTF16 string consumes 36 bytes when stored in a list (any length string carries fixed overhead of 18 bytes apparently) . a key as string consumes 90. So 2.5x not 3x

by equivalence for the approximation (guesstimate) then 700 x 2.5 = 1,750

Link to comment
Share on other sites


irihapeti wrote:

according to the wiki entry you linked to below then  (in MONO) a 9-char UTF16 string consumes 36 bytes when stored in a list (any length string carries fixed overhead of 18 bytes apparently) . a key as string consumes 90. So 2.5x not 3x

by equivalence for the approximation (guesstimate) then 700 x 2.5 = 1,750

The only way I know for you to verify your guess is to spend a few minutes coding your approach.

Link to comment
Share on other sites

1642 keys for 65520 memory

+/- however much bytecode the script uses more/less this than this gen script

 

default{    touch_end(integer total_number)    {        integer k = 1642;                        list lst;        string s;         integer i;         integer j;        integer n;        for (i = 0; i < k; i++)        {           for (j = 0; j < 9; j++)           {                           n = (integer)llFrand(0x8000);               s += llBase64ToString(llIntegerToBase64(                   0xE0808000 | (((n + 0x800) << 12) & 0xF000000) |                    (((n + 0x800) << 10) & 0x3F0000) | ((n << 8) & 0x3F00)));            }            lst += [s];            s = "";        }        llOwnerSay((string)llGetUsedMemory());    }}

 

+

a example key encoder/decoder can be found down in this chat for anybody who might want to play with such a thing

http://www.sluniverse.com/php/vb/scripting/93810-quotation-marks-strings.html

is public domain so can do whatever you want with it as you like

+

edit: i just correct the range in the gen script to be the same as the encoder script. it bump it up to a little bit to 1692 bc the range i had was overflowing on some randoms injecting extra spurious chars into the stream

1692 is right on the edge so in production codes then should have a way big margin for safety bc the memory allocation for LSL MONO is pretty unreliable seems like

 

  • Like 1
Link to comment
Share on other sites


irihapeti wrote:

1642 keys for 65520 memory

+/- however much bytecode the script uses more/less this than this gen script

 
default{    touch_end(integer total_number)    {        integer k = 1642;                        list lst;        string s;         integer i;         integer j;        integer n;        for (i = 0; i < k; i++)        {           for (j = 0; j < 9; j++)           {                           n = (integer)llFrand(0x8000);               s += llBase64ToString(llIntegerToBase64(                   0xE0808000 | (((n + 0x800) << 12) & 0xF000000) |                    (((n + 0x800) << 10) & 0x3F0000) | ((n << 8) & 0x3F00)));            }            lst += [s];            s = "";        }        llOwnerSay((string)llGetUsedMemory());    }}

 

+

a example key encoder/decoder can be found down in this chat for anybody who might want to play with such a thing

is public domain so can do whatever you want with it as you like

+

edit: i just correct the range in the gen script to be the same as the encoder script. it bump it up to a little bit to 1692 bc the range i had was overflowing on some randoms injecting extra spurious chars into the stream

1692 is right on the edge so in production codes then should have a way big margin for safety bc the memory allocation for LSL MONO is pretty unreliable seems like

 

Very nice try but you're not working with a single key anywhere in your code, you're just storing 9 integers away in a string. You need the entire suite of subroutines as elizabeth wrote them to handle keys and Jopsy summed up the consequences of this approach quite well imo.

 

And keep in mind that our programs carry memory overhead of it's own, one never has 64K of data storage.

default{    state_entry()    {        llOwnerSay((string)llGetUsedMemory());    }}

 

Link to comment
Share on other sites


LepreKhaun wrote:

irihapeti wrote:

1642 keys for 65520 memory

+/- however much bytecode the script uses more/less this than this gen script

 
default{    touch_end(integer total_number)    {        integer k = 1642;                        list lst;        string s;         integer i;         integer j;        integer n;        for (i = 0; i < k; i++)        {           for (j = 0; j < 9; j++)           {                           n = (integer)llFrand(0x8000);               s += llBase64ToString(llIntegerToBase64(                   0xE0808000 | (((n + 0x800) << 12) & 0xF000000) |                    (((n + 0x800) << 10) & 0x3F0000) | ((n << 8) & 0x3F00)));            }            lst += [s];            s = "";        }        llOwnerSay((string)llGetUsedMemory());    }}

 

+

a example key encoder/decoder can be found down in this chat for anybody who might want to play with such a thing

is public domain so can do whatever you want with it as you like

+

edit: i just correct the range in the gen script to be the same as the encoder script. it bump it up to a little bit to 1692 bc the range i had was overflowing on some randoms injecting extra spurious chars into the stream

1692 is right on the edge so in production codes then should have a way big margin for safety bc the memory allocation for LSL MONO is pretty unreliable seems like

 

Very nice try but you're not working with a single key anywhere in your code, you're just storing 9 integers away in a string. You need the entire suite of subroutines as 
 to handle keys and 
 of this approach quite well imo.

 

And keep in mind that our programs carry memory overhead of it's own, one never has 64K of data storage.
default{    state_entry()    {        llOwnerSay((string)llGetUsedMemory());    }}

 

+/- for bytecode yes. i did mention that in the line above the codes yes ?

+

for people who might end up reading this

the encoder/decoder linked to was designed to help with answering the questions

- how to encode a key losslessly into a smaller space?

- how to store encoded keys in logical groupings so that they can be extracted and decoded without loss

- how can the storage method be implemented so is transportable to other storage medium?

use cases other than OP wanting to transport to scripts and notecards (storage medium) is when transporting to a external website, packing into containers, etc.

it only came into this thread when the discussion turn to what other formats can be used to store unique identifiers losslessly in this DB solution

the discussion in this subthread is now about formats. Is not about the design of the DB solution itself. Which as I already said is pretty good. The lossy hash version is also pretty good when the probability loss margin is acceptable for your use case

+

anyone reading the link discussion can see that I actual agree with Jopsy and suggest an alternative coding approach to the problem confronting OP

the problem being that OP was trying to jam everything into fewer scripts than the app requirements metrics actual allow. Which OP came to realise themself. So all good

+

i just make another observation about optimisation in the xorhash version for the readers. bc I am a modder (:

if mod/move the hashing algo to the harness side then can pass to DB as integer. Can get a performance gain doing this, and can reduce further the bytecode size of the DB script by some amount. Is a transfer coding technique this. Transfer the bytecode space consumed to another memory block of the app where the space constraints are more relaxed.

if also think about this a bit then can see how I would deal with the encoder bytesize issue in any mod I might do

in a particular use case it may also be useful to know on the harness side what is the hash of a key for some other purpose. So if modding Leprekhaun's lossy DB solution for own purpose/use case then can think about this as well

+

in the general case then is not a biggie to not do the kind of opt/mod that I been chatting about

!!! and.... important !!!

opt/mod can obscure the purpose/intent of a general library solution. The purpose/intent of library is to provide a solution for the general case that can be easy used by others as is within its own bounds, and can be easy modded for specific use cases where those bounds need to be pushed/extended

so take what I am chatting about with this in mind ok. me modder

Link to comment
Share on other sites


irihapeti wrote:

.. [previous quotes snipped]...

+/- for bytecode yes. i did mention that in the line above the codes yes ?

+

for people who might end up reading this

the encoder/decoder linked to was designed to help with answering the questions

- how to encode a key losslessly into a smaller space?

- how to store encoded keys in logical groupings so that they can be extracted and decoded without loss

- how can the storage method be implemented so is transportable to other storage medium?

use cases other than OP wanting to transport to scripts and notecards (storage medium) is when transporting to a external website, packing into containers, etc.

it only came into this thread when the discussion turn to what other formats can be used to store unique identifiers losslessly in this DB solution

the discussion in this subthread is now about formats. Is not about the design of the DB solution itself. Which as I already said is pretty good. The lossy hash version is also pretty good when the probability loss margin is acceptable for your use case

+

anyone reading the link discussion can see that I actual agree with Jopsy and suggest an alternative coding approach to the problem confronting OP

the problem being that OP was trying to jam everything into fewer scripts than the app requirements metrics actual allow. Which OP came to realise themself. So all good

+

i just make another observation about optimisation in the xorhash version for the readers. bc I am a modder (:

if mod/move the hashing algo to the harness side then can pass to DB as integer. Can get a performance gain doing this, and can reduce further the bytecode size of the DB script by some amount. Is a transfer coding technique this. Transfer the bytecode space consumed to another memory block of the app where the space constraints are more relaxed.

if also think about this a bit then can see how I would deal with the encoder bytesize issue in any mod I might do

in a particular use case it may also be useful to know on the harness side what is the hash of a key for some other purpose. So if modding Leprekhaun's lossy DB solution for own purpose/use case then can think about this as well

+

in the general case then is not a biggie to not do the kind of opt/mod that I been chatting about

!!! and.... important !!!

opt/mod can obscure the purpose/intent of a general library solution. The purpose/intent of library is to provide a solution for the general case that can be easy used by others as is within its own bounds, and can be easy modded for specific use cases where those bounds need to be pushed/extended

so take what I am chatting about with this in mind ok. me modder

 

No need to get so defensive here. If you're going to make comparisons, you're required to do so in a way that apples are still apples is all.

 

As it turns out, your suggestion is an improvement of 2x.

// "Store 700+ Unique UUIDs In World" by LepreKhaun 4/18/2014// Modified 4/27/2014 using the suggestion of// irihapeti to use a complex compression algorithm// as written by elizabeth in http://www.sluniverse.com/php/vb/scripting/93810-quotation-marks-strings.html#post1928288//// This version will store *** 1,487 *** keys//// See http://community.secondlife.com/t5/LSL-Library/Store-700-Unique-UUIDs-In-World/td-p/2669408 for usage// May be freely used, modified and distributed ONLY with this header intact!//// BEGIN example key encoder decoder// public domain April 2014 by elizabeth (irihapeti)// a mod of works by:// Adam Wozniak, Doran Zemlja, Becky Pippen, Strife Onizuka// with mentions for exacts in the codes//// encodes a key (uuid) into a string of 9 UTF16 chars. 18 bytes// str = Key2UTF(key) // key = UTF2Key(str) //// UTF16 codes produced are copypasta into scripts and notecards in // SL viewer 3.7.3 (287491) Mar 4 2014 05:01:31// on Windows 8.1. Default USA english// dunno about earlier/later versions, LSL Editor or TPVs or other OS// just need be careful when copypasta as// - some UTF glyphs are not visible but are in the string// - many of them show as the same glyph. but they are decodeable// so best to Say wrapped in "" for copypasta purposes //// warninkkks !!! is no error trapping !!! if you need that then mod  // -- encoder ---integer enB; string enU(integer n){   // credit: Strife    return llBase64ToString(llIntegerToBase64(        0xE0808000 | (((n + 0x800) << 12) & 0xF000000) |         (((n + 0x800) << 10) & 0x3F0000) | ((n << 8) & 0x3F00)));}   string enP(integer n){       enB = (enB << 2) | (n & 0x3);    return enU((n >> 2) & 0x7FFF) + enU((n >> 17) & 0x7FFF); }   string Key2UTF(key k){       string s = (string)k;    string r =        enP((integer)("0x" + llGetSubString(s, 28, 35))) +       enP((integer)("0x" + llGetSubString(s, 19, 22) + llGetSubString(s, 24, 27))) +       enP((integer)("0x" + llGetSubString(s,  9, 12) + llGetSubString(s, 14, 17))) +       enP((integer)("0x" + llGetSubString(s,  0,  7)));    return r + enU(enB & 0xFF);}// --- end encoder ---   // --- decoder ---integer deB;list deH = ["0","1","2","3","4","5","6","7","8","9","a","b","c","d","e","f"];   integer deU(string s){   // credit: Becky     s = llEscapeURL(s);    return        ((((integer)("0x" + llGetSubString(s, 1, 2)) & 0x1F) << 12) |         (((integer)("0x" + llGetSubString(s, 4, 5)) & 0x3F) << 6) |          ((integer)("0x" + llGetSubString(s, 7, 8)) & 0x3F)) - 0x800;}    string deP(string s){    integer n = (deU(llGetSubString(s, 1, 1)) << 17) |                (deU(llGetSubString(s, 0, 0)) << 2) | (deB & 0x3);    deB = deB >> 2;    return          llList2String(deH, (n >> 28) & 0xF) + llList2String(deH, (n >> 24) & 0xF) +        llList2String(deH, (n >> 20) & 0xF) + llList2String(deH, (n >> 16) & 0xF) +        llList2String(deH, (n >> 12) & 0xF) + llList2String(deH, (n >>  8) & 0xF) +        llList2String(deH, (n >>  4) & 0xF) + llList2String(deH, n & 0xF);}     key UTF2Key(string s){      deB = deU(llGetSubString(s, 8, 8));    return (key)(        deP(llGetSubString(s, 6, 7)) + "-" +        llInsertString(deP(llGetSubString(s, 4, 5)), 4, "-") + "-" +        llInsertString(deP(llGetSubString(s, 2, 3)), 4, "-") +        deP(llGetSubString(s, 0, 1)));}// --- end decoder --- list keysStored;default{    link_message(integer sender_num, integer num, string str, key id)    {        if (~num) // abort unless num != -1            return;                    string elizabethCode = Key2UTF(id);                // see if the key is in list        if(~llListFindList(keysStored, [elizabethCode]))        {            // it was found            llMessageLinked(LINK_THIS, TRUE, "", id);        } else {            // it was not found, so            // store it first            keysStored += [elizabethCode];            llMessageLinked(LINK_THIS, FALSE, "", id);        }    }}

 

  • Like 1
Link to comment
Share on other sites

You are about to reply to a thread that has been inactive for 3600 days.

Please take a moment to consider if this thread is worth bumping.

Please sign in to comment

You will be able to leave a comment after signing in



Sign In Now
 Share

×
×
  • Create New...