1.\" $NetBSD: nbperf.1,v 1.8 2021/01/07 16:03:08 joerg Exp $ 2.\" 3.\" Copyright (c) 2009 The NetBSD Foundation, Inc. 4.\" All rights reserved. 5.\" 6.\" This code is derived from software contributed to The NetBSD Foundation 7.\" by Joerg Sonnenberger. 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.\" 18.\" THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 19.\" ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 20.\" TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 21.\" PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 22.\" BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 23.\" CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 24.\" SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 25.\" INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 26.\" CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 27.\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 28.\" POSSIBILITY OF SUCH DAMAGE. 29.\" 30.Dd January 5, 2021 31.Dt NBPERF 1 32.Os 33.Sh NAME 34.Nm nbperf 35.Nd compute a perfect hash function 36.Sh SYNOPSIS 37.Nm 38.Op Fl fps 39.Op Fl a Ar algorithm 40.Op Fl c Ar utilisation 41.Op Fl h Ar hash 42.Op Fl i Ar iterations 43.Op Fl m Ar map-file 44.Op Fl n Ar name 45.Op Fl o Ar output 46.Op Ar input 47.Sh DESCRIPTION 48.Nm 49reads a number of keys one per line from standard input or 50.Ar input . 51It computes a minimal perfect hash function and writes it to stdout or 52.Ar output . 53The default algorithm is 54.Qq Sy chm . 55.Pp 56The 57.Fl m 58argument instructs 59.Nm 60to write the resulting key mapping to 61.Ar map-file . 62Each line gives the result of the hash function for the corresponding input 63key. 64.Pp 65The parameter 66.Ar utilisation 67determines the space efficiency. 68.Pp 69Supported arguments for 70.Fl a : 71.Bl -tag -width "chm" 72.It Sy chm 73This results in an order preserving minimal perfect hash function. 74The 75.Ar utilisation 76must be at least 2, the default. 77The number of iterations needed grows if the utilisation is very near to 2. 78.It Sy chm3 79Similar to 80.Ar chm . 81The resulting hash function needs three instead of two table lookups when 82compared to 83.Ar chm . 84The 85.Ar utilisation 86must be at least 1.24, the default. 87This makes the output for 88.Ar chm3 89noticeably smaller than the output for 90.Ar chm . 91.It Sy bpz 92This results in a non-order preserving minimal perfect hash function. 93Output size is approximately 2.79 bit per key for the default value of 94.Ar utilisation , 951.24. 96This is also the smallest supported value. 97.El 98.Pp 99Supported arguments for 100.Fl h : 101.Bl -tag -width "mi_vector_hash" 102.It Sy mi_vector_hash 103Platform-independent version of Jenkins parallel hash. 104See 105.Xr mi_vector_hash 3 . 106.El 107.Pp 108The number of iterations can be limited with 109.Fl i . 110.Nm 111outputs a function matching 112.Ft uint32_t 113.Fn hash "const void * restrict" "size_t" 114to stdout. 115The function expects the key length as second argument, for strings not 116including the terminating NUL. 117It is the responsibility of the caller to pass in only valid keys or compare 118the resulting index to the key. 119The function name can be changed using 120.Fl n Ar name . 121If the 122.Fl s 123flag is specified, it will be static. 124.Pp 125After each failing iteration, a dot is written to stderr. 126.Pp 127.Nm 128checks for duplicate keys on the first iteration that passed 129basic hash distribution tests. 130In that case, an error message is printed and the program terminates. 131.Pp 132If the 133.Fl p 134flag is specified, the hash function is seeded in a stable way. 135This may take longer than the normal random seed, but ensures 136that the output is the same for repeated invocations as long as 137the input is constant. 138.Sh EXIT STATUS 139.Ex -std 140.Sh SEE ALSO 141.Xr mi_vector_hash 3 142.Sh AUTHORS 143.An J\(:org Sonnenberger 144