housisong
such as： [Inno Setup XDELTA Patch Maker](https://www.softpedia.com/get/Programming/Patchers/Inno-Setup-XDELTA-Patch-Maker.shtml) support xdelta3 , JojoDiff and HDiffPatch, from [Inno Setup](http://www.jrsoftware.org/isinfo.php) . it used to create patch for game or app, steam game is used...
尝试了分析“原地更新”，类似于外排序，算法最好情况下应该可以约束到O（n*log(n)), 写入放大系数约20倍左右(因为log(n))； 算法也没有完全解决，还剩下一个问题没有解决：如何在有限内存、无额外磁盘空间的情况下，O(n)时间内两路归并多块长度不同的磁盘数据； （继续分析后发现该算法不好）
核心问题抽象： 磁盘上已有一个大文件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数据区域都按文件尾对齐”
解释一下“将用到的Old数据区域都按文件尾对齐” ： 就是把Old中的数据看作2类，一类是被copy线引用过的，反之剩下的是无用数据；有用到的这些数据都按现有顺序堆放到文件尾部去。
“需要空间大小，可能接近于目标文件＋原文件的大小” 需要的空间是 max(目标文件,原文件),你再想想
当前的实现 create_single_compressed_diff\patch_single_stream ，已经解决了“支持在下载补丁包过程中，就可以开始执行(解压缩和)patch过程,内存占用可控”的问题。 剩余需求：原地更新老数据
“分段合成” 是分几次合成的意思吗？ patch_single_stream并不支持，它支持的还是**一次**性patch，patch过程中可以等待补丁数据陆续下载到本地，不断的和旧数据合成出新数据。
“是这个意思。也就是说，假如补丁20KB，可以先传10KB，用这10KB合成后，这10KB可以删掉了，再传10KB继续合成对吗？” 是的，可以分成更小的粒度，从而不用将补丁数据存储在硬盘上。 “嵌入式设备上flash空间无法同时存放old程序和new程序” 这需要重新设计算法，也是这个issue关注的问题；简单处理的话可以这样考虑：将old按固定大小分成n块，计算出哪些块可以重用，如果有块的位置需要调整，那需要计算出调整路径，...。 "嵌入式设备上" 如果对资源占用有更高要求，可以试试 create_lite_diff/hpatch_lite_patch这对函数,使用方法 参考仓库 [HPatchLite](https://github.com/sisong/HPatchLite)
> `“最长递增子序列” “只是差分包会变大” ` 嗯，这肯定会变大的； 可以注意下diff的其中一个参数`ICoverLinesListener`，用它可以进行一些优化； 比如进行2遍diff的方案：先默认执行一次diff，保留满足要求的有效covers； 然后用这些covers信息实现一个ICoverLinesListener接口，进行第二遍diff，就可以控制每一次的匹配，哪些位置的cover和长度满足要求，哪些cover忽略，从而得到更好的covers组合；