Changeset 22f94a4 for doc/theses/thierry_delisle_PhD/code/utils.hpp

Timestamp:

Aug 11, 2020, 4:40:15 PM (5 years ago)

Author:

Thierry Delisle <tdelisle@…>

Branches:

ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum

Children:

0d070ca

Parents:

07d867b (diff), 129674b (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Message:

Merge branch 'master' into new-ast

File:

• doc/theses/thierry_delisle_PhD/code/utils.hpp (modified) (3 diffs)

doc/theses/thierry_delisle_PhD/code/utils.hpp

@@ -35 +35 @@
 };
 
+// class Random {
+// private:
+//      unsigned int seed;
+// public:
+//      Random(int seed) {
+//              this->seed = seed;
+//      }
+
+//      /** returns pseudorandom x satisfying 0 <= x < n. **/
+//      unsigned int next() {
+//              seed ^= seed << 6;
+//              seed ^= seed >> 21;
+//              seed ^= seed << 7;
+//              return seed;
+//      }
+// };
+
+constexpr uint64_t extendedEuclidY(uint64_t a, uint64_t b);
+constexpr uint64_t extendedEuclidX(uint64_t a, uint64_t b){
+    return (b==0) ? 1 : extendedEuclidY(b, a - b * (a / b));
+}
+constexpr uint64_t extendedEuclidY(uint64_t a, uint64_t b){
+    return (b==0) ? 0 : extendedEuclidX(b, a - b * (a / b)) - (a / b) * extendedEuclidY(b, a - b * (a / b));
+}
+
 class Random {
 private:
-        unsigned int seed;
+        uint64_t x;
+
+        static constexpr const uint64_t M  = 1ul << 48ul;
+        static constexpr const uint64_t A  = 25214903917;
+        static constexpr const uint64_t C  = 11;
+        static constexpr const uint64_t D  = 16;
+
 public:
-        Random(int seed) {
-                this->seed = seed;
+        static constexpr const uint64_t m  = M;
+        static constexpr const uint64_t a  = A;
+        static constexpr const uint64_t c  = C;
+        static constexpr const uint64_t d  = D;
+        static constexpr const uint64_t ai = extendedEuclidX(A, M);
+public:
+        Random(unsigned int seed) {
+                this->x = seed * a;
         }
 
         /** returns pseudorandom x satisfying 0 <= x < n. **/
         unsigned int next() {
-                seed ^= seed << 6;
-                seed ^= seed >> 21;
-                seed ^= seed << 7;
-                return seed;
-        }
+                //nextx = (a * x + c) % m;
+                x = (A * x + C) & (M - 1);
+                return x >> D;
+        }
+        unsigned int prev() {
+                //prevx = (ainverse * (x - c)) mod m
+                unsigned int r = x >> D;
+                x = ai * (x - C) & (M - 1);
+                return r;
+        }
+
+        void set_raw_state(uint64_t _x) {
+                this->x = _x;
+        }
+
+        uint64_t get_raw_state() {
+                return this->x;
+        }
 };
 
@@ -106 +156 @@
 }
 
+static inline unsigned rand_bit(unsigned rnum, size_t mask) __attribute__((artificial));
 static inline unsigned rand_bit(unsigned rnum, size_t mask) {
         unsigned bit = mask ? rnum % __builtin_popcountl(mask) : 0;
@@ -143 +194 @@
 #endif
 }
+
+struct spinlock_t {
+        std::atomic_bool ll = { false };
+
+        inline void lock() {
+                while( __builtin_expect(ll.exchange(true),false) ) {
+                        while(ll.load(std::memory_order_relaxed))
+                                asm volatile("pause");
+                }
+        }
+
+        inline bool try_lock() {
+                return false == ll.exchange(true);
+        }
+
+        inline void unlock() {
+                ll.store(false, std::memory_order_release);
+        }
+
+        inline explicit operator bool() {
+                return ll.load(std::memory_order_relaxed);
+        }
+};
+
+static inline bool bts(std::atomic_size_t & target, size_t bit ) {
+        //*
+        int result = 0;
+        asm volatile(
+                "LOCK btsq %[bit], %[target]\n\t"
+                :"=@ccc" (result)
+                : [target] "m" (target), [bit] "r" (bit)
+        );
+        return result != 0;
+        /*/
+        size_t mask = 1ul << bit;
+        size_t ret = target.fetch_or(mask, std::memory_order_relaxed);
+        return (ret & mask) != 0;
+        //*/
+}
+
+static inline bool btr(std::atomic_size_t & target, size_t bit ) {
+        //*
+        int result = 0;
+        asm volatile(
+                "LOCK btrq %[bit], %[target]\n\t"
+                :"=@ccc" (result)
+                : [target] "m" (target), [bit] "r" (bit)
+        );
+        return result != 0;
+        /*/
+        size_t mask = 1ul << bit;
+        size_t ret = target.fetch_and(~mask, std::memory_order_relaxed);
+        return (ret & mask) != 0;
+        //*/
+}