Byte-level file differencing and updating algorithms

• US 6,925,467 B2
• Filed: 05/13/2002
• Issued: 08/02/2005
• Est. Priority Date: 05/13/2002
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: InnoPath Software, Inc. (Qualcomm, Inc.)
• Inventors: Gu, Jinsheng, Peng, Luosheng
• Primary Examiner(s): Harvey, Jack
• Assistant Examiner(s): Nguyen, Hai V.
• Application Number:
  US10/146,545
• Publication Number:
  US 20030212712A1
• Time in Patent Office: 1,177 Days
• Field of Search: 707/1, 707/101, 707/203, 707/204, 715/511, 709/203, 714/38, 717/168, 717/170
• US Class Current: 707/687
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A method for performing differencing and updating between electronic files is provided. A byte-level file differencing algorithm receives two byte streams corresponding to an original file and a new file. The new file includes updated and revised versions of the original file. The file differencing algorithm determines a longest common sub-string (LCS) between the two byte streams and divides each of the two byte streams into sub-streams. The sub-streams include the LCS along with prefix and suffix sub-streams to the LCS. The file differencing algorithm then recursively determines an LCS and divides each sub-stream until a size of the sub-streams is less than a pre-specified size. Byte-level differences are then identified between each of the corresponding sub-streams. Further, the file differencing algorithm defines a protocol for structuring a delta file by using a set of operation codes and a variable length integer format to eliminate redundant information in the delta file. Using this protocol, the file differencing algorithm generates the delta file including an operation array that codes the identified byte-level differences.

Claims

1. A system for updating electronic files comprising byte-level file differencing and updating (FDU) algorithms, wherein the file differencing algorithm of the FDU algorithms is hosted on a first device, the file differencing algorithm:

receiving two byte streams including byte streams corresponding to an original file and a new file, wherein the new file includes updated and revised versions of the original file;

determining a longest common sub-string (LCS) between the two byte streams and divides each of the two byte streams into sub-streams, wherein a first sub-stream is a prefix and a second sub-stream is a suffix to the respective LCS;

recursively determining an LCS and dividing each sub-stream until a size of the sub-streams is less than a pre-specified size and determines a byte-level difference between each of the corresponding sub-streams;

defining a protocol for structuring a delta file by using a set of operation codes and a variable length integer format to eliminate redundant information in the delta file;

generating the delta file including an operation array that codes the determined byte-level differences, wherein generating comprises merging operations of the operation array to reduce an amount of meta-data;

transferring the delta file to a second device via at least one coupling.

2. The system of claim 1, wherein the file updating algorithm of the FDU algorithms is hosted on a second device, the file updating algorithm:

receiving the delta file from the first device via the at least one coupling;

generating a copy of the new file using the delta file and a hosted original file;

updating the original file in the second device using the copy.

3. The system of claim 1, wherein the first device is a processor-based device accessible by at least one provider of software running on the second device.

4. 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.

5. The system of claim 1, wherein the at least one coupling is selected from among wireless connections, wired connections, hybrid wireless/wired connections, and couplings to networks including local area networks (LANs), metropolitan area networks (MANs), wide area networks (WANs), proprietary networks, backend networks, the Internet, and removable fixed mediums including floppy disks, hard disk drives, and CD-ROM disks, as well as telephone lines, buses, and electronic mail messages.

6. The system of claim 1, wherein the original and new files comprise software files including dynamic link library files, shared object files, embedded software components (EBSCs), firmware files, executable files, data files including hex data files, system configuration files, and files including personal use data.

7. The system of claim 1, further comprising at least one server of a communication service provider coupled among the first and second devices, wherein the at least one server:

receives the delta file from the first device;

generates a message to the second device in response to receipt of the delta file, wherein the message informs a user of the second device of the availability of an update to at least one electronic file hosted on the second device;

receives a request for the update from the user; and

provides the delta file to the second device in response to request.

8. A method for performing byte-level file differencing, comprising:

identifying a longest common sub-string (LCS) between two received byte streams, wherein the byte streams include a byte stream corresponding to an original file and a byte stream corresponding to a new file version of the original file;

dividing each of the two received byte streams into sub-streams, wherein a first sub-stream is a prefix and a second sub-stream is a suffix to the respective LCS;

recursively determining an LCS and dividing each sub-stream until a size of the sub-streams is less than a pre-specified size or an LCS is absent;

determining a byte-level difference between each of the corresponding sub-streams;

generating an operation array that codes the determined byte-level differences, wherein generating includes merging operations of the operation array to reduce an amount of meta-data; and

writing the operation array to a delta file, wherein writing comprises merging operations of the operation array to reduce an amount of meta-data and using a protocol for structuring the delta file by using a set of operation codes and a variable length integer format to eliminate redundant information in the delta file.

9. The method of claim 8, wherein writing the operation array further comprises using relative start addresses to identify locations of byte stream modifications.

10. The method of claim 8, wherein the variable length integer format uses one bit of a byte to indicate whether a following byte is read as part of an integer.

11. The method of claim 8, wherein the delta file format comprises a concatenation of a series of records selected from among an operation code, a relative start address of the new file at which the operation code is to be applied, and data of an insertion or replacement to the original file where necessary.

12. The method of claim 8, further comprising:

compressing the delta file; and

applying error correction coding to the delta file.

13. The method of claim 8, further comprising halving each of the two byte streams upon receiving the byte streams and determining that the byte streams are longer than a maximum specified size.

14. The method of claim 8, further comprising, in the absence of an LCS between two byte streams or between two sub-streams, writing replacement operations and deletion operations into appropriate locations of the operation array when a length of the byte stream corresponding to the new file is less than a length of the byte stream corresponding to the original file.

15. The method of claim 8, further comprising, in the absence of an LCS between two byte streams or between two sub-streams, writing replacement operations and insertion operations into appropriate locations of the operation array when a length of the byte stream corresponding to the new file is greater than a length of the byte stream corresponding to the original file.

16. The method of claim 8, wherein merging further comprises:

locating short sequences of match operations in the operation array, wherein the short sequences include three or less sequential match operations; and

replacing the match operations of the short sequence with substitution operations.

17. The method of claim 8, wherein merging further comprises:

locating sequences of operations other than match operations in the operation array; and

replacing the located sequences with a single operation specifying a type of the operation and a length of the sequence.

18. The method of claim 8, wherein merging further comprises:

locating sequences including at least one combination of insertion, deletion, and substitution operations; and

replacing the sequences with a single variable length replacement operation.

19. The method of claim 8, wherein merging further comprises:

locating sequences including an equal number of insertion and deletion operations; and

replacing the sequences with a single fixed length replacement operation.

20. The method of claim 8, wherein merging further comprises:

locating a unit of operations that repeats in a pattern, wherein the unit includes a fixed-length sequence of replacement operations and a fixed-length sequence of another type of operation; and

replacing the repeating unit with a single operation specifying a length of the sequence of replacement operations, a length of the unit, and a number of times the unit repeats in the pattern.

21. The method of claim 8, wherein merging further comprises:

placing operations appropriate to the operation array into a hash table; and

using a single copy operation including an offset parameter, wherein the copy operation inserts operations at the appropriate locations in the operation array using information of the hash table.

22. The method of claim 8, wherein the pre-specified size is approximately 4096 bytes.

23. A method for generating a difference file between electronic files, comprising:

receiving byte streams including an original byte stream and a new byte stream;

determining a size of each of the byte streams;

computing a longest common sub-string (LCS) between the byte streams using a linear-time analysis when each of the byte streams is of a first size;

generating at least one prefix byte stream set from each of the byte streams, wherein each prefix byte stream set includes bytes preceding the LCS;

generating at least one suffix byte stream set from each of the byte streams, wherein each suffix byte stream set includes bytes following the LCS;

recursively determining a size, computing the LCS, and generating at least one prefix and at least one suffix byte stream set for each of the generated prefix and suffix byte stream sets until the size of the generated prefix and suffix byte stream sets is less than a second size;

determining an edit distance between bytes of each of the generated prefix byte stream sets and between bytes of each of the generated suffix byte stream sets, wherein the edit distance is a minimum number of edit operations to transform the original byte stream into the new byte stream; and

generating a delta file comprising an operation array that includes information of the edit distance between the byte streams.

24. The method of claim 23, further comprising reducing a size of the delta file, comprising:

applying at least one merging and indexing operation to the operation array to reduce an amount of meta-data; and

writing the operation array using a variable length integer format, wherein redundant information of the operation array is reduced.

25. A method for performing byte-level file differencing and updating, comprising:

receiving two byte streams in a first system, wherein the two byte streams include byte streams corresponding to both an original file and a new file;

determining a longest common sub-string (LCS) between the two byte streams and dividing each of the two byte streams into sub-streams, wherein a first sub-stream is a prefix and a second sub-stream is a suffix to the respective LCS;

recursively determining an LCS and dividing each sub-stream until a size of the sub-streams is less than a pre-specified size and determining a byte-level difference between each of the corresponding sub-streams;

generating a delta file including an operation array that codes the determined byte-level differences, wherein generating comprises merging at least one operation of the operation array to reduce an amount of meta-data and writing the operation array using a variable length integer format;

transferring the delta file to a second system;

generating a copy of the new file in the second system using the delta file;

updating the original file in the second system using the copy of the new file.

26. An apparatus including at least one processing device configured to perform byte-level file differencing and updating, comprising:

means for receiving two byte streams including a byte stream corresponding to an original file and a byte stream corresponding to a new file;

means for determining a longest common sub-string (LCS) between the two received byte streams;

means for dividing each of the two received byte streams into sub-streams, wherein a first sub-stream is a prefix and a second sub-stream is a suffix to the respective LCS;

means for recursively determining an LCS and dividing each sub-stream until a size of the sub-streams is less than a pre-specified size;

means for determining a byte-level difference between each of the sub-streams, wherein byte-level differences are determined between the original file and the new file;

means for generating an operation array that codes the determined byte-level differences;

means for optimizing the operation array by merging operations to reduce file meta-data; and

means for generating a delta file by writing the optimized operation array using a variable length integer format.

27. An apparatus including at least one processing device configured to perform byte-level file differencing and updating, comprising:

means for receiving a delta file, wherein generation of the delta file comprises,

determining a longest common sub-string (LCS) between two byte streams including a byte stream corresponding to an original file and a byte stream corresponding to a new version of the original file,

dividing each of the two byte streams into sub-streams, wherein a first sub-stream is a prefix and a second sub-stream is a suffix to the respective LCS,

recursively determining an LCS and dividing each sub-stream until a size of the sub-streams is less than a pre-specified size,

determining a byte-level difference between each of the corresponding sub-streams,

generating the delta file by coding the byte-level differences in an operation array, merging at least one operation of the operation array to reduce an amount of meta-data, and writing the operation array using a variable length integer format;

means for generating a copy of the new file using the delta file; and

means for updating the original file in a second device using the copy.

28. A computer readable medium including executable instructions which, when executed in a processing system, performs byte-level file differencing and updating by:

determining a longest common sub-string (LCS) between two received byte streams, wherein the byte streams include a byte stream corresponding to an original file and a byte stream corresponding to a new file version of the original file;

dividing each of the two received byte streams into sub-streams, wherein a first sub-stream is a prefix and a second sub-stream is a suffix to the respective LCS;

recursively determining an LCS and dividing each sub-stream until a size of the sub-streams is less than a pre-specified size;

determining a byte-level difference between each of the corresponding sub-streams;

generating an operation array that codes the determined byte-level differences, wherein generating includes merging at least one operation of the operation array to reduce an amount of meta-data; and

writing the operation array to a delta file using a variable length integer format.