1 #ifndef libjmmcg_core_memops_hpp
2 #define libjmmcg_core_memops_hpp
3
4 /******************************************************************************
5 ** $Header: svn+ssh://jmmcg@svn.code.sf.net/p/libjmmcg/code/trunk/libjmmcg/core/memops.hpp 2218 2017-11-07 21:57:21Z jmmcg $
6 **
7 ** Copyright (c) 2013 by J.M.McGuiness, coder@hussar.me.uk
8 **
9 ** This library is free software; you can redistribute it and/or
10 ** modify it under the terms of the GNU Lesser General Public
11 ** License as published by the Free Software Foundation; either
12 ** version 2.1 of the License, or (at your option) any later version.
13 **
14 ** This library is distributed in the hope that it will be useful,
15 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
16 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 ** Lesser General Public License for more details.
18 **
19 ** You should have received a copy of the GNU Lesser General Public
20 ** License along with this library; if not, write to the Free Software
21 ** Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
22 */
23
24 #include "blatant_old_msvc_compiler_hacks.hpp"
25 #include "max_min.hpp"
26
27 #include <boost/mpl/assert.hpp>
28
29 #include <algorithm>
30 #include <cassert>
31 #include <cstdint>
32 #include <cstring>
33 #include <iostream>
34 #include <memory>
35
36 #include <immintrin.h>
37
38 #ifndef __SSE__
39 # error "At a miniumum SSE is required for the code to compile, please enable it with -march=native or -msse, or other suitable options and run the resultant binary on a suitable architecture."
40 #endif
41
42 /**
43 \file memops.hpp The objective of these template specialisations is to allow the compiler to correctly select the appropriate, high-speed operation.
44 */
45
46 namespace jmmcg {
47
48 /// Equivalent to the memcpy operations.
49 /**
50 \param dest A random-access iterator into a contiguous array of memory, note that the locations will not be pre-initialised, i.e. placement-new will only be used.
51 \param src A random-access iterator into a contiguous array of memory.
52 \param n The number of elements to copy. Must comprise a valid range.
53
54 \see std::memcpy(), std::wmemcpy()
55 */
56 template<class Iter1, class Iter2> inline void FORCE_INLINE
57 memcpy(Iter1 dest, Iter2 src, std::size_t n) noexcept(true);
58 template<> inline void FORCE_INLINE
59 memcpy<char *, char const *>(char *dest, char const *src, std::size_t n) noexcept(true);
60 template<> inline void FORCE_INLINE
61 memcpy<wchar_t *, wchar_t const *>(wchar_t *dest, wchar_t const *src, std::size_t n) noexcept(true);
62
63 /// Equivalent to the memmove operations.
64 /**
65 \param dest A random-access iterator into a contiguous array of memory, note that the locations will not be pre-initialised, i.e. placement-new will only be used.
66 \param src A random-access iterator into a contiguous array of memory.
67 \param n The number of elements to move. Must comprise a valid range.
68
69 \see std::memmove(), std::wmemmove()
70 */
71 template<class Iter1, class Iter2> inline void FORCE_INLINE
72 memmove(Iter1 dest, Iter2 src, std::size_t n) noexcept(true);
73 template<> inline void FORCE_INLINE
74 memmove<char *, char const *>(char *dest, char const *src, std::size_t n) noexcept(true);
75 template<> inline void FORCE_INLINE
76 memmove<wchar_t *, wchar_t const *>(wchar_t *dest, wchar_t const *src, std::size_t n) noexcept(true);
77
78 /// Equivalent to the memset operations.
79 /**
80 \param dest A random-access iterator into a contiguous array of memory.
81 \param i The value with which to initialise the elements in the range.
82 \param n The number of elements to set. Must comprise a valid range.
83
84 \see std::memset(), std::wmemset()
85 */
86 template<class Iter, class V> inline void FORCE_INLINE
87 memset(Iter dest, V i, std::size_t n) noexcept(true);
88 template<> inline void FORCE_INLINE
89 memset<char *, char>(char *dest, char i, std::size_t n) noexcept(true);
90 template<> inline void FORCE_INLINE
91 memset<wchar_t *, wchar_t>(wchar_t *dest, wchar_t i, std::size_t n) noexcept(true);
92
93 /// Equivalent to the std::memcmp() operations.
94 /**
95 \param src1 A random-access iterator into a contiguous array of memory.
96 \param src2 A random-access iterator into a contiguous array of memory.
97 \param n The number of elements to compare. Must comprise a valid range.
98 \return true iff the two sequences accessed via the iterators compare equal, element-by-element wise.
99
100 \see std::memcmp(), std::wmemcmp()
101 */
102 template<class Iter> inline bool FORCE_INLINE
103 memcmp(Iter src1, Iter src2, std::size_t n) noexcept(true);
104 template<> inline bool FORCE_INLINE
105 memcmp<char const *>(char const *src1, char const *src2, std::size_t n) noexcept(true);
106 template<> inline bool FORCE_INLINE
107 memcmp<wchar_t const *>(wchar_t const *src1, wchar_t const *src2, std::size_t n) noexcept(true);
108
109 template<class Val, std::size_t SrcSz, std::size_t DestSz> void FORCE_INLINE
110 memcpy(Val const (& src)[SrcSz], Val (& dest)[DestSz]) noexcept(false);
111
112 /// Copy the source array to the destination (which may overlap), statically unrolled.
113 /**
114 This method uses 256-bit, 128-bit, 64-bit, 32-bit, 16-bit then byte copies, unrolled to attempt to reduce the number of copy operations performed.
115
116 Algorithmic complexity: O(min(SrcSz, DestSz)/256)
117
118 \param src The source C-style char-array.
119 \param dest The destination C-style char-array.
120
121 \see std::memcpy()
122 */
123 template<
124 std::size_t SrcSz, ///< The size of the source array in bytes.
125 std::size_t DestSz ///< The size of the destination array in bytes.
126 >
127 inline constexpr void FORCE_INLINE
128 memcpy_opt(char const (&src)[SrcSz], char (&dest)[DestSz]) noexcept(true);
129
130 /// Compare the source array to the destination (which may overlap), statically unrolled.
131 /**
132 This method uses 256-bit, 128-bit, 64-bit, 32-bit, 16-bit then byte copies, unrolled to attempt to reduce the number of copy operations performed.
133
134 Algorithmic complexity: O(min(SrcSz, DestSz)/256)
135
136 \param src The first C-style char-array.
137 \param second The second C-style char-array.
138 \return True if they are identical arrays, otherwise false.
139
140 \see std::memcmp()
141 */
142 template<
143 std::size_t FirstSz, ///< The size of the first array in bytes.
144 std::size_t SecondSz ///< The size of the second array in bytes.
145 >
146 inline constexpr bool FORCE_INLINE
147 memcmp_opt(char const (&first)[FirstSz], char const (&second)[SecondSz]) noexcept(true);
148
149 /// Find the first occurrence of the character in the string.
150 /**
151 This is based upon algorithms from: <a href="https://www.strchr.com/strcmp_and_strlen_using_sse_4.2"/>.
152
153 Algorithmic complexity: O(min(FirstSz)/256)
154
155 \param haystack The C-style char-array.
156 \param needle The character to find.
157 \return Zero if the character was not found in the first, otherwise the first occurrence of the character in the string.
158
159 \see std::strchr()
160 */
161 template<
162 char const needle,
163 std::size_t FirstSz ///< The size of the first array in bytes.
164 >
165 inline constexpr char const * FORCE_INLINE
166 strchr_opt(char const (&haystack)[FirstSz]) noexcept(true) __attribute__((pure));
167
168 /// Find if the second string is a sub-string of the first.
169 /**
170 This is based upon algorithms from: <a href="https://github.com/WojciechMula/sse4-strstr/blob/master/avx2-strstr-v2.cpp"/> & <a href="http://0x80.pl/articles/simd-strfind.html#generic-sse-avx2"/>.
171
172 Algorithmic complexity: O(min(FirstSz, SecondSz)/256)
173
174 \param haystack The first C-style char-array, that must be in whole 32-byte units.
175 \param needle The second C-style char-array, up to a maximum size of 32 bytes.
176 \return Zero if the second string was not found in the first, otherwise the offset of the beginning of that string in the first.
177
178 \see std::strstr()
179 */
180 template<
181 std::size_t FirstSz, ///< The size of the first array in bytes.
182 std::size_t SecondSz, ///< The size of the second array in bytes.
183 class LessThan32BytesLong=typename std::enable_if<SecondSz<=32>::type
184 >
185 inline constexpr char const * FORCE_INLINE
186 strstr_opt(char const (&haystack)[FirstSz], char const (&needle)[SecondSz]) noexcept(true) __attribute__((pure));
187
188 template<
189 std::size_t SrcSz, ///< The size of the source array in bytes.
190 std::size_t DestSz ///< The size of the destination array in bytes.
191 >
192 inline constexpr void FORCE_INLINE
193 memcpy_opt(std::array<char, SrcSz> const &src, std::array<char, DestSz> &dest) noexcept(true);
194 template<
195 std::size_t SrcSz, ///< The size of the source array in bytes.
196 std::size_t DestSz ///< The size of the destination array in bytes.
197 >
198 inline constexpr void FORCE_INLINE
199 memcpy_opt(std::array<uint8_t, SrcSz> const &src, std::array<uint8_t, DestSz> &dest) noexcept(true);
200
201 template<
202 std::size_t Sz ///< The size of the arrays in bytes.
203 >
204 inline bool FORCE_INLINE
205 memcmp(std::array<char, Sz> const &src1, std::array<char, Sz> const &src2) noexcept(true);
206 template<
207 std::size_t Sz ///< The size of the arrays in bytes.
208 >
209 inline bool FORCE_INLINE
210 memcmp(std::array<uint8_t, Sz> const &src1, std::array<uint8_t, Sz> const &src2) noexcept(true);
211
212 template<
213 std::size_t Sz ///< The size of the arrays in bytes.
214 >
215 inline bool FORCE_INLINE
216 operator==(std::array<char, Sz> const &src1, std::array<char, Sz> const &src2) noexcept(true);
217 template<
218 std::size_t Sz ///< The size of the arrays in bytes.
219 >
220 inline bool FORCE_INLINE
221 operator==(std::array<uint8_t, Sz> const &src1, std::array<uint8_t, Sz> const &src2) noexcept(true);
222
223 /// Copy the source array to the destination (which may overlap) byte-by-byte, statically unrolled.
224 /**
225 Algorithmic complexity: O(min(SrcSz, DestSz))
226
227 \param src The source C-style array.
228 \param dest The destination C-style array.
229
230 \see std::memcpy()
231 */
232 template<
233 std::size_t SrcSz, ///< The size of the source array in bytes.
234 std::size_t DestSz ///< The size of the destination array in bytes.
235 >
236 inline constexpr void FORCE_INLINE
237 memcpy_slow(char const (& src)[SrcSz], char (& dest)[DestSz]) noexcept(true);
238
239 template<class T, class V=std::pair<typename T::value_type const *, typename T::value_type const *>> inline T FORCE_INLINE
240 copy(V const &src) noexcept(true);
241
242 template<
243 std::size_t SrcSz,
244 std::size_t DestSz
245 > inline constexpr std::array<char, DestSz> FORCE_INLINE
246 copy(std::array<char, SrcSz> const &src) noexcept(true);
247
248 template<
249 std::size_t SrcSz,
250 std::size_t DestSz
251 > inline constexpr std::array<uint8_t, DestSz> FORCE_INLINE
252 copy(std::array<uint8_t, SrcSz> const &src) noexcept(true);
253
254 }
255
256 namespace std {
257
258 template<
259 std::size_t Sz ///< The size of the arrays in bytes.
260 >
261 inline std::ostream &
262 operator<<(std::ostream &os, std::array<char, Sz> const &src);
263
264 }
265
266 #include "memops_impl.hpp"
267
268 #endif