1 /* gpmakesubwa.c 22/1/96.
2 * 31/12/98 - altered to make states of type labeled, where label is
3 * the coset rep. of coset of subgroup correspondiong to state.
4 * 6/8/98 large scale reorganisation to omit globals, etc.
5 * 5/2/98 change generators from type char to type `gen'.
6 *
7 * Build a candidate word-acceptor for those irreducible words in
8 * a shortlex automatic group that lie in a given subgroup.
9 * This will work, for example, for quasiconvex subgroups of
10 * hyperbolic groups.
11 *
12 * SYNOPSIS:
13 * gpmakesubwa [-w] [-kbprogcos/-diff1cos/-diff2cos]
14 * [-diff1/-diff2/-diff1c] [-mrl maxreducelen] [-nc nochange]
15 * [-v] [-silent] [-l] [-ms maxstates] groupname [subname]
16 *
17 * subname defaults to "sub".
18 * autgroup (or equivalents) should have been run on grouname already.
19 * groupname.subname should contain the definition of the subgroup,
20 * in the standard format.
21 *
22 * Two word-reduction routines are required, one for the group elements,
23 * and one for the cosets of the subgroup in the group.
24 * As in wordreduce, there are four possibilities for the automaton used
25 * to perform each of these reductions.
26 * However, since the group will have had its automatic structure calculated
27 * already, we always use diff_reduction for that, and do not allow
28 * rws_reduction.
29 * Input is from groupname.diff1, groupname.diff2 (default) or
30 * groupname.diff1c for the reduction in the group, and
31 * input is from groupname.wa (word-acceptor),
32 * groupname.subname.kbprog, groupname.subname.diff1,
33 * etc. for the coset reduction.
34 *
35 * The subgroup generators are input from groupname.subname, or from
36 * groupname.subname.words, if -w is called.
37 * (-w should be called after a run of gpchecksubwa has found words that
38 * should be accpeted by the subgroup word-acceptor but are not.)
39 * Output is to groupname.subname.wa.
40 *
41 * OPTIONS:
42 * -diff1/diff2/diff1c
43 * This determines which finite state automaton is used for
44 * the word-reduction in the group.
45 * The default is groupname.diff2.
46 * -kbprogcos/diff1cos/diff2cos
47 * Similar, for the coset reduction.
48 * Input from groupname.subname.kbprog, etc.
49 * -nc nochange
50 * Exit when nochange words have been added to the
51 * language of subwa, without subwa changing.
52 * Default is 64.
53 * -ms maxstates
54 * At most maxstates states are allowed in the subgroup
55 * word-acceptor being produced. Default is 32767
56 * represent words in the subgroup can be remembered.
57 * Default is 32767.
58 * -v verbose
59 * -silent no diagnostics
60 * -l/-h large/huge hash-tables (for big examples)
61 * -mrl maxreducelen
62 * To change the maximum word-length possible during reduction.
63 * Default is 4095
64 *
65 */
66
67 #include <stdio.h>
68 #include "defs.h"
69 #include "fsa.h"
70 #include "rws.h"
71 #include "hash.h"
72 #include "definitions.h"
73
74 #define MAXEQNS 32767
75 #define MAXSTATES 32767
76 #define MAXREDUCELEN 4095
77 #define NOCHANGE 64
78 #define MAXNOCHANGE 4096
79
80 static FILE *rfile, *wfile;
81
82 int (*reduce_word)(gen *w, reduction_struct *rs_rws);
83 int (*reduce_word_cos)(gen *w, reduction_struct *rs_rws);
84
85 /* Functions defined in this file */
86 static void fsa_init_subwa(fsa *subwaptr, fsa *gwaptr, gen_hash_table *coshtptr,
87 int ngens, int maxstates);
88 static int calc_inv(gen *gtestword, int ngens, int *inv, reduction_struct *rsptr);
89 static void invert_word(gen *gtestword, int *inv);
90 static int add_word_fsa(fsa *subwaptr, int ngens, int maxstates, gen *gtestword,
91 gen *costestword, char **names, gen_hash_table *coshtptr,
92 reduction_struct *rsptr);
93 static void badusage(void);
94
main(int argc,char * argv[])95 int main(int argc, char *argv[])
96 {
97 int arg, delim, numsubgens, numsubelts, nochangect, eltct, genct, aw;
98 char gpname[100], inf_wa[100], inf_gred[100], inf_cosred[100], suffix[100],
99 inf_sub[100], fsaname[100], outf[100], tempfilename[100];
100 boolean wordfile, diff1_ip, diff2_ip, diff1c_ip, open, rws_ipcos, diff1_ipcos,
101 diff2_ipcos;
102 gen_hash_table cosht;
103 gen *cosht_ptr;
104 gen gtestword[MAXREDUCELEN + 1], costestword[MAXREDUCELEN + 1];
105 int ngens, *inv;
106 int i, l, ns;
107 fsa gwa, subwa, *subgwa;
108 char **names;
109 static gen_hash_table ght;
110 rewriting_system rws, *rwsptr;
111 reduction_struct grs, cosrs;
112 int maxstates = MAXSTATES;
113 int nochange = NOCHANGE;
114
115 setbuf(stdout, (char *)0);
116 setbuf(stderr, (char *)0);
117
118 rwsptr = &rws;
119 rwsptr->maxeqns = MAXEQNS;
120 rwsptr->maxreducelen = MAXREDUCELEN;
121 rwsptr->maxreducelenset = FALSE;
122 rwsptr->inv_of = 0;
123 rwsptr->weight = 0;
124 rwsptr->level = 0;
125 rwsptr->history = 0;
126 rwsptr->slowhistory = 0;
127 rwsptr->slowhistorysp = 0;
128 rwsptr->preflen = 0;
129 rwsptr->prefno = 0;
130 rwsptr->cosets = FALSE;
131
132 gpname[0] = '\0';
133 suffix[0] = '\0';
134 arg = 1;
135 wordfile = FALSE;
136 diff1_ip = diff2_ip = diff1c_ip = rws_ipcos = diff1_ipcos = diff2_ipcos =
137 FALSE;
138 while (argc > arg) {
139 if (strcmp(argv[arg], "-w") == 0)
140 wordfile = TRUE;
141 else if (strcmp(argv[arg], "-diff1") == 0)
142 diff1_ip = TRUE;
143 else if (strcmp(argv[arg], "-diff2") == 0)
144 diff2_ip = TRUE;
145 else if (strcmp(argv[arg], "-diff1c") == 0)
146 diff1c_ip = TRUE;
147 else if (strcmp(argv[arg], "-kbprogcos") == 0)
148 rws_ipcos = TRUE;
149 else if (strcmp(argv[arg], "-diff1cos") == 0)
150 diff1_ipcos = TRUE;
151 else if (strcmp(argv[arg], "-diff2cos") == 0)
152 diff2_ipcos = TRUE;
153 else if (strcmp(argv[arg], "-silent") == 0)
154 kbm_print_level = 0;
155 else if (strcmp(argv[arg], "-v") == 0)
156 kbm_print_level = 2;
157 else if (strcmp(argv[arg], "-vv") == 0)
158 kbm_print_level = 3;
159 else if (strcmp(argv[arg], "-l") == 0)
160 kbm_large = TRUE;
161 else if (strcmp(argv[arg], "-h") == 0)
162 kbm_huge = TRUE;
163 else if (strcmp(argv[arg], "-mrl") == 0) {
164 rwsptr->maxreducelenset = TRUE;
165 arg++;
166 if (arg >= argc)
167 badusage();
168 rwsptr->maxreducelen = atoi(argv[arg]);
169 }
170 else if (strcmp(argv[arg], "-nc") == 0) {
171 arg++;
172 if (arg >= argc)
173 badusage();
174 nochange = atoi(argv[arg]);
175 }
176 else if (strcmp(argv[arg], "-ms") == 0) {
177 arg++;
178 if (arg >= argc)
179 badusage();
180 maxstates = atoi(argv[arg]);
181 }
182 else {
183 if (argv[arg][0] == '-')
184 badusage();
185 if (strcmp(suffix, ""))
186 badusage();
187 if (strcmp(gpname, "") == 0)
188 strcpy(gpname, argv[arg]);
189 else
190 strcpy(suffix, argv[arg]);
191 }
192 arg++;
193 }
194
195 if (stringlen(gpname) == 0)
196 badusage();
197
198 if (stringlen(suffix) == 0)
199 strcpy(suffix, "sub");
200 strcpy(inf_sub, gpname);
201 strcat(inf_sub, ".");
202 strcat(inf_sub, suffix);
203 strcpy(outf, inf_sub);
204 strcat(outf, ".wa");
205 if (wordfile)
206 strcat(inf_sub, ".words");
207
208 strcpy(tempfilename, inf_sub);
209 strcat(tempfilename, "temp_wa_XXX");
210
211 /* First sort out the reduction automaton and routine for the group */
212 strcpy(inf_gred, gpname);
213 if (diff1_ip)
214 strcat(inf_gred, ".diff1");
215 else if (diff2_ip)
216 strcat(inf_gred, ".diff2");
217 else if (diff1c_ip)
218 strcat(inf_gred, ".diff1c");
219 else {
220 diff2_ip = TRUE;
221 strcpy(inf_gred, gpname);
222 strcat(inf_gred, ".diff2");
223 }
224
225 if ((rfile = fopen(inf_gred, "r")) == 0) {
226 fprintf(stderr, "Cannot open file %s.\n", inf_gred);
227 exit(1);
228 }
229
230 tmalloc(grs.wd_fsa, fsa, 1)
231 fsa_read(rfile, grs.wd_fsa, DENSE, 0, 0, TRUE, fsaname);
232 fclose(rfile);
233 ngens = grs.wd_fsa->alphabet->base->size;
234 process_names(grs.wd_fsa->alphabet->base->names, ngens);
235 grs.separator = ngens + 1;
236 cosrs.separator = ngens + 1;
237 /* Set the pointers in the word-difference machine */
238 if (fsa_table_dptr_init(grs.wd_fsa) == -1)
239 exit(1);
240
241 /* Now the word-reduction machine for cosets */
242 if (strncmp(suffix, "sub", 3) == 0) {
243 strcpy(inf_cosred, gpname);
244 strcat(inf_cosred, ".cos");
245 strcat(inf_cosred, suffix + 3);
246 }
247 else {
248 strcpy(inf_cosred, gpname);
249 strcat(inf_cosred, ".");
250 strcat(inf_cosred, suffix);
251 strcat(inf_cosred, "_cos");
252 }
253
254 open = FALSE;
255 if (rws_ipcos)
256 strcat(inf_cosred, ".kbprog");
257 else if (diff1_ipcos)
258 strcat(inf_cosred, ".midiff1");
259 else if (diff2_ipcos)
260 strcat(inf_cosred, ".midiff2");
261 else {
262 strcat(inf_cosred, ".kbprog");
263 rfile = fopen(inf_cosred, "r");
264 if (rfile) {
265 rws_ipcos = TRUE;
266 open = TRUE;
267 }
268 else {
269 diff2_ipcos = TRUE;
270 strcpy(inf_cosred + stringlen(inf_cosred) - 6, "midiff2");
271 }
272 }
273
274 if (!open)
275 if ((rfile = fopen(inf_cosred, "r")) == 0) {
276 fprintf(stderr, "Cannot open file %s.\n", inf_cosred);
277 exit(1);
278 }
279
280 if (rws_ipcos) {
281 read_kbinput_simple(rfile, FALSE, rwsptr);
282 fclose(rfile);
283 tmalloc(rwsptr->reduction_fsa, fsa, 1);
284 strcpy(inf_cosred + stringlen(inf_cosred) - 6, "reduce");
285 if ((rfile = fopen(inf_cosred, "r")) == 0) {
286 fprintf(stderr, "Cannot open file %s.\n", inf_cosred);
287 exit(1);
288 }
289 fsa_read(rfile, rwsptr->reduction_fsa, DENSE, 0, 0, TRUE, fsaname);
290 fclose(rfile);
291 process_names(rws.gen_name, ngens);
292 tmalloc(rws.history, int, rws.maxreducelen + 1);
293 cosrs.rws = rwsptr;
294 }
295 else {
296 tmalloc(cosrs.wd_fsa, fsa, 1);
297 fsa_read(rfile, cosrs.wd_fsa, DENSE, 0, 0, TRUE, fsaname);
298 fclose(rfile);
299 ngens = cosrs.wd_fsa->alphabet->base->size;
300 process_names(cosrs.wd_fsa->alphabet->base->names, ngens);
301 /* Set the pointers in the word-difference machine */
302 fsa_table_dptr_init(cosrs.wd_fsa);
303 }
304
305 /* Set the generator names and the reduction algorithms. */
306 names = grs.wd_fsa->alphabet->base->names;
307 reduce_word = diff_reduce;
308 reduce_word_cos = rws_ipcos ? rws_reduce : diff_reduce_cos;
309
310 /* Now read the word-acceptor for the group */
311 strcpy(inf_wa, gpname);
312 strcat(inf_wa, ".wa");
313 if ((rfile = fopen(inf_wa, "r")) == 0) {
314 fprintf(stderr, "Cannot open file %s.\n", inf_wa);
315 exit(1);
316 }
317 fsa_read(rfile, &gwa, DENSE, 0, 0, TRUE, fsaname);
318 fclose(rfile);
319
320 /* Now we initialise the subgroup word-acceptor that we shall be building */
321 fsa_init_subwa(&subwa, &gwa, &cosht, ngens, maxstates);
322 /* Calculate inverses of G-generators */
323 tmalloc(inv, int, ngens + 1);
324 if (calc_inv(gtestword, ngens, inv, &grs) == -1)
325 exit(1);
326 /* Initialise the hash table for storing the words in the G-generators that
327 * lie in the subgroup.
328 */
329 gen_hash_init(&ght, FALSE, 0, 0, 0);
330
331 /* Now open the file containing the words that generate the subgroup,
332 * store them in the hash-table ght, and add them and their inverses to
333 * the language accepted by subwa.
334 */
335 if ((rfile = fopen(inf_sub, "r")) == 0) {
336 fprintf(stderr, "Cannot open file %s.\n", inf_sub);
337 exit(1);
338 }
339 read_ident(rfile, kbm_buffer, &delim, FALSE);
340 /* this is the name of the record containing the subgenerators */
341 if (delim != ':') {
342 fprintf(stderr, "#Input error: file must contain a record assignment\n");
343 exit(1);
344 }
345 check_next_char(rfile, '=');
346 read_ident(rfile, kbm_buffer, &delim, FALSE);
347 if (delim != '(' || strcmp(kbm_buffer, "rec") != 0) {
348 fprintf(stderr, "#Input error: file must contain a record assignment\n");
349 exit(1);
350 }
351 read_ident(rfile, kbm_buffer, &delim, FALSE);
352 if (strcmp(kbm_buffer, "subGenerators") != 0) {
353 fprintf(stderr, "Input error. 'subGenerators' list expected in subgroup "
354 "generator file.\n");
355 exit(1);
356 }
357 if (delim != ':') {
358 fprintf(stderr, "#Input error: bad 'subgens' list assignment\n");
359 exit(1);
360 }
361 check_next_char(rfile, '=');
362 check_next_char(rfile, '[');
363 numsubgens = 0;
364 numsubelts = 0;
365 do {
366 if (!read_word(rfile, gtestword, gtestword + rws.maxreducelen, &delim,
367 names, ngens, TRUE)) {
368 fprintf(stderr,
369 "#Input error: no subgroup generators or missing word.\n");
370 exit(1);
371 }
372 /* Check that it is reduced as a word in G */
373 if ((*reduce_word)(gtestword, &grs) == -1)
374 exit(1);
375 if (genstrlen(gtestword) > 0) {
376 /* Copy it into the hash-table and see if it is new */
377 genstrcpy(ght.current_ptr, gtestword);
378 if (gen_hash_locate(&ght, genstrlen(gtestword) + 1) > numsubgens) {
379 /*It is new - so add it to language of subwa */
380 numsubgens++;
381 if (add_word_fsa(&subwa, ngens, maxstates, gtestword, costestword,
382 names, &cosht, &cosrs) == -1)
383 exit(1);
384 /* Now try its inverse */
385 invert_word(gtestword, inv);
386 if ((*reduce_word)(gtestword, &grs) == -1)
387 exit(1);
388 genstrcpy(ght.current_ptr, gtestword);
389 if (gen_hash_locate(&ght, genstrlen(gtestword) + 1) > numsubgens) {
390 /*It is new - so add it to language of subwa */
391 numsubgens++;
392 if (add_word_fsa(&subwa, ngens, maxstates, gtestword, costestword,
393 names, &cosht, &cosrs) == -1)
394 exit(1);
395 }
396 }
397 }
398 } while (delim != ']');
399 fclose(rfile);
400
401 if (numsubgens * numsubgens > nochange) {
402 nochange = numsubgens * numsubgens <= MAXNOCHANGE ? numsubgens * numsubgens
403 : MAXNOCHANGE;
404 if (kbm_print_level > 1)
405 printf(" #Due to large number of subgp. gens., increasing nochange to "
406 "%d.\n",
407 nochange);
408 }
409 if (kbm_print_level > 0)
410 printf("#There are %d subgroup generators (including inverses).\n",
411 numsubgens);
412
413 /* Now we start to go through the sugroup elements stored in ght, and
414 * multiply them by the subgroup generators to get new words in the
415 * subgroup, and add them to the language of subwa.
416 * We stop after considering nochange words in the subgroup generators
417 * with no change to subwa.
418 */
419 numsubelts = numsubgens;
420 nochangect = 0;
421 for (eltct = 1; eltct <= numsubelts && nochangect < nochange; eltct++)
422 for (genct = 1; genct <= numsubgens && nochangect < nochange; genct++) {
423 genstrcpy(gtestword, gen_hash_rec(&ght, eltct));
424 genstrcat(gtestword, gen_hash_rec(&ght, genct));
425 /* Reduce it as a word in G */
426 if ((*reduce_word)(gtestword, &grs) == -1)
427 exit(1);
428 if (genstrlen(gtestword) > 0) {
429 /* Copy it into the hash-table and see if it is new */
430 genstrcpy(ght.current_ptr, gtestword);
431 if (gen_hash_locate(&ght, genstrlen(gtestword) + 1) > numsubelts) {
432 /*It is new - so add it to language of subwa */
433 numsubelts++;
434 if (kbm_print_level > 1 &&
435 ((numsubelts <= 500 && numsubelts % 100 == 0) ||
436 numsubelts % 500 == 0))
437 printf(" #Number of subgroup elements stored=%d.\n", numsubelts);
438 aw = add_word_fsa(&subwa, ngens, maxstates, gtestword, costestword,
439 names, &cosht, &cosrs);
440 if (aw == -1)
441 exit(1);
442 if (aw == 1)
443 nochangect = 0;
444 else
445 nochangect++;
446 /* Now try its inverse */
447 invert_word(gtestword, inv);
448 if ((*reduce_word)(gtestword, &grs) == -1)
449 exit(1);
450 genstrcpy(ght.current_ptr, gtestword);
451 if (gen_hash_locate(&ght, genstrlen(gtestword) + 1) > numsubgens) {
452 /*It is new - so add it to language of subwa */
453 numsubelts++;
454 if (kbm_print_level > 1 &&
455 ((numsubelts <= 500 && numsubelts % 100 == 0) ||
456 numsubelts % 500 == 0))
457 printf(" #Number of subgroup elements stored=%d.\n", numsubelts);
458 aw = add_word_fsa(&subwa, ngens, maxstates, gtestword, costestword,
459 names, &cosht, &cosrs);
460 if (aw == -1)
461 exit(1);
462 if (aw == 1)
463 nochangect = 0;
464 else
465 nochangect++;
466 }
467 }
468 }
469 }
470
471 /* record the coset reps. as labels of the states */
472 ns = subwa.states->size;
473 subwa.states->type = LABELED;
474 tmalloc(subwa.states->labels, srec, 1);
475 subwa.states->labels->size = ns;
476 subwa.states->labels->type = WORDS;
477 subwa.states->labels->alphabet_size = ngens;
478 for (i = 1; i <= ngens; i++) {
479 l = stringlen(grs.wd_fsa->alphabet->base->names[i]);
480 tmalloc(subwa.states->labels->alphabet[i], char, l + 1);
481 strcpy(subwa.states->labels->alphabet[i],
482 grs.wd_fsa->alphabet->base->names[i]);
483 }
484 tmalloc(subwa.states->setToLabels, setToLabelsType, ns + 1);
485 tmalloc(subwa.states->labels->words, gen *, ns + 1);
486 subwa.states->setToLabels[0] = 0;
487 for (i = 1; i <= ns; i++) {
488 cosht_ptr = gen_hash_rec(&cosht, i);
489 l = gen_hash_rec_len(&cosht, i);
490 tmalloc(subwa.states->labels->words[i], gen, l + 1);
491 genstrcpy(subwa.states->labels->words[i], cosht_ptr);
492 subwa.states->setToLabels[i] = i;
493 }
494 if (kbm_print_level > 1) {
495 printf(" #Initial subgroup word-acceptor with %d states computed.\n", ns);
496 printf(" #Now and-ing it with group word-acceptor.\n");
497 }
498 /* Now we "and" the subwa fsa with gwa and minimize */
499 subgwa = fsa_laband(&subwa, &gwa, DENSE, TRUE, tempfilename);
500 if (kbm_print_level > 1)
501 printf(" #Subgroup word-acceptor with %d states before minimization "
502 "computed.\n",
503 subgwa->states->size);
504 if (fsa_labeled_minimize(subgwa) == -1)
505 exit(1);
506
507 base_prefix(fsaname);
508 strcat(fsaname, ".wa");
509 wfile = fopen(outf, "w");
510 fsa_print(wfile, subgwa, fsaname);
511 fclose(wfile);
512 if (kbm_print_level > 0)
513 printf("#Subgroup word-acceptor with %d states computed.\n",
514 subgwa->states->size);
515
516 gen_hash_clear(&ght);
517 gen_hash_clear(&cosht);
518 tfree(inv);
519 fsa_clear(subgwa);
520 tfree(subgwa);
521 fsa_clear(grs.wd_fsa);
522 tfree(grs.wd_fsa);
523 if (rws_ipcos) {
524 rws_clear(&rws);
525 fsa_clear(rws.reduction_fsa);
526 tfree(rws.reduction_fsa);
527 }
528 else {
529 fsa_clear(cosrs.wd_fsa);
530 tfree(cosrs.wd_fsa);
531 }
532 exit(0);
533 }
534
535 /* Initialise the subgroup word-acceptor */
fsa_init_subwa(fsa * subwaptr,fsa * gwaptr,gen_hash_table * coshtptr,int ngens,int maxstates)536 void fsa_init_subwa(fsa *subwaptr, fsa *gwaptr, gen_hash_table *coshtptr,
537 int ngens, int maxstates)
538 {
539 int i;
540 fsa_init(subwaptr);
541
542
543 subwaptr->states->size = 1;
544
545 srec_copy(subwaptr->alphabet, gwaptr->alphabet);
546
547 subwaptr->num_initial = 1;
548 tmalloc(subwaptr->initial, int, 2);
549 subwaptr->initial[1] = 1;
550 /* The initial state is also the single accepting state */
551 subwaptr->num_accepting = 1;
552 tmalloc(subwaptr->accepting, int, 2);
553 subwaptr->accepting[1] = 1;
554
555 subwaptr->flags[DFA] = TRUE;
556 subwaptr->flags[ACCESSIBLE] = TRUE;
557
558 fsa_table_init(subwaptr->table, maxstates, ngens);
559 subwaptr->table->printing_format = DENSE;
560 for (i = 1; i <= ngens; i++)
561 set_dense_target(subwaptr->table->table_data_ptr, i, 1, 0);
562
563 /* The states of subwa will be cosets of the subgroup in G.
564 * They will be stored as G-words, specifying the minimal coset rep.
565 * These words will be stored in the hash-table *coshtptr.
566 * We initialise the word for the first state as the empty word.
567 */
568 gen_hash_init(coshtptr, FALSE, 0, 0, 0);
569 coshtptr->current_ptr[0] = '\0';
570 if (gen_hash_locate(coshtptr, 1) != 1) {
571 fprintf(stderr, "Hash-initialisation problem in fsa_init_subwa.\n");
572 exit(1);
573 }
574 }
575
576 /* Calculates inverses of generators - essentially the same as the routine
577 * calculate_inverses in ../lib/worddiff.c, but it is not convenient to
578 * use that here.
579 */
calc_inv(gen * gtestword,int ngens,int * inv,reduction_struct * rsptr)580 int calc_inv(gen *gtestword, int ngens, int *inv, reduction_struct *rsptr)
581 {
582 int i, j;
583 for (i = 1; i <= ngens; i++)
584 for (j = 1; j <= ngens; j++) {
585 gtestword[0] = i;
586 gtestword[1] = j;
587 gtestword[2] = '\0';
588 if ((*reduce_word)(gtestword, rsptr) == -1)
589 return -1;
590 if (genstrlen(gtestword) == 0) {
591 inv[i] = j;
592 break;
593 }
594 }
595 return 0;
596 }
597
598 /* Invert the word in gtestword */
invert_word(gen * gtestword,int * inv)599 void invert_word(gen *gtestword, int *inv)
600 {
601 gen *wb, *we, swap;
602 wb = gtestword;
603 we = gtestword + genstrlen(gtestword) - 1;
604 while (wb < we) {
605 swap = inv[*wb];
606 *wb = inv[*we];
607 *we = swap;
608 wb++;
609 we--;
610 }
611 if (wb == we)
612 *wb = inv[*wb];
613 }
614
615 /* Alter the fsa subwa to make it accept the word gtestword */
add_word_fsa(fsa * subwaptr,int ngens,int maxstates,gen * gtestword,gen * costestword,char ** names,gen_hash_table * coshtptr,reduction_struct * rsptr)616 int add_word_fsa(fsa *subwaptr, int ngens, int maxstates, gen *gtestword,
617 gen *costestword, char **names, gen_hash_table *coshtptr,
618 reduction_struct *rsptr)
619 {
620 int state, i, j, glen, coslen, newstate, imstate;
621 gen *cosrep, g;
622 int changed = 0;
623 int **subwa_table = subwaptr->table->table_data_ptr;
624 kbm_buffer[0] = '\0';
625 add_word_to_buffer(stdout, gtestword, names);
626 /* In case there is an error and we need to print gtestword */
627 state = 1;
628 costestword[0] = rsptr->separator;
629 costestword[1] = '\0';
630 /* We reduce the word _H*gtestword symbol by symbol, tracing it through
631 * subwa as we go.
632 */
633 glen = genstrlen(gtestword);
634 for (i = 0; i < glen; i++) {
635 coslen = genstrlen(costestword);
636 g = gtestword[i];
637 costestword[coslen] = g;
638 costestword[coslen + 1] = '\0';
639 if ((*reduce_word_cos)(costestword, rsptr) == -1)
640 return -1;
641 cosrep = costestword;
642 while (*cosrep != rsptr->separator)
643 cosrep++;
644 cosrep++;
645 /* Copy the coset-rep into the hash-table, and see if we have it already */
646 genstrcpy(coshtptr->current_ptr, cosrep);
647 newstate = gen_hash_locate(coshtptr, genstrlen(cosrep) + 1);
648 if (newstate > subwaptr->states->size) {
649 /* New state! */
650 changed = 1;
651 if (newstate > maxstates) {
652 fprintf(stderr, "Too many states in subwa - increase maxstates.\n");
653 exit(1);
654 }
655 if (kbm_print_level > 1 &&
656 ((newstate <= 500 && newstate % 100 == 0) || newstate % 500 == 0))
657 printf(" #Number of states in subwa = %d.\n", newstate);
658 for (j = 1; j <= ngens; j++)
659 set_dense_target(subwa_table, j, newstate, 0);
660 subwaptr->states->size = newstate;
661 /* should be subwaptr->states->size+1 ! */
662 }
663 if ((imstate = dense_target(subwa_table, g, state)) &&
664 imstate != newstate) {
665 fprintf(stderr, "Error tracing word: ");
666 printbuffer(stdout);
667 exit(1);
668 }
669 set_dense_target(subwa_table, g, state, newstate);
670 state = newstate;
671 }
672 if (state != 1) {
673 fprintf(stderr, "Final error tracing word: ");
674 printbuffer(stdout);
675 exit(1);
676 }
677 return changed;
678 }
679
badusage(void)680 void badusage(void)
681 {
682 fprintf(stderr, "Usage: gpmakesubwa [-w] [-kbprogcos/-diff1cos/-diff2cos]\n");
683 fprintf(stderr,
684 "\t[-diff1/-diff2/-diff1c] [-mrl maxreducelen] [-nc nochange]\n");
685 fprintf(stderr,
686 "\t[-v] [-silent] [-l] [-ms maxstates] groupname [subname]\n");
687 exit(1);
688 }
689