Processing software images for use in generating difference files

• US 7,089,270 B2
• Filed: 06/20/2003
• Issued: 08/08/2006
• Est. Priority Date: 06/20/2003
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: InnoPath Software, Inc. (Qualcomm, Inc.)
• Inventors: Gu, Jinsheng, Ren, Liwei
• Primary Examiner(s): ROBINSON, GRETA LEE
• Application Number:
  US10/600,978
• Publication Number:
  US 20040260734A1
• Time in Patent Office: 1,145 Days
• Field of Search: 707/200, 707/203, 707/102, 707/101, 707/201
• US Class Current: 707/695
• CPC Class Codes: G06F 8/658 Incremental updates; Differential updates
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99954 Version management

Abstract

Systems and methods are provided for pre-processing original and new versions of files as part of difference file generation between the original and new file versions, for example byte-level file differencing. Software/executable changes between file versions include primary changes/logical changes, which are defined to be the source code changes, and secondary changes. The secondary changes generally result from the primary changes and are generated by the software compiler/linker utilities. The secondary changes include address changes, pointer target address changes, and changes in address offsets. The pre-processing systems and methods provided use approximation rules between file versions to remove/reduce the secondary changes and encode information relating to the removal of these changes in information of the corresponding difference file.

Claims

1. A system for updating electronic files comprising:

a first device for generating a difference files that includes coded differences between an original version and a new version of an electronic file, wherein the first device includes at least one component configured for;

identifying differences between the original version and the new versions corresponding to address shifts resulting from at least one of code line deletion, code line addition, and code line modification;

removing the identified differences in text sections common to the original version and the new versions by modifying target addresses of instructions of the original version using at least one relationship between addresses of text sections of the original version and corresponding text sections of the new version;

generating a modified version of the original version that includes the instructions having modified target addresses;

generating the difference file using the new version and the modified version of the original version; and

a second device that receives the difference file and generates the new version in the second device using the difference file.

2. The system of claim 1, wherein removing further includes:

identifying first and second text sections that are common between the original version and the new versions, wherein the first text section in the original version includes a first calculable instruction and the second text section in the new version includes a second calculable instruction;

identifying third and fourth text sections that are common between the original version and the new versions, wherein the third text section in the original version includes a first target address that corresponds to the first calculable instruction, wherein the fourth text section in the new version includes a second target address that corresponds to the second calculable instruction;

generating a second instruction value from the second calculable instruction by modifying the first instruction value using a first difference between starting addresses of the third and fourth function units and using a second difference between starting addresses of the first and second function units; and

replacing a first instruction value of the first calculable instruction with the second instruction value.

3. The system of claim 1, further comprising removing the identified differences in instructions including data pointers that point to data sections common to the original version and the new versions by modifying data pointer values in the original version, wherein modifying data pointer values uses a difference between starting addresses of data sections in the original version pointed to by a current data pointer and starting addresses of corresponding data sections in the new version.

4. The system, of claim 3, wherein removing identified differences in instructions including data pointers further comprises:

identifying first and second code segments that are common between the original version and the new versions, wherein the first code segment in the original version includes a first data pointer and the second code segment in the new version includes a second data pointer;

identifying first and second data units that are common between the original version and the new versions, wherein the first data unit in the original version includes a first target address that corresponds to the first data pointer, wherein the second data unit in the new version includes a second target address that corresponds to the second data pointer;

generating a second data pointer value from the second data pointer by modifying a first data pointer value using a difference between starting addresses of the first and second data units; and

replacing a first data pointer value of the first data pointer with the second data pointer value.

5. The system of claim 1, wherein the second device is at least one processor-based device selected from among personal computers, portable computing devices, cellular telephones, portable communication devices, and personal digital assistants.

6. The system of claim 1, wherein the first device transfers the difference file to the second device using at least one coupling, wherein the at least one coupling is at least one of a wireless coupling, a wired coupling, and a hybrid wireless/wired coupling.

7. An apparatus for use in generating a difference files, comprising:

means for receiving an original version and a new version of an electronic file;

means for identifying units of code that are common to the original version and the new versions;

means for identifying instructions that are common to the units of code, wherein the instructions include instruction values that direct processing to another portion of a corresponding file;

means for generating a first instruction value from a first instruction of the original version;

means for generating a second instruction value from a second instruction of the new version, wherein the second instruction corresponds to the first instruction;

means for replacing the first instruction value of the first instruction with the second instruction value;

means for generating a modified version of the original version comprising the first instruction with the second instruction value; and

means for generating the difference file using the new version and the modified version of the original version.

8. A method for reducing a size of a difference file that includes coded differences between an original version and a new version of an electronic file, comprising:

identifying differences between the original version and the new versions corresponding to address shifts resulting from at least one of code line deletion, code line addition, and code line modification;

removing the identified differences in text sections common to the original version and the new versions by modifying target addresses of instructions of the original version using at least one relationship between addresses of text sections of the original version and corresponding text sections of the new version;

generating a modified version of the original version that includes the instructions having modified target addresses; and

generating the difference file using the new version and the modified version of the original version.

9. The method of claim 8, wherein removing further includes:

identifying first and second text sections that are common between the original version and the new versions, wherein the first text section in the original version includes a first calculable instruction and the second text section in the new version includes a second calculable instruction;

identifying third and fourth text sections that are common between the original version and the new versions, wherein the third text section in the original version includes a first target address that corresponds to the first calculable instruction, wherein the fourth text section in the new version includes a second target address that corresponds to the second calculable instruction;

generating a second instruction value from the second calculable instruction by modifying the first instruction value using a first difference between starting addresses of the third and fourth function units and using a second difference between starting addresses of the first and second function units; and

replacing a first instruction value of the first calculable instruction with the second instruction value.

10. The method of claim 8, further comprising removing the identified differences in instructions including data pointers that point to data sections common to the original version and the new versions by modifying data pointer values in the original version, wherein modifying data pointer values uses a difference between starting addresses of data sections in the original version pointed to by a current data pointer and starting addresses of corresponding data sections in the new version.

11. The method of claim 10, wherein removing identified differences in instructions including data pointers further comprises:

identifying first and second code segments that are common between the original version and the new versions, wherein the first code segment in the original version includes a first data pointer and the second code segment in the new version includes a second data pointer;

identifying first and second data units that are common between the original version and the new versions, wherein the first data unit in the original version includes a first target address that corresponds to the first data pointer, wherein the second data unit in the new version includes a second target address that corresponds to the second data pointer;

generating a second data pointer value from the second data pointer; and

replacing a first data pointer value of the first data pointer with the second data pointer value.

12. The method of claim 11, wherein generating the second data pointer value includes modifying a first data pointer value using a difference between starting addresses of the first and second data units.

13. The method of claim 10, further comprising generating a modified version of the original version that includes the instructions having modified data pointers.

14. The method of claim 10, further comprising merging common data units to form common data blocks.

15. The method of claim 14, wherein merging comprises:

combining first and second data units of the original version and combining corresponding first and second data units of the new version to form a common data block when the first data unit of the original version has a size equal to the first data unit of the new version, an ending address of the first data unit of the original version is equal to a starting address of the second data unit of the original version, and an ending address of the first data unit of the new version is equal to a starting address of the second data unit of the new version; and

repeating the combining operation for additional mergeable data units.

16. The method of claim 15, further comprising merging common text sections to form common function blocks.

17. The method of claim 16, wherein merging comprises:

combining first and second text sections of the original version and combining corresponding first and second text sections of the new version to form a common function block when the first text section of the original version has a size equal to the first text section of the new version, an ending address of the first text section of the original version is equal to a starting address of the second text section of the original version, and an ending address of the first text section of the new version is equal to a starting address of the second text section of the new version; and

repeating the combining operation for additional mergeable text sections.

18. A method for performing file differencing, comprising:

receiving an original version and a new version of an electronic file;

identifying units of code that are common to the original version and the new versions;

identifying instructions that are common to the units of code, wherein the instructions include instruction values that relate to another portion of a corresponding file;

decoding a first instruction value from a first instruction of the original version;

generating a second instruction value from a second instruction of the new version, wherein the second instruction corresponds to the first instruction;

replacing the first instruction value of the first instruction with the second instruction value;

generating a modified version of the original version comprising the first instruction with the second instruction value; and

performing file differencing between the new version and the modified version of the original version and generating a difference file.

19. The method of claim 18, further comprising extracting the common units of code from associated map files, wherein the common units of code include common function units and common data units.

20. The method of claim 18, further comprising merging common function units of the units of code to form common function blocks.

21. The method of claim 20, wherein merging comprises:

combining first and second function units of the original version and combining corresponding first and second function units of the new version to form a common function block when the first function unit of the original version has a size equal to the first function unit of the new version, an ending address of the first function unit of the original version is equal to a starting address of the second function unit of the original version, and an ending address of the first function unit of the new version is equal to a starting address of the second function unit of the new version; and

repeating the combining operation for additional mergeable function units.

22. The method of claim 20, further comprising encoding the common function blocks.

23. The method of claim 18, further comprising merging common data units of the units of code to form common data blocks.

24. The method of claim 23, wherein merging comprises:

combining first and second data units of the original version and combining corresponding first and second data units of the new version to form a common data block when the first data unit of the original version has a size equal to the first data unit of the new version, an ending address of the first data unit of the original version is equal to a starting address of the second data unit of the original version, and an ending address of the first data unit of the new version is equal to a starting address of the second data unit of the new version; and

repeating the combining operation for additional mergeable data units.

25. The method of claim 23, further comprising encoding the common data blocks.

26. The method of claim 18, wherein the units of code that are common to the original version and the new versions are common function units, wherein the first instruction includes a first calculable instruction and the second instruction includes a second calculable instruction, wherein generating the second instruction value includes modifying the first instruction value using a first difference between starting addresses of the common function units of the original version and the new versions that include a target address and using a second difference between the starting addresses of the common function units that include the first and second calculable instructions.

27. The method of claim 18, wherein the units of code include function units.

28. The method of claim 27, wherein generating the first instruction value includes generating a difference between a current instruction address of the first calculable instruction and a target address of the first calculable instruction.

29. The method of claim 27, wherein generating the second instruction value includes:

generating a difference between a current instruction address of the first calculable instruction and a target address of the first calculable instruction;

generating a difference between a start address of a first common function unit of the new version and a start address of a corresponding first common function unit of the original version; and

generating a difference between a start address of a second common function unit of the new version and a start address of a corresponding second common function unit of the original version.

30. The method of claim 18, wherein the units of code include data units and the instructions include data pointers.

31. The method of claim 18, wherein the units of code that are common to the original version and the new versions are common data units, wherein the first instruction includes a first data pointer and the second instruction includes a second data pointer, wherein the first instruction value includes a first data pointer value and the second instruction value includes a second data pointer value, wherein generating the second instruction value includes generating a second data pointer value by modifying the first data pointer value using a difference between starting addresses of the first and second data units.

32. The method of claim 18, further comprising:

transferring the difference file to a portable processing system; and

generating a version of the new version in the portable processing system using the difference file.

33. The method of claim 32, further comprising:

merging common function units of the units of code to form common function blocks;

merging common data units of the units of code to form common data blocks; and

encoding the common function blocks and the common data blocks for use in generating the version of the new version in the portable processing system.

34. A method for determining differences between electronic files, comprising:

receiving an original version and a new version of an electronic file;

identifying first and second function units that are common between the original version and the new version, wherein the first function unit in the original version includes a first calculable instruction and the second function unit in the new version includes a second calculable instruction;

identifying third and fourth function units that are common between the original version and the new version, wherein the third function unit in the original version includes a first target address that corresponds to the first calculable instruction, wherein the fourth function unit in the new version includes a second target address that corresponds to the second calculable instruction;

generating a second instruction value from the second calculable instruction;

replacing a first instruction value of the first calculable instruction with the second instruction value;

generating a modified version of the original version comprising the first instruction with the second instruction value; and

generating a difference file using the new version and the modified version of the original version, the difference file including the differences.

35. The method of claim 34, wherein generating the second instruction value includes modifying the first instruction value using a first difference between starting addresses of the third and fourth function units and using a second difference between starting addresses of the first and second function units.

36. The method of claim 34, further comprising:

identifying first and second code segments that are common between the original version and the new version, wherein the first code segment in the original version includes a first data pointer and the second code segment in the new version includes a second data pointer;

identifying first and second data units that are common between the original version and the new versions, wherein the first data unit in the original version includes a first target address that corresponds, to the first data pointer, wherein the second data unit in the new version includes a second target address that corresponds to the second data pointer;

generating a second data pointer value from the second data pointer;

replacing a first data pointer value of the first data pointer with the second data pointer value; and

generating a modified version of the original version comprising the first data pointer with the second data pointer value.

37. The method of claim 36, wherein generating the second data pointer value includes generating a difference between starting addresses of data sections in the original version pointed to by a current data pointer and starting addresses of corresponding data sections in the new version.

38. The method of claim 34, further comprising merging common function units to form common function blocks.

39. The method of claim 34, further comprising merging common data units to form common data blocks.

40. The method of claim 34, further comprising:

transferring the difference file to a portable processing system; and

generating a version of the new version in the portable processing system using the difference file.

41. A computer readable medium including executable instructions which, when executed in a processing system, reduce a size of a difference file that includes coded differences between an original version and a new version of an electronic file by:

identifying differences between the original version and the new version corresponding to address shifts resulting front at least one of code line deletion, code line addition, and code line modification;

removing the identified differences in text sections common to the original version and the new versions by modifying target addresses of instructions of the original version using at least one relationship between addresses of text sections of the original version and corresponding text sections of the new version;

generating a modified version of the original version that includes the instructions having modified target addresses; and

generating the difference file using the new version and the modified version of the original version.