diff --git a/core/Makefile b/core/Makefile
index e7eafe8..c0b2902 100644
--- a/core/Makefile
+++ b/core/Makefile
@@ -1135,7 +1135,8 @@
 	  $(HOST_OUT_EXECUTABLES)/mkuserimg.sh \
 	  $(HOST_OUT_EXECUTABLES)/make_ext4fs \
 	  $(HOST_OUT_EXECUTABLES)/simg2img \
-	  $(HOST_OUT_EXECUTABLES)/e2fsck
+	  $(HOST_OUT_EXECUTABLES)/e2fsck \
+	  $(HOST_OUT_EXECUTABLES)/xdelta3
 
 OTATOOLS := $(DISTTOOLS) \
 	  $(HOST_OUT_EXECUTABLES)/aapt
diff --git a/tools/releasetools/build_image.py b/tools/releasetools/build_image.py
index ffda6cf..927d89a 100755
--- a/tools/releasetools/build_image.py
+++ b/tools/releasetools/build_image.py
@@ -27,6 +27,8 @@
 import commands
 import shutil
 
+import simg_map
+
 def RunCommand(cmd):
   """ Echo and run the given command
 
@@ -146,6 +148,13 @@
     return False, None
   return True, unsparse_image_path
 
+def MappedUnsparseImage(sparse_image_path, unsparse_image_path,
+                        map_path, mapped_unsparse_image_path):
+  if simg_map.ComputeMap(sparse_image_path, unsparse_image_path,
+                         map_path, mapped_unsparse_image_path):
+    return False
+  return True
+
 def MakeVerityEnabledImage(out_file, prop_dict):
   """Creates an image that is verifiable using dm-verity.
 
diff --git a/tools/releasetools/common.py b/tools/releasetools/common.py
index b7e18fa..ca73ee4 100644
--- a/tools/releasetools/common.py
+++ b/tools/releasetools/common.py
@@ -1015,7 +1015,7 @@
     with open(output_file.name + ".xz") as patch_file:
       patch_data = patch_file.read()
       os.unlink(patch_file.name)
-      return File("system.img.p", patch_data)
+      return File("system.muimg.p", patch_data)
 
 def MakeRecoveryPatch(input_dir, output_sink, recovery_img, boot_img,
                       info_dict=None):
diff --git a/tools/releasetools/edify_generator.py b/tools/releasetools/edify_generator.py
index 7978062..af545db 100644
--- a/tools/releasetools/edify_generator.py
+++ b/tools/releasetools/edify_generator.py
@@ -190,6 +190,16 @@
                          (p.fs_type, common.PARTITION_TYPES[p.fs_type],
                           p.device, p.length, p.mount_point))
 
+  def WipeBlockDevice(self, partition):
+    if partition != "/system":
+      raise ValueError(("WipeBlockDevice currently only works "
+                        "on /system, not %s\n") % (partition,))
+    fstab = self.info.get("fstab", None)
+    size = self.info.get("system_size", None)
+    device = fstab[partition].device
+
+    self.script.append('wipe_block_device("%s", %s);' % (device, size))
+
   def DeleteFiles(self, file_list):
     """Delete all files in file_list."""
     if not file_list: return
@@ -224,7 +234,7 @@
     cmd = "".join(cmd)
     self.script.append(self._WordWrap(cmd))
 
-  def WriteRawImage(self, mount_point, fn):
+  def WriteRawImage(self, mount_point, fn, mapfn=None):
     """Write the given package file into the partition for the given
     mount point."""
 
@@ -238,8 +248,13 @@
             'write_raw_image(package_extract_file("%(fn)s"), "%(device)s");'
             % args)
       elif partition_type == "EMMC":
-        self.script.append(
-            'package_extract_file("%(fn)s", "%(device)s");' % args)
+        if mapfn:
+          args["map"] = mapfn
+          self.script.append(
+              'package_extract_file("%(fn)s", "%(device)s", "%(map)s");' % args)
+        else:
+          self.script.append(
+              'package_extract_file("%(fn)s", "%(device)s");' % args)
       else:
         raise ValueError("don't know how to write \"%s\" partitions" % (p.fs_type,))
 
@@ -309,7 +324,9 @@
     common.ZipWriteStr(output_zip, "META-INF/com/google/android/update-binary",
                        data, perms=0755)
 
-  def Syspatch(self, filename, size, target_sha, source_sha, patchfile):
+  def Syspatch(self, filename, target_mapfile, target_sha,
+               source_mapfile, source_sha, patchfile):
     """Applies a compressed binary patch to a block device."""
-    call = 'syspatch("%s", "%s", "%s", "%s", "%s");'
-    self.script.append(call % (filename, size, target_sha, source_sha, patchfile))
+    call = 'syspatch("%s", "%s", "%s", "%s", "%s", "%s");'
+    self.script.append(call % (filename, target_mapfile, target_sha,
+                               source_mapfile, source_sha, patchfile))
diff --git a/tools/releasetools/img_from_target_files.py b/tools/releasetools/img_from_target_files.py
index bd11a45..596a47e 100755
--- a/tools/releasetools/img_from_target_files.py
+++ b/tools/releasetools/img_from_target_files.py
@@ -60,7 +60,7 @@
   common.ZipWriteStr(output_zip, "system.img", data)
 
 
-def BuildSystem(input_dir, info_dict, sparse=True):
+def BuildSystem(input_dir, info_dict, sparse=True, map_file=None):
   print "creating system.img..."
 
   img = tempfile.NamedTemporaryFile()
@@ -87,6 +87,8 @@
                                 image_props, img.name)
   assert succ, "build system.img image failed"
 
+  mapdata = None
+
   if sparse:
     img.seek(os.SEEK_SET, 0)
     data = img.read()
@@ -95,13 +97,30 @@
     success, name = build_image.UnsparseImage(img.name, replace=False)
     if not success:
       assert False, "unsparsing system.img failed"
+
+    if map_file:
+      mmap = tempfile.NamedTemporaryFile()
+      mimg = tempfile.NamedTemporaryFile(delete=False)
+      success = build_image.MappedUnsparseImage(
+          img.name, name, mmap.name, mimg.name)
+      if not success:
+        assert False, "creating sparse map failed"
+      os.unlink(name)
+      name = mimg.name
+
+      with open(mmap.name) as f:
+        mapdata = f.read()
+
     try:
       with open(name) as f:
         data = f.read()
     finally:
       os.unlink(name)
 
-  return data
+  if mapdata is None:
+    return data
+  else:
+    return mapdata, data
 
 
 def AddVendor(output_zip):
diff --git a/tools/releasetools/ota_from_target_files b/tools/releasetools/ota_from_target_files
index a7936b1..59dd06e 100755
--- a/tools/releasetools/ota_from_target_files
+++ b/tools/releasetools/ota_from_target_files
@@ -461,8 +461,14 @@
 
   script.ShowProgress(system_progress, 30)
   if block_based:
-    img_from_target_files.AddSystem(output_zip, sparse=False)
-    script.WriteRawImage("/system", "system.img")
+    mapdata, data = img_from_target_files.BuildSystem(
+        OPTIONS.input_tmp, OPTIONS.info_dict,
+        sparse=False, map_file=True)
+
+    common.ZipWriteStr(output_zip, "system.map", mapdata)
+    common.ZipWriteStr(output_zip, "system.muimg", data)
+    script.WipeBlockDevice("/system")
+    script.WriteRawImage("/system", "system.muimg", mapfn="system.map")
   else:
     script.FormatPartition("/system")
     script.Mount("/system")
@@ -608,8 +614,10 @@
     with tempfile.NamedTemporaryFile() as tgt_file:
       print "building source system image..."
       src_file = tempfile.NamedTemporaryFile()
-      src_data = img_from_target_files.BuildSystem(
-          OPTIONS.source_tmp, OPTIONS.source_info_dict, sparse=False)
+      src_mapdata, src_data = img_from_target_files.BuildSystem(
+          OPTIONS.source_tmp, OPTIONS.source_info_dict,
+          sparse=False, map_file=True)
+
       src_sys_sha1 = sha1(src_data).hexdigest()
       print "source system sha1:", src_sys_sha1
       src_file.write(src_data)
@@ -617,8 +625,9 @@
 
       print "building target system image..."
       tgt_file = tempfile.NamedTemporaryFile()
-      tgt_data = img_from_target_files.BuildSystem(
-          OPTIONS.target_tmp, OPTIONS.target_info_dict, sparse=False)
+      tgt_mapdata, tgt_data = img_from_target_files.BuildSystem(
+          OPTIONS.target_tmp, OPTIONS.target_info_dict,
+          sparse=False, map_file=True)
       tgt_sys_sha1 = sha1(tgt_data).hexdigest()
       print "target system sha1:", tgt_sys_sha1
       tgt_sys_len = len(tgt_data)
@@ -628,6 +637,10 @@
       system_type, system_device = common.GetTypeAndDevice("/system", OPTIONS.info_dict)
       system_patch = common.MakeSystemPatch(src_file, tgt_file)
       system_patch.AddToZip(output_zip, compression=zipfile.ZIP_STORED)
+      src_mapfilename = system_patch.name + ".src.map"
+      common.ZipWriteStr(output_zip, src_mapfilename, src_mapdata)
+      tgt_mapfilename = system_patch.name + ".tgt.map"
+      common.ZipWriteStr(output_zip, tgt_mapfilename, tgt_mapdata)
 
   AppendAssertions(script, OPTIONS.target_info_dict)
   device_specific.IncrementalOTA_Assertions()
@@ -713,9 +726,8 @@
 
   script.Print("Patching system image...")
   script.Syspatch(system_device,
-                  OPTIONS.info_dict["system_size"],
-                  tgt_sys_sha1,
-                  src_sys_sha1,
+                  tgt_mapfilename, tgt_sys_sha1,
+                  src_mapfilename, src_sys_sha1,
                   system_patch.name)
 
   if OPTIONS.two_step:
@@ -1249,6 +1261,9 @@
     OPTIONS.source_tmp, source_zip = common.UnzipTemp(OPTIONS.incremental_source)
     OPTIONS.target_info_dict = OPTIONS.info_dict
     OPTIONS.source_info_dict = common.LoadInfoDict(source_zip)
+    if "selinux_fc" in OPTIONS.source_info_dict:
+      OPTIONS.source_info_dict["selinux_fc"] = os.path.join(OPTIONS.source_tmp, "BOOT", "RAMDISK",
+                                                            "file_contexts")
     if OPTIONS.package_key is None:
       OPTIONS.package_key = OPTIONS.source_info_dict.get(
           "default_system_dev_certificate",
diff --git a/tools/releasetools/simg_map.py b/tools/releasetools/simg_map.py
new file mode 100644
index 0000000..22dc863
--- /dev/null
+++ b/tools/releasetools/simg_map.py
@@ -0,0 +1,148 @@
+#! /usr/bin/env python
+
+# Copyright (C) 2012 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#      http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+from __future__ import print_function
+import getopt, posixpath, signal, struct, sys
+
+def main():
+  if len(sys.argv) == 4:
+    print("No sparse_image_file specified")
+    usage(me)
+
+  sparse_fn = sys.argv[1]
+  unsparse_fn = sys.argv[2]
+  map_file = sys.argv[3]
+  mapped_unsparse_fn = sys.argv[4]
+
+  return ComputeMap(sparse_fn, unsparse_fn, map_file, mapped_unsparse_fn)
+
+
+def ComputeMap(sparse_fn, unsparse_fn, map_file, mapped_unsparse_fn):
+  care_map = []
+
+  with open(sparse_fn, "rb") as FH:
+    header_bin = FH.read(28)
+    header = struct.unpack("<I4H4I", header_bin)
+
+    magic = header[0]
+    major_version = header[1]
+    minor_version = header[2]
+    file_hdr_sz = header[3]
+    chunk_hdr_sz = header[4]
+    blk_sz = header[5]
+    total_blks = header[6]
+    total_chunks = header[7]
+    image_checksum = header[8]
+
+    if magic != 0xED26FF3A:
+      print("%s: %s: Magic should be 0xED26FF3A but is 0x%08X"
+            % (me, path, magic))
+      return 1
+    if major_version != 1 or minor_version != 0:
+      print("%s: %s: I only know about version 1.0, but this is version %u.%u"
+            % (me, path, major_version, minor_version))
+      return 1
+    if file_hdr_sz != 28:
+      print("%s: %s: The file header size was expected to be 28, but is %u."
+            % (me, path, file_hdr_sz))
+      return 1
+    if chunk_hdr_sz != 12:
+      print("%s: %s: The chunk header size was expected to be 12, but is %u."
+            % (me, path, chunk_hdr_sz))
+      return 1
+
+    print("%s: Total of %u %u-byte output blocks in %u input chunks."
+          % (sparse_fn, total_blks, blk_sz, total_chunks))
+
+    offset = 0
+    for i in range(total_chunks):
+      header_bin = FH.read(12)
+      header = struct.unpack("<2H2I", header_bin)
+      chunk_type = header[0]
+      reserved1 = header[1]
+      chunk_sz = header[2]
+      total_sz = header[3]
+      data_sz = total_sz - 12
+
+      if chunk_type == 0xCAC1:
+        if data_sz != (chunk_sz * blk_sz):
+          print("Raw chunk input size (%u) does not match output size (%u)"
+                % (data_sz, chunk_sz * blk_sz))
+          return 1
+        else:
+          care_map.append((1, chunk_sz))
+          FH.seek(data_sz, 1)
+
+      elif chunk_type == 0xCAC2:
+        print("Fill chunks are not supported")
+        return 1
+
+      elif chunk_type == 0xCAC3:
+        if data_sz != 0:
+          print("Don't care chunk input size is non-zero (%u)" % (data_sz))
+          return 1
+        else:
+          care_map.append((0, chunk_sz))
+
+      elif chunk_type == 0xCAC4:
+        print("CRC32 chunks are not supported")
+
+      else:
+        print("Unknown chunk type 0x%04X not supported" % (chunk_type,))
+        return 1
+
+      offset += chunk_sz
+
+    if total_blks != offset:
+      print("The header said we should have %u output blocks, but we saw %u"
+            % (total_blks, offset))
+
+    junk_len = len(FH.read())
+    if junk_len:
+      print("There were %u bytes of extra data at the end of the file."
+            % (junk_len))
+      return 1
+
+  last_kind = None
+  new_care_map = []
+  for kind, size in care_map:
+    if kind != last_kind:
+      new_care_map.append((kind, size))
+      last_kind = kind
+    else:
+      new_care_map[-1] = (kind, new_care_map[-1][1] + size)
+
+  if new_care_map[0][0] == 0:
+    new_care_map.insert(0, (1, 0))
+  if len(new_care_map) % 2:
+    new_care_map.append((0, 0))
+
+  with open(map_file, "w") as fmap:
+    fmap.write("%d\n%d\n" % (blk_sz, len(new_care_map)))
+    for _, sz in new_care_map:
+      fmap.write("%d\n" % sz)
+
+  with open(unsparse_fn, "rb") as fin:
+    with open(mapped_unsparse_fn, "wb") as fout:
+      for k, sz in care_map:
+        data = fin.read(sz * blk_sz)
+        if k:
+          fout.write(data)
+        else:
+          assert data == "\x00" * len(data)
+
+if __name__ == "__main__":
+  sys.exit(main())