detect overlapping objects

The CLI will run one additional pass to determine whether objects
overlap one another. Overlap might indicate bad headers or gaps
in the file (object offsets shifted).

diff --git a/deltatar/crypto.py b/deltatar/crypto.py
index 2012a1a..a381d2b 100755 (executable)
--- a/deltatar/crypto.py
+++ b/deltatar/crypto.py
@@ -1843,6 +1843,35 @@ def noise_output_candidates (cands, indent=8, cols=PDTCRYPT_TT_COLUMNS):
         noise (line)
 
 
+SLICE_START = 1 # ordering is important to have starts of intervals
+SLICE_END   = 0 # sorted before equal ends
+
+def find_overlaps (slices):
+    """
+    Find overlapping slices: iterate open/close points of intervals, tracking
+    the ones open at any time.
+    """
+    bounds = []
+    inside = set () # of indices into bounds
+    ovrlp  = set () # of indices into bounds
+
+    for i, s in enumerate (slices):
+        bounds.append ((s [0], SLICE_START, i))
+        bounds.append ((s [1], SLICE_END  , i))
+    bounds = sorted (bounds)
+
+    for val in bounds:
+        i = val [2]
+        if val [1] == SLICE_START:
+            inside.add (i)
+        else:
+            if len (inside) > 1: # closing one that overlapped
+                ovrlp |= inside
+            inside.remove (i)
+
+    return [ slices [i] for i in ovrlp ]
+
+
 def mode_scan (secret, fname, outs=None, nacl=None):
     """
     Dissect a binary file, looking for PDTCRYPT headers and objects.
@@ -1872,12 +1901,13 @@ def mode_scan (secret, fname, outs=None, nacl=None):
         os.close (ifd)
         raise
 
-    junk, todo = [], []
+    junk, todo, slices = [], [], []
     try:
         nobj = 0
         for cand in cands:
             nobj += 1
             vdt, hdr = inspect_hdr (ifd, cand)
+
             if vdt == HDR_CAND_JUNK:
                 junk.append (cand)
             else:
@@ -1893,23 +1923,26 @@ def mode_scan (secret, fname, outs=None, nacl=None):
                     ofname = PDTCRYPT_RESCUENAME % nobj
                     ofd = open2_dump_file (ofname, outs, force=PDTCRYPT_OVERWRITE)
 
+                ctsize = hdr ["ctsize"]
                 try:
-                    ok = try_decrypt (ifd, off0, hdr, secret, ofd=ofd) == hdr ["ctsize"]
+                    l = try_decrypt (ifd, off0, hdr, secret, ofd=ofd)
+                    ok = l == ctsize
+                    slices.append ((off0, off0 + l))
                 finally:
                     if ofd != -1:
                         os.close (ofd)
                 if vdt == HDR_CAND_GOOD and ok is True:
                     noise ("PDT: %d → ✓ valid object %d–%d"
-                           % (cand, off0, off0 + hdr ["ctsize"]))
+                           % (cand, off0, off0 + ctsize))
                 elif vdt == HDR_CAND_FISHY and ok is True:
                     noise ("PDT: %d → × object %d–%d, corrupt header"
-                           % (cand, off0, off0 + hdr ["ctsize"]))
+                           % (cand, off0, off0 + ctsize))
                 elif vdt == HDR_CAND_GOOD and ok is False:
                     noise ("PDT: %d → × object %d–%d, problematic payload"
-                           % (cand, off0, off0 + hdr ["ctsize"]))
+                           % (cand, off0, off0 + ctsize))
                 elif vdt == HDR_CAND_FISHY and ok is False:
                     noise ("PDT: %d → × object %d–%d, corrupt header, problematic "
-                           "ciphertext" % (cand, off0, off0 + hdr ["ctsize"]))
+                           "ciphertext" % (cand, off0, off0 + ctsize))
                 else:
                     raise Unreachable
     finally:
@@ -1921,6 +1954,12 @@ def mode_scan (secret, fname, outs=None, nacl=None):
         noise ("PDT: %d candidates not parseable as headers:" % len (junk))
         noise_output_candidates (junk)
 
+    overlap = find_overlaps (slices)
+    if len (overlap) > 0:
+        noise ("PDT: %d objects overlapping others" % len (overlap))
+        for slice in overlap:
+            noise ("PDT:    × %d→%d" % (slice [0], slice [1]))
+
 def usage (err=False):
     out = print
     if err is True: