1 /* dir_engine.c -- recognizer that characterizes strokes by direction
2 
3    Copyright (C) 2000 Carl Worth
4 
5    This program is free software; you can redistribute it and/or modify
6    it under the terms of the GNU General Public License as published by
7    the Free Software Foundation; either version 2, or (at your option)
8    any later version.
9 
10    This program is distributed in the hope that it will be useful,
11    but WITHOUT ANY WARRANTY; without even the implied warranty of
12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13    GNU General Public License for more details.
14 */
15 
16 #include <stdio.h>
17 #include <stdlib.h>
18 #include <errno.h>
19 #include <string.h>
20 #include <math.h>
21 
22 #include "regex_feature.h"
23 #include "dir_engine.h"
24 #include "sprintf_alloc.h"
25 #include "fixed.h"
26 
27 #ifdef DMALLOC
28 #include "dmalloc.h"
29 #endif
30 
31 /* dir_engine_funcs are defined statically in rec_engine.c
32 rec_engine_funcs_t engine_funcs =
33 {
34     dir_priv_alloc,
35     dir_priv_free,
36     dir_feature_data_alloc,
37     dir_feature_data_free,
38     dir_classify_stroke,
39     dir_classification_str_alloc,
40     dir_free_classification,
41     dir_recognize_feature
42 };
43 */
44 
45 struct seg
46 {
47     int dir;
48     int length;
49     int first_pt;
50     int last_pt;
51     struct seg *next;
52 };
53 typedef struct seg seg_t;
54 
55 struct seg_list
56 {
57     seg_t *head;
58     seg_t *tail;
59 };
60 typedef struct seg_list seg_list_t;
61 
62 struct seg_stroke
63 {
64     stroke_t *stroke;
65     seg_list_t segs;
66 };
67 typedef struct seg_stroke seg_stroke_t;
68 
69 static int seg_stroke_init(seg_stroke_t *ss, stroke_t *stroke);
70 static void seg_stroke_deinit(seg_stroke_t *ss);
71 static void seg_stroke_resolve_ambiguities(seg_stroke_t *ss);
72 static int seg_stroke_merge_identical(seg_stroke_t *ss);
73 static int seg_stroke_merge_similar(seg_stroke_t *ss);
74 static void seg_stroke_find_lengths(seg_stroke_t *ss);
75 static char *seg_stroke_str_alloc(seg_stroke_t *ss, int include_length);
76 
77 static int seg_init_from_stroke_at(seg_t *seg, stroke_t *stroke, int first, int *last_ret);
78 static void seg_deinit(seg_t *seg);
79 static int seg_dir_from_slope(int dy, int dx);
80 static int seg_dir_ambiguous(seg_t *seg);
81 static int seg_dir_adjacent(seg_t *seg, seg_t *other);
82 
83 static int seg_list_init(seg_list_t *list);
84 static void seg_list_deinit(seg_list_t *list);
85 static void seg_list_append(seg_list_t *list, seg_t *seg);
86 static void seg_list_delete_after(seg_list_t *list, seg_t *seg);
87 
88 static char dir_chars[16] = {'<', '1', '`', '3', '^', '5', '\'', '7', '>', '9', 'l', 'B', 'v', 'D', '/', 'F'};
89 #define DIR_MAX_WINDOW 27
90 static char dir_lookups[DIR_MAX_WINDOW][DIR_MAX_WINDOW] = {
91     {'*','*','*','*','*','*','*','*','*','*','*','*','*','*','*','*','*','*','*','*','*','*','*','*','*','*','*'},
92     {'*','*','*','*','*','*','*','*','*','3','3','4','4','4','4','4','5','5','*','*','*','*','*','*','*','*','*'},
93     {'*','*','*','*','*','*','*','3','3','3','3','4','4','4','4','4','5','5','5','5','*','*','*','*','*','*','*'},
94     {'*','*','*','*','*','2','2','3','3','3','3','3','4','4','4','5','5','5','5','5','6','6','*','*','*','*','*'},
95     {'*','*','*','*','2','2','2','3','3','3','3','3','4','4','4','5','5','5','5','5','6','6','6','*','*','*','*'},
96     {'*','*','*','2','2','2','2','2','3','3','3','3','4','4','4','5','5','5','5','6','6','6','6','6','*','*','*'},
97     {'*','*','*','2','2','2','2','2','2','3','3','3','4','4','4','5','5','5','6','6','6','6','6','6','*','*','*'},
98     {'*','*','1','1','1','2','2','2','2','3','3','3','4','4','4','5','5','5','6','6','6','6','7','7','7','*','*'},
99     {'*','*','1','1','1','1','2','2','2','2','3','3','3','4','5','5','5','6','6','6','6','7','7','7','7','*','*'},
100     {'*','1','1','1','1','1','1','1','2','2','2','3','3','4','5','5','6','6','6','7','7','7','7','7','7','7','*'},
101     {'*','1','1','1','1','1','1','1','1','2','2','3','3','4','5','5','6','6','7','7','7','7','7','7','7','7','*'},
102     {'*','0','0','1','1','1','1','1','1','1','1','.','.','.','.','.','7','7','7','7','7','7','7','7','8','8','*'},
103     {'*','0','0','0','0','0','0','0','1','1','1','.','.','.','.','.','7','7','7','8','8','8','8','8','8','8','*'},
104     {'*','0','0','0','0','0','0','0','0','0','0','.','.','.','.','.','8','8','8','8','8','8','8','8','8','8','*'},
105     {'*','0','0','0','0','0','0','0','F','F','F','.','.','.','.','.','9','9','9','8','8','8','8','8','8','8','*'},
106     {'*','0','0','F','F','F','F','F','F','F','F','.','.','.','.','.','9','9','9','9','9','9','9','9','8','8','*'},
107     {'*','F','F','F','F','F','F','F','F','E','E','D','D','C','B','B','A','A','9','9','9','9','9','9','9','9','*'},
108     {'*','F','F','F','F','F','F','F','E','E','E','D','D','C','B','B','A','A','A','9','9','9','9','9','9','9','*'},
109     {'*','*','F','F','F','F','E','E','E','E','D','D','D','C','B','B','B','A','A','A','A','9','9','9','9','*','*'},
110     {'*','*','F','F','F','E','E','E','E','D','D','D','C','C','C','B','B','B','A','A','A','A','9','9','9','*','*'},
111     {'*','*','*','E','E','E','E','E','E','D','D','D','C','C','C','B','B','B','A','A','A','A','A','A','*','*','*'},
112     {'*','*','*','E','E','E','E','E','D','D','D','D','C','C','C','B','B','B','B','A','A','A','A','A','*','*','*'},
113     {'*','*','*','*','E','E','E','D','D','D','D','D','C','C','C','B','B','B','B','B','A','A','A','*','*','*','*'},
114     {'*','*','*','*','*','E','E','D','D','D','D','D','C','C','C','B','B','B','B','B','A','A','*','*','*','*','*'},
115     {'*','*','*','*','*','*','*','D','D','D','D','C','C','C','C','C','B','B','B','B','*','*','*','*','*','*','*'},
116     {'*','*','*','*','*','*','*','*','*','D','D','C','C','C','C','C','B','B','*','*','*','*','*','*','*','*','*'},
117     {'*','*','*','*','*','*','*','*','*','*','*','*','*','*','*','*','*','*','*','*','*','*','*','*','*','*','*'}
118 };
119 
dir_priv_alloc(rec_engine_t * engine)120 int dir_priv_alloc(rec_engine_t *engine)
121 {
122     return 0;
123 }
124 
dir_priv_free(rec_engine_t * engine)125 void dir_priv_free(rec_engine_t *engine)
126 {
127     /* Nothing to do here */
128 }
129 
dir_feature_data_alloc(rec_engine_t * engine,char * feature_data_str)130 void *dir_feature_data_alloc(rec_engine_t *engine, char *feature_data_str)
131 {
132     void *ret_val;
133     char *s, *d;
134     char *esc_str = malloc(strlen(feature_data_str)*2 + 1);
135     if (esc_str == NULL) {
136 	fprintf(stderr, "%s: Out of memory\n", __FUNCTION__);
137 	return NULL;
138     }
139 
140     /* Escape special regexp characters */
141     s = feature_data_str;
142     d = esc_str;
143     while (*s) {
144 	if (*s == '^' || *s == '\\') {
145 	    *d++ = '\\';
146 	}
147 	*d++ = *s++;
148     }
149     *d++ = '\0';
150     ret_val = regex_feature_alloc(esc_str);
151     free(esc_str);
152 
153     return ret_val;
154 }
155 
dir_feature_data_free(rec_engine_t * engine,void * feature_data)156 void dir_feature_data_free(rec_engine_t *engine, void *feature_data)
157 {
158     regex_feature_free((regex_t *) feature_data);
159 }
160 
161 /*
162 static int find_stroke_dir_at(stroke_t *stroke, int i)
163 {
164     pt_t *pt_a, *pt_b;
165     int dx, dy;
166     int p_bits = stroke->precision_bits;
167     static int dir_lookups[3][3] = {
168 	{3, 2, 1},
169 	{4, 0, 0},
170 	{5, 6, 7}
171     };
172 
173     if (i + 1 > stroke->num_pts) {
174 	fprintf(stderr, "%s: ERROR: argument i=%d invalid for stroke->num_pts=%d\n",
175 		__FUNCTION__, i, stroke->num_pts);
176 	return 0;
177     }
178 
179     pt_a = &stroke->pts[i];
180     pt_b = &stroke->pts[i+1];
181     dx = fixed_to_i_round(pt_b->x - pt_a->x, p_bits);
182     dy = fixed_to_i_round(pt_b->y - pt_a->y, p_bits);
183 
184     if (abs(dx) > 1 || abs(dy) > 1) {
185 	fprintf(stderr, "%s: ERROR: interval from (%d, %d) - (%d, %d) has Manhattan distance > 2\n",
186 		__FUNCTION__,
187 		fixed_to_i_round(pt_a->x, p_bits),
188 		fixed_to_i_round(pt_a->y, p_bits),
189 		fixed_to_i_round(pt_b->x, p_bits),
190 		fixed_to_i_round(pt_b->y, p_bits));
191 	return 0;
192     }
193 
194     return dir_lookups[dy+1][dx+1];
195 }
196 */
197 
dir_classify_stroke(rec_engine_t * engine,stroke_t * stroke)198 void dir_classify_stroke(rec_engine_t *engine, stroke_t *stroke)
199 {
200     seg_stroke_t seg_stroke;
201 
202     seg_stroke_init(&seg_stroke, stroke);
203     seg_stroke_resolve_ambiguities(&seg_stroke);
204     stroke->classifications[engine->num] = seg_stroke_str_alloc(&seg_stroke, 0);
205     seg_stroke_deinit(&seg_stroke);
206 }
207 
dir_length_classify_stroke(rec_engine_t * engine,stroke_t * stroke)208 void dir_length_classify_stroke(rec_engine_t *engine, stroke_t *stroke)
209 {
210     seg_stroke_t seg_stroke;
211 
212     seg_stroke_init(&seg_stroke, stroke);
213     seg_stroke_resolve_ambiguities(&seg_stroke);
214     stroke->classifications[engine->num] = seg_stroke_str_alloc(&seg_stroke, 1);
215     seg_stroke_deinit(&seg_stroke);
216 }
217 
seg_stroke_init(seg_stroke_t * ss,stroke_t * stroke)218 int seg_stroke_init(seg_stroke_t *ss, stroke_t *stroke)
219 {
220     int err;
221     int first = 0, last = 0;
222     seg_t *seg;
223 
224     ss->stroke = stroke;
225     seg_list_init(&ss->segs);
226 
227     while(1) {
228 	seg = malloc(sizeof(seg_t));
229 	if (seg == NULL) {
230 	    fprintf(stderr, "%s: out of memory\n", __FUNCTION__);
231 	    break;
232 	}
233 	err = seg_init_from_stroke_at(seg, stroke, first, &last);
234 	if (err) {
235 	    if (last < stroke->num_pts) {
236 		fprintf(stderr, "%s: An error occurred during seg_init_from_stroke_at\n",
237 			__FUNCTION__);
238 		return EINVAL;
239 	    } else {
240 		/* XXX: For now, ignore errors on the last segment. It
241                    was probably just too short to register as anything
242                    ambiguous. Technically, we are throwing away stroke
243                    information here, which is bad. But it's probably
244                    no that much information. One partial solution
245                    would be to just merge these last few points in
246                    with the previous segment, (that would at least
247                    preserve the extra bit of length information). */
248 		break;
249 	    }
250 	}
251 	seg_list_append(&ss->segs, seg);
252 	if (last >= stroke->num_pts) {
253 	    break;
254 	}
255 	first = last;
256     }
257 
258     return 0;
259 }
260 
seg_stroke_deinit(seg_stroke_t * ss)261 static void seg_stroke_deinit(seg_stroke_t *ss)
262 {
263     ss->stroke = NULL;
264     seg_list_deinit(&ss->segs);
265 }
266 
seg_list_init(seg_list_t * list)267 static int seg_list_init(seg_list_t *list)
268 {
269     list->head = NULL;
270     list->tail = NULL;
271 
272     return 0;
273 }
274 
seg_list_deinit(seg_list_t * list)275 static void seg_list_deinit(seg_list_t *list)
276 {
277     seg_t *next;
278 
279     while (list->head) {
280 	next = list->head->next;
281 	seg_deinit(list->head);
282 	free(list->head);
283 	list->head = next;
284     }
285     list->tail = NULL;
286 }
287 
288 
seg_list_append(seg_list_t * list,seg_t * seg)289 static void seg_list_append(seg_list_t *list, seg_t *seg)
290 {
291     if (list->head == NULL) {
292 	list->head = seg;
293     }
294     if (list->tail) {
295 	list->tail->next = seg;
296     }
297     list->tail = seg;
298 }
299 
300 
seg_list_delete_after(seg_list_t * list,seg_t * seg)301 static void seg_list_delete_after(seg_list_t *list, seg_t *seg)
302 {
303     seg_t *to_delete;
304 
305     to_delete = seg->next;
306     if (to_delete == NULL) {
307 	return;
308     }
309 
310     seg->next = to_delete->next;
311     if (list->tail == to_delete) {
312 	list->tail = seg;
313     }
314 
315     seg_deinit(to_delete);
316     free(to_delete);
317 }
318 
319 
seg_list_delete(seg_list_t * list,seg_t * seg)320 static void seg_list_delete(seg_list_t *list, seg_t *seg)
321 {
322     seg_t *prev;
323 
324     if (seg == list->head) {
325 	if (list->tail == list->head) {
326 	    list->tail = NULL;
327 	}
328 	list->head = list->head->next;
329 	seg_deinit(seg);
330 	free(seg);
331     } else {
332 	prev = list->head;
333 	while (prev && prev->next != seg) {
334 	    prev = prev->next;
335 	}
336 	if (prev == NULL) {
337 	    fprintf(stderr, "%s: Error: Can't delete seg which does not appear in list.\n", __FUNCTION__);
338 	}
339 	seg_list_delete_after(list, prev);
340     }
341 }
342 
seg_stroke_resolve_ambiguities(seg_stroke_t * ss)343 static void seg_stroke_resolve_ambiguities(seg_stroke_t *ss)
344 {
345     int changes;
346 
347     do {
348 	changes = 0;
349 	changes += seg_stroke_merge_identical(ss);
350 	changes += seg_stroke_merge_similar(ss);
351     } while (changes);
352 }
353 
seg_stroke_merge_similar(seg_stroke_t * ss)354 static int seg_stroke_merge_similar(seg_stroke_t *ss)
355 {
356     seg_t *seg, *prev, *next;
357     pt_t *pts = ss->stroke->pts;
358     int changes = 0;
359 
360     seg = ss->segs.head;
361     prev = NULL;
362     while (seg) {
363 	next = seg->next;
364 	if (seg_dir_ambiguous(seg)) {
365 	    int split_to_prev = 0, split_to_next = 0;
366 	    if (prev && seg_dir_adjacent(seg, prev)) {
367 		split_to_prev = 1;
368 	    }
369 	    if (next && seg_dir_adjacent(seg, next)) {
370 		split_to_next = 1;
371 	    }
372 	    switch (2 * split_to_prev + split_to_next) {
373 	    case 0:
374 	    {
375 		/* No clues from neighbors, fall back to a closer look at slope */
376 		int dy = pts[seg->last_pt].y - pts[seg->first_pt].y;
377 		int dx = pts[seg->last_pt].x - pts[seg->first_pt].x;
378 		seg->dir = seg_dir_from_slope(dy, dx);
379 		break;
380 	    }
381 	    case 1:
382 		next->first_pt = seg->first_pt;
383 		seg_list_delete(&ss->segs, seg);
384 		seg = prev;
385 		changes++;
386 		break;
387 	    case 2:
388 		prev->last_pt = seg->last_pt;
389 		seg_list_delete(&ss->segs, seg);
390 		seg = prev;
391 		changes++;
392 		break;
393 	    case 3:
394 	    {
395 		int mid = seg->first_pt + (seg->last_pt - seg->first_pt) / 2;
396 		prev->last_pt = mid;
397 		next->first_pt = mid + 1;
398 		seg_list_delete(&ss->segs, seg);
399 		seg = prev;
400 		changes++;
401 		break;
402 	    }
403 	    }
404 	}
405 	prev = seg;
406 	seg = next;
407     }
408 
409     return changes;
410 }
411 
seg_stroke_merge_identical(seg_stroke_t * ss)412 static int seg_stroke_merge_identical(seg_stroke_t *ss)
413 {
414     seg_t *seg;
415     int merged = 0;
416 
417     seg = ss->segs.head;
418     while (seg && seg->next) {
419 	if (seg->dir == seg->next->dir) {
420 	    seg->last_pt = seg->next->last_pt;
421 	    seg_list_delete_after(&ss->segs, seg);
422 	    merged++;
423 	    continue;
424 	}
425 	seg = seg->next;
426     }
427 
428     return merged;
429 }
430 
seg_stroke_find_lengths(seg_stroke_t * ss)431 static void seg_stroke_find_lengths(seg_stroke_t *ss)
432 {
433     seg_t *seg;
434     pt_t *pts = ss->stroke->pts;
435     pt_t *pt_first, *pt_last;
436     int dy, dx;
437     int p_bits = ss->stroke->precision_bits;
438 
439     for (seg = ss->segs.head; seg; seg = seg->next) {
440 	pt_first = &pts[seg->first_pt];
441 	pt_last = &pts[seg->last_pt];
442 	dx = fixed_to_i_round(pt_last->x - pt_first->x, p_bits);
443 	dy = fixed_to_i_round(pt_last->y - pt_first->y, p_bits);
444 	seg->length = sqrt(dx*dx + dy*dy);
445     }
446 }
447 
seg_stroke_str_alloc(seg_stroke_t * ss,int include_length)448 static char *seg_stroke_str_alloc(seg_stroke_t *ss, int include_length)
449 {
450     int num_segs;
451     seg_t *seg;
452     char *str, *p;
453     int str_max;
454 
455     num_segs = 0;
456     for (seg = ss->segs.head; seg; seg = seg->next) {
457 	num_segs++;
458     }
459 
460     if (include_length) {
461 	seg_stroke_find_lengths(ss);
462 	str_max = num_segs * 7 + 1;
463     } else {
464 	str_max = num_segs + 1;
465     }
466     str = malloc(str_max);
467     if (str == NULL) {
468 	char *stroke_str;
469 	fprintf(stderr, "%s: out of memory (Failed to malloc %u bytes).\n",\
470 		__FUNCTION__, str_max);
471 	stroke_str = stroke_str_alloc(ss->stroke);
472 	fprintf(stderr, "%s: Here's the offending stroke: %s\n",
473 		__FUNCTION__, stroke_str);
474 	free(stroke_str);
475 	return NULL;
476     }
477 
478     p = str;
479     for (seg = ss->segs.head; seg; seg = seg->next) {
480 	*p++ = dir_chars[seg->dir];
481 	if (include_length) {
482 	    p += sprintf(p, "(%d)", seg->length);
483 	}
484     }
485     *p = '\0';
486 
487     return str;
488 }
489 
seg_init_from_stroke_at(seg_t * seg,stroke_t * stroke,int first,int * last_ret)490 static int seg_init_from_stroke_at(seg_t *seg, stroke_t *stroke, int first, int *last_ret)
491 {
492     int last;
493     int dx, dy;
494     pt_t *pt_first, *pt_last;
495     int p_bits = stroke->precision_bits;
496     int center = DIR_MAX_WINDOW / 2;
497     char dir;
498 
499     seg->next = NULL;
500     seg->first_pt = first;
501 
502     pt_first = &stroke->pts[first];
503 
504     seg->dir = -1;
505     for (last = first + 1; last < stroke->num_pts; last++) {
506 	pt_last = &stroke->pts[last];
507 	dx = fixed_to_i_round(pt_last->x - pt_first->x, p_bits);
508 	dy = fixed_to_i_round(pt_last->y - pt_first->y, p_bits);
509 	if (abs(dx) > center || abs(dy) > center) {
510 	    fprintf(stderr, "%s: Error: Distance from pts[%d] (%d, %d) -> pts[%d] (%d, %d) exceeeds %d in one or both dimensions.\n",		    __FUNCTION__,
511 		    first,
512 		    fixed_to_i_round(pt_first->x, p_bits),
513 		    fixed_to_i_round(pt_first->y, p_bits),
514 		    last,
515 		    fixed_to_i_round(pt_last->x, p_bits),
516 		    fixed_to_i_round(pt_last->y, p_bits),
517 		    center);
518 	    break;
519 	}
520 	dir = dir_lookups[center + dy][center + dx];
521 	if (dir == '*') {
522 	    break;
523 	} else if (dir != '.') {
524 	    if (dir >= '0' && dir <= '9') {
525 		seg->dir = dir - '0';
526 	    } else if (dir >= 'A' && dir <= 'F') {
527 		seg->dir = 10 + dir - 'A';
528 	    } else {
529 		fprintf(stderr, "%s: Unexpected character `%c' found in dir_lookups table\n", __FUNCTION__, dir);
530 		break;
531 	    }
532 	    if (seg_dir_ambiguous(seg) == 0) {
533 		last++;
534 		break;
535 	    }
536 	}
537     }
538     *last_ret = last;
539 
540     seg->last_pt = last - 1;
541     if (seg->dir == -1) {
542 	return EINVAL;
543     } else {
544 	return 0;
545     }
546 }
547 
seg_dir_from_slope(int dy,int dx)548 static int seg_dir_from_slope(int dy, int dx)
549 {
550     static double dir_thresholds[8] = {
551 	-M_PI + 2 * M_PI * ( 1.0) / 16.0,
552 	-M_PI + 2 * M_PI * ( 3.0) / 16.0,
553 	-M_PI + 2 * M_PI * ( 5.0) / 16.0,
554 	-M_PI + 2 * M_PI * ( 7.0) / 16.0,
555 	-M_PI + 2 * M_PI * ( 9.0) / 16.0,
556 	-M_PI + 2 * M_PI * (11.0) / 16.0,
557 	-M_PI + 2 * M_PI * (13.0) / 16.0,
558 	-M_PI + 2 * M_PI * (15.0) / 16.0
559     };
560     int d;
561     double slope = atan2(dy, dx);
562 
563     for (d = 0; d < 8; d++) {
564 	if (dir_thresholds[d] > slope) {
565 	    break;
566 	}
567     }
568 
569     return 2 * d;
570 }
571 
seg_dir_ambiguous(seg_t * seg)572 static int seg_dir_ambiguous(seg_t *seg)
573 {
574     return seg->dir % 2 != 0;
575 }
576 
seg_dir_adjacent(seg_t * seg,seg_t * other)577 static int seg_dir_adjacent(seg_t *seg, seg_t *other)
578 {
579     return (abs(other->dir - seg->dir) % 14) == 1;
580 }
581 
seg_deinit(seg_t * seg)582 static void seg_deinit(seg_t *seg)
583 {
584     seg->dir = 0;
585     seg->next = NULL;
586 }
587 
dir_classify_stroke_old(rec_engine_t * engine,stroke_t * stroke)588 void dir_classify_stroke_old(rec_engine_t *engine, stroke_t *stroke)
589 {
590 #define DIR_MAX_SLOPE_WINDOW 27
591     static char dir_lookups[DIR_MAX_SLOPE_WINDOW][DIR_MAX_SLOPE_WINDOW]={
592 	{'`','`','`','.','.','.','.','.','.','.','.','^','^','^','^','^','.','.','.','.','.','.','.','.','\'','\'','\''},
593 	{'`','`','`','`','.','.','.','.','.','.','.','^','^','^','^','^','.','.','.','.','.','.','.','\'','\'','\'','\''},
594 	{'`','`','`','`','`','.','.','.','.','.','.','^','^','^','^','^','.','.','.','.','.','.','\'','\'','\'','\'','\''},
595 	{'.','`','`','`','`','.','.','.','.','.','.','.','^','^','^','.','.','.','.','.','.','.','\'','\'','\'','\'','.'},
596 	{'.','.','`','`','`','`','.','.','.','.','.','.','^','^','^','.','.','.','.','.','.','\'','\'','\'','\'','.','.'},
597 	{'.','.','.','.','`','`','`','.','.','.','.','.','^','^','^','.','.','.','.','.','\'','\'','\'','.','.','.','.'},
598 	{'.','.','.','.','.','`','`','`','.','.','.','.','^','^','^','.','.','.','.','\'','\'','\'','.','.','.','.','.'},
599 	{'.','.','.','.','.','.','`','`','.','.','.','.','.','^','.','.','.','.','.','\'','\'','.','.','.','.','.','.'},
600 	{'.','.','.','.','.','.','.','.','`','.','.','.','.','^','.','.','.','.','\'','.','.','.','.','.','.','.','.'},
601 	{'.','.','.','.','.','.','.','.','.','`','.','.','.','^','.','.','.','\'','.','.','.','.','.','.','.','.','.'},
602 	{'.','.','.','.','.','.','.','.','.','.','`','.','.','^','.','.','\'','.','.','.','.','.','.','.','.','.','.'},
603 	{'<','<','<','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','>','>','>'},
604 	{'<','<','<','<','<','<','<','.','.','.','.','.','.','.','.','.','.','.','.','.','>','>','>','>','>','>','>'},
605 	{'<','<','<','<','<','<','<','<','<','<','<','.','.','.','.','.','>','>','>','>','>','>','>','>','>','>','>'},
606 	{'<','<','<','<','<','<','<','.','.','.','.','.','.','.','.','.','.','.','.','.','>','>','>','>','>','>','>'},
607 	{'<','<','<','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','>','>','>'},
608 	{'.','.','.','.','.','.','.','.','.','.','/','.','.','v','.','.','l','.','.','.','.','.','.','.','.','.','.'},
609 	{'.','.','.','.','.','.','.','.','.','/','.','.','.','v','.','.','.','l','.','.','.','.','.','.','.','.','.'},
610 	{'.','.','.','.','.','.','.','.','/','.','.','.','.','v','.','.','.','.','l','.','.','.','.','.','.','.','.'},
611 	{'.','.','.','.','.','.','/','/','.','.','.','.','.','v','.','.','.','.','.','l','l','.','.','.','.','.','.'},
612 	{'.','.','.','.','.','/','/','/','.','.','.','.','v','v','v','.','.','.','.','l','l','l','.','.','.','.','.'},
613 	{'.','.','.','.','/','/','/','.','.','.','.','.','v','v','v','.','.','.','.','.','l','l','l','.','.','.','.'},
614 	{'.','.','/','/','/','/','.','.','.','.','.','.','v','v','v','.','.','.','.','.','.','l','l','l','l','.','.'},
615 	{'.','/','/','/','/','.','.','.','.','.','.','.','v','v','v','.','.','.','.','.','.','.','l','l','l','l','.'},
616 	{'/','/','/','/','/','.','.','.','.','.','.','v','v','v','v','v','.','.','.','.','.','.','l','l','l','l','l'},
617 	{'/','/','/','/','.','.','.','.','.','.','.','v','v','v','v','v','.','.','.','.','.','.','.','l','l','l','l'},
618 	{'/','/','/','.','.','.','.','.','.','.','.','v','v','v','v','v','.','.','.','.','.','.','.','.','l','l','l'},
619     };
620     int i, j, k;
621     int dx, dy;
622     char dir;
623     pt_t *pt_i, *pt_j;
624     int p_bits = stroke->precision_bits;
625     int center = DIR_MAX_SLOPE_WINDOW / 2;
626     char *seq = NULL;
627     int seq_len = 0, seq_max = 0;
628 
629     for (i=0; i < stroke->num_pts; i++) {
630 	pt_i = &stroke->pts[i];
631 
632 	j=i+1;
633 	while (1) {
634 	    if (j >= stroke->num_pts) {
635 		goto END_OF_SEQ;
636 	    }
637 	    pt_j = &stroke->pts[j];
638 	    dx = fixed_to_i_round(pt_j->x - pt_i->x, p_bits);
639 	    dy = fixed_to_i_round(pt_j->y - pt_i->y, p_bits);
640 	    if (abs(dx) > center || abs(dy) > center) {
641 		fprintf(stderr, "%s: Warning: slope ambiguities have forced me to the edge of my window.\n", __FUNCTION__);
642 		dir = '.';
643 		break;
644 	    }
645 	    dir = dir_lookups[center + dy][center + dx];
646 	    if (dir != '.') {
647 		break;
648 	    }
649 	    j++;
650 	}
651 
652 	for (k=0; k < j-i; k++) {
653 	    seq_len++;
654 	    if ((seq_len+1) > seq_max) {
655 		seq_max += 10;
656 		seq = realloc(seq, seq_max);
657 		if (seq == NULL) {
658 		    fprintf(stderr, "%s: out of memory", __FUNCTION__);
659 		    stroke->classifications[engine->num] = NULL;
660 		    return;
661 		}
662 	    }
663 	    seq[seq_len - 1] = dir;
664 	}
665 
666 	i = j;
667     }
668 
669   END_OF_SEQ:
670     if (seq) {
671 	seq[seq_len] = '\0';
672     }
673     stroke->classifications[engine->num] = seq;
674 }
675 
676 /*
677 void dir_hist_classify_stroke(rec_engine_t *engine, stroke_t *stroke)
678 {
679     int i, j, dir, max;
680     dir_priv_t *priv = (dir_priv_t *) engine->priv;
681     int win_sz = priv->window_size;
682     char *seq = NULL;
683     int seq_max = 0;
684     int seq_len = 0;
685     char dir_char, prev_dir_char = '\0';
686     int histogram[DIR_QUANTIZATION];
687     static char dir_hist_chars[DIR_QUANTIZATION] = {'>','\'','^','`','<','/','v','l'};
688 
689 
690     memset(histogram, 0, DIR_QUANTIZATION * sizeof(int));
691     for (i=0; i < win_sz && i + 1 < stroke->num_pts; i++) {
692 	dir = find_stroke_dir_at(stroke, i);
693 	histogram[dir]++;
694     }
695     for ( ; (i + 1) < stroke->num_pts; i++) {
696 	dir = 0;
697 	max = histogram[dir];
698 	for (j=0; j < DIR_QUANTIZATION; j++) {
699 	    if (histogram[j] > max) {
700 		dir = j;
701 		max = histogram[dir];
702 	    }
703 	}
704 
705 	dir_char = dir_hist_chars[dir];
706 /--	if (dir_char != prev_dir_char) { --/
707 	    seq_len++;
708 	    if ((seq_len+1) > seq_max) {
709 		seq_max += 10;
710 		seq = realloc(seq, seq_max);
711 		if (seq == NULL) {
712 		    fprintf(stderr, "%s: out of memory", __FUNCTION__);
713 		    stroke->classifications[engine->num] = NULL;
714 		    return;
715 		}
716 	    }
717 	    seq[seq_len - 1] = dir_char;
718 	    prev_dir_char = dir_char;
719 /--	} --/
720 
721 	dir = find_stroke_dir_at(stroke, i - win_sz);
722 	histogram[dir]--;
723 	dir = find_stroke_dir_at(stroke, i);
724 	histogram[dir]++;
725     }
726     seq[seq_len] = '\0';
727     stroke->classifications[engine->num] = seq;
728 }
729 */
730 
731 /*
732 void dir_raw_classify_stroke(rec_engine_t *engine, stroke_t *stroke)
733 {
734     int i;
735     dir_priv_t *priv = (dir_priv_t *) engine->priv;
736     int win_sz = priv->window_size;
737     char *seq = NULL;
738     int seq_max = 0;
739     int seq_len = 0;
740     pt_t *pt_a, *pt_b;
741     char dir;
742 
743     for (i=0; (i + win_sz) < stroke->num_pts; i++) {
744 	pt_a = &stroke->pts[i];
745 	pt_b = &stroke->pts[i + win_sz];
746 
747 	dir = find_dir(pt_a->x, pt_a->y, pt_b->x, pt_b->y, stroke->precision_bits);
748 
749 	if (dir != '.') {
750 	    seq_len++;
751 	    if ((seq_len+1) > seq_max) {
752 		seq_max += 10;
753 		seq = realloc(seq, seq_max);
754 		if (seq == NULL) {
755 		    fprintf(stderr, "%s: out of memory", __FUNCTION__);
756 		    stroke->classifications[engine->num] = NULL;
757 		    return;
758 		}
759 	    }
760 	    seq[seq_len - 1] = dir;
761 	}
762 
763 	/--comment
764 	while ((i + 1 + win_sz) < stroke->num_pts) {
765 	    pt_a = &stroke->pts[i+1];
766 	    pt_b = &stroke->pts[i+1+win_sz];
767 	    if (find_dir(pt_a->x, pt_a->y,
768 			 pt_b->x, pt_b->y, stroke->precision_bits) == dir) {
769 		i++;
770 	    } else {
771 		break;
772 	    }
773 	}
774 	comment--/
775     }
776     seq[seq_len] = '\0';
777     stroke->classifications[engine->num] = seq;
778 }
779 */
780 
dir_classification_str_alloc(rec_engine_t * engine,stroke_t * stroke)781 char *dir_classification_str_alloc(rec_engine_t *engine, stroke_t *stroke)
782 {
783     if (stroke->classifications[engine->num]) {
784 	return strdup((char *) stroke->classifications[engine->num]);
785     } else {
786 	return strdup("");
787     }
788 }
789 
dir_free_classification(rec_engine_t * engine,stroke_t * stroke)790 void dir_free_classification(rec_engine_t *engine, stroke_t *stroke)
791 {
792     free(stroke->classifications[engine->num]);
793 }
794 
dir_recognize_stroke(rec_engine_t * engine,stroke_t * stroke,void * feature_data)795 double dir_recognize_stroke(rec_engine_t *engine, stroke_t *stroke,
796 			     void *feature_data)
797 {
798     char *sequence = (char *) stroke->classifications[engine->num];
799     regex_t *regex = (regex_t *) feature_data;
800 
801     return regex_feature_recognize(regex, sequence);
802 }
803 
dir_set_option(rec_engine_t * engine,char * name,char * value)804 int dir_set_option(rec_engine_t *engine, char *name, char *value)
805 {
806 /*
807     dir_priv_t *priv;
808 
809     priv = (dir_priv_t *) engine->priv;
810     if (strcmp(name, "WindowSize") == 0) {
811 	int win_sz =  atoi(value);
812 	if (priv->window_size > DIR_MAX_WIN_SZ) {
813 	    fprintf(stderr, "%s: Warning: WindowSize %d > DIR_MAX_WIN_SZ. "
814 		    "Setting WindowSize to %d\n",
815 		    __FUNCTION__, win_sz, DIR_MAX_WIN_SZ);
816 	    win_sz = DIR_MAX_WIN_SZ;
817 	}
818 	priv->window_size = win_sz;
819 	return 0;
820     }
821 */
822     return EINVAL;
823 }
824 
825 /*
826 static char find_dir(int x1, int y1, int x2, int y2, int precision_bits)
827 {
828     static const char dir_table[DIR_MAX_WIN_SZ*2+1][DIR_MAX_WIN_SZ*2+1] =
829     {
830 	{'`','`','`','^','^','^','^','^','\'','\'','\''},
831 	{'`','`','`','.','^','^','^','.','\'','\'','\''},
832 	{'`','`','`','`','^','^','^','\'','\'','\'','\''},
833 	{'<','.','`','`','.','^','.','\'','\'','.','>'},
834 	{'<','<','<','.','`','^','\'','.','>','>','>'},
835 	{'<','<','<','<','<','.','>','>','>','>','>'},
836 	{'<','<','<','.','/','v','l','.','>','>','>'},
837 	{'<','.','/','/','.','v','.','l','l','.','>'},
838 	{'/','/','/','/','v','v','v','l','l','l','l'},
839 	{'/','/','/','.','v','v','v','.','l','l','l'},
840 	{'/','/','/','v','v','v','v','v','l','l','l'}
841     };
842 
843     int dx, dy;
844 
845     x1 = fixed_to_i_round(x1, precision_bits);
846     y1 = fixed_to_i_round(y1, precision_bits);
847     x2 = fixed_to_i_round(x2, precision_bits);
848     y2 = fixed_to_i_round(y2, precision_bits);
849 
850     dx = x2 - x1;
851     dy = y2 - y1;
852 
853     if (abs(dx) > DIR_MAX_WIN_SZ || abs(dy) > DIR_MAX_WIN_SZ) {
854 	fprintf(stderr,
855 		"%s: Error: Points (%d, %d) - (%d, %d) are too distant.\n"
856 		"%s:        (ie. greater than %d in one or both dimensions)\n",
857 		__FUNCTION__, x1, y1, x2, y2, __FUNCTION__, DIR_MAX_WIN_SZ);
858 	return '.';
859     }
860 
861     return dir_table[DIR_MAX_WIN_SZ + dy][DIR_MAX_WIN_SZ + dx];
862 }
863 */
864 
865