From patchwork Fri Jul 31 15:54:00 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?q?Alex_Benn=C3=A9e?= X-Patchwork-Id: 51793 Return-Path: X-Original-To: linaro@patches.linaro.org Delivered-To: linaro@patches.linaro.org Received: from mail-la0-f71.google.com (mail-la0-f71.google.com [209.85.215.71]) by patches.linaro.org (Postfix) with ESMTPS id B3F0822A8D for ; Fri, 31 Jul 2015 16:04:22 +0000 (UTC) Received: by labby2 with SMTP id by2sf7050704lab.3 for ; Fri, 31 Jul 2015 09:04:21 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:delivered-to:from:to:date:message-id:in-reply-to :references:mime-version:content-type:content-transfer-encoding:cc :subject:precedence:list-id:list-unsubscribe:list-archive:list-post :list-help:list-subscribe:errors-to:sender:x-original-sender :x-original-authentication-results:mailing-list; bh=mxgdcvpZE5stY4WkEIm8Gj/7aO1eqOuP2O7HeSEWKDI=; b=c3D/xluxyBDWyQtfpjGigjTPCnmbHNr3YXrJQRWy0WQgCZgla84re8fbvJWaHBiZlG SO4QizwpwB7fJVhKjyaVTuIG1fxtGfW+9+D0OC+7c6KCtxcZljIAiIk3YGhtTDa3VcSv +aT1xAUr/zrxD/9c343aT8AO6p4KKHdcMWQHVzv6F/DqMHeY8Dhi/QU17W+mQoiq5my7 nBxi4Z4TLa3JyHjZSL24tcz4wjgUPhhHMRfY3Ey/vVIiMYvE+tDcK3dQFimdApSW8M67 HfJKxOEAGuGfqrbjwe+2HIczXYyzTT+64t5jlWxfn1FJvZKA5ivps21kuzhC3zzke9dy kOUg== X-Gm-Message-State: ALoCoQkMZA2rCYHMZrDgzAjk9c9BQXwdTm00oasD1uGUrF8JUI3q/24Jq0/o7HjOO9cpLZuC4fbM X-Received: by 10.152.87.46 with SMTP id u14mr1150307laz.5.1438358661641; Fri, 31 Jul 2015 09:04:21 -0700 (PDT) X-BeenThere: patchwork-forward@linaro.org Received: by 10.152.205.107 with SMTP id lf11ls339732lac.40.gmail; Fri, 31 Jul 2015 09:04:21 -0700 (PDT) X-Received: by 10.112.40.66 with SMTP id v2mr3810050lbk.27.1438358661351; Fri, 31 Jul 2015 09:04:21 -0700 (PDT) Received: from mail-la0-f42.google.com (mail-la0-f42.google.com. [209.85.215.42]) by mx.google.com with ESMTPS id v8si4126243laj.130.2015.07.31.09.04.21 for (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 31 Jul 2015 09:04:21 -0700 (PDT) Received-SPF: pass (google.com: domain of patch+caf_=patchwork-forward=linaro.org@linaro.org designates 209.85.215.42 as permitted sender) client-ip=209.85.215.42; Received: by labiq1 with SMTP id iq1so12369190lab.3 for ; Fri, 31 Jul 2015 09:04:21 -0700 (PDT) X-Received: by 10.112.166.2 with SMTP id zc2mr3771918lbb.29.1438358660863; Fri, 31 Jul 2015 09:04:20 -0700 (PDT) X-Forwarded-To: patchwork-forward@linaro.org X-Forwarded-For: patch@linaro.org patchwork-forward@linaro.org Delivered-To: patch@linaro.org Received: by 10.112.7.198 with SMTP id l6csp477647lba; Fri, 31 Jul 2015 09:04:19 -0700 (PDT) X-Received: by 10.55.22.169 with SMTP id 41mr5515396qkw.13.1438358659321; Fri, 31 Jul 2015 09:04:19 -0700 (PDT) Received: from lists.gnu.org (lists.gnu.org. [2001:4830:134:3::11]) by mx.google.com with ESMTPS id b85si6353550qkh.108.2015.07.31.09.04.18 for (version=TLSv1 cipher=RC4-SHA bits=128/128); Fri, 31 Jul 2015 09:04:19 -0700 (PDT) Received-SPF: pass (google.com: domain of qemu-devel-bounces+patch=linaro.org@nongnu.org designates 2001:4830:134:3::11 as permitted sender) client-ip=2001:4830:134:3::11; Received: from localhost ([::1]:45029 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZLCnC-0001xO-2W for patch@linaro.org; Fri, 31 Jul 2015 12:04:18 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:36090) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZLCdw-00018S-00 for qemu-devel@nongnu.org; Fri, 31 Jul 2015 11:54:50 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1ZLCdm-0005wn-KS for qemu-devel@nongnu.org; Fri, 31 Jul 2015 11:54:43 -0400 Received: from mail-wi0-f181.google.com ([209.85.212.181]:34749) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ZLCdm-0005wj-CN for qemu-devel@nongnu.org; Fri, 31 Jul 2015 11:54:34 -0400 Received: by wibud3 with SMTP id ud3so63501719wib.1 for ; Fri, 31 Jul 2015 08:54:33 -0700 (PDT) X-Received: by 10.194.121.131 with SMTP id lk3mr6926823wjb.77.1438358073519; Fri, 31 Jul 2015 08:54:33 -0700 (PDT) Received: from zen.linaro.local ([81.128.185.34]) by smtp.gmail.com with ESMTPSA id lz10sm7762544wjb.48.2015.07.31.08.54.32 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 31 Jul 2015 08:54:32 -0700 (PDT) Received: from zen.linaroharston (localhost [127.0.0.1]) by zen.linaro.local (Postfix) with ESMTP id 771283E139A; Fri, 31 Jul 2015 16:54:23 +0100 (BST) From: =?UTF-8?q?Alex=20Benn=C3=A9e?= To: mttcg@listserver.greensocs.com, mark.burton@greensocs.com, fred.konrad@greensocs.com Date: Fri, 31 Jul 2015 16:54:00 +0100 Message-Id: <1438358041-18021-11-git-send-email-alex.bennee@linaro.org> X-Mailer: git-send-email 2.5.0 In-Reply-To: <1438358041-18021-1-git-send-email-alex.bennee@linaro.org> References: <1438358041-18021-1-git-send-email-alex.bennee@linaro.org> MIME-Version: 1.0 X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] [fuzzy] X-Received-From: 209.85.212.181 Cc: peter.maydell@linaro.org, drjones@redhat.com, kvm@vger.kernel.org, a.spyridakis@virtualopensystems.com, claudio.fontana@huawei.com, a.rigo@virtualopensystems.com, qemu-devel@nongnu.org, =?UTF-8?q?Alex=20Benn=C3=A9e?= , "Timothy B. Terriberry" Subject: [Qemu-devel] [kvm-unit-tests PATCH v5 10/11] new: add isaac prng library from CCAN X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: , List-Help: , List-Subscribe: , Errors-To: qemu-devel-bounces+patch=linaro.org@nongnu.org Sender: qemu-devel-bounces+patch=linaro.org@nongnu.org X-Removed-Original-Auth: Dkim didn't pass. X-Original-Sender: alex.bennee@linaro.org X-Original-Authentication-Results: mx.google.com; spf=pass (google.com: domain of patch+caf_=patchwork-forward=linaro.org@linaro.org designates 209.85.215.42 as permitted sender) smtp.mail=patch+caf_=patchwork-forward=linaro.org@linaro.org Mailing-list: list patchwork-forward@linaro.org; contact patchwork-forward+owners@linaro.org X-Google-Group-Id: 836684582541 It's often useful to introduce some sort of random variation when testing several racing CPU conditions. Instead of each test implementing some half-arsed PRNG bring in a a decent one which has good statistical randomness. Obviously it is deterministic for a given seed value which is likely the behaviour you want. I've pulled in the ISAAC library from CCAN: http://ccodearchive.net/info/isaac.html I shaved off the float related stuff which is less useful for unit testing and re-indented to fit the style. The original license was CC0 (Public Domain) which is compatible with the LGPL v2 of kvm-unit-tests. Signed-off-by: Alex Bennée CC: Timothy B. Terriberry --- config/config-arm-common.mak | 1 + lib/prng.c | 162 +++++++++++++++++++++++++++++++++++++++++++ lib/prng.h | 82 ++++++++++++++++++++++ 3 files changed, 245 insertions(+) create mode 100644 lib/prng.c create mode 100644 lib/prng.h diff --git a/config/config-arm-common.mak b/config/config-arm-common.mak index 9c7607b..67a9dda 100644 --- a/config/config-arm-common.mak +++ b/config/config-arm-common.mak @@ -34,6 +34,7 @@ cflatobjs += lib/devicetree.o cflatobjs += lib/virtio.o cflatobjs += lib/virtio-mmio.o cflatobjs += lib/chr-testdev.o +cflatobjs += lib/prng.o cflatobjs += lib/arm/io.o cflatobjs += lib/arm/setup.o cflatobjs += lib/arm/mmu.o diff --git a/lib/prng.c b/lib/prng.c new file mode 100644 index 0000000..ebd6df7 --- /dev/null +++ b/lib/prng.c @@ -0,0 +1,162 @@ +/* + * Pseudo Random Number Generator + * + * Lifted from ccan modules ilog/isaac under CC0 + * - http://ccodearchive.net/info/isaac.html + * - http://ccodearchive.net/info/ilog.html + * + * And lightly hacked to compile under the KVM unit test environment. + * This provides a handy RNG for torture tests that want to vary + * delays and the like. + * + */ + +/*Written by Timothy B. Terriberry (tterribe@xiph.org) 1999-2009. + CC0 (Public domain) - see LICENSE file for details + Based on the public domain implementation by Robert J. Jenkins Jr.*/ + +#include "libcflat.h" + +#include +#include "prng.h" + +#define ISAAC_MASK (0xFFFFFFFFU) + +/* Extract ISAAC_SZ_LOG bits (starting at bit 2). */ +static inline uint32_t lower_bits(uint32_t x) +{ + return (x & ((ISAAC_SZ-1) << 2)) >> 2; +} + +/* Extract next ISAAC_SZ_LOG bits (starting at bit ISAAC_SZ_LOG+2). */ +static inline uint32_t upper_bits(uint32_t y) +{ + return (y >> (ISAAC_SZ_LOG+2)) & (ISAAC_SZ-1); +} + +static void isaac_update(isaac_ctx *_ctx){ + uint32_t *m; + uint32_t *r; + uint32_t a; + uint32_t b; + uint32_t x; + uint32_t y; + int i; + m=_ctx->m; + r=_ctx->r; + a=_ctx->a; + b=_ctx->b+(++_ctx->c); + for(i=0;i>6)+m[i+ISAAC_SZ/2]; + m[i]=y=m[lower_bits(x)]+a+b; + r[i]=b=m[upper_bits(y)]+x; + x=m[++i]; + a=(a^a<<2)+m[i+ISAAC_SZ/2]; + m[i]=y=m[lower_bits(x)]+a+b; + r[i]=b=m[upper_bits(y)]+x; + x=m[++i]; + a=(a^a>>16)+m[i+ISAAC_SZ/2]; + m[i]=y=m[lower_bits(x)]+a+b; + r[i]=b=m[upper_bits(y)]+x; + } + for(i=ISAAC_SZ/2;i>6)+m[i-ISAAC_SZ/2]; + m[i]=y=m[lower_bits(x)]+a+b; + r[i]=b=m[upper_bits(y)]+x; + x=m[++i]; + a=(a^a<<2)+m[i-ISAAC_SZ/2]; + m[i]=y=m[lower_bits(x)]+a+b; + r[i]=b=m[upper_bits(y)]+x; + x=m[++i]; + a=(a^a>>16)+m[i-ISAAC_SZ/2]; + m[i]=y=m[lower_bits(x)]+a+b; + r[i]=b=m[upper_bits(y)]+x; + } + _ctx->b=b; + _ctx->a=a; + _ctx->n=ISAAC_SZ; +} + +static void isaac_mix(uint32_t _x[8]){ + static const unsigned char SHIFT[8]={11,2,8,16,10,4,8,9}; + int i; + for(i=0;i<8;i++){ + _x[i]^=_x[(i+1)&7]<>SHIFT[i]; + _x[(i+3)&7]+=_x[i]; + _x[(i+1)&7]+=_x[(i+2)&7]; + } +} + + +void isaac_init(isaac_ctx *_ctx,const unsigned char *_seed,int _nseed){ + _ctx->a=_ctx->b=_ctx->c=0; + memset(_ctx->r,0,sizeof(_ctx->r)); + isaac_reseed(_ctx,_seed,_nseed); +} + +void isaac_reseed(isaac_ctx *_ctx,const unsigned char *_seed,int _nseed){ + uint32_t *m; + uint32_t *r; + uint32_t x[8]; + int i; + int j; + m=_ctx->m; + r=_ctx->r; + if(_nseed>ISAAC_SEED_SZ_MAX)_nseed=ISAAC_SEED_SZ_MAX; + for(i=0;i<_nseed>>2;i++){ + r[i]^=(uint32_t)_seed[i<<2|3]<<24|(uint32_t)_seed[i<<2|2]<<16| + (uint32_t)_seed[i<<2|1]<<8|_seed[i<<2]; + } + _nseed-=i<<2; + if(_nseed>0){ + uint32_t ri; + ri=_seed[i<<2]; + for(j=1;j<_nseed;j++)ri|=(uint32_t)_seed[i<<2|j]<<(j<<3); + r[i++]^=ri; + } + x[0]=x[1]=x[2]=x[3]=x[4]=x[5]=x[6]=x[7]=0x9E3779B9U; + for(i=0;i<4;i++)isaac_mix(x); + for(i=0;in)isaac_update(_ctx); + return _ctx->r[--_ctx->n]; +} + +uint32_t isaac_next_uint(isaac_ctx *_ctx,uint32_t _n){ + uint32_t r; + uint32_t v; + uint32_t d; + do{ + r=isaac_next_uint32(_ctx); + v=r%_n; + d=r-v; + } + while(((d+_n-1)&ISAAC_MASK) + + + +typedef struct isaac_ctx isaac_ctx; + + + +/*This value may be lowered to reduce memory usage on embedded platforms, at + the cost of reducing security and increasing bias. + Quoting Bob Jenkins: "The current best guess is that bias is detectable after + 2**37 values for [ISAAC_SZ_LOG]=3, 2**45 for 4, 2**53 for 5, 2**61 for 6, + 2**69 for 7, and 2**77 values for [ISAAC_SZ_LOG]=8."*/ +#define ISAAC_SZ_LOG (8) +#define ISAAC_SZ (1<