Differential file compression of software image versions

• US 7,676,506 B2
• Filed: 05/09/2007
• Issued: 03/09/2010
• Est. Priority Date: 06/20/2003
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: InnoPath Software, Inc. (Qualcomm, Inc.)
• Inventors: Reinsch, Matthias
• Primary Examiner(s): Wong; Leslie
• Application Number:
  US11/801,463
• Publication Number:
  US 20080040401A1
• Time in Patent Office: 1,035 Days
• Field of Search: 707/203, 717/122, 717168-170
• US Class Current: 717/169
• CPC Class Codes: G06F 8/658 Incremental updates; Differential updates

Abstract

Embodiments include systems and methods for pre-processing and post-processing original and new versions of files as part of difference file generation between the original and new file versions. The systems and methods of an embodiment include a set of algorithms that reduce the difference file size by preprocessing a variety of regions in software images for embedded computing devices, an example of which is the compressed read-only memory (ROM) file system (CRAMFS) image. The algorithms treat a variety of types of data regions that are created by the compiler. Embodiments operate on the server side and the client side. On the server side, the preprocessing generates Compact Functional Differences (CFD) hint data directly from a pair of CRAMFS images, without the use of symbol files or log files generated by compiler/linker utilities.

Claims

1. A computing method for performing file differencing using at least one processor and a memory, comprising:

identifying a plurality of regions in an original version of software image and in a new version of a software image using the at least one processor, wherein the plurality of regions comprise compact functional differences (CFD) preprocessing regions, wherein the CFD preprocessing regions comprise at least one table of pointers; and

preprocessing the plurality of regions using the at least one processor, comprising,

examining the plurality of regions in the original version and the new version;

identifying matching paths in the new version and the old version using approximate matching techniques;

analyzing differences between corresponding regions in the new version and the old version; and

describing the differences using a transformation that depends on values of groups of N bytes in the corresponding regions.

2. The method of claim 1, wherein the original version and the new version comprise execute-in-place (XIP) files.

3. The method of claim 1, wherein the preprocessing the plurality of regions further comprises generating CFD hint data.

4. The method of claim 3, wherein the preprocessing the plurality of regions further comprises generating the CFD hint data from a pair of images.

5. The method of claim 1, wherein the analyzing differences between corresponding regions in the new version and the old version further comprises analyzing alignment properties in the new version and the old version.

6. The method of claim 1, wherein describing the differences using the transformation further comprises using a linear transformation function.

7. The method of claim 1, wherein describing the differences using the transformation further comprises using a transformation function that includes an N-byte value and a piece-wise constant function.

8. The method of claim 1, further comprising accounting for one of a preprocessing success rate and an amount of preprocessing data.

9. The method of claim 1, further comprising defining a piece-wise function for inclusion in a client device.

10. The method of claim 1, further comprising providing creating hint data using a serving computer.

11. The method of claim 1, further comprising defining hint data which includes a transformation function to describe the differences.

12. A computer system including at least one processor to perform file differencing by:

using the at least one processor and identifying portions in an original version of software image and in a new version of a software image, wherein the plurality of portions comprise at least one table of pointers that include compact functional differences; and

using the at least one processor and preprocessing the plurality of portions comprising,

identifying matching paths in the new version and the old version, including identifying matching file names;

analyzing differences between corresponding portions in the new version and the old version; and

describing the differences using a transformation that depends on values of groups of bytes in the corresponding portions.

13. The system of claim 12, wherein the original version and the new version comprise execute-in-place (XIP) files.

14. The system of claim 12, further operable to perform file differencing by using hint data as part of a preprocessing operation.

15. The system of claim 14, further operable to perform file differencing by using the hint data generated from at least one software image.

16. The system of claim 12, further operable to perform file differencing by analyzing differences including using alignment information associated with the new version and the old version.

17. A computer system to generate difference information comprising:

a processor coupled to a preprocessing engine, the preprocessing engine operable to preprocess image information by;

identifying a plurality of regions in an old version of software and in a new version of software, wherein the plurality of regions comprise compact functional differences (CFD) preprocessing regions, wherein the CFD preprocessing regions comprise at least one table of pointers;

identifying matching paths in the new version and the old version, including using a matching technique based in part on file information in the new version and the old version;

analyzing differences between corresponding regions in the new version and the old version; and

describing the differences using a transformation function that depends in part on at least one value of a group of bytes in at least one corresponding region.

18. The system of claim 17, wherein the preprocessing engine is further operable to preprocess the image information by using a piece-wise constant function to describe the differences.

19. The system of claim 17 further operable to communicate preprocessed image data to a client device.