1/*
2 * lfsr.c
3 *
4 */
5
6
7#include <stdio.h>
8#include "datatypes.h"
9
10uint32_t
11parity(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
27void
28compute_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
53uint32_t poly0 = 223;
54
55
56uint32_t polynomials[39] = {
5731,
5847,
5955,
6059,
6161,
6279,
6387,
6491,
65103,
66107,
67109,
68115,
69117,
70121,
71143,
72151,
73157,
74167,
75171,
76173,
77179,
78181,
79185,
80199,
81203,
82205,
83211,
84213,
85227,
86229,
87233,
88241,
89127,
90191,
91223,
92239,
93247,
94251,
95253
96};
97
98char binary_string[32];
99
100char *
101u32_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
117extern int octet_weight[256];
118
119unsigned int
120weight(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
136int
137period(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
173int A[MAX_WEIGHT+1];
174
175void
176weight_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
216void
217weight_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
256int
257main () {
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