Algorithms for block-level code alignment of software binary files
Filing Information
- Patent Number: US7031972
- Application Number: US10624704
- Filing date: 07/21/2003
- Issue date: 04/18/2006
- Prior Publication Data:
- US20050021572 - 01/27/2005
- Predicted expiration date: 05/10/2024
- Patent term adjustment: 294
View assignee updates
analyzing 100 million+ documents to uncover your network...Abstract
A file differencing and updating system is provided that includes a file differencing component and a file updating component. The file differencing component, or file differencing engine, generates a difference file in a first processor-based or computer system from an original or old version and a new version of an electronic file. Generation of the difference files includes processing to reduce the number of file changes introduced by code block swaps. The processing uses an alignment algorithm, which includes a sorting algorithm, to align the code blocks of the original version in the same order as those of the new version, thereby eliminating the increase in the number of byte-level file differences due to code block swaps. During the alignment operations, the block movements are dynamically recorded at a minimum cost level and encoded for transmission to the file updating component for use in code recovery.References Cited
U.S. Patent Documents
* cited by examinerOther Publications
| Tichy, Walter F., “The string-to-string correction problem with block moves”, ACM Transaction on Computer Systems, vol. 2, No. 4, Nov. 1984, pp. 309-321. |
| Ajtai, Miklos et al., “Compactly encoding unstructured inputs with differential compression”, IBM Almaden Research Center, 44 pages, no date. |
| Burns, Randal C. et al., “In-place reconstruction of delta compressed files”, IBM Almaden Research Center, 9 pages, no date. |
| Burns, Randal et al., “In-place reconstruction of version differences”, IBM Almaden Research Center, 25 pages, no date. |
| Ziv, Jacob et al., “A universal algorithm for sequential data compression”, IEEE Transactions on Information Theory, vol. IT-23, No. 3, May 1977. |
Referenced By
| Document Number | Assignee | Inventors | Issue/Pub Date |
|---|---|---|---|
| US7412691 | International Business Machines Corporation | James I. Bognar | Aug 2008 |
| US7516130 | Trend Micro, Inc. | Liwei Ren et al. | Apr 2009 |
| US7454431 | AT&T Corp. | Binh Dao Vo et al. | Nov 2008 |
| US7313791 | Hewlett-Packard Development Company, L.P. | Shao-Chun Chen et al. | Dec 2007 |
Patent Family
| Document Number | Assignee | Inventors | Issue/Pub Date |
|---|---|---|---|
| US20050021572 | Liwei Ren et al. | Jan 2005 | |
| WO2005015343 | INNOPATH SOFTWARE, INC. | Liwei REN et al. | Feb 2005 |
| US7031972 | InnoPath Software, Inc. | Liwei Ren et al. | Apr 2006 |
| US20060101040 | REN LIWEI | Liwei Ren et al. | May 2006 |
| US7392260 | InnoPath Software, Inc. | Liwei Ren et al. | Jun 2008 |
Independent Claims | See all claims (10)
- 1. A method for reducing a number of changes between an original file and a new file on a processor-based device, comprising: determining an order of code blocks of the new file using index values; sorting code blocks of the original file and generating a largest increasing subsequence (LIS) of code blocks according to the index values; generating at least one list of original order numbers of the code blacks of the original file affected by code block movement; and moving the code blocks of the original file to locations in the original file according to the largest increasing subsequence of code blocks, wherein the code blocks of the original file are aligned in the same order as code blocks of the new file.
- 2. An apparatus comprising at least one processor coupled to: means for receiving an original file and a new file, wherein the new file includes an updated version of the original file; means for determining an order of code blocks of the new file using index values; means for sorting code blocks of the original file and generating a largest increasing subsequence (LIS) of code blocks according to the index values; means for generating lists of original order numbers of the code blocks of the original file affected by code block movements; and means for moving the code blocks of the original file to locations in the original file according to the largest increasing subsequence of code blocks, wherein the code blocks of the original file are aligned in the same order as code blocks of the new file.
- 3. A system for updating electronic files of remote devices, comprising: a first device including a processor coupled to a file differencing engine that generates differences between an original version and a new version of an electronic file by: determining an order of code blocks of the new version using index values; sorting code blocks of the original version and generating a largest increasing subsequence (LIS) of code blocks according to the index values; generating lists of original order numbers of the code blocks of the original version affected by code block movements; moving the code blocks of the original version to locations in the original version according to the largest increasing subsequence of code blocks, wherein the code blocks of the original version are aligned in the saint order as code blocks of the new version; generating an encoded list including information of the code block moves; transmitting the encoded list to a second device; and a file updating engine coupled to a processor of the second device, the file updating engine generating a copy of the new version using a difference file and information of the code block moves.
- 5. A method for generating difference flies on a processor-based device, comprising: receiving an original file and a new file, wherein the new file includes an updated version of the original file; determining an order of code blocks of the new tile using index values; sorting code blocks of the original file and generating a largest increasing subsequence (LIS) of code blocks according to the index values; generating lists of original order numbers of the code blocks of the original file affected by code block movements; moving the code blocks of the original file to locations in the original file according to the largest increasing subsequence of code blocks, wherein the code blocks of the original file are aligned in the same order as code blocks of the new file; and generating an encoded list including information of the code block moves.
- 10. A computer readable medium including executable instructions which, when executed in a processing system, reduce a number of changes between an original file and a new file by: determining an order of code blocks of the new file using index values; sorting code blocks of the original file and generating a largest increasing subsequence (LIS) or code blocks according to the index values; generating lists of original order numbers of the code blocks of the original file affected by code block movements; and moving the code blocks of the original file to locations in the original file according to the largest increasing subsequence of code blocks, wherein the code blocks of the original file are aligned in the same order as code blocks of the new file.
