Abstract:
A generator for generating an update package for efficiently updating the software and/or firmware in an electronic device, and a method for operating such a generator are disclosed. An embodiment of the disclosed invention may produce a compact update package comprising a set of instructions that may be executed within the electronic device to produce an updated binary image of the software and/or firmware. Pre-processing of the existing or new binary image may result in a further reduction in the size of the update package, shortening the time needed to transmit the update package to the electronic device.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS/INCORPORATION BY REFERENCE 
     This application makes reference to and claims priority based on the following provisional applications, the complete subject matter of each of which is incorporated herein by reference in its entirety. 
     
       
         
               
               
               
               
               
             
           
               
                   
               
               
                   
                 Ser. No. 
                 Title 
                 Filed 
                 Inventors 
               
               
                   
               
             
             
               
                   
                 60/373,421 
                 Pattern Detection 
                 Apr. 12, 2002 
                 Chen 
               
               
                   
                   
                 Preprocessor in 
                   
                 O&#39;Neill 
               
               
                   
                   
                 an Update 
                   
                 Rao 
               
               
                   
                   
                 Generation System 
                   
                 Lilley 
               
               
                   
                 60/373,422 
                 Update Package 
                 Apr. 12, 2002 
                 O&#39;Neill 
               
               
                   
                   
                 Generation and 
                   
                 Rao 
               
               
                   
                   
                 Distribution 
                   
                   
               
               
                   
                   
                 Network 
                   
                   
               
               
                   
                 60/373,423 
                 Layout 
                 Apr. 12, 2002 
                 Chen 
               
               
                   
                   
                 Preprocessor 
                   
                 O&#39;Neill 
               
               
                   
                   
                 in an Update 
                   
                   
               
               
                   
                   
                 Generation 
                   
                   
               
               
                   
                   
                 System 
                   
                   
               
               
                   
                 60/372,066 
                 Memory 
                 Apr. 12, 2002 
                 Chen 
               
               
                   
                   
                 Initialization 
                   
                 O&#39;Neill 
               
               
                   
                   
                 System for 
                   
                   
               
               
                   
                   
                 Initializing a 
                   
                   
               
               
                   
                   
                 Memory Image 
                   
                   
               
               
                   
                   
                 with a Pattern 
               
               
                   
               
             
          
         
       
     
     This application is a continuation-in-part of U.S. patent application Ser. No. 10/311,462, “System and Method for Updating and Distributing Information”, filed May 13, 2002, which is the National Stage filing of PCT Application Ser. No. PCT/US01/44034, “System and Method for Updating and Distributing Information”, filed Nov. 19, 2001, which claims priority to U.S. Provisional Patent Application Ser. No. 60/249,606, filed Nov. 17, 2000, the complete subject matter of each of which is incorporated herein by reference in its entirety. 
     This application is also related to the following co-pending applications, each of which is hereby incorporated herein by reference in its entirety: 
     
       
         
               
               
               
               
             
           
               
                   
               
               
                 Ser. No. 
                 Title 
                 Filed 
                 Inventors 
               
               
                   
               
             
             
               
                   
                 Update Package 
                 Apr. 11, 2003 
                 O&#39;Neill 
               
               
                   
                 Generation and 
                   
                 Rao 
               
               
                   
                 Distribution 
                   
                   
               
               
                   
                 Network 
                   
                   
               
               
                   
                 Initialization 
                 Apr. 11, 2003 
                 Chen 
               
               
                   
                 and Update of 
                   
                 O&#39;Neill 
               
               
                   
                 Firmware in 
                   
                 Lim 
               
               
                   
                 Electronic 
                   
                 Jacobi 
               
               
                   
                 Devices 
                   
                 Sotos 
               
               
                   
               
             
          
         
       
     
    
    
     FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT 
     [Not Applicable] 
     MICROFICHE/COPYRIGHT REFERENCE 
     [Not Applicable] 
     BACKGROUND OF THE INVENTION 
     When a block of binary code associated with a software application in memory, such as flash memory, RAM memory, ROM memory, etc. has to be updated, as part of a version upgrade or as part of a bug-fix process, there are several issues to be considered. For one, the newer version of the software may differ significantly from an existing version in terms of size, functionality, etc. The newer version of the software may not fit into the space occupied by the existing version. Attempts to replace the existing version with the newer version by actual replacement of specific blocks of code with others may cause the relocation of several other blocks of code not directly related to the segment of code being replaced. Such relocations have several side-effects requiring the modifications of addresses and/or instructions in the relocated code in-order to keep them executable and operational. 
     The size of the update packages that may be sent to an electronic device as part of an update process is often of very important concern. Some electronic devices may be constrained in resources and unable to field the update packages sent to them. Even if they can store update packages sent to them, these electronic devices often lack additional free memory necessary to execute the instructions necessary to complete the update process. 
     It may be possible to reduce the size of an update package containing a new version of software that is sent to electronic devices. One important problem that needs to be solved while trying to reduce the size of an update package that is sent to electronic devices is the determination of code that is the same or similar in both existing and new software modules. Due to relocation of some code segments in the new memory image of the electronic device as compared to the existing memory image, often the same or similar software modules appear significantly different. 
     A related problem in determining how new memory images of software modules are different from existing memory images of the same software modules is the issue of byte alignments of data and operational codes. Two software modules that are essentially the same may occupy different amounts of memory if the layout of data and or code in one of the memory images forces the relocation of addresses due to alignment related issues. 
     Further limitations and disadvantages of conventional and traditional approaches will become apparent to one of skill in the art, through comparison of such systems with some aspects of the present invention as set forth in the remainder of the present application with reference to the drawings. 
     BRIEF SUMMARY OF THE INVENTION 
     Aspects of the present invention may be seen in a generator for producing an update package using a first binary image and a second binary image. The generator may comprise a comparator for determining at least one difference between the first binary image and the second binary image, and an encoder for encoding the at least one difference as at least one of addition to, deletion from, and modification of the first binary image using the second binary image, the encoded at least one difference collectively forming the update package. In an embodiment of the present invention, the encoder may use at least one heuristic. 
     In an embodiment of the present invention, the generator may further comprise a preprocessor for preprocessing before the encoding one of the first binary image and the second binary image, and the preprocessor may have at least a first mode and a second mode of operation. The first mode of operation may comprise modifying the first binary image to more closely match the second binary image, and the second mode of operation may comprise modifying the second binary image to more closely match the first binary image. The mode of operation may be selected using at least one heuristic. 
     Another aspect of the present invention may be observed in a method of operating a generator, the generator producing an update package using a first binary image and a second binary image. In such an embodiment, the method may comprise comparing the first binary image and the second binary image to determine at least one difference, and encoding the at least one difference as at least one of an addition to, a deletion from, and a modification of at least one portion of the first binary image using at least one portion of the second binary image, the encoded at least one difference collectively forming the update package. The encoding may use at least one heuristic. 
     The method may further comprise preprocessing before the encoding one of the first binary image and the second binary image, and the preprocessing may have a mode of operation comprising at least a first mode and a second mode. The first mode of operation may comprise modifying the first binary image to more closely match the second binary image, where the modifying may comprise at least one of relocating at least one portion of the first binary image and replacing at least one of an address or an offset within the first binary image with a predetermined value. The second mode of operation may comprise modifying the second binary image to more closely match the first binary image, where the modifying comprises at least one of relocating at least one portion of the second binary image and replacing at least one of an address or an offset within the second binary image with a predetermined value. In addition, the preprocessing may use at least one heuristic, and may produce a map table representative of the preprocessing performed. 
     A further embodiment of the present invention may include machine-readable storage, having stored thereon a computer program having a plurality of code sections executable by a machine for causing the machine to perform the foregoing. 
     These and other advantages, aspects, and novel features of the present invention, as well as details of illustrated embodiments, thereof, will be more fully understood from the following description and drawings. 
    
    
     
       BRIEF DESCRIPTION OF SEVERAL VIEWS OF THE DRAWINGS 
         FIG. 1  is block diagram of an exemplary update generation system, in accordance with an embodiment of the present invention. 
         FIG. 2A  is a block diagram of an exemplary layout of software modules in an existing memory image of an electronic device such as the electronic device of  FIG. 1  in which the software modules A, B, C, D and F are laid out adjacent to each other. 
         FIG. 2B  is block diagram of another exemplary layout of software modules in a new memory image of an electronic device in which some of the software modules of the memory image from  FIG. 2A  have been relocated to new addresses and have changed in size. 
         FIG. 3  is a flow chart illustrating an exemplary end-to-end update process, in accordance with an embodiment of the present invention. 
         FIG. 4  is a flow chart illustrating the pre-processing steps executed by an exemplary pattern detection pre-processor, in accordance with an embodiment of the present invention. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     Aspects of the present invention relate generally to the update of software in electronic devices, and more specifically, to the efficient generation and subsequent execution of software and/or firmware update activities in electronic devices. 
       FIG. 1  is block diagram of an exemplary update generation system  105 , in accordance with an embodiment of the present invention. The update generation system  105  comprises a generator  107 , an electronic device  111  with an update agent  109 , a pattern detection preprocessor  115 , and an optional update package repository  113 . The generator  107  generates update packages using a memory layout specification  117 . The update agent  109  may apply the update packages onto the electronic device  111  to upgrade any software and/or firmware resident in the electronic device  111 . The pattern detection preprocessor  115  facilitates the generation of efficient and compact update packages by detecting operation code patterns. The generator  107  creates an update package for the electronic device  111  using a map table created by the pattern detection preprocessor  115 . The generator  107  may also store the update package in the optional update package repository  113 , from which it may be subsequently retrieved and processed along with its associated map table by the electronic device  111 . 
     In the illustration of  FIG. 1 , the pattern detection preprocessor  115  facilitates the determination of similarities, and more specifically the occurrence of similar operation code patterns, in software and/or firmware modules in an existing memory image for the electronic device  111  and software and/or firmware modules in a new memory image for the same or similar electronic device  111 . The pattern detection preprocessor  115  generates a map table that may be employed by the generator  107  in creating efficient update packages (smaller in size than would otherwise be the case), and also by the update agent  109  to implement post-update processing. In addition, the map table may be stored in the update package repository  113  and delivered to the electronic device  111  as required to apply a given update package. The map table may be retrieved by the electronic device  111  from update package repository  113  along with an update package for an existing memory image and may be employed by the update agent  109  in a post-update task, after the existing memory image in the electronic device  111  has been updated. The post-update task may involve relocating code segments or software and/or firmware modules to the positions assigned to them in the new memory image using the map table information. 
     The pattern detection preprocessor  115  recognizes the similarities between software and/or firmware segments or modules in an existing memory image for the electronic device  111  and a new memory image for the same or similar electronic device  111 . Similarities between software and/or firmware segments or modules are recognized by the pattern detection preprocessor  115  despite relocation of such code in the new memory image. 
     In one embodiment, the similarities between software and/or firmware segments or modules may be determined based on applying pattern recognition techniques, primarily aimed at recognizing patterns of operation code. In such an embodiment, the existing and new memory images may be scanned for patterns of operation code that appear similar, and the location and length information in the memory images for each of the patterns of operation code that match may be stored for further processing. 
     Recognizing similar patterns of operation code may involve, among other tasks, comparing sequences of operation code in the existing memory image with sequences of operation code in the new image in order to determine if they are similar. The comparison of sequences of operation code may be further facilitated by initially (before comparing) encoding or replacing data and memory addresses with a different pattern that distinguishes them easily from valid operational codes. By doing so, the ability to distinguish valid sequence of operation code from other information is greatly enhanced. The map table created may contain, for example, a reference to each matching code pattern, its address in the existing memory map, its address in the new memory map, and the length of the matching code pattern. 
     The ability to compare sequences of operation code in the existing memory image and recognize similar patterns of operation codes in the new memory image may be further enhanced by adjusting the alignments of code and data sequences before comparing them. Once the code segments that are similar are identified, the new memory image may be made to resemble the existing memory image so as to minimize the size of the update package to be created. 
     In one embodiment, the new memory image may be made to look like the existing memory image so as to minimize the size of an update package. This may involve changing offsets in op codes and addresses in op codes in the new memory image using the map table. This process may involve changing the values of, for example, addresses, offsets, jump instructions, and subroutine branches in the software modules or code segments in the new memory image that are recognized as reproductions of a corresponding one from the existing memory image. After selectively altering the values of offsets, addresses, jump instructions, etc., the same code segment in the new memory image may be made to resemble the version in the existing memory image. Subsequent generation of an update package provides a smaller, simpler and more efficient update package. The update package as well as the map table may be delivered to the electronic device. In this situation, the update agent may first apply the update package and then reverse the values of addresses, offsets, jump instructions, subroutine branches, etc. in the software modules or code segments so as to re-create the new memory image. 
     In another embodiment, the new memory image may be made to look like the existing memory image so as to minimize the size of an update package. This may involve relocating specific code segments in the new memory image to positions occupied by the segment in the existing memory image, selectively altering the offsets and addresses for the op codes in the new memory image using the map table before generating an update package. Once the code segments that are similar have been identified, the relocation of code segments or operation code sequences in the new memory image to locations occupied by them in the existing memory image allows the generation of compact update packages by the generator  107 . 
     Both of the embodiments described above for making the new memory image look like the existing memory may be combined in yet another embodiment. For example, code segments may be relocated and the addresses of op code instructions, offsets, jumps, etc. may also be modified. 
     In an embodiment of the present invention, the generator  107  may create an update package for the electronic device  111  by comparing an existing version of software to a newer version of the same software, computing the differences, and specifying the differences as a combination of data and instructions to be executed. By relocating code that appears similar or the same, and by making the new image more closely resemble the existing image, the size of the update packages may be significantly reduced, i.e. the number of instructions and the size of data involved in such instructions may be reduced. The relocation-related information may be saved in a map table to be used later by the update agent  109  in the electronic device  111  in reversing the process of update package generation. The update agent  109  in the electronic device  111  may apply the update package onto the electronic device  111  by processing the data and/or executing the instructions provided within the update package. At the end of this process, the update agent may execute post-processing instructions employing the map table provided. In order to reduce update package sizes, for example, the update agent  109  may relocate some segments of the code that were initially relocated by the pattern detection preprocessor  115 . The size of a generated update package is thus minimized by the incorporation of the additional pre-processing and associated post-processing steps. 
     The memory layout specification  117  may specify information regarding, for example, the number and size of memory banks in the device, the size of the code and data segments to be employed, and the location of the code segments and data segments. The memory layout specification  117  may also be accessed by the generator  107  to create the update packages. In one embodiment of the present invention, the memory layout specification  117  employed by the generator  107  may be contained within the pattern detection preprocessor  115  and may be employed by the pattern detection preprocessor  115  to analyze the code, data segments, etc. in the memory images, both in the existing memory image and in the new memory image. In another embodiment, the memory layout specification  117  may be retrieved by the pattern detection preprocessor  115  from an external system. 
       FIG. 2A  is a block diagram of an exemplary layout of software modules in an existing memory image  205  of an electronic device such as the electronic device  111  of  FIG. 1  in which the software modules A, B, C, D and F are laid out adjacent to each other. The software modules A  207 , B  209 , C  211  and D  213  may or may not be related to each other. Because they are adjacent to one another without significant free memory between them, they cannot be modified or upgraded without requiring the relocation of addresses and references in another module, especially those that “follow” the changed module. For example, replacing an existing version of software module A  207  with a new version of software module A  207  may require more or less memory space and may involve relocating some or all of modules B  209 , C  211 , and D  213 . Thus, a new version of the memory image with a newer version of the software for module may cause the relocation of all the other software modules B  209 , C  211 , D  213  and E  215  in the new memory image. A relocation of software and/or firmware modules or segments generally necessitates, for example, changing the addresses of software jumps and changing references to addresses, to name just two items. Thus, there may be a sort of “avalanche” effect in which minor changes or upgrades to software module A  207  result in a large number of changes to other modules. 
       FIG. 2B  is block diagram of another exemplary layout of software modules in a new memory image of an electronic device such as electronic device  111  of  FIG. 1 , in which some of the software modules of the existing memory image  205  of  FIG. 2A  have been relocated to new addresses and are also different in size. Specifically, modules A  207 , B  209  and C  211  from existing memory image  205  of  FIG. 2A  are similar to corresponding software modules A  227 , B  229  and C  231  in the new memory image  225 . However, in the new memory image  225 , module D  233  has changed in size from corresponding module D  213  of existing memory image  205 . It has also been relocated to a new location. In addition, a free memory block F  237  is available in the new memory image  225  and software module E  235  has changed in size and location. 
     The pattern detection preprocessor, such as pattern detection preprocessor  115  of  FIG. 1 , may be used to recognize the similarities in software modules D of the existing memory image  205  and the new memory image  225 . After comparing the code segments of the two different memory images, pattern detection processor  115  may create entries in the memory map table that specify the location and size of code segments in the existing memory image  205  corresponding to code segments that are also found in the new memory image  225 . For example, for module D  213 ,  233 , one or more entries may be made for code segments that are found in both the existing and the new memory images. 
     In one embodiment of the present invention, the addresses, offsets, jump instructions, etc. in the code segments of the new memory image  225  may be set to their corresponding values in the existing memory image by the pattern detection preprocessor  115 , using the map table. The map table may be used to record such changes so that they may be reversed by the electronic device  111  in a post-processing phase. 
     In another embodiment in accordance with the present invention, code segments in the new memory image  225  may be relocated to their corresponding location in the existing memory image by the pattern detection preprocessor  115 , using the map table. An update package may then be created by a generator, such as generator  107  of  FIG. 1 . Using this approach, the update package is smaller in size and require fewer instructions than without such a preprocessor facility. 
       FIG. 3  is a flow chart illustrating an exemplary end-to-end update process, in accordance with the present invention. The processing starts (block  307 ), with the execution of the pattern detection preprocessor. Next, the memory layout specification is optionally retrieved (block  309 ). This may be used to pre-process a new memory image by comparing it to an existing memory image. Pre-processing (block  311 ) facilitates the detection of the same or similar code segments in existing and new memory images for an electronic device, such as electronic device  111  of  FIG. 1 . A map table is created that comprises the information used to prepare the new memory image for the generation of a compact update package. Once the map table is created, it is saved. 
     The new memory image is then modified (block  313 ) using the map table, to prepare it for the generation process. Relocation of code segments in the new memory image may be necessary to make the new memory image resemble the existing or reference memory image as closely as possible. An update package is created by the generator (block  315 ) and the update package is saved in a repository along with the associated map table. 
     The update package and its associated map table are retrieved by an update agent in the electronic device, and the instructions in the update package are executed to recreate the modified version of the new memory image (block  317 ). The new memory image is recreated and applied by the update agent in post-processing steps to the existing memory image of the electronic device, by selectively applying relocation instructions to the modified version of the new memory image, using the map table. Upon completion, processing stops (block  319 ). 
       FIG. 4  is a flow chart illustrating the pre-processing steps executed by an exemplary pattern detection pre-processor such as pattern detection preprocessor  115  of  FIG. 1 , in accordance with an embodiment of the present invention. The pre-processing starts (block  407 ) when an existing memory image, a new memory image, and a memory layout specification are accessed. The data and free memory bytes in the new memory image are replaced (block  409 ) by special codes that make it easy to distinguish them from valid operational codes (also called op codes). A search is then conducted (block  411 ) to identify all possible matching op code segments in the existing memory image and the new memory image. All instances of op code segments in the existing memory image that also occur in the new memory image are tracked. All matches within a specified tolerance limit are also tracked. 
     A map table is created (block  413 ) by applying heuristics to the information on op code pattern segments that match. In one embodiment of the present invention, the map table may be used to relocate code segments (block  415 ) in the new memory image to make it resemble the existing memory image (or a reference memory image) as much as possible. The modified new memory image is then ready for the update package generation process. Such relocation reduces the size of update packages that are generated by the generator by comparing the existing and the modified new memory image as part of the generation process. In another embodiment, the new memory image may be made to resemble the existing memory image (or a reference memory image), as much as possible, by altering addresses, offsets, jumps, etc. and tracking such alterations in the map table. 
     Subsequently, the map table is associated with the new memory image and stored. Processing then stops (block  419 ). 
     In another embodiment of the present invention, the existing memory image of the electronic device may be modified to resemble, as closely as possible, the new memory image by means of the pattern detection preprocessor, such as pattern detection preprocessor  115  of  FIG. 1 . In such an embodiment, an update package may be generated that facilitates translating a modified existing memory image into the new memory image. The map table may contain information that facilitates such a conversion. In such an embodiment, a pre-processing step using the map table may convert the existing memory image into a modified memory image that is ready for the application of the update package. In this embodiment, a pre-processor step that employs the map table precedes the application of the update package by the update agent in the electronic device. 
     In general, if the new memory image has deleted some old applications or removed some code, making the existing image look like the new memory image may be more effective. 
     Any of the following seven combinations of adding new code, deletion of existing code, and modification of existing code may be used: 
     a. addition of new code, 
     b. deletion of existing code, 
     c. addition of new as well as deletion of existing code, 
     d. modification of existing code, 
     e. addition of new code, and deletion and modification of existing code, 
     f. addition of new code and modification of existing code, 
     g. deletion of existing code and modification of existing code. 
     The three operations of addition, deletion and modification, may be incorporated in the generation of a new memory image. Heuristics may be used to determine if it is more effective to make the existing memory image resemble the new memory image, or vice versa. 
     The following exemplary heuristics may be employed: 
     For combinations (b) and (g) listed above, where the new image is primarily the result of deletions or a combination of deletions and modifications of some software and/or firmware modules or code segments, the process of making the existing memory image match the new image may be employed. 
     For combinations (a) and (f) listed above, the process of making the new memory image match the existing memory image may be employed. 
     Other heuristics may also be employed. 
     In yet another embodiment, a number of update packages and map tables may be generated using several different heuristics, and one of the update packages selected for use based on a specific criteria such as the size of the update package, the amount of time needed for the execution of the instructions in the update package, etc. 
     Accordingly, the present invention may be realized in hardware, software, or a combination of hardware and software. The present invention may be realized in a centralized fashion in one computer system, or in a distributed fashion where different elements are spread across several interconnected computer systems. Any kind of computer system or other apparatus adapted for carrying out the methods described herein is suited. A typical combination of hardware and software may be a general-purpose computer system with a computer program that, when being loaded and executed, controls the computer system such that it carries out the methods described herein. 
     The present invention also may be embedded in a computer program product, which comprises all the features enabling the implementation of the methods described herein, and which when loaded in a computer system is able to carry out these methods. Computer program in the present context means any expression, in any language, code or notation, of a set of instructions intended to cause a system having an information processing capability to perform a particular function either directly or after either or both of the following: a) conversion to another language, code or notation; b) reproduction in a different material form. 
     Notwithstanding, the invention and its inventive arrangements disclosed herein may be embodied in other forms without departing from the spirit or essential attributes thereof. Accordingly, reference should be made to the following claims, rather than to the foregoing specification, as indicating the scope of the invention. In this regard, the description above is intended by way of example only and is not intended to limit the present invention in any way, except as set forth in the following claims. 
     While the present invention has been described with reference to certain embodiments, it will be understood by those skilled in the art that various changes may be made and equivalents may be substituted without departing from the scope of the present invention. In addition, many modifications may be made to adapt a particular situation or material to the teachings of the present invention without departing from its scope. Therefore, it is intended that the present invention not be limited to the particular embodiment disclosed, but that the present invention will include all embodiments falling within the scope of the appended claims.