From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pl1-x62b.google.com (mail-pl1-x62b.google.com [IPv6:2607:f8b0:4864:20::62b]) by sourceware.org (Postfix) with ESMTPS id 70C46385381B for ; Tue, 2 Aug 2022 13:28:33 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 70C46385381B Received: by mail-pl1-x62b.google.com with SMTP id w14so389876plp.9 for ; Tue, 02 Aug 2022 06:28:33 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-message-state:from:to:cc; bh=wJ9Da12QKxuOoSMNQzdP0k3h0iEqpsXR+A6MDJHho1I=; b=DvPxuNjiS1XTpN77vWQQLRje6W0S1Z7q6107UHhoELYWV/G6E8uto2hDMbe47dAEB4 DUzmMH/6bxNVWjiRXH2LsUiIBHIjtjhSzm8uFSxkCpmi1ldqZDOdzOPgVUsrKWTuk5kF /G+iBsjNBCEFfW7HMUIWtzv+w5vRDnr0FS8Na3Ak20qyvON3WqoGFBfmGjm9jckyCWPN GrDNrgNHmE/aSWhgwqLq8zu3IYXAfn/sE7gC4VeJSrdwGFny00h5P7q8UfbAouNUyphz dvrxveLtPleIvqpAIVUSf5fxexyD62oio5H75ileFQtdAmRhq48jyPfvYStp39T+Reud Hdcg== X-Gm-Message-State: ACgBeo3nu3LeQjh/yHokWprGxxqRbur4bcOOTtawq98aaNRYVCSFLh/9 ZgFe/9F/xEUFu+BquH26Rp8rkXuQ30rDit9h X-Google-Smtp-Source: AA6agR4JW3TGkjp0D50eFjKDzsxPrZZKzqkWrNCAfsvSjSoJ4giymmQHkXNptZBocFDfC8y9I+F3jg== X-Received: by 2002:a17:902:70cc:b0:16c:60e0:50fb with SMTP id l12-20020a17090270cc00b0016c60e050fbmr21283323plt.156.1659446912195; Tue, 02 Aug 2022 06:28:32 -0700 (PDT) Received: from noah-tgl.. ([192.198.168.36]) by smtp.gmail.com with ESMTPSA id 67-20020a620446000000b0052c8208ef0asm10743740pfe.24.2022.08.02.06.28.29 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 02 Aug 2022 06:28:31 -0700 (PDT) From: Noah Goldstein To: libc-alpha@sourceware.org Subject: [PATCH v1] stdlib: Add more room for reuse of random bits in arc4random_uniform Date: Tue, 2 Aug 2022 21:28:25 +0800 Message-Id: <20220802132825.3218379-1-goldstein.w.n@gmail.com> X-Mailer: git-send-email 2.34.1 MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-10.1 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, RCVD_IN_BARRACUDACENTRAL, 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-List-Received-Date: Tue, 02 Aug 2022 13:28:35 -0000 The shift optimization doesn't need to clear all `z` bits. Bias is only introduced if shift count is less than the number of leading 1s. I.e for n = 6, for `value & mask` to be greater than `n` the bits in position 1/2 must be set so they must be set. But the bit in position 0 can be 0/1 (is completely unrelated to the comparison) so we can keep it for the next comparison only use a shift of 2. This patch reduces the number of expected syscalls if `n` is not a power_of_two - 1 --- stdlib/arc4random_uniform.c | 8 +++++++- 1 file changed, 7 insertions(+), 1 deletion(-) diff --git a/stdlib/arc4random_uniform.c b/stdlib/arc4random_uniform.c index 5aa98d1c13..e5c9dd04cf 100644 --- a/stdlib/arc4random_uniform.c +++ b/stdlib/arc4random_uniform.c @@ -45,7 +45,13 @@ __arc4random_uniform (uint32_t 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; + /* Amount of bits to shift out of value before retesting if `(value + & mask) < n`. We want this to be as small as possible to avoid + calling __arc4random (which has a syscall). The minimal value + without adding bias to the result is the number of leading 1s in `n` + starting at position `z`. popcount(n) is guaranteed to be as least + that large and is relatively fast. */ + int bits = __builtin_popcount (n); while (1) { -- 2.34.1