source: trunk/mgpp/lib/perf_hash.cpp@ 9612

Last change on this file since 9612 was 9612, checked in by kjdon, 17 years ago

added in x++ -> ++x changes submitted by Emanuel Dejanu

  • Property svn:executable set to *
  • Property svn:keywords set to Author Date Id Revision
File size: 23.2 KB
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 <time.h> /* for call to time () in SEED_RANDOM() */
31#include "sysfuncs.h"
32
33#include "local_strings.h"
34#include "memlib.h"
35#include "messages.h"
36#include "perf_hash.h"
37#include "netorder.h" /* [RPAP - Jan 97: Endian Ordering] */
38
39#define FALSE 0
40#define TRUE 1
41
42#define STATIC 0
43
44/* Random Number stuff */
45
46long irandm (long is[2]); /* from random.c */
47
48static long seed[] = {0, 0};
49#define RANDOM() irandm(seed)
50#define SEED_RANDOM(the_seed) do{ seed[0] = the_seed; }while(0)
51
52/* Max number of keys - must be a power of 2 minus 1 */
53static int MAX_M;
54
55
56static int MAX_CH;
57
58
59/* the width of the mapping tables */
60static int MAX_L;
61
62
63
64#define c 1.23
65static int MAX_N;
66
67
68
69
70static u_char *translate;
71
72#define MEMBER 0
73#define ERASED 1
74
75
76
77/* direction constants for the edge oriented 3-graph representation */
78#define A 0
79#define B (MAX_M)
80#define C (2*B)
81
82/* NODEa, NODEb, NODEc, FIRST and NEXT are used to represent a 3-graph */
83static int *NODEa, *NODEb, *NODEc;
84static int *FIRST;
85static int *NEXT;
86
87
88#define norm(e) ((e) % MAX_M)
89/* in general should be ((e) % MAX_M) but MAX_M = 2^k - 1 */
90
91
92static char *mk; /* for marking edges/vertices as removed */
93static int *g; /* array g defines a minimal perfect hash function */
94
95
96
97/* stack of edges, created during the independency */
98/* test, used in the assignment step */
99static struct
100 {
101 int sp;
102 int *st;
103 }
104S;
105#define push(s, e) s.st[s.sp++] = (e)
106#define pop(s, e) e = s.st[--s.sp]
107
108#ifndef STRUCT
109static long **tb0, **tb1, **tb2;
110#else
111struct tb_entry **tb;
112#endif
113
114
115static int
116unique (int v)
117{ /* checks if vertex v belongs to only one edge */
118 return (FIRST[v] != 0 && NEXT[FIRST[v]] == 0) ? FIRST[v] : 0;
119} /*unique */
120
121
122
123
124
125
126
127
128static void
129_delete (int v, int e)
130{ /* deletes edge e from list of v */
131
132 int b;
133
134 b = FIRST[v];
135 assert (norm (b) != 0);
136 if (norm (b) == e)
137 FIRST[v] = NEXT[FIRST[v]];
138 else
139 {
140 while (norm (NEXT[b]) != e)
141 {
142 b = NEXT[b];
143 assert (norm (b) != 0);
144 }
145 NEXT[b] = NEXT[NEXT[b]];
146 }
147} /*delete */
148
149
150
151
152
153
154#if 0
155/* recursively removes the edges of a 3-graph which have at least */
156/* one unique vertex. The removed edges are placed on stack S */
157static void
158ph_remove (int e, int v)
159{
160 int b;
161 mk[e] = ERASED;
162 push (S, e);
163
164 if (NODEa[e] != v)
165 _delete (NODEa[e], e);
166 if (NODEb[e] != v)
167 _delete (NODEb[e], e);
168 if (NODEc[e] != v)
169 _delete (NODEc[e], e);
170
171 if (NODEa[e] != v && mk[b = norm (unique (NODEa[e]))] == MEMBER)
172 ph_remove (b, NODEa[e]);
173 if (NODEb[e] != v && mk[b = norm (unique (NODEb[e]))] == MEMBER)
174 ph_remove (b, NODEb[e]);
175 if (NODEc[e] != v && mk[b = norm (unique (NODEc[e]))] == MEMBER)
176 ph_remove (b, NODEc[e]);
177}
178#else
179
180
181static int StackPos, StackMax;
182static struct Stack
183 {
184 int e, v, m;
185 }
186 *Stack = NULL;
187
188#define StackAdd(_e, _v, _m) \
189 do { \
190 if (StackPos == StackMax) \
191 { \
192 StackMax <<= 1; \
193 if (!(Stack = (struct Stack *)Xrealloc(Stack, sizeof(*Stack) * StackMax))) \
194 return(-1); \
195 } \
196 Stack[StackPos].e = (_e); \
197 Stack[StackPos].v = (_v); \
198 Stack[StackPos++].m = (_m); \
199 } while(0)
200
201
202static int
203ph_remove (int e, int v)
204{
205 if (!Stack)
206 {
207 StackMax = 256;
208 if (!(Stack = (struct Stack *) Xmalloc (sizeof (*Stack) * StackMax)))
209 return (-1);
210 StackPos = 0;
211 }
212 Stack[StackPos].e = e;
213 Stack[StackPos].v = v;
214 Stack[StackPos].m = 0;
215 ++StackPos;
216 while (StackPos)
217 {
218 int m, b;
219 --StackPos;
220 e = Stack[StackPos].e;
221 v = Stack[StackPos].v;
222 m = Stack[StackPos].m;
223
224
225 switch (m)
226 {
227 case 0:
228 {
229 mk[e] = ERASED;
230 push (S, e);
231
232 if (NODEa[e] != v)
233 _delete (NODEa[e], e);
234 if (NODEb[e] != v)
235 _delete (NODEb[e], e);
236 if (NODEc[e] != v)
237 _delete (NODEc[e], e);
238
239 if (NODEa[e] != v && mk[b = norm (unique (NODEa[e]))] == MEMBER)
240 {
241 Stack[StackPos++].m = 1;
242 StackAdd (b, NODEa[e], 0);
243 break;
244 }
245 }
246 case 1:
247 {
248 if (NODEb[e] != v && mk[b = norm (unique (NODEb[e]))] == MEMBER)
249 {
250 Stack[StackPos++].m = 2;
251 StackAdd (b, NODEb[e], 0);
252 break;
253 }
254 }
255 case 2:
256 if (NODEc[e] != v && mk[b = norm (unique (NODEc[e]))] == MEMBER)
257 StackAdd (b, NODEc[e], 0);
258 }
259 }
260 return (0);
261}
262#endif
263
264
265
266
267
268/* returns TRUE if and only if set of edges created in the tree_builder */
269/* procedure form a 3-graph with independent edges. Edges of a 3-graph */
270/* are independent iff repeated deletion of edges containing vertices */
271/* of degree 1 results in a graph with no edges in it. */
272static int
273acyclic (int m, int n)
274{
275
276 int v, e;
277 /* build list of edges for each node */
278 for (v = 1; v <= n; FIRST[v++] = 0);
279 for (e = 1; e <= m; ++e)
280 {
281 NEXT[A + e] = FIRST[NODEa[e]];
282 FIRST[NODEa[e]] = A + e;
283 NEXT[B + e] = FIRST[NODEb[e]];
284 FIRST[NODEb[e]] = B + e;
285 NEXT[C + e] = FIRST[NODEc[e]];
286 FIRST[NODEc[e]] = C + e;
287
288 /* mark edge e as belonging to the hypergraph */
289 mk[e] = MEMBER;
290 }
291
292
293 S.sp = 0; /* empty the stack */
294 mk[0] = ERASED; /* a sentinel for the test below */
295 for (v = 1; v <= n; ++v)
296 {
297 if (mk[e = norm (unique (v))] == MEMBER)
298 ph_remove (e, v);
299 }
300
301 /* check if any edges were left in the graph */
302 return S.sp == m;
303} /*acyclic */
304
305
306
307
308
309
310
311
312/* repeatedly maps words into edges of a 3-graph until the edges */
313/* are independent. */
314static int
315tree_builder (int num, u_char ** keys, int *n)
316{
317
318 int e, k = 0;
319 int i, j;
320 u_char *w;
321
322 do
323 {
324 *n = (int) (num * c + 1);
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 memset (translate, '\0', 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 = (int *) Xmalloc (sizeof (int) * (MAX_M + 1));
688 NODEb = (int *)Xmalloc (sizeof (int) * (MAX_M + 1));
689 NODEc = (int *)Xmalloc (sizeof (int) * (MAX_M + 1));
690 FIRST = (int *)Xmalloc (sizeof (int) * (MAX_N + 1));
691 NEXT = (int *)Xmalloc (sizeof (int) * (MAX_M + 1) * 3);
692 S.st = (int *)Xmalloc (sizeof (int) * MAX_M);
693 mk = (char *)Xmalloc (sizeof (char) * (MAX_N + 1));
694 g = (int *)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 = (tb_entry **)Xmalloc (sizeof (struct tb_entry *) * MAX_CH);
720 for (i = 0; i < MAX_CH; ++i)
721 if (tb)
722 if (!(tb[i] = (tb_entry *)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 = (u_char *)Xmalloc (sizeof (u_char) * 256);
742 memset(translate, '\0', 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 MAX_N = MAX_M + MAX_M / 4;
753
754 if (allocate_memory () == -1)
755 return (NULL);
756
757 /* construct an "acyclic" hypergraph */
758 tree_builder (num, keys, &n);
759 /* compute function g */
760 assign (n);
761
762 if (check (num) != 0)
763 FatalError (1, "An error has been detected in the mphf.");
764 temp_free ();
765
766 if (!(phd = (perf_hash_data *)Xmalloc (sizeof (perf_hash_data))))
767 return (NULL);
768
769 memcpy ((void *) g, (const void *) &g[1], n * sizeof (int));
770
771 phd->MAX_L = MAX_L;
772 phd->MAX_N = n;
773 phd->MAX_M = num;
774 phd->MAX_CH = MAX_CH;
775 phd->translate = translate;
776 phd->g = g;
777#ifndef STRUCT
778 phd->tb0 = tb0;
779 phd->tb1 = tb1;
780 phd->tb2 = tb2;
781#else
782 phd->tb = tb;
783#endif
784 return (phd);
785}
786
787int
788write_perf_hash_data (FILE * f, perf_hash_data * phd)
789{
790 int tot, i;
791 /* [RPAP - Jan 97: Endian Ordering] */
792 HTONSI(phd->MAX_L);
793 HTONSI(phd->MAX_N);
794 HTONSI(phd->MAX_M);
795 HTONSI(phd->MAX_CH);
796
797 tot = fwrite ((char *) &phd->MAX_L, sizeof (int), 1, f) * sizeof (int);
798 tot += fwrite ((char *) &phd->MAX_N, sizeof (int), 1, f) * sizeof (int);
799 tot += fwrite ((char *) &phd->MAX_M, sizeof (int), 1, f) * sizeof (int);
800 tot += fwrite ((char *) &phd->MAX_CH, sizeof (int), 1, f) * sizeof (int);
801
802 /* [RPAP - Jan 97: Endian Ordering] */
803 NTOHSI(phd->MAX_L);
804 NTOHSI(phd->MAX_N);
805 NTOHSI(phd->MAX_M);
806 NTOHSI(phd->MAX_CH);
807
808 tot += fwrite ((char *) phd->translate, sizeof (u_char), 256, f);
809
810 /* [RPAP - Jan 97: Endian Ordering] */
811 for (i = 0; i < phd->MAX_N + 1; ++i)
812 HTONSI(phd->g[i]);
813
814 tot += fwrite ((char *) phd->g, sizeof (int), phd->MAX_N + 1, f) * sizeof (int);
815
816 /* [RPAP - Jan 97: Endian Ordering] */
817 for (i = 0; i < phd->MAX_N + 1; ++i)
818 NTOHSI(phd->g[i]);
819
820#ifndef STRUCT
821 for (i = 0; i < phd->MAX_CH; ++i)
822 {
823 /* [RPAP - Jan 97: Endian Ordering] */
824 int j;
825 for (j = 0; j < phd->MAX_L; ++j)
826 {
827 HTONSI(phd->tb0[i][j]);
828 HTONSI(phd->tb1[i][j]);
829 HTONSI(phd->tb2[i][j]);
830 }
831
832 tot += fwrite ((char *) phd->tb0[i], sizeof (int), phd->MAX_L, f) *
833 sizeof (int);
834 tot += fwrite ((char *) phd->tb1[i], sizeof (int), phd->MAX_L, f) *
835 sizeof (int);
836 tot += fwrite ((char *) phd->tb2[i], sizeof (int), phd->MAX_L, f) *
837 sizeof (int);
838
839 /* [RPAP - Jan 97: Endian Ordering] */
840 for (j = 0; j < phd->MAX_L; ++j)
841 {
842 NTOHSI(phd->tb0[i][j]);
843 NTOHSI(phd->tb1[i][j]);
844 NTOHSI(phd->tb2[i][j]);
845 }
846 }
847#else
848 for (i = 0; i < phd->MAX_CH; ++i)
849 {
850 /* [RPAP - Jan 97: Endian Ordering] */
851 int j;
852 for (j = 0; j < phd->MAX_L; ++j)
853 {
854 HTONSL(phd->tb[i][j].tb0);
855 HTONSL(phd->tb[i][j].tb1);
856 HTONSL(phd->tb[i][j].tb2);
857 }
858
859 tot += fwrite ((char *) phd->tb[i], sizeof (struct tb_entry), phd->MAX_L, f) *
860 sizeof (struct tb_entry);
861
862 /* [RPAP - Jan 97: Endian Ordering] */
863 for (j = 0; j < phd->MAX_L; ++j)
864 {
865 NTOHSL(phd->tb[i][j].tb0);
866 NTOHSL(phd->tb[i][j].tb1);
867 NTOHSL(phd->tb[i][j].tb2);
868 }
869 }
870#endif
871 return (tot);
872}
873
874
875perf_hash_data *
876read_perf_hash_data (FILE * f)
877{
878 perf_hash_data *phd;
879 int i, tot, ok = 1;
880 if (!(phd = (perf_hash_data *)Xmalloc (sizeof (perf_hash_data))))
881 return (NULL);
882 tot = fread ((char *) &phd->MAX_L, sizeof (int), 1, f) * sizeof (int);
883 tot += fread ((char *) &phd->MAX_N, sizeof (int), 1, f) * sizeof (int);
884 tot += fread ((char *) &phd->MAX_M, sizeof (int), 1, f) * sizeof (int);
885 tot += fread ((char *) &phd->MAX_CH, sizeof (int), 1, f) * sizeof (int);
886
887 /* [RPAP - Jan 97: Endian Ordering] */
888 NTOHSI(phd->MAX_L);
889 NTOHSI(phd->MAX_N);
890 NTOHSI(phd->MAX_M);
891 NTOHSI(phd->MAX_CH);
892
893 if (tot != 4 * sizeof (int))
894 return (NULL);
895 phd->translate = (u_char *)Xmalloc (sizeof (u_char) * 256);
896 phd->g = (int *)Xmalloc (sizeof (int) * (phd->MAX_N + 1));
897#ifndef STRUCT
898 phd->tb0 = Xmalloc (sizeof (int *) * phd->MAX_CH);
899 phd->tb1 = Xmalloc (sizeof (int *) * phd->MAX_CH);
900 phd->tb2 = Xmalloc (sizeof (int *) * phd->MAX_CH);
901 for (i = 0; i < phd->MAX_CH; ++i)
902 {
903 if (phd->tb0)
904 if (!(phd->tb0[i] = Xmalloc (sizeof (long) * phd->MAX_L)))
905 ok = 0;
906 if (phd->tb1)
907 if (!(phd->tb1[i] = Xmalloc (sizeof (long) * phd->MAX_L)))
908 ok = 0;
909 if (phd->tb2)
910 if (!(phd->tb2[i] = Xmalloc (sizeof (long) * phd->MAX_L)))
911 ok = 0;
912 }
913 if (!(phd->translate && phd->g && phd->tb0 && phd->tb1 && phd->tb2 && ok))
914 {
915 if (phd->translate)
916 Xfree (phd->translate);
917 if (phd->g)
918 Xfree (phd->g);
919 for (i = 0; i < MAX_CH; ++i)
920 {
921 if (phd->tb0 && phd->tb0[i])
922 Xfree (phd->tb0[i]);
923 if (phd->tb1 && phd->tb1[i])
924 Xfree (phd->tb1[i]);
925 if (phd->tb2 && phd->tb2[i])
926 Xfree (phd->tb2[i]);
927 }
928 if (phd->tb0)
929 Xfree (phd->tb0);
930 if (phd->tb1)
931 Xfree (phd->tb1);
932 if (phd->tb2)
933 Xfree (phd->tb2);
934 Xfree (phd);
935 return (NULL);
936 }
937 tot += fread ((char *) phd->translate, sizeof (u_char), 256, f);
938 tot += fread ((char *) phd->g, sizeof (int), phd->MAX_N + 1, f) * sizeof (int);
939
940 /* [RPAP - Jan 97: Endian Ordering] */
941 for (i = 0; i < phd->MAX_N + 1; ++i)
942 NTOHSI(phd->g[i]);
943
944 for (i = 0; i < phd->MAX_CH; ++i)
945 {
946 int j;
947
948 tot += fread ((char *) phd->tb0[i], sizeof (long), phd->MAX_L, f) *
949 sizeof (int);
950 tot += fread ((char *) phd->tb1[i], sizeof (long), phd->MAX_L, f) *
951 sizeof (int);
952 tot += fread ((char *) phd->tb2[i], sizeof (long), phd->MAX_L, f) *
953 sizeof (int);
954
955 /* [RPAP - Jan 97: Endian Ordering] */
956 for (j = 0; j < phd->MAX_L; ++j)
957 {
958 NTOHSI(phd->tb0[i][j]);
959 NTOHSI(phd->tb1[i][j]);
960 NTOHSI(phd->tb2[i][j]);
961 }
962 }
963#else
964 phd->tb = (struct tb_entry **)Xmalloc (sizeof (struct tb_entry *) * phd->MAX_CH);
965 for (i = 0; i < phd->MAX_CH; ++i)
966 if (phd->tb)
967 if (!(phd->tb[i] = (struct tb_entry *)Xmalloc (sizeof (struct tb_entry) * phd->MAX_L)))
968 ok = 0;
969 if (!(phd->translate && phd->g && phd->tb && ok))
970 {
971 if (phd->translate)
972 Xfree (phd->translate);
973 if (phd->g)
974 Xfree (phd->g);
975 for (i = 0; i < MAX_CH; ++i)
976 if (phd->tb && phd->tb[i])
977 Xfree (phd->tb[i]);
978 if (phd->tb)
979 Xfree (phd->tb);
980 Xfree (phd);
981 return (NULL);
982 }
983 tot += fread ((char *) phd->translate, sizeof (u_char), 256, f);
984 tot += fread ((char *) phd->g, sizeof (int), phd->MAX_N + 1, f) * sizeof (int);
985
986 /* [RPAP - Jan 97: Endian Ordering] */
987 for (i = 0; i < phd->MAX_N + 1; ++i)
988 NTOHSI(phd->g[i]);
989
990 for (i = 0; i < phd->MAX_CH; ++i)
991 {
992 int j;
993
994 tot += fread ((char *) phd->tb[i], sizeof (struct tb_entry), phd->MAX_L, f) *
995 sizeof (struct tb_entry);
996
997 /* [RPAP - Jan 97: Endian Ordering] */
998 for (j = 0; j < phd->MAX_L; ++j)
999 {
1000 NTOHSL(phd->tb[i][j].tb0);
1001 NTOHSL(phd->tb[i][j].tb1);
1002 NTOHSL(phd->tb[i][j].tb2);
1003 }
1004 }
1005#endif
1006 return (phd);
1007}
1008
1009void
1010free_perf_hash (perf_hash_data * phd)
1011{
1012 int i;
1013 if (phd->translate)
1014 Xfree (phd->translate);
1015 if (phd->g)
1016 Xfree (phd->g);
1017 for (i = 0; i < phd->MAX_CH; ++i)
1018 if (phd->tb && phd->tb[i])
1019 Xfree (phd->tb[i]);
1020 if (phd->tb)
1021 Xfree (phd->tb);
1022 Xfree (phd);
1023}
1024
1025
1026int
1027perf_hash (perf_hash_data * phd, u_char * s)
1028{
1029 int u, v, w, i, l;
1030 l = *s++;
1031 i = (l - 1) % phd->MAX_L;
1032 u = v = w = 0;
1033 while (l)
1034 {
1035#ifndef STRUCT
1036 if ((u += phd->tb0[phd->translate[*s]][i]) >= phd->MAX_N)
1037 u -= phd->MAX_N;
1038 if ((v += phd->tb1[phd->translate[*s]][i]) >= phd->MAX_N)
1039 v -= phd->MAX_N;
1040 if ((w += phd->tb2[phd->translate[*s]][i]) >= phd->MAX_N)
1041 w -= phd->MAX_N;
1042#else
1043 struct tb_entry *tbp = &phd->tb[phd->translate[*s]][i];
1044 if ((u += tbp->tb0) >= phd->MAX_N)
1045 u -= phd->MAX_N;
1046 if ((v += tbp->tb1) >= phd->MAX_N)
1047 v -= phd->MAX_N;
1048 if ((w += tbp->tb2) >= phd->MAX_N)
1049 w -= phd->MAX_N;
1050#endif
1051 if (++i >= phd->MAX_L)
1052 i = 0;
1053 --l;
1054 ++s;
1055 }
1056 if (u == v && ++v >= phd->MAX_N)
1057 v = 0;
1058 if (w == v)
1059 {
1060 if (++w >= phd->MAX_N)
1061 w = 0;
1062 if (w == u && ++w >= phd->MAX_N)
1063 w = 0;
1064 }
1065 else if (w == u)
1066 {
1067 if (++w >= phd->MAX_N)
1068 w = 0;
1069 if (w == v && ++w >= phd->MAX_N)
1070 w = 0;
1071 }
1072 return ((phd->g[u] ^ phd->g[v] ^ phd->g[w]) > phd->MAX_M) ? 0 :
1073 (phd->g[u] ^ phd->g[v] ^ phd->g[w]);
1074}
Note: See TracBrowser for help on using the repository browser.