From patchwork Sat Dec 31 02:36:54 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Alejandro Colomar X-Patchwork-Id: 62495 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 C126F3858C30 for ; Sat, 31 Dec 2022 02:43:01 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org C126F3858C30 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1672454581; bh=zwcO6LBVkVX2gO/HOcIgzjpUquFecuYM4KWnfgah3/U=; h=To:Cc:Subject:Date:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:List-Subscribe:From:Reply-To:From; b=F0b3kqtrZJpYcd/8v/2ED7GwnmRWR89AjaiNTYeRfU3NUvfxuuPCar2afFwTQkkPP pvO+R3w8YFoR5NPt/sT0RF5nKkN03BBaHufV9zB1r5ofCsuZ9Cv7/3lA/t6+PoC+t5 pUFXhQTP5bpyDsnP8cYAw0Vxq+ODr5GzpWA2Zi0g= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-wm1-x32f.google.com (mail-wm1-x32f.google.com [IPv6:2a00:1450:4864:20::32f]) by sourceware.org (Postfix) with ESMTPS id 1AE143858D1E for ; Sat, 31 Dec 2022 02:42:39 +0000 (GMT) Received: by mail-wm1-x32f.google.com with SMTP id o15so16498048wmr.4 for ; Fri, 30 Dec 2022 18:42:39 -0800 (PST) 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:subject:date:message-id :reply-to; bh=zwcO6LBVkVX2gO/HOcIgzjpUquFecuYM4KWnfgah3/U=; b=gPplYSyrCfiVkhlCbUB6fVAdstDPNgxQROq8RKmnUGVwaFLbusTa784El2LGulgE04 vVHbohzFNAjq9gvy69U+1n4yQq/B5p1GXFaJfhPpJS9vYKgY0R3rrK64ReUdkO//Mrju n+ibD7E5UyjfcCppQguulH0n/SWSDncyuzfCima8DAOjGbCbWuc8ErXSflIZjoOtOYQf bAHMe3V0FCa0OymMnoB/cNuWDB0yG0UHbajeqFJ2SSHFSQzgLg6fXIE/Xfn2BpUZZrr0 VnsjZVCpAbTifUI7d/wSEut6Oa1uMWddOVOVaE5A+Is1C9jv/kWb5QDHH90958aS1MTY vVtQ== X-Gm-Message-State: AFqh2kqFvQxjdqComwxrJCDCyW83g4izIFJydU+KQvQN8NE1PRMSQAHH gdbT5HjZnamQIdB9KWqFlBQI1d2Y+cY= X-Google-Smtp-Source: AMrXdXsFXH8z6Ul9PwAIHK3FVpHGfeIU5RectnD1Ln9u2L9oIZbesHX7/HxHknJYD3aBPxLIsNF70A== X-Received: by 2002:a05:600c:1da3:b0:3d3:4dbc:75ef with SMTP id p35-20020a05600c1da300b003d34dbc75efmr23874782wms.17.1672454557624; Fri, 30 Dec 2022 18:42:37 -0800 (PST) Received: from asus5775.alejandro-colomar.es ([170.253.36.171]) by smtp.googlemail.com with ESMTPSA id hg15-20020a05600c538f00b003d971a6c513sm25618172wmb.25.2022.12.30.18.42.36 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 30 Dec 2022 18:42:37 -0800 (PST) X-Google-Original-From: Alejandro Colomar To: libc-alpha@sourceware.org Cc: Alejandro Colomar , Theo de Raadt , "Todd C . Miller" , "Jason A. Donenfeld" , =?utf-8?q?Cristian_Rodr=C3=ADguez?= , Adhemerval Zanella , Yann Droneaud , Joseph Myers Subject: [PATCH] Give a useful meaning to arc4random_uniform(0); Date: Sat, 31 Dec 2022 03:36:54 +0100 Message-Id: <20221231023653.41877-1-alx@kernel.org> X-Mailer: git-send-email 2.39.0 MIME-Version: 1.0 X-Developer-Signature: v=1; a=openpgp-sha256; l=2293; i=alx@kernel.org; h=from:subject; bh=536kracrEvP3A/moH6lq0u2vlsFJpTt4bJWvkK4Ct5s=; b=owEBbQKS/ZANAwAKAZ6MGvu+/9syAcsmYgBjr6A8nmuN60JQl802zexCZvb7izgx+VorxUDJ/IlP XvPyLO2JAjMEAAEKAB0WIQTqOofwpOugMORd8kCejBr7vv/bMgUCY6+gPAAKCRCejBr7vv/bMpqvEA CSpz7x+sk+qFHbDPz5OWywOqmGdUCXYHJLtvFRnQ2f1epsNL9/43TbIMtgtyAS+VKEj+ZMOM9u7Rxq 6oK9ZKOZ8SaVJDZYUnjLzks5+uwxui/H0q8xUNF57WeOi612i8YN6JSduU38AMvxBCbNd8RLbMByqO vUFnp9W2zslsmIVouknaS2ZcnVeuz370AJa0jvXZ0JdeGAZex/LhKjMr6pJZSf4FKz9AsoJ+4C2sar +S4ZlxZAWd7KOym9OOpPACOPJvjoso115MTGWqXDN8lTn2q18pKcPhfkcxas1BeI52wu8T4azw0WsH 4aHT5AMZT5Ksj75FWeprEGrsYKBuPNLJtN7Dh1aWcPqcMdMJPTQpND/2JNRxl2OWnGMASeKBx4lLFe Updu3swQ8+a2DNIQGgVMvO3RCe6XWPOvQ+mab3q2e6j8euQFPIuW/1uu5uuCrKIeSNhCBt/gZvJum8 hnSPyyDt4kgOIwwNGHPaGucUbQnOCjLv0/ir77jGzrJK91fg3chz6i/nyWXyvf58tyygooDRzjVwC0 +3LIOGd552O2IWqo8mJAMZMcEbYH+lTB7hTgCIuhG37BhFaTiJRY/JOHunFtckEmMVeKQV2IjKIY3a bo8Auxzg7OxRGtOqcrKyAYXFLV0rlml8TydJKUWcd5Rx016vzdu8qwTLg2Yg== X-Developer-Key: i=alx@kernel.org; a=openpgp; fpr=A9348594CE31283A826FBDD8D57633D441E25BB5 X-Spam-Status: No, score=-10.5 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, 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: Alejandro Colomar via Libc-alpha From: Alejandro Colomar Reply-To: Alejandro Colomar Errors-To: libc-alpha-bounces+patchwork=sourceware.org@sourceware.org Sender: "Libc-alpha" Special-casing it in the implementation to return 0 was useless. Instead, considering 0 as the value after UINT32_MAX has the property that it allows implementing the following function without any special cases: uint32_t arc4random_range(uint32_t min, uint32_t max) { return arc4random_uniform(max - min + 1) + min; } This works for any values of min and max (as long as min <= max, of course), even for (0, UINT32_MAX). Oh, and the implementation of arc4random_uniform(3) is now 2 lines simpler. :) This will work with the current implementation because powerof2(3) will also consider 0 as a power of 2. See powerof2(3): SYNOPSIS #include int powerof2(x); DESCRIPTION This macro returns true if x is a power of 2, and false otherwise. 0 is considered a power of 2. This can make sense con‐ sidering wrapping of unsigned integers, and has interest‐ ing properties. Cc: Theo de Raadt Cc: Todd C. Miller Cc: "Jason A. Donenfeld" Cc: Cristian Rodríguez Cc: Adhemerval Zanella Cc: Yann Droneaud Cc: Joseph Myers Signed-off-by: Alejandro Colomar --- Hi, I CCd Theo and Todd, because theirs is the original implementation, and while this is a useful feature (IMO), it wouldn't make sense to do it without consensus with other implementations, and especially with the original implementation. I found this useful for shadow, where the existing code had a function that produced a "random" value within a range, but due to the bogus implementation, it had bias for higher values. Implementing a *_range() variant in terms of *_uniform() made it really simple, but the *_uniform() function needed to do something useful for 0 for that to work. Cheers, Alex stdlib/arc4random_uniform.c | 10 ++++------ 1 file changed, 4 insertions(+), 6 deletions(-) diff --git a/stdlib/arc4random_uniform.c b/stdlib/arc4random_uniform.c index 5aa98d1c13..1cd52c0d1c 100644 --- a/stdlib/arc4random_uniform.c +++ b/stdlib/arc4random_uniform.c @@ -29,15 +29,13 @@ the asked range after range adjustment. The algorithm avoids modulo and divide operations, which might be costly - depending on the architecture. */ + depending on the architecture. + + 0 is treated as if it were UINT32_MAX + 1, and so arc4random_uniform(0) + is equivalent to arc4random(). */ uint32_t __arc4random_uniform (uint32_t n) { - if (n <= 1) - /* There is no valid return value for a zero limit, and 0 is the - only possible result for limit 1. */ - return 0; - /* Powers of two are easy. */ if (powerof2 (n)) return __arc4random () & (n - 1);