primes.c (2241B)
1 #include <stdio.h> 2 #include <string.h> 3 #include <stdbool.h> 4 #include <pthread.h> 5 6 #include "primes.h" 7 #include "storage.h" 8 9 #define NTHREADS 16 10 #define INDEX(i) ((i) >> 3) 11 #define MASK(i) (unsigned char)(1 << ((i) % 8)) 12 13 unsigned char primes_table[TABLESIZE]; 14 struct interval { int low; int high; int count; }; 15 16 void *pthread_routine(void *); 17 int primes_in_range(int, int, void (*)(const char *)); 18 void set_nonprime(unsigned char *, int); 19 bool isprime(const unsigned char *, int); 20 21 int primes_in_range(int low, int high, void (*log)(const char *)) { 22 static bool table_is_loaded = false; 23 24 pthread_t threads[NTHREADS]; 25 struct interval args[NTHREADS]; 26 27 if (low < 0 || high < low) 28 return 0; 29 30 if (!table_is_loaded) { 31 if (!read_table(primes_table)) { 32 generate_primes(primes_table, log); 33 if (!store_table(primes_table)) 34 log("Error storing table to indexed DB"); 35 } 36 37 table_is_loaded = true; 38 } 39 40 int interval_size = (high-low)/NTHREADS + 1; 41 for (int i = 0; i < NTHREADS; i++) { 42 args[i].low = low + i*interval_size; 43 args[i].high = args[i].low + interval_size; 44 pthread_create(&threads[i], NULL, pthread_routine, &args[i]); 45 } 46 47 log("All threads have started, computing..."); 48 49 int result = 0; 50 for (int i = 0; i < NTHREADS; i++) { 51 pthread_join(threads[i], NULL); 52 result += args[i].count; 53 } 54 55 return result; 56 } 57 58 void set_nonprime(unsigned char *table, int n) { 59 table[INDEX(n)] &= ~MASK(n); 60 } 61 62 bool isprime(const unsigned char *table, int n) { 63 return table[INDEX(n)] & MASK(n); 64 } 65 66 void generate_primes(unsigned char *table, void (*log)(const char *)) { 67 memset(table, 0xFF, TABLESIZE); 68 set_nonprime(table, 0); 69 set_nonprime(table, 1); 70 for (long long i = 0; i < MAX_PRIME; i++) { 71 if (i % 100000000 == 0 && log != NULL) { 72 char msg[200]; 73 sprintf(msg, 74 "Could not read table of primes, generating it\n" 75 "Done %llu / %d", i, MAX_PRIME); 76 log(msg); 77 } 78 if (!isprime(table, i)) 79 continue; 80 for (long long int j = 2*i; j < MAX_PRIME; j += i) 81 set_nonprime(table, j); 82 } 83 } 84 85 void *pthread_routine(void *arg) { 86 struct interval *interval = arg; 87 88 interval->count = 0; 89 for (int i = interval->low; i < interval->high; i++) 90 if (isprime(primes_table, i)) 91 interval->count++; 92 93 return NULL; 94 }