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)
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)
230 *off = fl->last_val - 1;
235 static struct lfsr_taps *find_lfsr(uint64_t size)
239 for (i = 0; lfsr_taps[i].length; i++)
240 if (((1UL << lfsr_taps[i].length) + FIO_LFSR_CRANKS) >= size)
241 return &lfsr_taps[i];
246 int lfsr_init(struct fio_lfsr *fl, uint64_t size, unsigned long seed)
248 struct lfsr_taps *tap;
251 tap = find_lfsr(size);
256 fl->max_val = size - 1;
258 fl->taps.length = tap->length;
259 for (i = 0; i < FIO_MAX_TAPS; i++) {
260 fl->taps.taps[i] = tap->taps[i];
261 if (!fl->taps.taps[i])
265 for (i = 0; i < FIO_LFSR_CRANKS; i++)
266 fl->last_val = __lfsr_next(fl->last_val, &fl->taps);