root/main/branches/64_bit_Greenstone/greenstone2/common-src/indexers/mg/lib/perf_hash.c @ 24031

Revision 24031, 23.5 KB (checked in by jmt12, 8 years ago)

Found mg indexing randomly broke on 64bit machines. Tracked it down to random.c and perf_hash.c. Replaced all occurances of 'long' (which is not well defined on 64 bit machines) with the more stable mg_s_long (mglong.h) to fix this issue.

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