Top

# miasm2.core.interval module

INT_EQ = 0      # Equivalent
INT_B_IN_A = 1  # B in A
INT_A_IN_B = -1 # A in B
INT_DISJOIN = 2 # Disjoint
INT_JOIN = 3    # Overlap
INT_JOIN_AB = 4 # B starts at the end of A
INT_JOIN_BA = 5 # A starts at the end of B

def cmp_interval(inter1, inter2):
"""Compare @inter1 and @inter2 and returns the associated INT_* case
@inter1, @inter2: interval instance
"""
if inter1 == inter2:
return INT_EQ

inter1_start, inter1_stop = inter1
inter2_start, inter2_stop = inter2
result = INT_JOIN
if inter1_start <= inter2_start and inter1_stop >= inter2_stop:
result = INT_B_IN_A
if inter2_start <= inter1_start and inter2_stop >= inter1_stop:
result = INT_A_IN_B
if inter1_stop + 1 == inter2_start:
result = INT_JOIN_AB
if inter2_stop + 1 == inter1_start:
result = INT_JOIN_BA
if inter1_start > inter2_stop + 1 or inter2_start > inter1_stop + 1:
result = INT_DISJOIN
return result

class interval(object):
"""Stands for intervals with integer bounds

Offers common methods to work with interval"""

def __init__(self, bounds=None):
"""Instance an interval object
@bounds: (optional) list of (int, int) and/or interval instance
"""
if bounds is None:
bounds = []
elif isinstance(bounds, interval):
bounds = bounds.intervals
self.is_cannon = False
self.intervals = bounds
self.cannon()

def __iter__(self):
"""Iterate on intervals"""
for inter in self.intervals:
yield inter

@staticmethod
def cannon_list(tmp):
"""
Return a cannonizes list of intervals
@tmp: list of (int, int)
"""
tmp = sorted([x for x in tmp if x[0] <= x[1]])
out = []
if not tmp:
return out
out.append(tmp.pop())
while tmp:
x = tmp.pop()
rez = cmp_interval(out[-1], x)

if rez == INT_EQ:
continue
elif rez == INT_DISJOIN:
out.append(x)
elif rez == INT_B_IN_A:
continue
elif rez in [INT_JOIN, INT_JOIN_AB, INT_JOIN_BA, INT_A_IN_B]:
u, v = x
while out and cmp_interval(out[-1], (u, v)) in [
INT_JOIN, INT_JOIN_AB, INT_JOIN_BA, INT_A_IN_B]:
u = min(u, out[-1][0])
v = max(v, out[-1][1])
out.pop()
out.append((u, v))
else:
raise ValueError('unknown state', rez)
return out[::-1]

def cannon(self):
"Apply .cannon_list() on self contained intervals"
if self.is_cannon is True:
return
self.intervals = interval.cannon_list(self.intervals)
self.is_cannon = True

def __repr__(self):
if self.intervals:
o = " U ".join(["[0x%X 0x%X]" % (x[0], x[1])
for x in self.intervals])
else:
o = "[]"
return o

def __contains__(self, other):
if isinstance(other, interval):
for intervalB in other.intervals:
is_in = False
for intervalA in self.intervals:
if cmp_interval(intervalA, intervalB) in [INT_EQ, INT_B_IN_A]:
is_in = True
break
if not is_in:
return False
return True
else:
for intervalA in self.intervals:
if intervalA[0] <= other <= intervalA[1]:
return True
return False

def __eq__(self, i):
return self.intervals == i.intervals

def __ne__(self, other):
return not self.__eq__(other)

if isinstance(i, interval):
i = i.intervals
i = interval(self.intervals + i)
return i

def __sub__(self, v):
to_test = self.intervals[:]
i = -1
to_del = v.intervals[:]
while i < len(to_test) - 1:
i += 1
x = to_test[i]
if x[0] > x[1]:
del to_test[i]
i -= 1
continue

while to_del and to_del[0][1] < x[0]:
del to_del[0]

for y in to_del:
if y[0] > x[1]:
break
rez = cmp_interval(x, y)
if rez == INT_DISJOIN:
continue
elif rez == INT_EQ:
del to_test[i]
i -= 1
break
elif rez == INT_A_IN_B:
del to_test[i]
i -= 1
break
elif rez == INT_B_IN_A:
del to_test[i]
i1 = (x[0], y[0] - 1)
i2 = (y[1] + 1, x[1])
to_test[i:i] = [i1, i2]
i -= 1
break
elif rez in [INT_JOIN_AB, INT_JOIN_BA]:
continue
elif rez == INT_JOIN:
del to_test[i]
if x[0] < y[0]:
to_test[i:i] = [(x[0], y[0] - 1)]
else:
to_test[i:i] = [(y[1] + 1, x[1])]
i -= 1
break
else:
raise ValueError('unknown state', rez)
return interval(to_test)

def __and__(self, v):
out = []
for x in self.intervals:
if x[0] > x[1]:
continue
for y in v.intervals:
rez = cmp_interval(x, y)

if rez == INT_DISJOIN:
continue
elif rez == INT_EQ:
out.append(x)
continue
elif rez == INT_A_IN_B:
out.append(x)
continue
elif rez == INT_B_IN_A:
out.append(y)
continue
elif rez == INT_JOIN_AB:
continue
elif rez == INT_JOIN_BA:
continue
elif rez == INT_JOIN:
if x[0] < y[0]:
out.append((y[0], x[1]))
else:
out.append((x[0], y[1]))
continue
else:
raise ValueError('unknown state', rez)
return interval(out)

def hull(self):
"Return the first and the last bounds of intervals"
if not self.intervals:
return None, None
return self.intervals[0][0], self.intervals[-1][1]

@property
def empty(self):
"""Return True iff the interval is empty"""
return not self.intervals

def show(self, img_x=1350, img_y=20, dry_run=False):
"""
show image representing the interval
"""
try:
import Image
import ImageDraw
except ImportError:
print 'cannot import python PIL imaging'
return

img = Image.new('RGB', (img_x, img_y), (100, 100, 100))
draw = ImageDraw.Draw(img)
i_min, i_max = self.hull()

print hex(i_min), hex(i_max)

for a, b in self.intervals:

if dry_run is False:
img.show()

@property
def length(self):
"""
Return the cumulated length of intervals
"""
# Do not use __len__ because we may return a value > 32 bits
return sum((stop - start + 1) for start, stop in self.intervals)

var INT_A_IN_B

var INT_B_IN_A

var INT_DISJOIN

var INT_EQ

var INT_JOIN

var INT_JOIN_AB

var INT_JOIN_BA

## Functions

def cmp_interval(

inter1, inter2)

Compare @inter1 and @inter2 and returns the associated INT_* case @inter1, @inter2: interval instance

def cmp_interval(inter1, inter2):
"""Compare @inter1 and @inter2 and returns the associated INT_* case
@inter1, @inter2: interval instance
"""
if inter1 == inter2:
return INT_EQ

inter1_start, inter1_stop = inter1
inter2_start, inter2_stop = inter2
result = INT_JOIN
if inter1_start <= inter2_start and inter1_stop >= inter2_stop:
result = INT_B_IN_A
if inter2_start <= inter1_start and inter2_stop >= inter1_stop:
result = INT_A_IN_B
if inter1_stop + 1 == inter2_start:
result = INT_JOIN_AB
if inter2_stop + 1 == inter1_start:
result = INT_JOIN_BA
if inter1_start > inter2_stop + 1 or inter2_start > inter1_stop + 1:
result = INT_DISJOIN
return result

## Classes

class interval

Stands for intervals with integer bounds

Offers common methods to work with interval

class interval(object):
"""Stands for intervals with integer bounds

Offers common methods to work with interval"""

def __init__(self, bounds=None):
"""Instance an interval object
@bounds: (optional) list of (int, int) and/or interval instance
"""
if bounds is None:
bounds = []
elif isinstance(bounds, interval):
bounds = bounds.intervals
self.is_cannon = False
self.intervals = bounds
self.cannon()

def __iter__(self):
"""Iterate on intervals"""
for inter in self.intervals:
yield inter

@staticmethod
def cannon_list(tmp):
"""
Return a cannonizes list of intervals
@tmp: list of (int, int)
"""
tmp = sorted([x for x in tmp if x[0] <= x[1]])
out = []
if not tmp:
return out
out.append(tmp.pop())
while tmp:
x = tmp.pop()
rez = cmp_interval(out[-1], x)

if rez == INT_EQ:
continue
elif rez == INT_DISJOIN:
out.append(x)
elif rez == INT_B_IN_A:
continue
elif rez in [INT_JOIN, INT_JOIN_AB, INT_JOIN_BA, INT_A_IN_B]:
u, v = x
while out and cmp_interval(out[-1], (u, v)) in [
INT_JOIN, INT_JOIN_AB, INT_JOIN_BA, INT_A_IN_B]:
u = min(u, out[-1][0])
v = max(v, out[-1][1])
out.pop()
out.append((u, v))
else:
raise ValueError('unknown state', rez)
return out[::-1]

def cannon(self):
"Apply .cannon_list() on self contained intervals"
if self.is_cannon is True:
return
self.intervals = interval.cannon_list(self.intervals)
self.is_cannon = True

def __repr__(self):
if self.intervals:
o = " U ".join(["[0x%X 0x%X]" % (x[0], x[1])
for x in self.intervals])
else:
o = "[]"
return o

def __contains__(self, other):
if isinstance(other, interval):
for intervalB in other.intervals:
is_in = False
for intervalA in self.intervals:
if cmp_interval(intervalA, intervalB) in [INT_EQ, INT_B_IN_A]:
is_in = True
break
if not is_in:
return False
return True
else:
for intervalA in self.intervals:
if intervalA[0] <= other <= intervalA[1]:
return True
return False

def __eq__(self, i):
return self.intervals == i.intervals

def __ne__(self, other):
return not self.__eq__(other)

if isinstance(i, interval):
i = i.intervals
i = interval(self.intervals + i)
return i

def __sub__(self, v):
to_test = self.intervals[:]
i = -1
to_del = v.intervals[:]
while i < len(to_test) - 1:
i += 1
x = to_test[i]
if x[0] > x[1]:
del to_test[i]
i -= 1
continue

while to_del and to_del[0][1] < x[0]:
del to_del[0]

for y in to_del:
if y[0] > x[1]:
break
rez = cmp_interval(x, y)
if rez == INT_DISJOIN:
continue
elif rez == INT_EQ:
del to_test[i]
i -= 1
break
elif rez == INT_A_IN_B:
del to_test[i]
i -= 1
break
elif rez == INT_B_IN_A:
del to_test[i]
i1 = (x[0], y[0] - 1)
i2 = (y[1] + 1, x[1])
to_test[i:i] = [i1, i2]
i -= 1
break
elif rez in [INT_JOIN_AB, INT_JOIN_BA]:
continue
elif rez == INT_JOIN:
del to_test[i]
if x[0] < y[0]:
to_test[i:i] = [(x[0], y[0] - 1)]
else:
to_test[i:i] = [(y[1] + 1, x[1])]
i -= 1
break
else:
raise ValueError('unknown state', rez)
return interval(to_test)

def __and__(self, v):
out = []
for x in self.intervals:
if x[0] > x[1]:
continue
for y in v.intervals:
rez = cmp_interval(x, y)

if rez == INT_DISJOIN:
continue
elif rez == INT_EQ:
out.append(x)
continue
elif rez == INT_A_IN_B:
out.append(x)
continue
elif rez == INT_B_IN_A:
out.append(y)
continue
elif rez == INT_JOIN_AB:
continue
elif rez == INT_JOIN_BA:
continue
elif rez == INT_JOIN:
if x[0] < y[0]:
out.append((y[0], x[1]))
else:
out.append((x[0], y[1]))
continue
else:
raise ValueError('unknown state', rez)
return interval(out)

def hull(self):
"Return the first and the last bounds of intervals"
if not self.intervals:
return None, None
return self.intervals[0][0], self.intervals[-1][1]

@property
def empty(self):
"""Return True iff the interval is empty"""
return not self.intervals

def show(self, img_x=1350, img_y=20, dry_run=False):
"""
show image representing the interval
"""
try:
import Image
import ImageDraw
except ImportError:
print 'cannot import python PIL imaging'
return

img = Image.new('RGB', (img_x, img_y), (100, 100, 100))
draw = ImageDraw.Draw(img)
i_min, i_max = self.hull()

print hex(i_min), hex(i_max)

for a, b in self.intervals:

if dry_run is False:
img.show()

@property
def length(self):
"""
Return the cumulated length of intervals
"""
# Do not use __len__ because we may return a value > 32 bits
return sum((stop - start + 1) for start, stop in self.intervals)

### Static methods

def cannon_list(

tmp)

Return a cannonizes list of intervals @tmp: list of (int, int)

@staticmethod
def cannon_list(tmp):
"""
Return a cannonizes list of intervals
@tmp: list of (int, int)
"""
tmp = sorted([x for x in tmp if x[0] <= x[1]])
out = []
if not tmp:
return out
out.append(tmp.pop())
while tmp:
x = tmp.pop()
rez = cmp_interval(out[-1], x)
if rez == INT_EQ:
continue
elif rez == INT_DISJOIN:
out.append(x)
elif rez == INT_B_IN_A:
continue
elif rez in [INT_JOIN, INT_JOIN_AB, INT_JOIN_BA, INT_A_IN_B]:
u, v = x
while out and cmp_interval(out[-1], (u, v)) in [
INT_JOIN, INT_JOIN_AB, INT_JOIN_BA, INT_A_IN_B]:
u = min(u, out[-1][0])
v = max(v, out[-1][1])
out.pop()
out.append((u, v))
else:
raise ValueError('unknown state', rez)
return out[::-1]

### Instance variables

var empty

Return True iff the interval is empty

var intervals

var is_cannon

var length

Return the cumulated length of intervals

### Methods

def __init__(

self, bounds=None)

Instance an interval object @bounds: (optional) list of (int, int) and/or interval instance

def __init__(self, bounds=None):
"""Instance an interval object
@bounds: (optional) list of (int, int) and/or interval instance
"""
if bounds is None:
bounds = []
elif isinstance(bounds, interval):
bounds = bounds.intervals
self.is_cannon = False
self.intervals = bounds
self.cannon()

def cannon(

self)

Apply .cannon_list() on self contained intervals

def cannon(self):
"Apply .cannon_list() on self contained intervals"
if self.is_cannon is True:
return
self.intervals = interval.cannon_list(self.intervals)
self.is_cannon = True

def hull(

self)

Return the first and the last bounds of intervals

def hull(self):
"Return the first and the last bounds of intervals"
if not self.intervals:
return None, None
return self.intervals[0][0], self.intervals[-1][1]

def show(

self, img_x=1350, img_y=20, dry_run=False)

show image representing the interval

def show(self, img_x=1350, img_y=20, dry_run=False):
"""
show image representing the interval
"""
try:
import Image
import ImageDraw
except ImportError:
print 'cannot import python PIL imaging'
return
img = Image.new('RGB', (img_x, img_y), (100, 100, 100))
draw = ImageDraw.Draw(img)
i_min, i_max = self.hull()
print hex(i_min), hex(i_max)