1 /* 2 * lfsr.c 3 * 4 */ 5 6 7 #include <stdio.h> 8 #include "datatypes.h" 9 10 uint32_t 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 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 * 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 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 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 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 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 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
