Re: [libvirt] [PATCH 1/8] Add virRandom() API to generate numbers with non-power-of-2 limit
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(a)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(a)redhat.com +1-919-301-3266
Libvirt virtualization library http://libvirt.org
Attachments:
- signature.asc (application/pgp-signature — 620 bytes)