diff --git a/Android.mk b/Android.mk
index 8658fb9..6cde546 100644
--- a/Android.mk
+++ b/Android.mk
@@ -733,6 +733,7 @@
     payload_generator/graph_types.cc \
     payload_generator/graph_utils.cc \
     payload_generator/inplace_generator.cc \
+    payload_generator/mapfile_filesystem.cc \
     payload_generator/payload_file.cc \
     payload_generator/payload_generation_config.cc \
     payload_generator/payload_signer.cc \
@@ -1063,6 +1064,7 @@
     payload_generator/full_update_generator_unittest.cc \
     payload_generator/graph_utils_unittest.cc \
     payload_generator/inplace_generator_unittest.cc \
+    payload_generator/mapfile_filesystem_unittest.cc \
     payload_generator/payload_file_unittest.cc \
     payload_generator/payload_generation_config_unittest.cc \
     payload_generator/payload_signer_unittest.cc \
diff --git a/payload_generator/delta_diff_generator.cc b/payload_generator/delta_diff_generator.cc
index a140d21..1db2144 100644
--- a/payload_generator/delta_diff_generator.cc
+++ b/payload_generator/delta_diff_generator.cc
@@ -92,10 +92,7 @@
 
       // Select payload generation strategy based on the config.
       unique_ptr<OperationsGenerator> strategy;
-      // We don't efficiently support deltas on squashfs. For now, we will
-      // produce full operations in that case.
-      if (!old_part.path.empty() &&
-          !diff_utils::IsSquashfs4Filesystem(new_part.path)) {
+      if (!old_part.path.empty()) {
         // Delta update.
         if (config.version.minor == kInPlaceMinorPayloadVersion) {
           LOG(INFO) << "Using generator InplaceGenerator().";
diff --git a/payload_generator/delta_diff_utils.cc b/payload_generator/delta_diff_utils.cc
index 077a48b..80c0287 100644
--- a/payload_generator/delta_diff_utils.cc
+++ b/payload_generator/delta_diff_utils.cc
@@ -802,32 +802,6 @@
   return true;
 }
 
-bool IsSquashfs4Filesystem(const string& device) {
-  brillo::Blob header;
-  // See fs/squashfs/squashfs_fs.h for format details. We only support
-  // Squashfs 4.x little endian.
-
-  // The first 96 is enough to read the squashfs superblock.
-  const ssize_t kSquashfsSuperBlockSize = 96;
-  if (!utils::ReadFileChunk(device, 0, kSquashfsSuperBlockSize, &header) ||
-      header.size() < kSquashfsSuperBlockSize)
-    return false;
-
-  // Check magic, squashfs_fs.h: SQUASHFS_MAGIC
-  if (memcmp(header.data(), "hsqs", 4) != 0)
-    return false;  // Only little endian is supported.
-
-  // squashfs_fs.h: struct squashfs_super_block.s_major
-  uint16_t s_major = *reinterpret_cast<const uint16_t*>(
-      header.data() + 5 * sizeof(uint32_t) + 4 * sizeof(uint16_t));
-
-  if (s_major != 4) {
-    LOG(ERROR) << "Found unsupported squashfs major version " << s_major;
-    return false;
-  }
-  return true;
-}
-
 }  // namespace diff_utils
 
 }  // namespace chromeos_update_engine
diff --git a/payload_generator/delta_diff_utils.h b/payload_generator/delta_diff_utils.h
index 4cc85fc..7254bca 100644
--- a/payload_generator/delta_diff_utils.h
+++ b/payload_generator/delta_diff_utils.h
@@ -143,11 +143,6 @@
 // false.
 bool IsExtFilesystem(const std::string& device);
 
-// Returns whether the filesystem is a squashfs4 filesystem. In case of failure,
-// such as if the file |device| doesn't exists or can't be read, it returns
-// false.
-bool IsSquashfs4Filesystem(const std::string& device);
-
 }  // namespace diff_utils
 
 }  // namespace chromeos_update_engine
diff --git a/payload_generator/delta_diff_utils_unittest.cc b/payload_generator/delta_diff_utils_unittest.cc
index 7044b95..232eab7 100644
--- a/payload_generator/delta_diff_utils_unittest.cc
+++ b/payload_generator/delta_diff_utils_unittest.cc
@@ -40,43 +40,6 @@
 
 namespace {
 
-// Squashfs example filesystem, generated with:
-//   echo hola>hola
-//   mksquashfs hola hola.sqfs -noappend -nopad
-//   hexdump hola.sqfs -e '16/1 "%02x, " "\n"'
-const uint8_t kSquashfsFile[] = {
-  0x68, 0x73, 0x71, 0x73, 0x02, 0x00, 0x00, 0x00,  // magic, inodes
-  0x3e, 0x49, 0x61, 0x54, 0x00, 0x00, 0x02, 0x00,
-  0x01, 0x00, 0x00, 0x00, 0x01, 0x00, 0x11, 0x00,
-  0xc0, 0x00, 0x02, 0x00, 0x04, 0x00, 0x00, 0x00,  // flags, noids, major, minor
-  0x20, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,  // root_inode
-  0xef, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,  // bytes_used
-  0xe7, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
-  0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
-  0x65, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
-  0x93, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
-  0xbd, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
-  0xd5, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
-  0x68, 0x6f, 0x6c, 0x61, 0x0a, 0x2c, 0x00, 0x78,
-  0xda, 0x63, 0x62, 0x58, 0xc2, 0xc8, 0xc0, 0xc0,
-  0xc8, 0xd0, 0x6b, 0x91, 0x18, 0x02, 0x64, 0xa0,
-  0x00, 0x56, 0x06, 0x90, 0xcc, 0x7f, 0xb0, 0xbc,
-  0x9d, 0x67, 0x62, 0x08, 0x13, 0x54, 0x1c, 0x44,
-  0x4b, 0x03, 0x31, 0x33, 0x10, 0x03, 0x00, 0xb5,
-  0x87, 0x04, 0x89, 0x16, 0x00, 0x78, 0xda, 0x63,
-  0x60, 0x80, 0x00, 0x46, 0x28, 0xcd, 0xc4, 0xc0,
-  0xcc, 0x90, 0x91, 0x9f, 0x93, 0x08, 0x00, 0x04,
-  0x70, 0x01, 0xab, 0x10, 0x80, 0x60, 0x00, 0x00,
-  0x00, 0x00, 0x00, 0x00, 0x00, 0x05, 0x00, 0x00,
-  0x01, 0x00, 0x00, 0x00, 0x00, 0xab, 0x00, 0x00,
-  0x00, 0x00, 0x00, 0x00, 0x00, 0x0e, 0x00, 0x78,
-  0xda, 0x63, 0x60, 0x80, 0x00, 0x05, 0x28, 0x0d,
-  0x00, 0x01, 0x10, 0x00, 0x21, 0xc5, 0x00, 0x00,
-  0x00, 0x00, 0x00, 0x00, 0x00, 0x08, 0x80, 0x99,
-  0xcd, 0x02, 0x00, 0x88, 0x13, 0x00, 0x00, 0xdd,
-  0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
-};
-
 // Writes the |data| in the blocks specified by |extents| on the partition
 // |part_path|. The |data| size could be smaller than the size of the blocks
 // passed.
@@ -748,26 +711,4 @@
       test_utils::GetBuildArtifactsPath("gen/disk_ext2_4k.img")));
 }
 
-TEST_F(DeltaDiffUtilsTest, IsSquashfs4FilesystemTest) {
-  uint8_t buffer[sizeof(kSquashfsFile)];
-  memcpy(buffer, kSquashfsFile, sizeof(kSquashfsFile));
-  string img;
-  EXPECT_TRUE(utils::MakeTempFile("img.XXXXXX", &img, nullptr));
-  ScopedPathUnlinker img_unlinker(img);
-
-  // Not enough bytes passed.
-  EXPECT_TRUE(utils::WriteFile(img.c_str(), buffer, 10));
-  EXPECT_FALSE(diff_utils::IsSquashfs4Filesystem(img));
-
-  // The whole file system is passed, which is enough for parsing.
-  EXPECT_TRUE(utils::WriteFile(img.c_str(), buffer, sizeof(kSquashfsFile)));
-  EXPECT_TRUE(diff_utils::IsSquashfs4Filesystem(img));
-
-  // Modify the major version to 5.
-  uint16_t* s_major = reinterpret_cast<uint16_t*>(buffer + 0x1c);
-  *s_major = 5;
-  EXPECT_TRUE(utils::WriteFile(img.c_str(), buffer, sizeof(kSquashfsFile)));
-  EXPECT_FALSE(diff_utils::IsSquashfs4Filesystem(img));
-}
-
 }  // namespace chromeos_update_engine
diff --git a/payload_generator/generate_delta_main.cc b/payload_generator/generate_delta_main.cc
index 99af679..0716c1f 100644
--- a/payload_generator/generate_delta_main.cc
+++ b/payload_generator/generate_delta_main.cc
@@ -20,7 +20,6 @@
 #include <sys/types.h>
 #include <unistd.h>
 
-#include <set>
 #include <string>
 #include <vector>
 
@@ -46,7 +45,6 @@
 // and an output file as arguments and the path to an output file and
 // generates a delta that can be sent to Chrome OS clients.
 
-using std::set;
 using std::string;
 using std::vector;
 
@@ -259,6 +257,17 @@
                 "a single argument with a colon between paths, e.g. "
                 "/path/to/part:/path/to/part2:/path/to/last_part . Path has "
                 "to match the order of partition_names.");
+  DEFINE_string(old_mapfiles,
+                "",
+                "Path to the .map files associated with the partition files "
+                "in the old partition. The .map file is normally generated "
+                "when creating the image in Android builds. Only recommended "
+                "for unsupported filesystem. Pass multiple files separated by "
+                "a colon as with -old_partitions.");
+  DEFINE_string(new_mapfiles,
+                "",
+                "Path to the .map files associated with the partition files "
+                "in the new partition, similar to the -old_mapfiles flag.");
   DEFINE_string(partition_names,
                 string(kLegacyPartitionNameRoot) + ":" +
                 kLegacyPartitionNameKernel,
@@ -404,6 +413,16 @@
   // PayloadGenerationConfig.
   PayloadGenerationConfig payload_config;
   vector<string> partition_names, old_partitions, new_partitions;
+  vector<string> old_mapfiles, new_mapfiles;
+
+  if (!FLAGS_old_mapfiles.empty()) {
+    old_mapfiles = base::SplitString(
+        FLAGS_old_mapfiles, ":", base::TRIM_WHITESPACE, base::SPLIT_WANT_ALL);
+  }
+  if (!FLAGS_new_mapfiles.empty()) {
+    new_mapfiles = base::SplitString(
+        FLAGS_new_mapfiles, ":", base::TRIM_WHITESPACE, base::SPLIT_WANT_ALL);
+  }
 
   partition_names =
       base::SplitString(FLAGS_partition_names, ":", base::TRIM_WHITESPACE,
@@ -448,6 +467,8 @@
         << "Partition name can't be empty, see --partition_names.";
     payload_config.target.partitions.emplace_back(partition_names[i]);
     payload_config.target.partitions.back().path = new_partitions[i];
+    if (i < new_mapfiles.size())
+      payload_config.target.partitions.back().mapfile_path = new_mapfiles[i];
   }
 
   if (payload_config.is_delta) {
@@ -464,6 +485,8 @@
     for (size_t i = 0; i < partition_names.size(); i++) {
       payload_config.source.partitions.emplace_back(partition_names[i]);
       payload_config.source.partitions.back().path = old_partitions[i];
+      if (i < old_mapfiles.size())
+        payload_config.source.partitions.back().mapfile_path = old_mapfiles[i];
     }
   }
 
diff --git a/payload_generator/mapfile_filesystem.cc b/payload_generator/mapfile_filesystem.cc
new file mode 100644
index 0000000..f4f0804
--- /dev/null
+++ b/payload_generator/mapfile_filesystem.cc
@@ -0,0 +1,151 @@
+//
+// 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/mapfile_filesystem.h"
+
+#include <algorithm>
+#include <map>
+
+#include <base/files/file_util.h>
+#include <base/logging.h>
+#include <base/strings/string_number_conversions.h>
+#include <base/strings/string_split.h>
+#include <brillo/make_unique_ptr.h>
+
+#include "update_engine/common/utils.h"
+#include "update_engine/payload_generator/extent_ranges.h"
+#include "update_engine/payload_generator/extent_utils.h"
+#include "update_engine/update_metadata.pb.h"
+
+using std::string;
+using std::vector;
+
+namespace {
+// The .map file is defined in terms of 4K blocks.
+size_t kMapfileBlockSize = 4096;
+}  // namespace
+
+namespace chromeos_update_engine {
+
+std::unique_ptr<MapfileFilesystem> MapfileFilesystem::CreateFromFile(
+    const string& filename, const string& mapfile_filename) {
+  if (filename.empty() || mapfile_filename.empty())
+    return nullptr;
+
+  off_t file_size = utils::FileSize(filename);
+  if (file_size < 0)
+    return nullptr;
+
+  if (file_size % kMapfileBlockSize) {
+    LOG(ERROR) << "Image file " << filename << " has a size of " << file_size
+               << " which is not multiple of " << kMapfileBlockSize;
+    return nullptr;
+  }
+  off_t num_blocks = file_size / kMapfileBlockSize;
+
+  if (!utils::FileExists(mapfile_filename.c_str())) {
+    LOG(ERROR) << "File " << mapfile_filename << " doesn't exist";
+    return nullptr;
+  }
+
+  return brillo::make_unique_ptr(
+      new MapfileFilesystem(mapfile_filename, num_blocks));
+}
+
+MapfileFilesystem::MapfileFilesystem(const string& mapfile_filename,
+                                     off_t num_blocks)
+    : mapfile_filename_(mapfile_filename), num_blocks_(num_blocks) {}
+
+size_t MapfileFilesystem::GetBlockSize() const {
+  return kMapfileBlockSize;
+}
+
+size_t MapfileFilesystem::GetBlockCount() const {
+  return num_blocks_;
+}
+
+bool MapfileFilesystem::GetFiles(vector<File>* files) const {
+  files->clear();
+
+  string file_data;
+  if (!base::ReadFileToString(base::FilePath(mapfile_filename_), &file_data)) {
+    LOG(ERROR) << "Unable to read .map file: " << mapfile_filename_;
+    return false;
+  }
+
+  // Iterate over all the lines in the file and generate one File entry per
+  // line.
+  vector<base::StringPiece> lines = base::SplitStringPiece(
+      file_data, "\n", base::KEEP_WHITESPACE, base::SPLIT_WANT_ALL);
+  for (const base::StringPiece& line : lines) {
+    File mapped_file;
+
+    mapped_file.extents = {};
+    size_t delim, last_delim = line.size();
+    while ((delim = line.rfind(' ', last_delim - 1)) != string::npos) {
+      string blocks =
+          line.substr(delim + 1, last_delim - (delim + 1)).as_string();
+      size_t dash = blocks.find('-', 0);
+      uint64_t block_start, block_end;
+      if (dash == string::npos && base::StringToUint64(blocks, &block_start)) {
+        mapped_file.extents.push_back(ExtentForRange(block_start, 1));
+      } else if (dash != string::npos &&
+                 base::StringToUint64(blocks.substr(0, dash), &block_start) &&
+                 base::StringToUint64(blocks.substr(dash + 1), &block_end)) {
+        if (block_end < block_start) {
+          LOG(ERROR) << "End block " << block_end
+                     << " is smaller than start block " << block_start
+                     << std::endl
+                     << line;
+          return false;
+        }
+        if (block_end > static_cast<uint64_t>(num_blocks_)) {
+          LOG(ERROR) << "The end block " << block_end
+                     << " is past the end of the file of " << num_blocks_
+                     << " blocks" << std::endl
+                     << line;
+          return false;
+        }
+        mapped_file.extents.push_back(
+            ExtentForRange(block_start, block_end - block_start + 1));
+      } else {
+        // If we can't parse N or N-M, we assume the block is actually part of
+        // the name of the file.
+        break;
+      }
+      last_delim = delim;
+    }
+    // We parsed the blocks from the end of the line, so we need to reverse
+    // the Extents in the file.
+    std::reverse(mapped_file.extents.begin(), mapped_file.extents.end());
+
+    if (last_delim == string::npos)
+      continue;
+    mapped_file.name = line.substr(0, last_delim).as_string();
+
+    files->push_back(mapped_file);
+  }
+
+  return true;
+}
+
+bool MapfileFilesystem::LoadSettings(brillo::KeyValueStore* store) const {
+  // Settings not supported in mapfile since the storage format is unknown.
+  LOG(ERROR) << "mapfile doesn't support LoadSettings().";
+  return false;
+}
+
+}  // namespace chromeos_update_engine
diff --git a/payload_generator/mapfile_filesystem.h b/payload_generator/mapfile_filesystem.h
new file mode 100644
index 0000000..fc03c4c
--- /dev/null
+++ b/payload_generator/mapfile_filesystem.h
@@ -0,0 +1,65 @@
+//
+// 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.
+//
+
+// A filesystem parser based on the Android .map files. When generating a
+// filesystem with the Android tools, either squashfs or ext4, a .map file can
+// be generated at the same time with the list of files and the 4K-blocks where
+// the data for those files is located in the filesystem. This class parses this
+// .map text file instead of parsing the structure of the actual filesystem
+// contents.
+
+#ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_MAPFILE_FILESYSTEM_H_
+#define UPDATE_ENGINE_PAYLOAD_GENERATOR_MAPFILE_FILESYSTEM_H_
+
+#include "update_engine/payload_generator/filesystem_interface.h"
+
+#include <memory>
+#include <string>
+#include <vector>
+
+namespace chromeos_update_engine {
+
+class MapfileFilesystem : public FilesystemInterface {
+ public:
+  static std::unique_ptr<MapfileFilesystem> CreateFromFile(
+      const std::string& filename, const std::string& mapfile_filename);
+  virtual ~MapfileFilesystem() = default;
+
+  // FilesystemInterface overrides.
+  size_t GetBlockSize() const override;
+  size_t GetBlockCount() const override;
+
+  // All the generated FilesystemInterface::File are reported as regular files.
+  // Files may overlap with other files in the same block.
+  bool GetFiles(std::vector<File>* files) const override;
+
+  bool LoadSettings(brillo::KeyValueStore* store) const override;
+
+ private:
+  MapfileFilesystem(const std::string& mapfile_filename, off_t num_blocks);
+
+  // The file where the map filesystem is stored.
+  std::string mapfile_filename_;
+
+  // The number of blocks in the filesystem.
+  off_t num_blocks_;
+
+  DISALLOW_COPY_AND_ASSIGN(MapfileFilesystem);
+};
+
+}  // namespace chromeos_update_engine
+
+#endif  // UPDATE_ENGINE_PAYLOAD_GENERATOR_MAPFILE_FILESYSTEM_H_
diff --git a/payload_generator/mapfile_filesystem_unittest.cc b/payload_generator/mapfile_filesystem_unittest.cc
new file mode 100644
index 0000000..36ae3bf
--- /dev/null
+++ b/payload_generator/mapfile_filesystem_unittest.cc
@@ -0,0 +1,134 @@
+//
+// 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/mapfile_filesystem.h"
+
+#include <unistd.h>
+
+#include <map>
+#include <string>
+#include <vector>
+
+#include <base/format_macros.h>
+#include <base/logging.h>
+#include <base/strings/string_number_conversions.h>
+#include <base/strings/string_util.h>
+#include <base/strings/stringprintf.h>
+#include <gtest/gtest.h>
+
+#include "update_engine/common/test_utils.h"
+#include "update_engine/common/utils.h"
+#include "update_engine/payload_generator/extent_ranges.h"
+#include "update_engine/payload_generator/extent_utils.h"
+
+using std::map;
+using std::string;
+using std::unique_ptr;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+namespace {
+
+// Checks that all the blocks in |extents| are in the range [0, total_blocks).
+void ExpectBlocksInRange(const vector<Extent>& extents, uint64_t total_blocks) {
+  for (const Extent& extent : extents) {
+    EXPECT_LE(0U, extent.start_block());
+    EXPECT_LE(extent.start_block() + extent.num_blocks(), total_blocks);
+  }
+}
+
+}  // namespace
+
+class MapfileFilesystemTest : public ::testing::Test {
+ protected:
+  test_utils::ScopedTempFile temp_file_{"mapfile_file.XXXXXX"};
+  test_utils::ScopedTempFile temp_mapfile_{"mapfile_mapfile.XXXXXX"};
+};
+
+TEST_F(MapfileFilesystemTest, EmptyFilesystem) {
+  unique_ptr<MapfileFilesystem> fs = MapfileFilesystem::CreateFromFile(
+      temp_file_.path(), temp_mapfile_.path());
+  ASSERT_NE(nullptr, fs.get());
+
+  EXPECT_EQ(0U, fs->GetBlockCount());
+  // .map files are always 4KiB blocks.
+  EXPECT_EQ(4096U, fs->GetBlockSize());
+}
+
+TEST_F(MapfileFilesystemTest, SeveralFileFormatTest) {
+  string text =
+      "/fileA 1\n"
+      "/fileB 2-4\n"
+      "/fileC 5-6 9 11-12\n"
+      "/file with spaces 14 19\n"
+      "/1234 7\n";
+  test_utils::WriteFileString(temp_mapfile_.path(), text);
+  EXPECT_EQ(0, HANDLE_EINTR(truncate(temp_file_.path().c_str(), 4096 * 20)));
+
+  unique_ptr<MapfileFilesystem> fs = MapfileFilesystem::CreateFromFile(
+      temp_file_.path(), temp_mapfile_.path());
+  ASSERT_NE(nullptr, fs.get());
+
+  vector<FilesystemInterface::File> files;
+  EXPECT_TRUE(fs->GetFiles(&files));
+
+  map<string, FilesystemInterface::File> map_files;
+  for (const auto& file : files) {
+    EXPECT_EQ(map_files.end(), map_files.find(file.name))
+        << "File " << file.name << " repeated in the list.";
+    map_files[file.name] = file;
+    ExpectBlocksInRange(file.extents, fs->GetBlockCount());
+  }
+
+  EXPECT_EQ(map_files["/fileA"].extents,
+            (vector<Extent>{ExtentForRange(1, 1)}));
+  EXPECT_EQ(map_files["/fileB"].extents,
+            (vector<Extent>{ExtentForRange(2, 3)}));
+  EXPECT_EQ(
+      map_files["/fileC"].extents,
+      (vector<Extent>{
+          ExtentForRange(5, 2), ExtentForRange(9, 1), ExtentForRange(11, 2)}));
+  EXPECT_EQ(map_files["/file with spaces"].extents,
+            (vector<Extent>{ExtentForRange(14, 1), ExtentForRange(19, 1)}));
+  EXPECT_EQ(map_files["/1234"].extents, (vector<Extent>{ExtentForRange(7, 1)}));
+}
+
+TEST_F(MapfileFilesystemTest, BlockNumberTooBigTest) {
+  test_utils::WriteFileString(temp_mapfile_.path(), "/some/file 1-4\n");
+  EXPECT_EQ(0, HANDLE_EINTR(truncate(temp_file_.path().c_str(), 4096 * 3)));
+
+  unique_ptr<MapfileFilesystem> fs = MapfileFilesystem::CreateFromFile(
+      temp_file_.path(), temp_mapfile_.path());
+  ASSERT_NE(nullptr, fs.get());
+
+  vector<FilesystemInterface::File> files;
+  EXPECT_FALSE(fs->GetFiles(&files));
+}
+
+TEST_F(MapfileFilesystemTest, EndBeforeStartTest) {
+  test_utils::WriteFileString(temp_mapfile_.path(), "/some/file 2-1\n");
+  EXPECT_EQ(0, HANDLE_EINTR(truncate(temp_file_.path().c_str(), 4096 * 3)));
+
+  unique_ptr<MapfileFilesystem> fs = MapfileFilesystem::CreateFromFile(
+      temp_file_.path(), temp_mapfile_.path());
+  ASSERT_NE(nullptr, fs.get());
+
+  vector<FilesystemInterface::File> files;
+  EXPECT_FALSE(fs->GetFiles(&files));
+}
+
+}  // namespace chromeos_update_engine
diff --git a/payload_generator/payload_generation_config.cc b/payload_generator/payload_generation_config.cc
index 38a72a9..e85d693 100644
--- a/payload_generator/payload_generation_config.cc
+++ b/payload_generator/payload_generation_config.cc
@@ -23,6 +23,7 @@
 #include "update_engine/payload_generator/delta_diff_generator.h"
 #include "update_engine/payload_generator/delta_diff_utils.h"
 #include "update_engine/payload_generator/ext2_filesystem.h"
+#include "update_engine/payload_generator/mapfile_filesystem.h"
 #include "update_engine/payload_generator/raw_filesystem.h"
 
 namespace chromeos_update_engine {
@@ -49,18 +50,24 @@
     fs_interface = Ext2Filesystem::CreateFromFile(path);
     // TODO(deymo): The delta generator algorithm doesn't support a block size
     // different than 4 KiB. Remove this check once that's fixed. b/26972455
-    if (fs_interface)
+    if (fs_interface) {
       TEST_AND_RETURN_FALSE(fs_interface->GetBlockSize() == kBlockSize);
+      return true;
+    }
   }
 
-  if (!fs_interface) {
-    // Fall back to a RAW filesystem.
-    TEST_AND_RETURN_FALSE(size % kBlockSize == 0);
-    fs_interface = RawFilesystem::Create(
-      "<" + name + "-partition>",
-      kBlockSize,
-      size / kBlockSize);
+  if (!mapfile_path.empty()) {
+    fs_interface = MapfileFilesystem::CreateFromFile(path, mapfile_path);
+    if (fs_interface) {
+      TEST_AND_RETURN_FALSE(fs_interface->GetBlockSize() == kBlockSize);
+      return true;
+    }
   }
+
+  // Fall back to a RAW filesystem.
+  TEST_AND_RETURN_FALSE(size % kBlockSize == 0);
+  fs_interface = RawFilesystem::Create(
+      "<" + name + "-partition>", kBlockSize, size / kBlockSize);
   return true;
 }
 
diff --git a/payload_generator/payload_generation_config.h b/payload_generator/payload_generation_config.h
index 373c7cd..8617d14 100644
--- a/payload_generator/payload_generation_config.h
+++ b/payload_generator/payload_generation_config.h
@@ -66,6 +66,11 @@
   // device such as a loop device.
   std::string path;
 
+  // The path to the .map file associated with |path| if any. The .map file is
+  // generated by the Android filesystem generation tools when creating a
+  // filesystem and describes the blocks used by each file.
+  std::string mapfile_path;
+
   // The size of the data in |path|. If rootfs verification is used (verity)
   // this value should match the size of the verity device for the rootfs, and
   // the size of the whole kernel. This value could be smaller than the
diff --git a/scripts/brillo_update_payload b/scripts/brillo_update_payload
index 648936b..fb6b862 100755
--- a/scripts/brillo_update_payload
+++ b/scripts/brillo_update_payload
@@ -187,6 +187,11 @@
 declare -A SRC_PARTITIONS
 declare -A DST_PARTITIONS
 
+# Associative arrays for the .map files associated with each src/dst partition
+# file in SRC_PARTITIONS and DST_PARTITIONS.
+declare -A SRC_PARTITIONS_MAP
+declare -A DST_PARTITIONS_MAP
+
 # List of partition names in order.
 declare -a PARTITIONS_ORDER
 
@@ -434,6 +439,12 @@
       part_file="${temp_raw}"
     fi
 
+    # Extract the .map file (if one is available).
+    part_map_file=$(create_tempfile "${part}.map.XXXXXX")
+    CLEANUP_FILES+=("${part_map_file}")
+    unzip -p "${image}" "IMAGES/${part}.map" >"${part_map_file}" || \
+      part_map_file=""
+
     # delta_generator only supports images multiple of 4 KiB. For target images
     # we pad the data with zeros if needed, but for source images we truncate
     # down the data since the last block of the old image could be padded on
@@ -451,6 +462,7 @@
     fi
 
     eval "${partitions_array}[\"${part}\"]=\"${part_file}\""
+    eval "${partitions_array}_MAP[\"${part}\"]=\"${part_map_file}\""
     echo "Extracted ${partitions_array}[${part}]: ${filesize} bytes"
   done
 }
@@ -481,27 +493,34 @@
   GENERATOR_ARGS=( -out_file="${FLAGS_payload}" )
 
   local part old_partitions="" new_partitions="" partition_names=""
+  local old_mapfiles="" new_mapfiles=""
   for part in "${PARTITIONS_ORDER[@]}"; do
     if [[ -n "${partition_names}" ]]; then
       partition_names+=":"
       new_partitions+=":"
       old_partitions+=":"
+      new_mapfiles+=":"
+      old_mapfiles+=":"
     fi
     partition_names+="${part}"
     new_partitions+="${DST_PARTITIONS[${part}]}"
     old_partitions+="${SRC_PARTITIONS[${part}]:-}"
+    new_mapfiles+="${DST_PARTITIONS_MAP[${part}]:-}"
+    old_mapfiles+="${SRC_PARTITIONS_MAP[${part}]:-}"
   done
 
   # Target image args:
   GENERATOR_ARGS+=(
     -partition_names="${partition_names}"
     -new_partitions="${new_partitions}"
+    -new_mapfiles="${new_mapfiles}"
   )
 
   if [[ "${payload_type}" == "delta" ]]; then
     # Source image args:
     GENERATOR_ARGS+=(
       -old_partitions="${old_partitions}"
+      -old_mapfiles="${old_mapfiles}"
     )
     if [[ -n "${FORCE_MINOR_VERSION}" ]]; then
       GENERATOR_ARGS+=( --minor_version="${FORCE_MINOR_VERSION}" )
diff --git a/update_engine.gyp b/update_engine.gyp
index 38d6ba1..e6ff776 100644
--- a/update_engine.gyp
+++ b/update_engine.gyp
@@ -398,6 +398,7 @@
         'payload_generator/graph_types.cc',
         'payload_generator/graph_utils.cc',
         'payload_generator/inplace_generator.cc',
+        'payload_generator/mapfile_filesystem.cc',
         'payload_generator/payload_file.cc',
         'payload_generator/payload_generation_config.cc',
         'payload_generator/payload_signer.cc',
@@ -542,6 +543,7 @@
             'payload_generator/full_update_generator_unittest.cc',
             'payload_generator/graph_utils_unittest.cc',
             'payload_generator/inplace_generator_unittest.cc',
+            'payload_generator/mapfile_filesystem_unittest.cc',
             'payload_generator/payload_file_unittest.cc',
             'payload_generator/payload_generation_config_unittest.cc',
             'payload_generator/payload_signer_unittest.cc',