/* 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) * * 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 /* for NULL, malloc */ #include /* for fprintf */ #include /* for strdup */ #include /* for malloc used by substring inclusion*/ #define MAXPATHS 40960 #ifdef UNX #include /* for exit */ #endif #include /*#define VERBOSE*/ #include "hnjalloc.h" #include "hyphen.h" static const char _svn_version[] = "$Id: hyphen.c 1696 2008-12-28 21:02:34Z oneiros $ $URL: http://scm.foundry.supelec.fr/svn/luatex/trunk/src/texk/web2c/luatexdir/lang/texlang.c $"; /* SHOULD BE MOVED TO SEPARATE LIBRARY */ static unsigned char * hnj_strdup( const unsigned char *s ) { unsigned char *new; int l; l = strlen ((char*)s); new = hnj_malloc (l + 1); memcpy (new, s, l); new[l] = 0; return new; } static int is_utf8_follow( unsigned char c ) { if (c>=0x80 && c<0xC0) return 1; return 0; } /* -------------------------------------------------------------------- * * Type definitions * * -------------------------------------------------------------------- */ /* a little bit of a hash table implementation. This simply maps strings to state numbers */ typedef struct _HashTab HashTab; typedef struct _HashEntry HashEntry; typedef struct _HashIter HashIter; typedef union _HashVal HashVal; /* A cheap, but effective, hack. */ #define HASH_SIZE 31627 struct _HashTab { HashEntry *entries[HASH_SIZE]; }; union _HashVal { int state; char* hyppat; }; struct _HashEntry { HashEntry *next; unsigned char *key; HashVal u; }; struct _HashIter { HashEntry** e; HashEntry* cur; int ndx; }; /* State machine */ typedef struct _HyphenState HyphenState; typedef struct _HyphenTrans HyphenTrans; #define MAX_CHARS 256 #define MAX_NAME 20 struct _HyphenDict { int num_states; int pat_length; char cset[MAX_NAME]; HyphenState *states; HashTab *patterns; HashTab *merged; HashTab *state_num; }; struct _HyphenState { char *match; /*char *repl;*/ /*signed char replindex;*/ /*signed char replcut;*/ int fallback_state; int num_trans; HyphenTrans *trans; }; struct _HyphenTrans { int uni_ch; int new_state; }; /* Combine two right-aligned number patterns, 04000 + 020 becomes 04020*/ static char *combine( char *expr, const char *subexpr ) { int l1 = strlen(expr); int l2 = strlen(subexpr); int off = l1-l2; int j; /* this works also for utf8 sequences because the substring is identical * to the last substring-length bytes of expr except for the (single byte) * hyphenation encoders */ for (j=0; je = h->entries; i->cur = NULL; i->ndx = -1; return i; } int nextHashStealPattern( HashIter*i, unsigned char**word, char **pattern ) { while (i->cur==NULL) { if (i->ndx >= HASH_SIZE-1) return 0; i->cur = i->e[++i->ndx]; } *word = i->cur->key; *pattern = i->cur->u.hyppat; i->cur->u.hyppat = NULL; i->cur = i->cur->next; return 1; } int nextHash( HashIter*i, unsigned char**word ) { while (i->cur==NULL) { if (i->ndx >= HASH_SIZE-1) return 0; i->cur = i->e[++i->ndx]; } *word = i->cur->key; i->cur = i->cur->next; return 1; } int eachHash( HashIter*i, unsigned char**word, char**pattern ) { while (i->cur==NULL) { if (i->ndx >= HASH_SIZE-1) return 0; i->cur = i->e[++i->ndx]; } *word = i->cur->key; *pattern = i->cur->u.hyppat; i->cur = i->cur->next; return 1; } void delete_HashIter( HashIter*i ) { hnj_free(i); } /* a char* hash function from ASU - adapted from Gtk+ */ static unsigned int hnj_string_hash ( const unsigned char *s ) { const unsigned 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 */; } /* assumes that key is not already present! */ static void state_insert( HashTab *hashtab, unsigned char *key, int state ) { int i; HashEntry *e; i = hnj_string_hash (key) % HASH_SIZE; e = hnj_malloc (sizeof(HashEntry)); e->next = hashtab->entries[i]; e->key = key; e->u.state = state; hashtab->entries[i] = e; } /* assumes that key is not already present! */ static void hyppat_insert( HashTab *hashtab, unsigned char *key, char* hyppat ) { int i; HashEntry *e; i = hnj_string_hash (key) % HASH_SIZE; for (e = hashtab->entries[i]; e; e=e->next) { if (strcmp((char*)e->key,(char*)key)==0) { if (e->u.hyppat) { if (hyppat && strcmp((char*)e->u.hyppat,(char*)hyppat)!=0) { int s = maketexstring("Conflicting pattern ignored"); do_print_err(s); error(); flush_str(s); } hnj_free(e->u.hyppat); } e->u.hyppat = hyppat; hnj_free(key); return; } } e = hnj_malloc (sizeof(HashEntry)); e->next = hashtab->entries[i]; e->key = key; e->u.hyppat = hyppat; hashtab->entries[i] = e; } /* return state if found, otherwise -1 */ static int state_lookup( HashTab *hashtab, const unsigned char *key ) { int i; HashEntry *e; i = hnj_string_hash (key) % HASH_SIZE; for (e = hashtab->entries[i]; e; e = e->next) { if (!strcmp ((char*)key, (char*)e->key)) { return e->u.state; } } return -1; } /* return state if found, otherwise -1 */ static char* hyppat_lookup( HashTab *hashtab, const unsigned char *chars, int l ) { int i; HashEntry *e; unsigned char key[128]; /* should be ample*/ strncpy((char*)key,(char*)chars,l); key[l]=0; i = hnj_string_hash (key) % HASH_SIZE; for (e = hashtab->entries[i]; e; e = e->next) { if (!strcmp ((char*)key, (char*)e->key)) { return e->u.hyppat; } } return NULL; } /* Get the state number, allocating a new state if necessary. */ static int hnj_get_state( HyphenDict *dict, const unsigned char *string, int *state_num ) { *state_num = state_lookup(dict->state_num, string); if (*state_num >= 0) return *state_num; state_insert(dict->state_num, hnj_strdup(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 = hnj_realloc( dict->states, (dict->num_states << 1) * sizeof(HyphenState)); } dict->states[dict->num_states].match = 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, int uni_ch ) { int num_trans; /* TH: this test was a bit too strict, it is quite normal for old patterns to have chars in the range 0-31 or 127-159 (inclusive). To ease the transition, let's only disallow NUL for now (this is probably a requirement of the code anyway). */ if (uni_ch==0) { fprintf(stderr,"Character out of bounds: u%04x \n",uni_ch); exit(1); } num_trans = dict->states[state1].num_trans; if (num_trans == 0) { dict->states[state1].trans = hnj_malloc(sizeof(HyphenTrans)); } else if (!(num_trans & (num_trans - 1))) { dict->states[state1].trans = hnj_realloc( dict->states[state1].trans, (num_trans << 1) * sizeof(HyphenTrans)); } dict->states[state1].trans[num_trans].uni_ch = uni_ch; dict->states[state1].trans[num_trans].new_state = state2; dict->states[state1].num_trans++; } #ifdef VERBOSE static unsigned char *get_state_str( int state ) { int i; HashEntry *e; for (i = 0; i < HASH_SIZE; i++) for (e = global->entries[i]; e; e = e->next) if (e->u.state == state) return e->key; return NULL; } #endif /* I've changed the semantics a bit here: hnj_hyphen_load used to operate on a file, but now the argument is a string buffer. */ static const unsigned char* next_pattern( size_t* length, const unsigned char **buf ) { const unsigned char *here, *rover = *buf; while (*rover && isspace(*rover)) rover++; here = rover; while (*rover) { if (isspace(*rover)) { *length = rover-here; *buf = rover; return here; } rover++; } *length = rover-here; *buf = rover; return *length ? here : NULL; /* zero sensed */ } static void init_hash( HashTab**h ) { int i; if (*h) return; *h = hnj_malloc(sizeof(HashTab)); for (i = 0; i < HASH_SIZE; i++) (*h)->entries[i] = NULL; } static void clear_state_hash( HashTab**h ) { int i; if (*h==NULL) return; for (i = 0; i < HASH_SIZE; i++) { HashEntry *e, *next; for (e = (*h)->entries[i]; e; e = next) { next = e->next; hnj_free (e->key); hnj_free (e); } } hnj_free(*h); *h=NULL; } static void clear_hyppat_hash( HashTab**h ) { int i; if (*h==NULL) return; for (i = 0; i < HASH_SIZE; i++) { HashEntry *e, *next; for (e = (*h)->entries[i]; e; e = next) { next = e->next; hnj_free(e->key); if (e->u.hyppat) hnj_free(e->u.hyppat); hnj_free(e); } } hnj_free(*h); *h=NULL; } static void init_dict( HyphenDict* dict ) { dict->num_states = 1; dict->pat_length = 0; dict->states = hnj_malloc (sizeof(HyphenState)); dict->states[0].match = NULL; dict->states[0].fallback_state = -1; dict->states[0].num_trans = 0; dict->states[0].trans = NULL; dict->patterns = NULL; dict->merged = NULL; dict->state_num = NULL; init_hash(&dict->patterns); } static void clear_dict( HyphenDict* dict ) { int state_num; for (state_num = 0; state_num < dict->num_states; state_num++) { HyphenState *hstate = &dict->states[state_num]; if (hstate->match) hnj_free (hstate->match); if (hstate->trans) hnj_free (hstate->trans); } hnj_free (dict->states); clear_hyppat_hash(&dict->patterns); clear_hyppat_hash(&dict->merged); clear_state_hash(&dict->state_num); } HyphenDict* hnj_hyphen_new() { HyphenDict* dict = hnj_malloc (sizeof(HyphenDict)); init_dict(dict); return dict; } void hnj_hyphen_clear( HyphenDict* dict ) { clear_dict(dict); init_dict(dict); } void hnj_hyphen_free( HyphenDict *dict ) { clear_dict(dict); hnj_free(dict); } unsigned char* hnj_serialize( HyphenDict* dict ) { HashIter *v; unsigned char* word; char* pattern; unsigned char* buf = hnj_malloc(dict->pat_length); unsigned char* cur = buf; v = new_HashIter(dict->patterns); while (eachHash(v,&word,&pattern)) { int i=0, e=0; while(word[e+i]) { if (pattern[i]!='0') *cur++ = (unsigned char) pattern[i]; *cur++ = word[e+i++]; while (is_utf8_follow(word[e+i])) *cur++ = word[i+e++]; } if (pattern[i]!='0') *cur++ = (unsigned char) pattern[i]; *cur++ = ' '; } delete_HashIter(v); *cur = 0; return buf; } void hnj_free_serialize( unsigned char* c ) { hnj_free(c); } /* hyphenation pattern: * signed bytes * 0 indicates end (actually any negative number) * : prio(1+),startpos,length,len1,[replace],len2,[replace] * most basic example is: * p n 0 0 0 * for a hyphenation point between characters */ void hnj_hyphen_load( HyphenDict* dict, const unsigned char *f ) { int state_num, last_state; int i, j = 0; int ch; int found; HashEntry *e; HashIter *v; unsigned char* word; char* pattern; size_t l = 0; /***************************************/ const unsigned char* format; const unsigned char* begin = f; unsigned char *pat; char *org; while((format = next_pattern(&l,&f))!=NULL) { int i,j,e; /* printf("%s\n",format); char* repl = strnchr(format, '/',l); int replindex = 0; int replcut = 0; if (repl) { int clen = l-(repl-format); l = repl-format; char * index = strnchr(repl + 1, ',',clen); if (index) { char * index2 = strnchr(index + 1, ',',clen-(index-repl)); if (index2) { replindex = (signed char) atoi(index + 1) - 1; replcut = (signed char) atoi(index2 + 1); } } else { hnj_strchomp(repl + 1); replindex = 0; replcut = strlen(buf); } repl = hnj_strdup(repl + 1); } */ for (i=0,j=0,e=0; (unsigned)i='0'&&format[i]<='9') j++; if (is_utf8_follow(format[i])) e++; } /* l-e => number of _characters_ not _bytes_*/ /* l-j => number of pattern bytes */ /* l-e-j => number of pattern characters*/ pat = (unsigned char*) malloc(1+l-j); org = ( char*) malloc(2+l-e-j); /* remove hyphenation encoders (digits) from pat*/ org[0] = '0'; for (i=0,j=0,e=0; (unsigned)i'9') { pat[e+j++] = c; org[j] = '0'; } else { org[j] = c; } } pat[e+j] = 0; org[j+1] = 0; hyppat_insert(dict->patterns,pat,org); } dict->pat_length += (f-begin)+2; /* 2 for spurious spaces*/ init_hash(&dict->merged); v = new_HashIter(dict->patterns); while (nextHash(v,&word)) { int wordsize = strlen((char*)word); int j,l; for (l=1; l<=wordsize; l++) { if (is_utf8_follow(word[l])) continue; /* Do not clip an utf8 sequence*/ for (j=1; j<=l; j++) { char *subpat_pat; int i = l-j; if (is_utf8_follow(word[i])) continue; /* Do not start halfway an utf8 sequence*/ if ((subpat_pat = hyppat_lookup(dict->patterns,word+i,j))!=NULL) { char* newpat_pat; if ((newpat_pat = hyppat_lookup(dict->merged,word,l))==NULL) { char *neworg; unsigned char *newword=(unsigned char*)malloc(l+1); int e=0; strncpy((char*)newword, (char*)word,l); newword[l]=0; for (i=0; imerged,newword,combine(neworg,subpat_pat)); } else { combine(newpat_pat,subpat_pat); } } } } } delete_HashIter(v); init_hash(&dict->state_num); state_insert(dict->state_num, hnj_strdup((unsigned char*)""), 0); v = new_HashIter(dict->merged); while (nextHashStealPattern(v,&word,&pattern)) { static unsigned char mask[] = {0x3F,0x1F,0xF,0x7}; int j = strlen((char*)word); #ifdef VERBOSE printf ("word %s pattern %s, j = %d\n", word, pattern, j); #endif state_num = hnj_get_state( dict, word, &found ); dict->states[state_num].match = pattern; /* now, put in the prefix transitions */ while (found < 0) { j--; last_state = state_num; ch = word[j]; if (ch>=0x80) { int m; int i=1; while (is_utf8_follow(word[j-i])) i++; ch = word[j-i] & mask[i]; m = j-i; while (i--) { ch = (ch<<6)+(0x3F & word[j-i]); } j = m; } word[j] = '\0'; state_num = hnj_get_state (dict, word, &found); hnj_add_trans (dict, state_num, last_state, ch); } } delete_HashIter(v); clear_hyppat_hash(&dict->merged); /***************************************/ /* put in the fallback states */ for (i = 0; i < HASH_SIZE; i++) { for (e = dict->state_num->entries[i]; e; e = e->next) { /* do not do state==0 otherwise things get confused*/ if (e->u.state) { for (j = 1; 1; j++) { state_num = state_lookup(dict->state_num, e->key + j); if (state_num >= 0) break; } dict->states[e->u.state].fallback_state = state_num; } } } #ifdef VERBOSE for (i = 0; i < HASH_SIZE; i++) { for (e = dict->state_num->entries[i]; e; e = e->next) { printf ("%d string %s state %d, fallback=%d\n", i, e->key, e->u.state, dict->states[e->u.state].fallback_state); for (j = 0; j < dict->states[e->u.state].num_trans; j++) { printf (" u%4x->%d\n", (int)dict->states[e->u.state].trans[j].uni_ch, dict->states[e->u.state].trans[j].new_state); } } } #endif clear_state_hash(&dict->state_num); } void hnj_hyphen_hyphenate( HyphenDict *dict, halfword first, halfword last, int length, halfword left, halfword right, lang_variables *lan ) { int char_num; halfword here; int state = 0; /* +2 for dots at each end, +1 for points /outside/ characters*/ int ext_word_len = length+2; int hyphen_len = ext_word_len+1; /*char *hyphens = hnj_malloc((hyphen_len*2)+1); */ /* LATER */ char *hyphens = hnj_malloc(hyphen_len+1); /* Add a '.' to beginning and end to facilitate matching*/ set_vlink(begin_point,first); set_vlink(end_point,get_vlink(last)); set_vlink(last,end_point); for (char_num = 0; char_num < hyphen_len; char_num++) { /* hyphens[char_num*2] = '0'; */ /* LATER */ /* hyphens[char_num*2+1] = '0'; */ /* LATER */ hyphens[char_num] = '0'; } /*hyphens[hyphen_len*2] = 0; */ /* LATER */ hyphens[hyphen_len] = 0; /* now, run the finite state machine */ for (char_num=0, here=begin_point; here!=get_vlink(end_point); here=get_vlink(here)) { int ch; if (here == begin_point || here == end_point) ch='.'; else ch = get_lc_code(get_character(here)); while (state!=-1) { /* printf("%*s%s%c",char_num-strlen(get_state_str(state)),"",get_state_str(state),(char)ch);*/ HyphenState *hstate = &dict->states[state]; int k; for (k = 0; k < hstate->num_trans; k++) { if (hstate->trans[k].uni_ch == ch) { char *match; state = hstate->trans[k].new_state; /* printf(" state %d\n",state);*/ match = dict->states[state].match; if (match) { /* +2 because: * 1 string length is one bigger than offset * 1 hyphenation starts before first character */ int offset = char_num + 2 - strlen (match); /* printf ("%*s%s\n", offset,"", match);*/ int m; for (m = 0; match[m]; m++) { if (hyphens[offset+m] < match[m]) hyphens[offset+m] = match[m]; } } goto try_next_letter; } } state = hstate->fallback_state; /* printf (" back to %d\n", state);*/ } /* nothing worked, let's go to the next character*/ state = 0; try_next_letter: ; char_num++; } /* restore the correct pointers*/ set_vlink(last,get_vlink(end_point)); /* pattern is ^.^w^o^r^d^.^ word_len=4, ext_word_len=6, hyphens=7 * check ^ ^ ^ so drop first two and stop after word_len-1 */ for (here=first,char_num=2; here!=left; here=get_vlink(here)) char_num++; for (; here!=right; here=get_vlink(here)) { if (hyphens[char_num] & 1) here = insert_syllable_discretionary(here, lan); char_num++; } hnj_free(hyphens); }