Primes in a range

From ab0db69a7b11ba1a9dc52d50c94e9e321b70ebf0 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Fri, 6 Jun 2025 09:13:54 +0200 Subject: Added example 6 --- 06_storage/build.sh | 9 +++++ 06_storage/index.html | 19 ++++++++++ 06_storage/init_idbfs.js | 16 +++++++++ 06_storage/mime.txt | 1 + 06_storage/primes.c | 94 ++++++++++++++++++++++++++++++++++++++++++++++++ 06_storage/primes.h | 12 +++++++ 06_storage/run-server.sh | 6 ++++ 06_storage/script.mjs | 20 +++++++++++ 06_storage/storage.c | 28 +++++++++++++++ 06_storage/storage.h | 7 ++++ 06_storage/worker.mjs | 22 ++++++++++++ 11 files changed, 234 insertions(+) create mode 100755 06_storage/build.sh create mode 100644 06_storage/index.html create mode 100644 06_storage/init_idbfs.js create mode 100644 06_storage/mime.txt create mode 100644 06_storage/primes.c create mode 100644 06_storage/primes.h create mode 100755 06_storage/run-server.sh create mode 100644 06_storage/script.mjs create mode 100644 06_storage/storage.c create mode 100644 06_storage/storage.h create mode 100644 06_storage/worker.mjs (limited to '06_storage') diff --git a/06_storage/build.sh b/06_storage/build.sh new file mode 100755 index 0000000..a477cc5 --- /dev/null +++ b/06_storage/build.sh @@ -0,0 +1,9 @@ +#!/bin/sh + +mkdir -p build +emcc -sEXPORTED_FUNCTIONS=_primes_in_range -sMODULARIZE -sEXPORT_NAME=Primes \ + -pthread -sPTHREAD_POOL_SIZE=16 \ + -sEXPORTED_RUNTIME_METHODS=addFunction,UTF8ToString \ + -sALLOW_TABLE_GROWTH \ + -lidbfs.js --pre-js init_idbfs.js -sINITIAL_MEMORY=272629760 \ + -o build/primes.mjs primes.c storage.c diff --git a/06_storage/index.html b/06_storage/index.html new file mode 100644 index 0000000..a4ba674 --- /dev/null +++ b/06_storage/index.html @@ -0,0 +1,19 @@ + + + + + + Primes in a range + + + + + Lower bound (included)
+ x
+ Upper bound (excluded)
+
+
+

+ + + diff --git a/06_storage/init_idbfs.js b/06_storage/init_idbfs.js new file mode 100644 index 0000000..82483f4 --- /dev/null +++ b/06_storage/init_idbfs.js @@ -0,0 +1,16 @@ +Module['preRun'] = [ + async () => { + const dir = "/assets"; + + FS.mkdir(dir); + FS.mount(IDBFS, { autoPersist: true }, dir); + + Module.fileSystemLoaded = new Promise((resolve, reject) => { + FS.syncfs(true, (err) => { + if (err) reject(err); + else resolve(true); + }); + }); + + } +]; diff --git a/06_storage/mime.txt b/06_storage/mime.txt new file mode 100644 index 0000000..6a9a425 --- /dev/null +++ b/06_storage/mime.txt @@ -0,0 +1 @@ +text/javascript mjs diff --git a/06_storage/primes.c b/06_storage/primes.c new file mode 100644 index 0000000..4a17e8d --- /dev/null +++ b/06_storage/primes.c @@ -0,0 +1,94 @@ +#include +#include +#include +#include + +#include "primes.h" +#include "storage.h" + +#define NTHREADS 16 +#define INDEX(i) ((i) >> 3) +#define MASK(i) (unsigned char)(1 << ((i) % 8)) + +unsigned char primes_table[TABLESIZE]; +struct interval { int low; int high; int count; }; + +void *pthread_routine(void *); +int primes_in_range(int, int, void (*)(const char *)); +void set_nonprime(unsigned char *, int); +bool isprime(const unsigned char *, int); + +int primes_in_range(int low, int high, void (*log)(const char *)) { + static bool table_is_loaded = false; + + pthread_t threads[NTHREADS]; + struct interval args[NTHREADS]; + + if (low < 0 || high < low) + return 0; + + if (!table_is_loaded) { + if (!read_table(primes_table)) { + generate_primes(primes_table, log); + if (!store_table(primes_table)) + log("Error storing table to indexed DB"); + } + + table_is_loaded = true; + } + + int interval_size = (high-low)/NTHREADS + 1; + for (int i = 0; i < NTHREADS; i++) { + args[i].low = low + i*interval_size; + args[i].high = args[i].low + interval_size; + pthread_create(&threads[i], NULL, pthread_routine, &args[i]); + } + + log("All threads have started, computing..."); + + int result = 0; + for (int i = 0; i < NTHREADS; i++) { + pthread_join(threads[i], NULL); + result += args[i].count; + } + + return result; +} + +void set_nonprime(unsigned char *table, int n) { + table[INDEX(n)] &= ~MASK(n); +} + +bool isprime(const unsigned char *table, int n) { + return table[INDEX(n)] & MASK(n); +} + +void generate_primes(unsigned char *table, void (*log)(const char *)) { + memset(table, 0xFF, TABLESIZE); + set_nonprime(table, 0); + set_nonprime(table, 1); + for (long long i = 0; i < MAX_PRIME; i++) { + if (i % 100000000 == 0 && log != NULL) { + char msg[200]; + sprintf(msg, + "Could not read table of primes, generating it\n" + "Done %llu / %d", i, MAX_PRIME); + log(msg); + } + if (!isprime(table, i)) + continue; + for (long long int j = 2*i; j < MAX_PRIME; j += i) + set_nonprime(table, j); + } +} + +void *pthread_routine(void *arg) { + struct interval *interval = arg; + + interval->count = 0; + for (int i = interval->low; i < interval->high; i++) + if (isprime(primes_table, i)) + interval->count++; + + return NULL; +} diff --git a/06_storage/primes.h b/06_storage/primes.h new file mode 100644 index 0000000..d9006f7 --- /dev/null +++ b/06_storage/primes.h @@ -0,0 +1,12 @@ +#ifndef PRIMES_H +#define PRIMES_H + +#include + +#define MAX_PRIME INT_MAX +#define TABLESIZE (1 << 28) + +int primes_in_range(int, int, void (*)(const char *)); +void generate_primes(unsigned char *, void (*)(const char *)); + +#endif diff --git a/06_storage/run-server.sh b/06_storage/run-server.sh new file mode 100755 index 0000000..3a526f3 --- /dev/null +++ b/06_storage/run-server.sh @@ -0,0 +1,6 @@ +#!/bin/sh + +darkhttpd . \ + --mimetypes mime.txt \ + --header 'Cross-Origin-Opener-Policy: same-origin' \ + --header 'Cross-Origin-Embedder-Policy: require-corp' diff --git a/06_storage/script.mjs b/06_storage/script.mjs new file mode 100644 index 0000000..1238371 --- /dev/null +++ b/06_storage/script.mjs @@ -0,0 +1,20 @@ +var aInput = document.getElementById("aInput"); +var bInput = document.getElementById("bInput"); +var button = document.getElementById("goButton"); +var resultText = document.getElementById("resultText"); + +var worker = new Worker("./worker.mjs", { type: "module" }); + +button.addEventListener("click", () => worker.postMessage({ + a: Number(aInput.value), + b: Number(bInput.value) +})); + +worker.onmessage = (e) => { + if (e.data.type == "response") + resultText.innerText = e.data.message; + else if (e.data.type == "readySignal") { + button.disabled = false; + button.innerText = "Compute" + } +}; diff --git a/06_storage/storage.c b/06_storage/storage.c new file mode 100644 index 0000000..7542022 --- /dev/null +++ b/06_storage/storage.c @@ -0,0 +1,28 @@ +#include +#include + +#include "primes.h" + +#define FILENAME "/assets/primes_table" + +bool read_table(unsigned char *table) { + FILE *f = fopen(FILENAME, "rb"); + if (f == NULL) + return false; + + int b = fread(table, TABLESIZE, 1, f); + fclose(f); + + return b == 1; +} + +bool store_table(const unsigned char *table) { + FILE *f = fopen(FILENAME, "wb"); + if (f == NULL) + return false; + + int b = fwrite(table, TABLESIZE, 1, f); + fclose(f); + + return b == 1; +} diff --git a/06_storage/storage.h b/06_storage/storage.h new file mode 100644 index 0000000..ff0afae --- /dev/null +++ b/06_storage/storage.h @@ -0,0 +1,7 @@ +#ifndef STORAGE_H +#define STORAGE_H + +bool read_table(unsigned char *); +bool store_table(const unsigned char *); + +#endif diff --git a/06_storage/worker.mjs b/06_storage/worker.mjs new file mode 100644 index 0000000..929fabc --- /dev/null +++ b/06_storage/worker.mjs @@ -0,0 +1,22 @@ +import Primes from "./build/primes.mjs"; + +var primes = await Primes(); + +const logPtr = primes.addFunction((cstr) => { + const str = primes.UTF8ToString(cstr); + console.log(str); + postMessage({ message: str }); +}, "vp"); + +onmessage = (e) => { + const count = primes._primes_in_range(e.data.a, e.data.b, logPtr); + postMessage({ + type: "response", + message: "There are " + count + " primes between " + + e.data.a + " and " + e.data.b + }); +}; + +primes.fileSystemLoaded.then(() => { + postMessage({ type: "readySignal" }); +}); -- cgit v1.3