TestForest.java 2.4 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182
  1. package oram;
  2. import java.math.BigInteger;
  3. import crypto.Crypto;
  4. import util.Util;
  5. public class TestForest {
  6. public static void main(String[] args) {
  7. Metadata md = new Metadata();
  8. // Forest forest = new Forest(md);
  9. Forest forest = Forest.readFromFile(md.getDefaultForestFileName());
  10. int tau = md.getTau();
  11. int addrBits = md.getAddrBits();
  12. long numRecords = md.getNumInsertRecords();
  13. int numTrees = forest.getNumTrees();
  14. long numTests = 100;
  15. // long numTests = numRecords;
  16. for (long n = 0; n < numTests; n++) {
  17. // address of record we want to test
  18. long testAddr = Util.nextLong(numRecords, Crypto.sr);
  19. // long testAddr = n;
  20. long L = 0;
  21. long outRecord = 0;
  22. for (int i = 0; i < numTrees; i++) {
  23. // set address of tuple and index of label for searching
  24. long N;
  25. int indexN;
  26. if (i == 0) {
  27. N = 0;
  28. indexN = Util.getSubBits(BigInteger.valueOf(testAddr), addrBits, addrBits - tau).intValue();
  29. } else if (i < numTrees - 1) {
  30. N = Util.getSubBits(testAddr, addrBits, addrBits - i * tau);
  31. indexN = Util.getSubBits(BigInteger.valueOf(testAddr), addrBits - i * tau,
  32. Math.max(addrBits - (i + 1) * tau, 0)).intValue();
  33. } else {
  34. N = testAddr;
  35. indexN = 0;
  36. }
  37. // get the path buckets and search for the tuple
  38. Tree tree = forest.getTree(i);
  39. Bucket[] pathBuckets = tree.getBucketsOnPath(L);
  40. Tuple targetTuple = null;
  41. if (i == 0) {
  42. targetTuple = pathBuckets[0].getTuple(0);
  43. } else {
  44. for (int j = 0; j < pathBuckets.length; j++) {
  45. for (int k = 0; k < pathBuckets[j].getNumTuples(); k++) {
  46. Tuple tuple = pathBuckets[j].getTuple(k);
  47. if (tuple.getF()[0] == 1 && new BigInteger(1, tuple.getL()).longValue() == L
  48. && new BigInteger(1, tuple.getN()).longValue() == N) {
  49. targetTuple = tuple;
  50. break;
  51. }
  52. }
  53. if (targetTuple != null)
  54. break;
  55. }
  56. }
  57. // retrieve the next label or record from the tuple
  58. if (i < numTrees - 1)
  59. L = new BigInteger(1,
  60. targetTuple.getSubA(indexN * tree.getAlBytes(), (indexN + 1) * tree.getAlBytes()))
  61. .longValue();
  62. else
  63. outRecord = new BigInteger(1, targetTuple.getA()).longValue();
  64. }
  65. // verify correctness
  66. if (testAddr == outRecord)
  67. System.out.println("Success on address " + BigInteger.valueOf(testAddr).toString(2));
  68. else
  69. System.err.println("Error on address " + BigInteger.valueOf(testAddr).toString(2));
  70. }
  71. }
  72. }