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