Commit | Line | Data |
---|---|---|
8055e41d JA |
1 | #include <stdio.h> |
2 | ||
3 | #include "lfsr.h" | |
4 | ||
5 | /* | |
c4fc0ff1 | 6 | * From table 3 of |
8055e41d JA |
7 | * |
8 | * http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf | |
9 | */ | |
10 | static struct lfsr_taps lfsr_taps[] = { | |
11 | { | |
12 | .length = 16, | |
13 | .taps = { 16, 15, 13, 4, }, | |
14 | }, | |
15 | { | |
16 | .length = 17, | |
17 | .taps = { 17, 14, }, | |
18 | }, | |
19 | { | |
20 | .length = 18, | |
21 | .taps = { 18, 11, }, | |
22 | }, | |
23 | { | |
24 | .length = 19, | |
25 | .taps = { 19, 6, 2, 1, }, | |
26 | }, | |
27 | { | |
28 | .length = 20, | |
29 | .taps = { 20, 17, }, | |
30 | }, | |
31 | { | |
32 | .length = 21, | |
33 | .taps = { 21, 19, }, | |
34 | }, | |
35 | { | |
36 | .length = 22, | |
37 | .taps = { 22, 21, }, | |
38 | }, | |
39 | { | |
40 | .length = 23, | |
41 | .taps = { 23, 18, }, | |
42 | }, | |
43 | { | |
44 | .length = 24, | |
45 | .taps = { 24, 23, 22, 17, }, | |
46 | }, | |
47 | { | |
48 | .length = 25, | |
49 | .taps = { 25, 22, }, | |
50 | }, | |
51 | { | |
52 | .length = 26, | |
53 | .taps = {26, 6, 2, 1, }, | |
54 | }, | |
55 | { | |
56 | .length = 27, | |
57 | .taps = { 27, 5, 2, 1, }, | |
58 | }, | |
59 | { | |
60 | .length = 28, | |
61 | .taps = { 28, 25, }, | |
62 | }, | |
63 | { | |
64 | .length = 29, | |
65 | .taps = {29, 27, }, | |
66 | }, | |
67 | { | |
68 | .length = 30, | |
69 | .taps = { 30, 6, 4, 1, }, | |
70 | }, | |
71 | { | |
72 | .length = 31, | |
73 | .taps = { 31, 28, }, | |
74 | }, | |
75 | { | |
76 | .length = 32, | |
77 | .taps = { 32, 22, 2, 1, }, | |
78 | }, | |
79 | { | |
80 | .length = 33, | |
81 | .taps = { 33, 20, }, | |
82 | }, | |
83 | { | |
84 | .length = 34, | |
85 | .taps = { 34, 27, 2, 1, }, | |
86 | }, | |
87 | { | |
88 | .length = 35, | |
89 | .taps = { 35, 33, }, | |
90 | }, | |
91 | { | |
92 | .length = 36, | |
93 | .taps = { 36, 25, }, | |
94 | }, | |
95 | { | |
96 | .length = 37, | |
97 | .taps = { 37, 5, 4, 3, 2, 1, }, | |
98 | }, | |
99 | { | |
100 | .length = 38, | |
101 | .taps = { 38, 6, 5, 1, }, | |
102 | }, | |
103 | { | |
104 | .length = 39, | |
105 | .taps = { 39, 35, }, | |
106 | }, | |
107 | { | |
108 | .length = 40, | |
109 | .taps = { 40, 38, 21, 19, }, | |
110 | }, | |
111 | { | |
112 | .length = 41, | |
113 | .taps = { 41, 38, }, | |
114 | }, | |
115 | { | |
116 | .length = 42, | |
117 | .taps = { 42, 41, 20, 19, }, | |
118 | }, | |
119 | { | |
120 | .length = 43, | |
121 | .taps = { 43, 42, 38, 37, }, | |
122 | }, | |
123 | { | |
124 | .length = 44, | |
125 | .taps = { 44, 43, 38, 37, }, | |
126 | }, | |
127 | { | |
128 | .length = 45, | |
129 | .taps = { 45, 44, 42, 41, }, | |
130 | }, | |
131 | { | |
132 | .length = 46, | |
133 | .taps = { 46, 45, 26, 25, }, | |
134 | }, | |
135 | { | |
136 | .length = 47, | |
137 | .taps = { 47, 42, }, | |
138 | }, | |
139 | { | |
140 | .length = 48, | |
141 | .taps = { 48, 47, 21, 20, }, | |
142 | }, | |
143 | { | |
144 | .length = 49, | |
145 | .taps = { 49, 40, }, | |
146 | }, | |
147 | { | |
148 | .length = 50, | |
149 | .taps = { 50, 49, 36, 35, }, | |
150 | }, | |
151 | { | |
152 | .length = 51, | |
153 | .taps = { 51, 50, 36, 35, }, | |
154 | }, | |
155 | { | |
156 | .length = 52, | |
157 | .taps = { 52, 49, }, | |
158 | }, | |
159 | { | |
160 | .length = 53, | |
161 | .taps = { 53, 52, 38, 37 }, | |
162 | }, | |
163 | { | |
164 | .length = 54, | |
165 | .taps = { 54, 53, 18, 17 }, | |
166 | }, | |
167 | { | |
168 | .length = 55, | |
169 | .taps = { 55, 31, }, | |
170 | }, | |
171 | { | |
172 | .length = 56, | |
173 | .taps = { 56, 55, 35, 34, }, | |
174 | }, | |
175 | { | |
176 | .length = 57, | |
177 | .taps = { 57, 50, }, | |
178 | }, | |
179 | { | |
180 | .length = 58, | |
181 | .taps = { 58, 39, }, | |
182 | }, | |
183 | { | |
184 | .length = 59, | |
185 | .taps = { 59, 58, 38, 37, }, | |
186 | }, | |
187 | { | |
188 | .length = 60, | |
189 | .taps = { 60, 59, }, | |
190 | }, | |
191 | { | |
192 | .length = 61, | |
193 | .taps = { 61, 60, 46, 45, }, | |
194 | }, | |
195 | { | |
196 | .length = 62, | |
197 | .taps = { 62, 61, 6, 5, }, | |
198 | }, | |
199 | { | |
200 | .length = 63, | |
201 | .taps = { 63, 62, }, | |
202 | }, | |
203 | }; | |
204 | ||
c4fc0ff1 JA |
205 | #define FIO_LFSR_CRANKS 128 |
206 | ||
8055e41d JA |
207 | static uint64_t __lfsr_next(uint64_t v, struct lfsr_taps *lt) |
208 | { | |
209 | uint64_t xor_mask = 0; | |
210 | int i; | |
211 | ||
212 | for (i = 0; lt->taps[i]; i++) | |
213 | xor_mask ^= (v << (lt->taps[i] - 1)); | |
214 | ||
215 | xor_mask &= ~(~0UL << 1) << (lt->length - 1); | |
216 | return xor_mask | (v >> 1); | |
217 | } | |
218 | ||
74776733 | 219 | int lfsr_next(struct fio_lfsr *fl, uint64_t *off, uint64_t last) |
8055e41d JA |
220 | { |
221 | if (fl->num_vals > fl->max_val) | |
222 | return 1; | |
223 | ||
224 | do { | |
225 | fl->last_val = __lfsr_next(fl->last_val, &fl->taps); | |
74776733 JA |
226 | if (fl->last_val - 1 <= fl->max_val && |
227 | fl->last_val <= last) | |
8055e41d JA |
228 | break; |
229 | } while (1); | |
230 | ||
231 | *off = fl->last_val - 1; | |
232 | fl->num_vals++; | |
233 | return 0; | |
234 | } | |
235 | ||
236 | static struct lfsr_taps *find_lfsr(uint64_t size) | |
237 | { | |
238 | int i; | |
239 | ||
240 | for (i = 0; lfsr_taps[i].length; i++) | |
c4fc0ff1 | 241 | if (((1UL << lfsr_taps[i].length) + FIO_LFSR_CRANKS) >= size) |
8055e41d JA |
242 | return &lfsr_taps[i]; |
243 | ||
244 | return NULL; | |
245 | } | |
246 | ||
82af46be | 247 | int lfsr_init(struct fio_lfsr *fl, uint64_t size, unsigned long seed) |
8055e41d JA |
248 | { |
249 | struct lfsr_taps *tap; | |
250 | int i; | |
251 | ||
252 | tap = find_lfsr(size); | |
253 | if (!tap) | |
254 | return 1; | |
255 | ||
82af46be | 256 | fl->last_val = seed; |
8055e41d JA |
257 | fl->max_val = size - 1; |
258 | fl->num_vals = 0; | |
259 | fl->taps.length = tap->length; | |
260 | for (i = 0; i < FIO_MAX_TAPS; i++) { | |
261 | fl->taps.taps[i] = tap->taps[i]; | |
262 | if (!fl->taps.taps[i]) | |
263 | break; | |
264 | } | |
265 | ||
c4fc0ff1 JA |
266 | for (i = 0; i < FIO_LFSR_CRANKS; i++) |
267 | fl->last_val = __lfsr_next(fl->last_val, &fl->taps); | |
268 | ||
8055e41d JA |
269 | return 0; |
270 | } |