[HICN-272] new hicn-light fib

Change-Id: Id0f13d6aebecc724556a80d3b3d57e8e06b6b262
Signed-off-by: michele papalini <micpapal@cisco.com>

5 files changed, 89 insertions, 108 deletions

diff --git a/hicn-light/src/hicn/core/mapMe.c b/hicn-light/src/hicn/core/mapMe.c
index 865841f67..0f86dfd7e 100644
--- a/hicn-light/src/hicn/core/mapMe.c
+++ b/hicn-light/src/hicn/core/mapMe.c
@@ -583,7 +583,7 @@ static bool mapMe_onSpecialInterest(const MapMe *mapme,
 #else
     fibEntry = fibEntry_Create(name, fwdStrategy);
 #endif /* WITH_POLICY */
-    FibEntry *lpm = fib_LPM(fib, name);
+    FibEntry *lpm = fib_MatchName(fib, name);
     mapMe_CreateTFIB(fibEntry);
     fib_Add(fib, fibEntry);
     if (!lpm) {
@@ -755,7 +755,7 @@ void mapMe_onSpecialInterestAck(const MapMe *mapme, const uint8_t *msgBuffer,
 
   const Name * name =
       name_CreateFromPacket(msgBuffer, MessagePacketType_ContentObject);
-  name_setLen(name, prefix->len);
+  name_setLen((Name*) name, prefix->len);
   char * name_str = name_ToString(name);
   INFO(mapme, "[MAP-Me] Received ack for name prefix=%s seq=%d on conn id=%d",
           name_str, params->seq, conn_in_id);
diff --git a/hicn-light/src/hicn/core/name.c b/hicn-light/src/hicn/core/name.c
index 8cf8dacbc..f4ea7dbca 100644
--- a/hicn-light/src/hicn/core/name.c
+++ b/hicn-light/src/hicn/core/name.c
@@ -162,6 +162,24 @@ Name *name_Acquire(const Name *original) {
   return copy;
 }
 
+Name *name_Copy(const Name *original) {
+  parcAssertNotNull(original, "Parameter must be non-null");
+  Name *copy = parcMemory_AllocateAndClear(sizeof(Name));
+  parcAssertNotNull(copy, "parcMemory_AllocateAndClear(%zu) returned NULL",
+                    sizeof(Name));
+
+  copy->content_name = nameBitvector_Copy(original->content_name);
+  copy->segment = original->segment;
+  copy->name_hash = original->name_hash;
+
+  copy->refCountPtr = parcMemory_Allocate(sizeof(unsigned));
+  parcAssertNotNull(copy->refCountPtr, "parcMemory_Allocate(%zu) returned NULL",
+                    sizeof(unsigned));
+  *copy->refCountPtr = 1;
+
+  return copy;
+}
+
 uint32_t name_HashCode(const Name *name) {
   parcAssertNotNull(name, "Parameter must be non-null");
   return name->name_hash;
@@ -211,13 +229,6 @@ int name_Compare(const Name *a, const Name *b) {
   }
 }
 
-bool name_StartsWith(const Name *name, const Name *prefix) {
-  parcAssertNotNull(name, "Parameter name must be non-null");
-  parcAssertNotNull(prefix, "Parameter prefix must be non-null");
-
-  return nameBitvector_StartsWith(name->content_name, prefix->content_name);
-}
-
 char *name_ToString(const Name *name) {
   char *output = malloc(128);
 
@@ -231,8 +242,9 @@ char *name_ToString(const Name *name) {
   return output;
 }
 
-void name_setLen(const Name *name, uint8_t len) {
+void name_setLen(Name *name, uint8_t len) {
   nameBitvector_setLen(name->content_name, len);
+  name->name_hash = _computeHash(name);
 }
 
 #ifdef WITH_POLICY
diff --git a/hicn-light/src/hicn/core/name.h b/hicn-light/src/hicn/core/name.h
index 4eb80cf36..f2ae1f64e 100644
--- a/hicn-light/src/hicn/core/name.h
+++ b/hicn-light/src/hicn/core/name.h
@@ -48,6 +48,11 @@ void name_Release(Name **namePtr);
 Name *name_Acquire(const Name *original);
 
 /**
+ * returns a copy of the name
+ */
+Name *name_Copy(const Name *original);
+
+/**
  * A hash value for use in hash tables
  *
  */
@@ -71,17 +76,6 @@ bool name_Equals(const Name *a, const Name *b);
 int name_Compare(const Name *a, const Name *b);
 
 /**
- * @function metsName_StartsWith
- * @abstract Checks if name starts with prefix
- * @discussion
- *   Byte-by-byte prefix comparison
- *
- * @return True if the name is equal to or begins with prefix
- */
-
-bool name_StartsWith(const Name *name, const Name *prefix);
-
-/**
  * return the name in string format (bitvector + segment number)
  *
  */
@@ -93,7 +87,7 @@ char *name_ToString(const Name *name);
  * @param [in] message - Interest message
  * @param [in] len - Name length
  */
-void name_setLen(const Name *name, uint8_t len);
+void name_setLen(Name *name, uint8_t len);
 
 /**
  * Creates a name from a Address
diff --git a/hicn-light/src/hicn/core/nameBitvector.c b/hicn-light/src/hicn/core/nameBitvector.c
index 8078778e3..ad6884d02 100644
--- a/hicn-light/src/hicn/core/nameBitvector.c
+++ b/hicn-light/src/hicn/core/nameBitvector.c
@@ -27,24 +27,21 @@
 
 #include <hicn/utils/commands.h>
 
-#define BLOCKS 2
+#define NAME_LEN 2
 
-const uint64_t BLOCK_SIZE = 64;
+const uint64_t BV_SIZE = 64;
 const uint64_t WIDTH = 128;
-const uint64_t BLOCK_ONE = 0x1;
-
-// the bits are encoded in the following order:
-// 00100101001---101010  00100011---110100100
-// [bits[0] (uint64_t)]  [bits[1] (uint64_t)]
-// ^                  ^  ^                  ^
-// 0                 63 64                127
-// address  2200::0011 is encoded as:
-//   1000 1000 0000 0010 00000 ....0100 0100
-//   ^                                     ^
-//   0                                   127
+const uint64_t ONE = 0x1;
+
+// address b000:0000:0000:0001:c000:0000:0000:0001 is encodend as follow
+// [bits[0] uint64_t       ] [bits[1] unit64_t       ]
+// ^                       ^ ^                       ^
+// 63                      0 127                     64
+// [1000 0000 ... 0000 1101] [1000 0000 ... 0000 0011] //binary
+//    1                  b     1                  c    //hex
 
 struct name_bitvector {
-  uint64_t bits[BLOCKS];
+  uint64_t bits[NAME_LEN];
   uint8_t len;
   uint8_t IPversion;
 };
@@ -62,11 +59,11 @@ NameBitvector *nameBitvector_CreateFromInAddr(uint32_t addr, uint8_t len) {
   uint8_t addr_3 = (addr & 0x0000ff00) >> 8;
   uint8_t addr_4 = (addr & 0x000000ff);
 
-  bitvector->bits[1] = (bitvector->bits[1] | addr_4) << 8;
-  bitvector->bits[1] = (bitvector->bits[1] | addr_3) << 8;
-  bitvector->bits[1] = (bitvector->bits[1] | addr_2) << 8;
-  bitvector->bits[1] = (bitvector->bits[1] | addr_1);
-  bitvector->bits[1] = bitvector->bits[1] << 32;
+  bitvector->bits[0] = (bitvector->bits[0] | addr_4) << 8;
+  bitvector->bits[0] = (bitvector->bits[0] | addr_3) << 8;
+  bitvector->bits[0] = (bitvector->bits[0] | addr_2) << 8;
+  bitvector->bits[0] = (bitvector->bits[0] | addr_1);
+  bitvector->bits[0] = bitvector->bits[0] << 32;
 
   bitvector->len = len;
 
@@ -87,11 +84,11 @@ NameBitvector *nameBitvector_CreateFromIn6Addr(struct in6_addr *addr,
   bitvector->bits[1] = 0;
 
   for (int i = 0; i < 8; ++i) {
-    bitvector->bits[1] = (bitvector->bits[1] << 8) | addr->s6_addr[i];
+    bitvector->bits[0] = (bitvector->bits[0] << 8) | addr->s6_addr[i];
   }
 
   for (int i = 8; i < 16; ++i) {
-    bitvector->bits[0] = (bitvector->bits[0] << 8) | addr->s6_addr[i];
+    bitvector->bits[1] = (bitvector->bits[1] << 8) | addr->s6_addr[i];
   }
 
   bitvector->len = len;
@@ -191,38 +188,13 @@ int nameBitvector_Compare(const NameBitvector *a, const NameBitvector *b) {
   }
 }
 
-bool nameBitvector_StartsWith(const NameBitvector *name,
-                              const NameBitvector *prefix) {
-  parcAssertNotNull(name, "name cannot be NULL");
-  parcAssertNotNull(prefix, "prefix cannot be NULL");
-  parcAssertTrue(prefix->len > 0, "prefix length can not be 0");
-
-  if (prefix->len > BLOCK_SIZE)
-    return (name->bits[1] == prefix->bits[1]) &&
-           ((name->bits[0] ^ prefix->bits[0]) >>
-                (BLOCK_SIZE - (prefix->len - BLOCK_SIZE)) ==
-            0);
-
-  return ((name->bits[1] ^ prefix->bits[1]) >> (BLOCK_SIZE - prefix->len) == 0);
-}
-
-bool nameBitvector_testBit(const NameBitvector *name, uint8_t pos) {
-  if (pos == WIDTH) pos = 127;
-
-  uint8_t final_pos = (uint8_t)(WIDTH - name->len);
-
-  // the bit to test is inside the name/prefix len
-  if (pos > final_pos) {
-    return (name->bits[pos / BLOCK_SIZE] & (BLOCK_ONE << (pos % BLOCK_SIZE)));
-  }
+int nameBitvector_testBit(const NameBitvector *name, uint8_t pos, bool *bit) {
+  if(pos >= name->len  || pos > (WIDTH -1))
+    return -1;
 
-  // the bit to test is outside the name/prefix len
-  if (pos < final_pos) {
-    return false;
-  }
+  *bit = (name->bits[pos / BV_SIZE] & (ONE << ((BV_SIZE - 1) - (pos % BV_SIZE))));
 
-  // pos is equal to the name/prefix len
-  return true;
+  return 0;
 }
 
 uint64_t _diff_bit_log2(uint64_t val) {
@@ -257,31 +229,38 @@ uint64_t _diff_bit_log2(uint64_t val) {
   return result;
 }
 
-uint8_t nameBitvector_firstDiff(const NameBitvector *a,
-                                const NameBitvector *b) {
-  uint8_t res = 0;
-  uint64_t diff = a->bits[1] ^ b->bits[1];
-  if (diff)
-    res = (uint8_t)(64 + _diff_bit_log2(diff));
-  else
-    res = (uint8_t)_diff_bit_log2(a->bits[0] ^ b->bits[0]);
-
-  // res is computed over the bitvector which is composed by 128 bit all the
-  // times however the prefixes may be diffrent just because the have different
-  // lengths example: prefix 1: 0::/30 prefix 2: 0::/20 at this point of the
-  // function res would be 0 since both the bitvectors are composed by 0s but
-  // the function will return 127-20, which is the position at which the two
-  // prefix are different, since prefix 2 has only 20 bits
-
-  uint8_t len_diff;
+uint32_t nameBitvector_lpm(const NameBitvector *a,
+                          const NameBitvector *b) {
+  uint32_t limit;
+  uint32_t prefix_len;
   if (a->len < b->len)
-    len_diff = (uint8_t)(WIDTH - a->len);
+    limit = a->len;
   else
-    len_diff = (uint8_t)(WIDTH - b->len);
+    limit = b->len;
+
+  uint64_t diff = a->bits[0] ^ b->bits[0];
+  if(diff){
+    prefix_len = BV_SIZE - (_diff_bit_log2(diff) + 1);
+    //printf("if 1 diff = %lu plen = %d\n", diff, prefix_len);
+  }else{
+    prefix_len = BV_SIZE;
+    diff = a->bits[1] ^ b->bits[1];
+    if(diff){
+      prefix_len +=  (BV_SIZE - (_diff_bit_log2(diff) + 1));
+      //printf("if 2 diff = %lu plen = %d\n", diff, prefix_len);
+    }else{
+      prefix_len += BV_SIZE;
+    }
+  }
 
-  if (len_diff > res) res = len_diff;
+  if(prefix_len < limit)
+    return prefix_len;
+  return limit;
+}
 
-  return res;
+void nameBitvector_clear(NameBitvector *a, uint8_t start_from){
+  for(uint8_t pos = start_from; pos < WIDTH; pos++)
+      a->bits[pos / BV_SIZE] &= ~(ONE << ((BV_SIZE - 1) - (pos % BV_SIZE)));
 }
 
 int nameBitvector_ToIPAddress(const NameBitvector *name,
@@ -291,7 +270,7 @@ int nameBitvector_ToIPAddress(const NameBitvector *name,
     ip_address->family = AF_INET;
     ip_address->prefix_len = IPV4_ADDR_LEN_BITS;
 
-    uint32_t tmp_addr = name->bits[1] >> 32ULL;
+    uint32_t tmp_addr = name->bits[0] >> 32ULL;
     uint8_t addr_1 = (tmp_addr & 0xff000000) >> 24;
     uint8_t addr_2 = (tmp_addr & 0x00ff0000) >> 16;
     uint8_t addr_3 = (tmp_addr & 0x0000ff00) >> 8;
@@ -309,12 +288,12 @@ int nameBitvector_ToIPAddress(const NameBitvector *name,
     ip_address->prefix_len = name->len;  // IPV6_ADDR_LEN_BITS;
 
     for (int i = 0; i < 8; i++) {
-      addr->s6_addr[i] = (uint8_t)((name->bits[1] >> 8 * (7 - i)) & 0xFF);
+      addr->s6_addr[i] = (uint8_t)((name->bits[0] >> 8 * (7 - i)) & 0xFF);
     }
 
     int x = 0;
     for (int i = 8; i < 16; ++i) {
-      addr->s6_addr[i] = (uint8_t)((name->bits[0] >> 8 * (7 - x)) & 0xFF);
+      addr->s6_addr[i] = (uint8_t)((name->bits[1] >> 8 * (7 - x)) & 0xFF);
       x++;
     }
   }
@@ -329,7 +308,7 @@ Address *nameBitvector_ToAddress(const NameBitvector *name) {
     addr.sin_family = AF_INET;
     addr.sin_port = htons(1234);
 
-    uint32_t tmp_addr = name->bits[1] >> 32ULL;
+    uint32_t tmp_addr = name->bits[0] >> 32ULL;
     uint8_t addr_1 = (tmp_addr & 0xff000000) >> 24;
     uint8_t addr_2 = (tmp_addr & 0x00ff0000) >> 16;
     uint8_t addr_3 = (tmp_addr & 0x0000ff00) >> 8;
@@ -354,13 +333,13 @@ Address *nameBitvector_ToAddress(const NameBitvector *name) {
 
     for (int i = 0; i < 8; i++) {
       addr.sin6_addr.s6_addr[i] =
-          (uint8_t)((name->bits[1] >> 8 * (7 - i)) & 0xFF);
+          (uint8_t)((name->bits[0] >> 8 * (7 - i)) & 0xFF);
     }
 
     int x = 0;
     for (int i = 8; i < 16; ++i) {
       addr.sin6_addr.s6_addr[i] =
-          (uint8_t)((name->bits[0] >> 8 * (7 - x)) & 0xFF);
+          (uint8_t)((name->bits[1] >> 8 * (7 - x)) & 0xFF);
       x++;
     }
 
@@ -380,4 +359,4 @@ char *nameBitvector_ToString(const NameBitvector *name) {
   addressDestroy(&packetAddr);
 
   return output;
-}
\ No newline at end of file
+}
diff --git a/hicn-light/src/hicn/core/nameBitvector.h b/hicn-light/src/hicn/core/nameBitvector.h
index 6ff859e3b..44cc45662 100644
--- a/hicn-light/src/hicn/core/nameBitvector.h
+++ b/hicn-light/src/hicn/core/nameBitvector.h
@@ -30,9 +30,6 @@ NameBitvector *nameBitvector_CreateFromInAddr(uint32_t addr, uint8_t len);
 NameBitvector *nameBitvector_CreateFromIn6Addr(struct in6_addr *addr,
                                                uint8_t len);
 
-NameBitvector *nameBitvector_CreateFromAddress(const Address *prefix,
-                                               uint8_t len);
-
 NameBitvector *nameBitvector_Copy(const NameBitvector *original);
 
 void nameBitvector_Destroy(NameBitvector **bitvectorPtr);
@@ -45,12 +42,11 @@ bool nameBitvector_Equals(const NameBitvector *a, const NameBitvector *b);
 
 int nameBitvector_Compare(const NameBitvector *a, const NameBitvector *b);
 
-bool nameBitvector_StartsWith(const NameBitvector *name,
-                              const NameBitvector *prefix);
+int nameBitvector_testBit(const NameBitvector *name, uint8_t pos, bool *bit);
 
-bool nameBitvector_testBit(const NameBitvector *name, uint8_t pos);
+uint32_t nameBitvector_lpm(const NameBitvector *a, const NameBitvector *b);
 
-uint8_t nameBitvector_firstDiff(const NameBitvector *a, const NameBitvector *b);
+void nameBitvector_clear(NameBitvector *a, uint8_t start_from);
 
 int nameBitvector_ToIPAddress(const NameBitvector *name,
                               ip_address_t *ip_address);