summaryrefslogtreecommitdiff
path: root/lib/lfsr.h
AgeCommit message (Collapse)Author
2019-04-17rand: fix truncated rand_seed on WindowsMing-Hung Tsai
The long data type is 32-bit on LLP64 platforms
2014-11-23lfsr: don't pass in last value to lfsr_next()Jens Axboe
It's cached in the 'fl' struct. This means we can move the max block calculation outside if the lfsr part, too. Signed-off-by: Jens Axboe <axboe@fb.com>
2013-03-12lfsr: fix verification and spin bugsAlex Pyrgiotis
Changes: 1. Verification now works properly and reports for which value it fails 2. Fix a mishandling of spin incrementation which led to multiple calculation of the same values Signed-off-by: Alex Pyrgiotis <apyrgio@grnet.gr> Signed-off-by: Jens Axboe <axboe@kernel.dk>
2013-03-08Improve LFSR implementationAlex Pyrgiotis
Changes: 1. Use Galois LFSR instead of Fibonacci LFSR. 2. Use XNOR gates instead of XOR gates. 3. Add tap sizes for LFSRs ranging from 3-bits to 15-bits. 4. Add spin parameter. Rationale: 1. Fibonacci LFSRs have the following drawbacks: a. Their next state can not be computed in one cycle, since the input bit must be propagated serially through the XOR gates. Galois LFSRs however, can be computed instantly with XOR-masks. b. Their state changes cannot be considered "irregular", even by I/O standards. Actually, if the current state of an n-bit LFSR is x, then the next will either be (x >> 1) or (2^n + (x >> 1)). Galois LFSRs have instead their XOR gates interleaved with their bits, which means that the inner bits are changed as well, besides of the shifting. If the number of taps is z, this means that the different outcomes are 2^(z + 1). 2. An LFSR with XOR gates has the all-zeroes state as illegal. Since zero is valid for most I/O operations, it would be more intuitive to use XNOR gates, that have as the all-ones state as illegal. 3. Allow smaller I/O benchmarks to use LFSRs. 4. The spin parameter follows the same rationale as in 1b. To make the LFSR outcome "appear" less predictable, we can spin internally the LFSR state and produce the i-th number. To understand the spin parameter, consider the following state sequence of a 3-bit LFSR: 0, 2, 3, 5, 6, 1, 4 Same LFSR, spin value 2: 0, 3, 6, 4, 2, 5, 1 But what is the benefit from using spin? Well, the benefits are two-fold: a. For the same I/O size, we can create a different I/O sequences. b. Following the rationale of 1b, we can have more variable outcomes. If the spin value is "i" and the taps are "z", the number of different outcomes become i * 2^(z + 1). Signed-off-by: Alex Pyrgiotis <apyrgio@grnet.gr> Signed-off-by: Jens Axboe <axboe@kernel.dk>
2013-01-21lfsr: add lfsr_reset()Jens Axboe
This enables us to restart a sequence. Signed-off-by: Jens Axboe <axboe@kernel.dk>
2013-01-11lfsr: ensure we don't generate an offset + buflen that exceeds the max sizeJens Axboe
Currently we check for the max value, but that doesn't always work since it may not fit the minimum block size (even if it is guaranteed to be smaller than the max offset). Pass in the last valid block. Signed-off-by: Jens Axboe <axboe@kernel.dk>
2012-12-04lfsr: ensure that the cycle follows the randrepeat= settingJens Axboe
Use the regular block offset seed to "seed" the lfsr generator, so that it obeys randrepeat=0/1 as well. Signed-off-by: Jens Axboe <axboe@kernel.dk>
2012-11-26Add LFSR generatorJens Axboe
Signed-off-by: Jens Axboe <axboe@kernel.dk>