1/* $NetBSD: test_hash.c,v 1.2 2011/02/16 02:14:23 christos Exp $ */
2
3/* Copyright (c) 2010 The NetBSD Foundation, Inc.
4 * All rights reserved.
5 *
6 * This code is derived from software contributed to The NetBSD Foundation
7 * by Mateusz Kocielski.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 * 1. Redistributions of source code must retain the above copyright
13 *    notice, this list of conditions and the following disclaimer.
14 * 2. Redistributions in binary form must reproduce the above copyright
15 *    notice, this list of conditions and the following disclaimer in the
16 *    documentation and/or other materials provided with the distribution.
17 * 3. All advertising materials mentioning features or use of this software
18 *    must display the following acknowledgement:
19 *        This product includes software developed by the NetBSD
20 *        Foundation, Inc. and its contributors.
21 * 4. Neither the name of The NetBSD Foundation nor the names of its
22 *    contributors may be used to endorse or promote products derived
23 *    from this software without specific prior written permission.
24 *
25 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
26 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
27 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
28 * PURPOSE ARE DISCLAIMED.	IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
29 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
30 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
31 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
32 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
33 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
34 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
35 * POSSIBILITY OF SUCH DAMAGE.
36 */
37
38#include <err.h>
39#include <malloc.h>
40#include <stdio.h>
41#include <stdlib.h>
42#include <string.h>
43
44#include <saslc.h>
45
46__RCSID("$NetBSD: test_hash.c,v 1.2 2011/02/16 02:14:23 christos Exp $");
47
48#define MAX_HASH_SIZE	256
49
50/*
51 * List of all property keys.
52 * NB: I did not list those used for debugging as collisions in that
53 * case don't really hurt anything.
54 */
55static const char *keys[] = {
56	SASLC_PROP_AUTHCID,
57	SASLC_PROP_AUTHZID,
58	SASLC_PROP_BASE64IO,
59	SASLC_PROP_CIPHERMASK,
60	SASLC_PROP_DEBUG,
61	SASLC_PROP_HOSTNAME,
62	SASLC_PROP_MAXBUF,
63	SASLC_PROP_PASSWD,
64	SASLC_PROP_QOPMASK,
65	SASLC_PROP_REALM,
66	SASLC_PROP_SECURITY,
67	SASLC_PROP_SERVICE,
68	SASLC_PROP_SERVNAME
69};
70
71/*
72 * This must match the dict.c::saslc__dict_hashval() routine.
73 */
74static size_t
75hash(const char *cp, size_t hsize, size_t hinit, size_t shift)
76{
77	size_t hval;
78
79	hval = hinit;
80	for (/*EMPTY*/; *cp != '\0'; cp++) {
81		hval <<= shift;
82		hval += (size_t)*cp;
83	}
84	return hval % hsize;
85}
86
87static int
88no_collision(size_t hsize, size_t hinit, size_t shift)
89{
90	const char **used;
91	size_t hval, i;
92
93	used = calloc(sizeof(*used), hsize);
94	if (used == NULL)
95		err(EXIT_FAILURE, "calloc");
96	for (i = 0; i < __arraycount(keys); i++) {
97		hval = hash(keys[i], hsize, hinit, shift);
98		if (used[hval] != 0) {
99			free(used);
100			return 0;
101		}
102		used[hval] = keys[i];
103	}
104#if 0
105	for (i = 0; i < hsize; i++) {
106		if (used[i] != NULL)
107			printf("%02zd: %s\n", i, used[i]);
108	}
109#endif
110	free(used);
111	return 1;
112}
113
114static int __dead
115usage(int rval)
116{
117
118	printf("%s [<min hash size> [<max hash size>]]\n", getprogname());
119	printf("min and max hash size must be >= %zu\n", __arraycount(keys));
120	exit(rval);
121}
122
123static void
124show_result(int brief, size_t h, size_t i, size_t s)
125{
126	if (brief)
127	    printf("no collisions: hsize=%zu  hinit=%zu  shift=%zu\n", h, i, s);
128	else {
129		printf("#define HASH_SIZE\t%zu\n", h);
130		printf("#define HASH_INIT\t%zu\n", i);
131		printf("#define HASH_SHIFT\t%zu\n", s);
132	}
133}
134
135int
136main(int argc, char **argv)
137{
138	char *p;
139	size_t i, h, s;
140	size_t h_min, h_max;
141	int brief;
142
143	brief = argc != 1;
144	h_min = 0;
145	h_max = 0;
146	switch (argc) {
147	case 1:
148		h_min = __arraycount(keys);
149		h_max = MAX_HASH_SIZE;
150		break;
151	case 3:
152		h = strtol(argv[2], &p, 0);
153		if (*p != '\0' || h == 0)
154			usage(-1);
155		h_max = h;
156		/*FALLTHROUGH*/
157	case 2:
158		h = strtol(argv[1], &p, 0);
159		if (*p != '\0' || h == 0)
160			usage(-1);
161		h_min = h;
162		if (argc == 2)
163			h_max = h;
164		break;
165	default:
166		usage(0);
167	}
168	if (h_max < __arraycount(keys) ||
169	    h_min < __arraycount(keys) ||
170	    h_max < h_min)
171		usage(-1);
172
173	for (h = h_min; h <= h_max; h++) {
174		for (s = 0; s < 32; s++) {
175			for (i = 0; i < h; i++) {
176				if (no_collision(h, i, s)) {
177					show_result(brief, h, i, s);
178					if (argc == 1)
179						return 0;
180				}
181			}
182		}
183	}
184	return 0;
185}
186