1 /// 2 /// @file Bucket.hpp 3 /// @brief A bucket is a container for sieving primes. 4 /// The Bucket class is designed as a singly linked list, 5 /// once there is no more space in the current Bucket 6 /// a new Bucket is allocated. 7 /// 8 /// Copyright (C) 2020 Kim Walisch, <kim.walisch@gmail.com> 9 /// 10 /// This file is distributed under the BSD License. See the COPYING 11 /// file in the top level directory. 12 /// 13 14 #ifndef BUCKET_HPP 15 #define BUCKET_HPP 16 17 #include "config.hpp" 18 #include "pmath.hpp" 19 20 #include <stdint.h> 21 #include <cstddef> 22 #include <cassert> 23 24 namespace primesieve { 25 26 /// Each SievingPrime object contains a sieving prime and the 27 /// position of its next multiple inside the sieve array i.e. 28 /// multipleIndex and a wheelIndex. In order to reduce the memory 29 /// usage the multipleIndex and wheelIndex are packed into a 30 /// single 32-bit variable. 31 /// 32 class SievingPrime 33 { 34 public: 35 enum { 36 MAX_MULTIPLEINDEX = (1 << 23) - 1, 37 MAX_WHEELINDEX = (1 << (32 - 23)) - 1 38 }; 39 40 SievingPrime() = default; 41 SievingPrime(uint64_t sievingPrime,uint64_t multipleIndex,uint64_t wheelIndex)42 SievingPrime(uint64_t sievingPrime, 43 uint64_t multipleIndex, 44 uint64_t wheelIndex) 45 { 46 set(sievingPrime, multipleIndex, wheelIndex); 47 } 48 set(uint64_t multipleIndex,uint64_t wheelIndex)49 void set(uint64_t multipleIndex, 50 uint64_t wheelIndex) 51 { 52 assert(multipleIndex <= MAX_MULTIPLEINDEX); 53 assert(wheelIndex <= MAX_WHEELINDEX); 54 indexes_ = (uint32_t) (multipleIndex | (wheelIndex << 23)); 55 } 56 set(uint64_t sievingPrime,uint64_t multipleIndex,uint64_t wheelIndex)57 void set(uint64_t sievingPrime, 58 uint64_t multipleIndex, 59 uint64_t wheelIndex) 60 { 61 assert(multipleIndex <= MAX_MULTIPLEINDEX); 62 assert(wheelIndex <= MAX_WHEELINDEX); 63 indexes_ = (uint32_t) (multipleIndex | (wheelIndex << 23)); 64 sievingPrime_ = (uint32_t) sievingPrime; 65 } 66 getSievingPrime() const67 uint64_t getSievingPrime() const 68 { 69 return sievingPrime_; 70 } 71 getMultipleIndex() const72 uint64_t getMultipleIndex() const 73 { 74 return indexes_ & MAX_MULTIPLEINDEX; 75 } 76 getWheelIndex() const77 uint64_t getWheelIndex() const 78 { 79 return indexes_ >> 23; 80 } 81 82 private: 83 /// multipleIndex = 23 least significant bits of indexes_ 84 /// wheelIndex = 9 most significant bits of indexes_ 85 uint32_t indexes_; 86 uint32_t sievingPrime_; 87 }; 88 89 /// The Bucket data structure is used to store sieving primes. 90 /// @see http://www.ieeta.pt/~tos/software/prime_sieve.html 91 /// The Bucket class is designed as a singly linked list, once 92 /// there is no more space in the current Bucket a new Bucket 93 /// is allocated. 94 /// 95 class Bucket 96 { 97 public: begin()98 SievingPrime* begin() { return &sievingPrimes_[0]; } end()99 SievingPrime* end() { return end_; } next()100 Bucket* next() { return next_; } setNext(Bucket * next)101 void setNext(Bucket* next) { next_ = next; } setEnd(SievingPrime * end)102 void setEnd(SievingPrime* end) { end_ = end; } reset()103 void reset() { end_ = begin(); } 104 105 /// Get the sieving prime's bucket. 106 /// For performance reasons we don't keep an array with all 107 /// buckets. Instead we find the sieving prime's bucket by 108 /// doing pointer arithmetic using the sieving prime's address. 109 /// Since all buckets are aligned by sizeof(Bucket) we 110 /// calculate the next address that is smaller than the sieving 111 /// prime's address and that is aligned by sizeof(Bucket). 112 /// That's the address of the sieving prime's bucket. 113 /// get(SievingPrime * sievingPrime)114 static Bucket* get(SievingPrime* sievingPrime) 115 { 116 assert(sievingPrime != nullptr); 117 std::size_t address = (std::size_t) sievingPrime; 118 // We need to adjust the address 119 // in case the bucket is full. 120 address -= 1; 121 address -= address % sizeof(Bucket); 122 return (Bucket*) address; 123 } 124 125 /// Returns true if the bucket is full with sieving primes 126 /// (or if there is no bucket i.e. sievingPrime == nullptr). 127 /// Each bucket's memory address is aligned by sizeof(Bucket) 128 /// (which is a power of 2) in the MemoryPool. This allows 129 /// us to quickly check if the bucket is full using the next 130 /// sieving prime's address % sizeof(Bucket). 131 /// isFull(SievingPrime * sievingPrime)132 static bool isFull(SievingPrime* sievingPrime) 133 { 134 std::size_t address = (std::size_t) sievingPrime; 135 return address % sizeof(Bucket) == 0; 136 } 137 138 private: 139 enum { 140 SIEVING_PRIMES_OFFSET = sizeof(SievingPrime*) + sizeof(Bucket*), 141 SIEVING_PRIMES_SIZE = (config::BUCKET_BYTES - SIEVING_PRIMES_OFFSET) / sizeof(SievingPrime) 142 }; 143 144 SievingPrime* end_; 145 Bucket* next_; 146 SievingPrime sievingPrimes_[SIEVING_PRIMES_SIZE]; 147 }; 148 149 static_assert(isPow2(sizeof(Bucket)), "sizeof(Bucket) must be a power of 2!"); 150 151 } // namespace 152 153 #endif 154