PyORAm

[iotcloud.git] / PyORAM / src / _cffi_src / virtual_heap_helper_build.py

diff --git a/PyORAM/src/_cffi_src/virtual_heap_helper_build.py b/PyORAM/src/_cffi_src/virtual_heap_helper_build.py
new file mode 100644 (file)
index 0000000..72bfc1d
--- /dev/null
+++ b/PyORAM/src/_cffi_src/virtual_heap_helper_build.py
@@ -0,0 +1,74 @@
+import cffi
+
+#
+# C functions that speed up commonly
+# executed heap calculations in tree-based
+# orams
+#
+
+ffi = cffi.FFI()
+ffi.cdef(
+"""
+int calculate_bucket_level(unsigned int k,
+                           unsigned long long b);
+int calculate_last_common_level(unsigned int k,
+                                unsigned long long b1,
+                                unsigned long long b2);
+""")
+
+ffi.set_source("pyoram.util._virtual_heap_helper",
+"""
+#include <stdio.h>
+#include <stdlib.h>
+
+int calculate_bucket_level(unsigned int k,
+                           unsigned long long b)
+{
+   unsigned int h;
+   unsigned long long pow;
+   if (k == 2) {
+      // This is simply log2floor(b+1)
+      h = 0;
+      b += 1;
+      while (b >>= 1) {++h;}
+      return h;
+   }
+   b = (k - 1) * (b + 1) + 1;
+   h = 0;
+   pow = k;
+   while (pow < b) {++h; pow *= k;}
+   return h;
+}
+
+int calculate_last_common_level(unsigned int k,
+                                unsigned long long b1,
+                                unsigned long long b2)
+{
+   int level1, level2;
+   level1 = calculate_bucket_level(k, b1);
+   level2 = calculate_bucket_level(k, b2);
+   if (level1 != level2) {
+      if (level1 > level2) {
+         while (level1 != level2) {
+            b1 = (b1 - 1)/k;
+            --level1;
+         }
+      }
+      else {
+         while (level2 != level1) {
+            b2 = (b2 - 1)/k;
+            --level2;
+         }
+      }
+   }
+   while (b1 != b2) {
+      b1 = (b1 - 1)/k;
+      b2 = (b2 - 1)/k;
+      --level1;
+   }
+   return level1;
+}
+""")
+
+if __name__ == "__main__":
+    ffi.compile()