支持原地更新老数据

[sisong]

磁盘占用可控：下载的补丁包可能不能存储到磁盘,也需要原地更新老数据；（如果磁盘空间可用，patch执行又很快，那“边下载边patch”的需求不太可能单独存在）
内存占用可控：只下载一部分就开始执行补丁过程，分阶段完成patch过程；

缺点：

• 原地更新老数据 的算法可行性还需要研究（已有初步可行结果，实现代码较复杂）；
• 可能需要定义新的补丁数据格式更好，可能不利于压缩（现有格式也还能用）；
• patch过程中，下载等失败不好复原（失败后业务上需要进入新旧替换更新，不能再使用补丁更新）；

[sisong]

尝试了分析“原地更新”，类似于外排序，算法最好情况下应该可以约束到O（n*log(n)), 写入放大系数约20倍左右(因为log(n))；
算法也没有完全解决，还剩下一个问题没有解决：如何在有限内存、无额外磁盘空间的情况下，O(n)时间内两路归并多块长度不同的磁盘数据；
（继续分析后发现该算法不好）

[sisong]

核心问题抽象：
磁盘上已有一个大文件Old,需要从Old中任意位置多次拷贝一些数据来构造一个新的大文件New,并舍弃Old；
每次拷贝操作可描述为结构(oldPos,newPos,copyLen)，所有拷贝操作组成已知数组C(已按newPos升序排序);
[oldPos,oldPos+copyLen)代表的区域之间可能重叠; 而[newPos,newPos+copyLen)代表的区域之间不会重叠,但可能有空隙（填充空隙的数据储存在补丁包中）；
现在的情况是 没有多余的磁盘空间、内存也很有限（假设能够装下数组C，否则算法写起来很费力）；

将Old文件大小设置为maxSize(Old,New)，遍历C数组，将被copy线引用到过的Old数据区域都按现有顺序对齐到文件尾，并更新C中oldPos新值；
将C数组按oldPos升序排序，遍历C数组，依次将数据copy到从Old文件头开始的写入位置；（不用担心覆盖掉还没有使用到的有效Old数据）；（完成后可以设置当前文件大小为size(new)）
现在的C数组的大小描述了文件中new被分成了相应的块数，C中的copyLen描述了每一块数据的大小，C中的newPos描述了这些块本应该在的位置；
现在剩下的问题就是如何快速完成该排序整理了；

假设一共有N块数据要排序，总数据长度S，不断的找到下一块应该排到最前面的new块，与当前要写入的位置的cur块交换，交换min(new,cur)长的数据；
如果2块大小一致（几率很小），那ok；如果不等，那还是剩余N块，但需要排序的总长度已经减少了min(new,cur)；
不断继续下去算法复杂度应该是：最大O(S)次操作、O(S)的总数据量读写就能完成排序；

这个算法的性能可能遇到的问题： 1. 每次从新的new块拿数据类似磁盘的随机访问，性能可能比较慢； 2.在迭代过程中，每次操作的数据块可能很小，甚至单字节，访问的额外磁盘代价很大；

对于重排序我现在的另一个思路： 用外排序的败者树的思路，假设可用内存为文件大小的1/M，那M次全文件范围的局部排序就能完成整体排序，也就是O(M*S)的总数据量读写；只要M够小（内存够大），而且因为文件一直是顺序访问，性能应该也还行；

[GTOTA]

（不用担心覆盖掉还没有使用到的Old数据），完成后设置当前文件大小为size(new);
为啥不用担心覆盖呀，后续的patch还有可能用到覆盖部分的数据吧

[sisong]

@GTOTA 你可能没有注意到这句“将用到的Old数据区域都按文件尾对齐”

[GTOTA]

@sisong 就是不太理解这句话，按文件尾对齐是啥意思，是把两个有重叠的copy数据区做对齐吗

[pysjp]

同问，确实不清楚，按照文件尾对齐是什么意思，具体是如何实现对齐？求解答

[sisong]

解释一下“将用到的Old数据区域都按文件尾对齐” ： 就是把Old中的数据看作2类，一类是被copy线引用过的，反之剩下的是无用数据；有用到的这些数据都按现有顺序堆放到文件尾部去。

[pysjp]

增量更新应该是目标版本只有很少一部分有差异，大部分内容都相同，按照把相同的数据都拷贝到文件尾部的思路，那么，需要空间大小，可能接近于目标文件＋原文件的大小，是这样吗？

[sisong]

“需要空间大小，可能接近于目标文件＋原文件的大小” 需要的空间是 max(目标文件,原文件),你再想想

[pysjp]

终于理解了，感谢大哥

[RPG3D]

感觉原地更新旧文件不太可靠,尤其是手机上, 用户中途关了app,会导致旧文件损坏.得重新下载全量资源

[sisong]

当前的实现 create_single_compressed_diff\patch_single_stream ，已经解决了“支持在下载补丁包过程中，就可以开始执行(解压缩和)patch过程,内存占用可控”的问题。
剩余需求：原地更新老数据

[wangchz13]

当前的实现 create_single_compressed_diff\patch_single_stream ，已经解决了“支持在下载补丁包过程中，就可以开始执行(解压缩和)patch过程,内存占用可控”的问题。 剩余需求：原地更新老数据

作者您好，请问这个意思是支持分段合成了吗？

[sisong]

“分段合成” 是分几次合成的意思吗？ patch_single_stream并不支持，它支持的还是一次性patch，patch过程中可以等待补丁数据陆续下载到本地，不断的和旧数据合成出新数据。

[wangchz13]

“分段合成” 是分几次合成的意思吗？ patch_single_stream并不支持，它支持的还是一次性patch，patch过程中可以等待补丁数据陆续下载到本地，不断的和旧数据合成出新数据。

是这个意思。也就是说，假如补丁20KB，可以先传10KB，用这10KB合成后，这10KB可以删掉了，再传10KB继续合成对吗？
想再请教您一个问题：嵌入式设备上flash空间无法同时存放old程序和new程序，所以我想能不能从old中拿出一段合成然后再拿一段再合成？我想这个方法应该比原地更新老数据要简单些，但是这样肯定要修改补丁包的结构甚至算法，想请问您有没有别的思路？感谢~

[sisong]

“是这个意思。也就是说，假如补丁20KB，可以先传10KB，用这10KB合成后，这10KB可以删掉了，再传10KB继续合成对吗？”
是的，可以分成更小的粒度，从而不用将补丁数据存储在硬盘上。

“嵌入式设备上flash空间无法同时存放old程序和new程序”
这需要重新设计算法，也是这个issue关注的问题；简单处理的话可以这样考虑：将old按固定大小分成n块，计算出哪些块可以重用，如果有块的位置需要调整，那需要计算出调整路径，...。

"嵌入式设备上"
如果对资源占用有更高要求，可以试试 create_lite_diff/hpatch_lite_patch这对函数,使用方法 参考仓库 HPatchLite

[wangchz13]

好的，感谢！

[wangchz13]

作者您好，我目前已经实现了原地更新老数据。做法是在diff.covers.oldPos找出一个最长递增子序列出来，然后把不在此序列的删掉。这样做最然会使diff变大，但这个代价是值得的。
然后用diff.length^2的复杂度找出一个diff.covers的安全移动路径出来，根据我的实验，只要diff.covers.oldPos是连续递增的，那么总能找到一个序列，能让diff.covers全部移完。如果最后有diff.covers无法移动的话，那就把这些covers删掉，只是差分包会变大。
最后差分包里多加了移动序列和覆盖线，而且在嵌入式设备上也成功运行了。

[sisong]

“最长递增子序列” “只是差分包会变大”
嗯，这肯定会变大的； 可以注意下diff的其中一个参数ICoverLinesListener，用它可以进行一些优化；
比如进行2遍diff的方案：先默认执行一次diff，保留满足要求的有效covers； 然后用这些covers信息实现一个ICoverLinesListener接口，进行第二遍diff，就可以控制每一次的匹配，哪些位置的cover和长度满足要求，哪些cover忽略，从而得到更好的covers组合；

[shamork]

作者您好，我目前已经实现了原地更新老数据。做法是在diff.covers.oldPos找出一个最长递增子序列出来，然后把不在此序列的删掉。这样做最然会使diff变大，但这个代价是值得的。 然后用diff.length^2的复杂度找出一个diff.covers的安全移动路径出来，根据我的实验，只要diff.covers.oldPos是连续递增的，那么总能找到一个序列，能让diff.covers全部移完。如果最后有diff.covers无法移动的话，那就把这些covers删掉，只是差分包会变大。 最后差分包里多加了移动序列和覆盖线，而且在嵌入式设备上也成功运行了。

Would please create a PR?

[wangchz13]

作者您好，我目前已经实现了原地更新老数据。做法是在diff.covers.oldPos找出一个最长递增子序列出来，然后把不在此序列的删掉。这样做最然会使diff变大，但这个代价是值得的。 然后用diff.length^2的复杂度找出一个diff.covers的安全移动路径出来，根据我的实验，只要diff.covers.oldPos是连续递增的，那么总能找到一个序列，能让diff.covers全部移完。如果最后有diff.covers无法移动的话，那就把这些covers删掉，只是差分包会变大。 最后差分包里多加了移动序列和覆盖线，而且在嵌入式设备上也成功运行了。

Would please create a PR?
no. my code is shit just like my english. The author will not merge it. haha

[wangchz13]

修改的原地升级版的我上传了 https://github.com/wangchz13/myhdiffpatch
代码可能比较烂，将就着看吧~

[district10]

我有一个类似的使用场景：有一个文件夹（workdir），有一系列的脚本（比如 prog1, prog2，prog3）来操作这里的数据；我想对比一些关键环节间的文件变动，比如 workdir#v2（prog2 处理后的 workdir 状态） 和 workdir#v3 的区别（可以呈现为 1) 文件变动元信息 + 2) 可应用到 #v2 让这个目录变为 #v3 的一个 patch）。

我感觉 dvc （把文件版本控制系统 git 扩展到数据版本控制）应该可以做这个事情，好像 dvc 也是对文件做分块然后用这些块来表达现在的文件（夹）数据。不知道 @sisong 有没有了解过，和 HDiffPatch 有啥异同，各自有什么样的适用场景。

[sisong]

对 dvc 没有了解。
HDiffPatch 的设计目标一直是： 增量更新， 计算从一个版本的数据到另一个版本数据之间的二进制补丁。
你的需求如果只是获得人不可读的补丁，那现在的程序就能直接使用； 如果是想了解 具体的”变动信息“，可能需要自己调用diff的API来获得覆盖线的信息，比如 get_match_covers_by_block 或 get_match_covers_by_sstring。

[jimmy6270]

@wangchz13
大哥，你这个原地升级拷贝到原工程里面后编译不过去啊

[wangchz13]

@jimmy6270
你好，目前版本和我之前的改动参数已经不匹配，故无法成功编译。我忘记是基于哪个版本修改，只有改动的项目还在，所以重新上传一份整个项目（VS2022）：MiniHDiffPatch
项目做了精简，去掉了解压缩等功能，只保留基础的差分生成功能

[hiiizxf]

hi,原地更新还没有实现吗？从原理上看，似乎需要牺牲压缩率才能实现
另外对目录的diff，是否存在压缩率更高的方案？

[sisong]

• 是的，HDiffPatch当前还不支持原地更新；

• “似乎需要牺牲压缩率才能实现”
  是的， 总是需要一些取舍；
  然而正因为取舍的方式很多，而且“受限环境”所代表的限制、数据特性、flash等硬件特性各不相同，造成没有简单通用的实现方式。

• “另外对目录的diff，是否存在压缩率更高的方案？”
  不知道你所说的“压缩率更高”是指什么？ 现在的方案有哪里造成了压缩率降低了吗？
  我记得大概有一处： 文件数量特别多而文件很小时，单独保存文件名将占用空间；而应该将新旧文件名也进行diff。

[hiiizxf]

• “另外对目录的diff，是否存在压缩率更高的方案？”
  从结果上看，当old目录有一个原始文件a 11MB, new目录有2个文件a、b， b也是11MB，a/b做文件差分时a/b的patch只有1.8MB（bzip2-9），对old目录和new目录做差分时，patch应该是1.8MB . 实际制作后patch是3.4MB. 和普通bzip2压缩后区别不大。

[sisong]

确实还有一处：old中如果和new中有文件数据完全一致，就会被排除出diff，这是为了优化diff速度，但可能因此错过一些匹配从而降低压缩率。

[hiiizxf]

确实还有一处：old中如果和new中有文件数据完全一致，就会被排除出diff，这是为了优化diff速度，但可能因此错过一些匹配从而降低压缩率。

如果说将所有文件排序后，做一个后缀数组，在执行patch，或许可以提高diff速度？只是在目录文件总体较大时，diff内存消耗也较大。

[sisong]

不仅仅是影响diff，还会影响patch流程，因为预先知道文件相同，并且patch到相同old文件夹的时候，可以跳过这些文件。(当然，该影响很好排除掉)

ps：完全不推荐再使用bzip2压缩器，推荐用zstd压缩