vppinfra: move unused code to extras/deprecated/vppinfra

Type: improvement

Signed-off-by: Dave Barach <dave@barachs.net>
Change-Id: Id28299a188feefa1899d835fd499f018af95d81b

1 files changed, 1017 insertions, 0 deletions

diff --git a/extras/deprecated/vppinfra/phash.c b/extras/deprecated/vppinfra/phash.c
new file mode 100644
index 00000000000..52c29b33f78
--- /dev/null
+++ b/extras/deprecated/vppinfra/phash.c
@@ -0,0 +1,1017 @@
+/*
+ * Copyright (c) 2015 Cisco and/or its affiliates.
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+/*
+  Copyright (c) 2005 Eliot Dresselhaus
+
+  Permission is hereby granted, free of charge, to any person obtaining
+  a copy of this software and associated documentation files (the
+  "Software"), to deal in the Software without restriction, including
+  without limitation the rights to use, copy, modify, merge, publish,
+  distribute, sublicense, and/or sell copies of the Software, and to
+  permit persons to whom the Software is furnished to do so, subject to
+  the following conditions:
+
+  The above copyright notice and this permission notice shall be
+  included in all copies or substantial portions of the Software.
+
+  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
+  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
+  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
+  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+*/
+
+/* This is all stolen from Bob Jenkins and reworked for clib.  Thanks
+   once again Bob for the great work. */
+
+/*
+------------------------------------------------------------------------------
+perfect.c: code to generate code for a hash for perfect hashing.
+(c) Bob Jenkins, September 1996, December 1999
+You may use this code in any way you wish, and it is free.  No warranty.
+I hereby place this in the public domain.
+Source is http://burtleburtle.net/bob/c/perfect.c
+
+This generates a minimal perfect hash function.  That means, given a
+set of n keys, this determines a hash function that maps each of
+those keys into a value in 0..n-1 with no collisions.
+
+The perfect hash function first uses a normal hash function on the key
+to determine (a,b) such that the pair (a,b) is distinct for all
+keys, then it computes a^scramble[tab[b]] to get the final perfect hash.
+tab[] is an array of 1-byte values and scramble[] is a 256-term array of
+2-byte or 4-byte values.  If there are n keys, the length of tab[] is a
+power of two between n/3 and n.
+
+I found the idea of computing distinct (a,b) values in "Practical minimal
+perfect hash functions for large databases", Fox, Heath, Chen, and Daoud,
+Communications of the ACM, January 1992.  They found the idea in Chichelli
+(CACM Jan 1980).  Beyond that, our methods differ.
+
+The key is hashed to a pair (a,b) where a in 0..*alen*-1 and b in
+0..*blen*-1.  A fast hash function determines both a and b
+simultaneously.  Any decent hash function is likely to produce
+hashes so that (a,b) is distinct for all pairs.  I try the hash
+using different values of *salt* until all pairs are distinct.
+
+The final hash is (a XOR scramble[tab[b]]).  *scramble* is a
+predetermined mapping of 0..255 into 0..smax-1.  *tab* is an
+array that we fill in in such a way as to make the hash perfect.
+
+First we fill in all values of *tab* that are used by more than one
+key.  We try all possible values for each position until one works.
+
+This leaves m unmapped keys and m values that something could hash to.
+If you treat unmapped keys as lefthand nodes and unused hash values
+as righthand nodes, and draw a line connecting each key to each hash
+value it could map to, you get a bipartite graph.  We attempt to
+find a perfect matching in this graph.  If we succeed, we have
+determined a perfect hash for the whole set of keys.
+
+*scramble* is used because (a^tab[i]) clusters keys around *a*.
+------------------------------------------------------------------------------
+*/
+
+#include <vppinfra/bitmap.h>
+#include <vppinfra/format.h>
+#include <vppinfra/phash.h>
+#include <vppinfra/random.h>
+
+static void
+init_keys_direct_u32 (phash_main_t * pm)
+{
+  int n_keys_left, b_mask, a_shift;
+  u32 seed;
+  phash_key_t *k;
+
+  seed = pm->hash_seed;
+  b_mask = (1 << pm->b_bits) - 1;
+  a_shift = BITS (seed) - pm->a_bits;
+
+  k = pm->keys;
+  n_keys_left = vec_len (pm->keys);
+
+  while (n_keys_left >= 2)
+    {
+      u32 x0, y0, z0;
+      u32 x1, y1, z1;
+
+      x0 = y0 = z0 = seed;
+      x1 = y1 = z1 = seed;
+      x0 += (u32) k[0].key;
+      x1 += (u32) k[1].key;
+
+      hash_mix32 (x0, y0, z0);
+      hash_mix32 (x1, y1, z1);
+
+      k[0].b = z0 & b_mask;
+      k[1].b = z1 & b_mask;
+      k[0].a = z0 >> a_shift;
+      k[1].a = z1 >> a_shift;
+      if (PREDICT_FALSE (a_shift >= BITS (z0)))
+	k[0].a = k[1].a = 0;
+
+      k += 2;
+      n_keys_left -= 2;
+    }
+
+  if (n_keys_left >= 1)
+    {
+      u32 x0, y0, z0;
+
+      x0 = y0 = z0 = seed;
+      x0 += k[0].key;
+
+      hash_mix32 (x0, y0, z0);
+
+      k[0].b = z0 & b_mask;
+      k[0].a = z0 >> a_shift;
+      if (PREDICT_FALSE (a_shift >= BITS (z0)))
+	k[0].a = 0;
+
+      k += 1;
+      n_keys_left -= 1;
+    }
+}
+
+static void
+init_keys_direct_u64 (phash_main_t * pm)
+{
+  int n_keys_left, b_mask, a_shift;
+  u64 seed;
+  phash_key_t *k;
+
+  seed = pm->hash_seed;
+  b_mask = (1 << pm->b_bits) - 1;
+  a_shift = BITS (seed) - pm->a_bits;
+
+  k = pm->keys;
+  n_keys_left = vec_len (pm->keys);
+
+  while (n_keys_left >= 2)
+    {
+      u64 x0, y0, z0;
+      u64 x1, y1, z1;
+
+      x0 = y0 = z0 = seed;
+      x1 = y1 = z1 = seed;
+      x0 += (u64) k[0].key;
+      x1 += (u64) k[1].key;
+
+      hash_mix64 (x0, y0, z0);
+      hash_mix64 (x1, y1, z1);
+
+      k[0].b = z0 & b_mask;
+      k[1].b = z1 & b_mask;
+      k[0].a = z0 >> a_shift;
+      k[1].a = z1 >> a_shift;
+      if (PREDICT_FALSE (a_shift >= BITS (z0)))
+	k[0].a = k[1].a = 0;
+
+      k += 2;
+      n_keys_left -= 2;
+    }
+
+  if (n_keys_left >= 1)
+    {
+      u64 x0, y0, z0;
+
+      x0 = y0 = z0 = seed;
+      x0 += k[0].key;
+
+      hash_mix64 (x0, y0, z0);
+
+      k[0].b = z0 & b_mask;
+      k[0].a = z0 >> a_shift;
+      if (PREDICT_FALSE (a_shift >= BITS (z0)))
+	k[0].a = 0;
+
+      k += 1;
+      n_keys_left -= 1;
+    }
+}
+
+static void
+init_keys_indirect_u32 (phash_main_t * pm)
+{
+  int n_keys_left, b_mask, a_shift;
+  u32 seed;
+  phash_key_t *k;
+
+  seed = pm->hash_seed;
+  b_mask = (1 << pm->b_bits) - 1;
+  a_shift = BITS (seed) - pm->a_bits;
+
+  k = pm->keys;
+  n_keys_left = vec_len (pm->keys);
+
+  while (n_keys_left >= 2)
+    {
+      u32 xyz[6];
+      u32 x0, y0, z0;
+      u32 x1, y1, z1;
+
+      pm->key_seed2 (pm->private, k[0].key, k[1].key, &xyz);
+
+      x0 = y0 = z0 = seed;
+      x1 = y1 = z1 = seed;
+      x0 += xyz[0];
+      y0 += xyz[1];
+      z0 += xyz[2];
+      x1 += xyz[3];
+      y1 += xyz[4];
+      z1 += xyz[5];
+
+      hash_mix32 (x0, y0, z0);
+      hash_mix32 (x1, y1, z1);
+
+      k[0].b = z0 & b_mask;
+      k[1].b = z1 & b_mask;
+      k[0].a = z0 >> a_shift;
+      k[1].a = z1 >> a_shift;
+      if (PREDICT_FALSE (a_shift >= BITS (z0)))
+	k[0].a = k[1].a = 0;
+
+      k += 2;
+      n_keys_left -= 2;
+    }
+
+  if (n_keys_left >= 1)
+    {
+      u32 xyz[3];
+      u32 x0, y0, z0;
+
+      pm->key_seed1 (pm->private, k[0].key, &xyz);
+
+      x0 = y0 = z0 = seed;
+      x0 += xyz[0];
+      y0 += xyz[1];
+      z0 += xyz[2];
+
+      hash_mix32 (x0, y0, z0);
+
+      k[0].b = z0 & b_mask;
+      k[0].a = z0 >> a_shift;
+      if (PREDICT_FALSE (a_shift >= BITS (z0)))
+	k[0].a = 0;
+
+      k += 1;
+      n_keys_left -= 1;
+    }
+}
+
+static void
+init_keys_indirect_u64 (phash_main_t * pm)
+{
+  int n_keys_left, b_mask, a_shift;
+  u64 seed;
+  phash_key_t *k;
+
+  seed = pm->hash_seed;
+  b_mask = (1 << pm->b_bits) - 1;
+  a_shift = BITS (seed) - pm->a_bits;
+
+  k = pm->keys;
+  n_keys_left = vec_len (pm->keys);
+
+  while (n_keys_left >= 2)
+    {
+      u64 xyz[6];
+      u64 x0, y0, z0;
+      u64 x1, y1, z1;
+
+      pm->key_seed2 (pm->private, k[0].key, k[1].key, &xyz);
+
+      x0 = y0 = z0 = seed;
+      x1 = y1 = z1 = seed;
+      x0 += xyz[0];
+      y0 += xyz[1];
+      z0 += xyz[2];
+      x1 += xyz[3];
+      y1 += xyz[4];
+      z1 += xyz[5];
+
+      hash_mix64 (x0, y0, z0);
+      hash_mix64 (x1, y1, z1);
+
+      k[0].b = z0 & b_mask;
+      k[1].b = z1 & b_mask;
+      k[0].a = z0 >> a_shift;
+      k[1].a = z1 >> a_shift;
+      if (PREDICT_FALSE (a_shift >= BITS (z0)))
+	k[0].a = k[1].a = 0;
+
+      k += 2;
+      n_keys_left -= 2;
+    }
+
+  if (n_keys_left >= 1)
+    {
+      u64 xyz[3];
+      u64 x0, y0, z0;
+
+      pm->key_seed1 (pm->private, k[0].key, &xyz);
+
+      x0 = y0 = z0 = seed;
+      x0 += xyz[0];
+      y0 += xyz[1];
+      z0 += xyz[2];
+
+      hash_mix64 (x0, y0, z0);
+
+      k[0].b = z0 & b_mask;
+      k[0].a = z0 >> a_shift;
+      if (PREDICT_FALSE (a_shift >= BITS (z0)))
+	k[0].a = 0;
+
+      k += 1;
+      n_keys_left -= 1;
+    }
+}
+
+/*
+ * insert keys into table according to key->b
+ * check if the initial hash might work
+ */
+static int
+init_tabb (phash_main_t * pm)
+{
+  int no_collisions;
+  phash_tabb_t *tb;
+  phash_key_t *k, *l;
+
+  if (pm->key_seed1)
+    {
+      if (pm->flags & PHASH_FLAG_MIX64)
+	init_keys_indirect_u64 (pm);
+      else
+	init_keys_indirect_u32 (pm);
+    }
+  else
+    {
+      if (pm->flags & PHASH_FLAG_MIX64)
+	init_keys_direct_u64 (pm);
+      else
+	init_keys_direct_u32 (pm);
+    }
+
+  if (!pm->tabb)
+    vec_resize (pm->tabb, 1 << pm->b_bits);
+  else
+    vec_foreach (tb, pm->tabb) phash_tabb_free (tb);
+
+  /* Two keys with the same (a,b) guarantees a collision */
+  no_collisions = 1;
+  vec_foreach (k, pm->keys)
+  {
+    u32 i, *ki;
+
+    tb = pm->tabb + k->b;
+    ki = tb->keys;
+    for (i = 0; i < vec_len (ki); i++)
+      {
+	l = pm->keys + ki[i];
+	if (k->a == l->a)
+	  {
+	    /* Given keys are supposed to be unique. */
+	    if (pm->key_is_equal
+		&& pm->key_is_equal (pm->private, l->key, k->key))
+	      clib_error ("duplicate keys");
+	    no_collisions = 0;
+	    goto done;
+	  }
+      }
+
+    vec_add1 (tb->keys, k - pm->keys);
+  }
+
+done:
+  return no_collisions;
+}
+
+/* Try to apply an augmenting list */
+static int
+apply (phash_main_t * pm, u32 tail, u32 rollback)
+{
+  phash_key_t *k;
+  phash_tabb_t *pb;
+  phash_tabq_t *q_child, *q_parent;
+  u32 ki, i, hash, child, parent;
+  u32 stabb;			/* scramble[tab[b]] */
+  int no_collision;
+
+  no_collision = 1;
+
+  /* Walk from child to parent until root is reached. */
+  for (child = tail - 1; child; child = parent)
+    {
+      q_child = &pm->tabq[child];
+      parent = q_child->parent_q;
+      q_parent = &pm->tabq[parent];
+
+      /* find parent's list of siblings */
+      ASSERT (q_parent->b_q < vec_len (pm->tabb));
+      pb = pm->tabb + q_parent->b_q;
+
+      /* erase old hash values */
+      stabb = pm->scramble[pb->val_b];
+      for (i = 0; i < vec_len (pb->keys); i++)
+	{
+	  ki = pb->keys[i];
+	  k = pm->keys + ki;
+	  hash = k->a ^ stabb;
+
+	  /* Erase hash for all of child's siblings. */
+	  if (ki == pm->tabh[hash])
+	    pm->tabh[hash] = ~0;
+	}
+
+      /* change pb->val_b, which will change the hashes of all parent siblings */
+      pb->val_b = rollback ? q_child->oldval_q : q_child->newval_q;
+
+      /* set new hash values */
+      stabb = pm->scramble[pb->val_b];
+      for (i = 0; i < vec_len (pb->keys); i++)
+	{
+	  ki = pb->keys[i];
+	  k = pm->keys + ki;
+
+	  hash = k->a ^ stabb;
+	  if (rollback)
+	    {
+	      if (parent == 0)
+		continue;	/* root never had a hash */
+	    }
+	  else if (pm->tabh[hash] != ~0)
+	    {
+	      /* Very rare case: roll back any changes. */
+	      apply (pm, tail, /* rollback changes */ 1);
+	      no_collision = 0;
+	      goto done;
+	    }
+	  pm->tabh[hash] = ki;
+	}
+    }
+
+done:
+  return no_collision;
+}
+
+
+/*
+-------------------------------------------------------------------------------
+augment(): Add item to the mapping.
+
+Construct a spanning tree of *b*s with *item* as root, where each
+parent can have all its hashes changed (by some new val_b) with
+at most one collision, and each child is the b of that collision.
+
+I got this from Tarjan's "Data Structures and Network Algorithms".  The
+path from *item* to a *b* that can be remapped with no collision is
+an "augmenting path".  Change values of tab[b] along the path so that
+the unmapped key gets mapped and the unused hash value gets used.
+
+Assuming 1 key per b, if m out of n hash values are still unused,
+you should expect the transitive closure to cover n/m nodes before
+an unused node is found.  Sum(i=1..n)(n/i) is about nlogn, so expect
+this approach to take about nlogn time to map all single-key b's.
+-------------------------------------------------------------------------------
+
+high_water: a value higher than any now in tabb[].water_b.
+*/
+static int
+augment (phash_main_t * pm, u32 b_root, u32 high_water)
+{
+  u32 q;			/* current position walking through the queue */
+  u32 tail;			/* tail of the queue.  0 is the head of the queue. */
+  phash_tabb_t *tb_parent, *tb_child, *tb_hit;
+  phash_key_t *k_parent, *k_child;
+  u32 v, v_limit;		/* possible value for myb->val_b */
+  u32 i, ki, hash;
+
+  v_limit =
+    1 << ((pm->flags & PHASH_FLAG_USE_SCRAMBLE) ? pm->s_bits : BITS (u8));
+
+  /* Initialize the root of the spanning tree. */
+  pm->tabq[0].b_q = b_root;
+  tail = 1;
+
+  /* construct the spanning tree by walking the queue, add children to tail */
+  for (q = 0; q < tail; q++)
+    {
+      if ((pm->flags & PHASH_FLAG_FAST_MODE)
+	  && !(pm->flags & PHASH_FLAG_MINIMAL) && q == 1)
+	break;			/* don't do transitive closure */
+
+      tb_parent = pm->tabb + pm->tabq[q].b_q;	/* the b for this node */
+
+      for (v = 0; v < v_limit; v++)
+	{
+	  tb_child = 0;
+
+	  for (i = 0; i < vec_len (tb_parent->keys); i++)
+	    {
+	      ki = tb_parent->keys[i];
+	      k_parent = pm->keys + ki;
+
+	      hash = k_parent->a ^ pm->scramble[v];
+	      if (hash >= pm->hash_max)
+		goto try_next_v;	/* hash code out of bounds => we can't use this v */
+
+	      ki = pm->tabh[hash];
+	      if (ki == ~0)
+		continue;
+
+	      k_child = pm->keys + ki;
+	      tb_hit = pm->tabb + k_child->b;
+
+	      if (tb_child)
+		{
+		  /* Hit at most one child b. */
+		  if (tb_child == tb_hit)
+		    goto try_next_v;
+		}
+	      else
+		{
+		  /* Remember this as child b. */
+		  tb_child = tb_hit;
+		  if (tb_hit->water_b == high_water)
+		    goto try_next_v;	/* already explored */
+		}
+	    }
+
+	  /* tb_parent with v has either one or zero collisions. */
+
+	  /* add child b to the queue of reachable things */
+	  if (tb_child)
+	    tb_child->water_b = high_water;
+	  pm->tabq[tail].b_q = tb_child ? tb_child - pm->tabb : ~0;
+	  pm->tabq[tail].newval_q = v;	/* how to make parent (myb) use this hash */
+	  pm->tabq[tail].oldval_q = tb_parent->val_b;	/* need this for rollback */
+	  pm->tabq[tail].parent_q = q;
+	  ++tail;
+
+	  /* Found a v with no collisions? */
+	  if (!tb_child)
+	    {
+	      /* Try to apply the augmenting path. */
+	      if (apply (pm, tail, /* rollback */ 0))
+		return 1;	/* success, item was added to the perfect hash */
+	      --tail;		/* don't know how to handle such a child! */
+	    }
+
+	try_next_v:
+	  ;
+	}
+    }
+  return 0;
+}
+
+
+static phash_tabb_t *sort_tabb;
+
+static int
+phash_tabb_compare (void *a1, void *a2)
+{
+  u32 *b1 = a1;
+  u32 *b2 = a2;
+  phash_tabb_t *tb1, *tb2;
+
+  tb1 = sort_tabb + b1[0];
+  tb2 = sort_tabb + b2[0];
+
+  return ((int) vec_len (tb2->keys) - (int) vec_len (tb1->keys));
+}
+
+/* find a mapping that makes this a perfect hash */
+static int
+perfect (phash_main_t * pm)
+{
+  u32 i;
+
+  /* clear any state from previous attempts */
+  if (vec_bytes (pm->tabh))
+    clib_memset (pm->tabh, ~0, vec_bytes (pm->tabh));
+
+  vec_validate (pm->tabb_sort, vec_len (pm->tabb) - 1);
+  for (i = 0; i < vec_len (pm->tabb_sort); i++)
+    pm->tabb_sort[i] = i;
+
+  sort_tabb = pm->tabb;
+
+  vec_sort_with_function (pm->tabb_sort, phash_tabb_compare);
+
+  /* In descending order by number of keys, map all *b*s */
+  for (i = 0; i < vec_len (pm->tabb_sort); i++)
+    {
+      if (!augment (pm, pm->tabb_sort[i], i + 1))
+	return 0;
+    }
+
+  /* Success!  We found a perfect hash of all keys into 0..nkeys-1. */
+  return 1;
+}
+
+
+/*
+ * Find initial a_bits = log2 (a_max), b_bits = log2 (b_max).
+ * Initial a_max and b_max values were found empirically.  Some factors:
+ *
+ * If s_max<256 there is no scramble, so tab[b] needs to cover 0..s_max-1.
+ *
+ * a_max and b_max must be powers of 2 because the values in 0..a_max-1 and
+ * 0..b_max-1 are produced by applying a bitmask to the initial hash function.
+ *
+ * a_max must be less than s_max, in fact less than n_keys, because otherwise
+ * there would often be no i such that a^scramble[i] is in 0..n_keys-1 for
+ * all the *a*s associated with a given *b*, so there would be no legal
+ * value to assign to tab[b].  This only matters when we're doing a minimal
+ * perfect hash.
+ *
+ * It takes around 800 trials to find distinct (a,b) with nkey=s_max*(5/8)
+ * and a_max*b_max = s_max*s_max/32.
+ *
+ * Values of b_max less than s_max/4 never work, and s_max/2 always works.
+ *
+ * We want b_max as small as possible because it is the number of bytes in
+ * the huge array we must create for the perfect hash.
+ *
+ * When nkey <= s_max*(5/8), b_max=s_max/4 works much more often with
+ * a_max=s_max/8 than with a_max=s_max/4.  Above s_max*(5/8), b_max=s_max/4
+ * doesn't seem to care whether a_max=s_max/8 or a_max=s_max/4.  I think it
+ * has something to do with 5/8 = 1/8 * 5.  For example examine 80000,
+ * 85000, and 90000 keys with different values of a_max.  This only matters
+ * if we're doing a minimal perfect hash.
+ *
+ * When a_max*b_max <= 1<<U32BITS, the initial hash must produce one integer.
+ * Bigger than that it must produce two integers, which increases the
+ * cost of the hash per character hashed.
+ */
+static void
+guess_initial_parameters (phash_main_t * pm)
+{
+  u32 s_bits, s_max, a_max, b_max, n_keys;
+  int is_minimal, is_fast_mode;
+  const u32 b_max_use_scramble_threshold = 4096;
+
+  is_minimal = (pm->flags & PHASH_FLAG_MINIMAL) != 0;
+  is_fast_mode = (pm->flags & PHASH_FLAG_FAST_MODE) != 0;
+
+  n_keys = vec_len (pm->keys);
+  s_bits = max_log2 (n_keys);
+  s_max = 1 << s_bits;
+  a_max = 0;
+
+  if (is_minimal)
+    {
+      switch (s_bits)
+	{
+	case 0:
+	  a_max = 1;
+	  b_max = 1;
+	case 1:
+	case 2:
+	case 3:
+	case 4:
+	case 5:
+	case 6:
+	case 7:
+	case 8:
+	  /*
+	   * Was: a_max = is_minimal ? s_max / 2 : s_max;
+	   * However, we know that is_minimal must be true, so the
+	   * if-arm of the ternary expression is always executed.
+	   */
+	  a_max = s_max / 2;
+	  b_max = s_max / 2;
+	  break;
+	case 9:
+	case 10:
+	case 11:
+	case 12:
+	case 13:
+	case 14:
+	case 15:
+	case 16:
+	case 17:
+	  if (is_fast_mode)
+	    {
+	      a_max = s_max / 2;
+	      b_max = s_max / 4;
+	    }
+	  else if (s_max / 4 < b_max_use_scramble_threshold)
+	    {
+	      if (n_keys <= s_max * 0.52)
+		a_max = b_max = s_max / 8;
+	      else
+		a_max = b_max = s_max / 4;
+	    }
+	  else
+	    {
+	      a_max = ((n_keys <= s_max * (5.0 / 8.0)) ? s_max / 8 :
+		       (n_keys <=
+			s_max * (3.0 / 4.0)) ? s_max / 4 : s_max / 2);
+	      b_max = s_max / 4;	/* always give the small size a shot */
+	    }
+	  break;
+	case 18:
+	  if (is_fast_mode)
+	    a_max = b_max = s_max / 2;
+	  else
+	    {
+	      a_max = s_max / 8;	/* never require the multiword hash */
+	      b_max = (n_keys <= s_max * (5.0 / 8.0)) ? s_max / 4 : s_max / 2;
+	    }
+	  break;
+	case 19:
+	case 20:
+	  a_max = (n_keys <= s_max * (5.0 / 8.0)) ? s_max / 8 : s_max / 2;
+	  b_max = (n_keys <= s_max * (5.0 / 8.0)) ? s_max / 4 : s_max / 2;
+	  break;
+	default:
+	  /* Just find a hash as quick as possible.
+	     We'll be thrashing virtual memory at this size. */
+	  a_max = b_max = s_max / 2;
+	  break;
+	}
+    }
+  else
+    {
+      /* Non-minimal perfect hash. */
+      if (is_fast_mode && n_keys > s_max * 0.8)
+	{
+	  s_max *= 2;
+	  s_bits += 1;
+	}
+
+      if (s_max / 4 <= (1 << 14))
+	b_max = ((n_keys <= s_max * 0.56) ? s_max / 32 :
+		 (n_keys <= s_max * 0.74) ? s_max / 16 : s_max / 8);
+      else
+	b_max = ((n_keys <= s_max * 0.6) ? s_max / 16 :
+		 (n_keys <= s_max * 0.8) ? s_max / 8 : s_max / 4);
+
+      if (is_fast_mode && b_max < s_max / 8)
+	b_max = s_max / 8;
+
+      if (a_max < 1)
+	a_max = 1;
+      if (b_max < 1)
+	b_max = 1;
+    }
+
+  ASSERT (s_max == (1 << s_bits));
+  ASSERT (is_pow2 (a_max));
+  ASSERT (is_pow2 (b_max));
+  pm->s_bits = s_bits;
+  pm->a_bits = min_log2 (a_max);
+  pm->b_bits = min_log2 (b_max);
+  if (b_max >= b_max_use_scramble_threshold)
+    pm->flags |= PHASH_FLAG_USE_SCRAMBLE;
+}
+
+/* compute p(x), where p is a permutation of 0..(1<<nbits)-1 */
+/* permute(0)=0.  This is intended and useful. */
+always_inline u32
+scramble_permute (u32 x, u32 nbits)
+{
+  int i;
+  int mask = (1 << nbits) - 1;
+  int const2 = 1 + nbits / 2;
+  int const3 = 1 + nbits / 3;
+  int const4 = 1 + nbits / 4;
+  int const5 = 1 + nbits / 5;
+  for (i = 0; i < 20; i++)
+    {
+      x = (x + (x << const2)) & mask;
+      x = (x ^ (x >> const3));
+      x = (x + (x << const4)) & mask;
+      x = (x ^ (x >> const5));
+    }
+  return x;
+}
+
+/* initialize scramble[] with distinct random values in 0..smax-1 */
+static void
+scramble_init (phash_main_t * pm)
+{
+  u32 i;
+
+  /* fill scramble[] with distinct random integers in 0..smax-1 */
+  vec_validate (pm->scramble, (1 << (pm->s_bits < 8 ? 8 : pm->s_bits)) - 1);
+  for (i = 0; i < vec_len (pm->scramble); i++)
+    pm->scramble[i] = scramble_permute (i, pm->s_bits);
+}
+
+/* Try to find a perfect hash function. */
+clib_error_t *
+phash_find_perfect_hash (phash_main_t * pm)
+{
+  clib_error_t *error = 0;
+  u32 max_a_bits, n_tries_this_a_b, want_minimal;
+
+  /* guess initial values for s_max, a_max and b_max */
+  guess_initial_parameters (pm);
+
+  want_minimal = pm->flags & PHASH_FLAG_MINIMAL;
+
+new_s:
+  if (pm->b_bits == 0)
+    pm->a_bits = pm->s_bits;
+
+  max_a_bits = pm->s_bits - want_minimal;
+  if (max_a_bits < 1)
+    max_a_bits = 1;
+
+  pm->hash_max = want_minimal ? vec_len (pm->keys) : (1 << pm->s_bits);
+
+  scramble_init (pm);
+
+  /* Allocate working memory. */
+  vec_free (pm->tabh);
+  vec_validate_init_empty (pm->tabh, pm->hash_max - 1, ~0);
+  vec_free (pm->tabq);
+  vec_validate (pm->tabq, 1 << pm->b_bits);
+
+  /* Actually find the perfect hash */
+  n_tries_this_a_b = 0;
+  while (1)
+    {
+      /* Choose random hash seeds until keys become unique. */
+      pm->hash_seed = random_u64 (&pm->random_seed);
+      pm->n_seed_trials++;
+      if (init_tabb (pm))
+	{
+	  /* Found unique (A, B). */
+
+	  /* Hash may already be perfect. */
+	  if (pm->b_bits == 0)
+	    goto done;
+
+	  pm->n_perfect_calls++;
+	  if (perfect (pm))
+	    goto done;
+
+	  goto increase_b;
+	}
+
+      /* Keep trying with different seed value. */
+      n_tries_this_a_b++;
+      if (n_tries_this_a_b < 2048)
+	continue;
+
+      /* Try to put more bits in (A,B) to make distinct (A,B) more likely */
+      if (pm->a_bits < max_a_bits)
+	pm->a_bits++;
+      else if (pm->b_bits < pm->s_bits)
+	{
+	increase_b:
+	  vec_resize (pm->tabb, vec_len (pm->tabb));
+	  vec_resize (pm->tabq, vec_len (pm->tabq));
+	  pm->b_bits++;
+	}
+      else
+	{
+	  /* Can't increase (A, B) any more, so try increasing S. */
+	  goto new_s;
+	}
+    }
+
+done:
+  /* Construct mapping table for hash lookups. */
+  if (!error)
+    {
+      u32 b, v;
+
+      pm->a_shift = ((pm->flags & PHASH_FLAG_MIX64) ? 64 : 32) - pm->a_bits;
+      pm->b_mask = (1 << pm->b_bits) - 1;
+
+      vec_resize (pm->tab, vec_len (pm->tabb));
+      for (b = 0; b < vec_len (pm->tabb); b++)
+	{
+	  v = pm->tabb[b].val_b;
+
+	  /* Apply scramble now for small enough value of b_bits. */
+	  if (!(pm->flags & PHASH_FLAG_USE_SCRAMBLE))
+	    v = pm->scramble[v];
+
+	  pm->tab[b] = v;
+	}
+    }
+
+  /* Free working memory. */
+  phash_main_free_working_memory (pm);
+
+  return error;
+}
+
+/* Slow hash computation for general keys. */
+uword
+phash_hash_slow (phash_main_t * pm, uword key)
+{
+  u32 a, b, v;
+
+  if (pm->flags & PHASH_FLAG_MIX64)
+    {
+      u64 x0, y0, z0;
+
+      x0 = y0 = z0 = pm->hash_seed;
+
+      if (pm->key_seed1)
+	{
+	  u64 xyz[3];
+	  pm->key_seed1 (pm->private, key, &xyz);
+	  x0 += xyz[0];
+	  y0 += xyz[1];
+	  z0 += xyz[2];
+	}
+      else
+	x0 += key;
+
+      hash_mix64 (x0, y0, z0);
+
+      a = z0 >> pm->a_shift;
+      b = z0 & pm->b_mask;
+    }
+  else
+    {
+      u32 x0, y0, z0;
+
+      x0 = y0 = z0 = pm->hash_seed;
+
+      if (pm->key_seed1)
+	{
+	  u32 xyz[3];
+	  pm->key_seed1 (pm->private, key, &xyz);
+	  x0 += xyz[0];
+	  y0 += xyz[1];
+	  z0 += xyz[2];
+	}
+      else
+	x0 += key;
+
+      hash_mix32 (x0, y0, z0);
+
+      a = z0 >> pm->a_shift;
+      b = z0 & pm->b_mask;
+    }
+
+  v = pm->tab[b];
+  if (pm->flags & PHASH_FLAG_USE_SCRAMBLE)
+    v = pm->scramble[v];
+  return a ^ v;
+}
+
+/* Verify that perfect hash is perfect. */
+clib_error_t *
+phash_validate (phash_main_t * pm)
+{
+  phash_key_t *k;
+  uword *unique_bitmap = 0;
+  clib_error_t *error = 0;
+
+  vec_foreach (k, pm->keys)
+  {
+    uword h = phash_hash_slow (pm, k->key);
+
+    if (h >= pm->hash_max)
+      {
+	error = clib_error_return (0, "hash out of range %wd", h);
+	goto done;
+      }
+
+    if (clib_bitmap_get (unique_bitmap, h))
+      {
+	error = clib_error_return (0, "hash non-unique");
+	goto done;
+      }
+
+    unique_bitmap = clib_bitmap_ori (unique_bitmap, h);
+  }
+
+done:
+  clib_bitmap_free (unique_bitmap);
+  return error;
+}
+
+/*
+ * fd.io coding-style-patch-verification: ON
+ *
+ * Local Variables:
+ * eval: (c-set-style "gnu")
+ * End:
+ */