diff --git a/payload_consumer/delta_performer.cc b/payload_consumer/delta_performer.cc
index c3fd411..95cc390 100644
--- a/payload_consumer/delta_performer.cc
+++ b/payload_consumer/delta_performer.cc
@@ -768,6 +768,7 @@
         OP_DURATION_HISTOGRAM("SOURCE_COPY", op_start_time);
         break;
       case InstallOperation::SOURCE_BSDIFF:
+      case InstallOperation::BROTLI_BSDIFF:
         op_result = PerformSourceBsdiffOperation(op, error);
         OP_DURATION_HISTOGRAM("SOURCE_BSDIFF", op_start_time);
         break;
@@ -1226,15 +1227,17 @@
   }
 
   string input_positions;
-  TEST_AND_RETURN_FALSE(ExtentsToBsdiffPositionsString(operation.src_extents(),
-                                                       block_size_,
-                                                       operation.src_length(),
-                                                       &input_positions));
+  TEST_AND_RETURN_FALSE(ExtentsToBsdiffPositionsString(
+      operation.src_extents(),
+      block_size_,
+      utils::BlocksInExtents(operation.src_extents()) * block_size_,
+      &input_positions));
   string output_positions;
-  TEST_AND_RETURN_FALSE(ExtentsToBsdiffPositionsString(operation.dst_extents(),
-                                                       block_size_,
-                                                       operation.dst_length(),
-                                                       &output_positions));
+  TEST_AND_RETURN_FALSE(ExtentsToBsdiffPositionsString(
+      operation.dst_extents(),
+      block_size_,
+      utils::BlocksInExtents(operation.dst_extents()) * block_size_,
+      &output_positions));
 
   TEST_AND_RETURN_FALSE(bsdiff::bspatch(source_path_.c_str(),
                                         target_path_.c_str(),
diff --git a/payload_consumer/payload_constants.cc b/payload_consumer/payload_constants.cc
index 7d396b6..ad193a0 100644
--- a/payload_consumer/payload_constants.cc
+++ b/payload_consumer/payload_constants.cc
@@ -54,6 +54,8 @@
       return "REPLACE_XZ";
     case InstallOperation::PUFFDIFF:
       return "PUFFDIFF";
+    case InstallOperation::BROTLI_BSDIFF:
+      return "BROTLI_BSDIFF";
   }
   return "<unknown_op>";
 }
diff --git a/payload_generator/ab_generator.h b/payload_generator/ab_generator.h
index 77afb87..343b546 100644
--- a/payload_generator/ab_generator.h
+++ b/payload_generator/ab_generator.h
@@ -55,13 +55,13 @@
       BlobFileWriter* blob_file,
       std::vector<AnnotatedOperation>* aops) override;
 
-  // Split the operations in the vector of AnnotatedOperations |aops|
-  // such that for every operation there is only one dst extent and updates
-  // |aops| with the new list of operations. All kinds of operations are
-  // fragmented except BSDIFF and SOURCE_BSDIFF operations.
-  // The |target_part_path| is the filename of the new image, where the
-  // destination extents refer to. The blobs of the operations in |aops| should
-  // reference |blob_file|. |blob_file| are updated if needed.
+  // Split the operations in the vector of AnnotatedOperations |aops| such that
+  // for every operation there is only one dst extent and updates |aops| with
+  // the new list of operations. All kinds of operations are fragmented except
+  // BSDIFF and SOURCE_BSDIFF, PUFFDIFF and BROTLI_BSDIFF operations.  The
+  // |target_part_path| is the filename of the new image, where the destination
+  // extents refer to. The blobs of the operations in |aops| should reference
+  // |blob_file|. |blob_file| are updated if needed.
   static bool FragmentOperations(const PayloadVersion& version,
                                  std::vector<AnnotatedOperation>* aops,
                                  const std::string& target_part_path,
diff --git a/payload_generator/delta_diff_utils.cc b/payload_generator/delta_diff_utils.cc
index b2b6b51..5a8bf8e 100644
--- a/payload_generator/delta_diff_utils.cc
+++ b/payload_generator/delta_diff_utils.cc
@@ -43,6 +43,7 @@
 #include "update_engine/common/hash_calculator.h"
 #include "update_engine/common/subprocess.h"
 #include "update_engine/common/utils.h"
+#include "update_engine/payload_consumer/payload_constants.h"
 #include "update_engine/payload_generator/block_mapping.h"
 #include "update_engine/payload_generator/bzip.h"
 #include "update_engine/payload_generator/deflate_utils.h"
@@ -821,10 +822,11 @@
     operation.set_dst_length(new_data.size() - removed_bytes);
   }
 
-  // Set legacy |src_length| and |dst_length| fields for both BSDIFF and
-  // SOURCE_BSDIFF as only these two use these parameters.
+  // WARNING: We always set legacy |src_length| and |dst_length| fields for
+  // BSDIFF. For SOURCE_BSDIFF we only set them for minor version 3 and lower.
   if (operation.type() == InstallOperation::BSDIFF ||
-      operation.type() == InstallOperation::SOURCE_BSDIFF) {
+      (operation.type() == InstallOperation::SOURCE_BSDIFF &&
+       version.minor <= kOpSrcHashMinorPayloadVersion)) {
     operation.set_src_length(old_data.size());
     operation.set_dst_length(new_data.size());
   }
diff --git a/payload_generator/payload_generation_config.cc b/payload_generator/payload_generation_config.cc
index e2fec21..836b481 100644
--- a/payload_generator/payload_generation_config.cc
+++ b/payload_generator/payload_generation_config.cc
@@ -165,6 +165,7 @@
     case InstallOperation::SOURCE_BSDIFF:
       return minor >= kSourceMinorPayloadVersion;
 
+    case InstallOperation::BROTLI_BSDIFF:
     case InstallOperation::PUFFDIFF:
       return minor >= kPuffdiffMinorPayloadVersion;
   }
diff --git a/scripts/update_payload/applier.py b/scripts/update_payload/applier.py
index 84d7e3c..3cb9741 100644
--- a/scripts/update_payload/applier.py
+++ b/scripts/update_payload/applier.py
@@ -349,9 +349,25 @@
     _WriteExtents(new_part_file, in_data, op.dst_extents, block_size,
                   '%s.dst_extents' % op_name)
 
+  def _BytesInExtents(self, extents, base_name):
+    """Counts the length of extents in bytes.
+
+    Args:
+      extents: The list of Extents.
+      base_name: For error reporting.
+
+    Returns:
+      The number of bytes in extents.
+    """
+
+    length = 0
+    for ex, ex_name in common.ExtentIter(extents, base_name):
+      length += ex.num_blocks * self.block_size
+    return length
+
   def _ApplyDiffOperation(self, op, op_name, patch_data, old_part_file,
                           new_part_file):
-    """Applies a SOURCE_BSDIFF or PUFFDIFF operation.
+    """Applies a SOURCE_BSDIFF, BROTLI_BSDIFF or PUFFDIFF operation.
 
     Args:
       op: the operation object
@@ -378,18 +394,22 @@
     if (hasattr(new_part_file, 'fileno') and
         ((not old_part_file) or hasattr(old_part_file, 'fileno'))):
       # Construct input and output extents argument for bspatch.
+
       in_extents_arg, _, _ = _ExtentsToBspatchArg(
           op.src_extents, block_size, '%s.src_extents' % op_name,
-          data_length=op.src_length)
+          data_length=op.src_length if op.src_length else
+          self._BytesInExtents(op.src_extents, "%s.src_extents"))
       out_extents_arg, pad_off, pad_len = _ExtentsToBspatchArg(
           op.dst_extents, block_size, '%s.dst_extents' % op_name,
-          data_length=op.dst_length)
+          data_length=op.dst_length if op.dst_length else
+          self._BytesInExtents(op.dst_extents, "%s.dst_extents"))
 
       new_file_name = '/dev/fd/%d' % new_part_file.fileno()
       # Diff from source partition.
       old_file_name = '/dev/fd/%d' % old_part_file.fileno()
 
-      if op.type in (common.OpType.BSDIFF, common.OpType.SOURCE_BSDIFF):
+      if op.type in (common.OpType.BSDIFF, common.OpType.SOURCE_BSDIFF,
+                     common.OpType.BROTLI_BSDIFF):
         # Invoke bspatch on partition file with extents args.
         bspatch_cmd = [self.bspatch_path, old_file_name, new_file_name,
                        patch_file_name, in_extents_arg, out_extents_arg]
@@ -415,7 +435,9 @@
       # Gather input raw data and write to a temp file.
       input_part_file = old_part_file if old_part_file else new_part_file
       in_data = _ReadExtents(input_part_file, op.src_extents, block_size,
-                             max_length=op.src_length)
+                             max_length=op.src_length if op.src_length else
+                             self._BytesInExtents(op.src_extents,
+                                                  "%s.src_extents"))
       with tempfile.NamedTemporaryFile(delete=False) as in_file:
         in_file_name = in_file.name
         in_file.write(in_data)
@@ -424,7 +446,8 @@
       with tempfile.NamedTemporaryFile(delete=False) as out_file:
         out_file_name = out_file.name
 
-      if op.type in (common.OpType.BSDIFF, common.OpType.SOURCE_BSDIFF):
+      if op.type in (common.OpType.BSDIFF, common.OpType.SOURCE_BSDIFF,
+                     common.OpType.BROTLI_BSDIFF):
         # Invoke bspatch.
         bspatch_cmd = [self.bspatch_path, in_file_name, out_file_name,
                        patch_file_name]
@@ -496,7 +519,8 @@
       elif op.type == common.OpType.SOURCE_COPY:
         self._ApplySourceCopyOperation(op, op_name, old_part_file,
                                        new_part_file)
-      elif op.type in (common.OpType.SOURCE_BSDIFF, common.OpType.PUFFDIFF):
+      elif op.type in (common.OpType.SOURCE_BSDIFF, common.OpType.PUFFDIFF,
+                       common.OpType.BROTLI_BSDIFF):
         self._ApplyDiffOperation(op, op_name, data, old_part_file,
                                  new_part_file)
       else:
diff --git a/scripts/update_payload/checker.py b/scripts/update_payload/checker.py
index c613642..c710c47 100644
--- a/scripts/update_payload/checker.py
+++ b/scripts/update_payload/checker.py
@@ -833,10 +833,12 @@
     if op.data_offset:
       raise error.PayloadError('%s: contains data_offset.' % op_name)
 
-  def _CheckAnyDiffOperation(self, data_length, total_dst_blocks, op_name):
-    """Specific checks for BSDIFF, SOURCE_BSDIFF and PUFFDIFF operations.
+  def _CheckAnyDiffOperation(self, op, data_length, total_dst_blocks, op_name):
+    """Specific checks for BSDIFF, SOURCE_BSDIFF, PUFFDIFF and BROTLI_BSDIFF
+       operations.
 
     Args:
+      op: The operation.
       data_length: The length of the data blob associated with the operation.
       total_dst_blocks: Total number of blocks in dst_extents.
       op_name: Operation name for error reporting.
@@ -856,6 +858,15 @@
           (op_name, data_length, total_dst_blocks, self.block_size,
            total_dst_blocks * self.block_size))
 
+    # Check the existence of src_length and dst_length for legacy bsdiffs.
+    if (op.type == common.OpType.BSDIFF or
+        (op.type == common.OpType.SOURCE_BSDIFF and self.minor_version <= 3)):
+      if not op.HasField('src_length') or not op.HasField('dst_length'):
+        raise error.PayloadError('%s: require {src,dst}_length.' % op_name)
+    else:
+      if op.HasField('src_length') or op.HasField('dst_length'):
+        raise error.PayloadError('%s: unneeded {src,dst}_length.' % op_name)
+
   def _CheckSourceCopyOperation(self, data_offset, total_src_blocks,
                                 total_dst_blocks, op_name):
     """Specific checks for SOURCE_COPY.
@@ -993,16 +1004,17 @@
     elif op.type == common.OpType.ZERO and self.minor_version >= 4:
       self._CheckZeroOperation(op, op_name)
     elif op.type == common.OpType.BSDIFF and self.minor_version == 1:
-      self._CheckAnyDiffOperation(data_length, total_dst_blocks, op_name)
+      self._CheckAnyDiffOperation(op, data_length, total_dst_blocks, op_name)
     elif op.type == common.OpType.SOURCE_COPY and self.minor_version >= 2:
       self._CheckSourceCopyOperation(data_offset, total_src_blocks,
                                      total_dst_blocks, op_name)
       self._CheckAnySourceOperation(op, total_src_blocks, op_name)
     elif op.type == common.OpType.SOURCE_BSDIFF and self.minor_version >= 2:
-      self._CheckAnyDiffOperation(data_length, total_dst_blocks, op_name)
+      self._CheckAnyDiffOperation(op, data_length, total_dst_blocks, op_name)
       self._CheckAnySourceOperation(op, total_src_blocks, op_name)
-    elif op.type == common.OpType.PUFFDIFF and self.minor_version >= 4:
-      self._CheckAnyDiffOperation(data_length, total_dst_blocks, op_name)
+    elif (op.type in (common.OpType.PUFFDIFF, common.OpType.BROTLI_BSDIFF) and
+          self.minor_version >= 4):
+      self._CheckAnyDiffOperation(op, data_length, total_dst_blocks, op_name)
       self._CheckAnySourceOperation(op, total_src_blocks, op_name)
     else:
       raise error.PayloadError(
@@ -1064,6 +1076,7 @@
         common.OpType.SOURCE_COPY: 0,
         common.OpType.SOURCE_BSDIFF: 0,
         common.OpType.PUFFDIFF: 0,
+        common.OpType.BROTLI_BSDIFF: 0,
     }
     # Total blob sizes for each operation type.
     op_blob_totals = {
@@ -1074,6 +1087,7 @@
         # SOURCE_COPY operations don't have blobs.
         common.OpType.SOURCE_BSDIFF: 0,
         common.OpType.PUFFDIFF: 0,
+        common.OpType.BROTLI_BSDIFF: 0,
     }
     # Counts of hashed vs unhashed operations.
     blob_hash_counts = {
diff --git a/scripts/update_payload/checker_unittest.py b/scripts/update_payload/checker_unittest.py
index eecd456..245da55 100755
--- a/scripts/update_payload/checker_unittest.py
+++ b/scripts/update_payload/checker_unittest.py
@@ -39,6 +39,7 @@
       'DISCARD': common.OpType.DISCARD,
       'REPLACE_XZ': common.OpType.REPLACE_XZ,
       'PUFFDIFF': common.OpType.PUFFDIFF,
+      'BROTLI_BSDIFF': common.OpType.BROTLI_BSDIFF,
   }
   return op_name_to_type[op_name]
 
@@ -771,22 +772,23 @@
   def testCheckAnyDiff(self):
     """Tests _CheckAnyDiffOperation()."""
     payload_checker = checker.PayloadChecker(self.MockPayload())
+    op = update_metadata_pb2.InstallOperation()
 
     # Pass.
     self.assertIsNone(
-        payload_checker._CheckAnyDiffOperation(10000, 3, 'foo'))
+        payload_checker._CheckAnyDiffOperation(op, 10000, 3, 'foo'))
 
     # Fail, missing data blob.
     self.assertRaises(
         update_payload.PayloadError,
         payload_checker._CheckAnyDiffOperation,
-        None, 3, 'foo')
+        op, None, 3, 'foo')
 
     # Fail, too big of a diff blob (unjustified).
     self.assertRaises(
         update_payload.PayloadError,
         payload_checker._CheckAnyDiffOperation,
-        10000, 2, 'foo')
+        op, 10000, 2, 'foo')
 
   def testCheckSourceCopyOperation_Pass(self):
     """Tests _CheckSourceCopyOperation(); pass case."""
@@ -818,7 +820,7 @@
 
     Args:
       op_type_name: 'REPLACE', 'REPLACE_BZ', 'MOVE', 'BSDIFF', 'SOURCE_COPY',
-        'SOURCE_BSDIFF' or 'PUFFDIFF'.
+        'SOURCE_BSDIFF', BROTLI_BSDIFF or 'PUFFDIFF'.
       is_last: Whether we're testing the last operation in a sequence.
       allow_signature: Whether we're testing a signature-capable operation.
       allow_unhashed: Whether we're allowing to not hash the data.
@@ -858,7 +860,7 @@
     total_src_blocks = 0
     if op_type in (common.OpType.MOVE, common.OpType.BSDIFF,
                    common.OpType.SOURCE_COPY, common.OpType.SOURCE_BSDIFF,
-                   common.OpType.PUFFDIFF):
+                   common.OpType.PUFFDIFF, common.OpType.BROTLI_BSDIFF):
       if fail_src_extents:
         self.AddToMessage(op.src_extents,
                           self.NewExtentList((1, 0)))
@@ -874,7 +876,7 @@
     elif op_type in (common.OpType.SOURCE_COPY, common.OpType.SOURCE_BSDIFF):
       payload_checker.minor_version = 1 if fail_bad_minor_version else 2
     elif op_type in (common.OpType.ZERO, common.OpType.DISCARD,
-                     common.OpType.PUFFDIFF):
+                     common.OpType.PUFFDIFF, common.OpType.BROTLI_BSDIFF):
       payload_checker.minor_version = 3 if fail_bad_minor_version else 4
 
     if op_type not in (common.OpType.MOVE, common.OpType.SOURCE_COPY):
@@ -893,6 +895,7 @@
           op.data_sha256_hash = hashlib.sha256(fake_data).digest()
           payload.ReadDataBlob(op.data_offset, op.data_length).AndReturn(
               fake_data)
+
       elif fail_data_hash:
         # Create an invalid data blob hash.
         op.data_sha256_hash = hashlib.sha256(
@@ -913,7 +916,9 @@
     if total_src_blocks:
       if fail_src_length:
         op.src_length = total_src_blocks * block_size + 8
-      else:
+      elif (op_type in (common.OpType.MOVE, common.OpType.BSDIFF,
+                        common.OpType.SOURCE_BSDIFF) and
+            payload_checker.minor_version <= 3):
         op.src_length = total_src_blocks * block_size
     elif fail_src_length:
       # Add an orphaned src_length.
@@ -922,7 +927,9 @@
     if total_dst_blocks:
       if fail_dst_length:
         op.dst_length = total_dst_blocks * block_size + 8
-      else:
+      elif (op_type in (common.OpType.MOVE, common.OpType.BSDIFF,
+                        common.OpType.SOURCE_BSDIFF) and
+            payload_checker.minor_version <= 3):
         op.dst_length = total_dst_blocks * block_size
 
     self.mox.ReplayAll()
@@ -1279,7 +1286,8 @@
   AddParametricTests('CheckOperation',
                      {'op_type_name': ('REPLACE', 'REPLACE_BZ', 'MOVE',
                                        'BSDIFF', 'SOURCE_COPY',
-                                       'SOURCE_BSDIFF', 'PUFFDIFF'),
+                                       'SOURCE_BSDIFF', 'PUFFDIFF',
+                                       'BROTLI_BSDIFF'),
                       'is_last': (True, False),
                       'allow_signature': (True, False),
                       'allow_unhashed': (True, False),
diff --git a/scripts/update_payload/common.py b/scripts/update_payload/common.py
index bab8a4f..eaf0611 100644
--- a/scripts/update_payload/common.py
+++ b/scripts/update_payload/common.py
@@ -46,8 +46,9 @@
   DISCARD = _CLASS.DISCARD
   REPLACE_XZ = _CLASS.REPLACE_XZ
   PUFFDIFF = _CLASS.PUFFDIFF
+  BROTLI_BSDIFF = _CLASS.BROTLI_BSDIFF
   ALL = (REPLACE, REPLACE_BZ, MOVE, BSDIFF, SOURCE_COPY, SOURCE_BSDIFF, ZERO,
-         DISCARD, REPLACE_XZ, PUFFDIFF)
+         DISCARD, REPLACE_XZ, PUFFDIFF, BROTLI_BSDIFF)
   NAMES = {
       REPLACE: 'REPLACE',
       REPLACE_BZ: 'REPLACE_BZ',
@@ -59,6 +60,7 @@
       DISCARD: 'DISCARD',
       REPLACE_XZ: 'REPLACE_XZ',
       PUFFDIFF: 'PUFFDIFF',
+      BROTLI_BSDIFF: 'BROTLI_BSDIFF',
   }
 
   def __init__(self):
diff --git a/scripts/update_payload/update_metadata_pb2.py b/scripts/update_payload/update_metadata_pb2.py
index 8cf87e3..595f2f6 100644
--- a/scripts/update_payload/update_metadata_pb2.py
+++ b/scripts/update_payload/update_metadata_pb2.py
@@ -13,7 +13,7 @@
 DESCRIPTOR = _descriptor.FileDescriptor(
   name='update_metadata.proto',
   package='chromeos_update_engine',
-  serialized_pb='\n\x15update_metadata.proto\x12\x16\x63hromeos_update_engine\"1\n\x06\x45xtent\x12\x13\n\x0bstart_block\x18\x01 \x01(\x04\x12\x12\n\nnum_blocks\x18\x02 \x01(\x04\"z\n\nSignatures\x12@\n\nsignatures\x18\x01 \x03(\x0b\x32,.chromeos_update_engine.Signatures.Signature\x1a*\n\tSignature\x12\x0f\n\x07version\x18\x01 \x01(\r\x12\x0c\n\x04\x64\x61ta\x18\x02 \x01(\x0c\"+\n\rPartitionInfo\x12\x0c\n\x04size\x18\x01 \x01(\x04\x12\x0c\n\x04hash\x18\x02 \x01(\x0c\"w\n\tImageInfo\x12\r\n\x05\x62oard\x18\x01 \x01(\t\x12\x0b\n\x03key\x18\x02 \x01(\t\x12\x0f\n\x07\x63hannel\x18\x03 \x01(\t\x12\x0f\n\x07version\x18\x04 \x01(\t\x12\x15\n\rbuild_channel\x18\x05 \x01(\t\x12\x15\n\rbuild_version\x18\x06 \x01(\t\"\xd3\x03\n\x10InstallOperation\x12;\n\x04type\x18\x01 \x02(\x0e\x32-.chromeos_update_engine.InstallOperation.Type\x12\x13\n\x0b\x64\x61ta_offset\x18\x02 \x01(\r\x12\x13\n\x0b\x64\x61ta_length\x18\x03 \x01(\r\x12\x33\n\x0bsrc_extents\x18\x04 \x03(\x0b\x32\x1e.chromeos_update_engine.Extent\x12\x12\n\nsrc_length\x18\x05 \x01(\x04\x12\x33\n\x0b\x64st_extents\x18\x06 \x03(\x0b\x32\x1e.chromeos_update_engine.Extent\x12\x12\n\ndst_length\x18\x07 \x01(\x04\x12\x18\n\x10\x64\x61ta_sha256_hash\x18\x08 \x01(\x0c\x12\x17\n\x0fsrc_sha256_hash\x18\t \x01(\x0c\"\x92\x01\n\x04Type\x12\x0b\n\x07REPLACE\x10\x00\x12\x0e\n\nREPLACE_BZ\x10\x01\x12\x08\n\x04MOVE\x10\x02\x12\n\n\x06\x42SDIFF\x10\x03\x12\x0f\n\x0bSOURCE_COPY\x10\x04\x12\x11\n\rSOURCE_BSDIFF\x10\x05\x12\x08\n\x04ZERO\x10\x06\x12\x0b\n\x07\x44ISCARD\x10\x07\x12\x0e\n\nREPLACE_XZ\x10\x08\x12\x0c\n\x08PUFFDIFF\x10\t\"\xa6\x03\n\x0fPartitionUpdate\x12\x16\n\x0epartition_name\x18\x01 \x02(\t\x12\x17\n\x0frun_postinstall\x18\x02 \x01(\x08\x12\x18\n\x10postinstall_path\x18\x03 \x01(\t\x12\x17\n\x0f\x66ilesystem_type\x18\x04 \x01(\t\x12M\n\x17new_partition_signature\x18\x05 \x03(\x0b\x32,.chromeos_update_engine.Signatures.Signature\x12\x41\n\x12old_partition_info\x18\x06 \x01(\x0b\x32%.chromeos_update_engine.PartitionInfo\x12\x41\n\x12new_partition_info\x18\x07 \x01(\x0b\x32%.chromeos_update_engine.PartitionInfo\x12<\n\noperations\x18\x08 \x03(\x0b\x32(.chromeos_update_engine.InstallOperation\x12\x1c\n\x14postinstall_optional\x18\t \x01(\x08\"\xc4\x05\n\x14\x44\x65ltaArchiveManifest\x12\x44\n\x12install_operations\x18\x01 \x03(\x0b\x32(.chromeos_update_engine.InstallOperation\x12K\n\x19kernel_install_operations\x18\x02 \x03(\x0b\x32(.chromeos_update_engine.InstallOperation\x12\x18\n\nblock_size\x18\x03 \x01(\r:\x04\x34\x30\x39\x36\x12\x19\n\x11signatures_offset\x18\x04 \x01(\x04\x12\x17\n\x0fsignatures_size\x18\x05 \x01(\x04\x12>\n\x0fold_kernel_info\x18\x06 \x01(\x0b\x32%.chromeos_update_engine.PartitionInfo\x12>\n\x0fnew_kernel_info\x18\x07 \x01(\x0b\x32%.chromeos_update_engine.PartitionInfo\x12>\n\x0fold_rootfs_info\x18\x08 \x01(\x0b\x32%.chromeos_update_engine.PartitionInfo\x12>\n\x0fnew_rootfs_info\x18\t \x01(\x0b\x32%.chromeos_update_engine.PartitionInfo\x12\x39\n\x0eold_image_info\x18\n \x01(\x0b\x32!.chromeos_update_engine.ImageInfo\x12\x39\n\x0enew_image_info\x18\x0b \x01(\x0b\x32!.chromeos_update_engine.ImageInfo\x12\x18\n\rminor_version\x18\x0c \x01(\r:\x01\x30\x12;\n\npartitions\x18\r \x03(\x0b\x32\'.chromeos_update_engine.PartitionUpdateB\x02H\x03')
+  serialized_pb='\n\x15update_metadata.proto\x12\x16\x63hromeos_update_engine\"1\n\x06\x45xtent\x12\x13\n\x0bstart_block\x18\x01 \x01(\x04\x12\x12\n\nnum_blocks\x18\x02 \x01(\x04\"z\n\nSignatures\x12@\n\nsignatures\x18\x01 \x03(\x0b\x32,.chromeos_update_engine.Signatures.Signature\x1a*\n\tSignature\x12\x0f\n\x07version\x18\x01 \x01(\r\x12\x0c\n\x04\x64\x61ta\x18\x02 \x01(\x0c\"+\n\rPartitionInfo\x12\x0c\n\x04size\x18\x01 \x01(\x04\x12\x0c\n\x04hash\x18\x02 \x01(\x0c\"w\n\tImageInfo\x12\r\n\x05\x62oard\x18\x01 \x01(\t\x12\x0b\n\x03key\x18\x02 \x01(\t\x12\x0f\n\x07\x63hannel\x18\x03 \x01(\t\x12\x0f\n\x07version\x18\x04 \x01(\t\x12\x15\n\rbuild_channel\x18\x05 \x01(\t\x12\x15\n\rbuild_version\x18\x06 \x01(\t\"\xe6\x03\n\x10InstallOperation\x12;\n\x04type\x18\x01 \x02(\x0e\x32-.chromeos_update_engine.InstallOperation.Type\x12\x13\n\x0b\x64\x61ta_offset\x18\x02 \x01(\r\x12\x13\n\x0b\x64\x61ta_length\x18\x03 \x01(\r\x12\x33\n\x0bsrc_extents\x18\x04 \x03(\x0b\x32\x1e.chromeos_update_engine.Extent\x12\x12\n\nsrc_length\x18\x05 \x01(\x04\x12\x33\n\x0b\x64st_extents\x18\x06 \x03(\x0b\x32\x1e.chromeos_update_engine.Extent\x12\x12\n\ndst_length\x18\x07 \x01(\x04\x12\x18\n\x10\x64\x61ta_sha256_hash\x18\x08 \x01(\x0c\x12\x17\n\x0fsrc_sha256_hash\x18\t \x01(\x0c\"\xa5\x01\n\x04Type\x12\x0b\n\x07REPLACE\x10\x00\x12\x0e\n\nREPLACE_BZ\x10\x01\x12\x08\n\x04MOVE\x10\x02\x12\n\n\x06\x42SDIFF\x10\x03\x12\x0f\n\x0bSOURCE_COPY\x10\x04\x12\x11\n\rSOURCE_BSDIFF\x10\x05\x12\x08\n\x04ZERO\x10\x06\x12\x0b\n\x07\x44ISCARD\x10\x07\x12\x0e\n\nREPLACE_XZ\x10\x08\x12\x0c\n\x08PUFFDIFF\x10\t\x12\x11\n\rBROTLI_BSDIFF\x10\n\"\xa6\x03\n\x0fPartitionUpdate\x12\x16\n\x0epartition_name\x18\x01 \x02(\t\x12\x17\n\x0frun_postinstall\x18\x02 \x01(\x08\x12\x18\n\x10postinstall_path\x18\x03 \x01(\t\x12\x17\n\x0f\x66ilesystem_type\x18\x04 \x01(\t\x12M\n\x17new_partition_signature\x18\x05 \x03(\x0b\x32,.chromeos_update_engine.Signatures.Signature\x12\x41\n\x12old_partition_info\x18\x06 \x01(\x0b\x32%.chromeos_update_engine.PartitionInfo\x12\x41\n\x12new_partition_info\x18\x07 \x01(\x0b\x32%.chromeos_update_engine.PartitionInfo\x12<\n\noperations\x18\x08 \x03(\x0b\x32(.chromeos_update_engine.InstallOperation\x12\x1c\n\x14postinstall_optional\x18\t \x01(\x08\"\xc4\x05\n\x14\x44\x65ltaArchiveManifest\x12\x44\n\x12install_operations\x18\x01 \x03(\x0b\x32(.chromeos_update_engine.InstallOperation\x12K\n\x19kernel_install_operations\x18\x02 \x03(\x0b\x32(.chromeos_update_engine.InstallOperation\x12\x18\n\nblock_size\x18\x03 \x01(\r:\x04\x34\x30\x39\x36\x12\x19\n\x11signatures_offset\x18\x04 \x01(\x04\x12\x17\n\x0fsignatures_size\x18\x05 \x01(\x04\x12>\n\x0fold_kernel_info\x18\x06 \x01(\x0b\x32%.chromeos_update_engine.PartitionInfo\x12>\n\x0fnew_kernel_info\x18\x07 \x01(\x0b\x32%.chromeos_update_engine.PartitionInfo\x12>\n\x0fold_rootfs_info\x18\x08 \x01(\x0b\x32%.chromeos_update_engine.PartitionInfo\x12>\n\x0fnew_rootfs_info\x18\t \x01(\x0b\x32%.chromeos_update_engine.PartitionInfo\x12\x39\n\x0eold_image_info\x18\n \x01(\x0b\x32!.chromeos_update_engine.ImageInfo\x12\x39\n\x0enew_image_info\x18\x0b \x01(\x0b\x32!.chromeos_update_engine.ImageInfo\x12\x18\n\rminor_version\x18\x0c \x01(\r:\x01\x30\x12;\n\npartitions\x18\r \x03(\x0b\x32\'.chromeos_update_engine.PartitionUpdateB\x02H\x03')
 
 
 
@@ -63,11 +63,15 @@
       name='PUFFDIFF', index=9, number=9,
       options=None,
       type=None),
+    _descriptor.EnumValueDescriptor(
+      name='BROTLI_BSDIFF', index=10, number=10,
+      options=None,
+      type=None),
   ],
   containing_type=None,
   options=None,
   serialized_start=712,
-  serialized_end=858,
+  serialized_end=877,
 )
 
 
@@ -347,7 +351,7 @@
   is_extendable=False,
   extension_ranges=[],
   serialized_start=391,
-  serialized_end=858,
+  serialized_end=877,
 )
 
 
@@ -430,8 +434,8 @@
   options=None,
   is_extendable=False,
   extension_ranges=[],
-  serialized_start=861,
-  serialized_end=1283,
+  serialized_start=880,
+  serialized_end=1302,
 )
 
 
@@ -542,8 +546,8 @@
   options=None,
   is_extendable=False,
   extension_ranges=[],
-  serialized_start=1286,
-  serialized_end=1994,
+  serialized_start=1305,
+  serialized_end=2013,
 )
 
 _SIGNATURES_SIGNATURE.containing_type = _SIGNATURES;
diff --git a/update_metadata.proto b/update_metadata.proto
index c5b2ed4..9175c42 100644
--- a/update_metadata.proto
+++ b/update_metadata.proto
@@ -170,6 +170,7 @@
 
     // On minor version 4 or newer, these operations are supported:
     PUFFDIFF = 9;  // The data is in puffdiff format.
+    BROTLI_BSDIFF = 10;  // Like SOURCE_BSDIFF, but compressed with brotli.
   }
   required Type type = 1;
   // The offset into the delta file (after the protobuf)