Subversion Repositories Scribus

Rev

Rev 402 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
3 paul 1
/* LibHnj is dual licensed under LGPL and MPL. Boilerplate for both
2
 * licenses follows.
3
 */
4
 
5
/* LibHnj - a library for high quality hyphenation and justification
6
 * Copyright (C) 1998 Raph Levien,
7
 *           (C) 2001 ALTLinux, Moscow (http://www.alt-linux.org),
8
 *           (C) 2001 Peter Novodvorsky (nidd@cs.msu.su)
9
 *
10
 * This library is free software; you can redistribute it and/or
11
 * modify it under the terms of the GNU Library General Public
12
 * License as published by the Free Software Foundation; either
13
 * version 2 of the License, or (at your option) any later version.
14
 *
15
 * This library is distributed in the hope that it will be useful,
16
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
18
 * Library General Public License for more details.
19
 *
20
 * You should have received a copy of the GNU Library General Public
21
 * License along with this library; if not, write to the
22
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
23
 * Boston, MA  02111-1307  USA.
24
*/
25
 
26
/*
27
 * The contents of this file are subject to the Mozilla Public License
28
 * Version 1.0 (the "MPL"); you may not use this file except in
29
 * compliance with the MPL.  You may obtain a copy of the MPL at
30
 * http://www.mozilla.org/MPL/
31
 *
32
 * Software distributed under the MPL is distributed on an "AS IS" basis,
33
 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the MPL
34
 * for the specific language governing rights and limitations under the
35
 * MPL.
36
 *
37
 */
38
#include <stdlib.h> /* for NULL, malloc */
39
#include <stdio.h>  /* for fprintf */
40
#include <string.h> /* for strdup */
41
 
42
#ifdef UNX
43
#include <unistd.h> /* for exit */
44
#endif
45
 
46
#define noVERBOSE
47
 
48
#include "hnjalloc.h"
49
#include "hyphen.h"
50
 
51
static char *
52
hnj_strdup (const char *s)
53
{
54
  char *new;
55
  int l;
56
 
57
  l = strlen (s);
58
  new = hnj_malloc (l + 1);
59
  memcpy (new, s, l);
60
  new[l] = 0;
61
  return new;
62
}
63
 
64
/* a little bit of a hash table implementation. This simply maps strings
65
   to state numbers */
66
 
67
typedef struct _HashTab HashTab;
68
typedef struct _HashEntry HashEntry;
69
 
70
/* A cheap, but effective, hack. */
71
#define HASH_SIZE 31627
72
 
73
struct _HashTab {
74
  HashEntry *entries[HASH_SIZE];
75
};
76
 
77
struct _HashEntry {
78
  HashEntry *next;
79
  char *key;
80
  int val;
81
};
82
 
83
/* a char* hash function from ASU - adapted from Gtk+ */
84
static unsigned int
85
hnj_string_hash (const char *s)
86
{
87
  const char *p;
88
  unsigned int h=0, g;
89
 
90
  for(p = s; *p != '\0'; p += 1) {
91
    h = ( h << 4 ) + *p;
92
    if ( ( g = h & 0xf0000000 ) ) {
93
      h = h ^ (g >> 24);
94
      h = h ^ g;
95
    }
96
  }
97
  return h /* % M */;
98
}
99
 
100
static HashTab *
101
hnj_hash_new (void)
102
{
103
  HashTab *hashtab;
104
  int i;
105
 
106
  hashtab = hnj_malloc (sizeof(HashTab));
107
  for (i = 0; i < HASH_SIZE; i++)
108
    hashtab->entries[i] = NULL;
109
 
110
  return hashtab;
111
}
112
 
113
static void
114
hnj_hash_free (HashTab *hashtab)
115
{
116
  int i;
117
  HashEntry *e, *next;
118
 
119
  for (i = 0; i < HASH_SIZE; i++)
120
    for (e = hashtab->entries[i]; e; e = next)
121
      {
122
        next = e->next;
123
        hnj_free (e->key);
124
        hnj_free (e);
125
      }
126
 
127
  hnj_free (hashtab);
128
}
129
 
130
/* assumes that key is not already present! */
131
static void
132
hnj_hash_insert (HashTab *hashtab, const char *key, int val)
133
{
134
  int i;
135
  HashEntry *e;
136
 
137
  i = hnj_string_hash (key) % HASH_SIZE;
138
  e = hnj_malloc (sizeof(HashEntry));
139
  e->next = hashtab->entries[i];
140
  e->key = hnj_strdup (key);
141
  e->val = val;
142
  hashtab->entries[i] = e;
143
}
144
 
145
/* return val if found, otherwise -1 */
146
static int
147
hnj_hash_lookup (HashTab *hashtab, const char *key)
148
{
149
  int i;
150
  HashEntry *e;
151
 
152
  i = hnj_string_hash (key) % HASH_SIZE;
153
  for (e = hashtab->entries[i]; e; e = e->next)
154
    if (!strcmp (key, e->key))
155
      return e->val;
156
  return -1;
157
}
158
 
159
/* Get the state number, allocating a new state if necessary. */
160
static int
161
hnj_get_state (HyphenDict *dict, HashTab *hashtab, const char *string)
162
{
163
  int state_num;
164
 
165
  state_num = hnj_hash_lookup (hashtab, string);
166
 
167
  if (state_num >= 0)
168
    return state_num;
169
 
170
  hnj_hash_insert (hashtab, string, dict->num_states);
171
  /* predicate is true if dict->num_states is a power of two */
172
  if (!(dict->num_states & (dict->num_states - 1)))
173
    {
174
      dict->states = hnj_realloc (dict->states,
175
                                  (dict->num_states << 1) *
176
                                  sizeof(HyphenState));
177
    }
178
  dict->states[dict->num_states].match = NULL;
179
  dict->states[dict->num_states].fallback_state = -1;
180
  dict->states[dict->num_states].num_trans = 0;
181
  dict->states[dict->num_states].trans = NULL;
182
  return dict->num_states++;
183
}
184
 
185
/* add a transition from state1 to state2 through ch - assumes that the
186
   transition does not already exist */
187
static void
188
hnj_add_trans (HyphenDict *dict, int state1, int state2, char ch)
189
{
190
  int num_trans;
191
 
192
  num_trans = dict->states[state1].num_trans;
193
  if (num_trans == 0)
194
    {
195
      dict->states[state1].trans = hnj_malloc (sizeof(HyphenTrans));
196
    }
197
  else if (!(num_trans & (num_trans - 1)))
198
    {
199
      dict->states[state1].trans = hnj_realloc (dict->states[state1].trans,
200
                                                (num_trans << 1) *
201
                                                sizeof(HyphenTrans));
202
    }
203
  dict->states[state1].trans[num_trans].ch = ch;
204
  dict->states[state1].trans[num_trans].new_state = state2;
205
  dict->states[state1].num_trans++;
206
}
207
 
208
#ifdef VERBOSE
209
HashTab *global;
210
 
211
static char *
212
get_state_str (int state)
213
{
214
  int i;
215
  HashEntry *e;
216
 
217
  for (i = 0; i < HASH_SIZE; i++)
218
    for (e = global->entries[i]; e; e = e->next)
219
      if (e->val == state)
220
        return e->key;
221
  return NULL;
222
}
223
#endif
224
 
225
HyphenDict *
226
hnj_hyphen_load (const char *fn)
227
{
228
  HyphenDict *dict;
229
  HashTab *hashtab;
230
  FILE *f;
231
  char buf[80];
232
  char word[80];
233
  char pattern[80];
234
  int state_num, last_state;
235
  int i, j;
236
  char ch;
237
  int found;
238
  HashEntry *e;
239
 
240
  f = fopen (fn, "r");
241
  if (f == NULL)
242
    return NULL;
243
 
244
  hashtab = hnj_hash_new ();
245
#ifdef VERBOSE
246
  global = hashtab;
247
#endif
248
  hnj_hash_insert (hashtab, "", 0);
249
 
250
  dict = hnj_malloc (sizeof(HyphenDict));
251
  dict->num_states = 1;
252
  dict->states = hnj_malloc (sizeof(HyphenState));
253
  dict->states[0].match = NULL;
254
  dict->states[0].fallback_state = -1;
255
  dict->states[0].num_trans = 0;
256
  dict->states[0].trans = NULL;
257
 
258
  /* read in character set info */
259
  for (i=0;i<MAX_NAME;i++) dict->cset[i]= 0;
260
  fgets(dict->cset,  sizeof(dict->cset),f);
261
  for (i=0;i<MAX_NAME;i++)
262
    if ((dict->cset[i] == '\r') || (dict->cset[i] == '\n'))
263
        dict->cset[i] = 0;
264
 
265
  while (fgets (buf, sizeof(buf), f) != NULL)
266
    {
267
      if (buf[0] != '%')
268
        {
269
          j = 0;
270
          pattern[j] = '0';
271
          for (i = 0; ((buf[i] > ' ') || (buf[i] < 0)); i++)
272
            {
273
              if (buf[i] >= '0' && buf[i] <= '9')
274
                pattern[j] = buf[i];
275
              else
276
                {
277
                  word[j] = buf[i];
278
                  pattern[++j] = '0';
279
                }
280
            }
281
          word[j] = '\0';
282
          pattern[j + 1] = '\0';
283
 
284
          /* Optimize away leading zeroes */
285
          for (i = 0; pattern[i] == '0'; i++);
286
 
287
#ifdef VERBOSE
288
          printf ("word %s pattern %s, j = %d\n", word, pattern + i, j);
289
#endif
290
          found = hnj_hash_lookup (hashtab, word);
291
 
292
          state_num = hnj_get_state (dict, hashtab, word);
293
          dict->states[state_num].match = hnj_strdup (pattern + i);
294
 
295
          /* now, put in the prefix transitions */
296
          for (; found < 0 ;j--)
297
            {
298
              last_state = state_num;
299
              ch = word[j - 1];
300
              word[j - 1] = '\0';
301
              found = hnj_hash_lookup (hashtab, word);
302
              state_num = hnj_get_state (dict, hashtab, word);
303
              hnj_add_trans (dict, state_num, last_state, ch);
304
            }
305
        }
306
    }
307
 
308
  /* Could do unioning of matches here (instead of the preprocessor script).
309
     If we did, the pseudocode would look something like this:
310
 
311
     foreach state in the hash table
312
        foreach i = [1..length(state) - 1]
313
           state to check is substr (state, i)
314
           look it up
315
           if found, and if there is a match, union the match in.
316
 
317
     It's also possible to avoid the quadratic blowup by doing the
318
     search in order of increasing state string sizes - then you
319
     can break the loop after finding the first match.
320
 
321
     This step should be optional in any case - if there is a
322
     preprocessed rule table, it's always faster to use that.
323
 
324
*/
325
 
326
  /* put in the fallback states */
327
  for (i = 0; i < HASH_SIZE; i++)
328
    for (e = hashtab->entries[i]; e; e = e->next)
329
      {
399 Franz 330
/*      for (j = 1; 1; j++) */
205 Franz 331
        for (j = 1; *(e->key); j++)
3 paul 332
          {
333
            state_num = hnj_hash_lookup (hashtab, e->key + j);
334
            if (state_num >= 0)
335
              break;
336
          }
399 Franz 337
        /* KBH: FIXME state 0 fallback_state should always be -1? */
3 paul 338
        if (e->val)
339
          dict->states[e->val].fallback_state = state_num;
340
      }
341
#ifdef VERBOSE
342
  for (i = 0; i < HASH_SIZE; i++)
343
    for (e = hashtab->entries[i]; e; e = e->next)
344
      {
345
        printf ("%d string %s state %d, fallback=%d\n", i, e->key, e->val,
346
                dict->states[e->val].fallback_state);
347
        for (j = 0; j < dict->states[e->val].num_trans; j++)
348
          printf (" %c->%d\n", dict->states[e->val].trans[j].ch,
349
                  dict->states[e->val].trans[j].new_state);
350
      }
351
#endif
352
 
353
#ifndef VERBOSE
354
  hnj_hash_free (hashtab);
355
#endif
356
  fclose(f);
357
  return dict;
358
}
359
 
360
void hnj_hyphen_free (HyphenDict *dict)
361
{
362
  int state_num;
363
  HyphenState *hstate;
364
 
365
  for (state_num = 0; state_num < dict->num_states; state_num++)
366
    {
367
      hstate = &dict->states[state_num];
368
      if (hstate->match)
369
        hnj_free (hstate->match);
370
      if (hstate->trans)
371
        hnj_free (hstate->trans);
372
    }
373
 
374
  hnj_free (dict->states);
375
 
376
  hnj_free (dict);
377
}
378
 
379
#define MAX_WORD 256
380
 
381
int hnj_hyphen_hyphenate (HyphenDict *dict,
382
                           const char *word, int word_size,
383
                           char *hyphens)
384
{
385
  char prep_word_buf[MAX_WORD];
386
  char *prep_word;
387
  int i, j, k;
388
  int state;
389
  char ch;
390
  HyphenState *hstate;
391
  char *match;
392
  int offset;
393
 
394
  if (word_size + 3 < MAX_WORD)
395
    prep_word = prep_word_buf;
396
  else
397
    prep_word = hnj_malloc (word_size + 3);
398
 
399
  j = 0;
400
  prep_word[j++] = '.';
401
 
402
  for (i = 0; i < word_size; i++)
403
      prep_word[j++] = word[i];
404
 
405
  for (i = 0; i < j; i++)                                                      
406
    hyphens[i] = '0';    
407
 
408
  prep_word[j++] = '.';
409
 
410
  prep_word[j] = '\0';
411
#ifdef VERBOSE
412
  printf ("prep_word = %s\n", prep_word);
413
#endif
414
 
415
  /* now, run the finite state machine */
416
  state = 0;
417
  for (i = 0; i < j; i++)
418
    {
419
      ch = prep_word[i];
420
      for (;;)
421
        {
422
 
423
          if (state == -1) {
399 Franz 424
            /* return 1;
425
             KBH: FIXME shouldn't this be as follows? */
3 paul 426
            state = 0;
427
            goto try_next_letter;
428
          }          
429
 
430
#ifdef VERBOSE
431
          char *state_str;
432
          state_str = get_state_str (state);
433
 
434
          for (k = 0; k < i - strlen (state_str); k++)
435
            putchar (' ');
436
          printf ("%s", state_str);
437
#endif
438
 
439
          hstate = &dict->states[state];
440
          for (k = 0; k < hstate->num_trans; k++)
441
            if (hstate->trans[k].ch == ch)
442
              {
443
                state = hstate->trans[k].new_state;
444
                goto found_state;
445
              }
446
          state = hstate->fallback_state;
447
#ifdef VERBOSE
448
          printf (" falling back, fallback_state %d\n", state);
449
#endif
450
        }
451
    found_state:
452
#ifdef VERBOSE
453
      printf ("found state %d\n",state);
454
#endif
455
      /* Additional optimization is possible here - especially,
456
         elimination of trailing zeroes from the match. Leading zeroes
457
         have already been optimized. */
458
      match = dict->states[state].match;
459
      if (match)
460
        {
461
          offset = i + 1 - strlen (match);
462
#ifdef VERBOSE
463
          for (k = 0; k < offset; k++)
464
            putchar (' ');
465
          printf ("%s\n", match);
466
#endif
467
          /* This is a linear search because I tried a binary search and
468
             found it to be just a teeny bit slower. */
469
          for (k = 0; match[k]; k++)
470
            if (hyphens[offset + k] < match[k])
471
              hyphens[offset + k] = match[k];
472
        }
473
 
402 Franz 474
      /* KBH: we need this to make sure we keep looking in a word
475
       for patterns even if the current character is not known in state 0
476
       since patterns for hyphenation may occur anywhere in the word */
3 paul 477
      try_next_letter: ;
478
 
479
    }
480
#ifdef VERBOSE
481
  for (i = 0; i < j; i++)
482
    putchar (hyphens[i]);
483
  putchar ('\n');
484
#endif
485
 
486
  for (i = 0; i < j - 4; i++)
487
#if 0
488
    if (hyphens[i + 1] & 1)
489
      hyphens[i] = '-';
490
#else
491
    hyphens[i] = hyphens[i + 1];
492
#endif
493
  hyphens[0] = '0';
494
  for (; i < word_size; i++)
495
    hyphens[i] = '0';
496
  hyphens[word_size] = '\0';
497
 
498
  if (prep_word != prep_word_buf)
499
    hnj_free (prep_word);
500
  return 0;    
501
}