Generate four type-4 GUIDs for me

Question

The type 4 GUID is described by Wikipedia, quoth:

Version 4 UUIDs use a scheme relying only on random numbers. This algorithm sets the version number (4 bits) as well as two reserved bits. All other bits (the remaining 122 bits) are set using a random or pseudorandom data source. Version 4 UUIDs have the form xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx where x is any hexadecimal digit and y is one of 8, 9, A, or B (e.g., f47ac10b-58cc-4372-a567-0e02b2c3d479).

Write a program that loads 488 bits (61 bytes) of cryptographic quality randomness and output them as 4 GUIDs using the format quoted above.

• Do not waste randomness.
  • All random bits must appear in the encoded output.
  • All encoded bits must be traceable to either a single random bit or one of the six fixed bits that must appear in each GUID.
• Use the cryptographic quality random number generator supplied by your language's standard library.
• Do not use a library or external resource that generates GUIDs.
• The hyphens must appear in their correct positions.
• The fixed bits of this form of GUID must appear in their correct positions.
• You may use a standard library function designed to output a GUID from 128 bits.
• Normal code-golf rules apply.

For example...

> gentype4
6FA53B63-E7EA-4461-81BE-9CD106A1AFF8
856970E9-377A-458E-96A7-43F587724573
E4F859AC-0004-4AA1-A3D2-AECB527D1D24
766811C5-0C44-4CC8-8C30-E3D6C7C6D00B

Update:
I asked for four GUIDs in order to allow a whole number of random bytes to be gathered without leaving any remainder. I also specified that none of the bits should be wasted in order to avoid the easy answer of getting 16 random bytes and dropping the 4 in. (No, shift the other bits along first.)

Update 2:
If your language's standard library doesn't have a cryptographic quality random byte generator, you may instead assume that there is a 61 byte file present with enough random bytes for you to use when the program starts. The file should be called "/dev/urandom" or another filename with 12 characters.

Answer 1

PHP, 338 bytes

<?php $r=openssl_random_pseudo_bytes(61);$b="";$s="substr";for($i=0;$i<61;)$b.=str_pad(decbin(ord($r[$i++])),8,0,0);function p($B,$L){return str_pad(dechex(bindec($B)),$L,0,0);}for($i=0;$i<4;$i++)echo p($s($b,$p=122*$i,32),8)."-".p($s($b,$p+32,16),4)."-4".p($s($b,$p+48,12),3)."-".p("10".$s($b,$p+60,14),4)."-".p($s($b,$p+74,48),12)."\n";

Some output

> php 32309.min.php
635fa088-4a66-47fc-9e50-2ccb2445b643
6e5c23c7-ba16-427e-960b-5316980ce4e3
fdb570ca-2e5e-4594-ab2e-db8446599b8f
203f2538-b5f4-47f0-89ac-012ca14b2f99
> php 32309.min.php
a6981255-0ab2-4d82-aab4-d1c64d2bb7eb
c348e728-f817-45d2-9bbf-b40426baa461
9b2baed2-e58b-41ef-a6fb-57e96db74a68
63e464e7-ab55-4e2a-a2a0-abdc535481dc
> php 32309.min.php
af7e68d3-b3ed-4e19-85b2-280270f746c6
0a86c610-8d0c-4c0a-bafe-44a6886d71f8
98c742b8-6a3b-47ff-97c7-ccab70d79a3c
59a93afc-ff81-4c97-a57b-72f0de384acb
> php 32309.min.php
72b352fc-0174-4051-969e-cacc0adbf941
50e4f859-76fe-45f6-baf5-d5fcceb41f72
5a18408e-6e7e-43a6-bd71-09d22a0fbf14
ae5a1391-5367-467e-8ecc-785ca72cbf95

Ungolfed

<?php
$r = openssl_random_pseudo_bytes(61);
$b = "";
$s = "substr";
for($i=0 ; $i<61 ;) $b .= str_pad(decbin(ord($r[$i++])), 8, 0, 0);

function p($B, $L) {
    return str_pad(dechex(bindec($B)), $L, 0, 0);
}

for($i=0 ; $i<4 ; $i++) {
    echo p($s($b, 122*$i, 32), 8)."-";
    echo p($s($b, 122*$i+32, 16), 4)."-4";
    echo p($s($b, 122*$i+48, 12), 3)."-";
    echo p("10".$s($b, 122*$i+60, 14), 4)."-";
    echo p($s($b, 122*$i+74, 48), 12)."\n";
}

Answer 2

J - 114 bytes

I took the simplest approach available. The function takes amount of GUID's required (you could replace the ] near the end with 4: to make it return 4 always) and outputs that many of them, separated by newlines.

Edit: I missed that no generated bits must go to waste... This answer doesn't comply and I don't know how to make it to.

f=:[:}.(,LF,(x@8:,'-',x@4:,'-4',x,'-',('89AB'{~?@4:),x,'-',(x=:'0123456789ABCDEF'{~?@$&16)@(12"_))@3:)^:(]`(''"_))

If an extra newline is allowed after the output, this could be written in 111 bytes.

f=:(,LF,~(x@8:,'-',x@4:,'-4',x,'-',('89AB'{~?@4:),x,'-',(x=:'0123456789ABCDEF'{~?@$&16)@(12"_))@3:)^:(]`(''"_))

Example:

   f 4
B23B10E3-6593-40F7-A5B0-D25A2763D781
3901709C-654E-4AF0-B23E-7252E859D35B
91E8D566-8E84-48CD-9B9D-EFC4E3F62C4E
F4578389-097C-4C38-A3C0-31EABFDCD630
   f 5
AF234012-8A9F-47A3-9BF5-4B28AF580E9C
A3FE1785-8B40-44E9-8D69-CFF1BE06AC06
84A2CEB9-744F-4B86-B37F-747D0FD3F3FC
0FD8B7A6-9642-42C3-89ED-DB4A35D83CF8
4F860D9B-6E20-4AF8-B6BF-0F8CB307B9B0

Answer 3

Golfscript, 75

Fixed now!

{{'0123456789ABCDEF'{.,rand>1<}:|~}:&8*'-':^&&&&^4&&&^'89AB'|&&&^{&}12*n}4*

Output example:

>ruby golfscript.rb p.gs
140BC879-EAC4-4170-B349-A616523458DB
E26B34A4-8E86-4508-9EE5-3C76BF7456B6
89F9B995-CC9E-4EF0-AA25-70703B80AF82
5F6A513C-9E97-45A4-A9D1-E9D3DF71EF99

>ruby golfscript.rb p.gs
38D7A76B-BEEB-4C98-A148-D1EA8C31E85F
807373E4-5CFE-4953-9D5E-671205EE1E8F
8BD88B76-5890-4543-9787-2753AB15D24B
CD7DF25F-632B-4902-A46C-A1E10BE83EC5

You can test it yourself here.

Answer 4

Python (85)

import os,uuid
for i in [1]*4:print uuid.UUID(os.urandom(16).encode('hex'),version=4)

os.urandom(n): Return a string of n random bytes suitable for cryptographic use.

I assume generating more than 488 bits is ok?

Answer 5

Python 2 - 188 / 182

This should obey the requirements faithfully:

import os
a=(ord(x)>>i&3for i in(0,2,4,6)for x in os.urandom(61))
h=lambda n:eval('"%X"%(a.next()*4+a.next())+'*n+'"-"')
exec'print h(8)+h(4)+"4"+h(3)+"%X"%(8+a.next())+h(3)+h(12)[:-1];'*4

If python's UUID is acceptable for outputting a nicely-formatted uuid from a 32-digit hex string, then this version has 182 bytes:

import os,uuid
a=(ord(x)>>i&3for i in(0,2,4,6)for x in os.urandom(61))
exec('s='+'"%X"%(a.next()*4+a.next())+'*30+'"";print uuid.UUID(s[3:15]+"4"+s[:3]+"%X"%(8+a.next())+s[15:]);')*4

a is a generator comprehension that gives 2 bits at a time from an initial source of 61 random bytes.

Thanks TheRare for tips

Answer 6

Javascript (ES6) - 177 163 158

Removed .toUpperCase(), replaced substring with substr and substr(0,3) to substr(1)

function f(){g=()=>(((1+Math.random())*0x10000)|0).toString(16).substr(1);for(i=0;i<4;i++)alert((g()+g()+"-"+g()+"-4"+g().substr(1)+"-"+g()+"-"+g()+g()+g()))}

EcmaScript 5 version of the above script:

function f(){function g(){return (((1+Math.random())*0x10000)|0).toString(16).substr(1)}for(i=0;i<4;i++)alert((g()+g()+"-"+g()+"-4"+g().substr(1)+"-"+g()+"-"+g()+g()+g()))}

Answer 7

Common Lisp

SBCL, 223

(define-alien-routine("arc4random_uniform"a)int(u
int))(labels((g(n)(a(expt 2 n)))(h()(g 16)))(dotimes(i 4)(format
t"~4,'0X~4,'0X-~4,'0X-~4,'0X-~4,'0X-~4,'0X~4,'0X~4,'0X~%"(h)(h)(h)(+
16384(g 12))(+ 32768(g 14))(h)(h)(h))))

CLISP, 299

(use-package :ffi)(def-call-out
a(:name"arc4random_uniform")(:arguments(u int))(:return-type
int)(:language :c)(:library :default))(labels((g(n)(a(expt 2
n)))(h()(g 16)))(dotimes(i 4)(format
t"~4,'0X~4,'0X-~4,'0X-~4,'0X-~4,'0X-~4,'0X~4,'0X~4,'0X~%"(h)(h)(h)(+
16384(g 12))(+ 32768(g 14))(h)(h)(h))))

About arc4random_uniform(3)

Both of these call the C function arc4random_uniform(3) in BSD libc. Some systems do not have this function.

Beware that my declaration of arc4random_uniform(3) is wrong. The correct declaration is

u_int32_t arc4random_uniform(u_int32_t);

where u_int32_t is an old BSDism for an unsigned 32-bit integer. (The standard type in C99 is uint32_t without the first underscore.) My wrong declaration is

int arc4random_uniform(int);

where int is a signed 32-bit integer. (I know systems where int only has 16 bits, but I would not run Lisp there.) I am wrong to use signed for unsigned, but my program works because I only pass small non-negative integers. In code golf, int is shorter than unsigned-int in SBCL or uint in CLISP.

To use arc4random_uniform(3) in Lisp, I define a Lisp function a. Here it is in SBCL:

; (use-package :sb-alien)  ; SBCL does this by default!
(define-alien-routine ("arc4random_uniform" a)
  int       ; return type
  (u int))  ; argument named u

And in CLISP:

(use-package :ffi)
(def-call-out a
  (:name "arc4random_uniform")
  (:arguments (u int))
  (:return-type int)
  (:language :c)
  (:library :default))

CLISP has two languages, :c for traditional K&R C and :stdc for C89, but I find no difference, so I use the shorter name.

Now (a u) returns a random integer at least 0 and less than u. If u is 2ⁿ, then I get exactly n bits. For example, (a (expt 2 14) provides 14 bits. Because of my wrong declaration, u must be less than 2³¹. If I want 32 bits, I may call (a 16) twice.

Rest of program

; after defining A
(labels ((g (n) (a (expt 2 n)))
         (h () (g 16)))
  (dotimes (i 4)
    (format t
            "~4,'0X~4,'0X-~4,'0X-~4,'0X-~4,'0X-~4,'0X~4,'0X~4,'0X~%"
            (h) (h) (h) (+ 16384 (g 12)) (+ 32768 (g 14)) (h) (h) (h))))

I define two local functions. (g n) generates n random bits. (expt 2 n) is much shorter than a left shift: 1<<n in C would become (let((v 0))(setf(ldb(byte 1 n)v)1)v) in Common Lisp!

(h) is an alias for (g 16). This alias costs 13 characters: 11 in (h()(g 16)), plus 2 to upgrade flet to labels, because h needs g in scope. Each call to (h) saves 3 characters, and I have 6 calls, so I save 18 after I spend 13.

When formatting each GUID, (+ 16384(g 12)) is shorter than (logior #x4000 (g 12) and (+ 32768(g 14)) is shorter than (logior #x8000 (g 14)).

One can generate the long format string "~4,'0X~4,'0X-~4,'0X-~4,'0X-~4,'0X-~4,'0X~4,'0X~4,'0X~%" (56 characters) with the expression (format()"~{~A~}~~%"(mapcar(lambda(e)(if e(format()"~~4,'0X")'-))'(t t()t()t()t()t t t))) (89 characters), but the literal string is shorter.