Random High Density Strings in Javascript

Question

I am currently generating UUIDs in Javascript using this function ( Create GUID / UUID in JavaScript? ):

lucid.uuid = function() { return 'xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'.replace(/[xy]/g, function(c) { var r = Math.random()*16|0, v = c == 'x' ? r : (r&0x3|0x8); return v.toString(16); }); } 

I understand that all randomness comes only from the Javascript Math.random () function, and I don't care if it matches the RFC for the UUID. I want to pack as much randomness as possible into a few bytes in a Javascript string. The above function gives about 128 bits of randomness. How small is the line (measured in UTF8 bytes sent over the wire in HTTP POST), can I insert 128 bits in Javascript? And how would I generate such a string?

Edit: this string will be part of the JSON object when sent to the server, so the characters that need to be escaped in the string are not very useful.

Answer 1

Here is one potential feature I came across. The source string is a set of unreserved URLs (66 of them). I have a prefix of randomness with 1-year timestamp data with 1-second resolution, which is useful since the conflict space for my particular application fills rather slowly over time (only on MOST several hundred of them are generated per second as a last resort).

 uuidDense = function() { var seed = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789-_.~'; //Start the UUID with 4 digits of seed from the current date/time in seconds //(which is almost a year worth of second data). var seconds = Math.floor((new Date().getTime())/1000); var ret = seed[seconds % seed.length]; ret += seed[Math.floor(seconds/=seed.length) % seed.length]; ret += seed[Math.floor(seconds/=seed.length) % seed.length]; ret += seed[Math.floor(seconds/=seed.length) % seed.length]; for(var i = 0; i < 8; i++) ret += seed[Math.random()*seed.length|0]; return ret; } 

Thoughts?

Answer 2

128 bit = 16 bytes → base64 → 16 * 3/2 = will give you a string of 24 characters (versus 36 characters you have)

You can also use base85 for a better density, but this will require URL encoding so you can get even worse results than yours.

Answer 3

Your question is somewhat controversial. Javascript strings use UCS-2 (fixed 16-bit characters) to represent them internally. However, UTF-8 is a variable width, but for encoding purposes, I believe that the most compact form will be to use 1-byte UTF8 characters, which only require the most significant bit, equal to zero. That is, you can pack 128 bits into 128 * 8/7 = 147 bits.

Converting to bytes and rounding, you can do this in 19 characters.