OLD | NEW |
| (Empty) |
1 /* | |
2 * lfsr.c | |
3 * | |
4 */ | |
5 | |
6 /* | |
7 * | |
8 * Copyright (c) 2001-2006, Cisco Systems, Inc. | |
9 * All rights reserved. | |
10 * | |
11 * Redistribution and use in source and binary forms, with or without | |
12 * modification, are permitted provided that the following conditions | |
13 * are met: | |
14 * | |
15 * Redistributions of source code must retain the above copyright | |
16 * notice, this list of conditions and the following disclaimer. | |
17 * | |
18 * Redistributions in binary form must reproduce the above | |
19 * copyright notice, this list of conditions and the following | |
20 * disclaimer in the documentation and/or other materials provided | |
21 * with the distribution. | |
22 * | |
23 * Neither the name of the Cisco Systems, Inc. nor the names of its | |
24 * contributors may be used to endorse or promote products derived | |
25 * from this software without specific prior written permission. | |
26 * | |
27 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
28 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
29 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS | |
30 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE | |
31 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, | |
32 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES | |
33 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR | |
34 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |
35 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, | |
36 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | |
37 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED | |
38 * OF THE POSSIBILITY OF SUCH DAMAGE. | |
39 * | |
40 */ | |
41 | |
42 #include <stdio.h> | |
43 #include "datatypes.h" | |
44 | |
45 uint32_t | |
46 parity(uint32_t x) { | |
47 | |
48 x ^= (x >> 16); | |
49 x ^= (x >> 8); | |
50 x ^= (x >> 4); | |
51 x ^= (x >> 2); | |
52 x ^= (x >> 1); | |
53 | |
54 return x & 1; | |
55 } | |
56 | |
57 | |
58 /* typedef struct { */ | |
59 /* uint32_t register[8]; */ | |
60 /* } lfsr_t; */ | |
61 | |
62 void | |
63 compute_period(uint32_t feedback_polynomial) { | |
64 int i; | |
65 v32_t lfsr; | |
66 v32_t mask; | |
67 | |
68 mask.value = feedback_polynomial; | |
69 lfsr.value = 1; | |
70 | |
71 printf("polynomial: %s\t", v32_bit_string(mask)); | |
72 | |
73 for (i=0; i < 256; i++) { | |
74 /* printf("%s\n", v32_bit_string(lfsr)); */ | |
75 if (parity(mask.value & lfsr.value)) | |
76 lfsr.value = ((lfsr.value << 1) | 1) & 0xff; | |
77 else | |
78 lfsr.value = (lfsr.value << 1) & 0xff; | |
79 | |
80 /* now halt if we're back at the initial state */ | |
81 if (lfsr.value == 1) { | |
82 printf("period: %d\n", i); | |
83 break; | |
84 } | |
85 } | |
86 } | |
87 | |
88 uint32_t poly0 = 223; | |
89 | |
90 | |
91 uint32_t polynomials[39] = { | |
92 31, | |
93 47, | |
94 55, | |
95 59, | |
96 61, | |
97 79, | |
98 87, | |
99 91, | |
100 103, | |
101 107, | |
102 109, | |
103 115, | |
104 117, | |
105 121, | |
106 143, | |
107 151, | |
108 157, | |
109 167, | |
110 171, | |
111 173, | |
112 179, | |
113 181, | |
114 185, | |
115 199, | |
116 203, | |
117 205, | |
118 211, | |
119 213, | |
120 227, | |
121 229, | |
122 233, | |
123 241, | |
124 127, | |
125 191, | |
126 223, | |
127 239, | |
128 247, | |
129 251, | |
130 253 | |
131 }; | |
132 | |
133 char binary_string[32]; | |
134 | |
135 char * | |
136 u32_bit_string(uint32_t x, unsigned int length) { | |
137 unsigned int mask; | |
138 int index; | |
139 | |
140 mask = 1 << length; | |
141 index = 0; | |
142 for (; mask > 0; mask >>= 1) | |
143 if ((x & mask) == 0) | |
144 binary_string[index++] = '0'; | |
145 else | |
146 binary_string[index++] = '1'; | |
147 | |
148 binary_string[index++] = 0; /* NULL terminate string */ | |
149 return binary_string; | |
150 } | |
151 | |
152 extern int octet_weight[256]; | |
153 | |
154 unsigned int | |
155 weight(uint32_t poly) { | |
156 int wt = 0; | |
157 | |
158 /* note: endian-ness makes no difference */ | |
159 wt += octet_weight[poly & 0xff]; | |
160 wt += octet_weight[(poly >> 8) & 0xff]; | |
161 wt += octet_weight[(poly >> 16) & 0xff]; | |
162 wt += octet_weight[(poly >> 24)]; | |
163 | |
164 return wt; | |
165 } | |
166 | |
167 #define MAX_PERIOD 65535 | |
168 | |
169 #define debug_print 0 | |
170 | |
171 int | |
172 period(uint32_t poly) { | |
173 int i; | |
174 uint32_t x; | |
175 | |
176 | |
177 /* set lfsr to 1 */ | |
178 x = 1; | |
179 #if debug_print | |
180 printf("%d:\t%s\n", 0, u32_bit_string(x,8)); | |
181 #endif | |
182 for (i=1; i < MAX_PERIOD; i++) { | |
183 if (x & 1) | |
184 x = (x >> 1) ^ poly; | |
185 else | |
186 x = (x >> 1); | |
187 | |
188 #if debug_print | |
189 /* print for a sanity check */ | |
190 printf("%d:\t%s\n", i, u32_bit_string(x,8)); | |
191 #endif | |
192 | |
193 /* check for return to original value */ | |
194 if (x == 1) | |
195 return i; | |
196 } | |
197 return i; | |
198 } | |
199 | |
200 /* | |
201 * weight distribution computes the weight distribution of the | |
202 * code generated by the polynomial poly | |
203 */ | |
204 | |
205 #define MAX_LEN 8 | |
206 #define MAX_WEIGHT (1 << MAX_LEN) | |
207 | |
208 int A[MAX_WEIGHT+1]; | |
209 | |
210 void | |
211 weight_distribution2(uint32_t poly, int *A) { | |
212 int i; | |
213 uint32_t x; | |
214 | |
215 /* zeroize array */ | |
216 for (i=0; i < MAX_WEIGHT+1; i++) | |
217 A[i] = 0; | |
218 | |
219 /* loop over all input sequences */ | |
220 | |
221 | |
222 /* set lfsr to 1 */ | |
223 x = 1; | |
224 #if debug_print | |
225 printf("%d:\t%s\n", 0, u32_bit_string(x,8)); | |
226 #endif | |
227 for (i=1; i < MAX_PERIOD; i++) { | |
228 if (x & 1) | |
229 x = (x >> 1) ^ poly; | |
230 else | |
231 x = (x >> 1); | |
232 | |
233 #if debug_print | |
234 /* print for a sanity check */ | |
235 printf("%d:\t%s\n", i, u32_bit_string(x,8)); | |
236 #endif | |
237 | |
238 /* increment weight */ | |
239 wt += (x & 1); | |
240 | |
241 /* check for return to original value */ | |
242 if (x == 1) | |
243 break; | |
244 } | |
245 | |
246 /* set zero */ | |
247 A[0] = 0; | |
248 } | |
249 | |
250 | |
251 void | |
252 weight_distribution(uint32_t poly, int *A) { | |
253 int i; | |
254 uint32_t x; | |
255 | |
256 /* zeroize array */ | |
257 for (i=0; i < MAX_WEIGHT+1; i++) | |
258 A[i] = 0; | |
259 | |
260 /* set lfsr to 1 */ | |
261 x = 1; | |
262 #if debug_print | |
263 printf("%d:\t%s\n", 0, u32_bit_string(x,8)); | |
264 #endif | |
265 for (i=1; i < MAX_PERIOD; i++) { | |
266 if (x & 1) | |
267 x = (x >> 1) ^ poly; | |
268 else | |
269 x = (x >> 1); | |
270 | |
271 #if debug_print | |
272 /* print for a sanity check */ | |
273 printf("%d:\t%s\n", i, u32_bit_string(x,8)); | |
274 #endif | |
275 | |
276 /* compute weight, increment proper element */ | |
277 A[weight(x)]++; | |
278 | |
279 /* check for return to original value */ | |
280 if (x == 1) | |
281 break; | |
282 } | |
283 | |
284 /* set zero */ | |
285 A[0] = 0; | |
286 } | |
287 | |
288 | |
289 | |
290 | |
291 int | |
292 main () { | |
293 | |
294 int i,j; | |
295 v32_t x; | |
296 v32_t p; | |
297 | |
298 /* originally 0xaf */ | |
299 p.value = 0x9; | |
300 | |
301 printf("polynomial: %s\tperiod: %d\n", | |
302 u32_bit_string(p.value,8), period(p.value)); | |
303 | |
304 /* compute weight distribution */ | |
305 weight_distribution(p.value, A); | |
306 | |
307 /* print weight distribution */ | |
308 for (i=0; i <= 8; i++) { | |
309 printf("A[%d]: %d\n", i, A[i]); | |
310 } | |
311 | |
312 #if 0 | |
313 for (i=0; i < 39; i++) { | |
314 printf("polynomial: %s\tperiod: %d\n", | |
315 u32_bit_string(polynomials[i],8), period(polynomials[i])); | |
316 | |
317 /* compute weight distribution */ | |
318 weight_distribution(p.value, A); | |
319 | |
320 /* print weight distribution */ | |
321 for (j=0; j <= 8; j++) { | |
322 printf("A[%d]: %d\n", j, A[j]); | |
323 } | |
324 } | |
325 #endif | |
326 | |
327 { | |
328 int bits = 8; | |
329 uint32_t y; | |
330 for (y=0; y < (1 << bits); y++) { | |
331 printf("polynomial: %s\tweight: %d\tperiod: %d\n", | |
332 u32_bit_string(y,bits), weight(y), period(y)); | |
333 | |
334 /* compute weight distribution */ | |
335 weight_distribution(y, A); | |
336 | |
337 /* print weight distribution */ | |
338 for (j=0; j <= 8; j++) { | |
339 printf("A[%d]: %d\n", j, A[j]); | |
340 } | |
341 } | |
342 } | |
343 | |
344 return 0; | |
345 } | |
OLD | NEW |