Generate the compute_hash_tree command

Generate the transfer command "compute_hash_tree" for incremental
updates of the non-A/B devices that enable verified boot 1.0

Other changes include:
i.  factor out verity_utils to use both in build_image and blockimgdiff
ii. add a new flag 'hashtree_info_generator' in sparse_image to generate
    the hashtree information.

Bug: 25170618
Test: generate a package for aosp_angler; and run simulator
Change-Id: I4d4d7a3e41dc3da810d2cbf8988e85d187c9ab0e
diff --git a/tools/releasetools/blockimgdiff.py b/tools/releasetools/blockimgdiff.py
index c7d93d3..aeb4379 100644
--- a/tools/releasetools/blockimgdiff.py
+++ b/tools/releasetools/blockimgdiff.py
@@ -32,7 +32,6 @@
 import common
 from rangelib import RangeSet
 
-
 __all__ = ["EmptyImage", "DataImage", "BlockImageDiff"]
 
 
@@ -649,6 +648,14 @@
 
     self.touched_src_sha1 = self.src.RangeSha1(self.touched_src_ranges)
 
+    if self.tgt.hashtree_info:
+      out.append("compute_hash_tree {} {} {} {} {}\n".format(
+          self.tgt.hashtree_info.hashtree_range.to_string_raw(),
+          self.tgt.hashtree_info.filesystem_range.to_string_raw(),
+          self.tgt.hashtree_info.hash_algorithm,
+          self.tgt.hashtree_info.salt,
+          self.tgt.hashtree_info.root_hash))
+
     # Zero out extended blocks as a workaround for bug 20881595.
     if self.tgt.extended:
       assert (WriteSplitTransfers(out, "zero", self.tgt.extended) ==
@@ -988,6 +995,12 @@
           assert touched[i] == 0
           touched[i] = 1
 
+    if self.tgt.hashtree_info:
+      for s, e in self.tgt.hashtree_info.hashtree_range:
+        for i in range(s, e):
+          assert touched[i] == 0
+          touched[i] = 1
+
     # Check that we've written every target block.
     for s, e in self.tgt.care_map:
       for i in range(s, e):
@@ -1533,6 +1546,9 @@
         AddTransfer(tgt_fn, None, tgt_ranges, empty, "new", self.transfers)
         continue
 
+      elif tgt_fn == "__HASHTREE":
+        continue
+
       elif tgt_fn in self.src.file_map:
         # Look for an exact pathname match in the source.
         AddTransfer(tgt_fn, tgt_fn, tgt_ranges, self.src.file_map[tgt_fn],