Context Navigation

← Previous Revision
Latest Revision
Next Revision →
Blame
Revision Log

source: trunk/gsdl/packages/mg/lib/perf_hash.c@ 1153

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

Note: See TracBrowser for help on using the repository browser.

Download in other formats: