/* Program to determine the smallest N for which a given mod-2 polynomial
   divides t^N+1.

   Author: M.V.Wickerhauser
   Date: 22 August 2002
*/

#include <stdio.h>

void
usage(const char *name, const char *msg)
{
  fprintf(stderr, "usage:  %s mod2poly \n ?? ", name);
  fputs(msg, stderr); fputc('\n', stderr);
  exit(1);
}

unsigned int least_power ( unsigned int mod2poly, int degree ) {
  unsigned int rem, mask, highbit, N;
  if(mod2poly%2==0) return 0;  /* error: t divides mod2poly */
  highbit = 0x1<<(degree-1);  mask = highbit|(highbit-1);
  for(rem=mod2poly&mask, N=degree;  rem!=0x1;  ++N )
    if( rem & highbit ) rem = ((rem<<1)^mod2poly) & mask; 
    else rem <<= 1;
  return N;
}

int
main ( int argc, char **argv )
{
  int degree;
  const char *bit;
  unsigned int mod2poly, N;

  /* Expect `mod2poly' as arg[1] on command line. */
  if(argc!=2) usage(argv[0], "Needs a bitstring for mod2poly.");

  /* Convert and store the tail bits of mod2poly */
  if(argv[1][0]!='1') usage(argv[0],"Leftmost bit of mod2poly must be 1.");
  bit = &argv[1][1];		/* all after the first bit */
  mod2poly = 1;
  degree = 0;
  while(bit[degree]) {
    mod2poly = (mod2poly<<1)|(bit[degree]=='1'? 0x1 : 0x0);
    ++degree;
  }
  if(degree<2) usage(argv[0],"need degree(mod2poly)>1.");
  if(degree>32) usage(argv[0],"need degree(mod2poly)< 33.");
  
  N = least_power(mod2poly, degree);

  printf("Mod-2 polynomial %u = %s (base 2) divides t^%u+1\n", 
	 mod2poly, argv[1], N);
  return 0;
}