usr.bin/nbperf/nbperf.1

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