openMSX
small_compare.hh
Go to the documentation of this file.
1 #ifndef SMALL_COMPARE_HH
2 #define SMALL_COMPARE_HH
3 
4 // small_compare utility function
5 //
6 // This can be used to replace
7 // string_view s1 = ...
8 // if (s1 == "foo") { ... }
9 // with
10 // if (small_compare<'f','o','o'>(s1)) { ... }
11 // This looks more ugly, but it can execute (much) faster.
12 //
13 // The first variant internally calls memcmp() to do the actual string
14 // comparison (after the string length has been checked).
15 //
16 // The second variant does a 4 byte unaligned load, masks the unnecessary 4th
17 // byte (so and with 0x00ffffff) and then compares with 0x006f6f66 ('f'->0x66,
18 // 'o'->0x6f) (on big endian system the mask and comparison constants are
19 // different). So only 3 instructions instead of a call to memcmp().
20 //
21 // In the general case small_compare does a 1, 2, 4 or 8 byte unaligned load
22 // (only strings upto 8 characters are supported). Possibly followed by a 'and'
23 // instruction (only needed for lengths 3, 5, 6 or 7), followed by a compare
24 // with a constant. This is much faster than memcmp().
25 //
26 // There are also some disadvantages.
27 // - (minor) We need unaligned load instructions. Many CPU architectures
28 // support these, but even in case these must be emulated it's still fast.
29 // - (major) We read upto 8 bytes, and that might be past the end of the
30 // input string. So it's only safe to use small_compare() if there's enough
31 // padding at the end of the buffer.
32 
33 #include "aligned.hh"
34 #include "build-info.hh"
35 #include <cstdint>
36 #include <cstring>
37 #include <string_view>
38 #include <type_traits>
39 
40 // Loader can load an 8/16/32/64 unaligned value.
41 struct Load8 {
42  using type = uint8_t;
43  [[nodiscard]] type operator()(const void* p) { return *reinterpret_cast<const uint8_t*>(p); }
44 };
45 struct Load16 {
46  using type = uint16_t;
47  [[nodiscard]] type operator()(const void* p) { return unalignedLoad16(p); }
48 };
49 struct Load32 {
50  using type = uint32_t;
51  [[nodiscard]] type operator()(const void* p) { return unalignedLoad32(p); }
52 };
53 struct Load64 {
54  using type = uint64_t;
55  [[nodiscard]] type operator()(const void* p) { return unalignedLoad64(p); }
56 };
57 struct ErrorNotSupportedLoader; // load only implemented up to 64 bit
58 template<size_t N> struct SelectLoader
59  : std::conditional_t<N <= 1, Load8,
60  std::conditional_t<N <= 2, Load16,
61  std::conditional_t<N <= 4, Load32,
62  std::conditional_t<N <= 8, Load64,
63  ErrorNotSupportedLoader>>>> {};
64 
65 
66 // ScVal-little-endian
67 template<typename T, T v, T m, T s, char ...Ns> struct ScValLeImpl;
68 template<typename T, T v, T m, T s> struct ScValLeImpl<T, v, m, s> {
69  static constexpr T value = v;
70  static constexpr T mask = m;
71 };
72 template<typename T, T v, T m, T s, char N0, char ...Ns> struct ScValLeImpl<T, v, m, s, N0, Ns...>
73  : ScValLeImpl<T, v + (T(N0 & 255) << s), m + (T(255) << s), T(s + 8), Ns...> {};
74 template<typename T, char ...Ns> struct ScValLe : ScValLeImpl<T, 0, 0, 0, Ns...> {};
75 
76 // ScVal-big-endian
77 template<typename T, T v, T m, T s, char ...Ns> struct ScValBeImpl;
78 template<typename T, T v, T m, T s> struct ScValBeImpl<T, v, m, s> {
79  static constexpr T value = v;
80  static constexpr T mask = m;
81 };
82 template<typename T, T v, T m, T s, char N0, char ...Ns> struct ScValBeImpl<T, v, m, s, N0, Ns...>
83  : ScValBeImpl<T, v + (T(N0 & 255) << s), m + (T(255) << s), T(s - 8), Ns...> {};
84 template<typename T, char ...Ns> struct ScValBe : ScValBeImpl<T, 0, 0, 8 * (sizeof(T) - 1), Ns...> {};
85 
86 // ScVal: combines all given characters in one value of type T, also computes a
87 // mask-value with 1-bits in the 'used' positions.
88 template<typename T, char ...Ns> struct ScVal
89  : std::conditional_t<openmsx::OPENMSX_BIGENDIAN, ScValBe<T, Ns...>,
90  ScValLe<T, Ns...>> {};
91 
92 
93 template<char ...Ns> struct SmallCompare {
94  using Loader = SelectLoader<sizeof...(Ns)>;
95  using C = ScVal<typename Loader::type, Ns...>;
96  static constexpr auto value = C::value;
97  static constexpr auto mask = C::mask;
98 };
99 
100 // The actual small-fixed-string-comparison.
101 template<char ...Ns> [[nodiscard]] bool small_compare(const char* p)
102 {
103  using SC = SmallCompare<Ns...>;
104  typename SC::Loader loader;
105  return (loader(p) & SC::mask) == SC::value;
106 }
107 
108 template<char ...Ns> [[nodiscard]] bool small_compare(std::string_view str)
109 {
110  if (str.size() != sizeof...(Ns)) return false;
111  return small_compare<Ns...>(str.data());
112 }
113 
114 #endif
aligned.hh
Load32
Definition: small_compare.hh:49
Load16
Definition: small_compare.hh:45
Load64::type
uint64_t type
Definition: small_compare.hh:54
Load8::type
uint8_t type
Definition: small_compare.hh:42
Load16::operator()
type operator()(const void *p)
Definition: small_compare.hh:47
unalignedLoad16
ALWAYS_INLINE uint16_t unalignedLoad16(const void *p)
Definition: aligned.hh:39
unalignedLoad32
ALWAYS_INLINE uint32_t unalignedLoad32(const void *p)
Definition: aligned.hh:42
Load16::type
uint16_t type
Definition: small_compare.hh:46
build-info.hh
Load8::operator()
type operator()(const void *p)
Definition: small_compare.hh:43
Load64::operator()
type operator()(const void *p)
Definition: small_compare.hh:55
Load8
Definition: small_compare.hh:41
unalignedLoad64
ALWAYS_INLINE uint64_t unalignedLoad64(const void *p)
Definition: aligned.hh:45
Load64
Definition: small_compare.hh:53
Load32::operator()
type operator()(const void *p)
Definition: small_compare.hh:51
Load32::type
uint32_t type
Definition: small_compare.hh:50