1 #include "tdef.h"
2 #include "fns.h"
3 #include "ext.h"
4 
5 #define	HY_BIT	0200	/* stuff in here only works for 7-bit ascii */
6 			/* this value is used (as a literal) in suftab.c */
7 			/* to encode possible hyphenation points in suffixes. */
8 			/* it could be changed, by widening the tables */
9 			/* to be shorts instead of chars. */
10 
11 /*
12  * troff8.c
13  * 
14  * hyphenation
15  */
16 
17 int	hexsize = 0;		/* hyphenation exception list size */
18 char	*hbufp = NULL;		/* base of list */
19 char	*nexth = NULL;		/* first free slot in list */
20 Tchar	*hyend;
21 
22 #define THRESH 160 		/* digram goodness threshold */
23 int	thresh = THRESH;
24 
25 int	texhyphen(void);
26 static	int	alpha(Tchar);
27 
28 void hyphen(Tchar *wp)
29 {
30 	int j;
31 	Tchar *i;
32 
33 	i = wp;
34 	while (punct((*i++)))
35 		;
36 	if (!alpha(*--i))
37 		return;
38 	wdstart = i++;
39 	while (alpha(*i++))
40 		;
41 	hyend = wdend = --i - 1;
42 	while (punct((*i++)))
43 		;
44 	if (*--i)
45 		return;
46 	if (wdend - wdstart < 4)	/* 4 chars is too short to hyphenate */
47 		return;
48 	hyp = hyptr;
49 	*hyp = 0;
50 	hyoff = 2;
51 
52 	/* for now, try exceptions first, then tex (if hyphalg is non-zero),
53 	   then suffix and digram if tex didn't hyphenate it at all.
54 	*/
55 
56 	if (!exword() && !texhyphen() && !suffix())
57 		digram();
58 
59 	/* this appears to sort hyphenation points into increasing order */
60 	*hyp++ = 0;
61 	if (*hyptr) 
62 		for (j = 1; j; ) {
63 			j = 0;
64 			for (hyp = hyptr + 1; *hyp != 0; hyp++) {
65 				if (*(hyp - 1) > *hyp) {
66 					j++;
67 					i = *hyp;
68 					*hyp = *(hyp - 1);
69 					*(hyp - 1) = i;
70 				}
71 			}
72 		}
73 }
74 
75 static int alpha(Tchar i)	/* non-zero if really alphabetic */
76 {
77 	if (ismot(i))
78 		return 0;
79 	else if (cbits(i) >= ALPHABET)	/* this isn't very elegant, but there's */
80 		return 0;		/* no good way to make sure i is in range for */
81 	else				/* the call of isalpha */
82 		return isalpha(cbits(i));
83 }
84 
85 int
86 punct(Tchar i)
87 {
88 	if (!i || alpha(i))
89 		return(0);
90 	else
91 		return(1);
92 }
93 
94 
95 void caseha(void)	/* set hyphenation algorithm */
96 {
97 	hyphalg = HYPHALG;
98 	if (skip())
99 		return;
100 	noscale++;
101 	hyphalg = atoi0();
102 	noscale = 0;
103 }
104 
105 
106 void caseht(void)	/* set hyphenation threshold;  not in manual! */
107 {
108 	thresh = THRESH;
109 	if (skip())
110 		return;
111 	noscale++;
112 	thresh = atoi0();
113 	noscale = 0;
114 }
115 
116 
117 char *growh(char *where)
118 {
119 	char *new;
120 
121 	hexsize += NHEX;
122 	if ((new = grow(hbufp, hexsize, sizeof(char))) == NULL)
123 		return NULL;
124 	if (new == hbufp) {
125 		return where;
126 	} else {
127 		int diff;
128 		diff = where - hbufp;
129 		hbufp = new;
130 		return new + diff;
131 	}
132 }
133 
134 
135 void casehw(void)
136 {
137 	int i, k;
138 	char *j;
139 	Tchar t;
140 
141 	if (nexth == NULL) {
142 		if ((nexth = hbufp = grow(hbufp, NHEX, sizeof(char))) == NULL) {
143 			ERROR "No space for exception word list." WARN;
144 			return;
145 		}
146 		hexsize = NHEX;
147 	}
148 	k = 0;
149 	while (!skip()) {
150 		if ((j = nexth) >= hbufp + hexsize - 2)
151 			if ((j = nexth = growh(j)) == NULL)
152 				goto full;
153 		for (;;) {
154 			if (ismot(t = getch()))
155 				continue;
156 			i = cbits(t);
157 			if (i == ' ' || i == '\n') {
158 				*j++ = 0;
159 				nexth = j;
160 				*j = 0;
161 				if (i == ' ')
162 					break;
163 				else
164 					return;
165 			}
166 			if (i == '-') {
167 				k = HY_BIT;
168 				continue;
169 			}
170 			*j++ = maplow(i) | k;
171 			k = 0;
172 			if (j >= hbufp + hexsize - 2)
173 				if ((j = growh(j)) == NULL)
174 					goto full;
175 		}
176 	}
177 	return;
178 full:
179 	ERROR "Cannot grow exception word list." WARN;
180 	*nexth = 0;
181 }
182 
183 
184 int exword(void)
185 {
186 	Tchar *w;
187 	char *e, *save;
188 
189 	e = hbufp;
190 	while (1) {
191 		save = e;
192 		if (e == NULL || *e == 0)
193 			return(0);
194 		w = wdstart;
195 		while (*e && w <= hyend && (*e & 0177) == maplow(cbits(*w))) {
196 			e++; 
197 			w++;
198 		}
199 		if (!*e) {
200 			if (w-1 == hyend || (w == wdend && maplow(cbits(*w)) == 's')) {
201 				w = wdstart;
202 				for (e = save; *e; e++) {
203 					if (*e & HY_BIT)
204 						*hyp++ = w;
205 					if (hyp > hyptr + NHYP - 1)
206 						hyp = hyptr + NHYP - 1;
207 					w++;
208 				}
209 				return(1);
210 			} else {
211 				e++; 
212 				continue;
213 			}
214 		} else 
215 			while (*e++)
216 				;
217 	}
218 }
219 
220 int
221 suffix(void)
222 {
223 	Tchar *w;
224 	char *s, *s0;
225 	Tchar i;
226 	extern char *suftab[];
227 
228 again:
229 	i = cbits(*hyend);
230 	if (!alpha(i))
231 		return(0);
232 	if (i < 'a')
233 		i -= 'A' - 'a';
234 	if ((s0 = suftab[i-'a']) == 0)
235 		return(0);
236 	for (;;) {
237 		if ((i = *s0 & 017) == 0)
238 			return(0);
239 		s = s0 + i - 1;
240 		w = hyend - 1;
241 		while (s > s0 && w >= wdstart && (*s & 0177) == maplow(cbits(*w))) {
242 			s--;
243 			w--;
244 		}
245 		if (s == s0)
246 			break;
247 		s0 += i;
248 	}
249 	s = s0 + i - 1;
250 	w = hyend;
251 	if (*s0 & HY_BIT) 
252 		goto mark;
253 	while (s > s0) {
254 		w--;
255 		if (*s-- & HY_BIT) {
256 mark:
257 			hyend = w - 1;
258 			if (*s0 & 0100)	/* 0100 used in suftab to encode something too */
259 				continue;
260 			if (!chkvow(w))
261 				return(0);
262 			*hyp++ = w;
263 		}
264 	}
265 	if (*s0 & 040)
266 		return(0);
267 	if (exword())
268 		return(1);
269 	goto again;
270 }
271 
272 int
273 maplow(int i)
274 {
275 	if (isupper(i)) 
276 		i = tolower(i);
277 	return(i);
278 }
279 
280 int
281 vowel(int i)
282 {
283 	switch (i) {
284 	case 'a': case 'A':
285 	case 'e': case 'E':
286 	case 'i': case 'I':
287 	case 'o': case 'O':
288 	case 'u': case 'U':
289 	case 'y': case 'Y':
290 		return(1);
291 	default:
292 		return(0);
293 	}
294 }
295 
296 
297 Tchar *chkvow(Tchar *w)
298 {
299 	while (--w >= wdstart)
300 		if (vowel(cbits(*w)))
301 			return(w);
302 	return(0);
303 }
304 
305 
306 void digram(void)
307 {
308 	Tchar *w;
309 	int val;
310 	Tchar *nhyend, *maxw;
311 	int maxval;
312 	extern char bxh[26][13], bxxh[26][13], xxh[26][13], xhx[26][13], hxx[26][13];
313         maxw = 0;
314 again:
315 	if (!(w = chkvow(hyend + 1)))
316 		return;
317 	hyend = w;
318 	if (!(w = chkvow(hyend)))
319 		return;
320 	nhyend = w;
321 	maxval = 0;
322 	w--;
323 	while (++w < hyend && w < wdend - 1) {
324 		val = 1;
325 		if (w == wdstart)
326 			val *= dilook('a', cbits(*w), bxh);
327 		else if (w == wdstart + 1)
328 			val *= dilook(cbits(*(w-1)), cbits(*w), bxxh);
329 		else 
330 			val *= dilook(cbits(*(w-1)), cbits(*w), xxh);
331 		val *= dilook(cbits(*w), cbits(*(w+1)), xhx);
332 		val *= dilook(cbits(*(w+1)), cbits(*(w+2)), hxx);
333 		if (val > maxval) {
334 			maxval = val;
335 			maxw = w + 1;
336 		}
337 	}
338 	hyend = nhyend;
339 	if (maxval > thresh)
340 		*hyp++ = maxw;
341 	goto again;
342 }
343 
344 int
345 dilook(int a, int b, char t[26][13])
346 {
347 	int i, j;
348 
349 	i = t[maplow(a)-'a'][(j = maplow(b)-'a')/2];
350 	if (!(j & 01))
351 		i >>= 4;
352 	return(i & 017);
353 }
354 
355 
356 /* here beginneth the tex hyphenation code, as interpreted freely */
357 /* the main difference is that there is no attempt to squeeze space */
358 /* as tightly at tex does. */
359 
360 static int	texit(Tchar *, Tchar *);
361 static int	readpats(void);
362 static void	install(char *);
363 static void	fixup(void);
364 static int	trieindex(int, int);
365 
366 static char	pats[50000];	/* size ought to be computed dynamically */
367 static char	*nextpat = pats;
368 static char	*trie[27*27];	/* english-specific sizes */
369 
370 int texhyphen(void)
371 {
372 	static int loaded = 0;		/* -1: couldn't find tex file */
373 
374 	if (hyphalg == 0 || loaded == -1)	/* non-zero => tex for now */
375 		return 0;
376 	if (loaded == 0) {
377 		if (readpats())
378 			loaded = 1;
379 		else
380 			loaded = -1;
381 	}
382 	return texit(wdstart, wdend);
383 }
384 
385 static int texit(Tchar *start, Tchar *end)	/* hyphenate as in tex, return # found */
386 {
387 	int nw, i, k, equal, cnt[500];
388 	char w[500+1], *np, *pp, *wp, *xpp, *xwp;
389 
390 	w[0] = '.';
391 	for (nw = 1; start <= end && nw < 500-1; nw++, start++)
392 		w[nw] = maplow(tolower(cbits(*start)));
393 	start -= (nw - 1);
394 	w[nw++] = '.';
395 	w[nw] = 0;
396 /*
397  * printf("try %s\n", w);
398 */
399 	for (i = 0; i <= nw; i++)
400 		cnt[i] = '0';
401 
402 	for (wp = w; wp < w + nw; wp++) {
403 		for (pp = trie[trieindex(*wp, *(wp+1))]; pp < nextpat; ) {
404 			if (pp == 0		/* no trie entry */
405 			 || *pp != *wp		/* no match on 1st letter */
406 			 || *(pp+1) != *(wp+1))	/* no match on 2nd letter */
407 				break;		/*   so move to next letter of word */
408 			equal = 1;
409 			for (xpp = pp+2, xwp = wp+2; *xpp; )
410 				if (*xpp++ != *xwp++) {
411 					equal = 0;
412 					break;
413 				}
414 			if (equal) {
415 				np = xpp+1;	/* numpat */
416 				for (k = wp-w; *np; k++, np++)
417 					if (*np > cnt[k])
418 						cnt[k] = *np;
419 /*
420  * printf("match: %s  %s\n", pp, xpp+1);
421 */
422 			}
423 			pp += *(pp-1);	/* skip over pattern and numbers to next */
424 		}
425 	}
426 /*
427  * for (i = 0; i < nw; i++) printf("%c", w[i]);
428  * printf("  ");
429  * for (i = 0; i <= nw; i++) printf("%c", cnt[i]);
430  * printf("\n");
431 */
432 /*
433  * 	for (i = 1; i < nw - 1; i++) {
434  * 		if (i > 2 && i < nw - 3 && cnt[i] % 2)
435  * 			printf("-");
436  * 		if (cbits(start[i-1]) != '.')
437  * 			printf("%c", cbits(start[i-1]));
438  * 	}
439  * 	printf("\n");
440 */
441 	for (i = 1; i < nw -1; i++)
442 		if (i > 2 && i < nw - 3 && cnt[i] % 2)
443 			*hyp++ = start + i - 1;
444 	return hyp - hyptr;	/* non-zero if a hyphen was found */
445 }
446 
447 /*
448 	This code assumes that hyphen.tex looks like
449 		% some comments
450 		\patterns{ % more comments
451 		pat5ter4ns, 1 per line, SORTED, nothing else
452 		}
453 		more goo
454 		\hyphenation{ % more comments
455 		ex-cep-tions, one per line; i ignore this part for now
456 		}
457 
458 	this code is NOT robust against variations.  unfortunately,
459 	it looks like every local language version of this file has
460 	a different format.  i have also made no provision for weird
461 	characters.  sigh.
462 */
463 
464 static int readpats(void)
465 {
466 	FILE *fp;
467 	char buf[200], buf1[200];
468 
469 	if ((fp = fopen(unsharp(TEXHYPHENS), "r")) == NULL
470 	 && (fp = fopen(unsharp(DWBalthyphens), "r")) == NULL) {
471 		ERROR "warning: can't find hyphen.tex" WARN;
472 		return 0;
473 	}
474 
475 	while (fgets(buf, sizeof buf, fp) != NULL) {
476 		sscanf(buf, "%s", buf1);
477 		if (strcmp(buf1, "\\patterns{") == 0)
478 			break;
479 	}
480 	while (fgets(buf, sizeof buf, fp) != NULL) {
481 		if (buf[0] == '}')
482 			break;
483 		install(buf);
484 	}
485 	fclose(fp);
486 	fixup();
487 	return 1;
488 }
489 
490 static void install(char *s)	/* map ab4c5de to: 12 abcde \0 00405 \0 */
491 {
492 	int npat, lastpat;
493 	char num[500], *onextpat = nextpat;
494 
495 	num[0] = '0';
496 	*nextpat++ = ' ';	/* fill in with count later */
497 	for (npat = lastpat = 0; *s != '\n' && *s != '\0'; s++) {
498 		if (isdigit(*s)) {
499 			num[npat] = *s;
500 			lastpat = npat;
501 		} else {
502 			*nextpat++ = *s;
503 			npat++;
504 			num[npat] = '0';
505 		}
506 	}
507 	*nextpat++ = 0;
508 	if (nextpat > pats + sizeof(pats)-20) {
509 		ERROR "tex hyphenation table overflow, tail end ignored" WARN;
510 		nextpat = onextpat;
511 	}
512 	num[lastpat+1] = 0;
513 	strcat(nextpat, num);
514 	nextpat += strlen(nextpat) + 1;
515 }
516 
517 static void fixup(void)	/* build indexes of where . a b c ... start */
518 {
519 	char *p, *lastc;
520 	int n;
521 
522 	for (lastc = pats, p = pats+1; p < nextpat; p++)
523 		if (*p == ' ') {
524 			*lastc = p - lastc;
525 			lastc = p;
526 		}
527 	*lastc = p - lastc;
528 	for (p = pats+1; p < nextpat; ) {
529 		n = trieindex(p[0], p[1]);
530 		if (trie[n] == 0)
531 			trie[n] = p;
532 		p += p[-1];
533 	}
534 	/* printf("pats = %d\n", nextpat - pats); */
535 }
536 
537 static int trieindex(int d1, int d2)
538 {
539 	return 27 * (d1 == '.' ? 0 : d1 - 'a' + 1) + (d2 == '.' ? 0 : d2 - 'a' + 1);
540 }