Implemented Count-Min Sketch [count how many times a value has been observed]

- ndpi_cm_sketch_init()
- ndpi_cm_sketch_add()
- ndpi_cm_sketch_count()
- ndpi_cm_sketch_destroy()

1 files changed, 16 insertions, 0 deletions

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);
+}
+