[libvirt] [PATCH 1/8] Add virRandom() API to generate numbers with non-power-of-2 limit

[Eric Blake]

On 08/10/2012 08:58 AM, Eric Blake wrote:
> On 08/10/2012 07:47 AM, Daniel P. Berrange wrote:
>> From: "Daniel P. Berrange" <berrange at redhat.com>
>>
>> The current virRandomBits() API is only usable if the caller wants
>> a random number in the range [0, (n-1)] where n is a power of two.
>> This adds a virRandom() API which works for upper limits which are
>> not a power of two. It works by using virRandomBits() to generate
>> a number to the next nearest power of 2 limit, and then scales it
>> down.
> 

>> +
>> +    while (tmp) {
>> +        tmp >>= 1;
>> +        bits++;
>> +    }
> 
> Slow.  I would suggest using gcc's __builtin_clz (the way qemu does),
> except that gnulib doesn't yet have a module exposing it.  I guess that
> means I'd better write a quick gnulib module.  Once you have clz(), this
> is much simpler as:
> 
> assert(max);
> bits = 64 - clz(max);

Gnulib side is done.  If you apply this patch to libvirt (including an
update to the latest gnulib), then you can #include
"count-leading-zeros.h" and call count_leading_zeros_ll(max) (spelled
that way in gnulib rather than clz to minimize potential clashes, since
it is not a standardized function).

diff --git i/.gnulib w/.gnulib
index dbd9144..0da76a9 160000
--- i/.gnulib
+++ w/.gnulib
@@ -1 +1 @@
-Subproject commit dbd914496c99c52220e5f5ba4121d6cb55fb3beb
+Subproject commit 0da76a94c8668319c68af5e8c2e71c80528db5de
diff --git i/bootstrap.conf w/bootstrap.conf
index c112ccd..58558c8 100644
--- i/bootstrap.conf
+++ w/bootstrap.conf
@@ -33,6 +33,7 @@ chown
 close
 connect
 configmake
+count-leading-zeros
 count-one-bits
 crypto/md5
 dirname-lgpl

-- 
Eric Blake   eblake at redhat.com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 620 bytes
Desc: OpenPGP digital signature
URL: <http://listman.redhat.com/archives/libvir-list/attachments/20120810/93ab8186/attachment-0001.sig>