#ifndef SMALL_COMPARE_HH

#define SMALL_COMPARE_HH

// small_compare utility function

//

// This can be used to replace

//   string_view s1 = ...

//   if (s1 == "foo") { ... }

// with

//   if (small_compare<"foo">(s1)) { ... }

// This looks more ugly, but it can execute faster.

//

// The first variant internally calls memcmp() to do the actual string

// comparison (after the string length has been checked).

// Update: gcc-12 optimizes memcmp() on small string-literals better:

//         e.g. it performs a 7-char comparison by using 2 4-byte loads

//              where the middle byte overlaps (older versions did a 4-byte,

//              2-byte and 1-byte load)

//         In the future, when gcc-12 is more common, we could remove this

//         small_compare utility.

//

// The second variant does a 4 byte unaligned load, masks the unnecessary 4th

// byte (so and with 0x00ffffff) and then compares with 0x006f6f66 ('f'->0x66,

// 'o'->0x6f) (on big endian system the mask and comparison constants are

// different). So only 3 instructions instead of a call to memcmp().

//

// In the general case small_compare does a 1, 2, 4 or 8 byte unaligned load

// (only strings upto 8 characters are supported). Possibly followed by a 'and'

// instruction (only needed for lengths 3, 5, 6 or 7), followed by a compare

// with a constant. This is much faster than memcmp().

//

// There are also some disadvantages.

// - (minor) We need unaligned load instructions. Many CPU architectures

//   support these, but even in case these must be emulated it's still fast.

// - (major) We read upto 8 bytes, and that might be past the end of the

//   input string. So it's only safe to use small_compare() if there's enough

//   padding at the end of the buffer.

#include "aligned.hh"

#include "endian.hh"

#include <algorithm>

#include <array>

#include <bit>

#include <cassert>

#include <cstdint>

#include <cstring>

#include <string_view>

#include <type_traits>

// A wrapper around a (zero-terminated) string literal.

// Could be moved to a separate header (when also needed in other contexts).

template<size_t N> struct StringLiteral {

	constexpr StringLiteral(const char (&str)[N])

	{

		assert(str[N - 1] == '\0');

		std::copy_n(str, N - 1, value.data());

	}

	[[nodiscard]] constexpr size_t size() const { return value.size(); }

	[[nodiscard]] constexpr const char* data() const { return value.data(); }

	std::array<char, N - 1> value;

};

namespace detail {

// Loader can load an 8/16/32/64 unaligned value.

struct Load8 {

	using type = uint8_t;

	[[nodiscard]] type operator()(const void* p) const { return *std::bit_cast<const uint8_t*>(p); }

};

struct Load16 {

	using type = uint16_t;

	[[nodiscard]] type operator()(const void* p) const { return unalignedLoad16(p); }

};

struct Load32 {

	using type = uint32_t;

	[[nodiscard]] type operator()(const void* p) const { return unalignedLoad32(p); }

};

struct Load64 {

	using type = uint64_t;

	[[nodiscard]] type operator()(const void* p) const { return unalignedLoad64(p); }

};

struct ErrorNotSupportedLoader; // load only implemented up to 64 bit

template<size_t N> struct SelectLoader

	: std::conditional_t<N <= 1, Load8,

	  std::conditional_t<N <= 2, Load16,

	  std::conditional_t<N <= 4, Load32,

	  std::conditional_t<N <= 8, Load64,

	  ErrorNotSupportedLoader>>>> {};

template<typename T> constexpr std::pair<T, T> calcValueMask(auto str)

{

	T v = 0;

	T m = 0;

	int s = Endian::LITTLE ? 0 : (8 * (sizeof(T) - 1));

	for (size_t i = 0; i < str.size(); ++i) {

		v = T(v + (T(str.data()[i]) << s));

		m = T(m + (T(255) << s));

		s += Endian::LITTLE ? 8 : -8;

	}

	return {v, m};

}

} // namespace detail

template<StringLiteral Literal>

[[nodiscard]] bool small_compare(const char* p)

{

	using Loader = detail::SelectLoader<Literal.size()>;

	using Type = typename Loader::type;

	static constexpr auto vm = detail::calcValueMask<Type>(Literal);

	auto [value, mask] = vm;

	Loader loader;

	return (loader(p) & mask) == value;

}

template<StringLiteral Literal>

[[nodiscard]] bool small_compare(std::string_view str)

{

	if (str.size() != Literal.size()) return false;

	return small_compare<Literal>(str.data());

}

#endif