From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from ouvsmtp1.octopuce.fr (ouvsmtp1.octopuce.fr [194.36.166.50]) by sourceware.org (Postfix) with ESMTPS id E70533858D1E for ; Fri, 30 Dec 2022 20:18:12 +0000 (GMT) Received: from panel.vitry.ouvaton.coop (unknown [194.36.166.20]) by ouvsmtp1.octopuce.fr (Postfix) with ESMTPS id 1C2C61B2; Fri, 30 Dec 2022 21:18:11 +0100 (CET) Received: from sm.ouvaton.coop (ouvadm.octopuce.fr [194.36.166.2]) by panel.vitry.ouvaton.coop (Postfix) with ESMTPSA id D529A5E2351; Fri, 30 Dec 2022 21:18:10 +0100 (CET) MIME-Version: 1.0 Date: Fri, 30 Dec 2022 20:18:10 +0000 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable From: "Yann Droneaud" Message-ID: Subject: Re: stdc_bit_ceil(3) and wrapping To: "Alejandro Colomar" , "Joseph Myers" Cc: gcc@gcc.gnu.org, "GNU C Library" In-Reply-To: References: X-Originating-IP: 10.0.20.16 X-Spam-Status: No, score=-5.6 required=5.0 tests=BAYES_00,KAM_DMARC_STATUS,SPF_HELO_PASS,SPF_PASS,TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: Hi, 30 d=C3=A9cembre 2022 =C3=A0 20:55 "Alejandro Colomar via Libc-alpha" a =C3=A9crit: >=20 >=20I'm implementing a small part of equivalent code for shado= w. I need=20 >=20stdc_bit_ceilul() for a random number generator limited to a range (y= ou've seen=20 >=20some of this in the glibc mailing list. >=20 >=20$ grepc -tfd shadow_random_uniform > ./libmisc/random.c:76: > unsigned long > shadow_random_uniform(unsigned long upper_bound) > { > unsigned long r; >=20 >=20 do { > r =3D shadow_random(); > r &=3D bit_ceil_wrapul(upper_bound) - 1; // optimization > } while (r > upper_bound - 1); >=20 >=20 return r; > } >=20 What's=20wrong with the following ? if (upper_bound < 2) return 0; unsigned long max =3D upper_bound - 1; unsigned long mask =3D ULONG_MAX >> __builtin_clzl(max); do { r =3D shadow_random(); r &=3D mask; } while (r > max); return r; > However, I need that it doesn't have undefined behavior if it doesn't f= it the=20 >=20type, but rather that it wraps around (as the simplest implementation= would do,=20 >=20BTW). I've done the following: >=20 >=20$ cat lib/bit.h > #include >=20 >=20inline int leading_zerosul(unsigned long x); > inline int bit_widthul(unsigned long x); > inline int bit_ceil_wrapul(unsigned long x); >=20 >=20inline int > leading_zerosul(unsigned long x) > { > return (x =3D=3D 0) ? ULONG_WIDTH : __builtin_clz(x); > } >=20 >=20inline int > bit_widthul(unsigned long x) > { > return ULONG_WIDTH - leading_zerosul(x); > } >=20 >=20/* Similar to stdc_bit_ceilul(), but wrap around instead of UB. */ > inline int > bit_ceil_wrapul(unsigned long x) > { > return 1 << bit_widthul(x - 1); > } >=20 >=20I was wondering if there was any reason to make that UB in the standa= rd, when=20 >=20unsigned wrapping has always been well-defined, and this is a case th= at is=20 >=20likely to be implemented with some operation that wraps around, right= ? I can't=20 >=20imagine of an implementation that invokes UB. Moreover, as you can se= e, it is=20 >=20useful to make it wrap around in a defined way. >=20 >=20Would you consider either or both of being more generous in the GNU= =20 >=20implementation and guarantee wrap around, and/or suggest that the sta= ndard=20 >=20guarantees the wrap around? >=20 >=20And BTW, if any of this code helps you implement that for GNU, please= feel free=20 >=20to take it. :) >=20 --=20 Yann Droneaud OPTEYA