001/**
002 *
003 * Licensed to the Apache Software Foundation (ASF) under one
004 * or more contributor license agreements.  See the NOTICE file
005 * distributed with this work for additional information
006 * regarding copyright ownership.  The ASF licenses this file
007 * to you under the Apache License, Version 2.0 (the
008 * "License"); you may not use this file except in compliance
009 * with the License.  You may obtain a copy of the License at
010 *
011 *     http://www.apache.org/licenses/LICENSE-2.0
012 *
013 * Unless required by applicable law or agreed to in writing, software
014 * distributed under the License is distributed on an "AS IS" BASIS,
015 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
016 * See the License for the specific language governing permissions and
017 * limitations under the License.
018 */
019
020package org.apache.hadoop.hbase.util;
021
022import java.util.HashSet;
023import java.util.Random;
024import java.util.Set;
025import java.util.concurrent.atomic.AtomicLong;
026import org.apache.yetus.audience.InterfaceAudience;
027import org.apache.hbase.thirdparty.com.google.common.base.Preconditions;
028
029/**
030 *
031 * An instance of this class is used to generate a stream of
032 * pseudorandom numbers. The class uses a 64-bit seed, which is
033 * modified using a linear congruential formula.
034 *
035 * see https://en.wikipedia.org/wiki/Linear_congruential_generator
036 */
037@InterfaceAudience.Private
038public class Random64 {
039
040  private static final long multiplier = 6364136223846793005L;
041  private static final long addend = 1442695040888963407L;
042
043  private static final AtomicLong seedUniquifier
044        = new AtomicLong(8682522807148012L);
045
046  private long seed;
047
048  /**
049   * Copy from {@link Random#seedUniquifier()}
050   */
051  private static long seedUniquifier() {
052    for (; ; ) {
053      long current = seedUniquifier.get();
054      long next = current * 181783497276652981L;
055      if (seedUniquifier.compareAndSet(current, next)) {
056        return next;
057      }
058    }
059  }
060
061  public Random64() {
062    this(seedUniquifier() ^ System.nanoTime());
063  }
064
065  public Random64(long seed) {
066    this.seed = seed;
067  }
068
069  public long nextLong() {
070    return next64(64);
071  }
072
073  public void nextBytes(byte[] bytes) {
074    for (int i = 0, len = bytes.length; i < len;) {
075      // We regard seed as unsigned long, therefore used '>>>' instead of '>>'.
076      for (long rnd = nextLong(), n = Math.min(len - i, Long.SIZE / Byte.SIZE);
077           n-- > 0; rnd >>>= Byte.SIZE) {
078        bytes[i++] = (byte) rnd;
079      }
080    }
081  }
082
083  private long next64(int bits) {
084    seed = seed * multiplier + addend;
085    return seed >>> (64 - bits);
086  }
087
088
089  /**
090   * Random64 is a pseudorandom algorithm(LCG). Therefore, we will get same sequence
091   * if seeds are the same. This main will test how many calls nextLong() it will
092   * get the same seed.
093   *
094   * We do not need to save all numbers (that is too large). We could save
095   * once every 100000 calls nextLong(). If it get a same seed, we can
096   * detect this by calling nextLong() 100000 times continuously.
097   *
098   */
099  public static void main(String[] args) {
100    long defaultTotalTestCnt = 1000000000000L; // 1 trillion
101
102    if (args.length == 1) {
103      defaultTotalTestCnt = Long.parseLong(args[0]);
104    }
105
106    Preconditions.checkArgument(defaultTotalTestCnt > 0, "totalTestCnt <= 0");
107
108    final int precision = 100000;
109    final long totalTestCnt = defaultTotalTestCnt + precision;
110    final int reportPeriod = 100 * precision;
111    final long startTime = System.currentTimeMillis();
112
113    System.out.println("Do collision test, totalTestCnt=" + totalTestCnt);
114
115    Random64 rand = new Random64();
116    Set<Long> longSet = new HashSet<>();
117
118    for (long cnt = 1; cnt <= totalTestCnt; cnt++) {
119      final long randLong = rand.nextLong();
120
121      if (longSet.contains(randLong)) {
122        System.err.println("Conflict! count=" + cnt);
123        System.exit(1);
124      }
125
126      if (cnt % precision == 0) {
127        if (!longSet.add(randLong)) {
128          System.err.println("Conflict! count=" + cnt);
129          System.exit(1);
130        }
131
132        if (cnt % reportPeriod == 0) {
133          long cost = System.currentTimeMillis() - startTime;
134          long remainingMs = (long) (1.0 * (totalTestCnt - cnt) * cost / cnt);
135          System.out.println(
136            String.format(
137              "Progress: %.3f%%, remaining %d minutes",
138              100.0 * cnt / totalTestCnt, remainingMs / 60000
139            )
140          );
141        }
142      }
143
144    }
145
146    System.out.println("No collision!");
147  }
148
149}