diff options
Diffstat (limited to 'Build/source/texk/web2c/luatexdir/lang/hyphen.w')
-rw-r--r-- | Build/source/texk/web2c/luatexdir/lang/hyphen.w | 857 |
1 files changed, 857 insertions, 0 deletions
diff --git a/Build/source/texk/web2c/luatexdir/lang/hyphen.w b/Build/source/texk/web2c/luatexdir/lang/hyphen.w new file mode 100644 index 00000000000..f7bbe6bd843 --- /dev/null +++ b/Build/source/texk/web2c/luatexdir/lang/hyphen.w @@ -0,0 +1,857 @@ +% 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. + + +@ @c +#include <stdlib.h> /* for NULL, malloc */ +#include <stdio.h> /* for fprintf */ +#include <string.h> /* for strdup */ +#include <stdlib.h> /* for malloc used by substring inclusion */ + +#define MAXPATHS 40960 + +#ifdef UNX +# include <unistd.h> /* for exit */ +#endif + +#include <kpathsea/c-ctype.h> + +#define noVERBOSE + +#include "lang/hnjalloc.h" +#include "lang/hyphen.h" + +@ @c +static const char _svn_version[] = + "$Id: hyphen.w 3584 2010-04-02 17:45:55Z hhenkel $ " +"$URL: http://foundry.supelec.fr/svn/luatex/tags/beta-0.60.0/source/texk/web2c/luatexdir/lang/hyphen.w $"; + +@ TODO: should be moved to separate library + +@c +static unsigned char *hnj_strdup(const unsigned char *s) +{ + unsigned char *new; + size_t l; + + l = strlen((const char *) s); + new = hnj_malloc((int) 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 + +@c +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 + +@c +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 + +@c +static char *combine(char *expr, const char *subexpr) +{ + size_t l1 = strlen(expr); + size_t l2 = strlen(subexpr); + size_t off = l1 - l2; + unsigned 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; j < l2; j++) { + if (expr[off + j] < subexpr[j]) + expr[off + j] = subexpr[j]; + } + return expr; +} + + +@ ORIGINAL CODE +@c +HashIter *new_HashIter(HashTab * h) +{ + HashIter *i = hnj_malloc(sizeof(HashIter)); + i->e = 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+ + +@c +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! + +@c +static void state_insert(HashTab * hashtab, unsigned char *key, int state) +{ + int i; + HashEntry *e; + + i = (int) (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! + +@c +static void hyppat_insert(HashTab * hashtab, unsigned char *key, char *hyppat) +{ + int i; + HashEntry *e; + + i = (int) (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) { + print_err("Conflicting pattern ignored"); + error(); + } + 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$ + +@c +static int state_lookup(HashTab * hashtab, const unsigned char *key) +{ + int i; + HashEntry *e; + + i = (int) (hnj_string_hash(key) % HASH_SIZE); + for (e = hashtab->entries[i]; e; e = e->next) { + if (!strcmp((const char *) key, (const char *) e->key)) { + return e->u.state; + } + } + return -1; +} + + +@ return state if found, otherwise $-1$ + +@c +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, (const char *) chars, (size_t) l); + key[l] = 0; + i = (int) (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. + +@c +static int hnj_get_state(HyphenDict * dict, + const unsigned char *str, int *state_num) +{ + *state_num = state_lookup(dict->state_num, str); + + if (*state_num >= 0) + return *state_num; + + state_insert(dict->state_num, hnj_strdup(str), 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, + (int) ((dict->num_states << 1) * + (int) 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 + +@c +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, + (int) (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. + +@c +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 = (size_t) (rover - here); + *buf = rover; + return here; + } + rover++; + } + *length = (size_t) (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(void) +{ + 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 + + +@c +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; +#if 0 + 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); + } +#endif + for (i = 0, j = 0, e = 0; (unsigned) i < l; i++) { + if (format[i] >= '0' && format[i] <= '9') + j++; + if (is_utf8_follow(format[i])) + e++; + } + /* |l-e| => number of {\it characters} not {\it bytes} */ + /* |l-j| => number of pattern bytes */ + /* |l-e-j| => number of pattern characters */ + pat = (unsigned char *) malloc((1 + l - (size_t) j)); + org = (char *) malloc((size_t) (2 + l - (size_t) e - (size_t) j)); + /* remove hyphenation encoders (digits) from pat */ + org[0] = '0'; + for (i = 0, j = 0, e = 0; (unsigned) i < l; i++) { + unsigned char c = format[i]; + if (is_utf8_follow(c)) { + pat[j + e++] = c; + } else if (c < '0' || c > '9') { + pat[e + j++] = c; + org[j] = '0'; + } else { + org[j] = (char) c; + } + } + pat[e + j] = 0; + org[j + 1] = 0; + hyppat_insert(dict->patterns, pat, org); + } + dict->pat_length += (int) ((f - begin) + 2); /* 2 for spurious spaces */ + init_hash(&dict->merged); + v = new_HashIter(dict->patterns); + while (nextHash(v, &word)) { + int wordsize = (int) 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((size_t) (l + 1)); + int e = 0; + strncpy((char *) newword, (char *) word, (size_t) l); + newword[l] = 0; + for (i = 0; i < l; i++) + if (is_utf8_follow(newword[i])) + e++; + neworg = malloc((size_t) (l + 2 - e)); + sprintf(neworg, "%0*d", l + 1 - e, 0); /* fill with right amount of '0' */ + hyppat_insert(dict->merged, 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((const unsigned char *) ""), 0); + v = new_HashIter(dict->merged); + while (nextHashStealPattern(v, &word, &pattern)) { + static unsigned char mask[] = { 0x3F, 0x1F, 0xF, 0x7 }; + int j = (int) 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); +} + +@ @c +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 + 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] = '0'; + } + 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) { +#if 0 + printf("%*s%s%c",char_num-strlen(get_state_str(state)),"",get_state_str(state),(char)ch); +#endif + 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; +#if 0 + printf(" state %d\n",state); +#endif + 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 = (int) (char_num + 2 - (int) strlen(match)); +#if 0 + printf ("%*s%s\n", offset,"", match); +#endif + 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; +#if 0 + printf (" back to %d\n", state); +#endif + } + /* 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); +} |