Abstract:
Incremental updating of a file ( 100 ) that has been rebased or realigned is accomplished through the use of a canonical form ( 100 B). In terms of rebasing, a canonical form ( 100 B) is one that has been rebased to a predetermined base address ( 104 ). In one embodiment this predetermined base address ( 104 ) is zero. In terms of realigning, a canonical form ( 100 B) is one that has been realigned in a predetermined way. In one embodiment, the segments ( 110 ) of the file ( 100 ) are realigned such that there is no gap ( 114 ) between the end of one segment ( 110 ) and the start of the next segment ( 110 ). In another embodiment, the segments ( 110 ) of the file ( 100 ) are realigned to page boundaries ( 112 ) of a predetermined size. An incremental update ( 124 ) for the file ( 100 ) is determined that transforms the file from the canonical form ( 100 B) to the desired update form ( 100 C). The process of updating the file ( 100 ) comprises transforming the file ( 100 ) to the canonical form ( 100 B) and applying the incremental update ( 124 ) to the canonical form ( 100 B).

Description:
FIELD OF INVENTION 
     This invention pertains to the field of software updating. More specifically, this invention pertains to a system and method for performing an update to an executable file which has undergone rebasing or realigning. 
     BACKGROUND OF THE INVENTION 
     Some computer software publishers update their software applications (computer programs and data files associated with the programs) frequently. These updates often add new features to the applications as well as remove existing bugs. Several methods are commonly used to update software applications. The simplest of these is to distribute one entire software application to replace an older one. This full update method is simple, but expensive and inconvenient. Typically the software is distributed on some type of removable media, such as floppy disks or CD-ROMs, which are costly to produce and distribute. The time an end user must wait for the removable medium to arrive and the time it takes for the software application to install itself on a computer system are inconvenient. This inconvenience is compounded where updates occur frequently. 
     Because of the large size of many software applications it is generally not feasible to distribute such updates over computer networks, such as the Internet. When full updates of larger applications are distributed over the Internet, they often cause such high loads on servers that other users suffer slow-downs on the network, and the servers have trouble meeting the demands. 
     In order to bypass many of the problems associated with this type of software updating, some software publishers distribute incremental updates. These updates do not contain entire software applications, but rather they contain that information which is necessary to transform a particular version of a software application to a newer version. Among the methods available to perform such incremental software updating is binary patching, performed by programs such as RTPatch, published by Pocket Soft, Inc. A binary patcher changes those binary bits of a software application which are different in a newer version. Because many software updates involve changes to only a small portion of a software application, a binary patcher needs, in addition to the old software application, only a small data file which includes the differences between the two versions. The smaller data files distributed for a binary patch update are often less than 1% of the size of a full update, taking advantage of the large amount of redundancy in the two versions. 
     The use of incremental update methods allows for smaller updates which can be distributed by means which are not conducive to the distribution of full updates, such as distribution over the Internet. The smaller incremental updates also make distribution by floppy disk more feasible where a full update would have required many disks, and an incremental update may require only one. 
     Conventional incremental update methods, however, require that application files being updated conform exactly to a known pre-update version. Because binary updating occurs by moving and replacing selected bits of a file, any differences between the file being updated and the expected pre-update file can produce unpredictable results. 
     There are a variety of ways in which files containing executable code modules can be modified in order to operate more effectively on a particular operating system or a particular computer system. Two of these ways are “rebasing” and “realigning.” Rebasing is the changing of information in a file in order to accommodate the file being loaded into memory at a new base address. Typically, rebasing involves changing absolute memory addresses which appear in code and data segments, so that the correct memory addresses appear. Realigning is the moving of code and data segments within a file such that the segments begin on particular numerical boundaries. Rebasing and realigning are explained in more detail below. Both of these forms of file manipulation create files which can be different from the original files installed on the system. When a software publisher wishes to update earlier versions of an application to a new version through incremental updating, the publisher generally assumes that the files being updated match one of a definite number of past versions. Update patches for these known versions can be produced and sent to users. If some of the application files have been rebased, realigned, or both, these application files will not be in a recognizable format for updating with the incremental update. Because the rebased or realigned file will generally not be available to the publisher of the incremental update, conventional incremental update methods are insufficient. 
     What is needed is a system for performing incremental updates to application files which have been rebased, realigned, or both. 
     SUMMARY OF THE INVENTION 
     The present invention is a system, computer implemented method, and computer readable medium for allowing incremental updating of a file ( 100 ) which has been rebased or realigned. A canonical form ( 100 B) is provided. In terms of rebasing, a canonical form ( 100 B) is one which has been rebased to a predetermined base address ( 104 ). In one embodiment this predetermined base address ( 104 ) is zero. In terms of realigning, a canonical form ( 100 B) is one which has been realigned in a predetermined way. In one embodiment, the segments ( 110 ) of the file ( 100 ) are realigned such that there are no unused memory locations ( 114 ) between the end of one segment ( 110 ) and the start of the next segment ( 110 ). In another embodiment, the segments ( 110 ) of the file ( 100 ) are realigned to page boundaries ( 112 ) of a predetermined size. 
     An incremental update ( 124 ) for the file ( 100 ) is determined which transforms the file ( 100 ) from the canonical form ( 100 B) to the desired update form ( 100 C). The process of updating the file ( 100 ) comprises transforming the file ( 100 ) to the canonical form ( 100 B) and applying the incremental update ( 124 ) to the canonical form ( 100 B), resulting in the desire update form ( 100 C). 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     These and other more detailed and specific objects and features of the present invention are more fully disclosed in the following specification, reference being had to the accompanying drawings, in which: 
     FIG. 1 is an illustration of a file  100  which includes executable code. 
     FIG. 2 is an illustration of a file  100  for which the base address  104  has been changed without changing references  102  to absolute memory addresses. 
     FIG. 3 is an illustration of a file  100  which has been rebased. 
     FIG. 4 is an illustration of a file  100  which conforms to the canonical form of the illustrative embodiment. 
     FIG. 5 is an illustration of a file  100  which does not have segments  110  aligned on page boundaries  112 . 
     FIG. 6 is an illustration of a file  100  which has been realigned. 
     FIG. 7 is an illustration of a file  100  which conforms to the canonical form of the illustrative embodiment. 
     FIG. 8 is an illustration of one embodiment of the present invention. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     To overcome the problem of incrementally updating files which have been rebased, realigned, or both, a canonical form is utilized. A canonical form is a predetermined form such that, given a set of files which are each equivalent to the others in the set, the canonical form of any file in the set is identical to the canonical form of any other file in the set. The utility of a canonical form is that non-identical files, if equivalent to each other, are identical when put into a canonical form. A file which is rebased is functionally equivalent to the original file; the executable code in the file operates the in the same manner before and after rebasing. Similarly, a file which has been realigned is functionally equivalent to the original form of the file. A file put into a canonical form will be identical to an equivalent file that has been put into the canonical form, regardless of any rebasing or realigning that had been performed on the files prior to being put into the canonical form. Because a canonical form is designed to eliminate the differences between equivalent files, the definition of any particular canonical form depends on the form of equivalence being preserved. In the illustrative embodiment, equivalences between rebased files and equivalences between realigned files are utilized. Other equivalences will be apparent to those skilled in the art. 
     All updating is performed on files which have been put into a canonical form. In order to explain the attributes of the canonical forms in the illustrative embodiment of the present invention, it is necessary to first describe rebasing and realigning in some detail. 
     Rebasing 
     Referring now to FIG. 1, file  100  (which may be, for example, a standard executable file or a dynamic link library) contains executable code which contains references  102  to absolute memory addresses which are within the memory intended to be occupied by file  100 . These references  102  are premised on the assumption that file  100  will be loaded into memory at a particular predetermined address  104  (the “base”). In the case of file  100  in FIG. 1, base address  104  is 9000h (all addresses in hexadecimal). Sometimes, however, it is not possible to accommodate file  100  by loading it into the intended base address  104 . For example, if one dynamic link library is already loaded at base address  104  and file  100  is being loaded, file  100  cannot be loaded at address  104 . As illustrated in FIG. 2, changing the base address  104 , without modifying absolute memory references  102 , would result in the code failing to function properly. Where data is read from a fixed address, the wrong data will be read. A jump to a fixed address will begin executing the wrong code. Therefore, such file  100  is rebased, if possible, to accommodate being loaded at a different base address  104 . The rebasing can take place in Random Access Memory (RAM) at run-time, or it can be performed once, with the rebased file being saved in place of the original file  100 . 
     As is typical of files which are capable of being rebased, file  100  contains a header block  106  at the beginning of file  100  which indicates which memory references  102  within file  100  need to be modified to account for the change in base address  104 . The rebasing is carried out by reading header block  106  and modifying each such memory reference  102  to reflect the new base address  104 . FIG. 3 illustrates a properly rebased form of file  100  from FIG.  1 . The difference between the old base address  104  and the new base address  104  has been applied to all absolute memory references  102 . Executable files and dynamic link libraries conforming to the Portable Executable (“PE”) format generally can be rebased in this way. The rebasing process takes a period of time which, when performed at run-time, is undesirable. When the rebasing is carried out by an operating system at run-time, the effect is that the execution of the code within file  100  is delayed. 
     The run-time delay associated with rebasing can be avoided by rebasing file  100  such that it loads at a base address  104  which is expected to be vacant, and saving the rebased version of file  100  in place of the original version. When loaded, this new file  100  will generally not need to be rebased again. This kind of rebasing can be carried out on particular files by using a rebasing tool such as the “REBASE.EXE” utility produced by Microsoft Corp. A system optimization program might also be used to rebase all executable files and dynamic link libraries on a computer system in such a way as to minimize the run-time rebasing required. Such functionality might even be built into an operating system, which would rebase files on a local file system to avoid the instances of run-time rebasing. 
     In order to ensure that file  100  is in an expected form before being updated, it is converted to the canonical form. In the illustrative embodiment, a file  100  is in the canonical form when it has been rebased to a predetermined value. This predetermined value can be included with an update, or can be set when file  100  is first published. In FIG. 4, the canonical form is one in which file  100  has been rebased to a base address  104  of zero. In other embodiments, file  100  may be rebased to any predetermined value. Although file  100  in the canonical form might not be the same as the form in which file  100  was originally distributed, this canonical form is useful as a common starting point. 
     Realigning 
     Referring now to FIG. 5, many files  100  containing executable code include multiple code and data segments  110 . In a typical file format, these code and data segments  110  follow header block  106  at the beginning of file  100 . In an operating system which maps file  100  to memory and uses memory pages of fixed size to move portions of file  100  in and out of memory, it is efficient for code and data segments  110  within file  100  to be aligned on memory boundaries  112  equal to the page size. For example, if the operating system uses memory pages of 4 Kb in size, and a 4 Kb code segment  110  (such as second Code Segment  110  in FIG. 5) begins at the 6 Kb address in file  100 , the operating system will need to move two 4 Kb portions (4 Kb to 12 Kb) of file  100  into memory in order to load that code segment  110 . If the code segment  110  were located at the 8 Kb boundary, as in FIG. 6, the segment  110  could be loaded into just one 4 Kb page of memory. By aligning code and data segments  110  in file  100  on page boundaries  112 , loading of files  100  containing executable code can be accomplished more quickly. 
     Many files  100  containing executable code are produced which do not have code and data segments  110  aligned on page boundaries  112  corresponding to a particular operating system. Part of the reason might be that the page size of the operating system on which the application is to run may not be known at the time files  100  are compiled and linked. Some applications are produced in which no attempt is made to align segments  110  on any particular page boundaries  112 . 
     Files  100  which are not aligned for a particular operating system can be realigned for efficient use by that operating system after being installed on the system. The process of moving segments  110  within file  100  containing executable code is similar to the process of rebasing. Information about the location of code and data segments  110  within file  100  is generally contained in header block  106 . As illustrated in FIG. 6, by adding or deleting slack space  114  between segments  110 , segments  110  can be made to coincide with particular page boundaries  112 . After segments  110  are realigned, header block  106  is updated with the new segment addresses, and any necessary changes are made to absolute memory references  102 , so that the code will function properly. This realigned file  100  then replaces the original file  100 , allowing file  100  to be more quickly loaded into memory. 
     As illustrated in FIG. 7, one canonical form of file  100  is one in which all segments  110  have been moved to be contiguous. This would be analogous to realigning file  100  to one byte boundaries  112 . Alternatively, any particular boundaries  112  may be determined at the time an incremental update is being calculated. Segments  110  are aligned on these boundaries  112  in the canonical form. In another embodiment, boundaries  112  are not fixed with respect to file  100 , but rather are fixed with respect to the preceding segment  110 . In such an embodiment, unused memory portions  114  would be specified as being a predetermined size. 
     Incremental Updating 
     Referring now to FIG. 8, software publisher  118  intends to update a first version of an application file  100 A to a new version  100 C. Because users may have files  100  which correspond to version  100 A but which have been rebased or realigned, the publisher uses canonical converter  120  to produce a version  100 B file from a version  100 A file. Version  100 B conforms to the canonical form of version  100 A. Rebasing and realigning techniques such as those described above can be used by canonical converter  120 . An update builder  122  then calculates the binary differences between file  100 B and file  100 C. Update builder  122  can be any conventional binary patch file builder which produces binary update files  124  from two versions of a file  100 . The differences are used to create update file  124 C-B. 
     Update file  124 C-B is then distributed to a user who installs it on computer  126 . Computer  126  also includes canonical converter  120 . The pre-update version of file  100  on computer  126  has been rebased and realigned, such that it is in state  100 D. Canonical converter  120  on computer  126  takes file  100 D and produces canonical version  100 B therefrom. Then update file  124 C-B can be used by updater  128  to produce desired version  100 C of the file. Updater  128  can be any conventional binary patcher which can apply patches  124  produced by update builder  122 . 
     By converting file  100 , which has been rebased, realigned, or both, to a canonical form, problems associated with returning file  100  to the original form are avoided. Because file  100  might not contain information sufficient to determine the original form, a process which operates by returning file  100  to the original form would require that patch  124  include a lot of information relating to the original form. The present invention overcomes such a situation by using an independent canonical form. 
     Transformations other than rebasing and realigning can give rise to equivalence and, therefore, canonical forms. For example, the code and data segments may be rearranged within a file. A canonical form which takes this into account can order the segments based on the numerical order off any distinct tags associated with the segments. Alternatively, the segments can be ordered numerically based on the content of the segments. 
     The above description is included to illustrate the operation of an exemplary embodiment and is not meant to limit the scope of the invention. The scope of the invention is to be limited only by the following claims. From the above description, many variations will be apparent to one skilled in the art that would be encompassed by the spirit and scope of the present invention.