Code alignment of binary files

• US 7,392,260 B2
• Filed: 12/21/2005
• Issued: 06/24/2008
• Est. Priority Date: 07/21/2003
• Status: Expired due to Fees

• Current Assignee: Qualcomm, Inc.
• Original Assignee: InnoPath Software, Inc. (Qualcomm, Inc.)
• Inventors: Gu, Jinsheng, Ren, Liwei, Peng, Luosheng
• Primary Examiner(s): LE, UYEN T
• Application Number:
  US11/314,405
• Publication Number:
  US 20060101040A1
• Time in Patent Office: 916 Days
• Field of Search: 707/202, 707/203, 707/1, 707/2, 707/7, 707/100, 707/101
• US Class Current: 707/752
• CPC Class Codes: G06F 8/658 Incremental updates; Differential updates
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

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.

Claims

1. A method for reducing a number of changes between an original file and a new file on a processor-based device, comprising:

sorting code blocks of the original file and generating a largest increasing subsequence (LIS) of code blocks according to index values;

generating a list of original order numbers of the code blocks 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 LIS, wherein the code blocks of the original file are aligned in the same order as code blocks of the new file.

2. The method of claim 1, wherein the new file includes an updated version of the original file.

3. The method of claim 1, comprising determining an order of code blocks of the new file using the index values.

4. The method of claim 1, further comprising:

generating mappings between code blocks of the original file and corresponding code blocks of the new file; and

generating a mapping array using information of the mappings.

5. The method of claim 4, further comprising:

generating a LIS of the mapping array;

identify membership of the LIS of the mapping array for each code block of the original file; and

generating a membership array using information of the LIS membership.

6. The method of claim 1, further comprising receiving one or more of a mapping array, a membership array, a start address array, a size array, and an original code block order number array, wherein the mapping array includes information of mappings between code blocks of the original file and corresponding code blocks of the new file, wherein the membership array includes information of a membership of a LIS for each code block of the original file, wherein the start address array includes information of code block start addresses, wherein the size array includes information of code block sizes, and wherein the original code block order number array includes information of the original order of code blocks in the original file prior to the code block movements.

7. The method of claim 1, comprising generating an encoded list including information of the code block moves.

8. The method of claim 7, further comprising:

transferring the encoded list to at least one remote system via at least one coupling, wherein the remote system includes at least one processor-based system, wherein the coupling includes at least one of a wireless coupling, a wired coupling, and a hybrid wireless/wired coupling; and

updating a hosted copy of the original file in the remote system using a difference file and the encoded list.

9. 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:

sorting code blocks of the original file and generating a largest increasing subsequence (LIS) of code blocks;

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 LIS, wherein the code blocks of the original file are aligned in the same order as code blocks of the new file.

10. An apparatus comprising:

a processor; and

a code block alignment system coupled to the processor, wherein the code block alignment system is configured to reduce a number of byte-level file differences between an original file and a new file by sorting and moving code blocks of the original file to align the code blocks of the original file in the same order as code blocks of the new file, wherein the code block alignment system is configured to dynamically record data describing the moving of the code blocks, wherein the code block alignment system is configured to transfer the data describing the moving to a remote device.

11. The apparatus of claim 10, wherein the code block alignment system is configured to determine an order of code blocks of the new file using index values.

12. The apparatus of claim 11, wherein the code block alignment system is configured to sort code blocks of the original file and generate a largest increasing subsequence (LIS) of code blocks according to the index values.

13. The apparatus of claim 12, wherein the code block alignment system is configured to record the data describing the moving of the code blocks by determining original order numbers of the code blocks of the original file affected by code block movements and recording the order numbers.

14. The apparatus of claim 10, wherein the remote device comprises a processor coupled to a file updating engine configured to generate a copy of the new version using a difference file and the data describing the moving of the code blocks.

15. A device comprising:

a processor; and

a differencing system coupled to the processor, the differencing system configured to generate differences between an original version and a new version of an electronic file, wherein the differencing system is configured to determine an order of code blocks of the new version using index values, wherein the differencing system is configured to sort code blocks of the original version and generate a largest increasing subsequence (LIS) of code blocks according to the index values, wherein the differencing system is configured to move the code blocks of the original version to locations in the original version according to the LIS so that the code blocks of the original version are aligned in the same order as code blocks of the new version.

16. The device of claim 15, wherein the differencing system is configured to generate a list of original order numbers of the code blocks of the original version affected by code block movements.

17. The device of claim 15, wherein the differencing system is configured to generate a list including information of the code block moves.

18. The device of claim 17, wherein the differencing system is configured to transmit the list to a second device.

19. The device of claim 18, wherein the second device includes a device selected from a group consisting of cellular telephones, portable communication devices, personal digital assistants, personal computers, and portable processor-based devices.

20. A system for updating electronic files of remote devices, comprising a first device including a processor coupled to a differencing system that generates differences between an original version and a new version of an electronic file, wherein the differencing system is configured to determine an order of code blocks of the new version using index values, sort code blocks of the original version and generating a largest increasing subsequence (LIS) of code blocks according to the index values, move the code blocks of the original version to locations in the original version according to the LIS so the code blocks of the original version are aligned in the same order as code blocks of the new version, and generate a list including data of the code block moves.

21. The system of claim 20, comprising a second device including a processor coupled to an updating engine, wherein the first device is configured to transfer the list to the second device.

22. The system of claim 21, wherein the updating engine is configured to generate a copy of the new version using a difference file and the data of the code block moves.

23. The system of claim 21, wherein the second device includes a device selected from a group consisting of cellular telephones, portable communication devices, personal digital assistants, personal computers, and portable processor-based devices.