问题标签 [patch]

是否有人拥有或知道 C# 中的二进制补丁生成算法实现？

基本上，比较两个文件（指定为old和new），并生成一个补丁文件，该补丁文件可用于升级旧文件以与新文件具有相同的内容。

实施必须相对较快，并且可以处理大量文件。它应该展示 O(n) 或 O(logn) 运行时。

我自己的算法要么很糟糕（快速但产生巨大的补丁），要么很慢（产生小补丁但运行时间为 O(n^2)）。

任何建议或实施指针都会很好。

具体来说，该实现将用于为我们拥有一台主服务器的各种大型数据文件保持服务器同步。当主服务器数据文件发生变化时，我们也需要更新几个异地服务器。

我做过的最天真的算法，它只适用于可以保存在内存中的文件，如下所示：

1. 从旧文件中获取前四个字节，称之为密钥
2. 将这些字节添加到字典中，其中key -> position，其中position是我抓取这 4 个字节的位置，以 0 开头
3. 跳过这四个字节中的第一个，抓取另外 4 个（3 个重叠，1 个），并以相同的方式添加到字典中
4. 对旧文件中的所有 4 字节块重复步骤 1-3
5. 从新文件的开头，抓取 4 个字节，并尝试在字典中查找它
6. 如果找到，则通过比较两个文件中的字节数，找到最长的匹配项（如果有多个）
7. 在旧文件中编码对该位置的引用，并跳过新文件中的匹配块
8. 如果未找到，则从新文件中编码 1 个字节，然后跳过它
9. 对新文件的其余部分重复步骤 5-8

这有点像压缩，没有开窗，所以会占用大量内存。但是，只要我尝试使代码输出最小化，它就相当快，并且会产生很小的补丁。

一种更节省内存的算法使用窗口，但会产生更大的补丁文件。

我在这篇文章中跳过了上述算法的更多细微差别，但如有必要，我可以发布更多细节。然而，我确实觉得我需要一个完全不同的算法，所以对上述算法的改进可能不会让我走得足够远。

编辑＃1：这是对上述算法的更详细描述。

首先，合并这两个文件，这样你就有了一个大文件。记住两个文件之间的切入点。

其次，抓取 4 个字节并将它们的位置添加到整个文件中所有内容的字典步骤中。

第三，从新文件开始的地方开始循环，尝试定位现有的 4 个字节组合，并找到最长的匹配项。确保我们只考虑旧文件中的位置，或者新文件中比我们当前所在位置更早的位置。这确保了我们可以在补丁应用期间重用旧文件和新文件中的材料。

编辑#2：上述算法的源代码

您可能会收到有关证书存在问题的警告。我不知道如何解决这个问题，所以暂时只接受证书。

源代码使用了我库的其余部分中的许多其他类型，因此该文件并不是它所需要的全部，但这就是算法实现。

@lomaxx，我试图为 subversion 中使用的算法找到一个很好的文档，称为 xdelta，但除非您已经知道该算法是如何工作的，否则我找到的文档无法告诉我我需要知道什么。

或者也许我只是很密集...... :)

我从您提供的那个站点快速浏览了算法，不幸的是它不可用。来自二进制差异文件的评论说：

找到一组最佳差异需要相对于输入大小的二次时间，因此它很快就会变得不可用。

我的需求不是最佳的，所以我正在寻找更实用的解决方案。

不过，感谢您的回答，如果我需要的话，可以在他的实用程序中添加一个书签。

编辑#1：注意，我会查看他的代码，看看我是否能找到一些想法，稍后我还会向他发送一封电子邮件，提出问题，但我已经阅读了他引用的那本书，尽管解决方案对找到最佳解决方案，由于时间要求，它在使用中是不切实际的。

编辑#2：我肯定会寻找 python xdelta 实现。

给定一个（源）补丁文件，在 Windows 下将这个补丁应用于源文件的最简单方法是什么？

我可以直观地比较未更改的源代码行的 GUI 工具会很棒。

如何diff忽略临时文件foo.c~？是否有一个配置文件将使忽略临时文件成为默认设置？

更一般地说：从 tarball 生成“干净”补丁的最佳方法是什么？我很少这样做（通过电子邮件向 OSS 项目提交错误修复），我总是在努力解决它......

编辑：好的，简短的回答是

有更好的答案吗？例如，这可以放在配置文件中吗？

终止程序然后从被终止的程序中运行其他代码的最佳方法是什么？例如，程序自我更新的最佳方式是什么？

在 SubVersion 中创建补丁非常容易，使用 Tortoise，您可以右键单击并选择创建补丁。但是对于我的生活，我在 TFS 中找不到这个功能。这可能吗？

如果不是，那么在开源 TFS 托管项目（a la CodePlex）中提交补丁的标准方法是什么？

在具有多个 Windows 服务器的环境中，确保所有系统的补丁合规性的最佳方法是什么？

是否有一个简单的工具（某种客户端/服务器应用程序？）允许生成报告以显示所有系统的状态，以便可以修复任何没有自动修补自身的问题，而无需每次审核时手动检查每个系统需要吗？

我一直想知道的一件事是软件补丁是如何工作的。许多软件似乎只是在其二进制文件上发布了需要安装在旧版本之上的新版本，但一些软件（尤其是像 Windows 这样的操作系统）似乎能够发布非常小的补丁来纠正错误或为现有的添加功能软件。

大多数时候，我看到的补丁不可能替换整个应用程序，甚至是应用程序中使用的小文件。在我看来，实际的二进制文件似乎正在被修改。

这些补丁是如何实际实施的？任何人都可以向我指出任何解释其工作原理的资源，还是就像替换应用程序中的链接库之类的小组件一样简单？

我可能永远不需要以这种方式进行部署，但我很想知道它是如何工作的。如果我的理解是正确的，补丁实际上只能修改二进制文件的一部分，那么这可以在.NET 中实现吗？如果是我想学习它，因为这是我最熟悉的框架，我想了解它是如何工作的。

我对使用 Subversion 作为其源代码控制的开源项目进行了一些本地更改。（我没有原始项目存储库的提交访问权限。）

我的更改添加了一个文件，但该文件不包含在“svn diff”的输出中。（可能值得注意的是，新文件是二进制文件，而不是纯文本。）

如何制作包含新文件的补丁？

我正在修补 connect() 以将网络流量重定向为库（NetHooker）的一部分，这很好用，但它取决于 ws2_32.dll 保持不变并且如果直接使用系统调用则不起作用。所以我想知道是否有办法在没有驱动程序的情况下捕获系统调用本身。有谁知道这是否可能？

当提到“提交补丁”时，补丁这个词到底是什么意思？

我已经看到它被大量使用，尤其是在开源世界中。这是什么意思以及提交补丁的具体内容是什么？