/* Libhnj is dual licensed under LGPL and MPL. Boilerplate for both * licenses follows. */ /* LibHnj - a library for high quality hyphenation and justification * Copyright (C) 1998 Raph Levien, * (C) 2001 ALTLinux, Moscow (http://www.alt-linux.org), * (C) 2001 Peter Novodvorsky (nidd@cs.msu.su) * (C) 2006, 2007, 2008, 2010 László Németh (nemeth at OOo) * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Library General Public * License as published by the Free Software Foundation; either * version 2 of the License, or (at your option) any later version. * * This library 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 * Library General Public License for more details. * * You should have received a copy of the GNU Library General Public * License along with this library; if not, write to the * Free Software Foundation, Inc., 59 Temple Place - Suite 330, * Boston, MA 02111-1307 USA. */ /* * The contents of this file are subject to the Mozilla Public License * Version 1.0 (the "MPL"); you may not use this file except in * compliance with the MPL. You may obtain a copy of the MPL at * http://www.mozilla.org/MPL/ * * Software distributed under the MPL is distributed on an "AS IS" basis, * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the MPL * for the specific language governing rights and limitations under the * MPL. * */ #include <stdlib.h> /* for NULL, malloc */ #include <stdio.h> /* for fprintf */ #include <string.h> /* for strdup */ #include <limits.h> /* for INT_MAX */ #ifdef UNX #include <unistd.h> /* for exit */ #endif #define noVERBOSE /* calculate hyphenmin values with long ligature length (2 or 3 characters * instead of 1 or 2) for comparison with hyphenation without ligatures */ #define noLONG_LIGATURE #ifdef LONG_LIGATURE #define LIG_xx 1 #define LIG_xxx 2 #else #define LIG_xx 0 #define LIG_xxx 1 #endif #include "hnjalloc.h" #include "hyphen.h" static char * hnj_strdup (const char *s) { char *newstr; int l; l = strlen (s); newstr = (char *) hnj_malloc (l + 1); memcpy (newstr, s, l); newstr[l] = 0; return newstr; } /* remove cross-platform text line end characters */ void hnj_strchomp(char * s) { int k = strlen(s); if ((k > 0) && ((*(s+k-1)=='\r') || (*(s+k-1)=='\n'))) *(s+k-1) = '\0'; if ((k > 1) && (*(s+k-2) == '\r')) *(s+k-2) = '\0'; } /* a little bit of a hash table implementation. This simply maps strings to state numbers */ typedef struct _HashTab HashTab; typedef struct _HashEntry HashEntry; /* A cheap, but effective, hack. */ #define HASH_SIZE 31627 struct _HashTab { HashEntry *entries[HASH_SIZE]; }; struct _HashEntry { HashEntry *next; char *key; int val; }; /* a char* hash function from ASU - adapted from Gtk+ */ static unsigned int hnj_string_hash (const char *s) { const char *p; unsigned int h=0, g; for(p = s; *p != '\0'; p += 1) { h = ( h << 4 ) + *p; if ( ( g = h & 0xf0000000 ) ) { h = h ^ (g >> 24); h = h ^ g; } } return h /* % M */; } static HashTab * hnj_hash_new (void) { HashTab *hashtab; int i; hashtab = (HashTab *) hnj_malloc (sizeof(HashTab)); for (i = 0; i < HASH_SIZE; i++) hashtab->entries[i] = NULL; return hashtab; } static void hnj_hash_free (HashTab *hashtab) { int i; HashEntry *e, *next; for (i = 0; i < HASH_SIZE; i++) for (e = hashtab->entries[i]; e; e = next) { next = e->next; hnj_free (e->key); hnj_free (e); } hnj_free (hashtab); } /* assumes that key is not already present! */ static void hnj_hash_insert (HashTab *hashtab, const char *key, int val) { int i; HashEntry *e; i = hnj_string_hash (key) % HASH_SIZE; e = (HashEntry *) hnj_malloc (sizeof(HashEntry)); e->next = hashtab->entries[i]; e->key = hnj_strdup (key); e->val = val; hashtab->entries[i] = e; } /* return val if found, otherwise -1 */ static int hnj_hash_lookup (HashTab *hashtab, const char *key) { int i; HashEntry *e; i = hnj_string_hash (key) % HASH_SIZE; for (e = hashtab->entries[i]; e; e = e->next) if (!strcmp (key, e->key)) return e->val; return -1; } /* Get the state number, allocating a new state if necessary. */ static int hnj_get_state (HyphenDict *dict, HashTab *hashtab, const char *string) { int state_num; state_num = hnj_hash_lookup (hashtab, string); if (state_num >= 0) return state_num; hnj_hash_insert (hashtab, string, dict->num_states); /* predicate is true if dict->num_states is a power of two */ if (!(dict->num_states & (dict->num_states - 1))) { dict->states = (HyphenState *) hnj_realloc (dict->states, (dict->num_states << 1) * sizeof(HyphenState)); } dict->states[dict->num_states].match = NULL; dict->states[dict->num_states].repl = NULL; dict->states[dict->num_states].fallback_state = -1; dict->states[dict->num_states].num_trans = 0; dict->states[dict->num_states].trans = NULL; return dict->num_states++; } /* add a transition from state1 to state2 through ch - assumes that the transition does not already exist */ static void hnj_add_trans (HyphenDict *dict, int state1, int state2, char ch) { int num_trans; num_trans = dict->states[state1].num_trans; if (num_trans == 0) { dict->states[state1].trans = (HyphenTrans *) hnj_malloc (sizeof(HyphenTrans)); } else if (!(num_trans & (num_trans - 1))) { dict->states[state1].trans = (HyphenTrans *) hnj_realloc (dict->states[state1].trans, (num_trans << 1) * sizeof(HyphenTrans)); } dict->states[state1].trans[num_trans].ch = ch; dict->states[state1].trans[num_trans].new_state = state2; dict->states[state1].num_trans++; } #ifdef VERBOSE HashTab *global[1]; static char * get_state_str (int state, int level) { int i; HashEntry *e; for (i = 0; i < HASH_SIZE; i++) for (e = global[level]->entries[i]; e; e = e->next) if (e->val == state) return e->key; return NULL; } #endif void hnj_hyphen_load_line(char * buf, HyphenDict * dict, HashTab * hashtab) { int i, j; char word[MAX_CHARS]; char pattern[MAX_CHARS]; char * repl; signed char replindex; signed char replcut; int state_num = 0; int last_state; char ch; int found; if (strncmp(buf, "LEFTHYPHENMIN", 13) == 0) { dict->lhmin = atoi(buf + 13); return; } else if (strncmp(buf, "RIGHTHYPHENMIN", 14) == 0) { dict->rhmin = atoi(buf + 14); return; } else if (strncmp(buf, "COMPOUNDLEFTHYPHENMIN", 21) == 0) { dict->clhmin = atoi(buf + 21); return; } else if (strncmp(buf, "COMPOUNDRIGHTHYPHENMIN", 22) == 0) { dict->crhmin = atoi(buf + 22); return; } else if (strncmp(buf, "NOHYPHEN", 8) == 0) { char * space = buf + 8; while (*space != '\0' && (*space == ' ' || *space == '\t')) space++; if (*buf != '\0') dict->nohyphen = hnj_strdup(space); if (dict->nohyphen) { char * nhe = dict->nohyphen + strlen(dict->nohyphen) - 1; *nhe = 0; for (nhe = nhe - 1; nhe > dict->nohyphen; nhe--) { if (*nhe == ',') { dict->nohyphenl++; *nhe = 0; } } } return; } j = 0; pattern[j] = '0'; repl = strchr(buf, '/'); replindex = 0; replcut = 0; if (repl) { char * index = strchr(repl + 1, ','); *repl = '\0'; if (index) { char * index2 = strchr(index + 1, ','); *index = '\0'; if (index2) { *index2 = '\0'; replindex = (signed char) atoi(index + 1) - 1; replcut = (signed char) atoi(index2 + 1); } } else { hnj_strchomp(repl + 1); replindex = 0; replcut = (signed char) strlen(buf); } repl = hnj_strdup(repl + 1); } for (i = 0; (unsigned char)buf[i] > (unsigned char)' '; i++) { if (buf[i] >= '0' && buf[i] <= '9') pattern[j] = buf[i]; else { word[j] = buf[i]; pattern[++j] = '0'; } } word[j] = '\0'; pattern[j + 1] = '\0'; i = 0; if (!repl) { /* Optimize away leading zeroes */ for (; pattern[i] == '0'; i++); } else { if (*word == '.') i++; /* convert UTF-8 char. positions of discretionary hyph. replacements to 8-bit */ if (dict->utf8) { int pu = -1; /* unicode character position */ int ps = -1; /* unicode start position (original replindex) */ size_t pc = (*word == '.') ? 1: 0; /* 8-bit character position */ for (; pc < (strlen(word) + 1); pc++) { /* beginning of an UTF-8 character (not '10' start bits) */ if ((((unsigned char) word[pc]) >> 6) != 2) pu++; if ((ps < 0) && (replindex == pu)) { ps = replindex; replindex = (signed char) pc; } if ((ps >= 0) && ((pu - ps) == replcut)) { replcut = (signed char) (pc - replindex); break; } } if (*word == '.') replindex--; } } #ifdef VERBOSE printf ("word %s pattern %s, j = %d repl: %s\n", word, pattern + i, j, repl); #endif found = hnj_hash_lookup (hashtab, word); state_num = hnj_get_state (dict, hashtab, word); dict->states[state_num].match = hnj_strdup (pattern + i); dict->states[state_num].repl = repl; dict->states[state_num].replindex = replindex; if (!replcut) { dict->states[state_num].replcut = (signed char) strlen(word); } else { dict->states[state_num].replcut = replcut; } /* now, put in the prefix transitions */ for (; found < 0 && j > 0; --j) { last_state = state_num; ch = word[j - 1]; word[j - 1] = '\0'; found = hnj_hash_lookup (hashtab, word); state_num = hnj_get_state (dict, hashtab, word); hnj_add_trans (dict, state_num, last_state, ch); } } HyphenDict * hnj_hyphen_load (const char *fn) { HyphenDict *result; FILE *f; f = fopen (fn, "r"); if (f == NULL) return NULL; result = hnj_hyphen_load_file(f); fclose(f); return result; } HyphenDict * hnj_hyphen_load_file (FILE *f) { HyphenDict *dict[2]; HashTab *hashtab; char buf[MAX_CHARS]; int nextlevel = 0; int i, j, k; HashEntry *e; int state_num = 0; /* loading one or two dictionaries (separated by NEXTLEVEL keyword) */ for (k = 0; k < 2; k++) { hashtab = hnj_hash_new (); #ifdef VERBOSE global[k] = hashtab; #endif hnj_hash_insert (hashtab, "", 0); dict[k] = (HyphenDict *) hnj_malloc (sizeof(HyphenDict)); dict[k]->num_states = 1; dict[k]->states = (HyphenState *) hnj_malloc (sizeof(HyphenState)); dict[k]->states[0].match = NULL; dict[k]->states[0].repl = NULL; dict[k]->states[0].fallback_state = -1; dict[k]->states[0].num_trans = 0; dict[k]->states[0].trans = NULL; dict[k]->nextlevel = NULL; dict[k]->lhmin = 0; dict[k]->rhmin = 0; dict[k]->clhmin = 0; dict[k]->crhmin = 0; dict[k]->nohyphen = NULL; dict[k]->nohyphenl = 0; /* read in character set info */ if (k == 0) { for (i=0;i<MAX_NAME;i++) dict[k]->cset[i]= 0; if (fgets(dict[k]->cset, sizeof(dict[k]->cset),f) != NULL) { for (i=0;i<MAX_NAME;i++) if ((dict[k]->cset[i] == '\r') || (dict[k]->cset[i] == '\n')) dict[k]->cset[i] = 0; } else { dict[k]->cset[0] = 0; } dict[k]->utf8 = (strcmp(dict[k]->cset, "UTF-8") == 0); } else { strncpy(dict[k]->cset, dict[0]->cset, sizeof(dict[k]->cset)-1); dict[k]->cset[sizeof(dict[k]->cset)-1] = '\0'; dict[k]->utf8 = dict[0]->utf8; } if (k == 0 || nextlevel) { while (fgets(buf, sizeof(buf), f) != NULL) { /* discard lines that don't fit in buffer */ if (!feof(f) && strchr(buf, '\n') == NULL) { int c; while ((c = fgetc(f)) != '\n' && c != EOF); /* issue warning if not a comment */ if (buf[0] != '%') { fprintf(stderr, "Warning: skipping too long pattern (more than %lu chars)\n", sizeof(buf)); } continue; } if (strncmp(buf, "NEXTLEVEL", 9) == 0) { nextlevel = 1; break; } else if (buf[0] != '%') { hnj_hyphen_load_line(buf, dict[k], hashtab); } } } else if (k == 1) { /* default first level: hyphen and ASCII apostrophe */ if (!dict[0]->utf8) hnj_hyphen_load_line("NOHYPHEN ',-\n", dict[k], hashtab); else hnj_hyphen_load_line("NOHYPHEN ',\xe2\x80\x93,\xe2\x80\x99,-\n", dict[k], hashtab); strncpy(buf, "1-1\n", MAX_CHARS-1); /* buf rewritten by hnj_hyphen_load here */ buf[MAX_CHARS-1] = '\0'; hnj_hyphen_load_line(buf, dict[k], hashtab); /* remove hyphen */ hnj_hyphen_load_line("1'1\n", dict[k], hashtab); /* ASCII apostrophe */ if (dict[0]->utf8) { hnj_hyphen_load_line("1\xe2\x80\x93" "1\n", dict[k], hashtab); /* endash */ hnj_hyphen_load_line("1\xe2\x80\x99" "1\n", dict[k], hashtab); /* apostrophe */ } } /* Could do unioning of matches here (instead of the preprocessor script). If we did, the pseudocode would look something like this: foreach state in the hash table foreach i = [1..length(state) - 1] state to check is substr (state, i) look it up if found, and if there is a match, union the match in. It's also possible to avoid the quadratic blowup by doing the search in order of increasing state string sizes - then you can break the loop after finding the first match. This step should be optional in any case - if there is a preprocessed rule table, it's always faster to use that. */ /* put in the fallback states */ for (i = 0; i < HASH_SIZE; i++) for (e = hashtab->entries[i]; e; e = e->next) { if (*(e->key)) for (j = 1; 1; j++) { state_num = hnj_hash_lookup (hashtab, e->key + j); if (state_num >= 0) break; } /* KBH: FIXME state 0 fallback_state should always be -1? */ if (e->val) dict[k]->states[e->val].fallback_state = state_num; } #ifdef VERBOSE for (i = 0; i < HASH_SIZE; i++) for (e = hashtab->entries[i]; e; e = e->next) { printf ("%d string %s state %d, fallback=%d\n", i, e->key, e->val, dict[k]->states[e->val].fallback_state); for (j = 0; j < dict[k]->states[e->val].num_trans; j++) printf (" %c->%d\n", dict[k]->states[e->val].trans[j].ch, dict[k]->states[e->val].trans[j].new_state); } #endif #ifndef VERBOSE hnj_hash_free (hashtab); #endif state_num = 0; } if (nextlevel) dict[0]->nextlevel = dict[1]; else { dict[1] -> nextlevel = dict[0]; dict[1]->lhmin = dict[0]->lhmin; dict[1]->rhmin = dict[0]->rhmin; dict[1]->clhmin = (dict[0]->clhmin) ? dict[0]->clhmin : ((dict[0]->lhmin) ? dict[0]->lhmin : 3); dict[1]->crhmin = (dict[0]->crhmin) ? dict[0]->crhmin : ((dict[0]->rhmin) ? dict[0]->rhmin : 3); #ifdef VERBOSE HashTab *r = global[0]; global[0] = global[1]; global[1] = r; #endif return dict[1]; } return dict[0]; } void hnj_hyphen_free (HyphenDict *dict) { int state_num; HyphenState *hstate; for (state_num = 0; state_num < dict->num_states; state_num++) { hstate = &dict->states[state_num]; if (hstate->match) hnj_free (hstate->match); if (hstate->repl) hnj_free (hstate->repl); if (hstate->trans) hnj_free (hstate->trans); } if (dict->nextlevel) hnj_hyphen_free(dict->nextlevel); if (dict->nohyphen) hnj_free(dict->nohyphen); hnj_free (dict->states); hnj_free (dict); } #define MAX_WORD 256 int hnj_hyphen_hyphenate (HyphenDict *dict, const char *word, int word_size, char *hyphens) { char *prep_word; int i, j, k; int state; char ch; HyphenState *hstate; char *match; int offset; prep_word = (char*) hnj_malloc (word_size + 3); j = 0; prep_word[j++] = '.'; for (i = 0; i < word_size; i++) { if (word[i] <= '9' && word[i] >= '0') { prep_word[j++] = '.'; } else { prep_word[j++] = word[i]; } } prep_word[j++] = '.'; prep_word[j] = '\0'; for (i = 0; i < word_size + 5; i++) hyphens[i] = '0'; #ifdef VERBOSE printf ("prep_word = %s\n", prep_word); #endif /* now, run the finite state machine */ state = 0; for (i = 0; i < j; i++) { ch = prep_word[i]; for (;;) { if (state == -1) { /* return 1; */ /* KBH: FIXME shouldn't this be as follows? */ state = 0; goto try_next_letter; } #ifdef VERBOSE char *state_str; state_str = get_state_str (state, 0); for (k = 0; k < i - strlen (state_str); k++) putchar (' '); printf ("%s", state_str); #endif hstate = &dict->states[state]; for (k = 0; k < hstate->num_trans; k++) if (hstate->trans[k].ch == ch) { state = hstate->trans[k].new_state; goto found_state; } state = hstate->fallback_state; #ifdef VERBOSE printf (" falling back, fallback_state %d\n", state); #endif } found_state: #ifdef VERBOSE printf ("found state %d\n",state); #endif /* Additional optimization is possible here - especially, elimination of trailing zeroes from the match. Leading zeroes have already been optimized. */ match = dict->states[state].match; /* replacing rules not handled by hyphen_hyphenate() */ if (match && !dict->states[state].repl) { offset = i + 1 - strlen (match); #ifdef VERBOSE for (k = 0; k < offset; k++) putchar (' '); printf ("%s\n", match); #endif /* This is a linear search because I tried a binary search and found it to be just a teeny bit slower. */ for (k = 0; match[k]; k++) if (hyphens[offset + k] < match[k]) hyphens[offset + k] = match[k]; } /* KBH: we need this to make sure we keep looking in a word */ /* for patterns even if the current character is not known in state 0 */ /* since patterns for hyphenation may occur anywhere in the word */ try_next_letter: ; } #ifdef VERBOSE for (i = 0; i < j; i++) putchar (hyphens[i]); putchar ('\n'); #endif for (i = 0; i < j - 4; i++) #if 0 if (hyphens[i + 1] & 1) hyphens[i] = '-'; #else hyphens[i] = hyphens[i + 1]; #endif hyphens[0] = '0'; for (; i < word_size; i++) hyphens[i] = '0'; hyphens[word_size] = '\0'; hnj_free (prep_word); return 0; } /* Unicode ligature length */ int hnj_ligature(unsigned char c) { switch (c) { case 0x80: /* ff */ case 0x81: /* fi */ case 0x82: return LIG_xx; /* fl */ case 0x83: /* ffi */ case 0x84: return LIG_xxx; /* ffl */ case 0x85: /* long st */ case 0x86: return LIG_xx; /* st */ } return 0; } /* character length of the first n byte of the input word */ int hnj_hyphen_strnlen(const char * word, int n, int utf8) { int i = 0; int j = 0; while (j < n && word[j] != '\0') { i++; /* Unicode ligature support */ if (utf8 && ((unsigned char) word[j] == 0xEF) && ((unsigned char) word[j + 1] == 0xAC)) { i += hnj_ligature(word[j + 2]); } for (j++; utf8 && (word[j] & 0xc0) == 0x80; j++); } return i; } int hnj_hyphen_lhmin(int utf8, const char *word, int word_size, char * hyphens, char *** rep, int ** pos, int ** cut, int lhmin) { int i = 1, j; /* Unicode ligature support */ if (utf8 && ((unsigned char) word[0] == 0xEF) && ((unsigned char) word[1] == 0xAC)) { i += hnj_ligature(word[2]); } /* ignore numbers */ for (j = 0; word[j] <= '9' && word[j] >= '0'; j++) i--; for (j = 0; i < lhmin && word[j] != '\0'; i++) do { /* check length of the non-standard part */ if (*rep && *pos && *cut && (*rep)[j]) { char * rh = strchr((*rep)[j], '='); if (rh && (hnj_hyphen_strnlen(word, j - (*pos)[j] + 1, utf8) + hnj_hyphen_strnlen((*rep)[j], rh - (*rep)[j], utf8)) < lhmin) { free((*rep)[j]); (*rep)[j] = NULL; hyphens[j] = '0'; } } else { hyphens[j] = '0'; } j++; /* Unicode ligature support */ if (utf8 && ((unsigned char) word[j] == 0xEF) && ((unsigned char) word[j + 1] == 0xAC)) { i += hnj_ligature(word[j + 2]); } } while (utf8 && (word[j] & 0xc0) == 0x80); return 0; } int hnj_hyphen_rhmin(int utf8, const char *word, int word_size, char * hyphens, char *** rep, int ** pos, int ** cut, int rhmin) { int i = 0; int j; /* ignore numbers */ for (j = word_size - 1; j > 0 && word[j] <= '9' && word[j] >= '0'; j--) i--; for (j = word_size - 1; i < rhmin && j > 0; j--) { /* check length of the non-standard part */ if (*rep && *pos && *cut && (*rep)[j]) { char * rh = strchr((*rep)[j], '='); if (rh && (hnj_hyphen_strnlen(word + j - (*pos)[j] + (*cut)[j] + 1, 100, utf8) + hnj_hyphen_strnlen(rh + 1, strlen(rh + 1), utf8)) < rhmin) { free((*rep)[j]); (*rep)[j] = NULL; hyphens[j] = '0'; } } else { hyphens[j] = '0'; } if (!utf8 || (word[j] & 0xc0) == 0xc0 || (word[j] & 0x80) != 0x80) i++; } return 0; } /* recursive function for compound level hyphenation */ int hnj_hyphen_hyph_(HyphenDict *dict, const char *word, int word_size, char * hyphens, char *** rep, int ** pos, int ** cut, int clhmin, int crhmin, int lend, int rend) { char *prep_word; int i, j, k; int state; char ch; HyphenState *hstate; char *match; char *repl; signed char replindex; signed char replcut; int offset; int * matchlen; int * matchindex; char ** matchrepl; int isrepl = 0; int nHyphCount; size_t prep_word_size = word_size + 3; prep_word = (char*) hnj_malloc (prep_word_size); matchlen = (int*) hnj_malloc ((word_size + 3) * sizeof(int)); matchindex = (int*) hnj_malloc ((word_size + 3) * sizeof(int)); matchrepl = (char**) hnj_malloc ((word_size + 3) * sizeof(char *)); j = 0; prep_word[j++] = '.'; for (i = 0; i < word_size; i++) { if (word[i] <= '9' && word[i] >= '0') { prep_word[j++] = '.'; } else { prep_word[j++] = word[i]; } } prep_word[j++] = '.'; prep_word[j] = '\0'; for (i = 0; i < j; i++) hyphens[i] = '0'; #ifdef VERBOSE printf ("prep_word = %s\n", prep_word); #endif /* now, run the finite state machine */ state = 0; for (i = 0; i < j; i++) { ch = prep_word[i]; for (;;) { if (state == -1) { /* return 1; */ /* KBH: FIXME shouldn't this be as follows? */ state = 0; goto try_next_letter; } #ifdef VERBOSE char *state_str; state_str = get_state_str (state, 1); for (k = 0; k < i - strlen (state_str); k++) putchar (' '); printf ("%s", state_str); #endif hstate = &dict->states[state]; for (k = 0; k < hstate->num_trans; k++) if (hstate->trans[k].ch == ch) { state = hstate->trans[k].new_state; goto found_state; } state = hstate->fallback_state; #ifdef VERBOSE printf (" falling back, fallback_state %d\n", state); #endif } found_state: #ifdef VERBOSE printf ("found state %d\n",state); #endif /* Additional optimization is possible here - especially, elimination of trailing zeroes from the match. Leading zeroes have already been optimized. */ match = dict->states[state].match; repl = dict->states[state].repl; replindex = dict->states[state].replindex; replcut = dict->states[state].replcut; /* replacing rules not handled by hyphen_hyphenate() */ if (match) { offset = i + 1 - strlen (match); #ifdef VERBOSE for (k = 0; k < offset; k++) putchar (' '); printf ("%s (%s)\n", match, repl); #endif if (repl) { if (!isrepl) for(; isrepl < word_size; isrepl++) { matchrepl[isrepl] = NULL; matchindex[isrepl] = -1; } matchlen[offset + replindex] = replcut; } /* This is a linear search because I tried a binary search and found it to be just a teeny bit slower. */ for (k = 0; match[k]; k++) { if ((hyphens[offset + k] < match[k])) { hyphens[offset + k] = match[k]; if (match[k]&1) { matchrepl[offset + k] = repl; if (repl && (k >= replindex) && (k <= replindex + replcut)) { matchindex[offset + replindex] = offset + k; } } } } } /* KBH: we need this to make sure we keep looking in a word */ /* for patterns even if the current character is not known in state 0 */ /* since patterns for hyphenation may occur anywhere in the word */ try_next_letter: ; } #ifdef VERBOSE for (i = 0; i < j; i++) putchar (hyphens[i]); putchar ('\n'); #endif for (i = 0; i < j - 3; i++) #if 0 if (hyphens[i + 1] & 1) hyphens[i] = '-'; #else hyphens[i] = hyphens[i + 1]; #endif for (; i < word_size; i++) hyphens[i] = '0'; hyphens[word_size] = '\0'; /* now create a new char string showing hyphenation positions */ /* count the hyphens and allocate space for the new hyphenated string */ nHyphCount = 0; for (i = 0; i < word_size; i++) if (hyphens[i]&1) nHyphCount++; j = 0; for (i = 0; i < word_size; i++) { if (isrepl && (matchindex[i] >= 0) && matchrepl[matchindex[i]]) { if (rep && pos && cut) { if (!*rep) *rep = (char **) calloc(word_size, sizeof(char *)); if (!*pos) *pos = (int *) calloc(word_size, sizeof(int)); if (!*cut) { *cut = (int *) calloc(word_size, sizeof(int)); } (*rep)[matchindex[i] - 1] = hnj_strdup(matchrepl[matchindex[i]]); (*pos)[matchindex[i] - 1] = matchindex[i] - i; (*cut)[matchindex[i] - 1] = matchlen[i]; } j += strlen(matchrepl[matchindex[i]]); i += matchlen[i] - 1; } } hnj_free (matchrepl); hnj_free (matchlen); hnj_free (matchindex); /* recursive hyphenation of the first (compound) level segments */ if (dict->nextlevel) { char ** rep2; int * pos2; int * cut2; char * hyphens2; int begin = 0; rep2 = (char**) hnj_malloc (word_size * sizeof(char *)); pos2 = (int*) hnj_malloc (word_size * sizeof(int)); cut2 = (int*) hnj_malloc (word_size * sizeof(int)); hyphens2 = (char*) hnj_malloc (word_size + 3); for (i = 0; i < word_size; i++) rep2[i] = NULL; for (i = 0; i < word_size; i++) if (hyphens[i]&1 || (begin > 0 && i + 1 == word_size)) { if (i - begin > 0) { int hyph = 0; prep_word[i + 2] = '\0'; /* non-standard hyphenation at compound boundary (Schiffahrt) */ if (rep && *rep && *pos && *cut && (*rep)[i]) { char * l = strchr((*rep)[i], '='); size_t offset = 2 + i - (*pos)[i]; strncpy(prep_word + offset, (*rep)[i], prep_word_size - offset - 1); prep_word[prep_word_size - 1] = '\0'; if (l) { hyph = (l - (*rep)[i]) - (*pos)[i]; prep_word[2 + i + hyph] = '\0'; } } hnj_hyphen_hyph_(dict, prep_word + begin + 1, i - begin + 1 + hyph, hyphens2, &rep2, &pos2, &cut2, clhmin, crhmin, (begin > 0 ? 0 : lend), (hyphens[i]&1 ? 0 : rend)); for (j = 0; j < i - begin; j++) { hyphens[begin + j] = hyphens2[j]; if (rep2[j] && rep && pos && cut) { if (!*rep && !*pos && !*cut) { int k; *rep = (char **) malloc(sizeof(char *) * word_size); *pos = (int *) malloc(sizeof(int) * word_size); *cut = (int *) malloc(sizeof(int) * word_size); for (k = 0; k < word_size; k++) { (*rep)[k] = NULL; (*pos)[k] = 0; (*cut)[k] = 0; } } (*rep)[begin + j] = rep2[j]; (*pos)[begin + j] = pos2[j]; (*cut)[begin + j] = cut2[j]; } } prep_word[i + 2] = word[i + 1]; if (*rep && *pos && *cut && (*rep)[i]) { size_t offset = 1; strncpy(prep_word + offset, word, prep_word_size - offset - 1); prep_word[prep_word_size - 1] = '\0'; } } begin = i + 1; for (j = 0; j < word_size; j++) rep2[j] = NULL; } /* non-compound */ if (begin == 0) { hnj_hyphen_hyph_(dict->nextlevel, word, word_size, hyphens, rep, pos, cut, clhmin, crhmin, lend, rend); if (!lend) hnj_hyphen_lhmin(dict->utf8, word, word_size, hyphens, rep, pos, cut, clhmin); if (!rend) hnj_hyphen_rhmin(dict->utf8, word, word_size, hyphens, rep, pos, cut, crhmin); } free(rep2); free(cut2); free(pos2); free(hyphens2); } hnj_free (prep_word); return 0; } /* UTF-8 normalization of hyphen and non-standard positions */ int hnj_hyphen_norm(const char *word, int word_size, char * hyphens, char *** rep, int ** pos, int ** cut) { int i, j, k; if ((((unsigned char) word[0]) >> 6) == 2) { fprintf(stderr, "error - bad, non UTF-8 input: %s\n", word); return 1; } /* calculate UTF-8 character positions */ for (i = 0, j = -1; i < word_size; i++) { /* beginning of an UTF-8 character (not '10' start bits) */ if ((((unsigned char) word[i]) >> 6) != 2) j++; hyphens[j] = hyphens[i]; if (rep && pos && cut && *rep && *pos && *cut) { int l = (*pos)[i]; (*pos)[j] = 0; for (k = 0; k < l; k++) { if ((((unsigned char) word[i - k]) >> 6) != 2) (*pos)[j]++; } k = i - l + 1; l = k + (*cut)[i]; (*cut)[j] = 0; for (; k < l; k++) { if ((((unsigned char) word[k]) >> 6) != 2) (*cut)[j]++; } (*rep)[j] = (*rep)[i]; if (j < i) { (*rep)[i] = NULL; (*pos)[i] = 0; (*cut)[i] = 0; } } } hyphens[j + 1] = '\0'; #ifdef VERBOSE printf ("nums: %s\n", hyphens); #endif return 0; } /* get the word with all possible hyphenations (output: hyphword) */ void hnj_hyphen_hyphword(const char * word, int word_size, const char * hyphens, char * hyphword, char *** rep, int ** pos, int ** cut) { if (word_size <= 0 || word_size > INT_MAX / 2) { hyphword[0] = '\0'; return; } /* hyphword buffer size must be at least 2 * l */ int hyphword_size = 2 * word_size - 1; int nonstandard = 0; if (*rep && *pos && *cut) { nonstandard = 1; } int i; int j = 0; for (i = 0; i < word_size && j < hyphword_size; i++) { hyphword[j++] = word[i]; if (hyphens[i]&1 && j < hyphword_size) { if (nonstandard && (*rep)[i] && j >= (*pos)[i]) { /* non-standard */ j -= (*pos)[i]; char *s = (*rep)[i]; while (*s && j < hyphword_size) { hyphword[j++] = *s++; } i += (*cut)[i] - (*pos)[i]; } else { /* standard */ hyphword[j++] = '='; } } } hyphword[j] = '\0'; } /* main api function with default hyphenmin parameters */ int hnj_hyphen_hyphenate2 (HyphenDict *dict, const char *word, int word_size, char * hyphens, char *hyphword, char *** rep, int ** pos, int ** cut) { hnj_hyphen_hyph_(dict, word, word_size, hyphens, rep, pos, cut, dict->clhmin, dict->crhmin, 1, 1); hnj_hyphen_lhmin(dict->utf8, word, word_size, hyphens, rep, pos, cut, (dict->lhmin > 0 ? dict->lhmin : 2)); hnj_hyphen_rhmin(dict->utf8, word, word_size, hyphens, rep, pos, cut, (dict->rhmin > 0 ? dict->rhmin : 2)); /* nohyphen */ if (dict->nohyphen) { char * nh = dict->nohyphen; int nhi; for (nhi = 0; nhi <= dict->nohyphenl; nhi++) { char * nhy = (char *) strstr(word, nh); while (nhy) { hyphens[nhy - word + strlen(nh) - 1] = '0'; if (nhy - word - 1 >= 0) hyphens[nhy - word - 1] = '0'; nhy = (char *) strstr(nhy + 1, nh); } nh = nh + strlen(nh) + 1; } } if (hyphword) hnj_hyphen_hyphword(word, word_size, hyphens, hyphword, rep, pos, cut); if (dict->utf8) return hnj_hyphen_norm(word, word_size, hyphens, rep, pos, cut); #ifdef VERBOSE printf ("nums: %s\n", hyphens); #endif return 0; } /* previous main api function with hyphenmin parameters */ int hnj_hyphen_hyphenate3 (HyphenDict *dict, const char *word, int word_size, char * hyphens, char *hyphword, char *** rep, int ** pos, int ** cut, int lhmin, int rhmin, int clhmin, int crhmin) { lhmin = (lhmin > dict->lhmin) ? lhmin : dict->lhmin; rhmin = (rhmin > dict->rhmin) ? rhmin : dict->rhmin; clhmin = (clhmin > dict->clhmin) ? clhmin : dict->clhmin; crhmin = (crhmin > dict->crhmin) ? crhmin : dict->crhmin; hnj_hyphen_hyph_(dict, word, word_size, hyphens, rep, pos, cut, clhmin, crhmin, 1, 1); hnj_hyphen_lhmin(dict->utf8, word, word_size, hyphens, rep, pos, cut, (lhmin > 0 ? lhmin : 2)); hnj_hyphen_rhmin(dict->utf8, word, word_size, hyphens, rep, pos, cut, (rhmin > 0 ? rhmin : 2)); if (hyphword) hnj_hyphen_hyphword(word, word_size, hyphens, hyphword, rep, pos, cut); /* nohyphen */ if (dict->nohyphen) { char * nh = dict->nohyphen; int nhi; for (nhi = 0; nhi <= dict->nohyphenl; nhi++) { char * nhy = (char *) strstr(word, nh); while (nhy) { hyphens[nhy - word + strlen(nh) - 1] = 0; if (nhy - word - 1 >= 0) hyphens[nhy - word - 1] = 0; nhy = (char *) strstr(nhy + 1, nh); } nh = nh + strlen(nh) + 1; } } if (dict->utf8) return hnj_hyphen_norm(word, word_size, hyphens, rep, pos, cut); return 0; }