System and method of updating programs and data

• US 8,438,558 B1
• Filed: 03/27/2009
• Issued: 05/07/2013
• Est. Priority Date: 03/27/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Adams, Stephen Robert
• Primary Examiner(s): TECKLU, ISAAC TUKU
• Application Number:
  US12/383,616
• Time in Patent Office: 1,502 Days
• Field of Search: None
• US Class Current: 717/170
• CPC Class Codes: G06F 8/658 Incremental updates; Differential updates

Abstract

A system and method are provided to (a) convert an older or base version of software into an alternate representation of the base version; (b) convert a newer or updated version of software into an alternate representation of the updated version; (c) compare the alternate updated version with the alternate base version (d) modify portions of the alternate updated version based on the comparison and (e) create a patch, where the patch represents the differences between the alternate updated version and the alternate base version.

Claims

1. A method of generating a patch comprising:

converting a first version of a program into a first alternate representation, the first alternate representation distinguishing between first references and first non-references, where the first references are portions of the first version that refer to other portions of the first version and where the first non-references are portions of the first version that do not refer to other portions of the first version;

converting a second version of the program into a second alternate representation where portions of the second version are the same as the first version and where portions of the second version are different than the first version, the second alternate representation distinguishing between second references and second non-references, where the second references are portions of the second version that refer to other portions of the second version and where the second non-references are portions of the second version that do not refer to other portions of the second version;

modifying, using a processor, a portion of the second alternate representation based on a comparison of the second references with the first references while retaining information to convert the modified second alternate representation back into the second version; and

generating a patch representing the differences between the first alternate representation and the modified second alternate representation.

2. The method of claim 1 wherein modifying a portion of the second representation further comprises modifying the second representation so as to reduce the differences between the first and second representation.

3. The method of claim 1 further comprising identifying targets, where a target is a portion of the version that is referred to by a reference.

4. The method of claim 3 wherein each representation associates each target and each reference with an index value, such that each target is assigned a unique index value, and such that each reference is assigned the index value of the reference'"'"'s target.

5. The method of claim 4 wherein each representation stores the references as an ordered list of indexes, where the order reflects the relative order of the references in the version.

6. The method of claim 1 wherein each representation stores a control list of values, where each member of the control list is associated with a portion of the version, and where the value of a member identifies whether the portion is a reference or a non-reference.

7. The method of claim 1 wherein each representation stores a list of non-references, where each member of the non-reference list is associated with a non-reference portion of the version, and where the value of a member identifies the value of the non-reference portion in the version.

8. The method of claim 7 wherein a plurality of the members of the non-reference list are associated with operations.

9. The method of claim 8 wherein the operations are represented in the non-reference list based on a machine code value.

10. The method of claim 1 wherein the first and second references comprise absolute addresses.

11. The method of claim 1 wherein the first and second references comprise relative addresses.

12. The method of claim 1 wherein the first and second references comprise absolute and relative addresses.

13. The method of claim 1 wherein the patch is executable by a processor.

14. The method of claim 1, wherein modifying the second representation based on a comparison of the second references with the first references comprises using an algorithm selected from the group consisting of a simulated annealing algorithm, a depth-first search algorithm, a sub-graph isomorphism algorithm, a genetic programming algorithm, or a combination thereof.

15. The method of claim 1 further comprising transmitting the patch over a network to a computing device.

16. A system comprising:

a memory storing instructions and data, the data comprising a first version of a program and a second version of the program;

a processor to execute the instructions and to process the data;

wherein the instructions comprise;

converting the first version of the program into a first alternate representation, the first alternate representation distinguishing between first references and first non-references, where the first references are portions of the first version that refer to other portions of the first version and where the first non-references are portions of the first version that do not refer to other portions of the first version;

converting the second version of the program into a second alternate representation where portions of the second version are the same as the first version and where portions of the second version are different than the first version, the second alternate representation distinguishing between second references and second non-references, where the second references are portions of the second version that refer to other portions of the second version and where the second non-references are portions of the second version that do not refer to other portions of the second version;

modifying a portion of the second alternate representation based on a comparison of the second references with the first references while retaining information to convert the modified second alternate representation back into the second version; and

storing, in the memory, a patch representing the differences between the first alternate representation and the modified second alternate representation.

17. The system of claim 16 wherein modifying a portion of the second representation further comprises modifying the second representation so as to reduce the differences between the first and second representation.

18. The system of claim 16, wherein the instructions further comprise identifying targets, where a target is a portion of the version that is referred to by a reference.

19. The system of claim 18, wherein each representation associates each target and each reference with an index value, such that each target is assigned a unique index value, and such that each reference is assigned the index value of the reference'"'"'s target.

20. The system of claim 19 wherein each representation stores the references as an ordered list of indexes, where the order reflects the relative order of the references in the version.

21. The system of claim 16 wherein each representation stores a control list of values, where each member of the control list is associated with a portion of the version, and where the value of a member identifies whether the portion is a reference or a non-reference.

22. The system of claim 16 wherein each representation stores a list of non-references, where each member of the non-reference list is associated with a non-reference portion of the version, and where the value of a member identifies the value of the non-reference portion in the version.

23. The system of claim 22 wherein a plurality of the members of the non-reference list are associated with operations.

24. The system of claim 23 wherein the operations are represented in the non-reference list based on a machine code value.

25. The system of claim 16 wherein the first and second references comprise absolute addresses.

26. The system of claim 16 wherein the first and second references comprise relative addresses.

27. The method of claim 16 wherein the first and second references comprise absolute and relative addresses.

28. The system of claim 16 further comprising a network and a computing device, wherein the instructions further comprise transmitting the patch over the network to the computing device.

29. A system comprising:

a first computer at a first node of a network, the first computer comprising a first memory storing a first set of instructions and a first processor that processes data in accordance with the first set of instructions;

the first computer having access to a first version of a program;

a second computer at a second node of a network, the second computer comprising a second memory storing a second set of instructions and a second processor that processes data in accordance with the second set of instructions;

the second computer having access to the first version of the program and having access to a second version of the program;

wherein the second set of instructions comprise;

converting the first version of the program into a first alternate representation, the first alternate representation distinguishing between first references and first non-references, where the first references are portions of the first version that refer to other portions of the first version and where the first non-references are portions of the first version that do not refer to other portions of the first version;

converting the second version of the program into a second alternate representation where portions of the second version are the same as the first version and where portions of the second version are different than the first version, the second alternate representation distinguishing between second references and second non-references, where the second references are portions of the second version that refer to other portions of the second version and where the second non-references are portions of the second version that do not refer to other portions of the second version;

modifying a portion of the second alternate representation based on a comparison of the second references with the first references while retaining information to convert the modified second alternate representation back into the second version;

generating a patch representing the differences between the first alternate representation and the modified second alternate representation, and

transmitting the patch to the first computer;

and wherein the first set of instructions comprise;

converting the first version of the program into the first alternate representation;

receiving the patch representing the differences between the first alternate representation and the modified second alternate representation;

creating, based on the patch, the modified second alternate representation from the first alternate representation; and

converting the modified second alternate representation into the second version of the program.

30. The system of claim 29 wherein modifying a portion of the second representation further comprises modifying the second representation so as to reduce the differences between the first and second representation.

31. The system of claim 29, wherein the first set of instructions further comprise identifying targets, where a target is a portion of the version that is referred to by a reference.

32. The system of claim 31, wherein each representation associates each target and each reference with an index value, such that each target is assigned a unique index value, and such that each reference is assigned the index value of the reference'"'"'s target.

33. The system of claim 32 wherein each representation stores the references as an ordered list of indexes, where the order reflects the relative order of the references in the version.

34. The system of claim 29 wherein each representation stores a control list of values, where each member of the control list is associated with a portion of the version, and where the value of a member identifies whether the portion is a reference or a non-reference.

35. The system of claim 29 wherein each representation stores a list of non-references, where each member of the non-reference list is associated with a non-reference portion of the version, and where the value of a member identifies the value of the non-reference portion in the version.

36. The system of claim 35 wherein a plurality of the members of the non-reference list are associated with operations.

37. The system of claim 36 wherein the operations are represented in the non-reference list based on a machine code value.