Software patch generator

• US 6,289,509 B1
• Filed: 09/01/1998
• Issued: 09/11/2001
• Est. Priority Date: 09/01/1998
• Status: Expired due to Term

• Current Assignee: PKWARE, Inc. (PKW Holdings, Inc.)
• Original Assignee: PKWARE, Inc. (PKW Holdings, Inc.)
• Inventors: Kryloff, Sergey A.
• Primary Examiner(s): Powell, Mark
• Assistant Examiner(s): NGUYEN BA, HOANG VU A
• Application Number:
  US09/144,666
• Time in Patent Office: 1,106 Days
• Field of Search: 395/712, 395/709, 395/701, 341/50, 364/200, 707/203, 709/221, 711/102, 712/300, 717/11, 717/9, 717/1
• US Class Current: 717/170
• CPC Class Codes: G06F 8/658 Incremental updates; Differential updates

Abstract

A system for generating a patch file from an old version of computer code which consists of a series of elements and a new version of computer code which also consists of a series of elements. Both the old and new versions of computer code are stored in a memory of a computer. An alphabet for processing the old and new versions of computer code is programmed into the computer and, once established, the old version of computer code is sorted with the data processor alphabetically according to the established alphabet to create a first sorted list of code. A pointer is maintained in order to indicate each element'"'"'s original location in the old version of computer code. Similarly, the new version of computer code is also sorted alphabetically to create a second sorted list of code with a pointer of each element to indicate the element'"'"'s original location in the new version of computer code. Once the two sorted lists are created, they are recursively compared one word (a group of elements) at a time to search for a match of the codes. Upon finding a match of the codes, the first and second sorted lists of code are searched to find the largest sequence of coinciding elements preceding and succeeding the match of the codes. Each sequence of coinciding words is then stored in a coincidences list. The coincidences list is processed to remove duplicative information and a patch file is created from the processed coincidences list.

Claims

1. A method of generating a patch file from an old version of computer code consisting of a series of elements and a new version of computer code consisting of a series of elements where both the old and new versions of computer code are stored in a memory and accessible by a data processor, the method comprising the steps of:

establishing an alphabet for processing the old and new versions of computer code where a word consists of one or more elements of the alphabet;

sorting the old version of computer code with the data processor alphabetically according to the established alphabet to create a first sorted list of code and maintaining a pointer for each element of the first sorted list of code indicating the element'"'"'s original location in the old version of computer code;

sorting the new version of computer code with the data processor alphabetically according to the established alphabet to create a second sorted list of code and maintaining a pointer for each element of the second sorted list of code indicating the element'"'"'s original location in the new version of computer code;

recursively comparing the first and second sorted lists of code one word at a time for a match of the codes, and storing the match of codes as a sequence of coinciding elements in a coincidences list;

upon finding a match of the codes, searching the first and second sorted lists of code again to find the largest sequence of coinciding elements preceding and succeeding the match of codes;

storing the largest sequence of coinciding elements in the coincidences list;

processing the coincidences list to remove duplicative coincidences; and

creating a patch file from the processed coincidences list.

2. The method of claim 1, wherein the patch file includes a series of write commands.

3. The method of claim 2, wherein creating a patch file from the processed coincidences list includes the steps of:

(a) finding a largest block of coinciding elements of the processed coincidences list that matches the second sorted list of code and recording the location of the largest found block;

(b) in the area before the previously found block, finding the next largest block of coinciding elements of the processed coincidences list that matches the second sorted list of code and recording the location of the next largest found block;

(c) repeating step (b) until

(i) the first member in the processed list of coincidences is reached;

or

(ii) there are no matches between the second sorted list of code and the processed coincidences list;

(d) writing a write from the old version of computer code command and offset and length information to the patch file if the first member of the processed list of coincidences is reached; and

(e) writing a write from patch file command and length and patch information to the patch file when there is no match between the second sorted list of code and the processed coincidences list.

4. A system for generating a patch file from an old version of computer code consisting of a series of elements and a new version of computer code consisting of a series of elements, the system comprising:

a data processor;

a memory storing the old and new versions of computer code;

means for sorting the old version of computer code with the data processor alphabetically according to an established alphabet to create a first sorted list of code and for maintaining a pointer for each element of the first sorted list of code indicating the element'"'"'s original location in the old version of computer code;

means for sorting the new version of computer code with the data processor alphabetically according to an established alphabet to create a second sorted list of code and for maintaining a pointer for each element of the second sorted list of code indicating the element'"'"'s original location in the new version of computer code;

means for searching the first and second sorted lists of code to find a match of codes, the match of codes including a sequence of coinciding elements;

means for storing the sequence of coinciding elements in a coincidences list;

means for processing the coincidences list to remove duplicative coincidences therefrom; and

means for creating a patch file from the processed coincidences list.

5. A system as in claim 4, wherein the means for creating a patch file includes:

means for finding the largest block of coinciding elements of the processed coincidences list that matches the second sorted list of code and recording the location of the largest found block of coinciding elements in a memory;

means for finding the next largest block of coinciding elements of the processed coincidences list that matches the second sorted list of code and recording the location of the next largest block of coinciding elements in the memory;

means for writing a write form the old version of computer code command and offset and length information to the patch file; and

means for writing a write from patch file command and length and patch information to the patch file.