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 AP |
90 | case 15: __LFSR_NEXT(fl, fl->last_val); |
91 | case 14: __LFSR_NEXT(fl, fl->last_val); | |
92 | case 13: __LFSR_NEXT(fl, fl->last_val); | |
93 | case 12: __LFSR_NEXT(fl, fl->last_val); | |
94 | case 11: __LFSR_NEXT(fl, fl->last_val); | |
95 | case 10: __LFSR_NEXT(fl, fl->last_val); | |
96 | case 9: __LFSR_NEXT(fl, fl->last_val); | |
97 | case 8: __LFSR_NEXT(fl, fl->last_val); | |
98 | case 7: __LFSR_NEXT(fl, fl->last_val); | |
99 | case 6: __LFSR_NEXT(fl, fl->last_val); | |
100 | case 5: __LFSR_NEXT(fl, fl->last_val); | |
101 | case 4: __LFSR_NEXT(fl, fl->last_val); | |
102 | case 3: __LFSR_NEXT(fl, fl->last_val); | |
103 | case 2: __LFSR_NEXT(fl, fl->last_val); | |
104 | case 1: __LFSR_NEXT(fl, fl->last_val); | |
105 | case 0: __LFSR_NEXT(fl, fl->last_val); | |
106 | default: break; | |
107 | } | |
8055e41d JA |
108 | } |
109 | ||
a64ea63f AP |
110 | /* |
111 | * lfsr_next does the following: | |
112 | * | |
113 | * a. Return if the number of max values has been exceeded. | |
d0f85362 AP |
114 | * b. Check if we have a spin value that produces a repeating subsequence. |
115 | * This is previously calculated in `prepare_spin` and cycle_length should | |
116 | * be > 0. If we do have such a spin: | |
117 | * | |
118 | * i. Decrement the calculated cycle. | |
119 | * ii. If it reaches zero, add "+1" to the spin and reset the cycle_length | |
120 | * (we have it cached in the struct fio_lfsr) | |
121 | * | |
122 | * In either case, continue with the calculation of the next value. | |
123 | * c. Check if the calculated value exceeds the desirable range. In this case, | |
124 | * go back to b, else return. | |
a64ea63f | 125 | */ |
6f49f8bc | 126 | int lfsr_next(struct fio_lfsr *fl, uint64_t *off) |
8055e41d | 127 | { |
a64ea63f AP |
128 | if (fl->num_vals++ > fl->max_val) |
129 | return 1; | |
130 | ||
8055e41d | 131 | do { |
d56036a4 AP |
132 | if (fl->cycle_length && !--fl->cycle_length) { |
133 | __lfsr_next(fl, fl->spin + 1); | |
134 | fl->cycle_length = fl->cached_cycle_length; | |
225ba9e3 JA |
135 | } else |
136 | __lfsr_next(fl, fl->spin); | |
137 | } while (fio_unlikely(fl->last_val > fl->max_val)); | |
8055e41d | 138 | |
d474cbc9 | 139 | *off = fl->last_val; |
8055e41d JA |
140 | return 0; |
141 | } | |
142 | ||
d474cbc9 | 143 | static uint64_t lfsr_create_xormask(uint8_t *taps) |
8055e41d JA |
144 | { |
145 | int i; | |
d474cbc9 | 146 | uint64_t xormask = 0; |
8055e41d | 147 | |
d474cbc9 | 148 | for(i = 0; i < FIO_MAX_TAPS && taps[i] != 0; i++) |
fe6e1197 | 149 | xormask |= 1ULL << (taps[i] - 1); |
8055e41d | 150 | |
d474cbc9 | 151 | return xormask; |
8055e41d JA |
152 | } |
153 | ||
d474cbc9 | 154 | static uint8_t *find_lfsr(uint64_t size) |
0415406f | 155 | { |
d474cbc9 | 156 | int i; |
0415406f | 157 | |
d56036a4 AP |
158 | /* |
159 | * For an LFSR, there is always a prohibited state (all ones). | |
8a1db9a1 JA |
160 | * Thus, if we need to find the proper LFSR for our size, we must |
161 | * take that into account. | |
d56036a4 | 162 | */ |
d474cbc9 | 163 | for (i = 3; i < 64; i++) |
fe6e1197 | 164 | if ((1ULL << i) > size) |
8a1db9a1 | 165 | return lfsr_taps[i]; |
0415406f | 166 | |
d474cbc9 | 167 | return NULL; |
0415406f JA |
168 | } |
169 | ||
d474cbc9 AP |
170 | /* |
171 | * It is well-known that all maximal n-bit LFSRs will start repeating | |
172 | * themselves after their 2^n iteration. The introduction of spins however, is | |
173 | * possible to create a repetition of a sub-sequence before we hit that mark. | |
174 | * This happens if: | |
175 | * | |
176 | * [1]: ((2^n - 1) * i) % (spin + 1) == 0, | |
177 | * where "n" is LFSR's bits and "i" any number within the range [1,spin] | |
178 | * | |
179 | * It is important to know beforehand if a spin can cause a repetition of a | |
180 | * sub-sequence (cycle) and its length. However, calculating (2^n - 1) * i may | |
181 | * produce a buffer overflow for "n" close to 64, so we expand the above to: | |
182 | * | |
183 | * [2]: (2^n - 1) -> (x * (spin + 1) + y), where x >= 0 and 0 <= y <= spin | |
184 | * | |
185 | * Thus, [1] is equivalent to (y * i) % (spin + 1) == 0; | |
186 | * Also, the cycle's length will be (x * i) + (y * i) / (spin + 1) | |
187 | */ | |
10aa136b | 188 | static int prepare_spin(struct fio_lfsr *fl, unsigned int spin) |
8055e41d | 189 | { |
d474cbc9 AP |
190 | uint64_t max = (fl->cached_bit << 1) - 1; |
191 | uint64_t x, y; | |
8055e41d JA |
192 | int i; |
193 | ||
d474cbc9 | 194 | if (spin > 15) |
8055e41d JA |
195 | return 1; |
196 | ||
d474cbc9 AP |
197 | x = max / (spin + 1); |
198 | y = max % (spin + 1); | |
d0f85362 | 199 | fl->cycle_length = 0; /* No cycle occurs, other than the expected */ |
d474cbc9 | 200 | fl->spin = spin; |
0415406f | 201 | |
d474cbc9 AP |
202 | for (i = 1; i <= spin; i++) { |
203 | if ((y * i) % (spin + 1) == 0) { | |
204 | fl->cycle_length = (x * i) + (y * i) / (spin + 1); | |
8055e41d | 205 | break; |
d474cbc9 | 206 | } |
8055e41d | 207 | } |
d0f85362 | 208 | fl->cached_cycle_length = fl->cycle_length; |
8055e41d | 209 | |
d56036a4 AP |
210 | /* |
211 | * Increment cycle length for the first time only since the stored value | |
212 | * will not be printed otherwise. | |
213 | */ | |
214 | fl->cycle_length++; | |
215 | ||
d474cbc9 AP |
216 | return 0; |
217 | } | |
218 | ||
219 | int lfsr_reset(struct fio_lfsr *fl, unsigned long seed) | |
220 | { | |
221 | uint64_t bitmask = (fl->cached_bit << 1) - 1; | |
222 | ||
223 | fl->num_vals = 0; | |
224 | fl->last_val = seed & bitmask; | |
225 | ||
226 | /* All-ones state is illegal for XNOR LFSRs */ | |
227 | if (fl->last_val == bitmask) | |
228 | return 1; | |
229 | ||
230 | return 0; | |
231 | } | |
232 | ||
233 | int lfsr_init(struct fio_lfsr *fl, uint64_t nums, unsigned long seed, | |
234 | unsigned int spin) | |
235 | { | |
8a1db9a1 | 236 | uint8_t *taps; |
d474cbc9 | 237 | |
8a1db9a1 JA |
238 | taps = find_lfsr(nums); |
239 | if (!taps) | |
d474cbc9 AP |
240 | return 1; |
241 | ||
242 | fl->max_val = nums - 1; | |
8a1db9a1 | 243 | fl->xormask = lfsr_create_xormask(taps); |
fe6e1197 | 244 | fl->cached_bit = 1ULL << (taps[0] - 1); |
d474cbc9 AP |
245 | |
246 | if (prepare_spin(fl, spin)) | |
247 | return 1; | |
248 | ||
249 | if (lfsr_reset(fl, seed)) | |
250 | return 1; | |
251 | ||
8055e41d JA |
252 | return 0; |
253 | } |