LibXDiff

[Оригинальная библиотека]|[Модификация для сборки в CMake]

Библиотека LibXDiff реализует базовые, но при этом полноценные функции для создания различий/патчей как для бинарных, так и для текстовых файлов. Она использует «файлы в памяти» (memory files) как абстракцию для достижения производительности и переносимости.

Для бинарных файлов LibXDiff реализует (с некоторыми изменениями) алгоритмы из статьи File System Support for Delta Compression Джошуа П. МакДональда и Fingerprinting By Random Polynomials Майкла О. Рабина. Для текстовых файлов библиотека следует принципам из статьи Юджина В. Майерса An O(ND) Difference Algorithm and Its Variations.

Файлы в памяти представляют собой набор буферов, хранящих содержимое файла. При передаче их в функции diff/patch есть два разных требования:

• Для текстовых файлов одна строка не должна пересекать границы блоков.
• Для бинарных файлов требуется компактное представление, то есть весь файл хранится в одном блоке.

Функции внутри библиотеки позволяют обеспечить эти условия. Например:

• флаг XDL_MMF_ATOMIC гарантирует, что запись не будет разделена между блоками;
• функции xdl_mmfile_iscompact(), xdl_mmfile_compact() и xdl_mmfile_writeallocate() позволяют проверить, компактен ли файл, и при необходимости создать его компактную версию.

Для текстовых файлов результат выводится в формате unified diff, но без заголовков файлов, так как результат всегда относится к сравнению ровно двух файлов. Вывод бинарных патчей — это собственный двоичный формат, который представляет собой набор команд copy и insert, как описано в статье МакДональда.

Библиотека совместима почти со всеми Unix-системами (через configure) и также поддерживает Windows (через nmake-файлы). Примеры использования можно найти в подкаталоге test дистрибутива, там же есть регрессионный тест: он генерирует случайные данные, выполняет diff и patch, а затем сравнивает результат.

Регрессионные тесты без ошибок работали сутками на Linux, Solaris, FreeBSD и Windows, что даёт основания считать библиотеку готовой к промышленному использованию (несмотря на её версию).