search.go raw

   1  //go:build !amd64
   2  // +build !amd64
   3  
   4  /*
   5   * SPDX-FileCopyrightText: © Hypermode Inc. <hello@hypermode.com>
   6   * SPDX-License-Identifier: Apache-2.0
   7   */
   8  
   9  package simd
  10  
  11  // Search uses the Clever search to find the correct key.
  12  func Search(xs []uint64, k uint64) int16 {
  13  	if len(xs) < 8 || (len(xs)%8 != 0) {
  14  		return Naive(xs, k)
  15  	}
  16  	var twos, pk [4]uint64
  17  	pk[0] = k
  18  	pk[1] = k
  19  	pk[2] = k
  20  	pk[3] = k
  21  	for i := 0; i < len(xs); i += 8 {
  22  		twos[0] = xs[i]
  23  		twos[1] = xs[i+2]
  24  		twos[2] = xs[i+4]
  25  		twos[3] = xs[i+6]
  26  		if twos[0] >= pk[0] {
  27  			return int16(i / 2)
  28  		}
  29  		if twos[1] >= pk[1] {
  30  			return int16((i + 2) / 2)
  31  		}
  32  		if twos[2] >= pk[2] {
  33  			return int16((i + 4) / 2)
  34  		}
  35  		if twos[3] >= pk[3] {
  36  			return int16((i + 6) / 2)
  37  		}
  38  
  39  	}
  40  	return int16(len(xs) / 2)
  41  }
  42