Repository: commons-rng Updated Branches: refs/heads/master 2f0a3e4ff -> c0b975767
RNG-56: Missing statements in least used branch entail infinite loop. Loop was replaced by recursion that would raise "StackOverFlow" error, rather than run forever in case of a bad RNG implementation. Project: http://git-wip-us.apache.org/repos/asf/commons-rng/repo Commit: http://git-wip-us.apache.org/repos/asf/commons-rng/commit/4f92fa2b Tree: http://git-wip-us.apache.org/repos/asf/commons-rng/tree/4f92fa2b Diff: http://git-wip-us.apache.org/repos/asf/commons-rng/diff/4f92fa2b Branch: refs/heads/master Commit: 4f92fa2b6db0f533810d3ec9efcd2f31d58dc041 Parents: 74c2b58 Author: Gilles <er...@apache.org> Authored: Fri Aug 24 18:11:57 2018 +0200 Committer: Gilles <er...@apache.org> Committed: Fri Aug 24 18:11:57 2018 +0200 ---------------------------------------------------------------------- .../ZigguratNormalizedGaussianSampler.java | 38 ++++++++-------- .../ZigguratNormalizedGaussianSamplerTest.java | 48 ++++++++++++++++++++ src/changes/changes.xml | 3 ++ 3 files changed, 70 insertions(+), 19 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/commons-rng/blob/4f92fa2b/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/distribution/ZigguratNormalizedGaussianSampler.java ---------------------------------------------------------------------- diff --git a/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/distribution/ZigguratNormalizedGaussianSampler.java b/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/distribution/ZigguratNormalizedGaussianSampler.java index b52c926..48d4342 100644 --- a/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/distribution/ZigguratNormalizedGaussianSampler.java +++ b/commons-rng-sampling/src/main/java/org/apache/commons/rng/sampling/distribution/ZigguratNormalizedGaussianSampler.java @@ -122,27 +122,27 @@ public class ZigguratNormalizedGaussianSampler double x; double y; - while (true) { - x = hz * W[iz]; - if (iz == 0) { - // Base strip. - do { - y = -Math.log(rng.nextDouble()); - x = -Math.log(rng.nextDouble()) * ONE_OVER_R; - } while (y + y < x * x); - - final double out = R + x; - return hz > 0 ? out : -out; + x = hz * W[iz]; + if (iz == 0) { + // Base strip. + do { + y = -Math.log(rng.nextDouble()); + x = -Math.log(rng.nextDouble()) * ONE_OVER_R; + } while (y + y < x * x); + + final double out = R + x; + return hz > 0 ? out : -out; + } else { + // Wedge of other strips. + if (F[iz] + rng.nextDouble() * (F[iz - 1] - F[iz]) < gauss(x)) { + return x; } else { - // Wedge of other strips. - if (F[iz] + rng.nextDouble() * (F[iz - 1] - F[iz]) < gauss(x)) { - return x; + final long hzNew = rng.nextLong(); + final int izNew = (int) (hzNew & LAST); + if (Math.abs(hzNew) < K[izNew]) { + return hzNew * W[izNew]; } else { - final long hzNew = rng.nextLong(); - final int izNew = (int) (hzNew & LAST); - if (Math.abs(hzNew) < K[izNew]) { - return hzNew * W[izNew]; - } + return fix(hzNew, izNew); } } } http://git-wip-us.apache.org/repos/asf/commons-rng/blob/4f92fa2b/commons-rng-sampling/src/test/java/org/apache/commons/rng/sampling/distribution/ZigguratNormalizedGaussianSamplerTest.java ---------------------------------------------------------------------- diff --git a/commons-rng-sampling/src/test/java/org/apache/commons/rng/sampling/distribution/ZigguratNormalizedGaussianSamplerTest.java b/commons-rng-sampling/src/test/java/org/apache/commons/rng/sampling/distribution/ZigguratNormalizedGaussianSamplerTest.java new file mode 100644 index 0000000..ebeea5b --- /dev/null +++ b/commons-rng-sampling/src/test/java/org/apache/commons/rng/sampling/distribution/ZigguratNormalizedGaussianSamplerTest.java @@ -0,0 +1,48 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.rng.sampling.distribution; + +import org.junit.Assert; +import org.junit.Test; +import org.apache.commons.rng.simple.RandomSource; +import org.apache.commons.rng.UniformRandomProvider; + +/** + * Test for {@link ZigguratNormalizedGaussianSampler}. + */ +public class ZigguratNormalizedGaussianSamplerTest { + // Cf. RNG-56 + @Test(expected = StackOverflowError.class) + public void testInfiniteLoop() { + // A bad implementation whose only purpose is to force access + // to the rarest branch. + final UniformRandomProvider bad = new UniformRandomProvider() { + public long nextLong(long n) { return 0; } + public long nextLong() { return Long.MAX_VALUE; } + public int nextInt(int n) { return 0; } + public int nextInt() { return Integer.MAX_VALUE; } + public float nextFloat() { return 1; } + public double nextDouble() { return 1;} + public void nextBytes(byte[] bytes, int start, int len) {} + public void nextBytes(byte[] bytes) {} + public boolean nextBoolean() { return false; } + }; + + // Infinite loop (in v1.1). + new ZigguratNormalizedGaussianSampler(bad).sample(); + } +} http://git-wip-us.apache.org/repos/asf/commons-rng/blob/4f92fa2b/src/changes/changes.xml ---------------------------------------------------------------------- diff --git a/src/changes/changes.xml b/src/changes/changes.xml index bbb9893..f161dcd 100644 --- a/src/changes/changes.xml +++ b/src/changes/changes.xml @@ -67,6 +67,9 @@ Additional code is provided in the following module: It is however not part of the official API and no compatibility should be expected in subsequent releases. "> + <action dev="erans" type="fix" issue="RNG-56"> + "ZigguratNormalizedGaussianSampler": Missing statements in least used branch. + </action> <action dev="erans" type="fix" issue="RNG-55" due-to="Alex D. Herbert"> "UnitSphereSampler": Prevent returning NaN components and forbid negative dimension.
