Tuned prime example and cbitset.h

2 files changed, 19 insertions, 28 deletions

diff --git a/examples/prime.c b/examples/prime.c
index 974a7d90..f04c71a3 100644
--- a/examples/prime.c
+++ b/examples/prime.c
@@ -1,10 +1,7 @@
 #include <stdio.h>

 #include <stc/cbitset.h>

-#include <stc/cvec.h>

 

-declare_cvec(ux, uint64_t);

-

-static inline cvec_ux sieveOfEratosthenes(size_t n)

+static inline cbitset_t sieveOfEratosthenes(size_t n)

 {

     cbitset_t pbits = cbitset_make(n + 1, true);

     cbitset_reset(&pbits, 0);

@@ -18,27 +15,23 @@ static inline cvec_ux sieveOfEratosthenes(size_t n)
             }

         }

     }

-    puts("count:");

-    size_t np = cbitset_count(pbits);

-    puts("done");

-    cvec_ux primes = cvec_init;

-    cvec_ux_reserve(&primes, np);

-    for (uint32_t i = 2; i <= n; ++i)

-       if (cbitset_test(pbits, i)) cvec_ux_push_back(&primes, i);

-    

-    cbitset_destroy(&pbits);

-    return primes;

+    return pbits;

 } 

 

+

 int main(void)

 {

-    int n = 1000000000;

+    int n = 100000000;

     printf("computing prime numbers up to %u\n", n);

     

-    cvec_ux primes = sieveOfEratosthenes(n);

-    printf("number of primes: %zu\n", cvec_size(primes));

-    for (size_t i = 0; i < 100; ++i)

-       printf("%zu ", primes.data[i]);

+    cbitset_t primes = sieveOfEratosthenes(n);

+    puts("done");

+    

+    size_t np = cbitset_count(primes);

+    printf("number of primes: %zu\n", np);

 

-    cvec_ux_destroy(&primes);

+    for (uint32_t i = 2; i <= 1000; ++i)

+       if (cbitset_test(primes, i)) printf("%zu ", i);

+    puts("");

+    cbitset_destroy(&primes);

 }
\ No newline at end of file
diff --git a/stc/cbitset.h b/stc/cbitset.h
index badc5ba0..acd86994 100644
--- a/stc/cbitset.h
+++ b/stc/cbitset.h
@@ -63,8 +63,8 @@ STC_INLINE cbitset_t cbitset_make(size_t size, bool value) {
     return set;

 }

 STC_INLINE cbitset_t cbitset_make_copy(cbitset_t other) {

-    size_t n = (other.size + 63) >> 6;

-    cbitset_t set = {(uint64_t *) memcpy(malloc(n * 8), other._arr, n * 8), other.size};

+    size_t bytes = ((other.size + 63) >> 6) * 8;

+    cbitset_t set = {(uint64_t *) memcpy(malloc(bytes), other._arr, bytes), other.size};

     return set;

 }

 STC_INLINE void cbitset_destroy(cbitset_t* self) {

@@ -158,10 +158,8 @@ STC_API void cbitset_resize(cbitset_t* self, size_t size, bool value) {
 #else

 /* http://en.wikipedia.org/wiki/Hamming_weight#Efficient_implementation */

 static inline uint64_t c_popcount64(uint64_t x) {

-    uint64_t m1 = 0x5555555555555555ll;

-    uint64_t m2 = 0x3333333333333333ll;

-    uint64_t m4 = 0x0F0F0F0F0F0F0F0Fll;

-    uint64_t h01 = 0x0101010101010101ll;

+    const uint64_t m1 = 0x5555555555555555, m2 = 0x3333333333333333,

+                   m4 = 0x0f0f0f0f0f0f0f0f, h01 = 0x0101010101010101;

     x -= (x >> 1) & m1;

     x = (x & m2) + ((x >> 2) & m2);

     x = (x + (x >> 4)) & m4;

@@ -170,9 +168,9 @@ static inline uint64_t c_popcount64(uint64_t x) {
 #endif

 

 STC_API size_t cbitset_count(cbitset_t set) {

-    size_t count = 0, n = (set.size + 63) >> 6;

+    size_t count = 0, n = ((set.size + 63) >> 6) - 1;

     if (set.size > 0) {

-        --n; for (size_t i=0; i<n; ++i) count += c_popcount64(set._arr[i]);

+        for (size_t i=0; i<n; ++i) count += c_popcount64(set._arr[i]);

         count += c_popcount64(set._arr[n] & ((1ull << (set.size & 63)) - 1));

     }

     return count;