PyORAM/src/_cffi_src/virtual_heap_helper_build.py

   1 import cffi
   2
   3 #
   4 # C functions that speed up commonly
   5 # executed heap calculations in tree-based
   6 # orams
   7 #
   8
   9 ffi = cffi.FFI()
  10 ffi.cdef(
  11 """
  12 int calculate_bucket_level(unsigned int k,
  13                            unsigned long long b);
  14 int calculate_last_common_level(unsigned int k,
  15                                 unsigned long long b1,
  16                                 unsigned long long b2);
  17 """)
  18
  19 ffi.set_source("pyoram.util._virtual_heap_helper",
  20 """
  21 #include <stdio.h>
  22 #include <stdlib.h>
  23
  24 int calculate_bucket_level(unsigned int k,
  25                            unsigned long long b)
  26 {
  27    unsigned int h;
  28    unsigned long long pow;
  29    if (k == 2) {
  30       // This is simply log2floor(b+1)
  31       h = 0;
  32       b += 1;
  33       while (b >>= 1) {++h;}
  34       return h;
  35    }
  36    b = (k - 1) * (b + 1) + 1;
  37    h = 0;
  38    pow = k;
  39    while (pow < b) {++h; pow *= k;}
  40    return h;
  41 }
  42
  43 int calculate_last_common_level(unsigned int k,
  44                                 unsigned long long b1,
  45                                 unsigned long long b2)
  46 {
  47    int level1, level2;
  48    level1 = calculate_bucket_level(k, b1);
  49    level2 = calculate_bucket_level(k, b2);
  50    if (level1 != level2) {
  51       if (level1 > level2) {
  52          while (level1 != level2) {
  53             b1 = (b1 - 1)/k;
  54             --level1;
  55          }
  56       }
  57       else {
  58          while (level2 != level1) {
  59             b2 = (b2 - 1)/k;
  60             --level2;
  61          }
  62       }
  63    }
  64    while (b1 != b2) {
  65       b1 = (b1 - 1)/k;
  66       b2 = (b2 - 1)/k;
  67       --level1;
  68    }
  69    return level1;
  70 }
  71 """)
  72
  73 if __name__ == "__main__":
  74     ffi.compile()