test/lfsr.c

/*
 * lfsr.c
 *
 */

/*
 *	
 * Copyright (c) 2001-2006, Cisco Systems, Inc.
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 
 *   Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * 
 *   Redistributions in binary form must reproduce the above
 *   copyright notice, this list of conditions and the following
 *   disclaimer in the documentation and/or other materials provided
 *   with the distribution.
 * 
 *   Neither the name of the Cisco Systems, Inc. nor the names of its
 *   contributors may be used to endorse or promote products derived
 *   from this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
 * OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 */

#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;
}