root/gsdl/trunk/trunk/mg/lib/perf_hash.c @ 16583

Revision 16583, 23.4 KB (checked in by davidb, 11 years ago)

Undoing change commited in r16582

  • Property svn:executable set to *
  • Property svn:keywords set to Author Date Id Revision
Line 
1/**************************************************************************
2 *
3 * perf_hash.c -- Perfect hashing functions
4 * Copyright (C) 1992  Bohdan S. Majewski
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
19 *
20 **************************************************************************
21 *
22 * 1994 Neil Sharman
23 *      Small modifications were made to the interface so that it fitted in
24 *      with mg.
25 *
26 **************************************************************************/
27
28#define STRUCT
29
30#include "sysfuncs.h"
31
32#include "local_strings.h"
33#include "memlib.h"
34#include "messages.h"
35#include "perf_hash.h"
36#include "netorder.h"  /* [RPAP - Jan 97: Endian Ordering] */
37
38#define FALSE 0
39#define TRUE  1
40
41#define STATIC 0
42
43/* Random Number stuff */
44static long seed[] = {0, 0};
45#define RANDOM() irandm(seed)
46#define SEED_RANDOM(the_seed) do{ seed[0] = the_seed; }while(0)
47
48/* Max number of keys - must be a power of 2 minus 1 */
49static int MAX_M;
50
51
52static int MAX_CH;
53
54
55/* the width of the mapping tables  */
56static int MAX_L;
57
58
59
60#define c     1.23
61static int MAX_N;
62
63/* An arbitrary amount to add to both MAX_N and n for building tree/acyclic
64   graph -- John McPherson - jrm21 (22-02-2001) */
65#define MAX_N_HEADROOM  100
66
67
68static u_char *translate;
69
70#define MEMBER 0
71#define ERASED 1
72
73
74
75/* direction constants for the edge oriented 3-graph representation */
76#define A              0
77#define B        (MAX_M)
78#define C          (2*B)
79
80/* NODEa, NODEb, NODEc, FIRST and NEXT are used to represent a 3-graph */
81static int *NODEa, *NODEb, *NODEc;
82static int *FIRST;
83static int *NEXT;
84
85
86#define norm(e) ((e) % MAX_M)
87/* in general should be ((e) % MAX_M) but MAX_M = 2^k - 1 */
88
89
90static char *mk;        /* for marking edges/vertices as removed */
91static int *g;          /* array g defines a minimal perfect hash function */
92
93
94
95/* stack of edges, created during the independency */
96/* test, used in the assignment step               */
97static struct
98  {
99    int sp;
100    int *st;
101  }
102S;
103#define push(s, e) s.st[s.sp++] = (e)
104#define pop(s, e)  e = s.st[--s.sp]
105
106#ifndef STRUCT
107static long **tb0, **tb1, **tb2;
108#else
109struct tb_entry **tb;
110#endif
111
112
113static int
114unique (int v)
115{               /* checks if vertex v belongs to only one edge */
116  return (FIRST[v] != 0 && NEXT[FIRST[v]] == 0) ? FIRST[v] : 0;
117}               /*unique */
118
119
120
121
122
123
124
125
126static void
127delete (int v, int e)
128{               /* deletes edge e from list of v */
129
130  int b;
131
132  b = FIRST[v];
133  assert (norm (b) != 0);
134  if (norm (b) == e)
135    FIRST[v] = NEXT[FIRST[v]];
136  else
137    {
138      while (norm (NEXT[b]) != e)
139    {
140      b = NEXT[b];
141      assert (norm (b) != 0);
142    }
143      NEXT[b] = NEXT[NEXT[b]];
144    }
145}               /*delete */
146
147
148
149
150
151
152#if 0
153/* recursively removes the edges of a 3-graph which have at least */
154/* one unique vertex. The removed edges are placed on stack S     */
155static void
156ph_remove (int e, int v)
157{
158  int b;
159  mk[e] = ERASED;
160  push (S, e);
161
162  if (NODEa[e] != v)
163    delete (NODEa[e], e);
164  if (NODEb[e] != v)
165    delete (NODEb[e], e);
166  if (NODEc[e] != v)
167    delete (NODEc[e], e);
168
169  if (NODEa[e] != v && mk[b = norm (unique (NODEa[e]))] == MEMBER)
170    ph_remove (b, NODEa[e]);
171  if (NODEb[e] != v && mk[b = norm (unique (NODEb[e]))] == MEMBER)
172    ph_remove (b, NODEb[e]);
173  if (NODEc[e] != v && mk[b = norm (unique (NODEc[e]))] == MEMBER)
174    ph_remove (b, NODEc[e]);
175}
176#else
177
178
179static int StackPos, StackMax;
180static struct Stack
181  {
182    int e, v, m;
183  }
184 *Stack = NULL;
185
186#define StackAdd(_e, _v, _m)                        \
187  do {                                  \
188    if (StackPos == StackMax)                       \
189      {                                 \
190        StackMax <<= 1;                         \
191    if (!(Stack = Xrealloc(Stack, sizeof(*Stack) * StackMax)))  \
192      return(-1);                           \
193      }                                 \
194    Stack[StackPos].e = (_e);                       \
195    Stack[StackPos].v = (_v);                       \
196    Stack[StackPos++].m = (_m);                     \
197  } while(0)
198
199
200static int
201ph_remove (int e, int v)
202{
203  if (!Stack)
204    {
205      StackMax = 256;
206      if (!(Stack = Xmalloc (sizeof (*Stack) * StackMax)))
207    return (-1);
208      StackPos = 0;
209    }
210  Stack[StackPos].e = e;
211  Stack[StackPos].v = v;
212  Stack[StackPos].m = 0;
213  StackPos++;
214  while (StackPos)
215    {
216      int m, b;
217      StackPos--;
218      e = Stack[StackPos].e;
219      v = Stack[StackPos].v;
220      m = Stack[StackPos].m;
221
222
223      switch (m)
224    {
225    case 0:
226      {
227        mk[e] = ERASED;
228        push (S, e);
229
230        if (NODEa[e] != v)
231          delete (NODEa[e], e);
232        if (NODEb[e] != v)
233          delete (NODEb[e], e);
234        if (NODEc[e] != v)
235          delete (NODEc[e], e);
236
237        if (NODEa[e] != v && mk[b = norm (unique (NODEa[e]))] == MEMBER)
238          {
239        Stack[StackPos++].m = 1;
240        StackAdd (b, NODEa[e], 0);
241        break;
242          }
243      }
244    case 1:
245      {
246        if (NODEb[e] != v && mk[b = norm (unique (NODEb[e]))] == MEMBER)
247          {
248        Stack[StackPos++].m = 2;
249        StackAdd (b, NODEb[e], 0);
250        break;
251          }
252      }
253    case 2:
254      if (NODEc[e] != v && mk[b = norm (unique (NODEc[e]))] == MEMBER)
255        StackAdd (b, NODEc[e], 0);
256    }
257    }
258  return (0);
259}
260#endif
261
262
263
264
265
266/* returns TRUE if and only if set of edges created in the tree_builder */
267/* procedure form a 3-graph with independent edges. Edges of a 3-graph  */
268/* are independent iff repeated deletion of edges containing vertices   */
269/* of degree 1 results in a graph with no edges in it.                  */
270static int
271acyclic (int m, int n)
272{
273
274  int v, e;
275  /* build list of edges for each node */
276  for (v = 1; v <= n; FIRST[v++] = 0);
277  for (e = 1; e <= m; e++)
278    {
279      NEXT[A + e] = FIRST[NODEa[e]];
280      FIRST[NODEa[e]] = A + e;
281      NEXT[B + e] = FIRST[NODEb[e]];
282      FIRST[NODEb[e]] = B + e;
283      NEXT[C + e] = FIRST[NODEc[e]];
284      FIRST[NODEc[e]] = C + e;
285
286      /* mark edge e as belonging to the hypergraph */
287      mk[e] = MEMBER;
288    }
289
290
291  S.sp = 0;         /* empty the stack */
292  mk[0] = ERASED;       /* a sentinel for the test below */
293  for (v = 1; v <= n; v++)
294    {
295      if (mk[e = norm (unique (v))] == MEMBER)
296    ph_remove (e, v);
297    }
298
299  /* check if any edges were left in the graph */
300  return S.sp == m;
301}               /*acyclic */
302
303
304
305
306
307
308
309
310/* repeatedly maps words into edges of a 3-graph until the edges */
311/* are independent.                                              */
312static int
313tree_builder (int num, u_char ** keys, int *n)
314{
315
316  int e, k = 0;
317  int i, j;
318  u_char *w;
319
320  do
321    {
322      /* Added variable - need to increase MAX_N on allocate as well */
323      *n = (int) (num * c + MAX_N_HEADROOM); /* john mcpherson 22-02-2001 */
324
325      /* initialize tables of random integers */
326      for (i = 0; i < MAX_CH; i++)
327    for (j = 0; j < MAX_L; j++)
328      {
329#ifndef STRUCT
330        tb0[i][j] = RANDOM () % *n;
331        tb1[i][j] = RANDOM () % *n;
332        tb2[i][j] = RANDOM () % *n;
333#else
334        struct tb_entry *tbp = &tb[i][j];
335        tbp->tb0 = RANDOM () % *n;
336        tbp->tb1 = RANDOM () % *n;
337        tbp->tb2 = RANDOM () % *n;
338#endif
339      }
340
341      /* compute an edge (NODEa[e], NODEb[e], NODEc[e]) for each word */
342      for (e = 1; e <= num; e++)
343    {
344      /*generate an edge corresponding to the ith word */
345      int x = 0, y = 0, z = 0, l;
346      w = keys[e - 1];
347
348      l = *w++;
349      j = (l - 1) % MAX_L;
350
351      do
352        {
353#ifndef STRUCT
354          x += tb0[translate[*w]][j];
355          y += tb1[translate[*w]][j];
356          z += tb2[translate[*w]][j];
357#else
358          struct tb_entry *tbp = &tb[translate[*w]][j];
359          x += tbp->tb0;
360          y += tbp->tb1;
361          z += tbp->tb2;
362#endif
363          if (++j >= MAX_L)
364        j = 0;
365          w++;
366        }
367      while (--l);
368      x = (x % *n) + 1;
369      y = (y % *n) + 1;
370      z = (z % *n) + 1;
371      if (y == x && ++y > *n)
372        y = 1;
373      if (z == x && ++z > *n)
374        z = 1;
375      if (z == y)
376        {
377          if (++z > *n)
378        z = 1;
379          if (z == x && ++z > *n)
380        z = 1;
381        }
382
383      NODEa[e] = x;
384      NODEb[e] = y;
385      NODEc[e] = z;
386    }
387      if (++k > 50)     /* make sure we will not wait for ever */
388    FatalError (1, "Unable to generate the perfect hash function. "
389            "This is probably because there aren't enough words");
390    }
391  while (!acyclic (num, *n));
392  return k;
393}               /*tree_builder */
394
395
396
397
398
399
400
401
402
403/* calculates values of the g function/array so that i-th word is */
404/* placed at the (i-1)st position of a hash table.                */
405static void
406assign (int n)
407{
408
409  int v, w = 0, e;
410
411  /* mark all the vertices of the 3-graph as unassigned */
412  for (v = 1; v <= n; mk[v++] = FALSE);
413
414  while (S.sp > 0)
415    {
416      int xor = 0;
417      pop (S, e);
418      v = NODEa[e];
419      if (mk[v])
420    xor ^= g[v];
421      else
422    {
423      g[w = v] = 0;
424      mk[v] = TRUE;
425    }
426      v = NODEb[e];
427      if (mk[v])
428    xor ^= g[v];
429      else
430    {
431      g[w = v] = 0;
432      mk[v] = TRUE;
433    }
434      v = NODEc[e];
435      if (mk[v])
436    xor ^= g[v];
437      else
438    {
439      g[w = v] = 0;
440      mk[v] = TRUE;
441    }
442      g[w] = (e - 1) ^ xor;
443    }
444}               /*assign */
445
446
447
448
449
450
451
452
453
454/*check returns 0 if no error in mphf is detected, else returns error code */
455static int
456check (int m)
457{
458
459  int e, err_code = 0;
460
461  /*for each word compute its place in hash table and check if correct */
462  for (e = 1; e <= m; e++)
463    {
464      if ((e - 1) != (g[NODEa[e]] ^ g[NODEb[e]] ^ g[NODEc[e]]))
465    {
466      (void) fprintf (stderr, "Error for %dth word detected.\n", e);
467      err_code = e;
468    }
469    }
470  return err_code;
471}               /*check */
472
473
474
475
476
477
478
479#if 0
480void
481outputh (int m, int n)
482{
483
484  int i, j, w = (int) ceil (log10 ((double) n + 1.0)) + 1;
485
486#if 0
487  char *PRG =
488  "int h(char *s)\n"
489  "{\n"
490  "  int u, v, w, i;\n"
491  "i = (strlen(s) - 1) % _HXL;\n"
492  "  u = v = w = 0;\n"
493  "  while(*s)\n"
494  "    {\n"
495  "      u += mt1[(*s) - _HFC][i];\n"
496  "      v += mt2[(*s) - _HFC][i];\n"
497  "      w += mt3[(*s++) - _HFC][i];\n"
498  "      if(++i >= _HXL) i = 0;\n"
499  "    }\n"
500  "  u %= _HFN; v %= _HFN; w %= _HFN;\n"
501  "  if(u == v && ++v >= _HFN) v = 0;\n"
502  "  if(w == u && ++w >= _HFN) w = 0;\n"
503  "  if(w == v && ++w >= _HFN) w = 0;\n"
504  "  if(w == u && ++w >= _HFN) w = 0;\n"
505  "  return (g[u] ^ g[v] ^ g[w]) % _HFM;\n"
506  "};\n\n";
507#endif
508
509  char *PRG =
510  "int h(char *s)\n"
511  "{\n"
512  "  int u, v, w, i;\n"
513  "  i = (strlen(s) - 1) % _HXL;\n"
514  "  u = v = w = 0;\n"
515  "  while(*s)\n"
516  "    {\n"
517  "      if((u += mt1[(*s) - _HFC][i]) >= _HFN) u -= _HFN;\n"
518  "      if((v += mt2[(*s) - _HFC][i]) >= _HFN) v -= _HFN;\n"
519  "      if((w += mt3[(*s++) - _HFC][i]) >= _HFN) w -= _HFN;\n"
520  "      if(++i >= _HXL) i = 0;\n"
521  "    }\n"
522  "  if(u == v && ++v >= _HFN) v = 0;\n"
523  "  if(w == v) \n"
524  "    {\n"
525  "      if(++w >= _HFN) w = 0;\n"
526  "      if(w == u && ++w >= _HFN) w = 0;\n"
527  "    }\n"
528  "  else\n"
529  "    if(w == u)\n"
530  "      {\n"
531  "      if(++w >= _HFN) w = 0;\n"
532  "      if(w == v && ++w >= _HFN) w = 0;\n"
533  "      }\n"
534  "  return ((g[u] ^ g[v] ^ g[w]) > _HFM)? 0 : (g[u] ^ g[v] ^ g[w]);\n"
535  "}\n\n";
536
537  printf ("#define _HFN %d\n#define _HFC %d\n", n, fc);
538  printf ("#define _HFM %d\n#define _HXL %d\n", m, MAX_L);
539  printf ("#define _HFA %d\n\nstatic int g[_HFN] = {\n", lc - fc + 1);
540  for (i = 1; i < n; i++)
541    {
542      if (i % 8 == 0)
543    putchar ('\n');
544      printf ("%5d, ", g[i]);
545    }
546  printf ("%5d};\n\n", g[n]);
547
548  printf ("static int mt1[_HFA][_HXL] = {\n");
549  for (j = fc; j < lc; j++)
550    {
551      printf ("{");
552      for (i = 0; i < MAX_L - 1; i++)
553    printf ("%*d,", w, tb0[j][i]);
554      printf ("%*d},\n", w, tb0[j][MAX_L - 1]);
555    }
556  printf ("{");
557  for (i = 0; i < MAX_L - 1; i++)
558    printf ("%*d,", w, tb0[lc][i]);
559  printf ("%*d}\n", w, tb0[lc][MAX_L - 1]);
560  printf ("};\n\n");
561
562  printf ("static int mt2[_HFA][_HXL] = {\n");
563  for (j = fc; j < lc; j++)
564    {
565      printf ("{");
566      for (i = 0; i < MAX_L - 1; i++)
567    printf ("%*d,", w, tb1[j][i]);
568      printf ("%*d},\n", w, tb1[j][MAX_L - 1]);
569    }
570  printf ("{");
571  for (i = 0; i < MAX_L - 1; i++)
572    printf ("%*d,", w, tb1[lc][i]);
573  printf ("%*d}\n", w, tb1[lc][MAX_L - 1]);
574  printf ("};\n\n");
575
576  printf ("static int mt3[_HFA][_HXL] = {\n");
577  for (j = fc; j < lc; j++)
578    {
579      printf ("{");
580      for (i = 0; i < MAX_L - 1; i++)
581    printf ("%*d,", w, tb2[j][i]);
582      printf ("%*d},\n", w, tb2[j][MAX_L - 1]);
583    }
584  printf ("{");
585  for (i = 0; i < MAX_L - 1; i++)
586    printf ("%*d,", w, tb2[lc][i]);
587  printf ("%*d}\n", w, tb2[lc][MAX_L - 1]);
588  printf ("};\n\n");
589
590  printf ("%s", PRG);
591}               /*outputh */
592#endif
593
594
595
596
597
598
599
600static void
601make_trans_func (int num, u_char ** keys)
602{
603  int i, j;
604
605  bzero ((char *) translate, sizeof (translate));
606
607  MAX_L = 1;
608  for (i = 0; i < num; i++)
609    {
610      unsigned len = keys[i][0];
611      u_char *s = keys[i] + 1;
612      for (; len; len--, s++)
613    translate[*s] = 1;
614      if (i)
615    {
616      int l;
617      l = prefixlen (keys[i - 1], keys[i]);
618      if (l + 1 > MAX_L)
619        MAX_L = l + 1;
620    }
621    }
622  j = 0;
623  for (i = 0; i < 256; i++)
624    if (translate[i])
625      translate[i] = j++;
626  MAX_CH = j;
627}
628
629
630static void
631temp_free (void)
632{
633  if (NODEa)
634    Xfree (NODEa);
635  if (NODEb)
636    Xfree (NODEb);
637  if (NODEc)
638    Xfree (NODEc);
639  if (FIRST)
640    Xfree (FIRST);
641  if (NEXT)
642    Xfree (NEXT);
643  if (S.st)
644    Xfree (S.st);
645  if (mk)
646    Xfree (mk);
647}
648
649static void
650all_free (void)
651{
652  int i;
653  temp_free ();
654  if (translate)
655    Xfree (translate);
656  if (g)
657    Xfree (g);
658#ifndef STRUCT
659  for (i = 0; i < MAX_CH; i++)
660    {
661      if (tb0 && tb0[i])
662    Xfree (tb0[i]);
663      if (tb1 && tb1[i])
664    Xfree (tb1[i]);
665      if (tb2 && tb2[i])
666    Xfree (tb2[i]);
667    }
668  if (tb0)
669    Xfree (tb0);
670  if (tb1)
671    Xfree (tb1);
672  if (tb2)
673    Xfree (tb2);
674#else
675  for (i = 0; i < MAX_CH; i++)
676    if (tb && tb[i])
677      Xfree (tb[i]);
678  if (tb)
679    Xfree (tb);
680#endif
681}
682
683static int
684allocate_memory (void)
685{
686  int i, ok = 1;
687  NODEa = Xmalloc (sizeof (int) * (MAX_M + 1));
688  NODEb = Xmalloc (sizeof (int) * (MAX_M + 1));
689  NODEc = Xmalloc (sizeof (int) * (MAX_M + 1));
690  FIRST = Xmalloc (sizeof (int) * (MAX_N + 1));
691  NEXT = Xmalloc (sizeof (int) * (MAX_M + 1) * 3);
692  S.st = Xmalloc (sizeof (int) * MAX_M);
693  mk = Xmalloc (sizeof (char) * (MAX_N + 1));
694  g = Xmalloc (sizeof (int) * (MAX_N + 1));
695#ifndef STRUCT
696  tb0 = Xmalloc (sizeof (int *) * MAX_CH);
697  tb1 = Xmalloc (sizeof (int *) * MAX_CH);
698  tb2 = Xmalloc (sizeof (int *) * MAX_CH);
699  for (i = 0; i < MAX_CH; i++)
700    {
701      if (tb0)
702    if (!(tb0[i] = Xmalloc (sizeof (long) * MAX_L)))
703        ok = 0;
704      if (tb1)
705    if (!(tb1[i] = Xmalloc (sizeof (long) * MAX_L)))
706        ok = 0;
707      if (tb2)
708    if (!(tb2[i] = Xmalloc (sizeof (long) * MAX_L)))
709        ok = 0;
710    }
711
712  if (!(NODEa && NODEb && NODEc && FIRST && NEXT && S.st && mk && g &&
713    tb0 && tb1 && tb2 && ok))
714    {
715      all_free ();
716      return (-1);
717    }
718#else
719  tb = Xmalloc (sizeof (struct tb_entry *) * MAX_CH);
720  for (i = 0; i < MAX_CH; i++)
721    if (tb)
722      if (!(tb[i] = Xmalloc (sizeof (struct tb_entry) * MAX_L)))
723      ok = 0;
724
725  if (!(NODEa && NODEb && NODEc && FIRST && NEXT && S.st && mk && g &&
726    tb && ok))
727    {
728      all_free ();
729      return (-1);
730    }
731#endif
732  return (0);
733}
734
735
736perf_hash_data *
737gen_hash_func (int num, u_char ** keys, int r)
738{
739  int n;
740  perf_hash_data *phd;
741  translate = Xmalloc (sizeof (u_char) * 256);
742  bzero ((char *) translate, sizeof (u_char) * 256);  /* [RPAP - Feb 97: WIN32 Port] */
743  make_trans_func (num, keys);
744
745  if (r <= 0)
746    SEED_RANDOM ((long) time ((time_t *) NULL));
747  else
748    SEED_RANDOM (r);
749
750  MAX_M = num + 1;
751
752  /* For extremely small lexicons (<4 words), this isn't good enough!
753   -- John McPherson jrm21 22-02-2001 */
754  /* MAX_N = MAX_M + MAX_M / 4; */
755  MAX_N = (int)(ceil (1.25 * MAX_M));
756  /* Add some space for "experimentation" of n in tree_builder() */
757  MAX_N += MAX_N_HEADROOM;
758
759  if (allocate_memory () == -1)
760    return (NULL);
761
762  /* construct an "acyclic" hypergraph */
763  tree_builder (num, keys, &n);
764  /* compute function g */
765  assign (n);
766
767  if (check (num) != 0)
768    FatalError (1, "An error has been detected in the mphf.");
769  temp_free ();
770
771  if (!(phd = Xmalloc (sizeof (perf_hash_data))))
772    return (NULL);
773
774  bcopy ((char *) &g[1], (char *) g, n * sizeof (int));
775
776  phd->MAX_L = MAX_L;
777  phd->MAX_N = n;
778  phd->MAX_M = num;
779  phd->MAX_CH = MAX_CH;
780  phd->translate = translate;
781  phd->g = g;
782#ifndef STRUCT
783  phd->tb0 = tb0;
784  phd->tb1 = tb1;
785  phd->tb2 = tb2;
786#else
787  phd->tb = tb;
788#endif
789  return (phd);
790}
791
792int
793write_perf_hash_data (FILE * f, perf_hash_data * phd)
794{
795  int tot, i;
796  /* [RPAP - Jan 97: Endian Ordering] */
797  HTONSI(phd->MAX_L);
798  HTONSI(phd->MAX_N);
799  HTONSI(phd->MAX_M);
800  HTONSI(phd->MAX_CH);
801
802  tot = fwrite ((char *) &phd->MAX_L, sizeof (int), 1, f) * sizeof (int);
803  tot += fwrite ((char *) &phd->MAX_N, sizeof (int), 1, f) * sizeof (int);
804  tot += fwrite ((char *) &phd->MAX_M, sizeof (int), 1, f) * sizeof (int);
805  tot += fwrite ((char *) &phd->MAX_CH, sizeof (int), 1, f) * sizeof (int);
806
807  /* [RPAP - Jan 97: Endian Ordering] */
808  NTOHSI(phd->MAX_L);
809  NTOHSI(phd->MAX_N);
810  NTOHSI(phd->MAX_M);
811  NTOHSI(phd->MAX_CH);
812
813  tot += fwrite ((char *) phd->translate, sizeof (u_char), 256, f);
814
815  /* [RPAP - Jan 97: Endian Ordering] */
816  for (i = 0; i < phd->MAX_N + 1; i++)
817    HTONSI(phd->g[i]);
818
819  tot += fwrite ((char *) phd->g, sizeof (int), phd->MAX_N + 1, f) * sizeof (int);
820
821  /* [RPAP - Jan 97: Endian Ordering] */
822  for (i = 0; i < phd->MAX_N + 1; i++)
823    NTOHSI(phd->g[i]);
824
825#ifndef STRUCT
826  for (i = 0; i < phd->MAX_CH; i++)
827    {
828      /* [RPAP - Jan 97: Endian Ordering] */
829      int j;
830      for (j = 0; j < phd->MAX_L; j++)
831    {
832      HTONSI(phd->tb0[i][j]);
833      HTONSI(phd->tb1[i][j]);
834      HTONSI(phd->tb2[i][j]);
835    }
836
837      tot += fwrite ((char *) phd->tb0[i], sizeof (int), phd->MAX_L, f) *
838        sizeof (int);
839      tot += fwrite ((char *) phd->tb1[i], sizeof (int), phd->MAX_L, f) *
840        sizeof (int);
841      tot += fwrite ((char *) phd->tb2[i], sizeof (int), phd->MAX_L, f) *
842        sizeof (int);
843
844      /* [RPAP - Jan 97: Endian Ordering] */
845      for (j = 0; j < phd->MAX_L; j++)
846    {
847      NTOHSI(phd->tb0[i][j]);
848      NTOHSI(phd->tb1[i][j]);
849      NTOHSI(phd->tb2[i][j]);
850    }
851    }
852#else
853  for (i = 0; i < phd->MAX_CH; i++)
854    {
855      /* [RPAP - Jan 97: Endian Ordering] */
856      int j;
857      for (j = 0; j < phd->MAX_L; j++)
858    {
859      HTONSL(phd->tb[i][j].tb0);
860      HTONSL(phd->tb[i][j].tb1);
861      HTONSL(phd->tb[i][j].tb2);
862    }
863
864      tot += fwrite ((char *) phd->tb[i], sizeof (struct tb_entry), phd->MAX_L, f) *
865    sizeof (struct tb_entry);
866
867      /* [RPAP - Jan 97: Endian Ordering] */
868      for (j = 0; j < phd->MAX_L; j++)
869    {
870      NTOHSL(phd->tb[i][j].tb0);
871      NTOHSL(phd->tb[i][j].tb1);
872      NTOHSL(phd->tb[i][j].tb2);
873    }
874    }
875#endif
876  return (tot);
877}
878
879
880perf_hash_data *
881read_perf_hash_data (FILE * f)
882{
883  perf_hash_data *phd;
884  int i, tot, ok = 1;
885  if (!(phd = Xmalloc (sizeof (perf_hash_data))))
886    return (NULL);
887  tot = fread ((char *) &phd->MAX_L, sizeof (int), 1, f) * sizeof (int);
888  tot += fread ((char *) &phd->MAX_N, sizeof (int), 1, f) * sizeof (int);
889  tot += fread ((char *) &phd->MAX_M, sizeof (int), 1, f) * sizeof (int);
890  tot += fread ((char *) &phd->MAX_CH, sizeof (int), 1, f) * sizeof (int);
891
892  /* [RPAP - Jan 97: Endian Ordering] */
893  NTOHSI(phd->MAX_L);
894  NTOHSI(phd->MAX_N);
895  NTOHSI(phd->MAX_M);
896  NTOHSI(phd->MAX_CH);
897
898  if (tot != 4 * sizeof (int))
899      return (NULL);
900  phd->translate = Xmalloc (sizeof (u_char) * 256);
901  phd->g = Xmalloc (sizeof (int) * (phd->MAX_N + 1));
902#ifndef STRUCT
903  phd->tb0 = Xmalloc (sizeof (int *) * phd->MAX_CH);
904  phd->tb1 = Xmalloc (sizeof (int *) * phd->MAX_CH);
905  phd->tb2 = Xmalloc (sizeof (int *) * phd->MAX_CH);
906  for (i = 0; i < phd->MAX_CH; i++)
907    {
908      if (phd->tb0)
909    if (!(phd->tb0[i] = Xmalloc (sizeof (long) * phd->MAX_L)))
910        ok = 0;
911      if (phd->tb1)
912    if (!(phd->tb1[i] = Xmalloc (sizeof (long) * phd->MAX_L)))
913        ok = 0;
914      if (phd->tb2)
915    if (!(phd->tb2[i] = Xmalloc (sizeof (long) * phd->MAX_L)))
916        ok = 0;
917    }
918  if (!(phd->translate && phd->g && phd->tb0 && phd->tb1 && phd->tb2 && ok))
919    {
920      if (phd->translate)
921    Xfree (phd->translate);
922      if (phd->g)
923    Xfree (phd->g);
924      for (i = 0; i < MAX_CH; i++)
925    {
926      if (phd->tb0 && phd->tb0[i])
927        Xfree (phd->tb0[i]);
928      if (phd->tb1 && phd->tb1[i])
929        Xfree (phd->tb1[i]);
930      if (phd->tb2 && phd->tb2[i])
931        Xfree (phd->tb2[i]);
932    }
933      if (phd->tb0)
934    Xfree (phd->tb0);
935      if (phd->tb1)
936    Xfree (phd->tb1);
937      if (phd->tb2)
938    Xfree (phd->tb2);
939      Xfree (phd);
940      return (NULL);
941    }
942  tot += fread ((char *) phd->translate, sizeof (u_char), 256, f);
943  tot += fread ((char *) phd->g, sizeof (int), phd->MAX_N + 1, f) * sizeof (int);
944
945  /* [RPAP - Jan 97: Endian Ordering] */
946  for (i = 0; i < phd->MAX_N + 1; i++)
947    NTOHSI(phd->g[i]);
948
949  for (i = 0; i < phd->MAX_CH; i++)
950    {
951      int j;
952
953      tot += fread ((char *) phd->tb0[i], sizeof (long), phd->MAX_L, f) *
954        sizeof (int);
955      tot += fread ((char *) phd->tb1[i], sizeof (long), phd->MAX_L, f) *
956        sizeof (int);
957      tot += fread ((char *) phd->tb2[i], sizeof (long), phd->MAX_L, f) *
958        sizeof (int);
959
960      /* [RPAP - Jan 97: Endian Ordering] */
961      for (j = 0; j < phd->MAX_L; j++)
962    {
963      NTOHSI(phd->tb0[i][j]);
964      NTOHSI(phd->tb1[i][j]);
965      NTOHSI(phd->tb2[i][j]);
966    }
967    }
968#else
969  phd->tb = Xmalloc (sizeof (struct tb_entry *) * phd->MAX_CH);
970  for (i = 0; i < phd->MAX_CH; i++)
971    if (phd->tb)
972      if (!(phd->tb[i] = Xmalloc (sizeof (struct tb_entry) * phd->MAX_L)))
973      ok = 0;
974  if (!(phd->translate && phd->g && phd->tb && ok))
975    {
976      if (phd->translate)
977    Xfree (phd->translate);
978      if (phd->g)
979    Xfree (phd->g);
980      for (i = 0; i < MAX_CH; i++)
981    if (phd->tb && phd->tb[i])
982      Xfree (phd->tb[i]);
983      if (phd->tb)
984    Xfree (phd->tb);
985      Xfree (phd);
986      return (NULL);
987    }
988  tot += fread ((char *) phd->translate, sizeof (u_char), 256, f);
989  tot += fread ((char *) phd->g, sizeof (int), phd->MAX_N + 1, f) * sizeof (int);
990
991  /* [RPAP - Jan 97: Endian Ordering] */
992  for (i = 0; i < phd->MAX_N + 1; i++)
993    NTOHSI(phd->g[i]);
994
995  for (i = 0; i < phd->MAX_CH; i++)
996    {
997      int j;
998
999      tot += fread ((char *) phd->tb[i], sizeof (struct tb_entry), phd->MAX_L, f) *
1000    sizeof (struct tb_entry);
1001
1002      /* [RPAP - Jan 97: Endian Ordering] */
1003      for (j = 0; j < phd->MAX_L; j++)
1004    {
1005      NTOHSL(phd->tb[i][j].tb0);
1006      NTOHSL(phd->tb[i][j].tb1);
1007      NTOHSL(phd->tb[i][j].tb2);
1008    }
1009    }
1010#endif
1011  return (phd);
1012}
1013
1014void
1015free_perf_hash (perf_hash_data * phd)
1016{
1017  int i;
1018  if (phd->translate)
1019    Xfree (phd->translate);
1020  if (phd->g)
1021    Xfree (phd->g);
1022  for (i = 0; i < phd->MAX_CH; i++)
1023    if (phd->tb && phd->tb[i])
1024      Xfree (phd->tb[i]);
1025  if (phd->tb)
1026    Xfree (phd->tb);
1027  Xfree (phd);
1028}
1029
1030
1031int
1032perf_hash (perf_hash_data * phd, u_char * s)
1033{
1034  int u, v, w, i, l;
1035  l = *s++;
1036  i = (l - 1) % phd->MAX_L;
1037  u = v = w = 0;
1038  while (l)
1039    {
1040#ifndef STRUCT
1041      if ((u += phd->tb0[phd->translate[*s]][i]) >= phd->MAX_N)
1042    u -= phd->MAX_N;
1043      if ((v += phd->tb1[phd->translate[*s]][i]) >= phd->MAX_N)
1044    v -= phd->MAX_N;
1045      if ((w += phd->tb2[phd->translate[*s]][i]) >= phd->MAX_N)
1046    w -= phd->MAX_N;
1047#else
1048      struct tb_entry *tbp = &phd->tb[phd->translate[*s]][i];
1049      if ((u += tbp->tb0) >= phd->MAX_N)
1050    u -= phd->MAX_N;
1051      if ((v += tbp->tb1) >= phd->MAX_N)
1052    v -= phd->MAX_N;
1053      if ((w += tbp->tb2) >= phd->MAX_N)
1054    w -= phd->MAX_N;
1055#endif
1056      if (++i >= phd->MAX_L)
1057    i = 0;
1058      l--;
1059      s++;
1060    }
1061  if (u == v && ++v >= phd->MAX_N)
1062    v = 0;
1063  if (w == v)
1064    {
1065      if (++w >= phd->MAX_N)
1066    w = 0;
1067      if (w == u && ++w >= phd->MAX_N)
1068    w = 0;
1069    }
1070  else if (w == u)
1071    {
1072      if (++w >= phd->MAX_N)
1073    w = 0;
1074      if (w == v && ++w >= phd->MAX_N)
1075    w = 0;
1076    }
1077  return ((phd->g[u] ^ phd->g[v] ^ phd->g[w]) > phd->MAX_M) ? 0 :
1078    (phd->g[u] ^ phd->g[v] ^ phd->g[w]);
1079}
Note: See TracBrowser for help on using the browser.