summaryrefslogtreecommitdiff
path: root/srtp/test/lfsr.c
diff options
context:
space:
mode:
authorErwin Nindl <nine@wirdorange.org>2007-06-22 13:59:20 +0000
committerErwin Nindl <nine@wirdorange.org>2007-06-22 13:59:20 +0000
commit0275479cb56c7f562f3513fef66c83fc44d1d8c9 (patch)
treef6fbb703cebf62d18b05e2a5e7591ac08c5b6702 /srtp/test/lfsr.c
parentsatp internet draft 00 final ietf version (diff)
added libsrtp to svn
Diffstat (limited to 'srtp/test/lfsr.c')
-rw-r--r--srtp/test/lfsr.c310
1 files changed, 310 insertions, 0 deletions
diff --git a/srtp/test/lfsr.c b/srtp/test/lfsr.c
new file mode 100644
index 0000000..28ea02e
--- /dev/null
+++ b/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;
+}