System and method for upgrading client software

• US 6,425,125 B1
• Filed: 03/30/1999
• Issued: 07/23/2002
• Est. Priority Date: 03/30/1999
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wahlert, Brian, Fries, Robert M.
• Primary Examiner(s): Morse, Gregory
• Assistant Examiner(s): DAS, CHAMELI
• Application Number:
  US09/281,734
• Time in Patent Office: 1,211 Days
• Field of Search: 717/11, 717/1, 717/5, 717/170, 717/174, 717/169, 710/1, 710/2, 703/21, 703/20, 711/2
• US Class Current: 717/168
• CPC Class Codes: G06F 8/658 Incremental updates; Differential updates

Abstract

A system for upgrading software has multiple clients coupled to an upgrade server. The clients store an old version of software. The upgrade server stores both the old version of software and a new version of software. The upgrade server creates an upgrade file from the old and new versions of the software such that the upgrade file is smaller than the new version. The upgrade server compares old character strings from the old version with new character strings from the new version to identify matching sections. The upgrade server derives a two-dimensional table containing multiple entries, whereby each entry represents a length of a longest common substring beginning at a first position in the old character string and at a second position in the new character string. The upgrade server then ascertains the longest common substring from the table. The upgrade server inserts headers into the upgrade file to distinguish between matching and non-matching sections. For matching sections, only the header is included and the section is omitted. The clients receive the upgrade file and begin processing the file to reconstruct the new version of software from the new sections included in the upgrade file and from the matching sections obtained locally from the stored old version of software.

Claims

1. A method for constructing an upgrade file to upgrade from an old version of software to a new version of software, comprising the following steps:

distinguishing between matching sections that match in both the old version and the new version from non-matching sections in the new version that have no match in the old version;

for matching sections, inserting in the upgrade file a first token identifying a corresponding section in the old version that matches a section in the new version; and

for non-matching sections, inserting in the upgrade file a second token and the non-matching section from the new version.

2. A method as recited in claim 1, wherein the first token comprises a header with at least one field indicating a number of bytes contained in the corresponding section in the old version.

3. A method as recited in claim 1, wherein the first token comprises a header with at least one first field indicating a number of bytes contained in the corresponding section in the old version and at least one second field holding an offset value into the old version to locate the corresponding section.

4. A method as recited in claim 1, wherein the second token comprises a header with at least one field indicating a number of bytes contained in the non-matching section in the new version.

5. A method as recited in claim 1, wherein:

the first token comprises a byte count indicating a number of bytes needed to represent an amount of data in the corresponding section, a data length indicating a number of bytes in the corresponding section, and an offset value into the old version to locate the corresponding section; and

the second token comprises a header with the byte count and the data length.

6. A method as recited in claim 1, further comprising the step of identifying the matching sections by performing the following steps:

comparing an old character string from the old version with a new character string from the new version;

finding longest common substrings beginning at first positions in the old character string and second positions in the new character string; and

for a particular second position in the new character string, ascertaining the longest common substring beginning at the particular second position.

7. A method as recited in claim 6, wherein the finding step comprises the step of constructing a two-dimensional table having multiple entries cross-indexed by the old and new character strings, individual entries representing a length of a longest common substring.

8. A method as recited in claim 1, further comprising the step of identifying the matching sections by performing the following steps:

hashing every possible group of k contiguous bytes in the old version to form first hash values;

hashing every possible group of k contiguous bytes in the new version to form second hash values; and

in an event that one of the first hash values equals one of the second hash values, comparing an old character string from the old version that includes the k contiguous bytes forming said one first hash value with a new character string from the new version that includes the k contiguous bytes forming said one second hash value.

9. A method as recited in claim 8, further comprising the following steps:

finding longest common substrings beginning at first positions in the old character string and second positions in the new character string; and

for a particular second position in the new character string, ascertaining the longest common substring beginning at the particular second position.

10. A method as recited in claim 9, wherein the finding step comprises the step of constructing a two-dimensional table having multiple entries cross-indexed by the old and new character strings, individual entries representing a length of a longest common substring.

11. A method as recited in claim 1, wherein the old version and the new version are at least partly compressed, further comprising the step of identifying the matching sections by performing the following steps:

decompressing the old version to form a decompressed old version;

decompressing the new version to form a decompressed new version;

comparing an old character string from the decompressed old version with a new character string from the decompressed new version;

finding longest common substrings beginning at first positions in the old character string and second positions in the new character string; and

for a particular second position in the new character string, ascertaining the longest common substring beginning at the particular second position.

12. A method as recited in claim 11, wherein the decompressing steps each comprise the following steps:

evaluating the old or new version section by section;

identifying compressed sections; and

decompressing the compressed sections.

13. A method as recited in claim 12, further comprising the step of inserting spacers between the sections.

14. A method as recited in claim 12, further comprising the step of writing into the upgrade file commands enabling recompression of the compressed sections at the client.

15. A method as recited in claim 1, wherein the old version and the new version are at least partly compressed, further comprising the step of identifying the matching sections by performing the following steps:

decompressing the old version to form a decompressed old version;

decompressing the new version to form a decompressed new version;

hashing every possible group of k contiguous bytes in the decompressed old version to form first hash values;

hashing every possible group of k contiguous bytes in the decompressed new version to form second hash values; and

in an event that one of the first hash values equals one of the second hash values, comparing an old character string from the decompressed old version that includes the k contiguous bytes forming said one first hash value with a new character string from the decompressed new version that includes the k contiguous bytes forming said one second hash value.

16. A method as recited in claim 15, wherein the decompressing steps each comprise the following steps:

evaluating the old or new version section by section;

identifying compressed sections; and

decompressing the compressed sections.

17. A method as recited in claim 16, further comprising the step of inserting spacers between the sections.

18. A method as recited in claim 16, further comprising the step of writing into the upgrade file commands enabling recompression of the compressed sections at the client.

19. A method as recited in claim 1, further comprising the step of using the upgrade file to upgrade the old version to the new version.

20. A computer-readable medium having computer-executable instructions for performing the steps as recited in claim 1.

21. A method for constructing an upgrade file to upgrade from an old version of software to a new version of software, comprising the following steps:

comparing an old character string from the old version with a new character string from the new version;

finding longest common substrings beginning at first positions in the old character string and second positions in the new character string;

for a particular second position in the new character string, ascertaining the longest common substring beginning at the particular second position;

inserting, in the upgrade file, a pointer header representing the longest common substring in lieu of inserting the longest common substring, the pointer header indicating a corresponding position in the old character string at which the longest common substring begins;

inserting, in the upgrade file, characters from the new character string that are not included in the longest common substring; and

placing a data header indicating that the characters being inserted are not matched in the old character string.

22. A method as recited in claim 21, wherein the finding step comprises the step of constructing a two-dimensional table having multiple entries cross-indexed by the old and new character strings, individual entries representing a length of a longest common substring beginning at a first position in the old character string and a second position in the new character string.

23. A method as recited in claim 21, wherein the pointer header includes a byte count indicating a number of bytes contained in the longest common substring.

24. A method as recited in claim 21, wherein the pointer header includes a byte count indicating a number of bytes contained in the longest common substring and an offset value identifying a corresponding first position in the old character string at which the longest common substring begins.

25. A method as recited in claim 21, wherein the data header includes a byte count indicating a number of bytes of the characters being inserted.

26. A method as recited in claim 21, further comprising the step of using the upgrade file to upgrade the old version to the new version.

27. A method for constructing an upgrade file to upgrade from an old version of software to a new version of software, comprising the following steps:

hashing every possible group of k contiguous bytes in the old version to form first hash values;

hashing every possible group of k contiguous bytes in the new version to form second hash values;

in an event that one of the first hash values equals one of the second hash values, comparing an old character string from the old version that includes the k contiguous bytes forming said one first hash value with a new character string from the new version that includes the k contiguous bytes forming said one second hash value;

finding longest common substrings beginning at first positions in the old character string and second positions in the new character string; and

for a particular second position in the new character string, ascertaining the longest common substring beginning at the particular second position.

28. A method as recited in claim 27, further comprising the following steps:

inserting, in the upgrade file, a pointer header representing the longest common substring in lieu of inserting the longest common substring, the pointer header indicating a corresponding position in the old character string at which the longest common substring begins;

inserting, in the upgrade file, characters from the new character string that are not included in the longest common substring; and

placing a data header indicating that the characters being inserted are not matched in the old character string.

29. A method as recited in claim 27, wherein the old version and the new version are at least partly compressed, further comprising the step of decompressing the old and new versions prior to the hashing steps.

30. A method for upgrading software in a client remotely from an upgrade server, comprising the following steps:

at the upgrade server, performing the following steps;

comparing an old character string from an old version of software with a new character string from a new version of software;

finding longest common substrings beginning at a first position in the old character string and a second position in the new character string;

for a particular second position in the new character string, ascertaining the longest common substring beginning at the particular second position;

inserting, in an upgrade file, a pointer header representing the longest common substring in lieu of inserting the longest common substring, the pointer header indicating a corresponding position in the old character string at which the longest common substring begins;

inserting, in the upgrade file, characters from the new character string that are not included in the longest common substring;

placing a data header indicating that the characters being inserted are not matched in the old character string; and

transferring the upgrade file to the client;

at the client, performing the following steps;

receiving the upgrade file from the upgrade server;

processing the upgrade server to reconstruct the new version of software;

for any section in the upgrade file demarcated by the data header, adding the new characters to the reconstructed new version; and

for any section in the upgrade file demarcated by the pointer header, copying the longest common substring from the old version into the reconstructed new version.

31. A method as recited in claim 30, wherein the finding step comprises the step of constructing a two-dimensional table having multiple entries cross-indexed by the old and new character strings, each entry representing the longest common substring beginning at the first position in the old character string and at the second position in the new character string.

32. A method as recited in claim 30, wherein the pointer header includes a byte count indicating a number of bytes contained in the longest common substring.

33. A method as recited in claim 30, wherein the pointer header includes a byte count indicating a number of bytes contained in the longest common substring and an offset value identifying a corresponding first position in the old character string at which the longest common substring begins.

34. A method as recited in claim 30, wherein the data header includes a byte count indicating a number of bytes of the characters being inserted.

35. A software upgrading system, comprising:

a client having a processor and a memory, the memory storing an old version of software;

an upgrade server having a processor and a memory, the upgrade server memory storing both the old version of software and a new version of software, the upgrade server identifying a longest common substring that is common to both the old version and the new version and creating an upgrade file with a pointer header representing the longest common substring in lieu of the longest common substring, the pointer header indicating a corresponding position in the old version at which the longest common substring begins, and the upgrade file further containing at least one section from the new version that is not included in the longest common substring and a data header indicating that the section is new; and

the client processing the upgrade file to reconstruct the new version of software by adding the new section corresponding to the data header and using the longest common substring in the old version that is identified by the pointer header.

36. A system as recited in claim 35, wherein the upgrade server constructs a table having multiple entries, in which an individual entry represents a length of a longest common substring beginning at a first position in the old character string and at a second position in the new character string, the upgrade server ascertaining the longest common substring beginning at a particular second position.

37. A system as recited in claim 35, wherein the upgrade server hashes every possible group of k contiguous bytes in the old version and every possible group of k contiguous bytes in the new version and only considers substrings that include k contiguous bytes that hash to the same value.

38. A system as recited in claim 35, wherein the pointer header includes a byte count indicating a number of bytes contained in the longest common substring.

39. A system as recited in claim 35, wherein the pointer header includes a byte count indicating a number of bytes contained in the longest common substring and an offset value identifying a corresponding first position in the old version at which the longest common substring begins.

40. A system as recited in claim 35, wherein the data header includes a byte count indicating a number of bytes of the section being added.

41. A computer-readable medium that stores computer-executable instructions for directing a computer to perform the following steps:

comparing an old character string from an old version of software with a new character string from a new version of software;

finding longest common substrings beginning at first positions in the old character string and second positions in the new character string;

for a particular second position in the new character string, ascertaining the longest common substring beginning at the particular second position;

inserting, in the upgrade file, a pointer header representing the longest common substring in lieu of inserting the longest common substring, the pointer header indicating a corresponding position in the old character string at which the longest common substring begins;

inserting, in the upgrade file, characters from the new character string that are not included in the longest common substring; and

placing a data header indicating that the characters being inserted are not matched in the old character string.

42. A computer-readable medium that stores computer-executable instructions for directing a computer to perform the following steps:

hashing every possible group of k contiguous bytes in the old version to form first hash values;

hashing every possible group of k contiguous bytes in the new version to form second hash values;

in an event that one of the first hash values equals one of the second hash values, comparing an old character string from the old version that includes the k contiguous bytes forming said one first hash value with a new character string from the new version that includes the k contiguous bytes forming said one second hash value;

finding longest common substrings beginning at first positions in the old character string and second positions in the new character string; and

for a particular second position in the new character string, ascertaining the longest common substring beginning at the particular second position.