1 // Copyright 2014 Wouter van Oortmerssen. All rights reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15
t_memcpy(T * dest,const T * src,S n)16 template<typename T, typename S> void t_memcpy(T *dest, const T *src, S n) {
17 memcpy(dest, src, n * sizeof(T));
18 }
19
t_memmove(T * dest,const T * src,S n)20 template<typename T, typename S> void t_memmove(T *dest, const T *src, S n) {
21 memmove(dest, src, n * sizeof(T));
22 }
23
ts_memcpy(T * dest,const T * src,S n)24 template<typename T, typename S> void ts_memcpy(T *dest, const T *src, S n) {
25 if (n) {
26 *dest++ = *src++;
27 if (n > 1) {
28 *dest++ = *src++;
29 if (n > 2) {
30 *dest++ = *src++;
31 if (n > 3) {
32 *dest++ = *src++;
33 for (S i = 4; i < n; i++) *dest++ = *src++;
34 }
35 }
36 }
37 }
38 }
39
tsnz_memcpy(T * dest,const T * src,S n)40 template<typename T, typename S> void tsnz_memcpy(T *dest, const T *src, S n) {
41 assert(n);
42 *dest++ = *src++;
43 if (n > 1) {
44 *dest++ = *src++;
45 if (n > 2) {
46 *dest++ = *src++;
47 if (n > 3) {
48 *dest++ = *src++;
49 for (S i = 4; i < n; i++) *dest++ = *src++;
50 }
51 }
52 }
53 }
54
55 // Doubly linked list.
56 // DLNodeRaw does not initialize nor assumes initialization, so can be used in
57 // situations where memory is already allocated DLNodeBase is meant to be a base
58 // class for objects that want to be held in a DLList. Unlike DLNodeRaw it is always
59 // initialized and checks that it's being used sensibly.
60 // These are better than std::list which doesn't have a node to inherit from,
61 // so causes 2 allocations rather than 1 for object hierarchies.
62
63 struct DLNodeRaw {
64 DLNodeRaw *prev, *next;
65
RemoveDLNodeRaw66 void Remove() {
67 prev->next = next;
68 next->prev = prev;
69 }
70
InsertAfterThisDLNodeRaw71 void InsertAfterThis(DLNodeRaw *o) {
72 o->next = next;
73 o->prev = this;
74 next->prev = o;
75 next = o;
76 }
77
InsertBeforeThisDLNodeRaw78 void InsertBeforeThis(DLNodeRaw *o) {
79 o->prev = prev;
80 o->next = this;
81 prev->next = o;
82 prev = o;
83 }
84 };
85
86 struct DLNodeBase : DLNodeRaw {
DLNodeBaseDLNodeBase87 DLNodeBase() { prev = next = nullptr; }
88
ConnectedDLNodeBase89 bool Connected() { return next && prev; }
90
~DLNodeBaseDLNodeBase91 virtual ~DLNodeBase() {
92 if (Connected()) Remove();
93 }
94
RemoveDLNodeBase95 void Remove() {
96 assert(Connected());
97 DLNodeRaw::Remove();
98 next = prev = nullptr;
99 }
100
InsertAfterThisDLNodeBase101 void InsertAfterThis(DLNodeBase *o) {
102 assert(Connected() && !o->Connected());
103 DLNodeRaw::InsertAfterThis(o);
104 }
105
InsertBeforeThisDLNodeBase106 void InsertBeforeThis(DLNodeBase *o) {
107 assert(Connected() && !o->Connected());
108 DLNodeRaw::InsertBeforeThis(o);
109 }
110 };
111
112 template<typename T> struct DLList : DLNodeRaw {
113 typedef T nodetype;
114
DLListDLList115 DLList() { next = prev = this; }
116
EmptyDLList117 bool Empty() { return next==this; }
118
GetDLList119 T *Get() {
120 assert(!Empty());
121 DLNodeRaw *r = next;
122 r->Remove();
123 return (T *)r;
124 }
125
NextDLList126 T *Next() { return (T *)next; }
PrevDLList127 T *Prev() { return (T *)prev; }
128 };
129
Next(T * n)130 template<typename T> T *Next(T *n) { return (T *)n->next; }
Prev(T * n)131 template<typename T> T *Prev(T *n) { return (T *)n->prev; }
132
133 // Safe Remove on not self.
134 #define loopdllistother(L, n) \
135 for (auto n = (L).Next(); n != (void *)&(L); n = Next(n))
136 // Safe Remove on self.
137 #define loopdllist(L, n) \
138 for (auto n = (L).Next(), p = Next(n); n != (void *)&(L); (n = p),(p = Next(n)))
139 // Safe Remove on self reverse.
140 #define loopdllistreverse(L, n) \
141 for (auto n = (L).Prev(), p = Prev(n); n != (void *)&(L); (n = p),(p = Prev(n)))
142
143 class MersenneTwister {
144 const static uint N = 624;
145 const static uint M = 397;
146 const static uint K = 0x9908B0DFU;
147
hiBit(uint u)148 uint hiBit(uint u) { return u & 0x80000000U; }
loBit(uint u)149 uint loBit(uint u) { return u & 0x00000001U; }
loBits(uint u)150 uint loBits(uint u) { return u & 0x7FFFFFFFU; }
151
mixBits(uint u,uint v)152 uint mixBits(uint u, uint v) { return hiBit(u) | loBits(v); }
153
154 uint state[N + 1];
155 uint *next;
156 int left = -1;
157
158 public:
159
Seed(uint seed)160 void Seed(uint seed) {
161 uint x = (seed | 1U) & 0xFFFFFFFFU, *s = state;
162 int j;
163 for (left = 0, *s++ = x, j = N; --j; *s++ = (x *= 69069U) & 0xFFFFFFFFU)
164 ;
165 }
166
Reload()167 uint Reload() {
168 uint *p0 = state, *p2 = state + 2, *pM = state + M, s0, s1;
169 int j;
170 if (left < -1) Seed(4357U);
171 left = N - 1;
172 next = state + 1;
173 for (s0 = state[0], s1 = state[1], j = N - M + 1; --j; s0 = s1, s1 = *p2++)
174 *p0++ = *pM++ ^ (mixBits(s0, s1) >> 1) ^ (loBit(s1) ? K : 0U);
175 for (pM = state, j = M; --j; s0 = s1, s1 = *p2++)
176 *p0++ = *pM++ ^ (mixBits(s0, s1) >> 1) ^ (loBit(s1) ? K : 0U);
177 s1 = state[0];
178 *p0 = *pM ^ (mixBits(s0, s1) >> 1) ^ (loBit(s1) ? K : 0U);
179 s1 ^= (s1 >> 11);
180 s1 ^= (s1 << 7) & 0x9D2C5680U;
181 s1 ^= (s1 << 15) & 0xEFC60000U;
182 return (s1 ^ (s1 >> 18));
183 }
184
Random()185 uint Random() {
186 uint y;
187 if (--left < 0) return (Reload());
188 y = *next++;
189 y ^= (y >> 11);
190 y ^= (y << 7) & 0x9D2C5680U;
191 y ^= (y << 15) & 0xEFC60000U;
192 return (y ^ (y >> 18));
193 }
194
ReSeed(uint seed)195 void ReSeed(uint seed) {
196 Seed(seed);
197 left = 0;
198 Reload();
199 }
200 };
201
202 class PCG32 {
203 // This is apparently better than the Mersenne Twister, and its also smaller/faster!
204 // Adapted from *Really* minimal PCG32 code / (c) 2014 M.E. O'Neill / pcg-random.org
205 // Licensed under Apache License 2.0 (NO WARRANTY, etc. see website).
206 uint64_t state = 0xABADCAFEDEADBEEF;
207 uint64_t inc = 0xDEADBABEABADD00D;
208
209 public:
210
Random()211 uint32_t Random() {
212 uint64_t oldstate = state;
213 // Advance internal state.
214 state = oldstate * 6364136223846793005ULL + (inc | 1);
215 // Calculate output function (XSH RR), uses old state for max ILP.
216 uint32_t xorshifted = uint32_t(((oldstate >> 18u) ^ oldstate) >> 27u);
217 uint32_t rot = oldstate >> 59u;
218 return (xorshifted >> rot) | (xorshifted << ((-rot) & 31));
219 }
220
ReSeed(uint32_t s)221 void ReSeed(uint32_t s) {
222 state = s;
223 inc = 0xDEADBABEABADD00D;
224 }
225 };
226
227 template<typename T> struct RandomNumberGenerator {
228 T rnd;
229
seedRandomNumberGenerator230 void seed(uint s) { rnd.ReSeed(s); }
231
operatorRandomNumberGenerator232 int operator()(int max) { return rnd.Random() % max; }
operatorRandomNumberGenerator233 int operator()() { return rnd.Random(); }
234
rnddoubleRandomNumberGenerator235 double rnddouble() { return rnd.Random() * (1.0 / 4294967296.0); }
rnd_floatRandomNumberGenerator236 float rnd_float() { return (float)rnddouble(); } // FIXME: performance?
rndfloatsignedRandomNumberGenerator237 float rndfloatsigned() { return (float)(rnddouble() * 2 - 1); }
238
239 double n2 = 0.0;
240 bool n2_cached = false;
241 // Returns gaussian with stddev of 1 and mean of 0.
242 // Box Muller method.
rnd_gaussianRandomNumberGenerator243 double rnd_gaussian() {
244 n2_cached = !n2_cached;
245 if (n2_cached) {
246 double x, y, r;
247 do {
248 x = 2.0 * rnddouble() - 1;
249 y = 2.0 * rnddouble() - 1;
250 r = x * x + y * y;
251 } while (r == 0.0 || r > 1.0);
252 double d = sqrt(-2.0 * log(r) / r);
253 double n1 = x * d;
254 n2 = y * d;
255 return n1;
256 } else {
257 return n2;
258 }
259 }
260 };
261
262 // Special case for to_string to get exact float formatting we need.
263 template<typename T> string to_string_float(T x, int decimals = -1) {
264 // ostringstream gives more consistent cross-platform results than to_string() for floats, and
265 // can at least be configured to turn scientific notation off.
266 ostringstream ss;
267 // Suppress scientific notation.
268 ss << std::fixed;
269 // There's no way to tell it to just output however many decimals are actually significant,
270 // sigh. Once you turn on fixed, it will default to 5 or 6, depending on platform, for both
271 // float and double. So we set our own more useful defaults:
272 int default_precision = sizeof(T) == sizeof(float) ? 6 : 12;
273 ss << std::setprecision(decimals <= 0 ? default_precision : decimals);
274 ss << x;
275 auto s = ss.str();
276 if (decimals <= 0) {
277 // First trim whatever lies beyond the precision to avoid garbage digits.
278 size_t max_significant = default_precision;
279 max_significant += 2; // "0."
280 if (s[0] == '-') max_significant++;
281 while (s.length() > max_significant && s.back() != '.') s.pop_back();
282 // Now strip unnecessary trailing zeroes.
283 while (s.back() == '0') s.pop_back();
284 // If there were only zeroes, keep at least 1.
285 if (s.back() == '.') s.push_back('0');
286 }
287 return s;
288 }
289
to_string_hex(ostringstream & ss,size_t x)290 inline void to_string_hex(ostringstream &ss, size_t x) {
291 ss << "0x" << std::hex << x << std::dec;
292 }
293
294 /* Accumulator: a container that is great for accumulating data like std::vector,
295 but without the reallocation/copying and unused memory overhead.
296 Instead stores elements as a 2-way growing list of blocks.
297 Loses the O(1) random access time, but instead has fast block-wise iteration.
298 Optimized to append/prepend many of T at once.
299 Can specify a minimum growth (block size) such that small appends are also efficient
300 */
301
302 template <typename T> class Accumulator {
303 struct Buf {
304 Buf *next;
305 size_t size, unused;
306
ElemsBuf307 T *Elems() { return this + 1; }
308 };
309
310 Buf *first = nullptr, *last = nullptr, *iterator = nullptr;
311 size_t mingrowth;
312 size_t totalsize = 0;
313
NewBuf(size_t _size,size_t numelems,T * elems,Buf * _next)314 Buf *NewBuf(size_t _size, size_t numelems, T *elems, Buf *_next) {
315 Buf *buf = (Buf *)malloc(sizeof(Buf) + sizeof(T) * _size);
316 buf->size = _size;
317 buf->unused = _size - numelems;
318 buf->next = _next;
319 t_memcpy(buf->Elems(), elems, numelems);
320 return buf;
321 }
322
323 // Don't copy, create instances of this class with new preferably.
324 Accumulator(const Accumulator &);
325 Accumulator &operator=(const Accumulator &);
326
327 public:
mingrowth(_mingrowth)328 Accumulator(size_t _mingrowth = 1024) : mingrowth(_mingrowth) {}
329
~Accumulator()330 ~Accumulator() {
331 while (first) {
332 Buf *buf = first->next;
333 free(first);
334 first = buf;
335 }
336 }
337
Size()338 size_t Size() { return totalsize; }
339
Append(const T & elem)340 void Append(const T &elem) { Append(&elem, 1); }
341
Append(const T * newelems,size_t amount)342 void Append(const T *newelems, size_t amount) {
343 totalsize += amount;
344 // First fill up any unused space in the last block, this the common path for small appends.
345 if (last && last->unused) {
346 size_t fit = min(amount, last->unused);
347 // Note: copy constructor skipped, if any.
348 t_memcpy(last->Elems() + (last->size - last->unused), newelems, fit);
349 last->unused -= fit;
350 amount -= fit;
351 }
352 // If there are more elements left, create a new block of mingrowth or bigger size.
353 if (amount) {
354 size_t allocsize = max(mingrowth, amount);
355 Buf *buf = NewBuf(allocsize, min(amount, allocsize), newelems, nullptr);
356 if (last) last->next = buf;
357 else last = first = buf;
358 }
359 }
360
Prepend(const T * newelems,size_t amount)361 void Prepend(const T *newelems, size_t amount) {
362 totalsize += amount;
363 // Since Prepend is a less common operation, we don't respect mingrowth here and just
364 // allocate a single block every time we could support mingrowth if needed, at the cost of
365 // complicating tracking where the unused space lives.
366 first = NewBuf(amount, amount, newelems, first);
367 if (!last) last = first;
368 }
369
370 // Custom iterator, because it is more efficient to do this a block at a time for clients
371 // wishing to process multiple elements at once. limitation of one iterator at a time seems
372 // reasonable.
ResetIterator()373 void ResetIterator() { iterator = first; }
374
Iterate(T * & buf)375 size_t Iterate(T *&buf) {
376 if (!iterator) return 0;
377 size_t size = iterator->size - iterator->unused;
378 buf = iterator->Elems();
379 iterator = iterator->next;
380 return size;
381 }
382
383 // Example of iterator usage: Copy into a single linear buffer. The size of dest must equal
384 // what Size() returns.
CopyTo(T * dest)385 void CopyTo(T *dest) {
386 T *buf;
387 size_t size;
388 ResetIterator();
389 while((size = Iterate(buf))) {
390 t_memcpy(dest, buf, size);
391 dest += size;
392 }
393 }
394 };
395
396 typedef Accumulator<uchar> ByteAccumulator;
397
398 // Easy "dynamic scope" helper: replace any variable by a new value, and at the end of the scope
399 // put the old value back.
400 template <typename T> struct DS {
401 T temp;
402 T &dest;
403
DSDS404 DS(T &_dest, const T &val) : dest(_dest) {
405 temp = dest;
406 dest = val;
407 }
408
~DSDS409 ~DS() {
410 dest = temp;
411 }
412 };
413
414 // Container that turns pointers into integers, with O(1) add/delete/get.
415 // Robust: passing invalid integers will just return a nullptr pointer / ignore the delete
416 // Cannot store nullptr pointers (will assert on Add)
417 // conveniently, index 0 is never used, so can be used by the client to indicate invalid index.
418
419 // TODO: Can change IntResourceManager to takes T's instead of T* by making the next field have a
420 // special value for in-use (e.g. -2, or 0 if you skip the first field).
421
422 template <typename T> class IntResourceManager {
423 struct Elem {
424 T *t;
425 size_t nextfree;
426
ElemElem427 Elem() : t(nullptr), nextfree(size_t(-1)) {}
428 };
429
430 vector<Elem> elems;
431 size_t firstfree = size_t(-1);
432
433 public:
434
IntResourceManager()435 IntResourceManager() {
436 // A nullptr item at index 0 that can never be allocated/deleted.
437 elems.push_back(Elem());
438 }
439
~IntResourceManager()440 ~IntResourceManager() {
441 for (auto &e : elems)
442 if (e.t)
443 delete e.t;
444 }
445
Add(T * t)446 size_t Add(T *t) {
447 // We can't store nullptr pointers as elements, because we wouldn't be able to distinguish
448 // them from unallocated slots.
449 assert(t);
450 size_t i = elems.size();
451 if (firstfree < i) {
452 i = firstfree;
453 firstfree = elems[i].nextfree;
454 } else {
455 elems.push_back(Elem());
456 }
457 elems[i].t = t;
458 return i;
459 }
460
Get(size_t i)461 T *Get(size_t i) {
462 return i < elems.size() ? elems[i].t : nullptr;
463 }
464
Delete(size_t i)465 void Delete(size_t i) {
466 T *e = Get(i);
467 if (e) {
468 delete e;
469 elems[i].t = nullptr;
470 elems[i].nextfree = firstfree;
471 firstfree = i;
472 }
473 }
474
Range()475 size_t Range() { return elems.size(); } // If you wanted to iterate over all elements.
476 };
477
478 // Same as IntResourceManager, but now uses pointer tagging to store the free list in-place.
479 // Uses half the memory. Access is slightly slower, but if memory bound could still be faster
480 // overall. Can store nullptr pointers, but not pointers with the lowest bit set (e.g. char *
481 // pointing inside of another allocation, will assert on Add).
482 template <typename T> class IntResourceManagerCompact {
483 vector<T *> elems;
484 size_t firstfree = SIZE_MAX;
485 const function<void(T *e)> deletefun;
486
487 // Free slots have their lowest bit set, and represent an index (shifted by 1).
IsFree(T * e)488 bool IsFree(T *e) { return ((size_t)e) & 1; }
GetIndex(T * e)489 size_t GetIndex(T *e) { return ((size_t)e) >> 1; }
CreateIndex(size_t i)490 T *CreateIndex(size_t i) { return (T *)((i << 1) | 1); }
ValidSlot(size_t i)491 bool ValidSlot(size_t i) { return i < elems.size() && !IsFree(elems[i]); }
492
493 public:
494
IntResourceManagerCompact(const function<void (T * e)> & _df)495 IntResourceManagerCompact(const function<void(T *e)> &_df)
496 : deletefun(_df) {
497 // Slot 0 is permanently blocked, so can be used to denote illegal index.
498 elems.push_back(nullptr);
499 }
500
~IntResourceManagerCompact()501 ~IntResourceManagerCompact() {
502 ForEach(deletefun);
503 }
504
ForEach(const function<void (T * e)> & f)505 void ForEach(const function<void(T *e)> &f) {
506 for (auto e : elems)
507 if (!IsFree(e) && e)
508 f(e);
509 }
510
Add(T * e)511 size_t Add(T *e) {
512 assert(!IsFree(e)); // Can't store pointers with their lowest bit set.
513
514 size_t i = elems.size();
515 if (firstfree < i) {
516 i = firstfree;
517 firstfree = GetIndex(elems[i]);
518 elems[i] = e;
519 } else {
520 elems.push_back(e);
521 }
522 return i;
523 }
524
Get(size_t i)525 T *Get(size_t i) {
526 return ValidSlot(i) ? elems[i] : nullptr;
527 }
528
Delete(size_t i)529 void Delete(size_t i) {
530 if (ValidSlot(i) && i) {
531 T *&e = elems[i];
532 if (e) deletefun(e);
533 e = CreateIndex(firstfree);
534 firstfree = i;
535 }
536 }
537
Range()538 size_t Range() { return elems.size(); } // If you wanted to iterate over all elements.
539 };
540
541
542 /*
543
544 // From: http://average-coder.blogspot.com/2012/07/python-style-range-loops-in-c.html
545
546 template<class T>
547 class range_iterator : public std::iterator<std::input_iterator_tag, T>{
548 public:
549 range_iterator(const T &item) : item(item) {}
550
551 // Dereference, returns the current item.
552 const T &operator*() {
553 return item;
554 }
555
556 // Prefix.
557 range_iterator<T> &operator++() {
558 ++item;
559 return *this;
560 }
561
562 // Postfix.
563 range_iterator<T> &operator++(int) {
564 range_iterator<T> range_copy(*this);
565 ++item;
566 return range_copy;
567 }
568
569 // Compare internal item
570 bool operator==(const range_iterator<T> &rhs) {
571 return item == rhs.item;
572 }
573
574 // Same as above
575 bool operator!=(const range_iterator<T> &rhs) {
576 return !(*this == rhs);
577 }
578 private:
579 T item;
580 };
581
582 template<class T>
583 class range_wrapper {
584 public:
585 range_wrapper(const T &r_start, const T &r_end)
586 : r_start(r_start), r_end(r_end) {}
587
588 range_iterator<T> begin() {
589 return range_iterator<T>(r_start);
590 }
591
592 range_iterator<T> end() {
593 return range_iterator<T>(r_end);
594 }
595 private:
596 T r_start, r_end;
597 };
598
599 // Returns a range_wrapper<T> containing the range [start, end)
600 template<class T>
601 range_wrapper<T> range(const T &start, const T &end) {
602 return range_wrapper<T>(start, end);
603 }
604
605 // Returns a range_wrapper<T> containing the range [T(), end)
606 template<class T>
607 range_wrapper<T> range(const T &end) {
608 return range_wrapper<T>(T(), end);
609 }
610
611 */
612
613 // From: http://reedbeta.com/blog/python-like-enumerate-in-cpp17/
614
615 template <typename T,
616 typename TIter = decltype(std::begin(std::declval<T>())),
617 typename = decltype(std::end(std::declval<T>()))>
enumerate(T && iterable)618 constexpr auto enumerate(T && iterable) {
619 struct iterator {
620 size_t i;
621 TIter iter;
622 bool operator != (const iterator & other) const { return iter != other.iter; }
623 void operator ++ () { ++i; ++iter; }
624 auto operator * () const { return std::tie(i, *iter); }
625 };
626 struct iterable_wrapper {
627 T iterable;
628 auto begin() { return iterator{ 0, std::begin(iterable) }; }
629 auto end() { return iterator{ 0, std::end(iterable) }; }
630 };
631 return iterable_wrapper{ std::forward<T>(iterable) };
632 }
633
634 // --- Reversed iterable
635
636 template<typename T> struct reversion_wrapper { T& iterable; };
begin(reversion_wrapper<T> w)637 template<typename T> auto begin(reversion_wrapper<T> w) { return rbegin(w.iterable); }
end(reversion_wrapper<T> w)638 template<typename T> auto end(reversion_wrapper<T> w) { return rend(w.iterable); }
reverse(T && iterable)639 template<typename T> reversion_wrapper<T> reverse(T &&iterable) { return { iterable }; }
640
641 // Stops a class from being accidental victim to default copy + destruct twice problem.
642
643 class NonCopyable {
644 NonCopyable(const NonCopyable&);
645 const NonCopyable& operator=(const NonCopyable&);
646
647 protected:
NonCopyable()648 NonCopyable() {}
649 //virtual ~NonCopyable() {}
650 };
651
652 // This turns a sequence of booleans (the current value, and the values it had before) into a
653 // single number:
654 // 0: "became false": false, but it was true before.
655 // 1: "became true": true, but it was false before.
656 // >1: "still true": true, and was already true. Number indicates how many times it has been true
657 // in sequence.
658 // <0: "still false": false, and false before it. Negative number indicates how many times it has
659 // been false.
660 // >=1: "true": currently true, regardless of history.
661 // <=0: "false": currently false, regardless of history.
662
663 // This is useful for detecting state changes and acting on them, such as for input device buttons.
664
665 // T must be a signed integer type. Bigger types means more history before it clamps.
666
667 // This is nicer than a bitfield, because basic checks like "became true" are simpler, it encodes
668 // the history in a more human readable way, and it can encode a way longer history in the same
669 // bits.
670 template<typename T> class TimeBool {
671 T step;
672
673 enum {
674 SIGN_BIT = 1 << ((sizeof(T) * 8) - 1),
675 HIGHEST_VALUE_BIT = SIGN_BIT >> 1
676 };
677
678 // This encodes 2 booleans into 1 number.
Step(bool current,bool before)679 static T Step(bool current, bool before) {
680 return T(current) * 2 - T(!before);
681 }
682
TimeBool(T _step)683 TimeBool(T _step) : step(_step) {}
684
685 public:
686
TimeBool()687 TimeBool() : step(-HIGHEST_VALUE_BIT) {}
TimeBool(bool current,bool before)688 TimeBool(bool current, bool before) : step(Step(current, before)) {}
689
True()690 bool True() { return step >= 1; }
False()691 bool False() { return step <= 0; }
BecameTrue()692 bool BecameTrue() { return step == 1; }
BecameFalse()693 bool BecameFalse() { return step == 0; }
StillTrue()694 bool StillTrue() { return step > 1; }
StillFalse()695 bool StillFalse() { return step < 0; }
696
Step()697 T Step() { return step; }
698
Sign()699 T Sign() { return True() * 2 - 1; }
700
701 // This makes one time step, retaining the current value.
702 // It increases the counter, i.e. 2 -> 3 or -1 -> -2, indicating the amount of steps it has
703 // been true. Only allows this to increase to the largest power of 2 that fits inside T, e.g.
704 // 64 and -64 for a char.
Advance()705 void Advance() {
706 // Increase away from 0 if highest 2 bits are equal.
707 if ((step & HIGHEST_VALUE_BIT) == (step & SIGN_BIT))
708 step += Sign();
709 }
710
711 // Sets new value, assumes its different from the one before (wipes history).
Set(bool newcurrent)712 void Set(bool newcurrent) { step = Step(newcurrent, True()); }
Update(bool newcurrent)713 void Update(bool newcurrent) { Advance(); Set(newcurrent); }
714
715 // Previous state.
716 // This gives accurate history for the "still true/false" values, but for "became true/false"
717 // it assumes the history is "still false/true" as opposed to "became false/true" (which is
718 // also possible). This is typically desirable, and usually the difference doesn't matter.
Back()719 TimeBool Back() { return TimeBool(step - Sign() * (step & ~1 ? 1 : HIGHEST_VALUE_BIT)); }
720 };
721
722 typedef TimeBool<char> TimeBool8;
723
FNV1A(string_view s)724 inline uint FNV1A(string_view s) {
725 uint hash = 0x811C9DC5;
726 for (auto c : s) {
727 hash ^= (uchar)c;
728 hash *= 0x01000193;
729 }
730 return hash;
731 }
732
733 // dynamic_cast succeeds on both the given type and any derived types, which is frequently
734 // undesirable. "is" only succeeds on the exact type given, and is cheaper. It also defaults
735 // to pointer arguments.
Is(U * o)736 template<typename T, typename U> T *Is(U *o) {
737 return typeid(T) == typeid(*o) ? static_cast<T *>(o) : nullptr;
738 }
739
Is(const U * o)740 template<typename T, typename U> const T *Is(const U *o) {
741 return typeid(T) == typeid(*o) ? static_cast<const T *>(o) : nullptr;
742 }
743
Is(U & o)744 template<typename T, typename U> T *Is(U &o) {
745 return typeid(T) == typeid(o) ? static_cast<T *>(&o) : nullptr;
746 }
747
Is(const U & o)748 template<typename T, typename U> const T *Is(const U &o) {
749 return typeid(T) == typeid(o) ? static_cast<const T *>(&o) : nullptr;
750 }
751
AssertIs(U * o)752 template<typename T, typename U> T *AssertIs(U *o) {
753 assert(typeid(T) == typeid(*o));
754 return static_cast<T *>(o);
755 }
756
AssertIs(const U * o)757 template<typename T, typename U> const T *AssertIs(const U *o) {
758 assert(typeid(T) == typeid(*o));
759 return static_cast<const T *>(o);
760 }
761
762
PopCount(uint32_t val)763 inline int PopCount(uint32_t val) {
764 #ifdef _WIN32
765 return (int)__popcnt(val);
766 #else
767 return __builtin_popcount(val);
768 #endif
769 }
770
PopCount(uint64_t val)771 inline int PopCount(uint64_t val) {
772 #ifdef _WIN32
773 #ifdef _WIN64
774 return (int)__popcnt64(val);
775 #else
776 return (int)(__popcnt((uint)val) + __popcnt((uint)(val >> 32)));
777 #endif
778 #else
779 return __builtin_popcountll(val);
780 #endif
781 }
782
783
784 // string & string_view helpers.
785
786 inline string operator+(string_view a, string_view b) {
787 string r;
788 r.reserve(a.size() + b.size());
789 r += a;
790 r += b;
791 return r;
792 }
793
cat_helper(stringstream &)794 inline void cat_helper(stringstream &) {}
cat_helper(stringstream & ss,const T & t,const Ts &...args)795 template<typename T, typename ...Ts> void cat_helper(stringstream &ss, const T &t, const Ts&... args) {
796 ss << t;
797 cat_helper(ss, args...);
798 }
cat(const Ts &...args)799 template<typename ...Ts> string cat(const Ts&... args) {
800 stringstream ss;
801 cat_helper(ss, args...);
802 return ss.str();
803 }
804
805 // This method is in C++20, but quite essential.
starts_with(string_view sv,string_view start)806 inline bool starts_with(string_view sv, string_view start) {
807 return start.size() <= sv.size() && sv.substr(0, start.size()) == start;
808 }
809
810 // Efficient passing of string_view to old APIs wanting a null-terminated
811 // const char *: only go thru a string if not null-terminated already, which is
812 // often the case.
813 // NOTE: uses static string, so to call twice inside the same statement supply
814 // template args <0>, <1> etc.
null_terminated(string_view sv)815 template<int I = 0> const char *null_terminated(string_view sv) {
816 if (!sv.data()[sv.size()]) return sv.data();
817 static string temp;
818 temp = sv;
819 return temp.data();
820 }
821
822 template<typename T> T parse_int(string_view sv, int base = 10, char **end = nullptr) {
823 // This should be using from_chars(), which apparently is not supported by
824 // gcc/clang yet :(
825 return (T)strtoll(null_terminated(sv), end, base);
826 }
827
828
829 // Strict aliasing safe memory reading and writing.
830 // memcpy with a constant size is replaced by a single instruction in VS release mode, and for
831 // clang/gcc always.
832
ReadMem(const void * p)833 template<typename T> T ReadMem(const void *p) {
834 T dest;
835 memcpy(&dest, p, sizeof(T));
836 return dest;
837 }
838
ReadMemInc(const uchar * & p)839 template<typename T> T ReadMemInc(const uchar *&p) {
840 T dest = ReadMem<T>(p);
841 p += sizeof(T);
842 return dest;
843 }
844
WriteMemInc(uchar * & dest,const T & src)845 template<typename T> void WriteMemInc(uchar *&dest, const T &src) {
846 memcpy(dest, &src, sizeof(T));
847 dest += sizeof(T);
848 }
849
850 // Enum operators.
851
852 #define DEFINE_BITWISE_OPERATORS_FOR_ENUM(T) \
853 inline T operator~ (T a) { return (T)~(int)a; } \
854 inline T operator| (T a, T b) { return (T)((int)a | (int)b); } \
855 inline T operator& (T a, T b) { return (T)((int)a & (int)b); } \
856 inline T &operator|= (T &a, T b) { return (T &)((int &)a |= (int)b); } \
857 inline T &operator&= (T &a, T b) { return (T &)((int &)a &= (int)b); }
858
859 #ifndef DISABLE_EXCEPTION_HANDLING
860 #define USE_EXCEPTION_HANDLING
861 #endif
862
863 #ifdef USE_EXCEPTION_HANDLING
864 #define THROW_OR_ABORT(X) { throw (X); }
865 #else
866 #define THROW_OR_ABORT(X) { printf("%s\n", (X).c_str()); abort(); }
867 #endif
868
869
unit_test_tools()870 inline void unit_test_tools() {
871 assert(strcmp(null_terminated<0>(string_view("aa", 1)),
872 null_terminated<1>(string_view("bb", 1))) != 0);
873 }
874