bamboo.hashgen source code

1 module bamboo.hashgen;
2 
3 import std.traits;
4 import bamboo.legacy_hash;
5 import bamboo.types;
6 
7 /// Computes a hash using `bamboo.legacy_hash`.
8 uint computeHash(Module file)
9 {
10     HashGenerator gen;
11     hashModule(gen, file);
12     return gen.hash;
13 }
14 
15 /// Provides mechanisms for generating hashes for DClasses.
16 struct HashGenerator
17 {
18     private size_t _hash;
19     private size_t _index;
20     private PrimeGenerator!size_t _primes;
21 
22 nothrow @nogc @safe:
23 
24     /// Adds an int to the accumulator.
25     void addInt(size_t num)
26     {
27         _index++;
28         _hash += _primes.front * num;
29         _primes.popFront;
30     }
31 
32     /// Adds a string to the accumulator.
33     void addString(string str)
34     {
35         addInt(str.length);
36 
37         foreach (c; str)
38         {
39             addInt(cast(size_t) c);
40         }
41     }
42 
43     /// Gets the current hash.
44     uint hash() inout @property
45     {
46         return cast(uint)(_hash & 0xffffffff);
47     }
48 }
49 
50 /// Utility for generating prime numers.
51 struct PrimeGenerator(T) if (isIntegral!T)
52 {
53     private T _current = 2;
54 
55 pure nothrow @nogc @safe:
56 
57     ///
58     enum bool empty = false;
59 
60     /// Returns: the current prime.
61     T front() inout @property
62     {
63         return _current;
64     }
65 
66     /// Advances the generator.
67     void popFront()
68     {
69         if (_current == 2)
70         {
71             ++_current;
72             return;
73         }
74 
75         // This is not at all efficient.
76         while (!isPrime(_current += 2))
77         {
78         }
79     }
80 
81     /// Creates a copy of the generator.
82     typeof(this) save()
83     {
84         return PrimeGenerator(_current);
85     }
86 }
87 
88 ///
89 pure nothrow @nogc @safe unittest
90 {
91     import std.algorithm : equal;
92     import std.range : take;
93 
94     // dfmt off
95     static immutable earlyPrimes = 
96        [ 2,   3,   5,   7,  11,   13,  17,  19,  23,  29,
97         31,  37,  41,  43,  47,   53,  59,  61,  67,  71,
98         73,  79,  83,  89,  97,  101, 103, 107, 109, 113,
99         127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 
100         179, 181, 191, 193, 197, 199, 211, 223, 227, 229];
101     // dfmt on
102 
103     auto primes = PrimeGenerator!int();
104 
105     assert(equal(earlyPrimes, primes.take(earlyPrimes.length)));
106 }
107 
108 /// Checks if a number is prime.
109 /// Returns: `true` if `n` is prime.
110 bool isPrime(T)(T n) if (isIntegral!T)
111 {
112     if (n == 2)
113     {
114         return true;
115     }
116     if (n == 1 || n < 1 || (n & 1) == 0)
117     {
118         return false;
119     }
120     if (n > 3)
121     {
122         for (auto i = 3; i * i <= n; i += 2)
123         {
124             if ((n % i) == 0)
125                 return false;
126         }
127     }
128     return true;
129 }
130 
131 ///
132 pure nothrow @nogc @safe unittest
133 {
134     assert(isPrime(2));
135     assert(isPrime(3));
136     assert(isPrime(5));
137     assert(isPrime(7));
138     assert(isPrime(199UL));
139     assert(isPrime(104_729)); // 10,000th prime.
140 
141     assert(!isPrime(-199));
142     assert(!isPrime(-1));
143     assert(!isPrime(1)); // 1 is not a prime number: https://primes.utm.edu/notes/faq/one.html
144     assert(!isPrime(4));
145 }