1 /*
2 * Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
3 * Copyright (C) 2014 - Scilab Enterprises - Calixte DENIZET
4 *
5 * Copyright (C) 2012 - 2016 - Scilab Enterprises
6 *
7 * This file is hereby licensed under the terms of the GNU GPL v2.0,
8 * pursuant to article 5.3.4 of the CeCILL v.2.1.
9 * This file was originally licensed under the terms of the CeCILL v2.1,
10 * and continues to be available under such terms.
11 * For more information, see the COPYING file which you should have received
12 * along with this program.
13 *
14 */
15
16 #ifndef __TOOLS_HXX__
17 #define __TOOLS_HXX__
18
19 #include <bitset>
20 #include <cmath>
21 #include <cstdint>
22 #include <iostream>
23 #include <limits>
24 #include <map>
25 #include <set>
26 #include <unordered_map>
27 #include <unordered_set>
28
29 #ifdef _MSC_VER
30 #include "stdint.h"
31 #include <intrin.h>
32 #endif
33
34 #include "core_math.h"
35 #include "symbol.hxx"
36
37 namespace analysis
38 {
39
40 namespace tools
41 {
42
43 #ifdef _MSC_VER
trunc(const double x)44 inline static double trunc(const double x)
45 {
46 return x > 0 ? floor(x) : ceil(x);
47 }
48
clz(const uint32_t x)49 inline static uint32_t clz(const uint32_t x)
50 {
51 unsigned long r = 0;
52 _BitScanForward(&r, x);
53 return r;
54 }
55
clzll(const uint64_t x)56 inline static uint32_t clzll(const uint64_t x)
57 {
58 #ifdef _WIN64
59 unsigned long r = 0;
60 _BitScanForward64(&r, x);
61 return r;
62 #else
63 const uint32_t u32 = x >> 32;
64 if (u32)
65 {
66 return clz(u32);
67 }
68 return 32 + clz(x & 0xFFFFFFFFUL);
69 #endif
70 }
71 #else
72 inline static double trunc(const double x)
73 {
74 #ifdef __APPLE__
75 // Needed for compilation with GCC 4.8.2
76 return x > 0 ? floor(x) : ceil(x);
77 #else
78 return std::trunc(x);
79 #endif
80 }
81
82 inline static uint32_t clz(const uint32_t x)
83 {
84 return x ? __builtin_clz(x) : 32;
85 }
86
87 inline static uint32_t clzll(const uint64_t x)
88 {
89 return x ? __builtin_clzll(x) : 64;
90 }
91 #endif
92
NaN()93 inline static double NaN()
94 {
95 return std::numeric_limits<double>::quiet_NaN();
96 }
97
isNaN(const double x)98 inline static bool isNaN(const double x)
99 {
100 return ISNAN(x) != 0;
101 }
102
isFinite(const double x)103 inline static bool isFinite(const double x)
104 {
105 return finite(x) != 0;
106 }
107
isInfinite(const double x)108 inline static bool isInfinite(const double x)
109 {
110 return !isFinite(x);
111 }
112
113 enum IntType { NOTANINT, SIGNED, UNSIGNED };
114
getIntType(const double x)115 inline static IntType getIntType(const double x)
116 {
117 if (x == trunc(x))
118 {
119 if (x >= 0)
120 {
121 if (x <= (double)std::numeric_limits<uint64_t>::max())
122 {
123 return UNSIGNED;
124 }
125 }
126 else if (x >= (double)std::numeric_limits<int64_t>::min())
127 {
128 return SIGNED;
129 }
130 }
131
132 return NOTANINT;
133 }
134
135 template<typename T>
asInteger(const double x,T & ival)136 inline static bool asInteger(const double x, T & ival)
137 {
138 if (x == trunc(x))
139 {
140 if (x >= 0)
141 {
142 if (x <= (double)std::numeric_limits<T>::max())
143 {
144 ival = (T)x;
145 return true;
146 }
147 }
148 else if (x >= (double)std::numeric_limits<T>::min())
149 {
150 ival = (T)x;
151 return true;
152 }
153 }
154
155 return false;
156 }
157
isAnInt(const double x)158 inline static bool isAnInt(const double x)
159 {
160 return getIntType(x) != NOTANINT;
161 }
162
163 template<typename T>
cast(const double x)164 inline static T cast(const double x)
165 {
166 if (x < static_cast<double>(std::numeric_limits<T>::max()))
167 {
168 if (x > static_cast<double>(std::numeric_limits<T>::min()))
169 {
170 return static_cast<T>(x);
171 }
172 else
173 {
174 return std::numeric_limits<T>::min();
175 }
176 }
177 else
178 {
179 return std::numeric_limits<T>::max();
180 }
181 }
182
183 template<typename T>
powui(T x,uint64_t n)184 inline static T powui(T x, uint64_t n)
185 {
186 T p = x;
187 T y = (n & 1) ? x : 1;
188
189 while (n >>= 1)
190 {
191 p *= p;
192 if (n & 1)
193 {
194 y *= p;
195 }
196 }
197
198 return y;
199 }
200
operator <<(std::wostream & out,const IntType & it)201 inline std::wostream & operator<<(std::wostream & out, const IntType & it)
202 {
203 switch (it)
204 {
205 case IntType::NOTANINT :
206 out << L"NAI";
207 break;
208 case IntType::SIGNED :
209 out << L'S';
210 break;
211 case IntType::UNSIGNED :
212 out << L'U';
213 break;
214 }
215 return out;
216 }
217
218 template<typename T>
popcount(const T x)219 inline static unsigned char popcount(const T x)
220 {
221 return std::bitset<sizeof(T)>(x).count();
222 }
223
log2(const unsigned int x)224 inline static unsigned char log2(const unsigned int x)
225 {
226 return (unsigned char)((sizeof(unsigned int) << 3) - clz(x) - 1);
227 }
228
log2(const unsigned long long x)229 inline static unsigned char log2(const unsigned long long x)
230 {
231 return (unsigned char)((sizeof(unsigned long long) << 3) - clzll(x) - 1);
232 }
233
234 template<typename T>
printSet(const T & set,std::wostream & out)235 static void printSet(const T & set, std::wostream & out)
236 {
237 if (set.empty())
238 {
239 out << L"{}";
240 }
241 else
242 {
243 out << L'{';
244 for (typename T::const_iterator i = set.begin(); i != set.end(); ++i)
245 {
246 if (std::next(i) == set.end())
247 {
248 out << *i << L'}';
249 }
250 else
251 {
252 out << *i << L',';
253 }
254 }
255 }
256 }
257
258 template<typename T>
printMap(const T & map,std::wostream & out,const bool newLine=false)259 static void printMap(const T & map, std::wostream & out, const bool newLine = false )
260 {
261 if (map.empty())
262 {
263 out << L"{}";
264 }
265 else
266 {
267 out << L'{';
268 for (typename T::const_iterator i = map.begin(); i != map.end(); ++i)
269 {
270 out << i->first << L" -> " << i->second;
271 if (std::next(i) == map.end())
272 {
273 out << L'}';
274 }
275 else
276 {
277 out << L',';
278 if (newLine)
279 {
280 out << L'\n';
281 }
282 }
283 }
284 }
285 }
286
287 template<typename T>
printMapInfo(std::wostream & out,const T & map,const bool show_collisions=false)288 static void printMapInfo(std::wostream & out, const T & map, const bool show_collisions = false)
289 {
290 double mean = 0;
291 double variance = 0;
292 const unsigned int count = map.bucket_count();
293 unsigned int empty_bucket_count = 0;
294 unsigned int collision_count = 0;
295
296 out << L"Map size: " << map.size() << std::endl;
297 out << L"Number of buckets: " << count << std::endl;
298
299 for (unsigned int i = 0; i < count; ++i)
300 {
301 if (const unsigned int s = map.bucket_size(i))
302 {
303 mean += (double)s;
304 if (s > 1)
305 {
306 ++collision_count;
307 }
308 }
309 else
310 {
311 ++empty_bucket_count;
312 }
313 }
314 mean /= (double)count;
315
316 for (unsigned int i = 0; i < count; ++i)
317 {
318 const double ms = mean - (double)map.bucket_size(i);
319 variance += ms * ms;
320 }
321 variance /= (double)count;
322
323 out << L"Number of elements by buckets: mean=" << mean << L", sigma=" << std::sqrt(variance) << std::endl;
324 out << L"Number of empty buckets: " << empty_bucket_count << std::endl;
325 out << L"Number of collisions: " << collision_count << std::endl;
326
327 if (show_collisions)
328 {
329 std::multimap<unsigned int, typename T::key_type> collisions;
330 for (const auto & p : map)
331 {
332 collisions.emplace(map.bucket(p.first), p.first);
333 }
334
335 for (const auto & p : collisions)
336 {
337 out << L"Bucket " << p.first << L": " << p.second << L", hash=" << (typename T::hasher()(p.second)) << std::endl;
338 }
339 }
340 }
341
hash_combine(const std::size_t seed)342 inline static std::size_t hash_combine(const std::size_t seed)
343 {
344 return seed;
345 }
346
347 template<typename... Args>
hash_combine(const std::size_t seed,Args...args)348 inline static std::size_t hash_combine(const std::size_t seed, Args... args)
349 {
350 // it is the way Boost has implemented hash_combine:
351 // http://www.boost.org/doc/libs/1_35_0/doc/html/boost/hash_combine_id241013.html
352 return seed ^ (hash_combine(args...) + 0x9e3779b9 + (seed << 6) + (seed >> 2));
353 }
354
355 struct HashSymbol
356 {
operator ()analysis::tools::HashSymbol357 inline std::size_t operator()(const symbol::Symbol & sym) const
358 {
359 return std::hash<std::wstring>()(sym.getName());
360 }
361 };
362
363 struct EqSymbol
364 {
operator ()analysis::tools::EqSymbol365 inline bool operator()(const symbol::Symbol & L, const symbol::Symbol & R) const
366 {
367 return L == R;
368 }
369 };
370
371 typedef std::set<symbol::Symbol> SymbolOrdSet;
372 typedef std::unordered_set<symbol::Symbol, HashSymbol> SymbolSet;
373 template<typename T>
374 using SymbolMap = std::unordered_map<symbol::Symbol, T, HashSymbol, EqSymbol>;
375
376 } // namespace tools
377
378 } // namespace analysis
379
380 #endif // __TOOLS_HXX__
381