System for finding differences between two computer files and updating the computer files

• US 6,526,574 B1
• Filed: 01/17/2000
• Issued: 02/25/2003
• Est. Priority Date: 07/15/1997
• Status: Expired due to Term

• Current Assignee: Pocket Soft Incorporated
• Original Assignee: Pocket Soft Incorporated
• Inventors: Jones, Kerry N
• Primary Examiner(s): Morse, Gregory
• Assistant Examiner(s): DAS, CHAMELI
• Application Number:
  US09/463,035
• Time in Patent Office: 1,135 Days
• Field of Search: 717/167, 717/168-173, 707/203, 707/10, 707/1, 707/101, 707/511, 707/100, 707/2, 341/65, 341/50, 341/51, 382/232, 382/244, 382/246, 709/221, 709/203
• US Class Current: 717/168
• CPC Class Codes: G06F 8/60 Software deployment
• CPC Class Codes: G06F 8/658 Incremental updates; Differential updates
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A computer file update or patch process involves building a Patch File. The existing or original file (the OLD file) and the revised file (the NEW file) are input into a Patch Build program. The differences in the OLD file and the NEW file are determined by the Patch Build program, and this information is output by the Patch Build program as a Patch File. The Patch File is distributed, along with a Patch Apply program, to end users so that the OLD file is efficiently converted to the desired, updated NEW file. The OLD file and the Patch File are input by the end user into the Patch Apply program. The Patch Apply program changes, at the bit level, only the portions of the OLD file required to yield the desired file update. By distributing only the Patch File and Patch Apply program to the end users, the desired file update can be implemented by the end user with maximum operational and economic efficiency. Furthermore, the update is implemented with numerous safety features including (1) automatic verification that the correct files have been used and that the patches have been built and applied correctly, (2) automatic check for sufficient disk space, (3) restart capability after power failure, (4) backup of any files affected by a patch, and (5) the ability to reverse the patched file or an entire system to the prior condition.

Claims

1. A method for converting an OLD computer file into an updated NEW computer file, the method comprising the steps of:

(a) identifying differences between said OLD file and a NEW computer file by passing both files through a patch build program;

(b) creating a patch file based on identified differences, comprising the steps of

(i) selecting a portion of said OLD file;

(ii) processing said portion of OLD file with a string table preparation subroutine thereby creating a string table from said selected portion of OLD file;

(iii) combining said portion of OLD file, said NEW file and said string table by a matchtable preparation subroutine thereby creating a match table having identified matches between said OLD file and said NEW file, wherein a selected number of mismatches are allowed;

(iv) repeating steps (b(i)) through (b(iii)) until all portions of OLD file have been processed; and

(v) combining said OLD file, said NEW file and said match table in a patch file encoding subroutine to create said patch file; and

(c) combining said OLD file and said patch file by passing both files through a patch apply program to obtain said NEW file.

2. The method of claim 1 wherein said patch file is created from said OLD file at a central facility, and patch files are subsequently distributed to a plurality of remote facilities to convert a plurality of the OLD files into plural NEW files and including the additional steps of:

(a) creating an auxiliary table from said patch file with a patch file decoder subroutine; and

(b) combining said auxiliary table, said OLD file and said patch file with a NEW file construction subroutine thereby generating a copy of said NEW file.

3. The method of claim 1 wherein said mach table subroutine comprises the additional steps of:

(a) successively selecting fixed-length substrings from the NEW file;

(b) utilizing the string table to find any matching copies of the selected sub strings in said OLD file portion; and

(c) extending said matching substring copy to a longer match in the forward and reverse directions, wherein a selected number of mismatches are allowed.

4. The method of claim 1 wherein a string table is prepared from the OLD file by the steps:

(a) successively selecting fixed-length substrings from said portion of OLD file whose position relative to beginning of said OLD file portion is a multiple of a fixed increment, said fixed length and fixed increment having no common factors greater than one; and

(b) if said selected substring does not comprise a repeating pattern, recording location of said selected sub strings in said string table.

5. The method of claim 4 wherein substrings which have already been recorded in said string table a fixed number of times are not recorded further in said string table until a subsequent portion of said OLD file is selected.

6. A computer readable program code for converting an OLD computer file into an updated NEW computer file, the program comprising:

(a) a NEW file template program which defines the form of said NEW file;

(b) a patch build program which identifies a difference

(i) identifying a portion of said OLD file to be converted, and

(ii) creating a patch file;

(c) a patch apply program which converts said OLD file into said NEW file by combining said patch file with said portion of the OLD file to be converted to form said NEW file;

(d) a string table memory receiving a string table from said OLD file formed by a string table subroutine;

(e) a match table memory for receiving the result of a match table subroutine which combines said OLD file, said NEW file and said string table to create a match table having identified matching regions between said OLD file and said NEW file, wherein a selected number of mismatches are allowed; and

(f) a patch file encoding subroutine which combines said OLD file, said NEW file and said match table to create said patch file.

7. The computer readable program code of claim 6 further comprising:

(a) a patch file decoder subroutine which creates an auxiliary table from said patch file; and

(b) a NEW file construction subroutine which combines said auxiliary table, said OLD file and said patch file for generating said NEW file.

8. The process of forming smaller patch files using the computer readable program code of claim 6 and comprising:

(a) inputting the OLD file to a string locating subroutine to collect a string table;

(b) inputting the string table into a match subroutine provided with the NEW input file to form a match table;

(c) collecting the matches from the table and non-matching regions from said NEW file to form a list of patches; and

(d) encoding said patches into a patch file for sending to a plurality of remote locations so that the remote locations can use said patch apply program to convert OLD files to NEW files.

9. A method for controlling a general purpose computer, and causing it to compare an OLD binary file and a NEW binary file, to construct a patch file containing the differences between the OLD and NEW binary files, and subsequently controlling a remote different general purpose computer to use said patch file to reconstruct and output said NEW file from said OLD file comprising:

(a) a binary file input sequence enabling the OLD and NEW files to be accessed repeatedly and progressively;

(b) a string table subroutine forming stored data structures comprising a plurality of fixed-length substrings within a selected portion of said OLD file;

(c) applying the string table subroutine to successive portions of said OLD file so that the contents of said string table are constructed based on selected portions of said OLD file so that the LD file is completely input thereto;

(d) a match table for storing data structures describing matches between portions of the NEW file compared to the OLD file, wherein a selected number of mismatches are allowed;

(e) inputting to the match table the said NEW file partitioned into selected length substrings from the OLD file processed through the sting table wherein said substrings are extended to longer matches in either the forward or reverse directions;

(f) cyclically repeating string table preparation and match table preparation wherein repeated, successive portions of said first file are processed;

(g) optimizing the match table lengths of the matches to produce a patch file of smaller patches;

(h) forming a completed patch file for subsequent use;

(i) forming a binary computer file including the patch file from the data structures in the match table encoded into a binary computer file and transmitted to a patch file driven different computer; and

(j) applying said patch file reconstruction to said OLD file with said encoded patch file.

10. The method of claim 9 wherein the step of forming the match table defines a substring match to occur when the ratio of total mismatched characters to total characters is less than a selected ratio, and no adjacent characters having a selected and fixed block size contains more mismatches than a fixed and selected value and said selected ratio and said selected value are input to control forming the matches.

11. The method of claim 9 wherein match table optimization proceeds by moving backwards through said NEW file by fixed increments, and progressively recording estimates of the number of characters required to encode said NEW file from that point forward to an end point, and adjusting the length of the match to minimize said estimate.

12. The method of claim 9 wherein said string table subroutine proceeds by placing into said string table data structures necessary to locate those substrings of said OLD file which have a fixed size and which begin at a location relative to the last selected portion which is a multiple of fixed length, and wherein said fixed length and fixed increment have no common factors greater than one and said increment is chosen from a plurality of choices.

13. The method of claim 9 wherein substrings of said OLD file comprising repeating patterns of a plurality of sizes are not input into said string table by said string table preparation method, and said fixed-length substrings of said NEW file comprising repeating patterns of a plurality of sizes are not processed by said match table preparation method, and repeating substrings are encoded separately into said patch file.

14. The method of claim 9 wherein said patch file encoding method proceeds by forming patch file records of a plurality of types, including:

(a) copy of records, wherein said completed patch file is instructed to append a copy of a region of said OLD file to reconstruction of NEW file, and comprising;

(i) an identifying code;

(ii) a location in said OLD file; and

(iii) a length;

(b) copy with gap records, wherein said completed patch file is instructed to append a gap to said reconstruction of NEW file, records the position and length of said gap, and then append a copy of a region of said OLD file and comprising;

(i) an identifying code;

(ii) a gap size;

(iii) a location in said OLD file; and

(iv) a length;

(c) mismatch modification records, wherein said completed patch file is instructed to set a current modification position to the beginning of said reconstruction of NEW file, and then to modify certain individual characters in said reconstruction of NEW file, and comprising;

(i) an identifying code;

(ii) a modification count;

(iii) a plurality of modification identifiers, comprising;

(1) an increment which is to be added to said current modification position of said reconstruction of NEW file;

(2) a difference which is added to the character at said modification position in said reconstruction of NEW file, and

(d) add records, wherein said completed patch file is instructed to place indicated characters in previously recorded gaps in said reconstruction of NEW file and append any remaining characters to said reconstruction of NEW file, and comprising;

(i) an identifying code,

(ii) a length, and

(iii) characters to be placed is said gaps or appended to said reconstruction of NEW file.

15. The method and apparatus of claim 9, wherein said patch file encoding method proceeds by forming patch file records of plurality of types, including

(a) copy records, wherein said patch application method is instructed to append a copy of a region of said OLD file to said reconstruction of NEW file, and comprising:

(i) an identifying code,

(ii) a location in said OLD file, and

(iii) a length,

(b) copy with gap records, wherein said completed patch file is instructed to append a gap to said reconstruction of NEW file, record the position and length of said gap, and then append a copy of a region of said OLD file to said reconstruction of NEW file, and comprising;

(i) an identifying code,

(ii) a gap size,

(iii) a location in said OLD file, and

(iv) a length,

(c) pattern fill records, wherein said completed patch file is instructed to append to said reconstruction of NEW filled with a repeating pattern, comprising;

(i) an identifying code, which also identifies length of said pattern,

(ii) a pattern, and

(iii) a length,

(d) pattern fill with gap records, wherein said completed patch file is instructed to append a gap to reconstruction of NEW file, record the position and length of said gap and then append to said file a region filled with a repeating pattern, and comprising;

(i) an identifying code, which also identifies length of said pattern,

(ii) a gap size,

(iii) a pattern, and

(e) mismatch modification records, wherein said completed patch file is instructed to set a current modification position to the beginning of said reconstruction of NEW file, and then to modify certain individual characters in said reconstruction of NEW file, and comprising;

(i) an identifying code,

(ii) as modification count,

(iii) a plurality of modification identifiers, comprising;

(1) an increment which is to be added to said current modification position of said reconstruction of NEW file,

(2) a difference which is added to the character at said modification position in said reconstruction of NEW file,

(f) add records, wherein said completed patch file is instructed to place indicated characters in previously recorded gaps in said reconstruction of NEW file and appends any remaining characters to said reconstruction of NEW file, and comprising;

(i) an identifying code,

(ii) a length, and

(iii) characters to be placed in said gaps or appended to said reconstruction of NEW file.

16. The method of claim 9 including the steps of:

(a) forming the string table;

(b) forming the match table;

(c) forming the patch file derived from the string and match table; and

(d) defining different measures of match in a match table subroutine so that the patch file is minimized in size.

17. The method of claim 16 including the steps of progressively building the match table by repeated processing of successive positions if the NEW file, and wherein repeated portions thereof are processed to completion.

18. The method of claim 17 wherein the match table encodes match position, number of matching symbols in sequence, and estimated number of symbols to encode the match.

19. Apparatus for controlling a general purpose computer to compare an OLD bring file and a NEW binary file, to construct a patch file containing the differences between said binary files, and subsequently enabling a general purpose providing with said patch file to construct said NEW file from said OLD file and patch file, comprising:

(a) a file input means enabling the OLD and NEW files to be accessed repeatedly;

(b) string table storage means storing data structures comprising a plurality of fixed-length substrings within a currently selected portion of said OLD file;

(c) a string table preparation circuit selecting successive portions of said OLD file so that the contents of said string table storage means are constructed based on the currently selected portioned of said OLD file;

(d) match table storage means storing data structures describing matches between regions of said OLD file and regions of said NEW file, wherein a selected number of mismatches are allowed;

(e) a match table preparation circuit forming from the said NEW file fixed-length substrings located in said OLD file by structures stored in the string table means, and substrings are extended thereby to longer matches in the forward or reverse directions;

(f) wherein said file input means drives said string table preparation circuit and said match table preparation circuit for repeated, successive portions of said OLD file, until all portions of said file are processed;

(g) a match table optimization circuit controlling the lengths of the matches in the data structures in the match table storage means to produce a minimized patch file; and

(h) patch file output means for patch file encoding so that the data structure in the match table storage means are encoded into a binary computer file and transmitted by said patch file output means.

20. The apparatus of claim 19 wherein said match table preparation circuit defines two substrings to match when the ratio of total characters is less than a selected proportion, and a block of adjacent characters contains fewer mismatches than a fixed value.

21. The apparatus of claim 19 wherein said match table optimization circuit proceeds by moving backwards through said NEW file by increments of a fixed size, and progressively makes and records estimates of the number of characters required to encode said NEW file from that point forward to the end, and adjusts the length of the match used to encode said block to minimize said estimate.

22. The apparatus of claim 19 wherein said string table preparation circuit processes data structures necessary to locate those substrings of said OLD file which have length equal to a fixed size and which begin at a location relative to said currently selected portion which is a multiple of a fixed increment, and wherein said fixed size and fixed increment have no common factors greater than one and said increment is selectable from a plurality of choices.

23. The apparatus of claim 19 wherein substrings of said OLD file comprising repeating patterns are not placed into said string table storage means, and said fixed-length substrings of said NEW file comprising repeating patterns of a plurality of sizes are not processed by said match table preparation circuit, but said repeating substrings are encoded separately into said patch file.

24. The apparatus of claim 19 wherein said patch file encoding proceeds by forming patch file records of a plurality of types, including:

(a) copy records wherein said patch file output means is instructed to append a copy of a region of said OLD file to reconstruction of NEW file, and comprising;

(i) an identifying code,

(ii) a location in said OLD file, and

(iii) a length;

(b) copy with gap records wherein said patch file output means is instructed to append a gap to the reconstruction of NEW file, record the position and length of said gap, and then copy a region of said OLD file, to the reconstruction of said NEW file, and comprising;

(i) an identifying code,

(ii) a gap size,

(iii) a location in said OLD file, and

(iv) a length;

(c) mismatch modification records, wherein said patch file output means is instructed to set a current modification position to the beginning of said reconstruction of NEW file and then to modify certain individual characters in said reconstruction of NEW file, comprising;

(i) an identifying code,

(ii) a modification count,

(iii) a plurality of modification identifiers, comprising;

(1) an increment which is to be added to said current modification position of said reconstruction of NEW file, and

(2) a difference which is added to the character at said modification position in said reconstruction of NEW file;

(d) add records wherein said patch file output means is instructed to place indicated characters in previously recorded gaps in said reconstruction of NEW file and appends any remaining characters to said reconstruction of NEW file, and comprising;

(i) an identifying code,

(ii) size

(iii) characters to be placed in said gaps or appended to said reconstruction of NEW file.

25. A method of processing NEW and OLD files through a patch build program in a computer comprising the steps of:

(a) building a string table from the OLD file processed from the start to the end thereof to compile strings therein;

(b) using strings in the string table to make matches with NEW file wherein the matches are stored in a match table;

(c) for each match in the match table preparing for each match values of I, RL, and S wherein I is match location, L is number of consecutive approximately matching characters in the forward direction, RL is number of consecutive matching characters in the reverse direction, and S is estimated number of characters required to encode the match, wherein a selected number of mismatches are allowed;

(d) progressively changing the values of L to find the longest match.

26. The method of claim 25 wherein the matches in the match table are progressively and dynamically changed by:

(a) adding to L an adjacent chunk of the OLD file;

(b) modifying S dependent on the added chunk;

(c) re-evaluating the value of L after steps (a) and (b) to obtain new values I, L, RI and S; and

(d) optimizing the match table by re-evaluating matches therein so that the entire table is processed by the repeated steps (a) and (b) until there are no remaining adjacent chunks to process.

27. The method claim 26 wherein match table optimization is dependent on chunk size and including the steps of changing chunk size.

28. The method of claim 27 wherein chunk size is increased by doubling the size.

29. A method for controlling a general purpose computer to progressively compare an OLD binary file with a NEW binary file, and construct a patch file containing the differences between the OLD and NEW binary files, and to enable subsequent operation of a remote and different general purpose computer to use said patch file to reconstruct and output said NEW file from said OLD file and comprising the steps of:

(a) forming a string table of stored data structures comprising a plurality of entries therein;

(b) evaluating a selected portion of said OLD file so that the contents of said string table are constructed based on selected portions of said OLD file;

(c) forming a match table for storing data structures describing matches between portions of the NEW file compared to the OLD file and inputting to the match table the stored data structures, wherein a selected number of mismatches are allowed;

(d) cyclically repeating string table and match table formation wherein repeated, successive entries into said tables are optimized in match table lengths to produce a patch file of selected sizes; and

(e) forming a completed patch file for subsequent use from the data structures in the match table encoded into a binary computer file to be transmitted as a patch file for a remote computer to enable patch file reconstruction of said OLD file with said transmitted patch file.

30. The method of claim 29 including the step of forming the string table from the OLD file by processing the OLD file progressively using selected portions of the OLD file, forming the match table by inputting all of the NEW file for match table formation, and progressively extending match table and string table formation wherein initial matches in the match table overlap other matches, and extending the process until match overlap ends.

31. The method of claim 29 including the step of forming the match table initially with a set of stored data structures describing matches, and subsequently refining the matches in an iterative process.

32. The method of claim 29 including the step of forming the match table by serially processing the entire NEW file to completion, and thereafter optimizing the match table to reduce the size of the patch file.

33. The method of claim 29 including the step of forming the patch file as a data stream stored on a memory media.

34. The product made by the method of claim 33.

35. The product made by the remote computer when provided with the patch file of claim 29 and the OLD file and which comprises the NEW file data stream.

36. The method of claim 29 wherein said string table is formed by locating repeated patterns in said OLD file, and forming the match table initially with matches wherein the matches are progressively refined while reducing the patch file size.

37. The method of claim 29 including the repeated step of evaluating the OLD file until the entire OLD file is evaluated, and including the step of evaluating the entire NEW file for matches with the entire OLD file.

38. The method of claim 37 including the step of completing the match table with the NEW file, and optimizing the match table overlapping the step of completing the match table.