From patchwork Thu Jul 28 12:45:28 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Adhemerval Zanella Netto X-Patchwork-Id: 56391 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 5B9B63857C51 for ; Thu, 28 Jul 2022 12:45:57 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 5B9B63857C51 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1659012357; bh=ycPbrsitBNtUmZEFlMkZKrc8WPLv63dZWkDawjwcyEw=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=P/9jSr2P0ovnBOW2IWsnpcoXbWuHtNdL2jg2TV1UISTI+0PgMKD/E+5sGMfFbE1NM HYzfbcLyMUq3usc/eP0c9uWgaaPtFjWI8tPPjTxOUboWwhW9dcJzQd7o+2D99otOEv neMMdD/reOBb0kMqlDkyJS+Rvdz/SOIUPVyuY5NQ= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-oa1-x2a.google.com (mail-oa1-x2a.google.com [IPv6:2001:4860:4864:20::2a]) by sourceware.org (Postfix) with ESMTPS id 192AB385800B for ; Thu, 28 Jul 2022 12:45:36 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 192AB385800B Received: by mail-oa1-x2a.google.com with SMTP id 586e51a60fabf-10e49d9a59bso2187374fac.5 for ; Thu, 28 Jul 2022 05:45:36 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:subject:date:message-id:mime-version :content-transfer-encoding; bh=ycPbrsitBNtUmZEFlMkZKrc8WPLv63dZWkDawjwcyEw=; b=YvfQXFKeTDUsfGwmxmhiFPzGqfafGJO1yXdHvRsHQBP13dnRJqjdihQ0NyIuyirOvX 0HqP5HzoB5UHsnKpfp67a2KECtaFl+vDWL3rr8T6gCKWu5xsGNBNHsfWn5o52HNvIB26 OlRLL1Q9mkxItU1w64hI6M+GIApxk1vf8lyQSEUaQ35ZYOu0cr5XCkDUnCTul5/3+pnW 8dkJzU0tsJtSQRvp4Q3tLedH9Q08rAO6/36fDa6zu7+zw8etWf8XCv+ikDuhKtOs1sSc zYBW1RPFZHqQ8yLm2KjrlsIAR/2c4oYsThj6ShrEV3xKSBGSOmQ6/uHtKbQz/ATngzLk wkcw== X-Gm-Message-State: AJIora+SJm1o1CPRc/+WYtbWlM42pOWS+iZXgkGC3jaLp9Um1bH5KrQZ DpkiCLwBpdoavaEKGiDjHfp9XxtC6PZ7Vw== X-Google-Smtp-Source: AGRyM1uN5SP4+DPL3MXDK2lhOolSXHT0cGvyi8Y+0uN5n++g0aQLnGiPc1hL7mNhDFoI+ZFuJEJOIQ== X-Received: by 2002:a05:6870:14c3:b0:fb:46b4:5b3f with SMTP id l3-20020a05687014c300b000fb46b45b3fmr4487492oab.56.1659012335187; Thu, 28 Jul 2022 05:45:35 -0700 (PDT) Received: from mandiga.. ([2804:431:c7cb:1e34:9d84:708f:f913:7597]) by smtp.gmail.com with ESMTPSA id l16-20020a544110000000b0033a422b39b4sm213358oic.49.2022.07.28.05.45.32 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 28 Jul 2022 05:45:34 -0700 (PDT) To: libc-alpha@sourceware.org, Florian Weimer , Carlos O'Donell , Yann Droneaud Subject: [PATCH] stdlib: Simplify arc4random_uniform Date: Thu, 28 Jul 2022 09:45:28 -0300 Message-Id: <20220728124528.39169-1-adhemerval.zanella@linaro.org> X-Mailer: git-send-email 2.34.1 MIME-Version: 1.0 X-Spam-Status: No, score=-10.4 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_SHORT, MIME_CHARSET_FARAWAY, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, 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 X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Adhemerval Zanella via Libc-alpha From: Adhemerval Zanella Netto Reply-To: Adhemerval Zanella Errors-To: libc-alpha-bounces+patchwork=sourceware.org@sourceware.org Sender: "Libc-alpha" It uses the bitmask with rejection [1], which calculates a mask being the lowest power of two bounding the request upper bound, successively queries new random values, and rejects values outside the requested range. Performance-wise, there is no much gain in trying to converse bits since arc4random is wrapper on getrandom syscall. It should be cheaper to just query a uint32_t value. The algorithm also avoids mudulo and divide operations, which might be costly depending of the architecture. [1] https://www.pcg-random.org/posts/bounded-rands.html Reviewed-by: Yann Droneaud --- stdlib/arc4random_uniform.c | 131 +++++++++--------------------------- 1 file changed, 32 insertions(+), 99 deletions(-) diff --git a/stdlib/arc4random_uniform.c b/stdlib/arc4random_uniform.c index 1326dfa593..425282cd15 100644 --- a/stdlib/arc4random_uniform.c +++ b/stdlib/arc4random_uniform.c @@ -17,38 +17,19 @@ License along with the GNU C Library; if not, see . */ -#include -#include #include #include -/* Return the number of bytes which cover values up to the limit. */ -__attribute__ ((const)) -static uint32_t -byte_count (uint32_t n) -{ - if (n < (1U << 8)) - return 1; - else if (n < (1U << 16)) - return 2; - else if (n < (1U << 24)) - return 3; - else - return 4; -} +/* Return a uniformly distributed random number less than N. The algorithm + calculates a mask being the lowest power of two bounding the upper bound + N, successively queries new random values, and rejects values outside of + the request range. -/* Fill the lower bits of the result with randomness, according to the - number of bytes requested. */ -static void -random_bytes (uint32_t *result, uint32_t byte_count) -{ - *result = 0; - unsigned char *ptr = (unsigned char *) result; - if (__BYTE_ORDER == __BIG_ENDIAN) - ptr += 4 - byte_count; - __arc4random_buf (ptr, byte_count); -} + For reject values, it also tries if the remaining entropy could fit on + the asked range after range adjustment. + The algorithm avoids modulo and divide operations, which might be costly + depending on the architecture. */ uint32_t __arc4random_uniform (uint32_t n) { @@ -57,83 +38,35 @@ __arc4random_uniform (uint32_t n) only possible result for limit 1. */ return 0; - /* The bits variable serves as a source for bits. Prefetch the - minimum number of bytes needed. */ - uint32_t count = byte_count (n); - uint32_t bits_length = count * CHAR_BIT; - uint32_t bits; - random_bytes (&bits, count); - /* Powers of two are easy. */ if (powerof2 (n)) - return bits & (n - 1); - - /* The general case. This algorithm follows Jérémie Lumbroso, - Optimal Discrete Uniform Generation from Coin Flips, and - Applications (2013), who credits Donald E. Knuth and Andrew - C. Yao, The complexity of nonuniform random number generation - (1976), for solving the general case. + return __arc4random () & (n - 1); - The implementation below unrolls the initialization stage of the - loop, where v is less than n. */ + /* mask is the smallest power of 2 minus 1 number larger than n. */ + int z = __builtin_clz (n); + uint32_t mask = ~UINT32_C(0) >> z; + int bits = CHAR_BIT * sizeof (uint32_t) - z; - /* Use 64-bit variables even though the intermediate results are - never larger than 33 bits. This ensures the code is easier to - compile on 64-bit architectures. */ - uint64_t v; - uint64_t c; - - /* Initialize v and c. v is the smallest power of 2 which is larger - than n.*/ - { - uint32_t log2p1 = 32 - __builtin_clz (n); - v = 1ULL << log2p1; - c = bits & (v - 1); - bits >>= log2p1; - bits_length -= log2p1; - } - - /* At the start of the loop, c is uniformly distributed within the - half-open interval [0, v), and v < 2n < 2**33. */ - while (true) + while (1) { - if (v >= n) - { - /* If the candidate is less than n, accept it. */ - if (c < n) - /* c is uniformly distributed on [0, n). */ - return c; - else - { - /* c is uniformly distributed on [n, v). */ - v -= n; - c -= n; - /* The distribution was shifted, so c is uniformly - distributed on [0, v) again. */ - } - } - /* v < n here. */ - - /* Replenish the bit source if necessary. */ - if (bits_length == 0) - { - /* Overwrite the least significant byte. */ - random_bytes (&bits, 1); - bits_length = CHAR_BIT; - } - - /* Double the range. No overflow because v < n < 2**32. */ - v *= 2; - /* v < 2n here. */ - - /* Extract a bit and append it to c. c remains less than v and - thus 2**33. */ - c = (c << 1) | (bits & 1); - bits >>= 1; - --bits_length; - - /* At this point, c is uniformly distributed on [0, v) again, - and v < 2n < 2**33. */ + uint32_t value = __arc4random (); + + /* Return if the lower power of 2 minus 1 satisfy the condition. */ + uint32_t r = value & mask; + if (r < n) + return r; + + /* Otherwise check if remaining bits of entropy provides fits in the + bound. */ + int bits_left = z; + while (bits_left >= bits) + { + value >>= bits; + r = value & mask; + if (r < n) + return r; + bits_left -= bits; + } } } libc_hidden_def (__arc4random_uniform)