| 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 | */ |