diff --git a/payload_generator/delta_diff_generator.cc b/payload_generator/delta_diff_generator.cc
index 3295df0..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() &&
-          !utils::IsSquashfsFilesystem(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/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 8ef30a0..c7ecca7 100644
--- a/payload_generator/payload_generation_config.cc
+++ b/payload_generator/payload_generation_config.cc
@@ -22,6 +22,7 @@
 #include "update_engine/payload_consumer/delta_performer.h"
 #include "update_engine/payload_generator/delta_diff_generator.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 {
@@ -58,14 +59,18 @@
     fs_interface = Ext2Filesystem::CreateFromFile(path);
   }
 
-  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