aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/include/ndpi_api.h14
-rw-r--r--src/include/ndpi_typedefs.h6
-rw-r--r--src/lib/Makefile.in2
-rw-r--r--src/lib/ndpi_analyze.c117
-rw-r--r--src/lib/ndpi_utils.c16
5 files changed, 151 insertions, 4 deletions
diff --git a/src/include/ndpi_api.h b/src/include/ndpi_api.h
index 258c09ae8..ce124bbf6 100644
--- a/src/include/ndpi_api.h
+++ b/src/include/ndpi_api.h
@@ -1747,7 +1747,8 @@ extern "C" {
/* ******************************* */
u_int32_t ndpi_crc32(const void* data, size_t n_bytes);
-
+ u_int32_t ndpi_nearest_power_of_two(u_int32_t x);
+
/* ******************************* */
int ndpi_des_init(struct ndpi_des_struct *des, double alpha, double beta, float significance);
@@ -1793,7 +1794,7 @@ extern "C" {
/* ******************************* */
- /* HyperLogLog cardinality estimator */
+ /* HyperLogLog cardinality estimator [count unique items] */
/* Memory lifecycle */
int ndpi_hll_init(struct ndpi_hll *hll, u_int8_t bits);
@@ -1809,6 +1810,15 @@ extern "C" {
/* ******************************* */
+ /* Count-Min Sketch [count how many times a value has been observed] */
+
+ struct ndpi_cm_sketch *ndpi_cm_sketch_init(u_int16_t depth);
+ void ndpi_cm_sketch_add(struct ndpi_cm_sketch *sketch, u_int32_t element);
+ u_int32_t ndpi_cm_sketch_count(struct ndpi_cm_sketch *sketch, u_int32_t element);
+ void ndpi_cm_sketch_destroy(struct ndpi_cm_sketch *sketch);
+
+ /* ******************************* */
+
int ndpi_init_bin(struct ndpi_bin *b, enum ndpi_bin_family f, u_int16_t num_bins);
void ndpi_free_bin(struct ndpi_bin *b);
struct ndpi_bin* ndpi_clone_bin(struct ndpi_bin *b);
diff --git a/src/include/ndpi_typedefs.h b/src/include/ndpi_typedefs.h
index e3a649892..373a704da 100644
--- a/src/include/ndpi_typedefs.h
+++ b/src/include/ndpi_typedefs.h
@@ -1897,6 +1897,12 @@ struct ndpi_hll {
u_int8_t *registers;
};
+struct ndpi_cm_sketch {
+ u_int16_t num_hashes; /* depth: Number of hash tables */
+ u_int32_t num_hash_buckets; /* Number pf nuckets of each hash */
+ u_int32_t *tables;
+};
+
/* **************************************** */
enum ndpi_bin_family {
diff --git a/src/lib/Makefile.in b/src/lib/Makefile.in
index 7ed7fabd6..7867f5424 100644
--- a/src/lib/Makefile.in
+++ b/src/lib/Makefile.in
@@ -41,7 +41,7 @@ endif
BUILD_MINGW = @BUILD_MINGW@
ifeq ($(OS),Darwin)
-CC=clang
+CC=clang -fno-color-diagnostics
SONAME_FLAG=
else
ifneq ($(BUILD_MINGW),)
diff --git a/src/lib/ndpi_analyze.c b/src/lib/ndpi_analyze.c
index d9828ad62..62d14fdd4 100644
--- a/src/lib/ndpi_analyze.c
+++ b/src/lib/ndpi_analyze.c
@@ -266,7 +266,7 @@ void ndpi_data_print_window_values(struct ndpi_analyze_struct *s) {
for(i=0; i<n; i++)
printf("[%u: %" PRIu64 "]", i, s->values[i]);
-
+
printf("\n");
}
}
@@ -1715,3 +1715,118 @@ u_int32_t ndpi_crc32(const void* data, size_t n_bytes) {
__crc32(data, n_bytes, &crc);
return crc;
}
+
+/* ********************************************************************************* */
+/* ********************************************************************************* */
+
+/*
+ Count-Min Sketch: Memory Usage
+
+ https://florian.github.io/count-min-sketch/
+ https://medium.com/@nehasingh18.9/count-min-sketch-for-beginners-f1e441bbe7a4
+ https://sites.google.com/site/countminsketch/code
+
+ [Depth: 8][Total memory: 1040]
+ [Depth: 16][Total memory: 2064]
+ [Depth: 32][Total memory: 4112]
+ [Depth: 64][Total memory: 8208]
+ [Depth: 256][Total memory: 32784]
+ [Depth: 512][Total memory: 65552]
+ [Depth: 1024][Total memory: 131088]
+ [Depth: 2048][Total memory: 262160]
+ [Depth: 4096][Total memory: 524304]
+ [Depth: 8192][Total memory: 1048592]
+*/
+
+#define NDPI_COUNT_MIN_SKETCH_NUM_BUCKETS 1024
+
+// #define DEBUG
+
+struct ndpi_cm_sketch *ndpi_cm_sketch_init(u_int16_t num_hashes) {
+#ifdef DEBUG
+ u_int32_t tot_mem;
+#endif
+ u_int32_t len;
+ struct ndpi_cm_sketch *sketch;
+
+ len = sizeof(struct ndpi_cm_sketch);
+ sketch = (struct ndpi_cm_sketch*)ndpi_malloc(len);
+
+ if(!sketch)
+ return(NULL);
+
+#ifdef DEBUG
+ tot_mem = len;
+#endif
+
+ if(num_hashes < 2) num_hashes = 2;
+
+ sketch->num_hashes = num_hashes;
+ sketch->num_hash_buckets = num_hashes * NDPI_COUNT_MIN_SKETCH_NUM_BUCKETS;
+ sketch->num_hash_buckets = ndpi_nearest_power_of_two(sketch->num_hash_buckets)-1,
+
+ len = num_hashes * NDPI_COUNT_MIN_SKETCH_NUM_BUCKETS * sizeof(u_int32_t);
+ sketch->tables = (u_int32_t*)ndpi_calloc(num_hashes, NDPI_COUNT_MIN_SKETCH_NUM_BUCKETS * sizeof(u_int32_t));
+
+#ifdef DEBUG
+ tot_mem += len;
+#endif
+
+#ifdef DEBUG
+ printf("[Num_Hashes: %u][Total memory: %u]\n", num_hashes, tot_mem);
+#endif
+
+ if(!sketch->tables) {
+ ndpi_free(sketch);
+ return(NULL);
+ }
+
+ return(sketch);
+}
+
+/* ********************************************************************************* */
+
+#define ndpi_simple_hash(value, seed) (value * seed)
+
+/* ********************************************************************************* */
+
+void ndpi_cm_sketch_add(struct ndpi_cm_sketch *sketch, u_int32_t element) {
+ u_int32_t idx;
+
+ for(idx = 1; idx <= sketch->num_hashes; idx++) {
+ u_int32_t hashval = ndpi_simple_hash(element, idx) & sketch->num_hash_buckets;
+
+ sketch->tables[hashval]++;
+
+#ifdef DEBUG
+ printf("ndpi_add_sketch_add() [hash: %d][num_hash_buckets: %u][hashval: %d][value: %d]\n",
+ idx, sketch->num_hash_buckets, hashval, sketch->tables[hashval]);
+#endif
+ }
+}
+
+/* ********************************************************************************* */
+
+u_int32_t ndpi_cm_sketch_count(struct ndpi_cm_sketch *sketch, u_int32_t element) {
+ u_int32_t min_value = INT_MAX, idx;
+
+ for(idx = 1; idx <= sketch->num_hashes; idx++) {
+ u_int32_t hashval = ndpi_simple_hash(element, idx) & sketch->num_hash_buckets;
+
+#ifdef DEBUG
+ printf("ndpi_add_sketch_add() [hash: %d][num_hash_buckets: %u][hashval: %d][value: %d]\n",
+ idx, sketch->num_hash_buckets, hashval, sketch->tables[hashval]);
+#endif
+
+ min_value = ndpi_min(min_value, sketch->tables[hashval]);
+ }
+
+ return(min_value);
+}
+
+/* ********************************************************************************* */
+
+void ndpi_cm_sketch_destroy(struct ndpi_cm_sketch *sketch) {
+ ndpi_free(sketch->tables);
+ ndpi_free(sketch);
+}
diff --git a/src/lib/ndpi_utils.c b/src/lib/ndpi_utils.c
index bd7c922ad..75201e55e 100644
--- a/src/lib/ndpi_utils.c
+++ b/src/lib/ndpi_utils.c
@@ -2989,3 +2989,19 @@ char* ndpi_intoav4(unsigned int addr, char* buf, u_int16_t bufLen) {
return(cp);
}
+/* ******************************************* */
+
+/* Find the nearest (>=) value of x */
+u_int32_t ndpi_nearest_power_of_two(u_int32_t x) {
+ x--;
+
+ x |= x >> 1;
+ x |= x >> 2;
+ x |= x >> 4;
+ x |= x >> 8;
+ x |= x >> 16;
+
+ x++;
+ return(x);
+}
+
Powered by cgit, Themed by Ted Yin.