diff options
Diffstat (limited to 'third_party/srtp/test/lfsr.c')
| -rw-r--r-- | third_party/srtp/test/lfsr.c | 310 |
1 files changed, 310 insertions, 0 deletions
diff --git a/third_party/srtp/test/lfsr.c b/third_party/srtp/test/lfsr.c new file mode 100644 index 00000000..28ea02eb --- /dev/null +++ b/third_party/srtp/test/lfsr.c @@ -0,0 +1,310 @@ +/* + * lfsr.c + * + */ + + +#include <stdio.h> +#include "datatypes.h" + +uint32_t +parity(uint32_t x) { + + x ^= (x >> 16); + x ^= (x >> 8); + x ^= (x >> 4); + x ^= (x >> 2); + x ^= (x >> 1); + + return x & 1; +} + + +/* typedef struct { */ +/* uint32_t register[8]; */ +/* } lfsr_t; */ + +void +compute_period(uint32_t feedback_polynomial) { + int i; + v32_t lfsr; + v32_t mask; + + mask.value = feedback_polynomial; + lfsr.value = 1; + + printf("polynomial: %s\t", v32_bit_string(mask)); + + for (i=0; i < 256; i++) { +/* printf("%s\n", v32_bit_string(lfsr)); */ + if (parity(mask.value & lfsr.value)) + lfsr.value = ((lfsr.value << 1) | 1) & 0xff; + else + lfsr.value = (lfsr.value << 1) & 0xff; + + /* now halt if we're back at the initial state */ + if (lfsr.value == 1) { + printf("period: %d\n", i); + break; + } + } +} + +uint32_t poly0 = 223; + + +uint32_t polynomials[39] = { +31, +47, +55, +59, +61, +79, +87, +91, +103, +107, +109, +115, +117, +121, +143, +151, +157, +167, +171, +173, +179, +181, +185, +199, +203, +205, +211, +213, +227, +229, +233, +241, +127, +191, +223, +239, +247, +251, +253 +}; + +char binary_string[32]; + +char * +u32_bit_string(uint32_t x, unsigned int length) { + unsigned int mask; + int index; + + mask = 1 << length; + index = 0; + for (; mask > 0; mask >>= 1) + if ((x & mask) == 0) + binary_string[index++] = '0'; + else + binary_string[index++] = '1'; + + binary_string[index++] = 0; /* NULL terminate string */ + return binary_string; +} + +extern int octet_weight[256]; + +unsigned int +weight(uint32_t poly) { + int wt = 0; + + /* note: endian-ness makes no difference */ + wt += octet_weight[poly & 0xff]; + wt += octet_weight[(poly >> 8) & 0xff]; + wt += octet_weight[(poly >> 16) & 0xff]; + wt += octet_weight[(poly >> 24)]; + + return wt; +} + +#define MAX_PERIOD 65535 + +#define debug_print 0 + +int +period(uint32_t poly) { + int i; + uint32_t x; + + + /* set lfsr to 1 */ + x = 1; +#if debug_print + printf("%d:\t%s\n", 0, u32_bit_string(x,8)); +#endif + for (i=1; i < MAX_PERIOD; i++) { + if (x & 1) + x = (x >> 1) ^ poly; + else + x = (x >> 1); + +#if debug_print + /* print for a sanity check */ + printf("%d:\t%s\n", i, u32_bit_string(x,8)); +#endif + + /* check for return to original value */ + if (x == 1) + return i; + } + return i; +} + +/* + * weight distribution computes the weight distribution of the + * code generated by the polynomial poly + */ + +#define MAX_LEN 8 +#define MAX_WEIGHT (1 << MAX_LEN) + +int A[MAX_WEIGHT+1]; + +void +weight_distribution2(uint32_t poly, int *A) { + int i; + uint32_t x; + + /* zeroize array */ + for (i=0; i < MAX_WEIGHT+1; i++) + A[i] = 0; + + /* loop over all input sequences */ + + + /* set lfsr to 1 */ + x = 1; +#if debug_print + printf("%d:\t%s\n", 0, u32_bit_string(x,8)); +#endif + for (i=1; i < MAX_PERIOD; i++) { + if (x & 1) + x = (x >> 1) ^ poly; + else + x = (x >> 1); + +#if debug_print + /* print for a sanity check */ + printf("%d:\t%s\n", i, u32_bit_string(x,8)); +#endif + + /* increment weight */ + wt += (x & 1); + + /* check for return to original value */ + if (x == 1) + break; + } + + /* set zero */ + A[0] = 0; +} + + +void +weight_distribution(uint32_t poly, int *A) { + int i; + uint32_t x; + + /* zeroize array */ + for (i=0; i < MAX_WEIGHT+1; i++) + A[i] = 0; + + /* set lfsr to 1 */ + x = 1; +#if debug_print + printf("%d:\t%s\n", 0, u32_bit_string(x,8)); +#endif + for (i=1; i < MAX_PERIOD; i++) { + if (x & 1) + x = (x >> 1) ^ poly; + else + x = (x >> 1); + +#if debug_print + /* print for a sanity check */ + printf("%d:\t%s\n", i, u32_bit_string(x,8)); +#endif + + /* compute weight, increment proper element */ + A[weight(x)]++; + + /* check for return to original value */ + if (x == 1) + break; + } + + /* set zero */ + A[0] = 0; +} + + + + +int +main () { + + int i,j; + v32_t x; + v32_t p; + + /* originally 0xaf */ + p.value = 0x9; + + printf("polynomial: %s\tperiod: %d\n", + u32_bit_string(p.value,8), period(p.value)); + + /* compute weight distribution */ + weight_distribution(p.value, A); + + /* print weight distribution */ + for (i=0; i <= 8; i++) { + printf("A[%d]: %d\n", i, A[i]); + } + +#if 0 + for (i=0; i < 39; i++) { + printf("polynomial: %s\tperiod: %d\n", + u32_bit_string(polynomials[i],8), period(polynomials[i])); + + /* compute weight distribution */ + weight_distribution(p.value, A); + + /* print weight distribution */ + for (j=0; j <= 8; j++) { + printf("A[%d]: %d\n", j, A[j]); + } + } +#endif + + { + int bits = 8; + uint32_t y; + for (y=0; y < (1 << bits); y++) { + printf("polynomial: %s\tweight: %d\tperiod: %d\n", + u32_bit_string(y,bits), weight(y), period(y)); + + /* compute weight distribution */ + weight_distribution(y, A); + + /* print weight distribution */ + for (j=0; j <= 8; j++) { + printf("A[%d]: %d\n", j, A[j]); + } + } + } + + return 0; +} |