-
Notifications
You must be signed in to change notification settings - Fork 0
/
MultibitNode.py
144 lines (100 loc) · 4.67 KB
/
MultibitNode.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
import itertools
import timeit
STRIDE = 3
class MultibitNode(object):
def __init__(self):
self.children = {}
def AddChild(self, prefix, path):
if path == "":
return
if len(path) < STRIDE: # if the path is shorter than the stride
# Expand the combinations and insert them all as children
for combination in GetCombinations(STRIDE - len(path)):
self.children[path + combination] = (prefix, None)
elif len(path) == STRIDE: # If it's exactly as long as the stride
# Set the corresponding dictionary entry
self.children[path] = (prefix, None)
else: # if it's longer than the stride
first = path[:STRIDE] # Take only the first STRIDE characters
# If we don't have this value in the dictionary yet, make a new node with no prefix
if first not in self.children:
self.children[first] = ("", MultibitNode())
# Otherwise keep the existing prefix and just create a child node
elif self.children[first][1] is None:
self.children[first] = (self.children[first][0], MultibitNode())
self.children[first][1].AddChild(prefix, path[STRIDE:])
def Lookup(self, address, backtrack=""):
if len(address) < STRIDE:
return backtrack
first = address[:STRIDE]
# If the child does not exist, return last valid prefix
if len(address) < STRIDE or first not in self.children:
return backtrack
child = self.children[first]
# We're here when address is at least as long as the stride
# If it's as long as the stride, or there is no pointer to another multibit node
if len(address) == STRIDE or child[1] is None:
return child[0]
else:
if child[0] == "":
return child[1].Lookup(address[STRIDE:], backtrack)
else:
return child[1].Lookup(address[STRIDE:], child[0])
def LookupNonRecursive(self, address, rootPrefix):
backtrack = rootPrefix
partialAddress = address
node = self
while node is not None:
if len(partialAddress) < STRIDE:
return backtrack
first = partialAddress[:STRIDE]
if len(partialAddress) < STRIDE or first not in node.children:
return backtrack
child = node.children[first]
node = node.children[first][1] # relocating pointer
if len(partialAddress) == STRIDE or child[1] is None:
return child[0]
else:
partialAddress = partialAddress[STRIDE:]
if child[0] != "":
backtrack = child[0]
node = child[1]
def GetCombinations(length):
# creating the combinations of the remaining bits
char_set = [0, 1]
return [''.join(map(str, i)) for i in itertools.product(char_set, repeat=length)]
def Create():
# helper method to rapidly create the trie reading the db.txt
_root = MultibitNode()
with open("db.txt", 'r') as f: # reading db for creating the trie
my_list = [line.rstrip('\n') for line in f]
for entry in my_list:
addr, binary_address = entry.split(",")
_root.AddChild(addr, binary_address)
return _root
def convert_in_bin(address):
# simple method to convert an IP address in its binary representation
if address.find('\\') != -1:
ip = address.split("\\")[0]
mask = int(address.split("\\")[1])
return ''.join([bin(int(x) + 256)[3:] for x in ip.split('.')])[:mask]
else:
return ''.join([bin(int(x) + 256)[3:] for x in address.split('.')])
# DEBUG
if __name__ == "__main__":
root = Create()
# Qui stiamo cercando 000. Se non lo trova usiamo il backtrack Default
# print (root.lookup("000", 'Default'))
# Qui stiamo cercando 010. Se non lo trova usiamo il backtrack Default altrimenti printa l'ip per intero
# print (root.lookup("010", "Default"))
# L'indirizzo che usavi tu aveva una mask non multipla di 3 quindi fa casino quando va a cercarlo, ricordi? Quindi fa sempre backtrack sul Default!
with open("tosearch.txt", 'r') as f: # reading for lookups
my_list = [line.rstrip('\n') for line in f]
times = []
for entry in my_list: # lookup timing
addr, binary_address = entry.split(",")
start = timeit.default_timer() # starting timing
root.LookupNonRecursive(binary_address, "0")
end = timeit.default_timer() - start
times.append(end*1000)
print ("MultibitTrie: " + str(sum(times)) + "ms")