Initial implementation of diff file format v2

1 files changed, 370 insertions, 63 deletions

diff --git a/src/backup.cpp b/src/backup.cpp
index bf8bfaf..4a76be5 100644
--- a/src/backup.cpp
+++ b/src/backup.cpp
@@ -1,4 +1,4 @@
-/* Copyright 2021 Ján Sučan <jan@jansucan.com>
+/* Copyright 2024 Ján Sučan <jan@jansucan.com>
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions are
@@ -26,91 +26,398 @@
 
 #include "backup.h"
 #include "buffered_file.h"
+#include "format_v2.h"
 
-#include <cstring>
-#include <fstream>
+#include <algorithm>
+#include <array>
+#include <cassert>
+#include <iostream>
+#include <vector>
 
-static void check_files(const OptionsBackup &opts);
+class Page
+{
+    friend bool operator==(const Page &lhs, const Page &rhs);
+
+  public:
+    Page() : m_start(0), m_end(0){};
+
+    Page(std::shared_ptr<char[]> data, uint64_t start, uint64_t end)
+        : m_data(data), m_start(start), m_end(end)
+    {
+        assert(m_start <= m_end);
+    };
+
+    std::shared_ptr<char[]> getData() const { return m_data; };
+    uint64_t getStart() const { return m_start; };
+    uint64_t getEnd() const { return m_end; };
+    size_t getSize() const { return m_end - m_start; };
+    bool isEmpty() const { return getSize() == 0; };
+
+  private:
+    std::shared_ptr<char[]> m_data;
+    uint64_t m_start;
+    uint64_t m_end;
+};
+
+bool
+operator==(const Page &lhs, const Page &rhs)
+{
+    return (lhs.m_data == rhs.m_data) && (lhs.m_start == rhs.m_start) &&
+           (lhs.m_end == rhs.m_end);
+}
+
+class PagedStreamReader
+{
+  public:
+    PagedStreamReader(std::istream &istr, size_t page_size_bytes)
+        : m_page_size_bytes(page_size_bytes), m_istream(istr),
+          m_stream_pos_bytes(0), m_buffer_index(0)
+    {
+        try {
+            m_buffers[0] = std::shared_ptr<char[]>(new char[m_page_size_bytes]);
+            m_buffers[1] = std::shared_ptr<char[]>(new char[m_page_size_bytes]);
+        } catch (const std::bad_alloc &e) {
+            throw BufferedFileError(
+                "cannot allocate pages for input stream data");
+        }
+    };
+
+    Page getNextPage()
+    {
+        m_buffer_index = (m_buffer_index + 1) % 2;
+        auto buf = m_buffers[m_buffer_index];
+        // Buffer for new data must not in use
+        assert(buf.use_count() == 2);
+
+        const size_t bytes_read{readFromStream(buf.get())};
+        m_stream_pos_bytes += bytes_read;
+
+        if (bytes_read == 0) {
+            buf = std::shared_ptr<char[]>();
+        }
+        return Page{buf, m_stream_pos_bytes - bytes_read, m_stream_pos_bytes};
+    }
+
+  private:
+    const size_t m_page_size_bytes;
+    std::istream &m_istream;
+    uint64_t m_stream_pos_bytes;
+    std::array<std::shared_ptr<char[]>, 2> m_buffers;
+    unsigned m_buffer_index;
+
+    size_t readFromStream(char *const data)
+    {
+        if (m_istream.eof()) {
+            return 0;
+        }
+
+        m_istream.read(data, m_page_size_bytes);
 
-static void
-check_files(const OptionsBackup &opts)
+        if (!m_istream.good() && !m_istream.eof()) {
+            throw BufferedFileError("cannot read from stream");
+        }
+
+        return m_istream.gcount();
+    }
+};
+
+enum class MergeState {
+    Finished,
+    Incomplete,
+};
+
+class Diff
+{
+    friend MergeState diffsTryMerge(Diff &diff_a, Diff &diff_b,
+                                    size_t max_merge_gap, size_t max_size);
+
+  public:
+    explicit Diff(uint64_t start_end)
+        : m_pages{}, m_start{start_end}, m_end{start_end}
+    {
+        assert(m_start <= m_end);
+    };
+    Diff(Page page, uint64_t start, uint64_t end)
+        : m_pages{page}, m_start{start}, m_end{end}
+    {
+        assert(m_start <= m_end);
+    };
+    uint64_t getStart() const { return m_start; };
+    uint64_t getEnd() const { return m_end; };
+    size_t getSize() const { return m_end - m_start; };
+    bool isEmpty() const { return getSize() == 0; };
+
+    std::vector<FormatV2::RecordData> getData() const
+    {
+        std::vector<FormatV2::RecordData> data{};
+
+        if (!m_pages[0].isEmpty() && m_pages[1].isEmpty()) {
+            // Only the first page
+            assert((m_start >= m_pages[0].getStart()) &&
+                   (m_start <= m_pages[0].getEnd()) &&
+                   (m_end >= m_pages[0].getStart()) &&
+                   (m_end <= m_pages[0].getEnd()));
+
+            const uint64_t offset{m_start - m_pages[0].getStart()};
+            auto data_first{std::shared_ptr<char[]>{
+                m_pages[0].getData(),
+                static_cast<char *>(m_pages[0].getData().get()) + offset}};
+            data.push_back(FormatV2::RecordData{getSize(), data_first});
+        } else if (!m_pages[0].isEmpty() && !m_pages[1].isEmpty()) {
+            // Both pages
+            assert((m_start >= m_pages[0].getStart()) &&
+                   (m_start <= m_pages[0].getEnd()) &&
+                   (m_end >= m_pages[1].getStart()) &&
+                   (m_end <= m_pages[1].getEnd()));
+
+            size_t size{m_pages[0].getEnd() - m_start};
+            const uint64_t offset{m_start - m_pages[0].getStart()};
+            auto data_first{std::shared_ptr<char[]>{
+                m_pages[0].getData(),
+                static_cast<char *>(m_pages[0].getData().get()) + offset}};
+            data.push_back(FormatV2::RecordData{size, data_first});
+
+            size = m_end - m_pages[1].getStart();
+            data.push_back(FormatV2::RecordData{size, m_pages[1].getData()});
+        }
+
+        return data;
+    };
+
+  private:
+    std::array<Page, 2> m_pages;
+    uint64_t m_start;
+    uint64_t m_end;
+
+    bool hasPage(size_t i) // cppcheck-suppress unusedPrivateFunction
+    {
+        return (i < m_pages.size()) && (m_pages[i].getData() != nullptr);
+    };
+};
+
+MergeState
+diffsTryMerge(Diff &diff_a, Diff &diff_b, size_t max_merge_gap, size_t max_size)
 {
-    size_t in_size{0};
-    try {
-        in_size = std::filesystem::file_size(opts.getInFilePath());
-    } catch (const std::exception &e) {
-        throw BackupError("cannot get size of input file: " +
-                          std::string(e.what()));
+    if (diff_a.isEmpty()) {
+        // Do not merge to an empty diff
+        return MergeState::Finished;
     }
 
-    size_t base_size{0};
-    try {
-        base_size = std::filesystem::file_size(opts.getBaseFilePath());
-    } catch (const std::exception &e) {
-        throw BackupError("cannot get size of base file: " +
-                          std::string(e.what()));
+    if (diff_b.isEmpty()) {
+        // Nothing to merge from an empty diff
+        return MergeState::Finished;
     }
 
-    /* Check sizes of the input file and the base file */
-    if (in_size != base_size) {
-        throw BackupError("input file and base file differ in size");
-    } else if ((in_size % opts.getSectorSize()) != 0) {
-        throw BackupError(
-            "size of input file and base file is not multiple of " +
-            std::to_string(opts.getSectorSize()));
+    assert(diff_a.getEnd() <= diff_b.getStart());
+    const size_t gap{diff_b.getStart() - diff_a.getEnd()};
+    if (gap > max_merge_gap) {
+        // B is too far away
+        return MergeState::Finished;
     }
+
+    if ((diff_a.getSize() + gap) >= max_size) {
+        // No space in A
+        return MergeState::Finished;
+    }
+
+    // Can be merged
+
+    // Adjust the diff start and end offsets
+
+    // There is always at least 1 byte free in A here
+    const size_t free{max_size - (diff_a.getSize() + gap)};
+    const size_t to_merge{std::min(free, diff_b.getSize())};
+    // There is always at least 1 byte to merge from B here
+
+    // Enlarge A
+    diff_a.m_end += gap + to_merge;
+    // Shrink B
+    diff_b.m_start += to_merge;
+
+    // Add B's page to A if needed
+
+    // Non-empty A must have only the first, or both pages
+    assert(diff_a.hasPage(0));
+    // Non-empty B must have only the first page
+    assert(diff_b.hasPage(0) && !diff_b.hasPage(1));
+
+    // If A has both pages, B's page must only be the same as A's second
+    // page. No setting of pages in A is needed in this case
+    assert(!diff_a.hasPage(1) || (diff_b.m_pages[0] == diff_a.m_pages[1]));
+    if (!diff_a.hasPage(1)) {
+        // If A has only the first page, B's page must only be the same as the
+        // A's first page or following it
+        const bool b_follows{
+            (diff_b.m_pages[0].getData() != diff_a.m_pages[0].getData()) &&
+            (diff_b.m_pages[0].getStart() == diff_a.m_pages[0].getEnd())};
+        assert((diff_b.m_pages[0] == diff_a.m_pages[0]) || b_follows);
+        if (b_follows) {
+            diff_a.m_pages[1] = diff_b.m_pages[0];
+        }
+    }
+
+    return (diff_a.getSize() >= max_size) ? MergeState::Finished
+                                          : MergeState::Incomplete;
 }
 
+class DiffFinder
+{
+  public:
+    DiffFinder(std::istream &old_stream, std::istream &new_stream,
+               uint32_t buffer_size, size_t max_merge_gap)
+        : m_old_page_reader(old_stream, buffer_size),
+          m_new_page_reader(new_stream, buffer_size),
+          m_diff_max_size(buffer_size), m_max_merge_gap(max_merge_gap),
+          m_offset_in_stream(0), m_diff(0),
+          m_search_state(SearchState::ReadPages){};
+
+    Diff findNextDiff()
+    {
+        for (;;) {
+            if (m_search_state == SearchState::ReadPages) {
+                m_old_page = m_old_page_reader.getNextPage();
+                m_new_page = m_new_page_reader.getNextPage();
+                assert(m_old_page.getStart() == m_new_page.getStart());
+
+                if (m_old_page.getSize() != m_new_page.getSize()) {
+                    throw BackupError(
+                        "cannot read the same amount of data from both files");
+                }
+
+                const bool end_of_stream{m_old_page.isEmpty() &&
+                                         m_new_page.isEmpty()};
+                if (end_of_stream) {
+                    const Diff return_diff{m_diff};
+                    m_diff = Diff{m_offset_in_stream};
+                    return return_diff;
+                }
+
+                m_search_state = SearchState::FindDiff;
+
+            } else if (m_search_state == SearchState::FindDiff) {
+                Diff diff{findDiffInPages(m_old_page, m_new_page,
+                                          m_offset_in_stream)};
+                m_offset_in_stream = diff.getEnd();
+
+                if (diff.isEmpty()) {
+                    // End of pages. On the next call, read new pages.
+                    m_old_page = Page{};
+                    m_new_page = Page{};
+                    m_search_state = SearchState::ReadPages;
+                }
+
+                const MergeState merge_state{diffsTryMerge(
+                    m_diff, diff, m_max_merge_gap, m_diff_max_size)};
+
+                if (merge_state == MergeState::Finished) {
+                    const Diff return_diff{m_diff};
+                    m_diff = diff;
+                    if (!return_diff.isEmpty()) {
+                        return return_diff;
+                    }
+                }
+
+            } else {
+                assert(false);
+            }
+        }
+    };
+
+  private:
+    enum class SearchState { ReadPages, FindDiff };
+
+    PagedStreamReader m_old_page_reader;
+    PagedStreamReader m_new_page_reader;
+    const size_t m_diff_max_size;
+    const size_t m_max_merge_gap;
+    Page m_old_page;
+    Page m_new_page;
+    uint64_t m_offset_in_stream;
+    Diff m_diff;
+    SearchState m_search_state;
+
+    Diff findDiffInPages(Page old_page, Page new_page,
+                         uint64_t offset_in_stream)
+    {
+        const char *old_data{old_page.getData().get()};
+        const char *new_data{new_page.getData().get()};
+        const uint64_t data_size_bytes{old_page.getSize()};
+
+        assert(offset_in_stream >= new_page.getStart());
+        size_t offset_in_pages{offset_in_stream - new_page.getStart()};
+
+        // Find offset of the first different byte
+        for (; offset_in_pages < data_size_bytes; ++offset_in_pages) {
+            if (new_data[offset_in_pages] != old_data[offset_in_pages]) {
+                break;
+            }
+        }
+        const size_t start_in_pages{offset_in_pages};
+
+        if (offset_in_pages < data_size_bytes) {
+            // Different byte found. Start searching for a same byte immediately
+            // after.
+            ++offset_in_pages;
+        }
+
+        // Find offset of the first same byte
+        for (; offset_in_pages < data_size_bytes; ++offset_in_pages) {
+            if (new_data[offset_in_pages] == old_data[offset_in_pages]) {
+                break;
+            }
+        }
+        const size_t end_in_pages{offset_in_pages};
+
+        // In the case when no different byte is found, the end offset will be
+        // the same as the start offset
+
+        const uint64_t start_in_stream{new_page.getStart() + start_in_pages};
+        const uint64_t end_in_stream{new_page.getStart() + end_in_pages};
+        if (start_in_stream == end_in_stream) {
+            return Diff{start_in_stream};
+        } else {
+            return Diff{new_page, start_in_stream, end_in_stream};
+        }
+    }
+};
+
 void
 backup(const OptionsBackup &opts)
 {
-    check_files(opts);
-
-    BufferedFileReader in_file(opts.getInFilePath(), opts.getBufferSize());
-    BufferedFileReader base_file(opts.getBaseFilePath(), opts.getBufferSize());
-    BufferedFileWriter out_file(opts.getOutFilePath(), opts.getBufferSize());
+    std::ifstream in_istream{opts.getInFilePath(),
+                             std::ifstream::in | std::ifstream::binary};
+    if (!in_istream) {
+        throw BufferedFileError("cannot open input file");
+    }
 
-    std::unique_ptr<char[]> in_buffer;
-    try {
-        in_buffer = std::make_unique<char[]>(opts.getSectorSize());
-    } catch (const std::bad_alloc &e) {
-        throw BackupError("cannot allocate sector buffer for input file data");
+    std::ifstream base_istream{opts.getBaseFilePath(),
+                               std::ifstream::in | std::ifstream::binary};
+    if (!base_istream) {
+        throw BufferedFileError("cannot open base file");
     }
 
-    std::unique_ptr<char[]> base_buffer;
-    try {
-        base_buffer = std::make_unique<char[]>(opts.getSectorSize());
-    } catch (const std::bad_alloc &e) {
-        throw BackupError("cannot allocate sector buffer for base file data");
+    // When backing up, the output file is truncated to hold the new data
+    std::ofstream out_ostream{opts.getOutFilePath(), std::ofstream::out |
+                                                         std::ofstream::trunc |
+                                                         std::ofstream::binary};
+    if (!out_ostream) {
+        throw BufferedFileError("cannot open output file");
     }
 
-    uint64_t input_file_offset{0};
+    DiffFinder diff_finder(base_istream, in_istream, opts.getBufferSize(),
+                           FormatV2::RecordHeaderSize);
+    FormatV2::Writer diff_writer(out_ostream, opts.getBufferSize());
+
     for (;;) {
-        // Read sectors
-        const size_t in_read_size =
-            in_file.read(in_buffer.get(), opts.getSectorSize());
-        const size_t base_read_size =
-            base_file.read(base_buffer.get(), opts.getSectorSize());
-
-        if (in_read_size != base_read_size) {
-            throw BackupError(
-                "cannot read equal amount of bytes from the input files");
-        } else if (in_read_size == 0) {
+        const Diff diff{diff_finder.findNextDiff()};
+        if (diff.isEmpty()) {
             break;
-        } else if (in_read_size != opts.getSectorSize()) {
-            throw BackupError("cannot read full sectors from the input files");
         }
 
-        // Check for difference
-        const bool differ = (memcmp(in_buffer.get(), base_buffer.get(),
-                                    opts.getSectorSize()) != 0);
-        if (differ) {
-            // Backup sector
-            uint64_t o = htole64(input_file_offset);
-            out_file.write(reinterpret_cast<char *>(&o), sizeof(o));
-            out_file.write(in_buffer.get(), opts.getSectorSize());
-        }
+        diff_writer.writeDiffRecord(diff.getStart(), diff.getSize(),
+                                    diff.getData());
 
-        input_file_offset += opts.getSectorSize();
+        // Here, the diff is destructed and page data reference counters
+        // decremented
     }
 }