[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[gnugo-devel] DFA code reorganization
|
From: |
Paul Pogonyshev |
|
Subject: |
[gnugo-devel] DFA code reorganization |
|
Date: |
26 Sep 2003 00:01:58 +0000 |
This patch reorganizes DFA code somewhat.
- dfa.c is now only used by `mkpat' and is no longer linked into `gnugo'
- new file `patterns/dfa-mkpat.h'
- buildSpiralOrder() moved to `transform.c' and renamed build_spiral_order()
- dfa_rotate_string() sped up
- new static function dfa_prepare_rotation_data() in `dfa.c'
I also moved several variables, including dfa_p[]. dfa_p[] size is
now 9 * (DFA_MAX_BOARD ^ 2) instead of 16 * (DFA_MAX_BOARD ^ 2).
Maybe we should consider making this an array of chars instead of an
array of ints. Can anyone predict if overhead of converting chars to
ints will be compensated by improved caching due to significant size
decrease?
No regression breakage of course.
Paul
Index: patterns/dfa.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/dfa.c,v
retrieving revision 1.33
diff -u -p -r1.33 dfa.c
--- patterns/dfa.c 30 Aug 2003 11:32:34 -0000 1.33
+++ patterns/dfa.c 25 Sep 2003 20:35:54 -0000
@@ -26,7 +26,7 @@
#include "liberty.h"
#include "patterns.h"
-#include "dfa.h"
+#include "dfa-mkpat.h"
#include "random.h"
#include <assert.h>
@@ -53,9 +53,6 @@ int dfa_verbose = 0;
* Private data *
*********************/
-/* the private board */
-int dfa_p[DFA_MAX_BOARD * 4 * DFA_MAX_BOARD * 4];
-
/* auxiliary dfa's for high level functions */
#define DFA_BINS 33 /* Number of temporary bins used to store intermediate
DFAs */
static dfa_t aux_dfa[DFA_BINS]; /* used to store intermediate DFAs */
@@ -66,14 +63,6 @@ static int dfa_was_initialized = 0;
static int aux_count = 0;
-/* convert is a table to convert the colors */
-const int convert[3][4] = {
- {-1, -1, -1, -1}, /* not used */
- {EMPTY, WHITE, BLACK, OUT_BOARD}, /* WHITE */
- {EMPTY, BLACK, WHITE, OUT_BOARD} /* BLACK */
-};
-
-
/* convert ATT_* values to the corresponding expected values on the board */
static const char att2val[8] = {
'.', 'X', 'O', 'x', 'o', ',', 'a', '!'
@@ -91,114 +80,8 @@ static void create_dfa(dfa_t *pdfa, cons
static void do_sync_product(int l, int r);
static void sync_product(dfa_t *pout, dfa_t *pleft, dfa_t *pright);
+static void dfa_prepare_rotation_data(void);
-/********************************
- * manipulating scan orders *
- ********************************/
-
-/* The spiral order is the way we scan the board,
- * we begin on the anchor and we
- * progressively scan all its neigbouring intersections,
- * collecting all the known patterns we meet on our way:
- *
- * 4 4 4
- * 1 1 13 13 513 513 ... and so on until we reach
- * 2 2 2 2 827 a stopping state in the
- * 6 dfa.
- */
-
-int spiral[MAX_ORDER][8];
-
-/*
- * Build the spiral order for each
- * transformation: instead of changing the board
- * or changing the patterns, we only change the order,
- * for eg. the same dfa can perform the pattern matching
- *
- * that way for identity:
- *
- * 765 567
- * 814F and this way for mirror symetry: F418
- * 923E E329
- * CABD DBAC
- *
- * Anther possibility is to generate one string by pattern and by
- * transformation in mkpat to avoid any runtime transformation
- * but it may increase the size of the dfa.
- *
- */
-
-static const int generator[4] = {
- 4 * DFA_MAX_BOARD, 1, -4 * DFA_MAX_BOARD, -1
-};
-
-void
-buildSpiralOrder(int order[MAX_ORDER][8])
-{
- int mark[DFA_MAX_BOARD * 4 * DFA_MAX_BOARD * 4];
- int fifo[8 * MAX_ORDER];
- int top = 0, end = 0;
- int i, j, i0, j0;
- int k, ll;
- int ii;
- int delta;
-
- if (dfa_verbose > 1)
- fprintf(stderr, "Building spiral order\n");
-
- /* First we build the basic (pseudo)spiral order */
-
- /* initialization */
-
- for (ii = 0; ii < DFA_MAX_BOARD * 4 * DFA_MAX_BOARD * 4; ii++)
- mark[ii] = 1;
-
- for (i = DFA_MAX_BOARD; i < DFA_MAX_BOARD * 3; i++)
- for (j = DFA_MAX_BOARD; j < DFA_MAX_BOARD * 3; j++)
- mark[DFA_POS(i, j)] = 0;
-
- end = 0;
- top = 1;
- fifo[end] = 2 * DFA_OFFSET;
- mark[fifo[end]] = 1;
-
- /* generation */
- while (end < MAX_ORDER) {
- ii = fifo[end];
- order[end][0] = ii - 2 * DFA_OFFSET;
- end++;
-
- for (k = 0; k != 4; k++) {
- delta = generator[k];
-
- if (!mark[ii + delta]) {
- fifo[top] = ii + delta;
- mark[ii + delta] = 1;
- top++;
- }
- }
- }
-
- /* Then we compute all the geometric transformations on this order */
- for (k = 0; k < MAX_ORDER; k++) {
- j0 = order[k][0] % (4 * DFA_MAX_BOARD);
- if (j0 >= 2 * DFA_MAX_BOARD)
- j0 -= 4 * DFA_MAX_BOARD;
- if (j0 < - 2 * DFA_MAX_BOARD)
- j0 += 4 * DFA_MAX_BOARD;
- i0 = (order[k][0] - j0) / (4 * DFA_MAX_BOARD);
- for (ll = 1; ll != 8; ll++) {
- TRANSFORM2(i0, j0, &i, &j, ll);
- order[k][ll] = DFA_POS(i, j);
- }
- }
-
- if (0) {
- for (ll = 0; ll < 8; ll++)
- for (i = 0; i < 13; i++)
- fprintf(stderr, "i:%d; ll:%d; %d(%c)\n", i, ll, order[i][ll], 'A'+i);
- }
-}
/********************************
* manipulating attributes list *
@@ -547,7 +430,7 @@ print_c_dfa(FILE *of, const char *name,
}
- fprintf(of, "\n#include \"dfa.h\"\n");
+ fprintf(of, "\n#include \"dfa-mkpat.h\"\n");
fprintf(of, "static const state_rt_t state_%s[%d] = {\n",
name, pdfa->last_state + 1);
@@ -867,20 +750,18 @@ sync_product(dfa_t *pout, dfa_t *pleft,
void
dfa_init(void)
{
- int ii;
int j;
if (dfa_verbose > 1)
fprintf(stderr, "dfa: init\n");
dfa_was_initialized++;
- buildSpiralOrder(spiral);
+
+ build_spiral_order();
+ dfa_prepare_rotation_data();
+
for (j = 0; j < DFA_BINS; j++)
new_dfa(&(aux_dfa[j]), "binAux ");
new_dfa(&aux_temp, "tempAux ");
-
- /* set the private board to OUT_BOARD */
- for (ii = 0; ii < 4 * DFA_MAX_BOARD * 4 * DFA_MAX_BOARD; ii++)
- dfa_p[ii] = OUT_BOARD;
}
void
@@ -1069,51 +950,52 @@ dfa_add_string(dfa_t *pdfa, const char *
}
-/* Create a transformation of `str' and store it in `strrot'. */
-void
-dfa_rotate_string(char *strrot, const char *str, int ll)
+/* Used for quick string rotation. */
+static int dfa_rotation_data[DFA_BASE * DFA_BASE];
+
+static void
+dfa_prepare_rotation_data(void)
{
- int i, j;
- char strdollar[MAX_ORDER+1];
+ int k;
- if (ll == 0) {
- strcpy(strrot, str);
- return;
- }
+ for (k = 0; k < DFA_MAX_ORDER; k++)
+ dfa_rotation_data[DFA_POS(0, 0) + spiral[k][0]] = k;
+}
- memset(strdollar, '$', sizeof(char) * (MAX_ORDER + 1));
- strcpy(strdollar, str);
- strdollar[strlen(str)] = '$';
- memset(strrot, '$', sizeof(char) * (MAX_ORDER + 1));
-
- for (i = 0; i < MAX_ORDER/2; i++) {
- for (j = 0; j < MAX_ORDER+1; j++) {
- if (spiral[i][0] == spiral[j][ll]) {
- if (0 && (spiral[i][0] == 84 || spiral[i][0] == -84
- || spiral[i][0]== 1 || spiral[i][0] == -1
- || spiral[j][ll] == 84 || spiral[j][ll] == -84
- || spiral[j][ll] == 1 || spiral[j][ll] == -1 ) )
- fprintf(stderr, "i: %d j: %d\n", i, j);
-
- assert(strrot[i] == '$');
- strrot[i] = strdollar[j];
- break;
+
+/* Create a transformation of `string' and store it in
+ * `rotated_string'. The latter must be of at least DFA_MAX_ORDER
+ * characters in length. */
+void
+dfa_rotate_string(char *rotated_string, const char *string, int transformation)
+{
+ if (transformation > 0) {
+ int k;
+ int length = strlen(string);
+ int new_length = 0;
+
+ memset(rotated_string, '$', DFA_MAX_ORDER);
+
+ for (k = 0; k < length; k++) {
+ if (string[k] != '$') {
+ int string_position = dfa_rotation_data[DFA_POS(0, 0)
+ + spiral[k][transformation]];
+ rotated_string[string_position] = string[k];
+ if (string_position + 1 > new_length)
+ new_length = string_position + 1;
}
}
- assert(j < MAX_ORDER+1);
+ rotated_string[new_length] = 0;
}
-
- j = MAX_ORDER;
- while (strrot[j] == '$')
- j--;
- strrot[j+1] = 0;
+ else
+ strcpy(rotated_string, string);
}
/*
- * Build a pattern string from a pattern.
- * str must refer a buffer of size greater than MAX_ORDER.
+ * Build a pattern string from a pattern. `str' must refer a buffer
+ * of size greater than DFA_MAX_ORDER.
*/
void
pattern_2_string(struct pattern *pat, struct patval_b *elements,
@@ -1129,7 +1011,7 @@ pattern_2_string(struct pattern *pat, st
n = DFA_MAX_BOARD * 2 + cj; /* position of the anchor */
assert(dfa_was_initialized);
- memset(str, 0, MAX_ORDER);
+ memset(str, 0, DFA_MAX_ORDER);
memset(work_space, '#', sizeof(work_space));
if (dfa_verbose > 0)
@@ -1235,14 +1117,14 @@ pattern_2_string(struct pattern *pat, st
*/
for (k = 0;
- (k != MAX_ORDER - 1) && ((borders > 0) || edges || to_test > 0);
+ (k != DFA_MAX_ORDER - 1) && ((borders > 0) || edges || to_test > 0);
k++) {
- j = spiral[k][0] % (4 * DFA_MAX_BOARD);
- if (j >= 2 * DFA_MAX_BOARD)
- j -= 4 * DFA_MAX_BOARD;
- if (j < - 2 * DFA_MAX_BOARD)
- j += 4 * DFA_MAX_BOARD;
- i = (spiral[k][0] - j) / (4 * DFA_MAX_BOARD);
+ j = spiral[k][0] % DFA_BASE;
+ if (j >= DFA_MAX_BOARD)
+ j -= DFA_BASE;
+ if (j <= -DFA_MAX_BOARD)
+ j += DFA_BASE;
+ i = (spiral[k][0] - j) / DFA_BASE;
if (i == pat->maxi)
borders &= ~SOUTH_EDGE;
@@ -1271,7 +1153,7 @@ pattern_2_string(struct pattern *pat, st
}
}
- assert(k < MAX_ORDER);
+ assert(k < DFA_MAX_ORDER);
str[k] = '\0'; /* end of string */
if (0 && dfa_verbose > 0)
Index: patterns/dfa.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/dfa.h,v
retrieving revision 1.25
diff -u -p -r1.25 dfa.h
--- patterns/dfa.h 30 Aug 2003 11:32:34 -0000 1.25
+++ patterns/dfa.h 25 Sep 2003 20:35:54 -0000
@@ -23,23 +23,14 @@
#ifndef _DFA_H_
#define _DFA_H_
-#include <stdio.h>
-#include <stdlib.h>
-#include <errno.h>
-#include <string.h>
-
-/********************************
- * parameters *
- ********************************/
-
-/* #define DFA_TRACE define this to trace the program */
-/* #define DFA_PARANOIAC define this to activate a lot of assert() */
-#define DFA_MAX_BOARD 21
-#define MAX_ORDER DFA_MAX_BOARD*DFA_MAX_BOARD*4
-/* maximum pattern matched at one positions */
-#define DFA_MAX_MATCHED 8*500
-#define DFA_RESIZE_STEP 20000
-#define DFA_INIT_SIZE 250
+
+#define DFA_MAX_BOARD 21
+#define DFA_MAX_ORDER ((2 * DFA_MAX_BOARD - 1) \
+ * (2 * DFA_MAX_BOARD - 1))
+#define DFA_BASE (3 * DFA_MAX_BOARD)
+#define DFA_POS(i, j) (((i) + DFA_MAX_BOARD) * DFA_BASE \
+ + ((j) + DFA_MAX_BOARD))
+
#ifndef EMPTY
#define EMPTY 0 /* . */
#define WHITE 1 /* O */
@@ -47,62 +38,31 @@
#endif
#define OUT_BOARD 3 /* # */
-/********************************
- * data types definition *
- ********************************/
-
-/* intersections */
-
-typedef unsigned short Intersection_t;
-/* attribute list */
-
-typedef struct attrib
-{
- int val;
- int next;
-} attrib_t;
+/* Maximum pattern matched at one positions. */
+#define DFA_MAX_MATCHED (8 * 500)
+/* Conversion macro. */
+#define EXPECTED_COLOR(player_c, position_c) (convert[player_c][position_c])
-/* dfa state */
-typedef struct state
-{
- int att;
- int next[4];
-} state_t;
+/* DFA spiral order. */
+extern int spiral[DFA_MAX_ORDER][8];
+void build_spiral_order(void);
-/* dfa */
-typedef struct dfa
-{
- /* file header */
- char name[80];
+/* The run-time data structures declared here are different from those
+ * used internally to build the DFA. */
- /* transition graph */
- state_t *states;
- int max_states;
- int last_state;
-
- /* attributes sets */
- attrib_t *indexes;
- int max_indexes;
- int last_index;
-} dfa_t;
-
-
-/* The run-time data structures are different from those used
- * internally to build the DFA */
-
-/* attribute list */
+/* Attribute list. */
typedef struct attrib_rt
{
short val;
short next;
} attrib_rt_t;
-/* dfa state */
+/* DFA state. */
typedef struct state_rt
{
short att;
@@ -111,179 +71,25 @@ typedef struct state_rt
typedef struct dfa_rt
{
- /* file header */
+ /* File header. */
const char name[80];
- /* transition graph */
+ /* Transition graph. */
const state_rt_t *states;
- /* attributes sets */
+ /* Attributes sets. */
const attrib_rt_t *indexes;
} dfa_rt_t;
-/* scan order */
-
#if 0
+/* Scan order. */
typedef struct
{
int i;
int j;
} order_t;
#endif
-
-
-/********************************
- * functions declaration *
- ********************************/
-
-void dfa_init(void); /* Every call to a dfa function must be done */
-void dfa_end(void); /* between calls of those 2 functions. */
-void buildSpiralOrder(int order[MAX_ORDER][8]); /* Needed by matchpat */
-
-/* basic dfa manipulation */
-void print_c_dfa(FILE *of, const char *name, dfa_t *pdfa);
-void new_dfa(dfa_t *pdfa, const char *name);
-void copy_dfa(dfa_t *p_to, dfa_t *p_from);
-void kill_dfa(dfa_t *pdfa);
-int dfa_size(dfa_t *pdfa); /* in kB */
-void save_dfa(const char *f_name, dfa_t *pdfa);
-dfa_t *load_dfa(const char *f_path, const char *f_name, dfa_t **ppdfa);
-void dfa_finalize(dfa_t *pdfa);
-void dfa_shuffle(dfa_t *pdfa);
-int dfa_minmax_delta(dfa_t *pdfa, int next_index, int isMin);
-void dump_dfa(FILE *f, dfa_t *pdfa);
-
-struct pattern;
-
-/* conversion between a gnugo pattern struct into a dfa string. */
-void pattern_2_string(struct pattern *pat, struct patval_b *elements,
- char *str, int ci, int cj);
-void dfa_rotate_string(char *strrot, const char *str, int ll);
-
-/* add a string with attribute att_val into a dfa */
-float dfa_add_string(dfa_t *pdfa, const char *str, int pattern_index, int ll);
-
-
-/* conversion macros */
-
-#define EXPECTED_COLOR(player_c, position_c) convert[player_c][position_c]
-
-/* incremental macro */
-
-#define BASE DFA_MAX_BOARD * 2
-#define DFA_POS(i, j) (4 * DFA_MAX_BOARD * (i) + (j))
-#define DFA_OFFSET DFA_POS(DFA_MAX_BOARD, DFA_MAX_BOARD)
-
-
-/********************************
- * global variables *
- ********************************/
-
-extern int dfa_verbose; /* the verbose level */
-
-
-/**************************************
- * Experimental dfa builder *
- **************************************/
-
-#define DFA_ATTRIB_BLOCK_SIZE 150000
-#define DFA_NODE_BLOCK_SIZE 50000
-
-typedef struct _dfa_attrib dfa_attrib;
-typedef struct _dfa_attrib_block dfa_attrib_block;
-typedef struct _dfa_attrib_array dfa_attrib_array;
-typedef struct _dfa_node dfa_node;
-typedef struct _dfa_node_block dfa_node_block;
-typedef struct _dfa_graph dfa_graph;
-
-struct _dfa_attrib {
- dfa_attrib *next;
- int string_index;
-};
-
-struct _dfa_attrib_block {
- dfa_attrib_block *previous;
- dfa_attrib attrib[DFA_ATTRIB_BLOCK_SIZE];
-};
-
-struct _dfa_attrib_array {
- dfa_attrib_block *last_block;
- int allocated;
-};
-
-struct _dfa_node {
- dfa_node *branch[4];
- dfa_attrib *attributes;
- dfa_attrib *passing_strings;
-};
-
-struct _dfa_node_block {
- dfa_node_block *previous;
- dfa_node node[DFA_NODE_BLOCK_SIZE];
-};
-
-struct _dfa_graph {
- int num_nodes;
- dfa_node *root;
- dfa_node_block *last_block;
- int allocated;
- dfa_attrib_array attributes;
-};
-
-
-#define DFA_HASH_BLOCK_SIZE 10000
-
-#define DFA_HASH_TABLE_SIZE 4096
-#define DFA_HASH_VALUE_1 1
-#define DFA_HASH_VALUE_2 79
-#define DFA_HASH_VALUE_3 2971
-
-typedef struct _dfa_hash_entry dfa_hash_entry;
-typedef struct _dfa_hash_block dfa_hash_block;
-
-struct _dfa_hash_entry {
- dfa_hash_entry *next;
- dfa_attrib *key;
- dfa_node *value;
-};
-
-struct _dfa_hash_block {
- dfa_hash_block *previous;
- dfa_hash_entry entry[DFA_HASH_BLOCK_SIZE];
-};
-
-
-typedef struct _dfa_pattern dfa_pattern;
-typedef struct _dfa_patterns dfa_patterns;
-
-struct _dfa_pattern {
- dfa_pattern *next;
- int num_variations;
- int current_variation;
- char *variation[8];
-};
-
-struct _dfa_patterns {
- int num_patterns;
- dfa_pattern *patterns;
- dfa_pattern *last_pattern;
- dfa_graph graph;
-};
-
-
-void dfa_graph_reset(dfa_graph *graph);
-
-void dfa_patterns_reset(dfa_patterns *patterns);
-void dfa_patterns_clear(dfa_patterns *patterns);
-void dfa_patterns_add_pattern(dfa_patterns *patterns,
- const char *string, int index);
-void dfa_patterns_set_last_pattern_variation(dfa_patterns *patterns,
- int variation);
-void dfa_patterns_select_shortest_variation(dfa_patterns *patterns);
-void dfa_patterns_build_graph(dfa_patterns *patterns);
-int * dfa_patterns_optimize_variations(dfa_patterns *patterns,
- int iterations);
#endif /* _DFA_H_ */
Index: patterns/dfa-mkpat.h
===================================================================
RCS file: patterns/dfa-mkpat.h
diff -N patterns/dfa-mkpat.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ patterns/dfa-mkpat.h 25 Sep 2003 20:36:44 -0000
@@ -0,0 +1,230 @@
+/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
+ * This is GNU Go, a Go program. Contact address@hidden, or see *
+ * http://www.gnu.org/software/gnugo/ for more information. *
+ * *
+ * Copyright 1999, 2000, 2001, 2002 and 2003 *
+ * by the Free Software Foundation. *
+ * *
+ * This program is free software; you can redistribute it and/or *
+ * modify it under the terms of the GNU General Public License as *
+ * published by the Free Software Foundation - version 2 *
+ * *
+ * This program is distributed in the hope that it will be useful, *
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of *
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
+ * GNU General Public License in file COPYING for more details. *
+ * *
+ * You should have received a copy of the GNU General Public *
+ * License along with this program; if not, write to the Free *
+ * Software Foundation, Inc., 59 Temple Place - Suite 330, *
+ * Boston, MA 02111, USA. *
+\* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
+
+#ifndef _DFA_MKPAT_H_
+#define _DFA_MKPAT_H_
+
+#include "dfa.h"
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <errno.h>
+#include <string.h>
+
+/********************************
+ * Parameters *
+ ********************************/
+
+#define DFA_RESIZE_STEP 20000
+#define DFA_INIT_SIZE 250
+
+/********************************
+ * Data types definition *
+ ********************************/
+
+/* Intersections. */
+typedef unsigned short Intersection_t;
+
+/* Attribute list. */
+typedef struct attrib
+{
+ int val;
+ int next;
+} attrib_t;
+
+
+/* DFA state. */
+typedef struct state
+{
+ int att;
+ int next[4];
+} state_t;
+
+
+/* DFA. */
+typedef struct dfa
+{
+ /* File header. */
+ char name[80];
+
+ /* Transition graph. */
+ state_t *states;
+ int max_states;
+ int last_state;
+
+ /* Attributes sets. */
+ attrib_t *indexes;
+ int max_indexes;
+ int last_index;
+} dfa_t;
+
+
+/********************************
+ * Functions declaration *
+ ********************************/
+
+void dfa_init(void); /* Every call to a DFA function must be done */
+void dfa_end(void); /* between calls to these two functions. */
+
+/* Basic DFA manipulation. */
+void print_c_dfa(FILE *of, const char *name, dfa_t *pdfa);
+void new_dfa(dfa_t *pdfa, const char *name);
+void copy_dfa(dfa_t *p_to, dfa_t *p_from);
+void kill_dfa(dfa_t *pdfa);
+int dfa_size(dfa_t *pdfa); /* in kB */
+void save_dfa(const char *f_name, dfa_t *pdfa);
+dfa_t *load_dfa(const char *f_path, const char *f_name, dfa_t **ppdfa);
+void dfa_finalize(dfa_t *pdfa);
+void dfa_shuffle(dfa_t *pdfa);
+int dfa_minmax_delta(dfa_t *pdfa, int next_index, int isMin);
+void dump_dfa(FILE *f, dfa_t *pdfa);
+
+struct pattern;
+
+/* Conversion between a GNU Go pattern struct into a DFA string. */
+void pattern_2_string(struct pattern *pat, struct patval_b *elements,
+ char *str, int ci, int cj);
+void dfa_rotate_string(char *strrot, const char *str, int ll);
+
+/* Add a string with attribute `att_val' into a DFA. */
+float dfa_add_string(dfa_t *pdfa, const char *str, int pattern_index, int ll);
+
+
+/********************************
+ * Global variables *
+ ********************************/
+
+extern int dfa_verbose; /* Verbiage level. */
+
+
+/**************************************
+ * Experimental DFA builder *
+ **************************************/
+
+#define DFA_ATTRIB_BLOCK_SIZE 150000
+#define DFA_NODE_BLOCK_SIZE 50000
+
+typedef struct _dfa_attrib dfa_attrib;
+typedef struct _dfa_attrib_block dfa_attrib_block;
+typedef struct _dfa_attrib_array dfa_attrib_array;
+typedef struct _dfa_node dfa_node;
+typedef struct _dfa_node_block dfa_node_block;
+typedef struct _dfa_graph dfa_graph;
+
+struct _dfa_attrib {
+ dfa_attrib *next;
+ int string_index;
+};
+
+struct _dfa_attrib_block {
+ dfa_attrib_block *previous;
+ dfa_attrib attrib[DFA_ATTRIB_BLOCK_SIZE];
+};
+
+struct _dfa_attrib_array {
+ dfa_attrib_block *last_block;
+ int allocated;
+};
+
+struct _dfa_node {
+ dfa_node *branch[4];
+ dfa_attrib *attributes;
+ dfa_attrib *passing_strings;
+};
+
+struct _dfa_node_block {
+ dfa_node_block *previous;
+ dfa_node node[DFA_NODE_BLOCK_SIZE];
+};
+
+struct _dfa_graph {
+ int num_nodes;
+ dfa_node *root;
+ dfa_node_block *last_block;
+ int allocated;
+ dfa_attrib_array attributes;
+};
+
+
+#define DFA_HASH_BLOCK_SIZE 10000
+
+#define DFA_HASH_TABLE_SIZE 4096
+#define DFA_HASH_VALUE_1 1
+#define DFA_HASH_VALUE_2 79
+#define DFA_HASH_VALUE_3 2971
+
+typedef struct _dfa_hash_entry dfa_hash_entry;
+typedef struct _dfa_hash_block dfa_hash_block;
+
+struct _dfa_hash_entry {
+ dfa_hash_entry *next;
+ dfa_attrib *key;
+ dfa_node *value;
+};
+
+struct _dfa_hash_block {
+ dfa_hash_block *previous;
+ dfa_hash_entry entry[DFA_HASH_BLOCK_SIZE];
+};
+
+
+typedef struct _dfa_pattern dfa_pattern;
+typedef struct _dfa_patterns dfa_patterns;
+
+struct _dfa_pattern {
+ dfa_pattern *next;
+ int num_variations;
+ int current_variation;
+ char *variation[8];
+};
+
+struct _dfa_patterns {
+ int num_patterns;
+ dfa_pattern *patterns;
+ dfa_pattern *last_pattern;
+ dfa_graph graph;
+};
+
+
+void dfa_graph_reset(dfa_graph *graph);
+
+void dfa_patterns_reset(dfa_patterns *patterns);
+void dfa_patterns_clear(dfa_patterns *patterns);
+void dfa_patterns_add_pattern(dfa_patterns *patterns,
+ const char *string, int index);
+void dfa_patterns_set_last_pattern_variation(dfa_patterns *patterns,
+ int variation);
+void dfa_patterns_select_shortest_variation(dfa_patterns *patterns);
+void dfa_patterns_build_graph(dfa_patterns *patterns);
+int * dfa_patterns_optimize_variations(dfa_patterns *patterns,
+ int iterations);
+
+
+#endif /* _DFA_MKPAT_H_ */
+
+
+/*
+ * Local Variables:
+ * tab-width: 8
+ * c-basic-offset: 2
+ * End:
+ */
Index: patterns/mkpat.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/mkpat.c,v
retrieving revision 1.124
diff -u -p -r1.124 mkpat.c
--- patterns/mkpat.c 30 Aug 2003 11:32:34 -0000 1.124
+++ patterns/mkpat.c 25 Sep 2003 20:39:11 -0000
@@ -87,7 +87,7 @@ If output file is not specified, writes
#include "gg-getopt.h"
#include "gg_utils.h"
-#include "dfa.h"
+#include "dfa-mkpat.h"
#define DB_GENERAL ((int) 'p')
@@ -612,7 +612,8 @@ find_extents(void)
static void
write_to_dfa(int index)
{
- char str[MAX_ORDER + 1], strrot[MAX_ORDER + 1];
+ char str[DFA_MAX_ORDER + 1];
+ char strrot[DFA_MAX_ORDER + 1];
assert(ci != -1 && cj != -1);
#if 0
Index: patterns/transform.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/transform.c,v
retrieving revision 1.11
diff -u -p -r1.11 transform.c
--- patterns/transform.c 18 Jul 2003 18:59:22 -0000 1.11
+++ patterns/transform.c 25 Sep 2003 20:39:11 -0000
@@ -21,6 +21,9 @@
\* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
#include "liberty.h"
+#include "dfa.h"
+
+#include <memory.h>
/* Array for use by TRANSFORM() macro. */
int transformation[MAX_OFFSET][8];
@@ -73,3 +76,98 @@ transformation_init(void)
}
}
}
+/* Spiral orders for DFA matching and building. */
+int spiral[DFA_MAX_ORDER][8];
+
+/* The spiral order is the way we scan the board, we begin on the
+ * anchor and we progressively scan all its neigbouring intersections,
+ * collecting all the known patterns we meet on our way:
+ *
+ * 4 4 4
+ * 1 1 13 13 513 513 ... and so on until we reach a
+ * 2 2 2 2 827 stopping state in the DFA.
+ * 6
+ *
+ * Build the spiral order for each transformation: instead of changing
+ * the board or changing the patterns, we only change the order. For
+ * e.g. the same DFA can perform the pattern matching
+ *
+ * That way for identity:
+ *
+ * 40 04
+ * 5139 and this way for mirror symetry: 9315
+ * 827 728
+ * 6 6
+ *
+ * Anther possibility is to generate one string by pattern and by
+ * transformation in `mkpat' to avoid any runtime transformation but
+ * it drastically increases the size of DFAs.
+ */
+void
+build_spiral_order(void)
+{
+ int i;
+ int j;
+ int k;
+ char mark[2 * DFA_MAX_BOARD + 1][2 * DFA_MAX_BOARD + 1];
+ int queue_i[DFA_MAX_ORDER];
+ int queue_j[DFA_MAX_ORDER];
+ int queue_start = 0;
+ int queue_end = 1;
+
+ static const int delta_i[4] = { 1, 0, -1, 0};
+ static const int delta_j[4] = { 0, 1, 0, -1};
+
+ /* Initialization. */
+ memset(mark, 1, sizeof(mark));
+ for (i = 1; i < 2 * DFA_MAX_BOARD; i++) {
+ for (j = 1; j < 2 * DFA_MAX_BOARD; j++)
+ mark[i][j] = 0;
+ }
+
+ queue_i[0] = DFA_MAX_BOARD;
+ queue_j[0] = DFA_MAX_BOARD;
+ mark[DFA_MAX_BOARD][DFA_MAX_BOARD] = 1;
+
+ do {
+ int transformation;
+
+ /* Transform queued coordinates and store DFA offsets in spiral[][]. */
+ for (transformation = 0; transformation < 8; transformation++) {
+ TRANSFORM2(queue_i[queue_start] - DFA_MAX_BOARD,
+ queue_j[queue_start] - DFA_MAX_BOARD,
+ &i, &j, transformation);
+ spiral[queue_start][transformation] = DFA_BASE * i + j;
+ }
+
+ for (k = 0; k < 4; k++) {
+ i = queue_i[queue_start] + delta_i[k];
+ j = queue_j[queue_start] + delta_j[k];
+
+ if (!mark[i][j]) {
+ queue_i[queue_end] = i;
+ queue_j[queue_end++] = j;
+ mark[i][j] = 1;
+ }
+ }
+ } while (++queue_start < queue_end);
+
+ if (0) {
+ int transformation;
+ for (transformation = 0; transformation < 8; transformation++) {
+ fprintf(stderr, "Transformation %d:\n", transformation);
+ for (k = 0; k < 16; k++) {
+ fprintf(stderr, "\t%d(%c); %d\n", k, 'A' + k,
+ spiral[k][transformation]);
+ }
+ }
+ }
+}
+
+
+/*
+ * Local Variables:
+ * tab-width: 8
+ * c-basic-offset: 2
+ * End:
+ */
Index: patterns/Makefile.am
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/Makefile.am,v
retrieving revision 1.22
diff -u -p -r1.22 Makefile.am
--- patterns/Makefile.am 30 Jul 2003 16:57:23 -0000 1.22
+++ patterns/Makefile.am 25 Sep 2003 20:39:15 -0000
@@ -37,9 +37,9 @@ EXTRA_DIST = $(DSP)\
read_defend.db\
oracle.db
-mkpat_SOURCES = mkpat.c transform.c
+mkpat_SOURCES = mkpat.c transform.c dfa.c
-mkpat_LDADD = libdfa.a ../utils/libutils.a
+mkpat_LDADD = ../utils/libutils.a
if DFA_ENABLED
DFAFLAGS = -D -m
@@ -58,11 +58,10 @@ extract_fuseki_SOURCES = extract_fuseki
extract_fuseki_LDADD = ../engine/libengine.a libpatterns.a\
../engine/libengine.a libpatterns.a\
../sgf/libsgf.a ../utils/libutils.a\
- libdfa.a
extract_fuseki_INCLUDES = -I$(top_srcdir)/sgf
-noinst_HEADERS = patterns.h eyes.h patlib.h dfa.h
+noinst_HEADERS = patterns.h eyes.h patlib.h dfa.h dfa-mkpat.h
GGBUILTSOURCES = conn.c patterns.c apatterns.c dpatterns.c eyes.c\
influence.c barriers.c endgame.c aa_attackpat.c\
@@ -83,10 +82,9 @@ dist-hook:
# source files in this directory get access to private prototypes
INCLUDES = -I$(top_srcdir)/engine -I$(top_srcdir)/utils -I$(top_srcdir)/sgf
-noinst_LIBRARIES = libpatterns.a libdfa.a
+noinst_LIBRARIES = libpatterns.a
-libpatterns_a_SOURCES = connections.c helpers.c $(GGBUILTSOURCES)
-libdfa_a_SOURCES = dfa.c transform.c
+libpatterns_a_SOURCES = connections.c helpers.c transform.c $(GGBUILTSOURCES)
hoshi_keima.db : $(srcdir)/hoshi_keima.sgf joseki$(EXEEXT)
./joseki JH $(srcdir)/hoshi_keima.sgf >hoshi_keima.db
Index: engine/matchpat.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/matchpat.c,v
retrieving revision 1.59
diff -u -p -r1.59 matchpat.c
--- engine/matchpat.c 30 Aug 2003 11:32:34 -0000 1.59
+++ engine/matchpat.c 25 Sep 2003 20:39:22 -0000
@@ -775,14 +775,16 @@ tree_initialize_pointers(struct tree_nod
/* Set this to show the dfa board in action */
/* #define DFA_TRACE 1 */
-/* data */
-extern int board_size;
+/* Data. */
static int dfa_board_size = -1;
-extern int dfa_p[DFA_MAX_BOARD * 4 * DFA_MAX_BOARD * 4];
-extern int spiral[MAX_ORDER][8];
+static int dfa_p[DFA_BASE * DFA_BASE];
/* This is used by the EXPECTED_COLOR macro. */
-extern const int convert[3][4];
+static const int convert[3][4] = {
+ {-1, -1, -1, -1}, /* not used */
+ {EMPTY, WHITE, BLACK, OUT_BOARD}, /* WHITE */
+ {EMPTY, BLACK, WHITE, OUT_BOARD} /* BLACK */
+};
/* Forward declarations. */
static void dfa_prepare_for_match(int color);
@@ -813,7 +815,7 @@ static void dfa_matchpat_loop(matchpat_c
void
dfa_match_init(void)
{
- buildSpiralOrder(spiral);
+ build_spiral_order();
if (owl_vital_apat_db.pdfa != NULL)
DEBUG(DEBUG_MATCHER, "owl_vital_apat --> using dfa\n");
@@ -850,36 +852,38 @@ static void
dfa_prepare_for_match(int color)
{
int i, j;
- int ii;
+ int pos;
if (dfa_board_size != board_size) {
dfa_board_size = board_size;
/* clean up the board */
- for (ii = 0; ii < 4 * DFA_MAX_BOARD * 4 * DFA_MAX_BOARD; ii++)
- dfa_p[ii] = OUT_BOARD;
+ for (pos = 0; pos < DFA_BASE * DFA_BASE; pos++)
+ dfa_p[pos] = OUT_BOARD;
}
/* copy the board */
for (i = 0; i < dfa_board_size; i++)
for (j = 0; j < dfa_board_size; j++)
- dfa_p[DFA_POS(i, j) + DFA_OFFSET] = EXPECTED_COLOR(color, BOARD(i, j));
+ dfa_p[DFA_POS(i, j)] = EXPECTED_COLOR(color, BOARD(i, j));
prepare_for_match(color);
}
#if 0
-/* debug function */
+/* Debug function. */
static void
dump_dfa_board(int m, int n)
{
int i, j;
- for (i = DFA_MAX_BOARD / 2; i < DFA_MAX_BOARD*1.5 ; i++) {
- for (j = DFA_MAX_BOARD / 2 ; j < DFA_MAX_BOARD*1.5 ; j++)
- if (i != (m+DFA_MAX_BOARD) || j != (n+DFA_MAX_BOARD))
+ for (i = 0; i < dfa_board_size ; i++) {
+ for (j = 0; j < dfa_board_size; j++) {
+ if (i != m || j != n)
fprintf(stderr, "%1d", dfa_p[DFA_POS(i, j)]);
else
fprintf(stderr, "*");
+ }
+
fprintf(stderr, "\n");
}
}
@@ -914,7 +918,7 @@ scan_for_patterns(dfa_rt_t *pdfa, int l,
row++;
} while (delta != 0); /* while not on error state */
- gg_assert(row < MAX_ORDER);
+ gg_assert(row < DFA_MAX_ORDER);
return id;
}
@@ -931,7 +935,7 @@ do_dfa_matchpat(dfa_rt_t *pdfa,
int ll; /* Iterate over transformations (rotations or reflections) */
int patterns[DFA_MAX_MATCHED + 8];
int num_matched = 0;
- int *dfa_pos = dfa_p + DFA_POS(I(anchor), J(anchor)) + DFA_OFFSET;
+ int *dfa_pos = dfa_p + DFA_POS(I(anchor), J(anchor));
/* Basic sanity checks. */
ASSERT_ON_BOARD1(anchor);
Index: interface/Makefile.am
===================================================================
RCS file: /cvsroot/gnugo/gnugo/interface/Makefile.am,v
retrieving revision 1.6
diff -u -p -r1.6 Makefile.am
--- interface/Makefile.am 1 Aug 2003 14:12:23 -0000 1.6
+++ interface/Makefile.am 25 Sep 2003 20:39:22 -0000
@@ -17,7 +17,6 @@ INCLUDES = \
LDADD = \
../engine/libengine.a \
../patterns/libpatterns.a \
- ../patterns/libdfa.a \
../sgf/libsgf.a \
../utils/libutils.a
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- [gnugo-devel] DFA code reorganization,
Paul Pogonyshev <=