diff --git a/CleanSpec.mk b/CleanSpec.mk
index 877c690..2f1def0 100644
--- a/CleanSpec.mk
+++ b/CleanSpec.mk
@@ -205,6 +205,15 @@
 $(call add-clean-step, rm -rf $(PRODUCT_OUT)/system/app/*)
 $(call add-clean-step, rm -rf $(PRODUCT_OUT)/obj/APPS/*)
 
+# 4.4.1
+$(call add-clean-step, rm -rf $(PRODUCT_OUT)/system/build.prop)
+
+# 4.4.2
+$(call add-clean-step, rm -rf $(PRODUCT_OUT)/system/build.prop)
+
+# 4.4.3
+$(call add-clean-step, rm -rf $(PRODUCT_OUT)/system/build.prop)
+
 # ************************************************
 # NEWER CLEAN STEPS MUST BE AT THE END OF THE LIST
 # ************************************************
diff --git a/core/Makefile b/core/Makefile
index 298eef1..27f22a9 100644
--- a/core/Makefile
+++ b/core/Makefile
@@ -1243,6 +1243,7 @@
 	@# build them.
 	$(hide) mkdir -p $(zip_root)/META
 	$(hide) $(ACP) $(APKCERTS_FILE) $(zip_root)/META/apkcerts.txt
+	$(hide) if test -e $(tool_extensions)/releasetools.py; then $(ACP) $(tool_extensions)/releasetools.py $(zip_root)/META/; fi
 	$(hide)	echo "$(PRODUCT_OTA_PUBLIC_KEYS)" > $(zip_root)/META/otakeys.txt
 	$(hide) echo "recovery_api_version=$(PRIVATE_RECOVERY_API_VERSION)" > $(zip_root)/META/misc_info.txt
 	$(hide) echo "fstab_version=$(PRIVATE_RECOVERY_FSTAB_VERSION)" >> $(zip_root)/META/misc_info.txt
@@ -1262,6 +1263,8 @@
 endif
 	$(hide) echo "mkbootimg_args=$(BOARD_MKBOOTIMG_ARGS)" >> $(zip_root)/META/misc_info.txt
 	$(hide) echo "use_set_metadata=1" >> $(zip_root)/META/misc_info.txt
+	$(hide) echo "multistage_support=1" >> $(zip_root)/META/misc_info.txt
+	$(hide) echo "update_rename_support=1" >> $(zip_root)/META/misc_info.txt
 	$(call generate-userimage-prop-dictionary, $(zip_root)/META/misc_info.txt)
 	@# Zip everything up, preserving symlinks
 	$(hide) (cd $(zip_root) && zip -qry ../$(notdir $@) .)
diff --git a/core/clear_vars.mk b/core/clear_vars.mk
index a8b7b28..9713b6e 100644
--- a/core/clear_vars.mk
+++ b/core/clear_vars.mk
@@ -141,6 +141,7 @@
 LOCAL_POST_INSTALL_CMD:=
 LOCAL_DIST_BUNDLED_BINARIES:=
 LOCAL_HAL_STATIC_LIBRARIES:=
+LOCAL_TEST_MODULE_TO_PROGUARD_WITH:=
 
 # Trim MAKEFILE_LIST so that $(call my-dir) doesn't need to
 # iterate over thousands of entries every time.
diff --git a/core/definitions.mk b/core/definitions.mk
index 290bb2f..76b86ff 100644
--- a/core/definitions.mk
+++ b/core/definitions.mk
@@ -342,6 +342,22 @@
 endef
 
 ###########################################################
+# Use utility find to find given files in the given subdirs.
+# This function uses $(1), instead of LOCAL_PATH as the base.
+# $(1): the base dir, relative to the root of the source tree.
+# $(2): the file name pattern to be passed to find as "-name".
+# $(3): a list of subdirs of the base dir.
+# Returns: a list of paths relative to the base dir.
+###########################################################
+
+define find-files-in-subdirs
+$(patsubst ./%,%, \
+  $(shell cd $(1) ; \
+          find -L $(3) -name $(2) -and -not -name ".*") \
+ )
+endef
+
+###########################################################
 ## Scan through each directory of $(1) looking for files
 ## that match $(2) using $(wildcard).  Useful for seeing if
 ## a given directory or one of its parents contains
@@ -1633,7 +1649,7 @@
     $(addprefix -I , $(PRIVATE_AAPT_INCLUDES)) \
     $(addprefix --min-sdk-version , $(PRIVATE_DEFAULT_APP_TARGET_SDK)) \
     $(addprefix --target-sdk-version , $(PRIVATE_DEFAULT_APP_TARGET_SDK)) \
-    $(addprefix --product , $(TARGET_AAPT_CHARACTERISTICS)) \
+    $(if $(filter --product,$(PRIVATE_AAPT_FLAGS)),,$(addprefix --product , $(TARGET_AAPT_CHARACTERISTICS))) \
     $(if $(filter --version-code,$(PRIVATE_AAPT_FLAGS)),,$(addprefix --version-code , $(PLATFORM_SDK_VERSION))) \
     $(if $(filter --version-name,$(PRIVATE_AAPT_FLAGS)),,$(addprefix --version-name , $(PLATFORM_VERSION)-$(BUILD_NUMBER))) \
     $(addprefix --rename-manifest-package , $(PRIVATE_MANIFEST_PACKAGE_NAME)) \
@@ -1868,7 +1884,8 @@
 ###########################################################
 define transform-jar-to-proguard
 @echo Proguard: $@
-$(hide) $(PROGUARD) -injars $< -outjars $@ $(PRIVATE_PROGUARD_FLAGS)
+$(hide) $(PROGUARD) -injars $< -outjars $@ $(PRIVATE_PROGUARD_FLAGS) \
+    $(addprefix -injars , $(PRIVATE_EXTRA_INPUT_JAR))
 endef
 
 ###########################################################
diff --git a/core/droiddoc.mk b/core/droiddoc.mk
index 0d3094d..fd7f338 100644
--- a/core/droiddoc.mk
+++ b/core/droiddoc.mk
@@ -231,6 +231,8 @@
 	@mkdir -p $(dir $@)
 	$(hide) ( F=$$(pwd)/$@ ; cd $(PRIVATE_DOCS_DIR) && zip -rq $$F * )
 
+$(LOCAL_MODULE)-docs.zip : $(out_zip)
+
 $(call dist-for-goals,docs,$(out_zip))
 
 endif
diff --git a/core/java.mk b/core/java.mk
index f237965..4f44770 100644
--- a/core/java.mk
+++ b/core/java.mk
@@ -430,8 +430,14 @@
 proguard_flag_files := $(addprefix $(LOCAL_PATH)/, $(LOCAL_PROGUARD_FLAG_FILES))
 LOCAL_PROGUARD_FLAGS += $(addprefix -include , $(proguard_flag_files))
 
+ifdef LOCAL_TEST_MODULE_TO_PROGUARD_WITH
+extra_input_jar := $(call intermediates-dir-for,APPS,$(LOCAL_TEST_MODULE_TO_PROGUARD_WITH),,COMMON)/classes.jar
+else
+extra_input_jar :=
+endif
+$(full_classes_proguard_jar): PRIVATE_EXTRA_INPUT_JAR := $(extra_input_jar)
 $(full_classes_proguard_jar): PRIVATE_PROGUARD_FLAGS := $(proguard_flags) $(LOCAL_PROGUARD_FLAGS)
-$(full_classes_proguard_jar) : $(full_classes_jar) $(proguard_flag_files) | $(ACP) $(PROGUARD)
+$(full_classes_proguard_jar) : $(full_classes_jar) $(extra_input_jar) $(proguard_flag_files) | $(ACP) $(PROGUARD)
 	$(call transform-jar-to-proguard)
 
 else  # LOCAL_PROGUARD_ENABLED not defined
diff --git a/core/pathmap.mk b/core/pathmap.mk
index 5dfc543..1399724 100644
--- a/core/pathmap.mk
+++ b/core/pathmap.mk
@@ -105,6 +105,7 @@
 # A list of all source roots under frameworks/support.
 #
 FRAMEWORKS_SUPPORT_SUBDIRS := \
+        annotations \
         v4 \
         v7/gridlayout \
         v7/appcompat \
diff --git a/core/version_defaults.mk b/core/version_defaults.mk
index faa12d2..1e172ed 100644
--- a/core/version_defaults.mk
+++ b/core/version_defaults.mk
@@ -41,7 +41,7 @@
   # which is the version that we reveal to the end user.
   # Update this value when the platform version changes (rather
   # than overriding it somewhere else).  Can be an arbitrary string.
-  PLATFORM_VERSION := 4.4
+  PLATFORM_VERSION := 4.4.3
 endif
 
 ifeq "" "$(PLATFORM_SDK_VERSION)"
diff --git a/target/product/core_minimal.mk b/target/product/core_minimal.mk
index fc2fc80..159e7b2 100644
--- a/target/product/core_minimal.mk
+++ b/target/product/core_minimal.mk
@@ -33,6 +33,8 @@
     bu \
     com.android.location.provider \
     com.android.location.provider.xml \
+    com.android.media.remotedisplay \
+    com.android.media.remotedisplay.xml \
     drmserver \
     framework-res \
     installd \
diff --git a/target/product/sdk.mk b/target/product/sdk.mk
index 817d9a4..604790a 100644
--- a/target/product/sdk.mk
+++ b/target/product/sdk.mk
@@ -62,7 +62,8 @@
 	SmokeTest \
 	SmokeTestApp \
 	rild \
-	LegacyCamera
+	LegacyCamera \
+	Dialer
 
 # Define the host tools and libs that are parts of the SDK.
 -include sdk/build/product_sdk.mk
diff --git a/tools/droiddoc/templates-sdk/sample.cs b/tools/droiddoc/templates-sdk/sample.cs
index 684e284..c6f28f8 100644
--- a/tools/droiddoc/templates-sdk/sample.cs
+++ b/tools/droiddoc/templates-sdk/sample.cs
@@ -7,7 +7,7 @@
 
 <div <?cs if:fullpage
 ?>class="fullpage"<?cs elif:design||tools||about||sdk||distribute
-?>class="col-13" id="doc-col"<?cs else 
+?>class="col-13" id="doc-col"<?cs else
 ?>class="col-12" id="doc-col"<?cs /if ?> >
 
 <!-- start breadcrumb block -->
diff --git a/tools/releasetools/check_target_files_signatures b/tools/releasetools/check_target_files_signatures
index ae372ba..45d30a6 100755
--- a/tools/releasetools/check_target_files_signatures
+++ b/tools/releasetools/check_target_files_signatures
@@ -135,7 +135,7 @@
 
     for i in to_load:
       f = open(i)
-      cert = ParseCertificate(f.read())
+      cert = common.ParseCertificate(f.read())
       f.close()
       name, _ = os.path.splitext(i)
       name, _ = os.path.splitext(name)
@@ -144,21 +144,6 @@
 ALL_CERTS = CertDB()
 
 
-def ParseCertificate(data):
-  """Parse a PEM-format certificate."""
-  cert = []
-  save = False
-  for line in data.split("\n"):
-    if "--END CERTIFICATE--" in line:
-      break
-    if save:
-      cert.append(line)
-    if "--BEGIN CERTIFICATE--" in line:
-      save = True
-  cert = "".join(cert).decode('base64')
-  return cert
-
-
 def CertFromPKCS7(data, filename):
   """Read the cert out of a PKCS#7-format file (which is what is
   stored in a signed .apk)."""
@@ -175,7 +160,7 @@
       AddProblem("error reading cert:\n" + err)
       return None
 
-    cert = ParseCertificate(out)
+    cert = common.ParseCertificate(out)
     if not cert:
       AddProblem("error parsing cert output")
       return None
diff --git a/tools/releasetools/common.py b/tools/releasetools/common.py
index 58582ba..a3217dd 100644
--- a/tools/releasetools/common.py
+++ b/tools/releasetools/common.py
@@ -954,3 +954,18 @@
     return PARTITION_TYPES[fstab[mount_point].fs_type], fstab[mount_point].device
   else:
     return None
+
+
+def ParseCertificate(data):
+  """Parse a PEM-format certificate."""
+  cert = []
+  save = False
+  for line in data.split("\n"):
+    if "--END CERTIFICATE--" in line:
+      break
+    if save:
+      cert.append(line)
+    if "--BEGIN CERTIFICATE--" in line:
+      save = True
+  cert = "".join(cert).decode('base64')
+  return cert
diff --git a/tools/releasetools/edify_generator.py b/tools/releasetools/edify_generator.py
index 2c3b9e7..426b713 100644
--- a/tools/releasetools/edify_generator.py
+++ b/tools/releasetools/edify_generator.py
@@ -184,6 +184,20 @@
     cmd = "delete(" + ",\0".join(['"%s"' % (i,) for i in file_list]) + ");"
     self.script.append(self._WordWrap(cmd))
 
+  def RenameFile(self, srcfile, tgtfile):
+    """Moves a file from one location to another."""
+    if self.info.get("update_rename_support", False):
+      self.script.append('rename("%s", "%s");' % (srcfile, tgtfile))
+    else:
+      raise ValueError("Rename not supported by update binary")
+
+  def SkipNextActionIfTargetExists(self, tgtfile, tgtsha1):
+    """Prepend an action with an apply_patch_check in order to
+       skip the action if the file exists.  Used when a patch
+       is later renamed."""
+    cmd = ('sha1_check(read_file("%s"), %s) || ' % (tgtfile, tgtsha1))
+    self.script.append(self._WordWrap(cmd))
+
   def ApplyPatch(self, srcfile, tgtfile, tgtsize, tgtsha1, *patchpairs):
     """Apply binary patches (in *patchpairs) to the given srcfile to
     produce tgtfile (which may be "-" to indicate overwriting the
diff --git a/tools/releasetools/ota_from_target_files b/tools/releasetools/ota_from_target_files
index a6b9b69..a31d70a 100755
--- a/tools/releasetools/ota_from_target_files
+++ b/tools/releasetools/ota_from_target_files
@@ -52,6 +52,11 @@
   -a  (--aslr_mode)  <on|off>
       Specify whether to turn on ASLR for the package (on by default).
 
+  -2  (--two_step)
+      Generate a 'two-step' OTA package, where recovery is updated
+      first, so that any changes made to the system partition are done
+      using the new recovery (new kernel, etc.).
+
 """
 
 import sys
@@ -88,6 +93,7 @@
 OPTIONS.extra_script = None
 OPTIONS.aslr_mode = True
 OPTIONS.worker_threads = 3
+OPTIONS.two_step = False
 
 def MostPopularKey(d, default):
   """Given a dict, return the key corresponding to the largest
@@ -108,6 +114,31 @@
   symlink."""
   return (info.external_attr >> 28) == 010
 
+def ClosestFileMatch(src, tgtfiles, existing):
+  """Returns the closest file match between a source file and list
+     of potential matches.  The exact filename match is preferred,
+     then the sha1 is searched for, and finally a file with the same
+     basename is evaluated.  Rename support in the updater-binary is
+     required for the latter checks to be used."""
+
+  result = tgtfiles.get("path:" + src.name)
+  if result is not None:
+    return result
+
+  if not OPTIONS.target_info_dict.get("update_rename_support", False):
+    return None
+
+  if src.size < 1000:
+    return None
+
+  result = tgtfiles.get("sha1:" + src.sha1)
+  if result is not None and existing.get(result.name) is None:
+    return result
+  result = tgtfiles.get("file:" + src.name.split("/")[-1])
+  if result is not None and existing.get(result.name) is None:
+    return result
+  return None
+
 class Item:
   """Items represent the metadata (user, group, mode) of files and
   directories in the system image."""
@@ -404,6 +435,46 @@
 
   AppendAssertions(script, OPTIONS.info_dict)
   device_specific.FullOTA_Assertions()
+
+  # Two-step package strategy (in chronological order, which is *not*
+  # the order in which the generated script has things):
+  #
+  # if stage is not "2/3" or "3/3":
+  #    write recovery image to boot partition
+  #    set stage to "2/3"
+  #    reboot to boot partition and restart recovery
+  # else if stage is "2/3":
+  #    write recovery image to recovery partition
+  #    set stage to "3/3"
+  #    reboot to recovery partition and restart recovery
+  # else:
+  #    (stage must be "3/3")
+  #    set stage to ""
+  #    do normal full package installation:
+  #       wipe and install system, boot image, etc.
+  #       set up system to update recovery partition on first boot
+  #    complete script normally (allow recovery to mark itself finished and reboot)
+
+  recovery_img = common.GetBootableImage("recovery.img", "recovery.img",
+                                         OPTIONS.input_tmp, "RECOVERY")
+  if OPTIONS.two_step:
+    if not OPTIONS.info_dict.get("multistage_support", None):
+      assert False, "two-step packages not supported by this build"
+    fs = OPTIONS.info_dict["fstab"]["/misc"]
+    assert fs.fs_type.upper() == "EMMC", \
+        "two-step packages only supported on devices with EMMC /misc partitions"
+    bcb_dev = {"bcb_dev": fs.device}
+    common.ZipWriteStr(output_zip, "recovery.img", recovery_img.data)
+    script.AppendExtra("""
+if get_stage("%(bcb_dev)s", "stage") == "2/3" then
+""" % bcb_dev)
+    script.WriteRawImage("/recovery", "recovery.img")
+    script.AppendExtra("""
+set_stage("%(bcb_dev)s", "3/3");
+reboot_now("%(bcb_dev)s", "recovery");
+else if get_stage("%(bcb_dev)s", "stage") == "3/3" then
+""" % bcb_dev)
+
   device_specific.FullOTA_InstallBegin()
 
   script.ShowProgress(0.5, 0)
@@ -424,8 +495,6 @@
 
   boot_img = common.GetBootableImage("boot.img", "boot.img",
                                      OPTIONS.input_tmp, "BOOT")
-  recovery_img = common.GetBootableImage("recovery.img", "recovery.img",
-                                         OPTIONS.input_tmp, "RECOVERY")
   MakeRecoveryPatch(OPTIONS.input_tmp, output_zip, recovery_img, boot_img)
 
   Item.GetMetadata(input_zip)
@@ -445,6 +514,19 @@
     script.AppendExtra(OPTIONS.extra_script)
 
   script.UnmountAll()
+
+  if OPTIONS.two_step:
+    script.AppendExtra("""
+set_stage("%(bcb_dev)s", "");
+""" % bcb_dev)
+    script.AppendExtra("else\n")
+    script.WriteRawImage("/boot", "recovery.img")
+    script.AppendExtra("""
+set_stage("%(bcb_dev)s", "2/3");
+reboot_now("%(bcb_dev)s", "");
+endif;
+endif;
+""" % bcb_dev)
   script.AddToZip(input_zip, output_zip)
   WriteMetadata(metadata, output_zip)
 
@@ -479,6 +561,16 @@
   except KeyError:
     raise common.ExternalError("couldn't find %s in build.prop" % (property,))
 
+def AddToKnownPaths(filename, known_paths):
+  if filename[-1] == "/":
+    return
+  dirs = filename.split("/")[:-1]
+  while len(dirs) > 0:
+    path = "/".join(dirs)
+    if path in known_paths:
+      break;
+    known_paths.add(path)
+    dirs.pop()
 
 def WriteIncrementalOTAPackage(target_zip, source_zip, output_zip):
   source_version = OPTIONS.source_info_dict["recovery_api_version"]
@@ -514,11 +606,29 @@
   verbatim_targets = []
   patch_list = []
   diffs = []
+  renames = {}
+  known_paths = set()
   largest_source_size = 0
+
+  matching_file_cache = {}
+  for fn, sf in source_data.items():
+    assert fn == sf.name
+    matching_file_cache["path:" + fn] = sf
+    if fn in target_data.keys():
+      AddToKnownPaths(fn, known_paths)
+    # Only allow eligibility for filename/sha matching
+    # if there isn't a perfect path match.
+    if target_data.get(sf.name) is None:
+      matching_file_cache["file:" + fn.split("/")[-1]] = sf
+      matching_file_cache["sha:" + sf.sha1] = sf
+
   for fn in sorted(target_data.keys()):
     tf = target_data[fn]
     assert fn == tf.name
-    sf = source_data.get(fn, None)
+    sf = ClosestFileMatch(tf, matching_file_cache, renames)
+    if sf is not None and sf.name != tf.name:
+      print "File has moved from " + sf.name + " to " + tf.name
+      renames[sf.name] = tf
 
     if sf is None or fn in OPTIONS.require_verbatim:
       # This file should be included verbatim
@@ -527,24 +637,33 @@
       print "send", fn, "verbatim"
       tf.AddToZip(output_zip)
       verbatim_targets.append((fn, tf.size))
+      if fn in target_data.keys():
+        AddToKnownPaths(fn, known_paths)
     elif tf.sha1 != sf.sha1:
       # File is different; consider sending as a patch
       diffs.append(common.Difference(tf, sf))
     else:
-      # Target file identical to source.
+      # Target file data identical to source (may still be renamed)
       pass
 
   common.ComputeDifferences(diffs)
 
   for diff in diffs:
     tf, sf, d = diff.GetPatch()
-    if d is None or len(d) > tf.size * OPTIONS.patch_threshold:
+    path = "/".join(tf.name.split("/")[:-1])
+    if d is None or len(d) > tf.size * OPTIONS.patch_threshold or \
+        path not in known_paths:
       # patch is almost as big as the file; don't bother patching
+      # or a patch + rename cannot take place due to the target 
+      # directory not existing
       tf.AddToZip(output_zip)
       verbatim_targets.append((tf.name, tf.size))
+      if sf.name in renames:
+        del renames[sf.name]
+      AddToKnownPaths(tf.name, known_paths)
     else:
-      common.ZipWriteStr(output_zip, "patch/" + tf.name + ".p", d)
-      patch_list.append((tf.name, tf, sf, tf.size, common.sha1(d).hexdigest()))
+      common.ZipWriteStr(output_zip, "patch/" + sf.name + ".p", d)
+      patch_list.append((tf, sf, tf.size, common.sha1(d).hexdigest()))
       largest_source_size = max(largest_source_size, sf.size)
 
   source_fp = GetBuildProp("ro.build.fingerprint", OPTIONS.source_info_dict)
@@ -560,7 +679,8 @@
       OPTIONS.source_info_dict)
   target_boot = common.GetBootableImage(
       "/tmp/boot.img", "boot.img", OPTIONS.target_tmp, "BOOT")
-  updating_boot = (source_boot.data != target_boot.data)
+  updating_boot = (not OPTIONS.two_step and
+                   (source_boot.data != target_boot.data))
 
   source_recovery = common.GetBootableImage(
       "/tmp/recovery.img", "recovery.img", OPTIONS.source_tmp, "RECOVERY",
@@ -578,18 +698,60 @@
   AppendAssertions(script, OPTIONS.target_info_dict)
   device_specific.IncrementalOTA_Assertions()
 
+  # Two-step incremental package strategy (in chronological order,
+  # which is *not* the order in which the generated script has
+  # things):
+  #
+  # if stage is not "2/3" or "3/3":
+  #    do verification on current system
+  #    write recovery image to boot partition
+  #    set stage to "2/3"
+  #    reboot to boot partition and restart recovery
+  # else if stage is "2/3":
+  #    write recovery image to recovery partition
+  #    set stage to "3/3"
+  #    reboot to recovery partition and restart recovery
+  # else:
+  #    (stage must be "3/3")
+  #    perform update:
+  #       patch system files, etc.
+  #       force full install of new boot image
+  #       set up system to update recovery partition on first boot
+  #    complete script normally (allow recovery to mark itself finished and reboot)
+
+  if OPTIONS.two_step:
+    if not OPTIONS.info_dict.get("multistage_support", None):
+      assert False, "two-step packages not supported by this build"
+    fs = OPTIONS.info_dict["fstab"]["/misc"]
+    assert fs.fs_type.upper() == "EMMC", \
+        "two-step packages only supported on devices with EMMC /misc partitions"
+    bcb_dev = {"bcb_dev": fs.device}
+    common.ZipWriteStr(output_zip, "recovery.img", target_recovery.data)
+    script.AppendExtra("""
+if get_stage("%(bcb_dev)s", "stage") == "2/3" then
+""" % bcb_dev)
+    script.AppendExtra("sleep(20);\n");
+    script.WriteRawImage("/recovery", "recovery.img")
+    script.AppendExtra("""
+set_stage("%(bcb_dev)s", "3/3");
+reboot_now("%(bcb_dev)s", "recovery");
+else if get_stage("%(bcb_dev)s", "stage") != "3/3" then
+""" % bcb_dev)
+
   script.Print("Verifying current system...")
 
   device_specific.IncrementalOTA_VerifyBegin()
 
   script.ShowProgress(0.1, 0)
-  total_verify_size = float(sum([i[2].size for i in patch_list]) + 1)
+  total_verify_size = float(sum([i[1].size for i in patch_list]) + 1)
   if updating_boot:
     total_verify_size += source_boot.size
   so_far = 0
 
-  for fn, tf, sf, size, patch_sha in patch_list:
-    script.PatchCheck("/"+fn, tf.sha1, sf.sha1)
+  for tf, sf, size, patch_sha in patch_list:
+    if tf.name != sf.name:
+      script.SkipNextActionIfTargetExists(tf.name, tf.sha1)
+    script.PatchCheck("/"+sf.name, tf.sha1, sf.sha1)
     so_far += sf.size
     script.SetProgress(so_far / total_verify_size)
 
@@ -615,10 +777,23 @@
 
   device_specific.IncrementalOTA_VerifyEnd()
 
+  if OPTIONS.two_step:
+    script.WriteRawImage("/boot", "recovery.img")
+    script.AppendExtra("""
+set_stage("%(bcb_dev)s", "2/3");
+reboot_now("%(bcb_dev)s", "");
+else
+""" % bcb_dev)
+
   script.Comment("---- start making changes here ----")
 
   device_specific.IncrementalOTA_InstallBegin()
 
+  if OPTIONS.two_step:
+    common.ZipWriteStr(output_zip, "boot.img", target_boot.data)
+    script.WriteRawImage("/boot", "boot.img")
+    print "writing full boot image (forced by two-step mode)"
+
   if OPTIONS.wipe_user_data:
     script.Print("Erasing user data...")
     script.FormatPartition("/data")
@@ -626,7 +801,8 @@
   script.Print("Removing unneeded files...")
   script.DeleteFiles(["/"+i[0] for i in verbatim_targets] +
                      ["/"+i for i in sorted(source_data)
-                            if i not in target_data] +
+                            if i not in target_data and
+                            i not in renames] +
                      ["/system/recovery.img"])
 
   script.ShowProgress(0.8, 0)
@@ -638,31 +814,34 @@
   script.Print("Patching system files...")
   deferred_patch_list = []
   for item in patch_list:
-    fn, tf, sf, size, _ = item
+    tf, sf, size, _ = item
     if tf.name == "system/build.prop":
       deferred_patch_list.append(item)
       continue
-    script.ApplyPatch("/"+fn, "-", tf.size, tf.sha1, sf.sha1, "patch/"+fn+".p")
+    if (sf.name != tf.name):
+      script.SkipNextActionIfTargetExists(tf.name, tf.sha1)
+    script.ApplyPatch("/"+sf.name, "-", tf.size, tf.sha1, sf.sha1, "patch/"+sf.name+".p")
     so_far += tf.size
     script.SetProgress(so_far / total_patch_size)
 
-  if updating_boot:
-    # Produce the boot image by applying a patch to the current
-    # contents of the boot partition, and write it back to the
-    # partition.
-    script.Print("Patching boot image...")
-    script.ApplyPatch("%s:%s:%d:%s:%d:%s"
-                      % (boot_type, boot_device,
-                         source_boot.size, source_boot.sha1,
-                         target_boot.size, target_boot.sha1),
-                      "-",
-                      target_boot.size, target_boot.sha1,
-                      source_boot.sha1, "patch/boot.img.p")
-    so_far += target_boot.size
-    script.SetProgress(so_far / total_patch_size)
-    print "boot image changed; including."
-  else:
-    print "boot image unchanged; skipping."
+  if not OPTIONS.two_step:
+    if updating_boot:
+      # Produce the boot image by applying a patch to the current
+      # contents of the boot partition, and write it back to the
+      # partition.
+      script.Print("Patching boot image...")
+      script.ApplyPatch("%s:%s:%d:%s:%d:%s"
+                        % (boot_type, boot_device,
+                           source_boot.size, source_boot.sha1,
+                           target_boot.size, target_boot.sha1),
+                        "-",
+                        target_boot.size, target_boot.sha1,
+                        source_boot.sha1, "patch/boot.img.p")
+      so_far += target_boot.size
+      script.SetProgress(so_far / total_patch_size)
+      print "boot image changed; including."
+    else:
+      print "boot image unchanged; skipping."
 
   if updating_recovery:
     # Recovery is generated as a patch using both the boot image
@@ -713,6 +892,13 @@
     script.Print("Unpacking new recovery...")
     script.UnpackPackageDir("recovery", "/system")
 
+  if len(renames) > 0:
+    script.Print("Renaming files...")
+
+  for src in renames:
+    print "Renaming " + src + " to " + renames[src].name
+    script.RenameFile(src, renames[src].name)
+
   script.Print("Symlinks and permissions...")
 
   # Create all the symlinks that don't already exist, or point to
@@ -743,10 +929,17 @@
   # get set the OTA package again to retry.
   script.Print("Patching remaining system files...")
   for item in deferred_patch_list:
-    fn, tf, sf, size, _ = item
-    script.ApplyPatch("/"+fn, "-", tf.size, tf.sha1, sf.sha1, "patch/"+fn+".p")
+    tf, sf, size, _ = item
+    script.ApplyPatch("/"+sf.name, "-", tf.size, tf.sha1, sf.sha1, "patch/"+sf.name+".p")
   script.SetPermissions("/system/build.prop", 0, 0, 0644, None, None)
 
+  if OPTIONS.two_step:
+    script.AppendExtra("""
+set_stage("%(bcb_dev)s", "");
+endif;
+endif;
+""" % bcb_dev)
+
   script.AddToZip(target_zip, output_zip)
   WriteMetadata(metadata, output_zip)
 
@@ -773,12 +966,14 @@
         OPTIONS.aslr_mode = False
     elif o in ("--worker_threads"):
       OPTIONS.worker_threads = int(a)
+    elif o in ("-2", "--two_step"):
+      OPTIONS.two_step = True
     else:
       return False
     return True
 
   args = common.ParseOptions(argv, __doc__,
-                             extra_opts="b:k:i:d:wne:a:",
+                             extra_opts="b:k:i:d:wne:a:2",
                              extra_long_opts=["board_config=",
                                               "package_key=",
                                               "incremental_from=",
@@ -787,6 +982,7 @@
                                               "extra_script=",
                                               "worker_threads=",
                                               "aslr_mode=",
+                                              "two_step",
                                               ],
                              extra_option_handler=option_handler)
 
diff --git a/tools/releasetools/sign_target_files_apks b/tools/releasetools/sign_target_files_apks
index 5556573..00693b8 100755
--- a/tools/releasetools/sign_target_files_apks
+++ b/tools/releasetools/sign_target_files_apks
@@ -71,8 +71,10 @@
   print >> sys.stderr, "Python 2.4 or newer is required."
   sys.exit(1)
 
+import base64
 import cStringIO
 import copy
+import errno
 import os
 import re
 import subprocess
@@ -161,11 +163,45 @@
       print "rewriting %s:" % (info.filename,)
       new_data = RewriteProps(data)
       output_tf_zip.writestr(out_info, new_data)
+    elif info.filename.endswith("mac_permissions.xml"):
+      print "rewriting %s with new keys." % (info.filename,)
+      new_data = ReplaceCerts(data)
+      output_tf_zip.writestr(out_info, new_data)
     else:
       # a non-APK file; copy it verbatim
       output_tf_zip.writestr(out_info, data)
 
 
+def ReplaceCerts(data):
+  """Given a string of data, replace all occurences of a set
+  of X509 certs with a newer set of X509 certs and return
+  the updated data string."""
+  for old, new in OPTIONS.key_map.iteritems():
+    try:
+      if OPTIONS.verbose:
+        print "    Replacing %s.x509.pem with %s.x509.pem" % (old, new)
+      f = open(old + ".x509.pem")
+      old_cert16 = base64.b16encode(common.ParseCertificate(f.read())).lower()
+      f.close()
+      f = open(new + ".x509.pem")
+      new_cert16 = base64.b16encode(common.ParseCertificate(f.read())).lower()
+      f.close()
+      # Only match entire certs.
+      pattern = "\\b"+old_cert16+"\\b"
+      (data, num) = re.subn(pattern, new_cert16, data, flags=re.IGNORECASE)
+      if OPTIONS.verbose:
+        print "    Replaced %d occurence(s) of %s.x509.pem with " \
+            "%s.x509.pem" % (num, old, new)
+    except IOError, e:
+      if (e.errno == errno.ENOENT and not OPTIONS.verbose):
+        continue
+
+      print "    Error accessing %s. %s. Skip replacing %s.x509.pem " \
+          "with %s.x509.pem." % (e.filename, e.strerror, old, new)
+
+  return data
+
+
 def EditTags(tags):
   """Given a string containing comma-separated tags, apply the edits
   specified in OPTIONS.tag_changes and return the updated string."""