key_detail.h

Go to the documentation of this file.

 
#pragma once
 
#include <everett/backend.h>
 
#include <bit>
#include <cstddef>
#include <cstdint>
#include <cstring>
 
namespace everett::key_detail {
  // All loads remain within count bytes; neither alignment nor padding is assumed.
  template <simd::architecture Arch = simd::scalar>
  simd_inline std::size_t common_bytes(void const * lhs, void const * rhs, std::size_t count) noexcept {
    auto a = static_cast<unsigned char const *>(lhs);
    auto b = static_cast<unsigned char const *>(rhs);
    std::size_t at = 0;
    if constexpr (!std::is_same_v<Arch, simd::scalar>) {
      constexpr auto lanes = backend_detail::register_bytes<Arch>;
      using V = simd::vec<std::uint8_t, lanes, Arch>;
      for (; count - at >= lanes; at += lanes) {
        auto different = V::load(a + at) != V::load(b + at);
        if constexpr (std::is_same_v<Arch, simd::neon>) {
          // A cheap horizontal test retains the scalar mismatch locator.
          if (any(different)) break;
        } else if (auto bits = different.to_bitset()) return at + std::countr_zero(bits);
      }
    }
    for (; count - at >= 8; at += 8) {
      std::uint64_t x, y;
      std::memcpy(&x, a + at, 8); std::memcpy(&y, b + at, 8);
      if (auto different = x ^ y) {
        if constexpr (std::endian::native == std::endian::little) return at + (std::countr_zero(different) >> 3);
        else if constexpr (std::endian::native == std::endian::big) return at + (std::countl_zero(different) >> 3);
        else break;
      }
    }
    while (at != count && a[at] == b[at]) ++at;
    return at;
  }
 
  inline std::uint64_t reverse_bytes(std::uint64_t x) noexcept {
    x = ((x & 0x00ff00ff00ff00ffull) << 8) | ((x >> 8) & 0x00ff00ff00ff00ffull);
    x = ((x & 0x0000ffff0000ffffull) << 16) | ((x >> 16) & 0x0000ffff0000ffffull);
    return (x << 32) | (x >> 32);
  }
  inline std::uint64_t load_big(void const * source) noexcept {
    if constexpr (std::endian::native == std::endian::little || std::endian::native == std::endian::big) {
      std::uint64_t value; std::memcpy(&value, source, 8);
      if constexpr (std::endian::native == std::endian::little) return reverse_bytes(value);
      else return value;
    } else {
      auto bytes = static_cast<unsigned char const *>(source);
      std::uint64_t value = 0;
      for (unsigned i = 0; i != 8; ++i) value = (value << 8) | bytes[i];
      return value;
    }
  }
  inline void store_big(void * target, std::uint64_t value) noexcept {
    if constexpr (std::endian::native == std::endian::little) {
      value = reverse_bytes(value); std::memcpy(target, &value, 8);
    } else if constexpr (std::endian::native == std::endian::big) std::memcpy(target, &value, 8);
    else {
      auto bytes = static_cast<unsigned char *>(target);
      for (unsigned i = 0; i != 8; ++i) bytes[i] = static_cast<unsigned char>(value >> (56 - (i << 3)));
    }
  }
}