1 /*
2 * lfsr.c
3 *
4 */
5
6
7 #include <stdio.h>
8 #include "datatypes.h"
9
10 uint32_t
parity(uint32_t x)11 parity(uint32_t x) {
12
13 x ^= (x >> 16);
14 x ^= (x >> 8);
15 x ^= (x >> 4);
16 x ^= (x >> 2);
17 x ^= (x >> 1);
18
19 return x & 1;
20 }
21
22
23 /* typedef struct { */
24 /* uint32_t register[8]; */
25 /* } lfsr_t; */
26
27 void
compute_period(uint32_t feedback_polynomial)28 compute_period(uint32_t feedback_polynomial) {
29 int i;
30 v32_t lfsr;
31 v32_t mask;
32
33 mask.value = feedback_polynomial;
34 lfsr.value = 1;
35
36 printf("polynomial: %s\t", v32_bit_string(mask));
37
38 for (i=0; i < 256; i++) {
39 /* printf("%s\n", v32_bit_string(lfsr)); */
40 if (parity(mask.value & lfsr.value))
41 lfsr.value = ((lfsr.value << 1) | 1) & 0xff;
42 else
43 lfsr.value = (lfsr.value << 1) & 0xff;
44
45 /* now halt if we're back at the initial state */
46 if (lfsr.value == 1) {
47 printf("period: %d\n", i);
48 break;
49 }
50 }
51 }
52
53 uint32_t poly0 = 223;
54
55
56 uint32_t polynomials[39] = {
57 31,
58 47,
59 55,
60 59,
61 61,
62 79,
63 87,
64 91,
65 103,
66 107,
67 109,
68 115,
69 117,
70 121,
71 143,
72 151,
73 157,
74 167,
75 171,
76 173,
77 179,
78 181,
79 185,
80 199,
81 203,
82 205,
83 211,
84 213,
85 227,
86 229,
87 233,
88 241,
89 127,
90 191,
91 223,
92 239,
93 247,
94 251,
95 253
96 };
97
98 char binary_string[32];
99
100 char *
u32_bit_string(uint32_t x,unsigned int length)101 u32_bit_string(uint32_t x, unsigned int length) {
102 unsigned int mask;
103 int index;
104
105 mask = 1 << length;
106 index = 0;
107 for (; mask > 0; mask >>= 1)
108 if ((x & mask) == 0)
109 binary_string[index++] = '0';
110 else
111 binary_string[index++] = '1';
112
113 binary_string[index++] = 0; /* NULL terminate string */
114 return binary_string;
115 }
116
117 extern int octet_weight[256];
118
119 unsigned int
weight(uint32_t poly)120 weight(uint32_t poly) {
121 int wt = 0;
122
123 /* note: endian-ness makes no difference */
124 wt += octet_weight[poly & 0xff];
125 wt += octet_weight[(poly >> 8) & 0xff];
126 wt += octet_weight[(poly >> 16) & 0xff];
127 wt += octet_weight[(poly >> 24)];
128
129 return wt;
130 }
131
132 #define MAX_PERIOD 65535
133
134 #define debug_print 0
135
136 int
period(uint32_t poly)137 period(uint32_t poly) {
138 int i;
139 uint32_t x;
140
141
142 /* set lfsr to 1 */
143 x = 1;
144 #if debug_print
145 printf("%d:\t%s\n", 0, u32_bit_string(x,8));
146 #endif
147 for (i=1; i < MAX_PERIOD; i++) {
148 if (x & 1)
149 x = (x >> 1) ^ poly;
150 else
151 x = (x >> 1);
152
153 #if debug_print
154 /* print for a sanity check */
155 printf("%d:\t%s\n", i, u32_bit_string(x,8));
156 #endif
157
158 /* check for return to original value */
159 if (x == 1)
160 return i;
161 }
162 return i;
163 }
164
165 /*
166 * weight distribution computes the weight distribution of the
167 * code generated by the polynomial poly
168 */
169
170 #define MAX_LEN 8
171 #define MAX_WEIGHT (1 << MAX_LEN)
172
173 int A[MAX_WEIGHT+1];
174
175 void
weight_distribution2(uint32_t poly,int * A)176 weight_distribution2(uint32_t poly, int *A) {
177 int i;
178 uint32_t x;
179
180 /* zeroize array */
181 for (i=0; i < MAX_WEIGHT+1; i++)
182 A[i] = 0;
183
184 /* loop over all input sequences */
185
186
187 /* set lfsr to 1 */
188 x = 1;
189 #if debug_print
190 printf("%d:\t%s\n", 0, u32_bit_string(x,8));
191 #endif
192 for (i=1; i < MAX_PERIOD; i++) {
193 if (x & 1)
194 x = (x >> 1) ^ poly;
195 else
196 x = (x >> 1);
197
198 #if debug_print
199 /* print for a sanity check */
200 printf("%d:\t%s\n", i, u32_bit_string(x,8));
201 #endif
202
203 /* increment weight */
204 wt += (x & 1);
205
206 /* check for return to original value */
207 if (x == 1)
208 break;
209 }
210
211 /* set zero */
212 A[0] = 0;
213 }
214
215
216 void
weight_distribution(uint32_t poly,int * A)217 weight_distribution(uint32_t poly, int *A) {
218 int i;
219 uint32_t x;
220
221 /* zeroize array */
222 for (i=0; i < MAX_WEIGHT+1; i++)
223 A[i] = 0;
224
225 /* set lfsr to 1 */
226 x = 1;
227 #if debug_print
228 printf("%d:\t%s\n", 0, u32_bit_string(x,8));
229 #endif
230 for (i=1; i < MAX_PERIOD; i++) {
231 if (x & 1)
232 x = (x >> 1) ^ poly;
233 else
234 x = (x >> 1);
235
236 #if debug_print
237 /* print for a sanity check */
238 printf("%d:\t%s\n", i, u32_bit_string(x,8));
239 #endif
240
241 /* compute weight, increment proper element */
242 A[weight(x)]++;
243
244 /* check for return to original value */
245 if (x == 1)
246 break;
247 }
248
249 /* set zero */
250 A[0] = 0;
251 }
252
253
254
255
256 int
main()257 main () {
258
259 int i,j;
260 v32_t x;
261 v32_t p;
262
263 /* originally 0xaf */
264 p.value = 0x9;
265
266 printf("polynomial: %s\tperiod: %d\n",
267 u32_bit_string(p.value,8), period(p.value));
268
269 /* compute weight distribution */
270 weight_distribution(p.value, A);
271
272 /* print weight distribution */
273 for (i=0; i <= 8; i++) {
274 printf("A[%d]: %d\n", i, A[i]);
275 }
276
277 #if 0
278 for (i=0; i < 39; i++) {
279 printf("polynomial: %s\tperiod: %d\n",
280 u32_bit_string(polynomials[i],8), period(polynomials[i]));
281
282 /* compute weight distribution */
283 weight_distribution(p.value, A);
284
285 /* print weight distribution */
286 for (j=0; j <= 8; j++) {
287 printf("A[%d]: %d\n", j, A[j]);
288 }
289 }
290 #endif
291
292 {
293 int bits = 8;
294 uint32_t y;
295 for (y=0; y < (1 << bits); y++) {
296 printf("polynomial: %s\tweight: %d\tperiod: %d\n",
297 u32_bit_string(y,bits), weight(y), period(y));
298
299 /* compute weight distribution */
300 weight_distribution(y, A);
301
302 /* print weight distribution */
303 for (j=0; j <= 8; j++) {
304 printf("A[%d]: %d\n", j, A[j]);
305 }
306 }
307 }
308
309 return 0;
310 }
311