1.\" $NetBSD: nbperf.1,v 1.2 2010/03/03 01:55:04 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 March 3, 2010 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 s 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 an order-preserving minimal perfect hash function and writes 52it to stdout or 53.Ar output . 54.Pp 55The 56.Fl m 57argument instructs 58.Nm 59to write the resulting key mapping to 60.Ar map-file . 61Each line gives the result of the hash function for the corresponding input 62key. 63.Pp 64The parameter 65.Ar utilisation 66determines the space efficiency. 67.Pp 68Supported arguments for 69.Fl a : 70.Bl -tag -width "chm" 71.It Sy chm 72This results in an order preserving minimal perfect hash function. 73The 74.Ar utilisation 75must be at least 2, the default. 76The number of iterations needed grows if the utilisation is very near to 2. 77.It Sy chm3 78Similar to 79.Ar chm . 80The resulting hash function needs three instead of two table lookups when 81compared to 82.Ar chm . 83The 84.Ar utilisation 85must be at least 1.24, the default. 86This makes the output for 87.Ar chm3 88noticable smaller than the output for 89.Ar chm . 90.It Sy bdz 91This results in a non-order preserving minimal perfect hash function. 92Output size is approximately 2.85 bit per key for the default value of 93.Ar utilisation , 941.24. 95This is also the smallest supported value. 96.El 97.Pp 98Supported arguments for 99.Fl h : 100.Bl -tag -width "mi_vector_hash" 101.It Sy mi_vector_hash 102Platform-independent version of Jenkins parallel hash. 103See 104.Xr mi_vector_hash 3 . 105.El 106.Pp 107The number of iterations can be limited with 108.Fl i . 109.Nm 110outputs a function matching 111.Ft uint32_t 112.Fn hash "const void * restrict" "size_t" 113to stdout. 114The function expects the key length as second argument, for strings not 115including the terminating NUL. 116It is the responsibility of the caller to pass in only valid keys or compare 117the resulting index to the key. 118The function name can be changed using 119.Fl n Ar name . 120If the 121.Fl s 122flag is specified, it will be static. 123.Pp 124After each failing iteration, a dot is written to stderr. 125.Pp 126.Nm 127checks for duplicate keys on the first iteration that passed basic hash distribution 128tests. 129In that case, an error message is printed and the program terminates. 130.Sh EXIT STATUS 131.Ex -std 132.Sh SEE ALSO 133.Xr mi_vector_hash 3 134.Sh AUTHORS 135.An J\(:org Sonnenberger 136