diff --git a/payload_generator/bzip.cc b/payload_generator/bzip.cc
index 9040193..c2388ca 100644
--- a/payload_generator/bzip.cc
+++ b/payload_generator/bzip.cc
@@ -24,63 +24,32 @@
 
 #include "update_engine/common/utils.h"
 
-using std::string;
-
 namespace chromeos_update_engine {
 
-namespace {
-
-// BzipData compresses or decompresses the input to the output.
-// Returns true on success.
-// Use one of BzipBuffToBuff*ompress as the template parameter to BzipData().
-int BzipBuffToBuffDecompress(uint8_t* out,
-                             uint32_t* out_length,
-                             const void* in,
-                             uint32_t in_length) {
-  return BZ2_bzBuffToBuffDecompress(
-      reinterpret_cast<char*>(out),
-      out_length,
-      reinterpret_cast<char*>(const_cast<void*>(in)),
-      in_length,
-      0,  // Silent verbosity
-      0);  // Normal algorithm
-}
-
-int BzipBuffToBuffCompress(uint8_t* out,
-                           uint32_t* out_length,
-                           const void* in,
-                           uint32_t in_length) {
-  return BZ2_bzBuffToBuffCompress(
-      reinterpret_cast<char*>(out),
-      out_length,
-      reinterpret_cast<char*>(const_cast<void*>(in)),
-      in_length,
-      9,  // Best compression
-      0,  // Silent verbosity
-      0);  // Default work factor
-}
-
-template<int F(uint8_t* out,
-               uint32_t* out_length,
-               const void* in,
-               uint32_t in_length)>
-bool BzipData(const void* const in,
-              const size_t in_size,
-              brillo::Blob* const out) {
+bool BzipCompress(const brillo::Blob& in, brillo::Blob* out) {
   TEST_AND_RETURN_FALSE(out);
   out->clear();
-  if (in_size == 0) {
+  if (in.size() == 0)
     return true;
-  }
-  // Try increasing buffer size until it works
-  size_t buf_size = in_size;
+
+  // We expect a compression ratio of about 35% with bzip2, so we start with
+  // that much output space, which will then be doubled if needed.
+  size_t buf_size = 40 + in.size() * 35 / 100;
   out->resize(buf_size);
 
+  // Try increasing buffer size until it works
   for (;;) {
     if (buf_size > std::numeric_limits<uint32_t>::max())
       return false;
     uint32_t data_size = buf_size;
-    int rc = F(out->data(), &data_size, in, in_size);
+    int rc = BZ2_bzBuffToBuffCompress(
+        reinterpret_cast<char*>(out->data()),
+        &data_size,
+        reinterpret_cast<char*>(const_cast<uint8_t*>(in.data())),
+        in.size(),
+        9,   // Best compression
+        0,   // Silent verbosity
+        0);  // Default work factor
     TEST_AND_RETURN_FALSE(rc == BZ_OUTBUFF_FULL || rc == BZ_OK);
     if (rc == BZ_OK) {
       // we're done!
@@ -94,37 +63,4 @@
   }
 }
 
-}  // namespace
-
-bool BzipDecompress(const brillo::Blob& in, brillo::Blob* out) {
-  return BzipData<BzipBuffToBuffDecompress>(in.data(), in.size(), out);
-}
-
-bool BzipCompress(const brillo::Blob& in, brillo::Blob* out) {
-  return BzipData<BzipBuffToBuffCompress>(in.data(), in.size(), out);
-}
-
-namespace {
-template<bool F(const void* const in,
-                const size_t in_size,
-                brillo::Blob* const out)>
-bool BzipString(const string& str,
-                brillo::Blob* out) {
-  TEST_AND_RETURN_FALSE(out);
-  brillo::Blob temp;
-  TEST_AND_RETURN_FALSE(F(str.data(), str.size(), &temp));
-  out->clear();
-  out->insert(out->end(), temp.begin(), temp.end());
-  return true;
-}
-}  // namespace
-
-bool BzipCompressString(const string& str, brillo::Blob* out) {
-  return BzipString<BzipData<BzipBuffToBuffCompress>>(str, out);
-}
-
-bool BzipDecompressString(const string& str, brillo::Blob* out) {
-  return BzipString<BzipData<BzipBuffToBuffDecompress>>(str, out);
-}
-
 }  // namespace chromeos_update_engine
diff --git a/payload_generator/bzip.h b/payload_generator/bzip.h
index ca9956e..198768f 100644
--- a/payload_generator/bzip.h
+++ b/payload_generator/bzip.h
@@ -17,18 +17,12 @@
 #ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_BZIP_H_
 #define UPDATE_ENGINE_PAYLOAD_GENERATOR_BZIP_H_
 
-#include <string>
-#include <vector>
-
 #include <brillo/secure_blob.h>
 
 namespace chromeos_update_engine {
 
-// Bzip2 compresses or decompresses str/in to out.
-bool BzipDecompress(const brillo::Blob& in, brillo::Blob* out);
+// Compresses the input buffer |in| into |out| with bzip2.
 bool BzipCompress(const brillo::Blob& in, brillo::Blob* out);
-bool BzipCompressString(const std::string& str, brillo::Blob* out);
-bool BzipDecompressString(const std::string& str, brillo::Blob* out);
 
 }  // namespace chromeos_update_engine
 
diff --git a/payload_generator/generate_delta_main.cc b/payload_generator/generate_delta_main.cc
index f4ea884..f1fcad5 100644
--- a/payload_generator/generate_delta_main.cc
+++ b/payload_generator/generate_delta_main.cc
@@ -39,6 +39,7 @@
 #include "update_engine/payload_generator/delta_diff_utils.h"
 #include "update_engine/payload_generator/payload_generation_config.h"
 #include "update_engine/payload_generator/payload_signer.h"
+#include "update_engine/payload_generator/xz.h"
 #include "update_engine/update_metadata.pb.h"
 
 // This file contains a simple program that takes an old path, a new path,
@@ -367,6 +368,9 @@
 
   logging::InitLogging(log_settings);
 
+  // Initialize the Xz compressor.
+  XzCompressInit();
+
   vector<int> signature_sizes;
   ParseSignatureSizes(FLAGS_signature_size, &signature_sizes);
 
diff --git a/payload_generator/xz.h b/payload_generator/xz.h
new file mode 100644
index 0000000..6e0a26c
--- /dev/null
+++ b/payload_generator/xz.h
@@ -0,0 +1,34 @@
+//
+// Copyright (C) 2016 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.
+//
+
+#ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_XZ_H_
+#define UPDATE_ENGINE_PAYLOAD_GENERATOR_XZ_H_
+
+#include <brillo/secure_blob.h>
+
+namespace chromeos_update_engine {
+
+// Initialize the xz compression unit. Call once before any call to
+// XzCompress().
+void XzCompressInit();
+
+// Compresses the input buffer |in| into |out| with xz. The compressed stream
+// will be the equivalent of running xz -9 --check=none
+bool XzCompress(const brillo::Blob& in, brillo::Blob* out);
+
+}  // namespace chromeos_update_engine
+
+#endif  // UPDATE_ENGINE_PAYLOAD_GENERATOR_XZ_H_
diff --git a/payload_generator/xz_android.cc b/payload_generator/xz_android.cc
new file mode 100644
index 0000000..f3b836d
--- /dev/null
+++ b/payload_generator/xz_android.cc
@@ -0,0 +1,116 @@
+//
+// Copyright (C) 2016 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.
+//
+
+#include "update_engine/payload_generator/xz.h"
+
+#include <7zCrc.h>
+#include <Xz.h>
+#include <XzEnc.h>
+
+#include <algorithm>
+
+#include <base/logging.h>
+
+namespace {
+
+bool xz_initialized = false;
+
+// An ISeqInStream implementation that reads all the data from the passed Blob.
+struct BlobReaderStream : public ISeqInStream {
+  explicit BlobReaderStream(const brillo::Blob& data) : data_(data) {
+    Read = &BlobReaderStream::ReadStatic;
+  }
+
+  static SRes ReadStatic(void* p, void* buf, size_t* size) {
+    auto* self =
+        static_cast<BlobReaderStream*>(reinterpret_cast<ISeqInStream*>(p));
+    *size = std::min(*size, self->data_.size() - self->pos_);
+    memcpy(buf, self->data_.data() + self->pos_, *size);
+    self->pos_ += *size;
+    return SZ_OK;
+  }
+
+  const brillo::Blob& data_;
+
+  // The current reader position.
+  size_t pos_ = 0;
+};
+
+// An ISeqOutStream implementation that writes all the data to the passed Blob.
+struct BlobWriterStream : public ISeqOutStream {
+  explicit BlobWriterStream(brillo::Blob* data) : data_(data) {
+    Write = &BlobWriterStream::WriteStatic;
+  }
+
+  static size_t WriteStatic(void* p, const void* buf, size_t size) {
+    auto* self =
+        static_cast<BlobWriterStream*>(reinterpret_cast<ISeqOutStream*>(p));
+    const uint8_t* buffer = reinterpret_cast<const uint8_t*>(buf);
+    self->data_->reserve(self->data_->size() + size);
+    self->data_->insert(self->data_->end(), buffer, buffer + size);
+    return size;
+  }
+
+  brillo::Blob* data_;
+};
+
+}  // namespace
+
+namespace chromeos_update_engine {
+
+void XzCompressInit() {
+  if (xz_initialized)
+    return;
+  xz_initialized = true;
+  // Although we don't include a CRC32 for the stream, the xz file header has
+  // a CRC32 of the header itself, which required the CRC table to be
+  // initialized.
+  CrcGenerateTable();
+}
+
+bool XzCompress(const brillo::Blob& in, brillo::Blob* out) {
+  CHECK(xz_initialized) << "Initialize XzCompress first";
+  out->clear();
+  if (in.empty())
+    return true;
+
+  // Xz compression properties.
+  CXzProps props;
+  XzProps_Init(&props);
+  // No checksum in the xz stream. xz-embedded (used by the decompressor) only
+  // supports CRC32, but we already check the sha-1 of the whole blob during
+  // payload application.
+  props.checkId = XZ_CHECK_NO;
+
+  // LZMA2 compression properties.
+  CLzma2EncProps lzma2Props;
+  props.lzma2Props = &lzma2Props;
+  Lzma2EncProps_Init(&lzma2Props);
+  // LZMA compression "level 6" requires 9 MB of RAM to decompress in the worst
+  // case.
+  lzma2Props.lzmaProps.level = 6;
+  lzma2Props.lzmaProps.numThreads = 1;
+  // The input size data is used to reduce the dictionary size if possible.
+  lzma2Props.lzmaProps.reduceSize = in.size();
+  Lzma2EncProps_Normalize(&lzma2Props);
+
+  BlobWriterStream out_writer(out);
+  BlobReaderStream in_reader(in);
+  SRes res = Xz_Encode(&out_writer, &in_reader, &props, nullptr /* progress */);
+  return res == SZ_OK;
+}
+
+}  // namespace chromeos_update_engine
diff --git a/payload_generator/xz_chromeos.cc b/payload_generator/xz_chromeos.cc
new file mode 100644
index 0000000..a8cda4e
--- /dev/null
+++ b/payload_generator/xz_chromeos.cc
@@ -0,0 +1,28 @@
+//
+// Copyright (C) 2016 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.
+//
+
+#include "update_engine/payload_generator/xz.h"
+
+namespace chromeos_update_engine {
+
+void XzCompressInit() {}
+
+bool XzCompress(const brillo::Blob& in, brillo::Blob* out) {
+  // No Xz compressor implementation in Chrome OS delta_generator builds.
+  return false;
+}
+
+}  // namespace chromeos_update_engine
diff --git a/payload_generator/zip_unittest.cc b/payload_generator/zip_unittest.cc
index 0c95a8f..c38f8b8 100644
--- a/payload_generator/zip_unittest.cc
+++ b/payload_generator/zip_unittest.cc
@@ -20,10 +20,15 @@
 #include <string>
 #include <vector>
 
+#include <brillo/make_unique_ptr.h>
 #include <gtest/gtest.h>
 
 #include "update_engine/common/test_utils.h"
+#include "update_engine/payload_consumer/bzip_extent_writer.h"
+#include "update_engine/payload_consumer/extent_writer.h"
+#include "update_engine/payload_consumer/xz_extent_writer.h"
 #include "update_engine/payload_generator/bzip.h"
+#include "update_engine/payload_generator/xz.h"
 
 using chromeos_update_engine::test_utils::kRandomString;
 using std::string;
@@ -31,13 +36,55 @@
 
 namespace chromeos_update_engine {
 
+namespace {
+
+// ExtentWriter class that writes to memory, used to test the decompression
+// step with the corresponding extent writer.
+class MemoryExtentWriter : public ExtentWriter {
+ public:
+  // Creates the ExtentWriter that will write all the bytes to the passed |data|
+  // blob.
+  explicit MemoryExtentWriter(brillo::Blob* data) : data_(data) {
+    data_->clear();
+  }
+  ~MemoryExtentWriter() override = default;
+
+  bool Init(FileDescriptorPtr fd,
+            const vector<Extent>& extents,
+            uint32_t block_size) override {
+    return true;
+  }
+  bool Write(const void* bytes, size_t count) override {
+    data_->reserve(data_->size() + count);
+    data_->insert(data_->end(),
+                  static_cast<const uint8_t*>(bytes),
+                  static_cast<const uint8_t*>(bytes) + count);
+    return true;
+  }
+  bool EndImpl() override { return true; }
+
+ private:
+  brillo::Blob* data_;
+};
+
+template <typename W>
+bool DecompressWithWriter(const brillo::Blob& in, brillo::Blob* out) {
+  std::unique_ptr<ExtentWriter> writer(
+      new W(brillo::make_unique_ptr(new MemoryExtentWriter(out))));
+  // Init() parameters are ignored by the testing MemoryExtentWriter.
+  TEST_AND_RETURN_FALSE(writer->Init(nullptr, {}, 1));
+  TEST_AND_RETURN_FALSE(writer->Write(in.data(), in.size()));
+  TEST_AND_RETURN_FALSE(writer->End());
+  return true;
+}
+
+}  // namespace
+
 template <typename T>
 class ZipTest : public ::testing::Test {
  public:
-  bool ZipDecompress(const brillo::Blob& in, brillo::Blob* out) const = 0;
   bool ZipCompress(const brillo::Blob& in, brillo::Blob* out) const = 0;
-  bool ZipCompressString(const string& str, brillo::Blob* out) const = 0;
-  bool ZipDecompressString(const string& str, brillo::Blob* out) const = 0;
+  bool ZipDecompress(const brillo::Blob& in, brillo::Blob* out) const = 0;
 };
 
 class BzipTest {};
@@ -45,34 +92,47 @@
 template <>
 class ZipTest<BzipTest> : public ::testing::Test {
  public:
-  bool ZipDecompress(const brillo::Blob& in, brillo::Blob* out) const {
-    return BzipDecompress(in, out);
-  }
   bool ZipCompress(const brillo::Blob& in, brillo::Blob* out) const {
     return BzipCompress(in, out);
   }
-  bool ZipCompressString(const string& str, brillo::Blob* out) const {
-    return BzipCompressString(str, out);
-  }
-  bool ZipDecompressString(const string& str, brillo::Blob* out) const {
-    return BzipDecompressString(str, out);
+  bool ZipDecompress(const brillo::Blob& in, brillo::Blob* out) const {
+    return DecompressWithWriter<BzipExtentWriter>(in, out);
   }
 };
 
+class XzTest {};
+
+template <>
+class ZipTest<XzTest> : public ::testing::Test {
+ public:
+  bool ZipCompress(const brillo::Blob& in, brillo::Blob* out) const {
+    return XzCompress(in, out);
+  }
+  bool ZipDecompress(const brillo::Blob& in, brillo::Blob* out) const {
+    return DecompressWithWriter<XzExtentWriter>(in, out);
+  }
+};
+
+#ifdef __ANDROID__
+typedef ::testing::Types<BzipTest, XzTest> ZipTestTypes;
+#else
+// Chrome OS implementation of Xz compressor just returns false.
 typedef ::testing::Types<BzipTest> ZipTestTypes;
+#endif  // __ANDROID__
+
 TYPED_TEST_CASE(ZipTest, ZipTestTypes);
 
-
-
 TYPED_TEST(ZipTest, SimpleTest) {
-  string in("this should compress well xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
-            "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
-            "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
-            "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
-            "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
-            "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx");
+  string in_str(
+      "this should compress well xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
+      "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
+      "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
+      "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
+      "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
+      "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx");
+  brillo::Blob in(in_str.begin(), in_str.end());
   brillo::Blob out;
-  EXPECT_TRUE(this->ZipCompressString(in, &out));
+  EXPECT_TRUE(this->ZipCompress(in, &out));
   EXPECT_LT(out.size(), in.size());
   EXPECT_GT(out.size(), 0U);
   brillo::Blob decompressed;
@@ -82,32 +142,29 @@
 }
 
 TYPED_TEST(ZipTest, PoorCompressionTest) {
-  string in(reinterpret_cast<const char*>(kRandomString),
-            sizeof(kRandomString));
+  brillo::Blob in(std::begin(kRandomString), std::end(kRandomString));
   brillo::Blob out;
-  EXPECT_TRUE(this->ZipCompressString(in, &out));
+  EXPECT_TRUE(this->ZipCompress(in, &out));
   EXPECT_GT(out.size(), in.size());
-  string out_string(out.begin(), out.end());
   brillo::Blob decompressed;
-  EXPECT_TRUE(this->ZipDecompressString(out_string, &decompressed));
+  EXPECT_TRUE(this->ZipDecompress(out, &decompressed));
   EXPECT_EQ(in.size(), decompressed.size());
-  EXPECT_TRUE(!memcmp(in.data(), decompressed.data(), in.size()));
+  EXPECT_EQ(in, decompressed);
 }
 
 TYPED_TEST(ZipTest, MalformedZipTest) {
-  string in(reinterpret_cast<const char*>(kRandomString),
-            sizeof(kRandomString));
+  brillo::Blob in(std::begin(kRandomString), std::end(kRandomString));
   brillo::Blob out;
-  EXPECT_FALSE(this->ZipDecompressString(in, &out));
+  EXPECT_FALSE(this->ZipDecompress(in, &out));
 }
 
 TYPED_TEST(ZipTest, EmptyInputsTest) {
-  string in;
+  brillo::Blob in;
   brillo::Blob out;
-  EXPECT_TRUE(this->ZipDecompressString(in, &out));
+  EXPECT_TRUE(this->ZipDecompress(in, &out));
   EXPECT_EQ(0U, out.size());
 
-  EXPECT_TRUE(this->ZipCompressString(in, &out));
+  EXPECT_TRUE(this->ZipCompress(in, &out));
   EXPECT_EQ(0U, out.size());
 }