From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ua1-x92c.google.com (mail-ua1-x92c.google.com [IPv6:2607:f8b0:4864:20::92c]) by sourceware.org (Postfix) with ESMTPS id 70F34385AE43 for ; Tue, 2 Aug 2022 12:14:52 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 70F34385AE43 Received: by mail-ua1-x92c.google.com with SMTP id f15so5691426uao.12 for ; Tue, 02 Aug 2022 05:14:52 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:date:mime-version:user-agent:subject :content-language:to:cc:references:from:organization:in-reply-to :content-transfer-encoding; bh=e4M/zER77Q+ToLMiUbENXoKT6NCsg2bxGWUtg5S8brs=; b=OPPEy9dPvqB73hFATe7IOQJrmuaFLC8Ob1EiIDFh4t4cNPe5MDAqUedb0rmVq30Kjq zgfLs04bUGZWHv6Pi/Wr8WUow1neRNi7kMkJ55tTVNfUUWu0k3T2NhnTrWVUL5v7Dobq xd4TmW0skDCUN/VrjMcMp+U8xJN9OsdPIbcHsyon/LrzsDVOosg+rv5BUJ4kIsgOK8wT fovGg1wAwuXjgLpPrk8P3HGzLeZe/V0UkaczzIv20WnkzKm5SnhEEr4+qGClc7qZo0vz XOyyTW3t7uqaKVI462O9zrn9j7G5jlJ530ruX8IPU1usnf7dggnmWjdLVKl1yhb0O00k KmIA== X-Gm-Message-State: ACgBeo2EfioiHy/b7EM2cwAXWReF3CEawsfvkXi6KGWgpSbL/9fNcuY8 5UpfzkK2Omj+n801pQIMdMQQUQ== X-Google-Smtp-Source: AA6agR5OU4NQg3by3GO4zo8cWs8ys8Xfo3r0M9A4nAjwKkDF7LG9ino/jpGGdAG/1p/iPCAApyBX9A== X-Received: by 2002:ab0:65d6:0:b0:385:f6e1:83ef with SMTP id n22-20020ab065d6000000b00385f6e183efmr8140142uaq.23.1659442491709; Tue, 02 Aug 2022 05:14:51 -0700 (PDT) Received: from ?IPV6:2804:431:c7cb:1e34:a813:f55c:8e00:64cd? ([2804:431:c7cb:1e34:a813:f55c:8e00:64cd]) by smtp.gmail.com with ESMTPSA id 83-20020a1f1256000000b003748499ee4esm7698690vks.44.2022.08.02.05.14.50 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 02 Aug 2022 05:14:51 -0700 (PDT) Message-ID: Date: Tue, 2 Aug 2022 09:14:47 -0300 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:102.0) Gecko/20100101 Thunderbird/102.1.0 Subject: Re: [PATCH v2] stdlib: Simplify arc4random_uniform Content-Language: en-US To: Yann Droneaud , Noah Goldstein Cc: GNU C Library References: <20220729123211.876374-1-adhemerval.zanella@linaro.org> <178c4ebc-7754-e413-7b0d-f2044ceeb27f@opteya.com> From: Adhemerval Zanella Netto Organization: Linaro In-Reply-To: <178c4ebc-7754-e413-7b0d-f2044ceeb27f@opteya.com> Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-11.4 required=5.0 tests=BAYES_00, BODY_8BITS, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, NICE_REPLY_A, 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 12:14:54 -0000 On 02/08/22 09:08, Yann Droneaud wrote: > Hi, > > Le 01/08/2022 à 21:20, Noah Goldstein a écrit : >>> 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 >>> >>>   uint32_t >>>   __arc4random_uniform (uint32_t n) >>>   { >>> @@ -57,83 +38,33 @@ __arc4random_uniform (uint32_t n) >>> +  while (1) >>>       { >>> +      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; >> Can this just be shift by 1 and repeat (32 - z) times or does that >> introduce bias (not seeing exactly why it would)? > > > That was bothering me too, as I was thinking a rotation would be possible instead of shift. > > I posted the question https://crypto.stackexchange.com/questions/101325/uniform-rejection-sampling-by-shifting-or-rotating-bits-from-csprng-output-safe > > The answer: there's indeed a bias. > > This explains why my attempt with rotation leads to dieharder complaining. It was so obvious ... Damn > Thanks, I will remove it then. We might evaluate later if using the mask and compare is indeed better than the other methods (as using by OpenBSD).