dfa.c

细胞自动机的一个源代码

#include "dfa.h"

int dfa_init(dfa_t *d, int a, int sn, int **s, int ol, int *oa) {
  int i, j, k, w;

  d->a = a;
  d->sn = sn;
  d->w = 2*a;

  w = d->w;

  d->s = (int **)malloc(sizeof(int *)*sn);
  for (i=0; i<sn; i++) {
    d->s[i] = (int *)malloc(sizeof(int)*w);

    for (j=0; j<w; j++) {
      d->s[i][j] = s[i][j];
    }
  }

  d->o = ol;
  d->oa = (int *)malloc(sizeof(int)*ol);
  for (i=0; i<ol; i++) {
    d->oa[i] = oa[i];
  }

  d->cur = 0; /* always assume start state at 0 */

  return(1);
}

void dfa_free(dfa_t *d) {
  int i, j;

  if (d) {
    if (d->s) {
      for (i=0; i<d->w; i++) {
	if (d->s[i]) {
	  free(d->s[i]);
	}
      }
      free(d->s);
    }
    if (d->oa) {
      free(d->oa);
    }
    free(d);
  }
}

void dfa_reset(dfa_t *d) {
  int i, j;

  if (d) {
    if (d->s) {
      for (i=0; i<d->w; i++) {
	if (d->s[i]) {
	  free(d->s[i]);
	}
      }
      free(d->s);
    }
    if (d->oa) {
      free(d->oa);
    }

    memset(d, 0, sizeof(dfa_t));

  }
}

int dfa_step(dfa_t *d, int inp, int *o) {
  int i, j, k;

  *o = d->s[d->cur][(inp*2)+1];
  d->cur = d->s[d->cur][inp*2];
  return(d->cur);
}

int dfa_config(dfa_t *d, FILE *fp) {
  int i, j, k;
  int sn, a, **s, o, *oa;
  char l[CA_MAX_LINE], *c;

  c = ca_readcfgl(l, fp);
  if (atoi(c) != 3) return(0);
  c = ca_readcfgl(l, fp);
  sn = atoi(c);
  c = strchr(c+1, ' ');
  a = atoi(c);

  s = (int **)malloc(sizeof(int *)*sn);
  for (i=0; i<sn; i++) {
    c = ca_readcfgl(l, fp);

    s[i] = (int *)malloc(sizeof(int)*2*a);
    for (j=0; j<(2*a); j++) {
      s[i][j] = atoi(c);
      c = strchr(c+1, ' ');
    }
  }

  o = atoi(ca_readcfgl(l, fp));
  oa = (int *)malloc(sizeof(int)*o);
  c = ca_readcfgl(l, fp);
  for (i=0; i<o; i++) {
    oa[i] = atoi(c);
    c = strchr(c+1, ' ');
  }

  dfa_init(d, a, sn, s, o, oa);

  for (i=0; i<sn; i++) {
    free(s[i]);
  }
  free(s);
  free(oa);

}

void dfa_print(dfa_t *d) {
  int i, j, k;

  printf("alphabet: %i\n", d->a);
  printf("state number: %i\n", d->sn);
  printf("dfa width: %i\n", d->w);
  printf("cur pos: %i\n", d->cur);

  printf("states:\n");
  for (i=0; i<d->sn; i++) {
    for (j=0; j<d->w; j++) {
      printf("%i ", d->s[i][j]);
    }
    printf("\n");
  }
  printf("\noutput alphbet: %i\n", d->o);
  printf("output lookup:\n");
  for (i=0; i<d->o; i++) {
    printf("%i ", d->oa[i]);
  }
  printf("\n-----\n");
}

void dfa_ca_free(dfa_ca_t *dc) {
  int i, j, k;

  if (dc) {
    if (dc->g) free(dc->g);
    if (dc->b) free(dc->b);
    if (dc->oa) free(dc->oa);
    free(dc);
  }
}

void dfa_ca_reset(dfa_ca_t *dc) {
  int i, j, k;

  if (dc) {
    if (dc->g) free(dc->g);
    if (dc->b) free(dc->b);
    if (dc->oa) free(dc->oa);
    memset(dc, 0, sizeof(dfa_ca_t));
  }
}


int dfa_ca_init(dfa_ca_t *dc, dfa_t *d, ca_t *c) {
  int i, j, k;

  dc->dfa = d;
  dc->ca = c;
  dc->g = (int *)malloc(sizeof(int)*(c->fd)*(c->wlen));
  dc->b = (int *)malloc(sizeof(int)*(c->dim + 1));
  for (i=0; i<c->dim; i++) {
    dc->b[i] = c->d[i];
  }
  dc->b[i] = c->wlen;
  dc->dim = c->dim + 1;
  dc->fd = (c->fd)*(c->wlen);

  for (i=0; i<dc->fd; i++) {
    dc->g[i] = -1;
  }

  dc->o = d->o;
  dc->oa = (int *)malloc(sizeof(int)*(d->o));
  for (i=0; i<(d->o); i++) {
    dc->oa[i] = d->oa[i];
  }

  return(1);

}

void dfa_ca_update(dfa_t *dfa, dfa_ca_t *dc, ca_t *ica) {
  int i, j, k;
  int ns, a;
  int *p, d, dpos;

  d = ica->dim;
  p = (int *)malloc(sizeof(int)*d);
  dpos = 0;

  for (i=0; i<ica->wlen; i++) {

    for (j=0; j<ica->fd; j++) {

      if ((j%ica->d[0])==0) {
	dfa->cur=0;
      }

      dfa_step(dfa, ica->ca[i][j], &a);
      dc->g[j + (i*ica->fd)] = a;

    }

  }

}



void dfa_ca_print(dfa_ca_t *dc) {
  int i, j, k;

  printf("dfa ca print\n");
  printf("dim: %i\n", dc->dim);
  printf("basises:\n");
  for (i=0; i<dc->dim; i++) {
    printf("%i ", dc->b[i]);
  }
  printf("\n");
  printf("output alphabet (%i):\n", dc->o);
  for (i=0; i<dc->o; i++) {
    printf("%i ", dc->oa[i]);
  }

  printf("g (%i):\n", dc->fd);
  for (i=0; i<dc->fd; i++) {
    printf("%i ", dc->g[i]);
  }

  printf("\ndfa: %i, ca: %i\n", dc->dfa, dc->ca);
  printf("----\n");

}

/**************************
int main(void) {
  int i, j, k;
  char fn[] = "conf/dfa/sampo.conf";
  dfa_t *dfa;
  FILE *fp;

  dfa = (dfa_t *)malloc(sizeof(dfa_t));

  fp = fopen(fn, "r");
  if (!fp) {
    printf("bad read, exiting\n");
  }
  dfa_config(dfa, fp);
  fclose(fp);

  dfa_print(dfa);

  for (i=0; i<5; i++) {

    j = dfa_step(dfa, i%2, &k);
    printf("%i: %i (%i), %i\n", i, j, dfa->cur, k);
  }

  dfa_free(dfa);

}
**************************/