1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
2  * This is GNU Go, a Go program. Contact gnugo@gnu.org, or see       *
3  * http://www.gnu.org/software/gnugo/ for more information.          *
4  *                                                                   *
5  * Copyright 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007,   *
6  * 2008 and 2009 by the Free Software Foundation.                    *
7  *                                                                   *
8  * This program is free software; you can redistribute it and/or     *
9  * modify it under the terms of the GNU General Public License as    *
10  * published by the Free Software Foundation - version 3             *
11  * or (at your option) any later version.                            *
12  *                                                                   *
13  * This program is distributed in the hope that it will be useful,   *
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of    *
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the     *
16  * GNU General Public License in file COPYING for more details.      *
17  *                                                                   *
18  * You should have received a copy of the GNU General Public         *
19  * License along with this program; if not, write to the Free        *
20  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,       *
21  * Boston, MA 02111, USA.                                            *
22 \* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
23 
24 #ifndef _DFA_MKPAT_H_
25 #define _DFA_MKPAT_H_
26 
27 #include "dfa.h"
28 
29 #include <stdio.h>
30 #include <stdlib.h>
31 #include <errno.h>
32 #include <string.h>
33 
34 /********************************
35  *         Parameters           *
36  ********************************/
37 
38 #define DFA_RESIZE_STEP		20000
39 #define DFA_INIT_SIZE		250
40 
41 /********************************
42  *    Data types definition     *
43  ********************************/
44 
45 /* Intersections. */
46 typedef unsigned short Intersection_t;
47 
48 /* Attribute list. */
49 typedef struct attrib
50 {
51   int val;
52   int next;
53 } attrib_t;
54 
55 
56 /* DFA state. */
57 typedef struct state
58 {
59   int att;
60   int next[4];
61 } state_t;
62 
63 
64 /* DFA. */
65 typedef struct dfa
66 {
67   /* File header. */
68   char name[80];
69 
70   /* Transition graph. */
71   state_t *states;
72   int max_states;
73   int last_state;
74 
75   /* Attributes sets. */
76   attrib_t *indexes;
77   int max_indexes;
78   int last_index;
79 } dfa_t;
80 
81 
82 /********************************
83  *    Functions declaration     *
84  ********************************/
85 
86 void dfa_init(void);		/* Every call to a DFA function must be done */
87 void dfa_end(void);		/* between calls to these two functions. */
88 
89 /* Basic DFA manipulation. */
90 void print_c_dfa(FILE *of, const char *name, dfa_t *pdfa);
91 void new_dfa(dfa_t *pdfa, const char *name);
92 void copy_dfa(dfa_t *p_to, dfa_t *p_from);
93 void kill_dfa(dfa_t *pdfa);
94 int dfa_size(dfa_t *pdfa);	/* in kB */
95 void save_dfa(const char *f_name, dfa_t *pdfa);
96 dfa_t *load_dfa(const char *f_path, const char *f_name, dfa_t **ppdfa);
97 void dfa_finalize(dfa_t *pdfa);
98 void dfa_shuffle(dfa_t *pdfa);
99 int dfa_calculate_max_matched_patterns(dfa_t *pdfa);
100 int dfa_minmax_delta(dfa_t *pdfa, int next_index, int isMin);
101 void dump_dfa(FILE *f, dfa_t *pdfa);
102 
103 struct pattern;
104 
105 /* Conversion between a GNU Go pattern struct into a DFA string. */
106 void pattern_2_string(struct pattern *pat, struct patval_b *elements,
107 		      char *str, int ci, int cj);
108 void dfa_rotate_string(char *strrot, const char *str, int ll);
109 
110 /* Add a string with attribute `att_val' into a DFA. */
111 float dfa_add_string(dfa_t *pdfa, const char *str, int pattern_index, int ll);
112 
113 
114 /********************************
115  *    Global variables          *
116  ********************************/
117 
118 extern int dfa_verbose;		/* Verbiage level. */
119 
120 
121 /**************************************
122  *	Experimental DFA builder      *
123  **************************************/
124 
125 #define DFA_ATTRIB_BLOCK_SIZE	150000
126 #define DFA_NODE_BLOCK_SIZE	 50000
127 
128 typedef struct _dfa_attrib	 dfa_attrib;
129 typedef struct _dfa_attrib_block dfa_attrib_block;
130 typedef struct _dfa_attrib_array dfa_attrib_array;
131 typedef struct _dfa_node	 dfa_node;
132 typedef struct _dfa_node_block	 dfa_node_block;
133 typedef struct _dfa_graph	 dfa_graph;
134 
135 struct _dfa_attrib {
136   dfa_attrib	   *next;
137   int		    string_index;
138 };
139 
140 struct _dfa_attrib_block {
141   dfa_attrib_block *previous;
142   dfa_attrib	    attrib[DFA_ATTRIB_BLOCK_SIZE];
143 };
144 
145 struct _dfa_attrib_array {
146   dfa_attrib_block *last_block;
147   int		    allocated;
148 };
149 
150 struct _dfa_node {
151   dfa_node	   *branch[4];
152   dfa_attrib	   *attributes;
153   dfa_attrib	   *passing_strings;
154 };
155 
156 struct _dfa_node_block {
157   dfa_node_block   *previous;
158   dfa_node	    node[DFA_NODE_BLOCK_SIZE];
159 };
160 
161 struct _dfa_graph {
162   int		    num_nodes;
163   dfa_node	   *root;
164   dfa_node_block   *last_block;
165   int		    allocated;
166   dfa_attrib_array  attributes;
167 };
168 
169 
170 #define DFA_HASH_BLOCK_SIZE	 10000
171 
172 #define DFA_HASH_TABLE_SIZE	  4096
173 #define DFA_HASH_VALUE_1	     1
174 #define DFA_HASH_VALUE_2	    79
175 #define DFA_HASH_VALUE_3	  2971
176 
177 typedef struct _dfa_hash_entry	 dfa_hash_entry;
178 typedef struct _dfa_hash_block	 dfa_hash_block;
179 
180 struct _dfa_hash_entry {
181   dfa_hash_entry   *next;
182   dfa_attrib	   *key;
183   dfa_node	   *value;
184 };
185 
186 struct _dfa_hash_block {
187   dfa_hash_block   *previous;
188   dfa_hash_entry    entry[DFA_HASH_BLOCK_SIZE];
189 };
190 
191 
192 typedef struct _dfa_pattern	 dfa_pattern;
193 typedef struct _dfa_patterns	 dfa_patterns;
194 
195 struct _dfa_pattern {
196   dfa_pattern	   *next;
197   int		    num_variations;
198   int		    current_variation;
199   char		   *variation[8];
200 };
201 
202 struct _dfa_patterns {
203   int		    num_patterns;
204   dfa_pattern	   *patterns;
205   dfa_pattern	   *last_pattern;
206   dfa_graph	    graph;
207 };
208 
209 
210 void dfa_graph_reset(dfa_graph *graph);
211 
212 void dfa_patterns_reset(dfa_patterns *patterns);
213 void dfa_patterns_clear(dfa_patterns *patterns);
214 void dfa_patterns_add_pattern(dfa_patterns *patterns,
215 			      const char *string, int index);
216 void dfa_patterns_set_last_pattern_variation(dfa_patterns *patterns,
217 					     int variation);
218 void dfa_patterns_select_shortest_variation(dfa_patterns *patterns);
219 void dfa_patterns_build_graph(dfa_patterns *patterns);
220 int *dfa_patterns_optimize_variations(dfa_patterns *patterns, int iterations);
221 
222 
223 #endif /* _DFA_MKPAT_H_ */
224 
225 
226 /*
227  * Local Variables:
228  * tab-width: 8
229  * c-basic-offset: 2
230  * End:
231  */
232