Passing a key via on_rez (concept)

would it be possible to translate a key into binary, and then pass the binary code as an integer along the on_rez parameters, and then decode the binary "integer" into a key again for use with an object? the main limitation being the number of decimal places in acurracy that an integer can hold with floating point. I have no idea what binary standard notation is for alphanumeric in computers as I have only dealt with base "x" systems from a purely mathematical standpoint, but if a key could be coded into binary (or some other base(x) system), I think it would lessen a lot of the server loads on scripts that rez objects and then listen for a channel to pass keys along.

without getting into key speculation and binary mathmatics the simple awnser is yes, but ...

using my key as an example i have numbers that range from 0-f (16 total)
a set of 8, 4, 4 ,4,12 not counting the dashes

first second and 3rd value 01000 01111 01101 and so on
and thats just 8ed the start of my key.

http://www.helpwithpcs.com/courses/binary-numbers.htm#decimal-to-binary-conversion

Not in an integer. A key is 32 hexadecimal characters (if you leave out the dashes), so thats 32 * 16 bits needed, which is more bits than an integer has. Someone posted a script recently that used a smaller string to store the key with some pretty clever bit shifting. But it still won't fit into a single integer. I don't think so, anyway.

Hmm... maybe with run-length encoding, or something like that? But even that's not deterministic, so there's no guarantee the encoded data will fit in an integer.

maby a 32 bit fudge, fit 2 values in 1 i dunno its getting late lol

0-9,a-v =32 total
0-f = 16
g-v = 16

{some decoder code}

What Kala said - even dropping out the non-alphanumeric characters that's still seven bits per character, and while you might be able to do some compression, an integer is only 32 bits.

Since keys are a string of 32 hex characters (0-F) it would be possible to convert the key into a 16-character string... (hex = 4 bytes, character = 8 bytes).

This would leave you with 16 bytes rather than 32, half the size of the original key.

But after compressing it to this state... getting it to shrink further is a chore.

I'm still working on this... It is ungodly hard.

If someone could figure out how to script a nice lossless compression algorythm to convert a 16-byte string into a 4-byte string, implemented in LSL... This would be possible.

Research!

~G

Yumi Murakami came up with some key crunching/uncrunching functions that were pretty clever.

/54/5f/72011/1.html

You can't do the 8 bits per character thing, because LSL doesn't really give you access to the full 256 ASCII characters, and there's no C-like means to convert integers to characters and then build up a character string with that. Yumi's idea is the next best thing - use the printable characters, which gets you to 6 bits instead of 8, and then do some clever bit shifting to compact the key string down.

I've been trying to get it smaller, but haven't managed to yet.. one thing I did find is that the crunched key strings from those functions have a spare 4 bits at the end, so if you want to put an extra value from 0-16 in there too you can. If you don't mind it messing up attempts to match the key in future.. which I usually did..

Oddly I found that encoding the key as a list of 4 integers took MUCH more memory than the string. Which ironically means that, presumably, encoding lists of integers in general as strings would ALSO save memory...(!?)

So because SL doesn't support all 256, we can reduce it to printable characters... And thus reduce the size of the variable necessary to store said character. This allows for further compression of the string, and adding 4 extra bytes to the end.

This could help a bit!

First, we can use compression of some kind to shrink them even more, and we've got an extra 4 bytes for use in something else....... maybe a hash for unlocking/uncompressing?

I need to find a good compression algorythm.





So now we've got 12 bytes instead of 16 bytes... this means that we only have to compress it to 1/3 of its size instead of 1/4. Much more manageable... but still difficult.

hmm......


Also we have to make sure that we can do the entire process backwards, so that we can get the original key when we're done.

the only problem i see with the 6-bit thing is this:

each hex character represents 4 bits

two hex characters represent 8 bits

if you remove 2 bits, you lose the hex.

I don't see a way to store all potential hex pairs (00-FF) in a 6-bit variable.

Look through the script. It's not a 2-to-1 mapping, it shifts bits around and encodes it 6 bits at a time. It takes some time to understand how that script works

I'm thinking maybe huffman compression...

Now, this would be a cheap hack, and I don't know how well it would compress the 16 byte string, but it's something that's possible. It also wouldn't be very memory-efficient... But like I said, it's a quick hack.

1. Take the key
2. Half it's size (combine each hex pair to make a 1-byte integer)
3. Add each integer to a list, which will contain all 16 integers
4. Add each integer in the list to a string by converting it from its integer form to its huffman key (e.g. 0 would be "0" 1 would be "100" 2 would be "101" 3 would be "110" 4 would be "111" etc.)
5. convert the resulting binary data into an integer.
6. pray that the resulting binary data actually fits into 4 bytes.

#2 would actually be storing the combined pair in an integer data type, rather than in a character.

The problem with this is that if you use a static keyset (rather than dynamic, based on the actual characters involved) then there's the chance that the string will not be compressed at all.

However, if we can find a way to transmit the resulting characters (after combining hex keys) to the new prim, we could have it create the tree dynamically and thus have a constant size for compression.

The problem with THIS idea is that you're no longer transmitting all data via the start_params integer. You are now basically just transmitting a shrunk key via start_params, and then transmitting a decompression key via llSay or whatever.

So...... if you feel like transmitting keys without people knowing you're transmitting keys this could work. But.... I don't see another method yet.

I'll look closer at the script... but all 6 bits does is shrink it from 16 bytes to 12 bytes.

We still gotta reduce it.

Huffman compression works if the values being compressed have a substantially non-uniform distribution.

The 128 bits (at 4 bits per character) of the key are effectively random numbers.

Any compression scheme will only make the average size larger.

The bottom line is that a key contains 128 bits of real data. You can't leave any of those 128 bits behind and be able to reconstruct the key.

0123abcd <- 32-bit integer, 4 bytes, 8 nybbles, represented as 8 hex digits.

66864f3c-e095-d9c8-058d-d6575e6ed1b8 <- 128-bit integer, 16 bytes, 32 nybbles, represented by 32 hex digits and 4 dashes.

You can't fit the second into the first. No how. No way. There is no compression scheme or other trick that will do it.

It's encoding 8-bit values into 6-bit values. That would give you a 24-byte string after you removed the useless dashes. The problem is that even if you DID compress all the way down to the irreducable 4 bits of actual data per character you're still left with 128 bits of incompressible information that you can't fit into a 32-bit word.

Agreed. I was trying to explain that the script wouldn't lose the last 2 bits of every hex digit like Ghordon was afraid it would. At least, that's what I thought Ghordon was saying, and that's what I think I tried to say in response

Okay...

So.

I did some math...

Let me show you something.

66864f3c-e095-d9c8-058d-d6575e6ed1b8

take out the dashes, show it in a more friendly manner:

66 86 4f 3c e0 95 d9 c8 05 8d d6 57 5e 6e d1 b8

now convert hex pairs to single bytes (represented by integers)

102 134 79 60 224 149 217 200 5 141 214 87 94 110 209 184

now we've got 16 bytes of data, half of what we originally had.

take these, see if we've got any repeat values (unlikely...)

put them through huffman compression:

102 = 0
134 = 100
79 = 101
60 = 1111
224 = 11000
149 = 11001
217 = 11010
200 = 11011
5 = 1110000
141 = 1110001
214 = 1110010
87 = 1110011
94 = 1110100
110 = 1110101
209 = 1110110
184 = 1110111

line the binary up (split into bytes):

01001011
11111000
11001110
10110111
11000011
10001111
00101110
01111101
00111010
11110110
1110111x

(the x is an extra bit that's unused)

this results in eleven bytes rather than 16. (i'm not even sure if I used the highest possible compression of this method...

anywho.... I know that huffman compresses the data into a smaller chunk than it originally was.

These eleven bytes are less than half of what the original key size was.

we've still not reached that magic number 4 yet...

but if we combine yumi's script with huffman we might get even closer.

of course, i'm not really sure about how practical this is.

I know for a fact we can write scripts to compress the key to at least 10 bytes rather than 32, but shrinking 10 bytes to four and being able to undo all the changes.... that's going to be a lot more difficult.

Of course, that is assuming that you later pass information to the child prim in some other way.... in which case you might as well just tell it the key.

If you're trying to make a script that gets a key to sense once it's rezzed... you might try this:

compress and compress (or make a hash of) the key until you get it to 4 bytes.

send that via on_rez().

have the rezzed prim scan the area and find all keys, then use the same compression/hash function on each.

when it finds a match, that's the most likely cantidate for the person you were trying to referr to it.




This will help, for instance, if you're trying to create a gun that senses a specific target then creates a bullet that auto-seeks that target.

However it won't be possible to run the script backwards to find the original key... it'll just have to hope that only one key matches that hash.

That was what I was afraid of, and I understand that they won't be lost now.

However, I still don't see it getting compressed (reversably) to 4 bytes.

You'll be able to compress some strings to the right length. But given that keys are pretty much random, you won't be able to guarantee that.

There's a basic information space here that can't be compressed. I wish I could remember more of my information theory now, and that I'd payed more attention instead of going out drinking with dubious types who taught me how to smoke.

I don't think you can apply the same compression algorithm repeatedly and always get something that is smaller than the step before. If that were possible, Winzip would reduce every file down to 1 byte.



I don't know enough math to be able to prove whether 128 bits of data can or cannot be stored in 32 bits. But if it cannot, then there is no way to do this. It is easy to come up with examples where it will work - a key of all 0s or all 1s can be stored in 1 byte. But for a generic random key, I don't know if this is doable or not, and I don't have the math skills to prove it one way or the other.

Of course.

If we happened to get NULL_KEY (all zeroes) we could compress it directly to 2 bytes in size.

Same for 010101010101010101010101... and 02020202020202... etc.

if we had 001100110011 etc. we could compress to 2 bytes.

but anything with more variation than three or four specific hex pairs (in this case, 00 and 11) could result in more than 4 bytes...




For example:

key 00000000-0000-0000-0000-000000000000 (NULL_KEY) can be reduced (by hex pairs 00) into the following 16 bytes: 0000000000000000. Now, since each of those bytes are the same, you get one bit to represent all of them, and suddenly you've got: 00000000 00000000 (two bytes).

However:

the key 00111100-0011-0000-1111-000011001111 would reduce (hex pair) to:

0 17 17 0 0 17 0 0 17 17 0 0 1 0 17 17

assign the following bits:

0 - 0
17 - 1

and it becomes:

01100100 11001011 (two bytes)


now....

00112200-1100-2222-221100221100

reduced to integers:

0 17 32 0 17 0 32 32 32 17 0 32 17 0

0 - 5 occurrences
17 - 4 occurrences
32 - 5 occurrences

give them huffman bits:

0 - 0
32 - 10
17 - 11

then you get:

01110011 01010101 1010110 (just under 3 bytes....)


anything with 4+ pairs could potentially result in more than 4 bytes...

true.... it has to be reversable. one byte cannnot be made into an entire Metallica album. this is why winzip eventually gets to the point where it can't compress itself anymore.

That, and if it's a dynamic huffman encryption, it has to store the key as well.... thus it will always be at least 256 bytes in size, because there are 256 possible characters in one byte.

however, if you apply the huffman algorithm over and over to itself, you will eventually end up with one byte: 0



when i spoke of a hash, i was talking about a one-way hash. It's something that isn't intended to be decrypted or uncompressed. there's no way to get the original value from just the hash.