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