text: /* 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 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 <fcntl.h>
  #include <sys/mman.h>
  #include <sys/stat.h>
  #include <stdlib.h> /* for NULL, malloc */
  #include <stdio.h>  /* for fprintf */
  #include <string.h> /* for strdup */
  #include <unistd.h> /* for close */
  
  #define noVERBOSE
  
  #include "hnjalloc.h"
  #include "hyphen.h"
  
  static char *
  hnj_strdup (const char *s)
  {
      char *new;
      int l;
  
      l = strlen (s);
      new = hnj_malloc (l + 1);
      memcpy (new, s, l);
      new[l] = 0;
      return new;
  }
  
  /* 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 = 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 = 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 = 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 = 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].ch = ch;
      dict->states[state1].trans[num_trans].new_state = state2;
      dict->states[state1].num_trans++;
  }
  
  #ifdef VERBOSE
  HashTab *global;
  
  static 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->val == state)
                  return e->key;
      return NULL;
  }
  #endif
  
  // Get a line from the dictionary contents.
  static char *
  get_line (char *s, int size, const char *dict_contents, int dict_length,
      int *dict_ptr)
  {
      int len = 0;
      while (len < (size - 1) && *dict_ptr < dict_length) {
          s[len++] = *(dict_contents + *dict_ptr);
          (*dict_ptr)++;
          if (s[len - 1] == '\n')
              break;
      }
      s[len] = '\0';
      if (len > 0) {
          return s;
      } else {
          return NULL;
      }
  }
  
  HyphenDict *
  hnj_hyphen_load (const char *fn)
  {
      if (fn == NULL)
          return NULL;
      const int fd = open(fn, O_RDONLY);
      if (fd == -1)
          return NULL;
      struct stat sb;
      if (fstat(fd, &sb) == -1)  {  /* To obtain file size */
          close(fd);
          return NULL;
      }
  
      const char *addr = mmap(NULL, sb.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
      if (addr == MAP_FAILED) {
          close(fd);
          return NULL;
      }
      HyphenDict *dict = hnj_hyphen_load_from_buffer(addr, sb.st_size);
      munmap((void *)addr, sb.st_size);
      close(fd);
  
      return dict;
  }
  
  HyphenDict *
  hnj_hyphen_load_from_buffer (const char *dict_contents, int dict_length)
  {
      HyphenDict *dict[2];
      HashTab *hashtab;
      char buf[MAX_CHARS];
      char word[MAX_CHARS];
      char pattern[MAX_CHARS];
      char * repl;
      signed char replindex;
      signed char replcut;
      int state_num = 0, last_state;
      int i, j, k;
      char ch;
      int found;
      HashEntry *e;
      int nextlevel = 0;
  
      if (dict_contents == NULL)
          return NULL;
  
      int dict_ptr = 0;
  // loading one or two dictionaries (separated by NEXTLEVEL keyword)
      for (k = 0; k == 0 || (k == 1 && nextlevel); k++) { 
          hashtab = hnj_hash_new ();
  #ifdef VERBOSE
          global = hashtab;
  #endif
          hnj_hash_insert (hashtab, "", 0);
          dict[k] = hnj_malloc (sizeof(HyphenDict));
          dict[k]->num_states = 1;
          dict[k]->states = 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;
  
          /* read in character set info */
          if (k == 0) {
              for (i=0;i<MAX_NAME;i++) dict[k]->cset[i]= 0;
              get_line(dict[k]->cset, sizeof(dict[k]->cset), dict_contents,
                  dict_length, &dict_ptr);
              for (i=0;i<MAX_NAME;i++)
                  if ((dict[k]->cset[i] == '\r') || (dict[k]->cset[i] == '\n'))
                      dict[k]->cset[i] = 0;
              dict[k]->utf8 = (strcmp(dict[k]->cset, "UTF-8") == 0);
          } else {
              strcpy(dict[k]->cset, dict[0]->cset);
              dict[k]->utf8 = dict[0]->utf8;
          }
  
          while (get_line(buf, sizeof(buf), dict_contents, dict_length,
                  &dict_ptr) != NULL)
          {
              if (buf[0] != '%')
              {
                  if (strncmp(buf, "NEXTLEVEL", 9) == 0) {
                      nextlevel = 1;
                      break;
                  } else if (strncmp(buf, "LEFTHYPHENMIN", 13) == 0) {
                      dict[k]->lhmin = atoi(buf + 13);
                      continue;
                  } else if (strncmp(buf, "RIGHTHYPHENMIN", 14) == 0) {
                      dict[k]->rhmin = atoi(buf + 14);
                      continue;
                  } else if (strncmp(buf, "COMPOUNDLEFTHYPHENMIN", 21) == 0) {
                      dict[k]->clhmin = atoi(buf + 21);
                      continue;
                  } else if (strncmp(buf, "COMPOUNDRIGHTHYPHENMIN", 22) == 0) {
                      dict[k]->crhmin = atoi(buf + 22);
                      continue;
                  } 
                  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 = strlen(buf);
                      }
                      repl = hnj_strdup(repl + 1);
                  }
                  for (i = 0; ((buf[i] > ' ') || (buf[i] < 0)); 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[k]->utf8) {
                          int pu = -1;        /* unicode character position */
                          int ps = -1;        /* unicode start position (original replindex) */
                          int 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 = pc;
                              }
                              if ((ps >= 0) && ((pu - ps) == replcut)) {
                                  replcut = (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[k], hashtab, word);
                  dict[k]->states[state_num].match = hnj_strdup (pattern + i);
                  dict[k]->states[state_num].repl = repl;
                  dict[k]->states[state_num].replindex = replindex;
                  if (!replcut) {
                      dict[k]->states[state_num].replcut = strlen(word);
                  } else {
                      dict[k]->states[state_num].replcut = replcut;
                  }
  
                  /* now, put in the prefix transitions */
                  for (; found < 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[k], hashtab, word);
                      hnj_add_trans (dict[k], state_num, last_state, ch);
                  }
              }
          }
  
          /* 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 (k == 2) dict[0]->nextlevel = 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);
  
      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_buf[MAX_WORD];
      char *prep_word;
      int i, j, k;
      int state;
      char ch;
      HyphenState *hstate;
      char *match;
      int offset;
  
      if (word_size + 3 < MAX_WORD)
          prep_word = prep_word_buf;
      else
          prep_word = hnj_malloc (word_size + 3);
  
      j = 0;
      prep_word[j++] = '.';
    
      for (i = 0; i < word_size; i++)
          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);
  
              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';
  
      if (prep_word != prep_word_buf)
          hnj_free (prep_word);
      
      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++;
          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, j;
      for (i = 1, 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++;
          } while (utf8 && (word[j + 1] & 0xc0) == 0xc0);
      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;
      int j = word_size - 2;    
      for (i = 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) 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_buf[MAX_WORD];
      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_buf[MAX_CHARS];
      int matchindex_buf[MAX_CHARS];
      char * matchrepl_buf[MAX_CHARS];
      int * matchlen;
      int * matchindex;
      char ** matchrepl;  
      int isrepl = 0;
      int nHyphCount;
  
      if (word_size + 3 < MAX_CHARS) {
          prep_word = prep_word_buf;
          matchlen = matchlen_buf;
          matchindex = matchindex_buf;
          matchrepl = matchrepl_buf;
      } else {
          prep_word = hnj_malloc (word_size + 3);
          matchlen = hnj_malloc ((word_size + 3) * sizeof(int));
          matchindex = hnj_malloc ((word_size + 3) * sizeof(int));
          matchrepl = hnj_malloc ((word_size + 3) * sizeof(char *));
      }
  
      j = 0;
      prep_word[j++] = '.';
    
      for (i = 0; i < word_size; i++)
          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);
  
              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 && !*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)[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;
          }
      }
  
      if (matchrepl != matchrepl_buf) {
          hnj_free (matchrepl);
          hnj_free (matchlen);
          hnj_free (matchindex);
      }
  
      // recursive hyphenation of the first (compound) level segments
      if (dict->nextlevel) {
          char * rep2_buf[MAX_WORD];
          int pos2_buf[MAX_WORD];
          int cut2_buf[MAX_WORD];
          char hyphens2_buf[MAX_WORD];
          char ** rep2;
          int * pos2;
          int * cut2;
          char * hyphens2;
          int begin = 0;
          if (word_size < MAX_CHARS) {
              rep2 = rep2_buf;
              pos2 = pos2_buf;
              cut2 = cut2_buf;
              hyphens2 = hyphens2_buf;
          } else {
              rep2 = hnj_malloc (word_size * sizeof(char *));
              pos2 = hnj_malloc (word_size * sizeof(int));
              cut2 = hnj_malloc (word_size * sizeof(int));
              hyphens2 = hnj_malloc (word_size);
          }
          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 > 1) {
                      int hyph = 0;
                      prep_word[i + 2] = '\0';
                      /* non-standard hyphenation at compound boundary (Schiffahrt) */
                      if (*rep && *pos && *cut && (*rep)[i]) {
                          char * l = strchr((*rep)[i], '=');
                          strcpy(prep_word + 2 + i - (*pos)[i], (*rep)[i]);
                          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 - 1; 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]) {
                          strcpy(prep_word + 1, word);
                      }
                  }
                  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);
          }
       
          if (rep2 != rep2_buf) {
              free(rep2);
              free(cut2);
              free(pos2);
              free(hyphens2);
          }
      }
  
      if (prep_word != prep_word_buf) 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)
  {
      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 */
      int i, j, k;
      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';
      return 0;
  }
  
  /* get the word with all possible hyphenations (output: hyphword) */
  void hnj_hyphen_hyphword(const char * word, int l, const char * hyphens, 
      char * hyphword, char *** rep, int ** pos, int ** cut)
  {
      int i, j;
      for (i = 0, j = 0; i < l; i++, j++) {
          if (hyphens[i]&1) {
              hyphword[j] = word[i];
              if (*rep && *pos && *cut && (*rep)[i]) {
                  strcpy(hyphword + j - (*pos)[i] + 1, (*rep)[i]);
                  j += strlen((*rep)[i]) - (*pos)[i];
                  i += (*cut)[i] - (*pos)[i];
              } else hyphword[++j] = '=';
          } else hyphword[j] = word[i];
      }
      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));
      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);
      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 > 0 ? lhmin : dict->lhmin);
      rhmin = (rhmin > 0 ? rhmin : dict->rhmin);
      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);
      if (dict->utf8) return hnj_hyphen_norm(word, word_size, hyphens, rep, pos, cut);
      return 0;
  }
  