// Generate bit patterns and input sequences for FSM assignment
//
// Usage: ./main [-o] [-s] [nbits]
//   -o     check match and mismatch overlaps
//   -s     show FSM solutions
//   nbits  number of bits in the pattern, default = 6
//
// R. Perry, Feb 2023
//
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ZERO '0'
#define ONE  '1'

int not( int b) { return (b == ZERO) ? ONE : ZERO; }

// increment bitstring by 1, return non-zero if no overflow
int incr( char *b, int n) {
  int carry = ONE, sum;
  for( int i = n-1; i >= 0; i--) {
    sum = (b[i] != carry) ? ONE : ZERO;
    carry = (b[i] == ONE && carry == ONE) ? ONE : ZERO;
    b[i] = sum;
  }
  return (carry == ZERO);
}

// return non-zero for prefix match up to end of shorter string
int match( const char *p, const char  *b) {
  while( *p && *b) if( *p++ != *b++) return 0;
  return 1;
}

// return non-zero for mismatch overlap with match
int mismatch( const char *p, int nbits) {
  char q[BUFSIZ]; strcpy( q, p);
  for( int j = nbits-1; j > 0; --j) {
    q[j] = not(q[j]);
    for( int k = 1; q[k]; ++k) if( match( p, q+k)) return k;
    q[j] = 0;
  }
  return 0;
}

// check match and mismatch overlaps
void overlaps( const char *p, int nbits) {
  int offset; printf( "%s", p);
 // show longest suffix which matches the prefix
  for( offset = 1; offset < nbits; ++offset)
    if( match( p, p+offset) ) { printf( " %s ", p+offset); break; }
  if( offset == nbits) printf( " - ");
 // show mismatch overlap with match
  int k = mismatch( p, nbits); for( int i = 0; i < k; ++i) putchar( p[i]);
  printf( "%s\n", p);
}

// generate an input for a pattern, return 0 if skipped
int input( char *in, const char *p, int nbits, int d) {
  int offset = 0, len = 0;
  for( offset = 1; offset < nbits; ++offset) if( match( p, p+offset) ) break;
  if( offset == nbits) return 0; // skip patterns which can't have overlaps
 // let first input bit not match
  in[0] = not(p[0]); len = 1;
 // partial match
  int k = mismatch( p, nbits);
  if( k > 0) { // mismatch overlap with match
    strncpy( in+len, p, k); len += k;
  } else { // next two bits match, third bit not match
    in[1] = p[0]; in[2] = p[1]; in[3] = not(p[2]); len += 3;
  }
 // match
  strcpy( in+len, p); len += nbits;
 // overlap match
  strcpy( in+len, p+nbits-offset); len += offset;
 // two more bits not overlap
  in[len] = not(p[nbits-offset]); in[len+1] = not(p[0]); len += 2;
 // match
  strcpy( in+len, p); len += nbits;
 // one more bit not overlap
  in[len] = not(p[nbits-1]); in[len+1] = 0; len += 1;
  // printf("%s %d\n", in, partial); // debug
  // printf("%s %d\n", in, len); // debug
  return 1;
}

// generate the output for an input and pattern
void output( const char *in, const char *p, int nbits) {
  for( int i = 0; i < nbits-1; ++i) putchar(ZERO);
  for( const char *x = in, *y = in + strlen(in) - nbits + 1; x < y; ++x)
    if( strncmp( x, p, nbits) == 0) putchar(ONE); else putchar(ZERO);
  putchar('\n');
}

// show FSM solution, state number is number of pattern bits matched
void solve( const char *p, int nbits, int d) {
  int state, next, in, out, offset;
  printf( "\n#%d: %s\n cur   in  out next\n", d, p);
 // matching state transitions
  for( state = 0; state < nbits; ++state) {
    in = p[state]; out = ZERO; next = state+1;
    if( state == nbits-1) { out = ONE;
      for( offset = 1; offset < nbits; ++offset) if( match( p, p+offset) ) break;
      next = nbits - offset;
    }
    printf( "%4d %4c %4c %4d\n", state, in, out, next);
  }
 // non-matching transitions
  out = ZERO; char q[BUFSIZ];
  for( state = 0; state < nbits; ++state) {
    q[state] = in = not(p[state]); q[state+1] = 0;
    for( offset = 1; offset <= state; ++offset) if( match( p, q+offset) ) break;
    next = state + 1 - offset;
    q[state] = p[state];
    printf( "%4d %4c %4c %4d\n", state, in, out, next);
  }
}

int main( int argc, char *argv[]) {
  int oflag = 0; if( argc > 1 && strcmp( argv[1], "-o") == 0) { oflag = 1; --argc; ++argv; }
  int sflag = 0; if( argc > 1 && strcmp( argv[1], "-s") == 0) { sflag = 1; --argc; ++argv; }
  int nbits = 6; if( argc > 1) nbits = atoi( argv[1]);
  char p[BUFSIZ], in[BUFSIZ]; memset( p, ZERO, nbits); p[nbits] = 0;
  int d = 0; // decimal value of bit pattern
  do {
    if( oflag) overlaps( p, nbits);
    else if( input( in, p, nbits, d)) {
      if( sflag) solve( p, nbits, d);
      else { printf( "%s %d\n", p, d); printf("%s\n", in); output( in, p, nbits); }
    }
    ++d;
  } while( incr( p, nbits) );
}