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