Commit | Line | Data |
---|---|---|
8055e41d JA |
1 | #include <stdio.h> |
2 | ||
3 | #include "lfsr.h" | |
225ba9e3 | 4 | #include "../compiler/compiler.h" |
8055e41d JA |
5 | |
6 | /* | |
d474cbc9 AP |
7 | * LFSR taps retrieved from: |
8 | * http://home1.gte.net/res0658s/electronics/LFSRtaps.html | |
8055e41d | 9 | * |
d474cbc9 AP |
10 | * The memory overhead of the following tap table should be relatively small, |
11 | * no more than 400 bytes. | |
8055e41d | 12 | */ |
8a1db9a1 | 13 | static uint8_t lfsr_taps[64][FIO_MAX_TAPS] = |
d474cbc9 | 14 | { |
b136e932 JA |
15 | {0}, {0}, {0}, //LFSRs with less that 3-bits cannot exist |
16 | {3, 2}, //Tap position for 3-bit LFSR | |
17 | {4, 3}, //Tap position for 4-bit LFSR | |
18 | {5, 3}, //Tap position for 5-bit LFSR | |
19 | {6, 5}, //Tap position for 6-bit LFSR | |
20 | {7, 6}, //Tap position for 7-bit LFSR | |
21 | {8, 6, 5 ,4}, //Tap position for 8-bit LFSR | |
22 | {9, 5}, //Tap position for 9-bit LFSR | |
23 | {10, 7}, //Tap position for 10-bit LFSR | |
24 | {11, 9}, //Tap position for 11-bit LFSR | |
25 | {12, 6, 4, 1}, //Tap position for 12-bit LFSR | |
26 | {13, 4, 3, 1}, //Tap position for 13-bit LFSR | |
27 | {14, 5, 3, 1}, //Tap position for 14-bit LFSR | |
28 | {15, 14}, //Tap position for 15-bit LFSR | |
29 | {16, 15, 13, 4}, //Tap position for 16-bit LFSR | |
30 | {17, 14}, //Tap position for 17-bit LFSR | |
31 | {18, 11}, //Tap position for 18-bit LFSR | |
32 | {19, 6, 2, 1}, //Tap position for 19-bit LFSR | |
33 | {20, 17}, //Tap position for 20-bit LFSR | |
34 | {21, 19}, //Tap position for 21-bit LFSR | |
35 | {22, 21}, //Tap position for 22-bit LFSR | |
36 | {23, 18}, //Tap position for 23-bit LFSR | |
37 | {24, 23, 22, 17}, //Tap position for 24-bit LFSR | |
38 | {25, 22}, //Tap position for 25-bit LFSR | |
39 | {26, 6, 2, 1}, //Tap position for 26-bit LFSR | |
40 | {27, 5, 2, 1}, //Tap position for 27-bit LFSR | |
41 | {28, 25}, //Tap position for 28-bit LFSR | |
42 | {29, 27}, //Tap position for 29-bit LFSR | |
43 | {30, 6, 4, 1}, //Tap position for 30-bit LFSR | |
44 | {31, 28}, //Tap position for 31-bit LFSR | |
45 | {32, 31, 29, 1}, //Tap position for 32-bit LFSR | |
46 | {33, 20}, //Tap position for 33-bit LFSR | |
47 | {34, 27, 2, 1}, //Tap position for 34-bit LFSR | |
48 | {35, 33}, //Tap position for 35-bit LFSR | |
49 | {36, 25}, //Tap position for 36-bit LFSR | |
50 | {37, 5, 4, 3, 2, 1}, //Tap position for 37-bit LFSR | |
51 | {38, 6, 5, 1}, //Tap position for 38-bit LFSR | |
52 | {39, 35}, //Tap position for 39-bit LFSR | |
53 | {40, 38, 21, 19}, //Tap position for 40-bit LFSR | |
54 | {41, 38}, //Tap position for 41-bit LFSR | |
55 | {42, 41, 20, 19}, //Tap position for 42-bit LFSR | |
56 | {43, 42, 38, 37}, //Tap position for 43-bit LFSR | |
57 | {44, 43, 18, 17}, //Tap position for 44-bit LFSR | |
58 | {45, 44, 42, 41}, //Tap position for 45-bit LFSR | |
59 | {46, 45, 26, 25}, //Tap position for 46-bit LFSR | |
60 | {47, 42}, //Tap position for 47-bit LFSR | |
61 | {48, 47, 21, 20}, //Tap position for 48-bit LFSR | |
62 | {49, 40}, //Tap position for 49-bit LFSR | |
63 | {50, 49, 24, 23}, //Tap position for 50-bit LFSR | |
64 | {51, 50, 36, 35}, //Tap position for 51-bit LFSR | |
65 | {52, 49}, //Tap position for 52-bit LFSR | |
66 | {53, 52, 38, 37}, //Tap position for 53-bit LFSR | |
67 | {54, 53, 18, 17}, //Tap position for 54-bit LFSR | |
68 | {55, 31}, //Tap position for 55-bit LFSR | |
69 | {56, 55, 35, 34}, //Tap position for 56-bit LFSR | |
70 | {57, 50}, //Tap position for 57-bit LFSR | |
71 | {58, 39}, //Tap position for 58-bit LFSR | |
72 | {59, 58, 38, 37}, //Tap position for 59-bit LFSR | |
73 | {60, 59}, //Tap position for 60-bit LFSR | |
74 | {61, 60, 46, 45}, //Tap position for 61-bit LFSR | |
75 | {62, 61, 6, 5}, //Tap position for 62-bit LFSR | |
76 | {63, 62}, //Tap position for 63-bit LFSR | |
8055e41d JA |
77 | }; |
78 | ||
d474cbc9 AP |
79 | #define __LFSR_NEXT(__fl, __v) \ |
80 | __v = ((__v >> 1) | __fl->cached_bit) ^ \ | |
fe6e1197 | 81 | (((__v & 1ULL) - 1ULL) & __fl->xormask); |
c4fc0ff1 | 82 | |
d474cbc9 | 83 | static inline void __lfsr_next(struct fio_lfsr *fl, unsigned int spin) |
8055e41d | 84 | { |
d474cbc9 AP |
85 | /* |
86 | * This should be O(1) since most compilers will create a jump table for | |
87 | * this switch. | |
88 | */ | |
89 | switch (spin) { | |
d474cbc9 | 90 | case 15: __LFSR_NEXT(fl, fl->last_val); |
db83b0ab | 91 | fallthrough; |
d474cbc9 | 92 | case 14: __LFSR_NEXT(fl, fl->last_val); |
db83b0ab | 93 | fallthrough; |
d474cbc9 | 94 | case 13: __LFSR_NEXT(fl, fl->last_val); |
db83b0ab | 95 | fallthrough; |
d474cbc9 | 96 | case 12: __LFSR_NEXT(fl, fl->last_val); |
db83b0ab | 97 | fallthrough; |
d474cbc9 | 98 | case 11: __LFSR_NEXT(fl, fl->last_val); |
db83b0ab | 99 | fallthrough; |
d474cbc9 | 100 | case 10: __LFSR_NEXT(fl, fl->last_val); |
db83b0ab | 101 | fallthrough; |
d474cbc9 | 102 | case 9: __LFSR_NEXT(fl, fl->last_val); |
db83b0ab | 103 | fallthrough; |
d474cbc9 | 104 | case 8: __LFSR_NEXT(fl, fl->last_val); |
db83b0ab | 105 | fallthrough; |
d474cbc9 | 106 | case 7: __LFSR_NEXT(fl, fl->last_val); |
db83b0ab | 107 | fallthrough; |
d474cbc9 | 108 | case 6: __LFSR_NEXT(fl, fl->last_val); |
db83b0ab | 109 | fallthrough; |
d474cbc9 | 110 | case 5: __LFSR_NEXT(fl, fl->last_val); |
db83b0ab | 111 | fallthrough; |
d474cbc9 | 112 | case 4: __LFSR_NEXT(fl, fl->last_val); |
db83b0ab | 113 | fallthrough; |
d474cbc9 | 114 | case 3: __LFSR_NEXT(fl, fl->last_val); |
db83b0ab | 115 | fallthrough; |
d474cbc9 | 116 | case 2: __LFSR_NEXT(fl, fl->last_val); |
db83b0ab | 117 | fallthrough; |
d474cbc9 | 118 | case 1: __LFSR_NEXT(fl, fl->last_val); |
db83b0ab | 119 | fallthrough; |
d474cbc9 | 120 | case 0: __LFSR_NEXT(fl, fl->last_val); |
db83b0ab | 121 | fallthrough; |
d474cbc9 AP |
122 | default: break; |
123 | } | |
8055e41d JA |
124 | } |
125 | ||
a64ea63f AP |
126 | /* |
127 | * lfsr_next does the following: | |
128 | * | |
129 | * a. Return if the number of max values has been exceeded. | |
d0f85362 AP |
130 | * b. Check if we have a spin value that produces a repeating subsequence. |
131 | * This is previously calculated in `prepare_spin` and cycle_length should | |
132 | * be > 0. If we do have such a spin: | |
133 | * | |
134 | * i. Decrement the calculated cycle. | |
135 | * ii. If it reaches zero, add "+1" to the spin and reset the cycle_length | |
136 | * (we have it cached in the struct fio_lfsr) | |
137 | * | |
138 | * In either case, continue with the calculation of the next value. | |
139 | * c. Check if the calculated value exceeds the desirable range. In this case, | |
140 | * go back to b, else return. | |
a64ea63f | 141 | */ |
6f49f8bc | 142 | int lfsr_next(struct fio_lfsr *fl, uint64_t *off) |
8055e41d | 143 | { |
a64ea63f AP |
144 | if (fl->num_vals++ > fl->max_val) |
145 | return 1; | |
146 | ||
8055e41d | 147 | do { |
d56036a4 AP |
148 | if (fl->cycle_length && !--fl->cycle_length) { |
149 | __lfsr_next(fl, fl->spin + 1); | |
150 | fl->cycle_length = fl->cached_cycle_length; | |
225ba9e3 JA |
151 | } else |
152 | __lfsr_next(fl, fl->spin); | |
153 | } while (fio_unlikely(fl->last_val > fl->max_val)); | |
8055e41d | 154 | |
d474cbc9 | 155 | *off = fl->last_val; |
8055e41d JA |
156 | return 0; |
157 | } | |
158 | ||
d474cbc9 | 159 | static uint64_t lfsr_create_xormask(uint8_t *taps) |
8055e41d JA |
160 | { |
161 | int i; | |
d474cbc9 | 162 | uint64_t xormask = 0; |
8055e41d | 163 | |
d474cbc9 | 164 | for(i = 0; i < FIO_MAX_TAPS && taps[i] != 0; i++) |
fe6e1197 | 165 | xormask |= 1ULL << (taps[i] - 1); |
8055e41d | 166 | |
d474cbc9 | 167 | return xormask; |
8055e41d JA |
168 | } |
169 | ||
d474cbc9 | 170 | static uint8_t *find_lfsr(uint64_t size) |
0415406f | 171 | { |
d474cbc9 | 172 | int i; |
0415406f | 173 | |
d56036a4 AP |
174 | /* |
175 | * For an LFSR, there is always a prohibited state (all ones). | |
8a1db9a1 JA |
176 | * Thus, if we need to find the proper LFSR for our size, we must |
177 | * take that into account. | |
d56036a4 | 178 | */ |
d474cbc9 | 179 | for (i = 3; i < 64; i++) |
fe6e1197 | 180 | if ((1ULL << i) > size) |
8a1db9a1 | 181 | return lfsr_taps[i]; |
0415406f | 182 | |
d474cbc9 | 183 | return NULL; |
0415406f JA |
184 | } |
185 | ||
d474cbc9 AP |
186 | /* |
187 | * It is well-known that all maximal n-bit LFSRs will start repeating | |
188 | * themselves after their 2^n iteration. The introduction of spins however, is | |
189 | * possible to create a repetition of a sub-sequence before we hit that mark. | |
190 | * This happens if: | |
191 | * | |
192 | * [1]: ((2^n - 1) * i) % (spin + 1) == 0, | |
193 | * where "n" is LFSR's bits and "i" any number within the range [1,spin] | |
194 | * | |
195 | * It is important to know beforehand if a spin can cause a repetition of a | |
196 | * sub-sequence (cycle) and its length. However, calculating (2^n - 1) * i may | |
197 | * produce a buffer overflow for "n" close to 64, so we expand the above to: | |
198 | * | |
199 | * [2]: (2^n - 1) -> (x * (spin + 1) + y), where x >= 0 and 0 <= y <= spin | |
200 | * | |
201 | * Thus, [1] is equivalent to (y * i) % (spin + 1) == 0; | |
202 | * Also, the cycle's length will be (x * i) + (y * i) / (spin + 1) | |
203 | */ | |
10aa136b | 204 | static int prepare_spin(struct fio_lfsr *fl, unsigned int spin) |
8055e41d | 205 | { |
d474cbc9 AP |
206 | uint64_t max = (fl->cached_bit << 1) - 1; |
207 | uint64_t x, y; | |
8055e41d JA |
208 | int i; |
209 | ||
d474cbc9 | 210 | if (spin > 15) |
8055e41d JA |
211 | return 1; |
212 | ||
d474cbc9 AP |
213 | x = max / (spin + 1); |
214 | y = max % (spin + 1); | |
d0f85362 | 215 | fl->cycle_length = 0; /* No cycle occurs, other than the expected */ |
d474cbc9 | 216 | fl->spin = spin; |
0415406f | 217 | |
d474cbc9 AP |
218 | for (i = 1; i <= spin; i++) { |
219 | if ((y * i) % (spin + 1) == 0) { | |
220 | fl->cycle_length = (x * i) + (y * i) / (spin + 1); | |
8055e41d | 221 | break; |
d474cbc9 | 222 | } |
8055e41d | 223 | } |
d0f85362 | 224 | fl->cached_cycle_length = fl->cycle_length; |
8055e41d | 225 | |
d56036a4 AP |
226 | /* |
227 | * Increment cycle length for the first time only since the stored value | |
228 | * will not be printed otherwise. | |
229 | */ | |
230 | fl->cycle_length++; | |
231 | ||
d474cbc9 AP |
232 | return 0; |
233 | } | |
234 | ||
9781c080 | 235 | int lfsr_reset(struct fio_lfsr *fl, uint64_t seed) |
d474cbc9 AP |
236 | { |
237 | uint64_t bitmask = (fl->cached_bit << 1) - 1; | |
238 | ||
239 | fl->num_vals = 0; | |
240 | fl->last_val = seed & bitmask; | |
241 | ||
242 | /* All-ones state is illegal for XNOR LFSRs */ | |
243 | if (fl->last_val == bitmask) | |
244 | return 1; | |
245 | ||
246 | return 0; | |
247 | } | |
248 | ||
9781c080 MHT |
249 | int lfsr_init(struct fio_lfsr *fl, uint64_t nums, uint64_t seed, |
250 | unsigned int spin) | |
d474cbc9 | 251 | { |
8a1db9a1 | 252 | uint8_t *taps; |
d474cbc9 | 253 | |
8a1db9a1 JA |
254 | taps = find_lfsr(nums); |
255 | if (!taps) | |
d474cbc9 AP |
256 | return 1; |
257 | ||
258 | fl->max_val = nums - 1; | |
8a1db9a1 | 259 | fl->xormask = lfsr_create_xormask(taps); |
fe6e1197 | 260 | fl->cached_bit = 1ULL << (taps[0] - 1); |
d474cbc9 AP |
261 | |
262 | if (prepare_spin(fl, spin)) | |
263 | return 1; | |
264 | ||
265 | if (lfsr_reset(fl, seed)) | |
266 | return 1; | |
267 | ||
8055e41d JA |
268 | return 0; |
269 | } |