From 75e6b0e8c55b0f648c737693952e0709449fa40a Mon Sep 17 00:00:00 2001
From: Tyge Løvset <tylo@norceresearch.no>
Date: Fri, 31 Jul 2020 00:09:56 +0200
Subject: Tuned prime example and cbitset.h

---
 examples/prime.c | 33 +++++++++++++--------------------
 stc/cbitset.h    | 14 ++++++--------
 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;
-- 
cgit v1.2.3