Commit | Line | Data |
---|---|---|
8055e41d | 1 | #include <stdio.h> |
d474cbc9 | 2 | #include <math.h> |
8055e41d JA |
3 | |
4 | #include "lfsr.h" | |
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 | */ |
d474cbc9 AP |
13 | static uint8_t taps[64][FIO_MAX_TAPS] = |
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) ^ \ | |
81 | (((__v & 1UL) - 1UL) & __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) { | |
90 | case 16: __LFSR_NEXT(fl, fl->last_val); | |
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. | |
115 | * b. Check if the next iteration(s) produce a cycle (due to spin) and add "1" | |
116 | * where necessary. | |
117 | * c. Calculate the next value and return. | |
118 | */ | |
74776733 | 119 | int lfsr_next(struct fio_lfsr *fl, uint64_t *off, uint64_t last) |
8055e41d | 120 | { |
d474cbc9 AP |
121 | int repeat; |
122 | unsigned int spin; | |
123 | ||
a64ea63f AP |
124 | if (fl->num_vals++ > fl->max_val) |
125 | return 1; | |
126 | ||
d474cbc9 AP |
127 | repeat = fl->num_vals % fl->cycle_length; |
128 | if (repeat == 0) | |
129 | spin = fl->spin + 1; | |
130 | else | |
131 | spin = fl->spin; | |
132 | ||
8055e41d | 133 | do { |
d474cbc9 AP |
134 | __lfsr_next(fl, spin); |
135 | } while (fl->last_val > fl->max_val); | |
8055e41d | 136 | |
d474cbc9 | 137 | *off = fl->last_val; |
8055e41d JA |
138 | return 0; |
139 | } | |
140 | ||
d474cbc9 | 141 | static uint64_t lfsr_create_xormask(uint8_t *taps) |
8055e41d JA |
142 | { |
143 | int i; | |
d474cbc9 | 144 | uint64_t xormask = 0; |
8055e41d | 145 | |
d474cbc9 AP |
146 | for(i = 0; i < FIO_MAX_TAPS && taps[i] != 0; i++) |
147 | xormask |= 1UL << (taps[i] - 1); | |
8055e41d | 148 | |
d474cbc9 | 149 | return xormask; |
8055e41d JA |
150 | } |
151 | ||
d474cbc9 | 152 | static uint8_t *find_lfsr(uint64_t size) |
0415406f | 153 | { |
d474cbc9 | 154 | int i; |
0415406f | 155 | |
d474cbc9 AP |
156 | for (i = 3; i < 64; i++) |
157 | if ((1UL << i) > size) /* TODO: Explain why. */ | |
158 | return taps[i]; | |
0415406f | 159 | |
d474cbc9 | 160 | return NULL; |
0415406f JA |
161 | } |
162 | ||
d474cbc9 AP |
163 | /* |
164 | * It is well-known that all maximal n-bit LFSRs will start repeating | |
165 | * themselves after their 2^n iteration. The introduction of spins however, is | |
166 | * possible to create a repetition of a sub-sequence before we hit that mark. | |
167 | * This happens if: | |
168 | * | |
169 | * [1]: ((2^n - 1) * i) % (spin + 1) == 0, | |
170 | * where "n" is LFSR's bits and "i" any number within the range [1,spin] | |
171 | * | |
172 | * It is important to know beforehand if a spin can cause a repetition of a | |
173 | * sub-sequence (cycle) and its length. However, calculating (2^n - 1) * i may | |
174 | * produce a buffer overflow for "n" close to 64, so we expand the above to: | |
175 | * | |
176 | * [2]: (2^n - 1) -> (x * (spin + 1) + y), where x >= 0 and 0 <= y <= spin | |
177 | * | |
178 | * Thus, [1] is equivalent to (y * i) % (spin + 1) == 0; | |
179 | * Also, the cycle's length will be (x * i) + (y * i) / (spin + 1) | |
180 | */ | |
181 | int prepare_spin(struct fio_lfsr *fl, unsigned int spin) | |
8055e41d | 182 | { |
d474cbc9 AP |
183 | uint64_t max = (fl->cached_bit << 1) - 1; |
184 | uint64_t x, y; | |
8055e41d JA |
185 | int i; |
186 | ||
d474cbc9 | 187 | if (spin > 15) |
8055e41d JA |
188 | return 1; |
189 | ||
d474cbc9 AP |
190 | x = max / (spin + 1); |
191 | y = max % (spin + 1); | |
192 | fl->cycle_length = max; /* This is the expected cycle */ | |
193 | fl->spin = spin; | |
0415406f | 194 | |
d474cbc9 AP |
195 | for (i = 1; i <= spin; i++) { |
196 | if ((y * i) % (spin + 1) == 0) { | |
197 | fl->cycle_length = (x * i) + (y * i) / (spin + 1); | |
8055e41d | 198 | break; |
d474cbc9 | 199 | } |
8055e41d JA |
200 | } |
201 | ||
d474cbc9 AP |
202 | return 0; |
203 | } | |
204 | ||
205 | int lfsr_reset(struct fio_lfsr *fl, unsigned long seed) | |
206 | { | |
207 | uint64_t bitmask = (fl->cached_bit << 1) - 1; | |
208 | ||
209 | fl->num_vals = 0; | |
210 | fl->last_val = seed & bitmask; | |
211 | ||
212 | /* All-ones state is illegal for XNOR LFSRs */ | |
213 | if (fl->last_val == bitmask) | |
214 | return 1; | |
215 | ||
216 | return 0; | |
217 | } | |
218 | ||
219 | int lfsr_init(struct fio_lfsr *fl, uint64_t nums, unsigned long seed, | |
220 | unsigned int spin) | |
221 | { | |
222 | uint8_t *lfsr_taps; | |
223 | ||
224 | lfsr_taps = find_lfsr(nums); | |
225 | if (!lfsr_taps) | |
226 | return 1; | |
227 | ||
228 | fl->max_val = nums - 1; | |
229 | fl->xormask = lfsr_create_xormask(lfsr_taps); | |
230 | fl->cached_bit = 1UL << (lfsr_taps[0] - 1); | |
231 | ||
232 | if (prepare_spin(fl, spin)) | |
233 | return 1; | |
234 | ||
235 | if (lfsr_reset(fl, seed)) | |
236 | return 1; | |
237 | ||
8055e41d JA |
238 | return 0; |
239 | } |