releasetools: Detect incomplete block ranges.

This CL detects incomplete block ranges (e.g. due to the holes in
mke2fs created images). Such block ranges will be tagged, so we won't
attempt to imgdiff those files. Note that the change to blockimgdiff.py,
which uses the tag info, will come in a separate CL.

An 'extra' attribute is added to RangeSet class, which defaults to an
empty dict. An 'incomplete' tag will be added into the dict by the
caller of the class. Not adding this tag as an immediate attribute,
because it is not a property regarding the ranges being represented, but
rather some storage space for the caller.

This CL also refactors GetSparseImage and RoundUpTo4K into common.py, so
the same code can be called from both of ota_from_target_files.py and
validate_target_files.py. Not able to add unittests for
GetSparseImage(), as SparseImage requires data in specific format.

Bug: 68016761
Test: Run validate_target_files.py on target-files.zip. It skips
      validating files with missing holes as before.
Test: Run ota_from_target_files.py on angler target-files.zip. It gives
      identical packages w/ and w/o the CL.
Test: pylint on changed files. There're warnings with common.py, but
      unrelated to this change.
Change-Id: I126ccfea13c0d5ebcc8c1b4ff1a4f9200e97423a
diff --git a/tools/releasetools/common.py b/tools/releasetools/common.py
index d0ee6ae..d09f60c 100644
--- a/tools/releasetools/common.py
+++ b/tools/releasetools/common.py
@@ -25,6 +25,7 @@
 import re
 import shlex
 import shutil
+import string
 import subprocess
 import sys
 import tempfile
@@ -34,6 +35,7 @@
 from hashlib import sha1, sha256
 
 import blockimgdiff
+import sparse_img
 
 class Options(object):
   def __init__(self):
@@ -124,6 +126,11 @@
   return subprocess.Popen(args, **kwargs)
 
 
+def RoundUpTo4K(value):
+  rounded_up = value + 4095
+  return rounded_up - (rounded_up % 4096)
+
+
 def CloseInheritedPipes():
   """ Gmake in MAC OS has file descriptor (PIPE) leak. We close those fds
   before doing other work."""
@@ -618,6 +625,56 @@
   return tmp, zipfile.ZipFile(filename, "r")
 
 
+def GetSparseImage(which, tmpdir, input_zip):
+  """Returns a SparseImage object suitable for passing to BlockImageDiff.
+
+  This function loads the specified sparse image from the given path, and
+  performs additional processing for OTA purpose. For example, it always adds
+  block 0 to clobbered blocks list. It also detects files that cannot be
+  reconstructed from the block list, for whom we should avoid applying imgdiff.
+
+  Args:
+    which: The partition name, which must be "system" or "vendor".
+    tmpdir: The directory that contains the prebuilt image and block map file.
+    input_zip: The target-files ZIP archive.
+
+  Returns:
+    A SparseImage object, with file_map info loaded.
+  """
+  assert which in ("system", "vendor")
+
+  path = os.path.join(tmpdir, "IMAGES", which + ".img")
+  mappath = os.path.join(tmpdir, "IMAGES", which + ".map")
+
+  # The image and map files must have been created prior to calling
+  # ota_from_target_files.py (since LMP).
+  assert os.path.exists(path) and os.path.exists(mappath)
+
+  # In ext4 filesystems, block 0 might be changed even being mounted R/O. We add
+  # it to clobbered_blocks so that it will be written to the target
+  # unconditionally. Note that they are still part of care_map. (Bug: 20939131)
+  clobbered_blocks = "0"
+
+  image = sparse_img.SparseImage(path, mappath, clobbered_blocks)
+
+  # block.map may contain less blocks, because mke2fs may skip allocating blocks
+  # if they contain all zeros. We can't reconstruct such a file from its block
+  # list. Tag such entries accordingly. (Bug: 65213616)
+  for entry in image.file_map:
+    # "/system/framework/am.jar" => "SYSTEM/framework/am.jar".
+    arcname = string.replace(entry, which, which.upper(), 1)[1:]
+    # Skip artificial names, such as "__ZERO", "__NONZERO-1".
+    if arcname not in input_zip.namelist():
+      continue
+
+    info = input_zip.getinfo(arcname)
+    ranges = image.file_map[entry]
+    if RoundUpTo4K(info.file_size) > ranges.size() * 4096:
+      ranges.extra['incomplete'] = True
+
+  return image
+
+
 def GetKeyPasswords(keylist):
   """Given a list of keys, prompt the user to enter passwords for
   those which require them.  Return a {key: password} dict.  password