8 * http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf
10 static struct lfsr_taps lfsr_taps[] = {
13 .taps = { 16, 15, 13, 4, },
25 .taps = { 19, 6, 2, 1, },
45 .taps = { 24, 23, 22, 17, },
53 .taps = {26, 6, 2, 1, },
57 .taps = { 27, 5, 2, 1, },
69 .taps = { 30, 6, 4, 1, },
77 .taps = { 32, 22, 2, 1, },
85 .taps = { 34, 27, 2, 1, },
97 .taps = { 37, 5, 4, 3, 2, 1, },
101 .taps = { 38, 6, 5, 1, },
109 .taps = { 40, 38, 21, 19, },
117 .taps = { 42, 41, 20, 19, },
121 .taps = { 43, 42, 38, 37, },
125 .taps = { 44, 43, 38, 37, },
129 .taps = { 45, 44, 42, 41, },
133 .taps = { 46, 45, 26, 25, },
141 .taps = { 48, 47, 21, 20, },
149 .taps = { 50, 49, 36, 35, },
153 .taps = { 51, 50, 36, 35, },
161 .taps = { 53, 52, 38, 37 },
165 .taps = { 54, 53, 18, 17 },
173 .taps = { 56, 55, 35, 34, },
185 .taps = { 59, 58, 38, 37, },
193 .taps = { 61, 60, 46, 45, },
197 .taps = { 62, 61, 6, 5, },
205 #define FIO_LFSR_CRANKS 128
207 static uint64_t __lfsr_next(uint64_t v, struct lfsr_taps *lt)
209 uint64_t xor_mask = 0;
212 for (i = 0; lt->taps[i]; i++)
213 xor_mask ^= (v << (lt->taps[i] - 1));
215 xor_mask &= ~(~0UL << 1) << (lt->length - 1);
216 return xor_mask | (v >> 1);
219 int lfsr_next(struct fio_lfsr *fl, uint64_t *off, uint64_t last)
221 if (fl->num_vals > fl->max_val)
225 fl->last_val = __lfsr_next(fl->last_val, &fl->taps);
226 if (fl->last_val - 1 <= fl->max_val &&
227 fl->last_val <= last)
231 *off = fl->last_val - 1;
236 static struct lfsr_taps *find_lfsr(uint64_t size)
240 for (i = 0; lfsr_taps[i].length; i++)
241 if (((1UL << lfsr_taps[i].length) + FIO_LFSR_CRANKS) >= size)
242 return &lfsr_taps[i];
247 void lfsr_reset(struct fio_lfsr *fl, unsigned long seed)
254 for (i = 0; i < FIO_LFSR_CRANKS; i++)
255 fl->last_val = __lfsr_next(fl->last_val, &fl->taps);
258 int lfsr_init(struct fio_lfsr *fl, uint64_t size, unsigned long seed)
260 struct lfsr_taps *tap;
263 tap = find_lfsr(size);
267 fl->max_val = size - 1;
268 fl->taps.length = tap->length;
270 for (i = 0; i < FIO_MAX_TAPS; i++) {
271 fl->taps.taps[i] = tap->taps[i];
272 if (!fl->taps.taps[i])
276 lfsr_reset(fl, seed);