From patchwork Fri Jul 29 12:32:11 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: 56434 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 B5D193858429 for ; Fri, 29 Jul 2022 12:32:40 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org B5D193858429 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1659097960; bh=wCz1oQTa8AElPczSse6l5gJ9Hn9mS6IfRYm+veLw0lk=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=pwdtMWP38+lyoSeclKjgNPZu2cqAFRKnlmbU4CxU6/L7SplqDf45u4o7UZsWu+6NM 1HX76bwTFNTbN48f14sNy8h2fJQ8Wb0Ccn8r2ssbkGl3Xddrd1O3MCkufCrys76Ynh Y0XYoeuArQeTsutKAlmoC4TpFFZMFNbbSytL8oc0= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-vk1-xa31.google.com (mail-vk1-xa31.google.com [IPv6:2607:f8b0:4864:20::a31]) by sourceware.org (Postfix) with ESMTPS id A8DE13858429 for ; Fri, 29 Jul 2022 12:32:18 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org A8DE13858429 Received: by mail-vk1-xa31.google.com with SMTP id q14so689462vke.9 for ; Fri, 29 Jul 2022 05:32:18 -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=wCz1oQTa8AElPczSse6l5gJ9Hn9mS6IfRYm+veLw0lk=; b=CaBJ3PHX7/i46+21L0Eo16EP6/PYSbrXwGWDZBWLtCfmWc59jLKxIg1gTxnB5UeZwL FjkKhdpakRh4uoO3Wxft2LgkS0Kfeg0H6xDj6uPzAAp3RhaarGJ3Z+RGiCzgJoyOWHUh P3WC5RnBMNhm/3cHen9Yr3hex31A7brgz4RTCiiNi6kK2ewQdCsmGPnmptf2Nkt06KXe kbNfSRO+KH0zeNzedBCiHdwcEggIBWovISP1GixmsSRf9T91aMe/OSPWqhL9T9qO6FPw iTMtqLmVRZBB5kQe6kb6w7dQNLIndcmJJMArOeiX5OsJozr/Z96eeCRz0rUWwGgDkEQV mqmA== X-Gm-Message-State: AJIora+eqLa+BTZ3yjsT0ol3W1KMFOzlF2wJZ5xSFjUe+YnWhYru4eLQ E0xw7UuxYpQIOkHeRpQeitkAFarchKx7SA== X-Google-Smtp-Source: AGRyM1uFelJH9oiy5TTWQpFhc/LCkEFAoP/wm5rDgH8/mI5hR6liwxZwXBUvUcge2gjvHVQQuiXCGg== X-Received: by 2002:a05:6122:da8:b0:376:c611:9cdf with SMTP id bc40-20020a0561220da800b00376c6119cdfmr1097255vkb.36.1659097937766; Fri, 29 Jul 2022 05:32:17 -0700 (PDT) Received: from mandiga.. ([2804:431:c7cb:1e34:6d1c:a7bd:d033:5986]) by smtp.gmail.com with ESMTPSA id c20-20020ab07a74000000b0038467d003e3sm811026uat.38.2022.07.29.05.32.16 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 29 Jul 2022 05:32:17 -0700 (PDT) To: libc-alpha@sourceware.org, Florian Weimer , Carlos O'Donell , Yann Droneaud , Paul Eggert Subject: [PATCH v2] stdlib: Simplify arc4random_uniform Date: Fri, 29 Jul 2022 09:32:11 -0300 Message-Id: <20220729123211.876374-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 conserve bits since arc4random is wrapper on getrandom syscall. It should be cheaper to just query a uint32_t value. The algorithm also avoids modulo 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 --- v2: Fixed typos in commit message and simplify loop. --- stdlib/arc4random_uniform.c | 129 +++++++++--------------------------- 1 file changed, 30 insertions(+), 99 deletions(-) diff --git a/stdlib/arc4random_uniform.c b/stdlib/arc4random_uniform.c index 1326dfa593..5aa98d1c13 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,33 @@ __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. */ + for (int bits_left = z; bits_left >= bits; bits_left -= bits) + { + value >>= bits; + r = value & mask; + if (r < n) + return r; + } } } libc_hidden_def (__arc4random_uniform)