Byte-level file differencing and updating algorithms

• US 8,156,071 B2
• Filed: 06/15/2005
• Issued: 04/10/2012
• Est. Priority Date: 05/13/2002
• Status: Expired due to Fees

• Current Assignee: Qualcomm, Inc.
• Original Assignee: InnoPath Software, Inc. (Qualcomm, Inc.)
• Inventors: Gu, Jinsheng, Peng, Luosheng
• Primary Examiner(s): DOAN, DUYEN MY
• Application Number:
  US11/154,492
• Publication Number:
  US 20050234997A1
• Time in Patent Office: 2,491 Days
• Field of Search: 707/1, 707/101, 707/203, 707/204, 707/610, 717/168, 341 50- 51
• US Class Current: 707/101
• 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, the system including

a memory;

a processor processing at least one application, wherein the processor is configured to;

receive two byte streams including byte streams corresponding to an original file and a new file;

determine a longest common sub-string (LCS) between the two byte streams;

divide each of the two byte streams into a plurality of sub-streams, and when the LCS is at least a first pre-specified size, recursively determine another LCS between at least two sub-streams of the plurality of sub-streams and re-divide each sub-stream until a size of the sub-streams is less than a second pre-specified size, wherein the second pre-specified size of the sub-streams is proportional to computation time of byte-level differencing between sub-streams of the plurality of sub-streams;

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

generate a delta file that includes the byte-level difference.

2. The system of claim 1, wherein a first sub-stream of the plurality of sub-streams is a prefix to the respective LCS.

3. The system of claim 1, wherein a second sub-stream of the plurality of sub-streams is a suffix to the respective LCS.

4. The system of claim 1, wherein the new file includes updated and revised versions of the original file.

5. The system of claim 1, wherein the processor is configured to structure the delta file using a set of operation codes and a variable length integer format that eliminates redundant information in the delta file.

6. The system of claim 5, 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.

7. The system of claim 1, wherein the processor is configured to generate an operation array that codes the determined byte-level differences.

8. The system of claim 7, wherein the processor is configured to merge operations of the operation array to reduce an amount of meta-data.

9. The system of claim 7, wherein the processor is configured to write the operation array to the delta file.

10. The system of claim 9, wherein the processor is configured to write the operation array using relative start addresses to identify locations of byte stream modifications.

11. The system of claim 7, wherein the processor is configured to, in the absence of an LCS between two byte streams or between two sub-streams, write 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.

12. The system of claim 7, wherein the processor is configured to, in the absence of an LCS between two byte streams or between two sub-streams, write 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.

13. The system of claim 7, wherein the processor is configured to merge operations of the operation array by locating short sequences of match operations in the operation array and replacing the match operations of the short sequence with substitution operations.

14. The system of claim 13, wherein the short sequences include three or less sequential match operations.

15. The system of claim 7, wherein the processor is configured to merge operations of the operation array by 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.

16. The system of claim 7, wherein the processor is configured to merge operations of the operation array by locating sequences including at least one combination of insertion, deletion, and substitution operations and replacing the sequences with a single variable length replacement operation.

17. The system of claim 7, wherein the processor is configured to merge operations of the operation array by locating sequences including an equal number of insertion and deletion operations and replacing the sequences with a single fixed length replacement operation.

18. The system of claim 7, wherein the processor is configured to merge operations of the operation array by locating a unit of operations that repeats in a pattern 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.

19. The system of claim 18, wherein the unit includes a fixed-length sequence of replacement operations and a fixed-length sequence of another type of operation.

20. The system of claim 7, wherein the processor is configured to merge operations of the operation array by 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.

21. The system of claim 1, wherein a format of the delta file 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.

22. The system of claim 1, wherein the processor is configured to halve each of the two byte streams upon determining that the byte streams are longer than a maximum size.

23. The system of claim 1, wherein the processor is configured to compress the delta file.

24. The system of claim 1, wherein the processor is configured to apply error correction coding to the delta file.

25. The system of claim 1, wherein the processor is configured to transmit the delta file over at least one wireless link.

26. The system of claim 1, further comprising a mobile client device that includes an embedded system, the embedded system configured to:

receive the delta file;

generate a copy of the new file using the delta file and a local copy of the original file; and

update a local copy of the original file using the copy of the new file.

27. The system of claim 26, wherein the mobile client device is at least one of a personal computer, portable computing device, cellular telephone, portable communication device, and personal digital assistant.

28. The system of claim 26, further comprising at least one server of a communication service provider coupled among the processor and the mobile client device, wherein the at least one server is configured to:

receive the delta file from the processor;

generate a message to the mobile client device in response to receipt of the delta file, wherein the message informs a user of the mobile client device of the availability of an update to the embedded system;

receive a request for the update from the user; and

provide the delta file to the mobile client device in response to the request.

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

30. A system including

a memory;

a processor processing at least one application, the processor configured to;

determine a longest common sub-string (LCS) between two byte streams;

divide each of the two byte streams into a plurality of sub-streams, and when the LCS is at least a first pre-specified size, recursively determine another LCS between at least two sub-streams of the plurality of sub-streams and perform at least one division of each sub-stream until a size of the sub-streams is less than a second pre-specified size, wherein the second pre-specified size is proportional to computation time of byte level differencing between sub-streams of the plurality of sub-streams; and

determine a byte-level difference between each of the corresponding sub-streams.

31. The system of claim 30, wherein the at least one processor is configured to generate a delta file that includes information of the byte-level difference.

32. The system of claim 31, wherein the at least one processor is configured to generate the delta file using a set of operation codes and a variable length integer format that eliminates redundant information in the delta file.

33. The system of claim 31, wherein the at least one processor is configured to transfer the delta file to at least one mobile device for use in updating electronic files of the mobile device.

34. The system of claim 30, wherein the two byte streams include byte streams of an original file and byte streams of a new file, wherein the byte-level difference represents a difference between the original file and the new file.