1 /* 2 * 3 * Copyright (c) 2001-2006, Cisco Systems, Inc. 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 10 * Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 13 * Redistributions in binary form must reproduce the above 14 * copyright notice, this list of conditions and the following 15 * disclaimer in the documentation and/or other materials provided 16 * with the distribution. 17 * 18 * Neither the name of the Cisco Systems, Inc. nor the names of its 19 * contributors may be used to endorse or promote products derived 20 * from this software without specific prior written permission. 21 * 22 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 23 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 24 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 25 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 26 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, 27 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 28 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 29 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 31 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 32 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 33 * OF THE POSSIBILITY OF SUCH DAMAGE. 34 * 35 */ 36 /* 37 * lfsr.c 38 * 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 } 346
