package org.softwareheritage.graph.utils;
import it.unimi.dsi.big.webgraph.LazyLongIterator;
import java.util.Random;
/** A Linear Feedback Shift Register
*
* Generates a random uniform permutation of [0, n] as a *stream* that takes O(1) space.
* Because the entire state is a single long integer,
*
* https://en.wikipedia.org/wiki/Linear-feedback_shift_register
* https://stackoverflow.com/a/32193751
* https://www.uobabylon.edu.iq/eprints/paper_1_17528_649.pdf
* http://users.ece.cmu.edu/~koopman/lfsr/
* https://docs.xilinx.com/v/u/en-US/xapp052
*/
public class LinearFeedbackShiftRegister implements LazyLongIterator {
private final long n;
private long state;
private final int numBits;
public LinearFeedbackShiftRegister(long n, long seed) {
if (n <= 0) {
throw new RuntimeException("n must be >= 0");
}
this.n = n;
this.state = (seed % n) + 1;
this.numBits = ((int) (Math.log(n) / Math.log(2))) + 1;
}
public LinearFeedbackShiftRegister(long n) {
this(n, (new Random()).nextLong());
}
@Override
public long nextLong() {
do {
long bits = state;
for (int s : SHIFT_AMT[numBits]) {
bits ^= (state >> s);
}
state = ((state >> 1) | ((bits & 1) << (numBits - 1)));
} while (state > n);
return state - 1;
}
@Override
public long skip(long l) {
long i = 0;
while (i < l && nextLong() != -1)
i++;
return i;
}
/** Maximal Length LFSR Feedback Terms (coefficients of primitive polynomials) for each bit length */
private static final int[][] SHIFT_AMT = new int[][] {
// Taps taken from https://docs.xilinx.com/v/u/en-US/xapp052
// For each k, numBits - k is the coefficient of the primitive polynomial. numBits is also a coefficient.
// Example: for numBits = 16, the array contains 1, 3, 12, which means the coefficients are:
// {16, 16 - 1, 16 - 3, 16 - 12} = {16, 15, 13, 4}
//
// p = [l.strip().split() for l in open('lol').readlines()]
// p = [(int(l[0]), list(map(int, l[1].split(',')))) for l in p]
// p = [[l[0] - x for x in l[1]] for l in p]
new int[]{},
new int[]{1},
new int[]{1},
new int[]{1},
new int[]{1},
new int[]{2},
new int[]{1},
new int[]{1},
new int[]{2, 3, 4},
new int[]{4},
new int[]{3},
new int[]{2},
new int[]{6, 8, 11},
new int[]{9, 10, 12},
new int[]{9, 11, 13},
new int[]{1},
new int[]{1, 3, 12},
new int[]{3},
new int[]{7},
new int[]{13, 17, 18},
new int[]{3},
new int[]{2},
new int[]{1},
new int[]{5},
new int[]{1, 2, 7},
new int[]{3},
new int[]{20, 24, 25},
new int[]{22, 25, 26},
new int[]{3},
new int[]{2},
new int[]{24, 26, 29},
new int[]{3},
new int[]{10, 30, 31},
new int[]{13},
new int[]{7, 32, 33},
new int[]{2},
new int[]{11},
new int[]{32, 33, 34, 35, 36},
new int[]{32, 33, 37},
new int[]{4},
new int[]{2, 19, 21},
new int[]{3},
new int[]{1, 22, 23},
new int[]{1, 5, 6},
new int[]{1, 26, 27},
new int[]{1, 3, 4},
new int[]{1, 20, 21},
new int[]{5},
new int[]{1, 27, 28},
new int[]{9},
new int[]{1, 26, 27},
new int[]{1, 15, 16},
new int[]{3},
new int[]{1, 15, 16},
new int[]{1, 36, 37},
new int[]{24},
new int[]{1, 21, 22},
new int[]{7},
new int[]{19},
new int[]{1, 21, 22},
new int[]{1},
new int[]{1, 15, 16},
new int[]{1, 56, 57},
new int[]{1},
new int[]{1, 3, 4},
};
}