1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.lang3;
18
19 import java.util.Objects;
20 import java.util.Random;
21
22 /**
23 * Generates random integers of specific bit length.
24 *
25 * <p>
26 * It is more efficient than calling Random.nextInt(1 << nbBits). It uses a cache of cacheSize random bytes that it replenishes when it gets empty. This is
27 * especially beneficial for SecureRandom Drbg implementations, which incur a constant cost at each randomness generation.
28 * </p>
29 *
30 * <p>
31 * Used internally by RandomStringUtils.
32 * </p>
33 *
34 * <p>
35 * #NotThreadSafe#
36 * </p>
37 */
38 final class CachedRandomBits {
39
40 private final Random random;
41
42 private final byte[] cache;
43
44 /**
45 * Index of the next bit in the cache to be used.
46 *
47 * <ul>
48 * <li>bitIndex=0 means the cache is fully random and none of the bits have been used yet.</li>
49 * <li>bitIndex=1 means that only the LSB of cache[0] has been used and all other bits can be used.</li>
50 * <li>bitIndex=8 means that only the 8 bits of cache[0] has been used.</li>
51 * </ul>
52 */
53 private int bitIndex;
54
55 /**
56 * Creates a new instance.
57 *
58 * @param cacheSize number of bytes cached (only affects performance)
59 * @param random random source
60 */
61 CachedRandomBits(final int cacheSize, final Random random) {
62 if (cacheSize <= 0) {
63 throw new IllegalArgumentException("cacheSize must be positive");
64 }
65 this.cache = new byte[cacheSize];
66 this.random = Objects.requireNonNull(random, "random");
67 this.random.nextBytes(this.cache);
68 this.bitIndex = 0;
69 }
70
71 /**
72 * Generates a random integer with the specified number of bits.
73 *
74 * @param bits number of bits to generate, MUST be between 1 and 32
75 * @return random integer with {@code bits} bits
76 */
77 public int nextBits(final int bits) {
78 if (bits > 32 || bits <= 0) {
79 throw new IllegalArgumentException("number of bits must be between 1 and 32");
80 }
81 int result = 0;
82 int generatedBits = 0; // number of generated bits up to now
83 while (generatedBits < bits) {
84 if (bitIndex >> 3 >= cache.length) {
85 // we exhausted the number of bits in the cache
86 // this should only happen if the bitIndex is exactly matching the cache length
87 assert bitIndex == cache.length * 8;
88 random.nextBytes(cache);
89 bitIndex = 0;
90 }
91 // generatedBitsInIteration is the number of bits that we will generate
92 // in this iteration of the while loop
93 int generatedBitsInIteration = Math.min(8 - (bitIndex & 0x7), bits - generatedBits);
94 result = result << generatedBitsInIteration;
95 result |= (cache[bitIndex >> 3] >> (bitIndex & 0x7)) & ((1 << generatedBitsInIteration) - 1);
96 generatedBits += generatedBitsInIteration;
97 bitIndex += generatedBitsInIteration;
98 }
99 return result;
100 }
101 }