UUIDGEN in lisp

UUIDGEN in lisp

[Brad Collins]

As part of a major mode I'm writing, I call uuidgen to automatically
insert a UUID in document metadata.  This is fine when I'm on a *nix
box, but becomes a real pain when using a Windows box.  I've had no
luck getting rsh working between my windows and linux box.

There is no cygwin version of uuidgen (that I can find) and there is a
uuidgen.exe made by MS but it's only bundled in some other large
package.

So I was wondering if anyone knows of a lisp UUID generator that has
already been written.  I've found a couple of unique ID generators in
gnus and message but I don't know if these are producing proper uuids.

I think it would be generally helpful to have a generic unique id
generator for a number available for any application but I'm not sure
if this has already been done or not.

Any ideas?

b/

--
Brad Collins
Chenla Labs
Bangkok, Thailand

Re: UUIDGEN in lisp

[Jesper Harder]

Brad Collins <brad@studiojungle.net> writes:

> I think it would be generally helpful to have a generic unique id
> generator for a number available for any application but I'm not
> sure if this has already been done or not.
>
> Any ideas?

Concat some strings that should identify the user -- uid, pid,
system-name etc. -- plus some random stuff, and take a hash?

Something like:

(md5 (format "%s%s%s%s%s%s%s%s" 
	     (user-uid)
	     (emacs-pid)
	     (system-name)
	     (user-full-name)
	     user-mail-address
	     (current-time)
	     (random)
	     (recent-keys)))

Re: UUIDGEN in lisp

[Brad Collins]

I didn't know about the MD5 function in Emacs!  Wow...

But I really do need to use a proper UUID.

I've been trying to see how it's been done by others but it's not easy
stuff.  I still don't understand about high and low parts of a time
stamp and how to convert them.. The Perl module Data::UUID seems very
complete and seems to use MD5 to create hashes of the different parts
of the time stamp to create the four parts of the UUID but I'm still
not getting it....

b/


--
Brad Collins
Chenla Labs
http://www.chenla.org/
Bangkok, Thailand

Re: UUIDGEN in lisp

[Kai Grossjohann]

Brad Collins <brad@studiojungle.net> writes:

> As part of a major mode I'm writing, I call uuidgen to automatically
> insert a UUID in document metadata.  This is fine when I'm on a *nix
> box, but becomes a real pain when using a Windows box.  I've had no
> luck getting rsh working between my windows and linux box.

Off-topic reply: maybe it works to set up ssh on your linux box and to
use PuTTY and WinSCP to access that from your windows box.

Kai

Re: UUIDGEN in lisp

[Jesper Harder]

Brad Collins <brad@studiojungle.net> writes:

> But I really do need to use a proper UUID.
>
> I've been trying to see how it's been done by others but it's not
> easy stuff.  I still don't understand about high and low parts of a
> time stamp and how to convert them..

Well, the time-based UUID is annoying to generate -- it requires
system-wide storage of a seed.  I don't see how you can guarantee
that your generator will use the same storage as, say, the Perl
generator and whatever else might generate UUIDs on ms-windows.

This type of UUID also leaks your MAC address.

Random-based UUIDs are much nicer.  Below is an implementation.  It
uses /dev/urandom as a source of high quality random bits on
GNU/Linux, but I don't know if the built-in `random' in Emacs used on
other systems qualifies as a "cryptographic strength random number
generator".

(defun uuid ()
  "Generate a version 4 UUID."
  (let ((bytes (uuid-random)))
    (setf (nth 7 bytes)
	  (logior #B01000000 (logand #B01111111 (nth 7 bytes))))
    (setf (nth 8 bytes)
	  (logior #B01000000 (logand #B01001111 (nth 8 bytes))))
    (apply 'format
	   "%02x%02x%02x%02x-%02x%02x-%02x%02x-%02x%02x-%02x%02x%02x%02x%02x%02x"
	   bytes)))

(defun uuid-random ()
  "Return a list of 16 random bytes."
  (if (file-readable-p "/dev/urandom")
      (let (((coding-system-for-read 'binary)))
	(mapcar 'identity
		(substring
		 (string-as-unibyte
		  (shell-command-to-string
		   "dd count=16 bs=1 < /dev/urandom"))
		 0 16)))
    (random t)
    (mapcar 'random (make-list 16 255))))

Re: UUIDGEN in lisp

[Felix]

>>>>> "Kai" == Kai Grossjohann <kai@emptydomain.de> writes:

    Kai> Brad Collins <brad@studiojungle.net> writes:
    >> As part of a major mode I'm writing, I call uuidgen to automatically
    >> insert a UUID in document metadata.  This is fine when I'm on a *nix
    >> box, but becomes a real pain when using a Windows box.  I've had no
    >> luck getting rsh working between my windows and linux box.

    Kai> Off-topic reply: maybe it works to set up ssh on your linux box and
    Kai> to use PuTTY and WinSCP to access that from your windows box.

    Kai> Kai

windows has the console uuidgen.exe too which comes with the free ms
platform sdk.

-- 
Felix

Re: UUIDGEN in lisp

[Brad Collins]

Fantastic!  Thanks Jesper!

I never could have come up with anything like this on my own.  This
is perfect for my present needs.  I'll include a customization
item to let people switch to another external UUID generator.

I'll be studying this to learn how it works over the next few days but
as far as I can tell, I can drop this into into the mode as is.

The major mode I'm working on will be GPL'd, is it okay to include
this code in the mode?

I'm aware of uuidgen.exe but I don't have the MS SDK or the money to
buy it (or even the money to go to Panthip plaza on the other side of
Bangkok and buy a pirate copy for that matter -- thought the taxi
would cost more than the software).  I'm in _very_ lean startup mode
at the moment :)

b/

Re: UUIDGEN in lisp

[Brad Collins]

Interesting to see that if you call the script twice in less than a
second you get a duplicate id....  not sure why, but it means that one
should take care it in scripts....

b/

Re: UUIDGEN in lisp

[Jesper Harder]

Brad Collins <brad@studiojungle.net> writes:

> The major mode I'm working on will be GPL'd, is it okay to include
> this code in the mode?

Sure.

> Interesting to see that if you call the script twice in less than a
> second you get a duplicate id....  not sure why, but it means that
> one should take care it in scripts....

Ah, yes.  It happens because of the `(random t)' in `uuid-random'.
It seeds the RNG, which is necessary because otherwise you'll always
get the same sequence of random number.

But Emacs uses the current time (plus pid) as the seed, so you'll get
the same numbers if you call it with intervals shorter than the time
resolution.  So you should remove the (random t) from the function:

(defun uuid-random ()
  "Return a list of 16 random bytes."
  (if (file-readable-p "/dev/urandom")
      (let ((coding-system-for-read 'binary))
	(mapcar 'identity
		(substring
		 (string-as-unibyte
		  (shell-command-to-string
		   "dd count=16 bs=1 < /dev/urandom"))
		 0 16)))
    (mapcar 'random (make-list 16 255))))

and just place it at the top-level (or in the function that starts
your mode).

Re: UUIDGEN in lisp

[Eli Zaretskii]

> Newsgroups: gnu.emacs.help
> From: Jesper Harder <harder@myrealbox.com>
> Date: Sun, 15 Feb 2004 21:47:44 +0100
> 
> (defun uuid-random ()
>   "Return a list of 16 random bytes."
>   (if (file-readable-p "/dev/urandom")
>       (let ((coding-system-for-read 'binary))
> 	(mapcar 'identity
> 		(substring
> 		 (string-as-unibyte
> 		  (shell-command-to-string
> 		   "dd count=16 bs=1 < /dev/urandom"))
> 		 0 16)))
>     (mapcar 'random (make-list 16 255))))

Jesper, can you explain why did you need all these monstrocities with
coding-system-for-read and string-as-unibyte?  Is there some real
problem behind this, or simply a bit of paranoia (no offense)?  What
am I missing?

Re: UUIDGEN in lisp

[Brad Collins]

Fantastic!  Just as you said, moving (random t) outside the function
allows you to generate as many as you please.  This is very helpful
for assigning ids to a large list of items at the same time.  I don't
know how many you can assign at the same time (the spec says 10
million a unique ids in a second per machine).  I wouldn't want to put
this little script to any test that big, but I would think it should
be okay for assigning a couple hundred or even a couple thousand items
at a time in a replace funcion....

Last question -- promise :)

I've looked this up in the elisp manual but don't really understand
what is going on.  I noticed in the original script that the third
field always would begin with the number four.  I started changing
things around and found if I changed the following,

    (logior #B01000000 (logand #B11111111 (nth 7 bytes))))
                                ^^^^^^

the numbers would be begin looking random again.  What does `logior'
and `logand' actually do in the script and what does the string
#B01000000 mean?  And how should they be set in this script?  The
manual completely lost me.

Sorry to keep bugging you like this but I like to understand how
things work....

BTW I've been Googling to see how good /dev/random and /dev/urandom
are on cygwin.  A number of people seem to have asked the same
question and it sounds like it's good enough for most purposes....

Thanks,

b/

--
Brad Collins
Chenla Labs
www.chenla.org
Bangkok, Thailand

Re: UUIDGEN in lisp

[Jesper Harder]

"Eli Zaretskii" <eliz@elta.co.il> writes:

> Jesper, can you explain why did you need all these monstrocities
> with coding-system-for-read

Binding coding-system-for-read is definitely necessary.  I'm reading
random bytes, and I don't want Emacs to convert any of the values.  If
I don't bind it, `uuid-random' can return a list like:

(159 92 2210 119 150 148 2275 2265 2290 2220 2240 62 84 2235 150 18)

which is wrong, since it's not a list of bytes.

> and string-as-unibyte?  

string-as-unibyte is probably unnecessary.

> Is there some real problem behind this, or simply a bit of paranoia
> (no offense)?  What am I missing?

Uhm, I don't think there's anything strange about having to bind
coding-system-for-read to binary -- I _am_ reading binary data, after
all.

Re: UUIDGEN in lisp

[Jesper Harder]

Brad Collins <brad@studiojungle.net> writes:

> I've looked this up in the elisp manual but don't really understand
> what is going on.  I noticed in the original script that the third
> field always would begin with the number four.

Yes,  it should be 4.  A random UUID is 128 bits, but only 122 bits
are random.  It's generated according to this algorithm[1]:

,----
|   The version 4 UUID is meant for generating UUIDs from truly-random or
|   pseudo-random numbers.
| 
|   The algorithm is as follows:
| 
|   .  Set the 2 most significant bits (bits numbered 6 and 7) of the
|      clock_seq_hi_and_reserved to 0 and 1, respectively.
| 
|   .  Set the 4 most significant bits (bits numbered 12 to 15 inclusive)
|      of the time_hi_and_version field to the 4-bit version number
|      corresponding to the UUID version being created, as shown in the
|      table above.  [0 1 0 0]
| 
|   .  Set all the other bits to randomly (or pseudo-randomly) chosen
|      values.
`----

The six non-random bits identify which kind of UUID it is, time-based,
random-based etc.

> What does `logior' and `logand' actually do in the script

They set the non-random bits.

> and what does the string #B01000000 mean?

It is read syntax for writing numbers in base 2. `#B01000000' is the
same as the number 64.

[1] http://hegel.ittc.ukans.edu/topics/internet/internet-drafts/draft-l/draft-leach-uuids-guids-01.txt

Re: UUIDGEN in lisp

[Eli Zaretskii]

> Newsgroups: gnu.emacs.help
> From: Jesper Harder <harder@myrealbox.com>
> Date: Mon, 16 Feb 2004 17:30:10 +0100
> 
> Binding coding-system-for-read is definitely necessary.  I'm reading
> random bytes, and I don't want Emacs to convert any of the values.  If
> I don't bind it, `uuid-random' can return a list like:
> 
> (159 92 2210 119 150 148 2275 2265 2290 2220 2240 62 84 2235 150 18)
> 
> which is wrong, since it's not a list of bytes.

Do you have an actual example where that happens?

> Uhm, I don't think there's anything strange about having to bind
> coding-system-for-read to binary -- I _am_ reading binary data, after
> all.

raw-text is probably a better candidate.

Re: UUIDGEN in lisp

[Jesper Harder]

"Eli Zaretskii" <eliz@elta.co.il> writes:

>> Binding coding-system-for-read is definitely necessary.  I'm
>> reading random bytes, and I don't want Emacs to convert any of the
>> values.  If I don't bind it, `uuid-random' can return a list like:
>> 
>> (159 92 2210 119 150 148 2275 2265 2290 2220 2240 62 84 2235 150 18)
>> 
>> which is wrong, since it's not a list of bytes.
>
> Do you have an actual example where that happens?

The list above _is_ an actual example.  It happens all the time if you
don't bind coding-system-for-read -- just try it a few times :-)

>> Uhm, I don't think there's anything strange about having to bind
>> coding-system-for-read to binary -- I _am_ reading binary data, after
>> all.
>
> raw-text is probably a better candidate.

Why?  Doesn't raw-text do EOL conversion?  (which we don't want here).

Re: UUIDGEN in lisp

[Eli Zaretskii]

> Newsgroups: gnu.emacs.help
> From: Jesper Harder <harder@myrealbox.com>
> Date: Mon, 16 Feb 2004 22:05:49 +0100
> 
> The list above _is_ an actual example.  It happens all the time if you
> don't bind coding-system-for-read -- just try it a few times :-)

I tried, but didn't see it.  Probably due to something different in
the way we customize our Emacsen.

> > raw-text is probably a better candidate.
> 
> Why?  Doesn't raw-text do EOL conversion?  (which we don't want here).

raw-text-unix is your friend.

Re: UUIDGEN in lisp

[Jesper Harder]

Eli Zaretskii <eliz@elta.co.il> writes:

>> > raw-text is probably a better candidate.
>> 
>> Why?  Doesn't raw-text do EOL conversion?  (which we don't want here).
>
> raw-text-unix is your friend.

What is the difference between `raw-text-unix' and `binary'?  In which
cases should you use one or the other?

Re: UUIDGEN in lisp

[Eli Zaretskii]

> Newsgroups: gnu.emacs.help
> From: Jesper Harder <harder@myrealbox.com>
> Date: Tue, 17 Feb 2004 19:45:37 +0100
> 
> What is the difference between `raw-text-unix' and `binary'?  In which
> cases should you use one or the other?

I suggest to use raw-text-unix when doing I/O of random bytes that you
don't want to be mangled.  no-conversion (binary is just its alias)
once meant that the internal Mule representation was read and written
to produce multibyte characters, so I suggest to avoid that to prevent
confusion.

Re: UUIDGEN in lisp

[Jesper Harder]

"Eli Zaretskii" <eliz@elta.co.il> writes:

>> What is the difference between `raw-text-unix' and `binary'?  In which
>> cases should you use one or the other?
>
> I suggest to use raw-text-unix when doing I/O of random bytes that you
> don't want to be mangled.  no-conversion (binary is just its alias)
> once meant that the internal Mule representation was read and written
> to produce multibyte characters, so I suggest to avoid that to prevent
> confusion.

So you're saying that `raw-text-unix' and `binary' are completely
equivalent today, right?

Re: UUIDGEN in lisp

[Eli Zaretskii]

> Newsgroups: gnu.emacs.help
> From: Jesper Harder <harder@myrealbox.com>
> Date: Tue, 17 Feb 2004 22:21:07 +0100
> 
> So you're saying that `raw-text-unix' and `binary' are completely
> equivalent today, right?

Yes, it seems like that.  But the exact meaning of both raw-text and
no-conversion has changed several times since Emacs 20.1, so I'd
suggest to preserve the distinction mentally, to keep your sanity.

Re: UUIDGEN in lisp

[Stefan Monnier]

> I suggest to use raw-text-unix when doing I/O of random bytes that you
> don't want to be mangled.  no-conversion (binary is just its alias)
> once meant that the internal Mule representation was read and written
> to produce multibyte characters, so I suggest to avoid that to prevent
> confusion.


AFAIK, binary, no-conversion, and raw-text-unix are completely equivalent.
There might have been an earlier version of Emacs where `binary' was not
handled as binary, but that was clearly a bug because `binary' says very
clearly what it means.
So I recommend to use `binary' when reading a binary file because it's
obviously the right thing and if things go wrong it's clear that it's
a problem with Emacs rather than with the elisp code.  The bytes read from
/dev/urandom have nothing to do with text, so `raw-text-unix' is just
a bad choice.


        Stefan