ハードウェア構成法 ステートマシンメモ

試験にステートマシーンが出そうなので、知らないステートマシンが出たときにループを解析してくれるプログラムを書いてみました。かなりいい加減なので、正常に動くかどうかは保障しませんよw(ぉ。たぶんパターン数に対してO(n)ぐらいで動いてくれると思います(関係無w)。

入力・結果出力について

喩えは、ステートマシンの中身が

   1 #define BITNUM 5
   2 void cirfunc(char in[BITNUM],char out[BITNUM]){
   3         out[0]=not(and(in[3],in[4]));
   4         out[1]=in[0];
   5         out[2]=in[1];
   6         out[3]=in[2];
   7         out[4]=in[3];
   8 }

のとき、

00000,00001,00010,00011,00100,00101,00110,00111,01000,01001,01010,01011,01100,01101,01110,01111,10000,10001,10010,10011,10100,10101,10110,10111,11000,11001,11010,11011,11100,11101,11110,11111
10000,10000,10001,00001,10010,10010,10011,00011,10100,10100,10101,00101,10110,10110,10111,00111,11000,11000,11001,01001,11010,11010,11011,01011,11100,11100,11101,01101,11110,11110,11111,01111
---------------------------
 00001
 10000-00000
 11000-10001-00010
 11100-11001-10010-00101-01011-10111-01110
                  -00100
 11110-11101-11010-10101-01010
                  -10100-01000
                        -01001-10011-00110
 11111
 01111
 00111
 00011
---------------------------
 01101
 10110-01100
 11011
---------------------------

のような出力になります。

teststatemachine.PNG

1,2行目は状態の遷移の関係を表します。

---------------------------

で区切られているそれぞれがループで、一番左の項目がループになっており、そこにその右についている木がつながります。上の例だと、

---------------------------
ループ:00001->10000->11000->11100->11110->11111->01111->00111->00011 ->00001->...
 00001
 10000<─00000
 11000<─10001<─00010
 11100<─11001<─10010<┬00101<─01011<─10111<─01110
                       └00100
 11110<─11101<─11010<┬10101<─01010
                       └10100<┬01000
                               └01001<─10011<─00110
 11111
 01111
 00111
 00011
---------------------------
ループ:01101->10110->11011 ->01101->...
 01101
 10110<─01100
 11011
---------------------------

プログラム

パーサはC++ですが、Cです。ちょうど200行になった件。

   1 #include<stdio.h>
   2 #include<stdlib.h>
   3 
   4 /*ステートマシンのビット数*/
   5 #define BITNUM 6
   6 
   7 #define and(a,b) ((a)&(b))
   8 #define or(a,b) ((a)|(b))
   9 #define xor(a,b) ((a)^(b))
  10 #define not(a) (!(a))
  11 
  12 /*ステートマシンの内容を、各ラッチの入力と出力の関係で記述する*/
  13 /*e.g.リングカウンタ
  14 void cirfunc(char in[BITNUM],char out[BITNUM]){
  15         out[0]=not(or(in[0],or(in[1],in[2])));
  16         out[1]=in[0];
  17         out[2]=in[1];
  18         out[3]=in[2];
  19 }*/
  20 
  21 void cirfunc(char in[BITNUM],char out[BITNUM]){
  22         out[0]=not(or(in[3],or(in[4],in[5])));
  23         out[1]=in[0];
  24         out[2]=in[1];
  25         out[3]=in[2];
  26         out[4]=in[3];
  27         out[5]=in[4];
  28 }
  29 
  30 /*以下プログラム*/
  31 
  32 #define BITSIZE (1<<BITNUM)
  33 #define STRSIZE 64
  34 
  35 typedef struct tag_listnode{
  36         struct tag_listnode* nextp;
  37         int data;
  38 } listnode;
  39 
  40 void extendlist(listnode** root,int newdata){
  41         listnode *newnode=(listnode*)malloc(sizeof(listnode));
  42         newnode->data=newdata;
  43         newnode->nextp=*root;
  44         *root=newnode;
  45 }
  46 
  47 void freelist(listnode** root){
  48         listnode *delnode,*nextnode;
  49         for(delnode=*root;delnode!=NULL;delnode=nextnode){
  50                 nextnode=delnode->nextp;
  51                 free(delnode);
  52         }
  53         *root=NULL;
  54 }
  55 
  56 
  57 typedef struct tag_loopdata{
  58         int to[BITSIZE];
  59         listnode *from[BITSIZE];
  60         int b_passed[BITSIZE];
  61         int b_loop[BITSIZE];
  62 } loopdata;
  63 
  64 void initializeloopdata(loopdata* p){
  65         int i;
  66         for(i=0;i<BITSIZE;i++){
  67                 p->from[i]=NULL;
  68                 p->b_passed[i]=0;
  69                 p->b_loop[i]=0;
  70         }
  71 }
  72 
  73 void freeloopdata(loopdata* p){
  74         int i;
  75         for(i=0;i<BITSIZE;i++){
  76                 freelist(p->from+i);
  77         }
  78 }
  79 
  80 void DFS(loopdata* p,int (*f)(int)){
  81         int i,j,next,k=1;
  82         for(i=0;i<BITSIZE;i++){
  83                 if(!p->b_passed[i]){//not passed
  84                         for(j=i;!p->b_passed[j];j=next){
  85                                 next=f(j);
  86                                 p->to[j]=next;
  87                                 extendlist(p->from+next,j);
  88                                 p->b_passed[j]=k;
  89                         }
  90                         if(p->b_passed[j]==k){
  91                                 for(;!p->b_loop[j];j=f(j)){
  92                                         p->b_loop[j]=k;
  93                                 }
  94                         }
  95                         k++;
  96                 }
  97         }
  98 }
  99 
 100 void bin2arr(int n,char str[BITNUM]){
 101         int i;
 102         int fil;
 103         for(i=0;i<BITNUM;i++){
 104                 fil=BITNUM-1-i;
 105                 str[i]=((n&(1<<fil))>>fil);
 106         }
 107 }
 108 
 109 int arr2bin(char str[BITNUM]){
 110         int i,r=0;
 111         for(i=0;i<BITNUM;i++){
 112                 r=(r<<1)+str[i];
 113         }
 114         return r;
 115 }
 116 
 117 void bin2s(int n,char* str){
 118         int i;
 119         int fil;
 120         for(i=0;i<BITNUM;i++){
 121                 fil=BITNUM-1-i;
 122                 str[i]=((n&(1<<fil))>>fil)+'0';
 123         }
 124 }
 125 
 126 void printbin(int n,char* str){
 127         bin2s(n,str);
 128         str[BITNUM]='\0';
 129 }
 130 
 131 void printtree(loopdata* p,int root,int spaces,FILE *fp){
 132         listnode *node;
 133         int i,tag=spaces;
 134         int t;
 135         char str[STRSIZE];
 136         t=0;
 137         for(node=p->from[root];node!=NULL;node=node->nextp){
 138                 if(!p->b_loop[node->data]){
 139                         for(i=tag;i<spaces;i++){
 140                                 fprintf(fp," ");
 141                         }
 142                         str[0]='-';printbin(node->data,((char*)str)+1);
 143                         fprintf(fp,"%s",str);
 144                         printtree(p,node->data,spaces+strlen(str),fp);
 145                         tag=0;
 146                         t++;
 147                 }
 148         }
 149         if(t==0){
 150                 fprintf(fp,"\n");
 151         }
 152 }
 153 
 154 void printloop(loopdata* p,FILE *fp){
 155         int i,j;
 156         char str[STRSIZE];
 157         printbin(0,((char*)str));
 158         fprintf(fp,"%s",str);
 159         for(i=1;i<BITSIZE;i++){
 160                 str[0]=',';printbin(i,((char*)str)+1);
 161                 fprintf(fp,"%s",str);
 162         }
 163         fprintf(fp,"\n");
 164         printbin(p->to[0],((char*)str));
 165         fprintf(fp,"%s",str);
 166         for(i=1;i<BITSIZE;i++){
 167                 str[0]=',';printbin(p->to[i],((char*)str)+1);
 168                 fprintf(fp,"%s",str);
 169         }
 170         fprintf(fp,"\n");
 171 
 172         fprintf(fp,"---------------------------\n",str);
 173         for(i=0;i<BITSIZE;i++){
 174                 if(p->b_passed[i]&&p->b_loop[i]){
 175                         for(j=i;p->b_passed[j];j=p->to[j]){
 176                                 p->b_passed[j]=0;
 177                                 str[0]=' ';printbin(j,((char*)str)+1);
 178                                 fprintf(fp,"%s",str);
 179                                 printtree(p,j,strlen(str),fp);
 180                         }
 181                         fprintf(fp,"---------------------------\n",str);
 182                 }
 183         }
 184 }
 185 
 186 int func(int i){
 187         char in[BITNUM],out[BITNUM];
 188         bin2arr(i,in);
 189         cirfunc(in,out);
 190         return arr2bin(out);
 191 }
 192 
 193 int main(){
 194         loopdata Data,*data=&Data;
 195         initializeloopdata(data);
 196         DFS(data,func);
 197         printloop(data,stdout);
 198         freeloopdata(data);
 199         return 0;
 200 }

ハードウェア構成法/ステートマシンメモ (last edited 2009-01-28 14:51:08 by xyx)