REGISTER  |  SIGN IN
United States Patent6832373
O'NeillDecember 14, 2004
Title
System and method for updating and distributing information
Abstract
The present invention discloses efficient devices, systems, and methods for updating digital information sequences that are comprised by software (110a), devices (104c), and data (110c). In addition, these digital information sequences may be stored and used in various forms, including but not limited to files, memory locations, and/or embedded storage locations. The disclosed invention is thus suitable for updating many types of digital information sequences and in the context of updating software comprised of multiple files. Furthermore, the devices, systems, and methods described herein provide a developer skilled in the art with an improved ability to generate update information as needed and, additionally, allow users to proceed through a simplified update path, which is not error-prone, and may be performed more quickly than through the use of existing technologies.
Inventors:O'Neill; Patrick J. (Dana Point, CA)
Assignee:Bitfone Corporation (Laguna Nigel, CA)
Appl. No.:404601
Filed:April 1, 2003
Current U.S. Class:717/171 714/25 714/807 
Field of Search:717/171,170 714/25,807
U.S. Patent Documents
20010029178October 2001Criss et al.
20010047363November 2001Peng
20010048728December 2001Peng
20020078209June 2002Peng
20020116261August 2002Moskowitz et al.
20020131404September 2002Mehta et al.
20020152005October 2002Bagnordi
20020156863October 2002Peng
20020157090October 2002Anton, Jr.
20030033599February 2003Rajaram et al.
20030037075February 2003Hannigan et al.
20030061384March 2003Nakatani
5084816January 1992Boese et al.
5261055November 1993Moran et al.
5442771August 1995Filepp et al.
5479637December 1995Lisimaque et al.
5579522November 1996Christeson et al.
5596738January 1997Pope
5598534January 1997Haas
5608910March 1997Shimakura
5623604April 1997Russell et al.
5666293September 1997Metz et al.
5752039May 1998Tanimura
5778440July 1998Yiu et al.
5790974August 1998Tognazzini
5878256March 1999Bealkowski et al.
5960445September 1999Tamori et al.
5968182October 1999Chen et al.
6009497December 1999Wells et al.
6038636March 2000Brown, III et al.
6064814May 2000Capriles et al.
6073206June 2000Piwonka et al.
6073214June 2000Fawcett
6088759July 2000Hasbun et al.
6105063August 2000Hayes, Jr.
6112024August 2000Almond et al.
6112197August 2000Chatterjee et al.
6126327October 2000Bi et al.
6128695October 2000Estakhri et al.
6138249October 2000Nolet
6157559December 2000Yoo
6163274December 2000Lindgren
6198946March 2001Shin et al.
6279153August 2001Bi et al.
6311322October 2001Ikeda et al.
6438585August 2002Mousseau et al.
6668336December 2003Lasser
6725392April 2004Frey et al.
Foreign Patent Documents
2001-0100328Nov., 2001KR
2002-0034228May., 2000KR
2339923Mar., 2000CA
8202626Aug., 1996JP
Other References
Computer Dictionary Micrsoft Press Third Edition, pp. 88, 190, 1997.
Primary Examiner: Ingberg; Todd
Attorney, Agent or Firm:McAndrews, Held & Malloy, Ltd.
Parent Case Text


CROSS-REFERENCE TO RELATED APPLICATIONS/INCORPORATION BY REFERENCE

This application is a Continuation Application of PCT application number PCT/US01/44034, filed Nov. 19, 2001, which designates the United States, and which in turn claims priority to U.S. Provisional Application Ser. No. 60/249,606, filed Nov. 17, 2000. This application is also a Continuation Application of U.S. patent application Ser. No. 10/311,462, "SYSTEM AND METHOD FOR UPDATING AND DISTRIBUTING INFORMATION," filed on Dec. 13, 2002, which is a national phase filing based on a PCT application number PCT/US01/44034, filed Nov. 19, 2001, which in turn claims priority to U.S. Provisional Application Serial No. 601249,606 filed Nov. 17, 2000. Each of these applications are incorporated herein by reference in their entirety.
Claims

What is claimed is:
1. A method of operating an electronic device having a non-volatile memory containing a first code version, the method comprising: updating at least one portion of the non-volatile memory to a second code version using an update package received via a public network, the update package comprising a set of instructions for converting the first code version to the second code version.

2. The method of claim 1 wherein the public network is a wireless network.

3. The method of claim 1 wherein the public network is the internet.

4. The method of claim 1 wherein the updating is fault tolerant.

5. The method of claim 1 further comprising: sending to an update server at least one identifying characteristic; and receiving from the update server the update package corresponding to the at least one identifying characteristic.

6. The method of claim 5 wherein the at least one identifying characteristic comprises an identifier of the manufacturer of the electronic device.

7. The method of claim 5 wherein the at least one identifying characteristic comprises a model identifier.

8. The method of claim 5 wherein the at least one identifying characteristic comprises at least one version identifier.

9. The method of claim 8 wherein the at least one version identifier comprises a first and a second code version identifier.

10. The method of claim 5 wherein the at least one identifying characteristic comprises a type of the electronic device.

11. The method of claim 1 wherein the updating comprises: retrieving from the update server a metadata; halting the updating if it is determined from the metadata that the updating should not proceed; and continuing the updating if it is determined from the metadata that the updating should proceed.

12. The method of claim 1 wherein the updating comprises; verifying the received update package; proceeding with the updating if the verification of the update package is success; and halting the updating if the verification of the update package is not successful.

13. The method of claim 12 wherein the verifying comprises: determining that the update package is appropriate for at least one identifying characteristic.

14. The method of claim 13 wherein at least one of a cyclic redundancy check, hash value, digital signature, digital fingerprint, and message digest is used.

15. The method of claim 1 wherein the non-volatile memory comprises a change indicator that is set upon receipt of the update package.

16. The method of claim 15, wherein the updating comprises: detecting whether or not the change indicator is set; proceeding with the updating if the change indicator is set; inhibiting the updating if the change indicator is not set; and resetting the change indicator.

17. The method of claim 15 wherein the change indicator is a status table.

18. A method of operating an electronic client device, the electronic client device having a memory, the method comprising: receiving, by the electronic client device via a communications medium, executable instructions; and performing, using the executable instructions, a fault-tolerant update of code in at least a portion of the electronic client device.

19. The method of claim 18 wherein the code is software.

20. The method of claim 18 wherein the code is firmware.

21. The method of claim 18 wherein the communications medium is a wireless network.

22. The method of claim 18 wherein the communications medium is the Internet.

23. A method of operating an electronic client device having a non-volatile memory, the non-volatile memory comprising a change indicator for signaling the availability of an update package received via a communication medium, the method comprising: detecting a state of the change indicator Indicating the availability of the received update package; performing a fault tolerant update of non-volatile memory if the change indicator is set; refraining from performing a fault tolerant update of non-volatile memory if the change indicator is not set; and resetting the change indicator upon completion of the fault tolerant update.

24. The method of claim 23 wherein the detecting occurs during the period after operating power is supplied to the electronic client device and until the electronic client device is operating for its intended use by a user.

25. The method of claim 23 wherein the detecting occurs immediately after the electronic client device is reset.

26. The method of claim 23 wherein the detecting occurs immediately following interruption of the fault tolerant update.

27. The method of claim 23 wherein the change indicator is a status table.

28. A method of operating an update server, the update server communicatively coupled to an electronic client device containing a code, the update server having stored upon it at least one update package, the method comprising: receiving at least one identifying characteristic from the electronic client device; selecting one of the at least one updated package based on at least one identifying characteristic, the selected update package comprising a set of instructions for converting the code into an updated code; and communicating to the electronic client device the selected pudate package comprising a set of instructions for converting the code into an updated code.

29. The method of claim 28 wherein the at least one identifying characteristic comprises an identifier of the manufacturer of the electronic client device.

30. The method of claim 28 wherein the at least one identifying characteristic comprises a model identifier.

31. The method of claim 28 wherein the at least one identifying characteristic comprises a model identifier.

32. The method of claim 28 wherein the at least one version identifier comprises a first and a second firmware version identifier.

33. The method of claim 28 wherein the at least one identifying characteristic comprises a type of the electronic client device.

34. The method of claim 28 wherein the electronic client device is a wireless mobile device.

35. The method of claim 28 wherein the code is software.

36. The method of claim 28 wherein the code is firmware.

37. The method of claim 28 further comprising: determining that an update of the electronic client device is required; sending an update notice to the electronic client device; receiving an update request from the electronic client device; and retrieving an update package.

38. The method of claim 28 wherein the update server comprises a generator for generating the at least one update package.

39. A method of operating a generator, the generator having access to an old code and a new code, the method comprising: generating an update package comprising a sequence of instructions transforming the old code into the new code using a bank by bank method.

40. The method of claim 39, wherein the transforming comprises generating, from the old code, at least one version of modified old code, that is processed along with the update package to generate the now code.

41. A method of operating an electronic device having a non-volatile memory, the non-volatile memory comprising a plurality of banks, the method comprising: (a) selecting one of the plurality of banks; (b) determining whether or not the selected bank has been updated; (c) updating the selected bank if it is determined that it has not been updated; (d) refraining from updating the selected bank if it is determined that it has been updated; (e) repeating (a) through (d) until it is determined that all of the plurality of banks have been updated; and wherein the determining compares a first value to a second value, the second value being calculated from a contents of the selected bank.

42. The method of claim 41 wherein: the non-volatile memory comprises an update package and a backup bank; the backup bank is used for storing information needed for fault tolerant recovery; the electronic device comprises a volatile memory; and the volatile memory comprises a working bank for converting the contents of each of the plurality of banks from a portion of a code to a portion of an updated code.

43. The method of claim 42 wherein: the update package comprises information used in the bank-by-bank update method.

44. The method of claim 42 wherein the updating comprises: moving a copy of the selected bank to the working bank; converting a code in the working bank according to at least a portion of the update package; copying the working bank to the backup bank; and duplicating the working bank in the selected bank.

45. The method of claim 41 wherein the calculation of the second value uses a checksum algorithm.

46. The method of claim 41 wherein the calculation of the second value uses a cyclic redundancy check algorithm.

47. The method of claim 41 wherein the calculation of the second value uses a digital signature algorithm.

48. The method of claim 41 wherein the calculation of the second value uses a message digest algorithm.

49. The method of claim 41 wherein the calculation of the second value uses a hash algorithm.

50. A method of operating an electronic client device, the electronic client device having a non-volatile memory, the method comprising: receiving, by the electronic client device via a communications medium, executable instructions; and updating the non-volatile memory using a fault tolerant bank-by-bank update method.

51. The method of claim 50 wherein the communications medium is a wireless network.

52. The method of claim 50 wherein the communications medium is the Internet.

53. A method of operating an update distribution system for delivering to an electronic device an update package, the electronic device having at least one identifying characteristic, the method comprising: provisioning the update package using the at least one identifying characteristic, the update package comprising a set of instructions for converting a first code version to a second code version; retrieving using at least one retrieval criterion the update package comprising the set of instructions for converting a first code version to a second code version; and providing to the electronic device the retrieved update package comprising the set of instructions for converting a first code version to a second code version.

54. A method of operating an electronic device, the method capable of determining where an interrupted fault-tolerant activity should be resumed without requiring the saving of status information in non-volatile memory during execution of the fault-tolerant activity.

55. The method of claim 54 wherein the electronic device determines where an interrupted fault-tolerant activity should be resumed by sequentially computing a signature in a bank-by-bank fashion for a plurality of banks associated with a code corresponding to the fault-tolerant activity and comparing the computed signatures to a list of pre-computed signatures until a mismatch is encountered thereby determining where the interrupted fault-tolerant activity should be resumed.
Description
FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT

[Not Applicable]

MICROFICHE/COPYRIGHT REFERENCE

[Not Applicable]

FIELD OF THE INVENTION

The present invention generally relates to information updating systems, and more particularly, to a software system and method for updating information which reduces the size of an update and distributes the update in a platform independent manner.

DESCRIPTION OF THE RELATED ART

With the rapid and continuous advancement of software and hardware technology, maintenance of existing devices and software components presents an ever-increasing challenge. Routine installation of information updates and patches has become a recognized necessity to insure that computers, devices, and software applications are kept fully functional over their operational lifetimes. Unfortunately, for many devices and applications, update management can be a cumbersome, time consuming, and error prone process. These problems are often exacerbated in portable electronic devices such as cellular phones and personal digital assistants due to memory constraints and bandwidth restrictions. Furthermore, portable electronic devices often lack the ability to perform automated update operations in a convenient and reliable manner. As a result, there is an ongoing need for improved update processes that can be used in conjunction with both hardware and software systems. Furthermore, there is a need for an update methodology that reduces the size of the update package to help alleviate potential problems that arise due to memory constraints and bandwidth limitations.

Increased sophistication of updateable electronic devices and software often necessitates frequent maintenance where updates are made available and desirably applied on weekly or monthly basis. During the update process, problems often arise when the update is improperly performed or interrupted and may result in data corruption, loss of program functionality, or hardware failure. This presents developers and consumers alike with significant obstacles to insure that available updates are installed in a timely and effective manner. Additionally, developers must dedicate a substantial amount of time and resources to insure their users are provided with necessary updates, patches, and new versions of existing software and/or hardware components.

Some of the concerns which the developer must address include the substantial amount of resources required to store and provide updates to a large customer base, technical support issues related to helping customers properly apply the updates, and the methods by which the updates are distributed to the customers in a timely and efficient manner. A further problem exists where a high degree of requisite of skill is needed to acquire and install an available update and may involve technical skills beyond that of the average customer. Even if a customer is able to retrieve the update, he is faced with the problem of insuring its proper installation. Improper installation of an update package may result in software failure or render the device to which the update is applied inoperative and place a further burden on the developer in resolving customer-related update problems. With increased dependence on electronic devices having updateable components, there is a need for faster and more intuitive updating capabilities and smaller update file sizes to insure that updates can be readily retrieved and properly installed as necessary or desired. In many instances, the ease, reliability, and availability of an update package can significantly affect customer number and loyalty and is a distinguishing characteristic for a successful developer or merchant.

Although the importance of a superior updating system is apparent, conventional updating solutions typically suffer from a number of drawbacks. These problems are particularly prevalent in portable electronics devices and arise from a number of factors related to creation, distribution, and installation of the update package. For example, electronic devices such as cellular phones are often limited with respect to the available memory or storage space available for update processing. The size of the update package must be kept to a minimum in order to accommodate the reduced availability of resources on these devices and, as a result, the ability to perform significant alterations or modifications of the embedded code in these devices may be limited. Furthermore, conventional update methods for portable electronic devices which are directed towards complete operating system replacement or maintenance require the device to be physically connected by a wired connection to a dedicated apparatus which applies the update. Updating in this manner requires specialized hardware and necessitates the device to be updated to be returned to the manufacturer or a suitable service location. This is inconvenient for the user and may not be practical when the number of devices to be updated is large.

In devices that support wireless acquisition and installation of update packages, problems are frequently encountered due to bandwidth limitations needed to distribute available update packages. Furthermore, acquisition of the update package by wireless methods may take long periods of time and be subject to interruption or data corruption. Even when the update package has been acquired, the installation of the update often requires significant technical expertise at the user end complicating the proper installation of the update package. During this time the user may be faced with problems associated with uninstalling a previous version of the code to be updated or applying the update in manner that will be successful. This can present a further problem as it discourages the user from performing update operations for long periods of time or in some cases altogether.

A further problem exists with update management systems that rely on publicly accessible servers to provide updates to large number of users. These servers often become busy or crowded and reduce the efficiency by which the update can be acquired. Additional complexities resulting from update requirements arise from shortened product version lifecycles. It is not uncommon for new software releases to be available every few months (or even weeks, in the case of `bug fixes` and intra-version updates). This places increased demands on developer resources required to maintain the update services and results in developers expending added resources for existing software maintenance potentially shifting their focus from developing new product capabilities to supporting and updating older versions. From a business perspective software updating is generally recognized as a non-revenue producing activity and may consume an inordinate percentage of developer resources. Therefore there is an ongoing need to reduce the time, resources, and personnel needed to service existing software while at the same time insuring the customers are presented with the most up-to-date software versions. Attempts to make updates faster and more intuitive have led to the development of internally-designed and supported update solutions. A number of problems are associated with these solutions which are typically expensive, proprietary, and platform-specific. Other methods for update creation use commercial software packages designed to create updates or to generate patches for software. Both of these methods have inherent problems with flexibility and file size. Commercially available software updaters can be expensive and typically create updates which have unnecessarily large file sizes. In some instances, the new version or update generated by the updater is actually a fill version of the software rather than an actual patch. Because of the problems associated with large update file sizes, developers may be hesitant to release frequent patches and as a result, pursue longer software development cycles. This may be a disservice to the customer due to the limited number of updates, which may be released only when there are substantial enough changes and/or improvements to warrant the creation and disbursement of large update files.

From the foregoing, it can be appreciated that there is an ongoing need for a convenient and reliable update management system. To this end, there is a need for a system which generates and distributes updates that are of reduced size to allow for more rapid acquisition. Additionally there is a need for an automated process that provides a convenient trouble-free method for installing desired updates to both hardware and software systems alike.

SUMMARY OF THE INVENTION

The present invention satisfies aforementioned needs for efficient updating of digital information sequences that comprise software, devices, and data. Further, these digital information sequences may be stored and used in various forms, including but not limited to files, memory locations, or embedded storage locations. The system and methods described herein provide a developer with an improved ability to create update information as needed and additionally allow users to proceed through a simplified update path which is not error-prone and can be performed more quickly than through the use of existing technologies.

In one embodiment the invention comprises a system for updating a plurality of distributed electronic devices with an updated operating code comprising a first plurality of digital information sequences wherein each of the plurality of electronic devices include a resident operating code comprising a second plurality of digital information sequences that are stored within the electronic device. The system further comprises an update generator that compares an image of the first plurality of digital information sequences comprising the updated operating code to an image of the second plurality of digital information sequences comprising the resident operating code and identifies differences between of the updated operating code and the resident operating code and thereafter generates an update package comprising an instruction set which specifies how to generate the updated operating code utilizing at least a portion of the second plurality of digital information sequences of the resident operating code. The system further comprises a distribution system that distributes the update package to the electronic devices such that the update package is received by the electronic devices and stored therein. The system further comprises a plurality of client modules that are respectively resident on each of the plurality of electronic devices, wherein the plurality of client modules access the distribution system and receive the update package and wherein the instruction set of the update package is executed by the client modules so as to generate the updated operating code by utilizing a least a portion of the second plurality of digital information sequences from the resident operating code.

In another aspect the invention comprises a system for updating an electronic device containing a first plurality of data sequences comprising a first code version to a second code version comprising a second plurality of data sequences using a update package comprising a plurality of transformation instructions which transform the first code version into the second code version. The system further comprises an update generator that performs a version comparison between the first code version and the second code version to identify pattern differences between the first plurality of data sequences and the second plurality of data sequences, wherein the identified pattern differences are encoded using the transformation instructions which identify portions of the first plurality of data sequences that can be used in the construction of the identified pattern differences, and thereafter forming the update package using the transformation instructions. The system further comprises a distribution system that receives the update package from the update generator and distributes the update package to the electronic device. The system further comprises an update agent resident on the electronic device that executes the transformation instructions of the update package thereby transforming the first code version resident in the electronic device into the updated second code version.

In yet another aspect the invention comprises a system for updating a plurality of distributed electronic devices with an updated operating code that comprises a plurality of data blocks wherein each of the plurality of distributed electronic devices include a resident operating code that is stored as plurality of data blocks. The system further comprises an update generator that compares the plurality of data blocks of the resident operating code with the plurality of data blocks of the updated operating code and thereby generates an update package comprising an instruction set which indicates how to generate the updated operating code utilizing at least in part the plurality of data blocks of the resident operating code. The system further comprises a distribution system that includes the update package and is accessible by each of the plurality of distributed electronic devices. The system further comprises a plurality of client modules that are respectively resident on each of the plurality of distributed electronic set, wherein the plurality of client modules accesses the distribution system so as to be able to receive the update package, wherein the instruction set provides instructions to the client modules such that the client modules generates at least a portion of the plurality of data blocks comprising the updating operating code by utilizing the plurality of data blocks comprising the resident operating code.

In still another aspect the invention comprises a system for updating a plurality of distributed electronic devices with an updated operating code that comprises a plurality of data blocks wherein each of the plurality of distributed electronic devices include a resident operating code that is stored as plurality of data blocks. The system further comprises an update generator that compares the plurality of data blocks of the resident operating code with the plurality of data blocks of the updated operating code and thereby identifies update data blocks that are different between the update operating code and the resident operating code wherein the update generator generates an update package comprising an instruction set which indicates how to transform the resident operating code into the updated operating code and how to generate the update data blocks utilizing at least in part the plurality of data blocks of the resident operating code. The system further comprises a distribution system that includes the update package and is accessible by each of the plurality of distributed electronic devices. The system further comprises a plurality of client modules that are respectively resident on each of the plurality of distributed electronic set, wherein the plurality of client modules accesses the distribution system so as to be able to receive the update package, wherein the instruction set provides instructions to the client modules such that the client modules modifies the resident operating code into the updated operating code and wherein the client modules generates at least a portion of the update data blocks by utilizing the received instruction set to perform operations on the data blocks of the resident operating code to generate the update data blocks.

In a further embodiment the invention comprises a method of updating a resident operating code stored in a first storage section of an electronic device into an updated operating code. The method further comprises the step of developing an update package comprising a plurality of transformation operations to transform the resident operating code into the updated operating code. The method further comprises the step of transferring the update package to the electrical device. The method further comprises the step of copying a portion of the resident operating code into a second storage section. The method further comprises the step of updating the portion of the resident operating code stored in the second storage section using the transformation operations of the update package to transform the resident operating code into updated operating code. The method further comprises the step of replacing the portion of resident operating code stored in the first storage section with the portion of updated operating code stored in the second storage section. The method further comprises the step of repeating steps of copying, updating, and replacing noted above until the resident operating code has been fully updated to the updated operating code.

In a still further embodiment the invention comprises an updatable electronic device comprising a non-volatile storage section having operating code stored therein, a volatile storage section that is adapted to receive an update package comprising a plurality of instructions via a communications medium, and a controller that implements the instructions of the update package to update the operating code stored in the nonvolatile storage section. In this embodiment the controller is configured to sequentially (i) retrieve original portions of operating code from the non-volatile storage section into the volatile storage section and (ii) apply the instructions of the update package to the retrieved portions in the volatile storage section to thereby transform the retrieved original operating code portion into an updated operating code portion and then (iii) replace the original operating code portion with the updated operating code portion.

BRIEF DESCRIPTION OF THE DRAWINGS

These and other aspects, advantages, and novel features of the invention will become apparent upon reading the following detailed description and upon reference to the accompanying drawings. In the drawings, similar elements have similar reference numerals.

FIG. 1A is a block diagram illustrating one embodiment of an update management and distribution system.

FIG. 1B is a block diagram illustrating another embodiment of an update management and distribution system including an update server array.

FIG. 1C is a block diagram illustrating another embodiment of an update management and distribution system including an update server array having an update store and an update device server.

FIG. 1D is a block diagram illustrating another embodiment of an update distribution system including an update server array having an update store and a plurality of update device servers.

FIG. 2A is a flowchart illustrating one embodiment of an update installation process.

FIG. 2B is a flowchart illustrating another embodiment of an update installation process.

FIG. 3 is a flowchart illustrating one embodiment of an update creation process.

FIG. 4 illustrates one embodiment of a hash array.

FIG. 5 is a flowchart illustrating one embodiment of an instruction set generation process.

FIG. 6A illustrates one embodiment of a run length encoding instruction.

FIG. 6B illustrates one embodiment of an existing sequence instruction.

FIG. 6C illustrates one embodiment of a hash instruction.

FIG. 6D illustrates one embodiment of a default instruction.

FIG. 7 illustrates one embodiment of a reconstructed digital information sequence.

FIG. 8A illustrates one embodiment of an exemplary memory or storage architecture.

FIG. 8B illustrates one embodiment of a non-volatile memory or storage area.

FIG. 9 is a flowchart illustrating one embodiment of a bank-by-bank update method.

FIG. 10 illustrates one embodiment of the application of an update package using the bank-by-bank update process.

FIG. 11 is a flowchart illustrating one embodiment of a fault tolerance process.

FIG. 12 is a flowchart illustrating one embodiment of a signature creation and authentication process.

FIG. 13 shows a block diagram illustrating an exemplary method of determining the next bank to be updated that may correspond to the actions of state 1312 of FIG. 11, in accordance with an embodiment of the present invention.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

Reference will now be made to the drawings wherein like numerals refer to like parts throughout. FIG. 1A illustrates one embodiment of an update distribution system 100. The update distribution system 100 includes an update generator 102 and a client device 104. In one embodiment, the update generator 102 receives a first code version 106, such as an old version of a software application, and a second code version 108, such as a new version of a software application. The update generator 102
produces an update package 110 comprising an instruction set which represents a plurality of operations that are desirably used to transform the first original code version 106 into the second updated code version. The update package 110 is then transferred to a client device 104 via a communications medium 112. Viable choices for communications media 112 may include hardwired media, removable storage media, wireless media, volatile and non-volatile memory based media, and the Internet. Other communications media 112 may include by way of example, local area networks (LANs), wide area networks (WANs), public Internets, private Internets, a private computer network, a secure Internet, a private network, a public network, a value-added network, interactive television networks, wireless data transmission networks, two-way cable networks, interactive kiosk networks, and the like. In addition, the client device 104 may comprise numerous types of devices capable of receiving and processing the update package 10, such as computers, personal digital assistants (PDAs), hardwired phones, mobile phones, pagers, electronic peripheral devices, appliances, and other such devices capable of being configured to receive the update package.

In one aspect, the instruction set utilizes a conversion process employed by the client device 104 to efficiently convert the existing first code version 106 to the second code version 108. The instruction set and the implementation of the conversion process will be discussed in greater detail herein below.

At least one method by which the client device 104 may securely and reliably obtain the update package 110 from the update generator 102 may occur by transfer of information in the form of the update package 110 through at least one of the above-mentioned communications media types. The client device 104 may further be equipped with the capability to bi-directionally communicate with the update generator 102. In one embodiment, the client device 104 transfers identity information 113, including type, model, and/or make of the device, as well as the version of operational software or applications currently in use by the client device 104. The update generator 102 receives the identity information 113 from the client device 104 and subsequently generates the desired update package 110 required and/or requested by the client device 104. Alternatively, the update generator 102 may be equipped with the ability to generate and provide a plurality of update packages 10, which reference a plurality of operational software versions or applications, prior to receiving the identity information 113. In this embodiment, the update generator 102 may retrieve from memory or storage an archived version of the desired update package 110a. In addition, the update generator 102 may create a version manifest, which comprises a list of archived update packages 110 including operational software version information for a wide range of particular client devices 104. Once the update package 110 is generated, validated, and deemed available, the update generator 102 may function as a server and transfer the desired update package 110 to the client device 104 as requested or required. It will be appreciated that one or more update packages 110 may be generated and archived as updated versions of operational software become available. Furthermore, update packages 110 can be prepared for use with hardware update systems, such as may be required, for example, to update non-volatile memory components or portable electronic devices. One desirable feature of the update management system is that it may be readily adapted for use in wireless update procedures or over the air (OTA) updating. This method allows updates for software or firmware components in devices without hardware changes. The updating methods described herein can further be used to update a client device including applications, operational functionality, operating system software and the like. Furthermore, the updating operations can correct errors or problems with existing code resident in the device, add new features or functionality, change or modify resident applications, or perform other desired update operations in a manner that will be described in greater detail herein below.

In one embodiment, the update generator 102 comprises a single computing device or server component which is responsible for both generating and distributing update packages 110. The update generator 102 is equipped to run specialized software to construct the instruction set of the update package 110 for the client device 104. Moreover, the update generator 102 creates the update package 110 by comparing the first code version 106 to the second code version 108. The update package 110
desirably includes mathematical operations and instructions coded into the instruction set which transform the first code version 106 into the second code version 108. A principle feature of the update management system is that update packages 110 are generated in such a way so as to utilize existing code or information resident on the device. The methods for update package generation are specifically designed to analyze the differences between the code versions 106,108 and make use of existing information sequences in the device when possible to transform the first code version 106 into the second code version 108. This feature is significant in that it significantly reduces the size of the update package compared to conventional methods. In one aspect, the file size of the update package 1107 may be reduced by more than 90 percent with respect to the first code version 106. Advantageously, since the file size of the update package 110 is relatively small and compact, the update package 110
may be easily transferred and stored in a memory component of the client device 104 without significantly altering the memory allocation size and bandwidth specifications of the client device 104. In one aspect the update generator 102 generates and archives a plurality of update packages 110 for distribution to one or more different types of client devices 104. Each client device 104 may then request transfer of the desired update package 110 which is selectively sent by the server.

FIG. 1B illustrates another embodiment of an update distribution system 120. The update distribution system 120 is similar in scope and functionality to the update distribution system 100 of FIG. 1A except that the update distribution system 120
is illustrated with separate computing components including an update server array 122. The update distribution system 120 includes the update generator 102, the update server array 122, and a plurality of client devices 104a, 104b, 104c. In this particular embodiment, the update generator 102 is shown to generate the plurality of update packages 111a, 110b, 110c and transfer the plurality of update packages 110a, 110b, 110c to the update server array 122. Additionally, the update server array
122 subsequently transfers the plurality of update packages 110a, 110b, 110c to the plurality of client devices 104a, 104b, 104c via communication media 112a, 112b, 112c, where the communication media 112a, 112b, 112c may correspond, for example, to the communication media 112 of FIG. 1A.

In one aspect, the update server array 122 comprises one or more computing devices, which may be configured to store and archive the plurality of update packages 111a, 110b, 110c transferred from the update generator 100. Storage components include, but are not limited to, hard drives, magnetic tape drives, random access memory (RAM), read only memory (ROM), and removable RAM and/or ROM-based storage media including compact discs, floppy disks, magnetic tape. Additionally, the update server array 122 may be equipped with the capability to independently and bi-directionally communicate with the plurality of client devices 104a, 104b, 104c, wherein the update server array 122 receives identity information 113a, 113b. 113c, including, type, model, and, make of the device, and version of operational software or firmware currently in use on client devices 104a, 104b, 104c. In addition, the client devices 104a, 104b, 104c may request update packages 110a, 110b, as needed or desired.

In one aspect, the update server array 122 receives the identity information 113a, 113b, 113c from individual client devices 104a, 104b, 104c along with a request for transfer of a specified update package 110a, 110b, 110c. The update server array 122 subsequently locates the requested archived update packages and transfers the requested update package to the client device. The update server array 122 may further automatically transfer the update package 110 to the client device 104 without a request from the client device 104.

Advantageously, the update server array 122 may coordinate the transfer of a plurality of update packages 110a, 1110b, 110c to the plurality of client devices 104a, 104b, 104c through at least one of the various above-mentioned communication media types for the purpose of increased flexibility and efficiency of update distribution. After receiving the identity information 113a, 113b, 113c from at least one of the plurality of client devices 104a, 104b, 104c, the update server array 122
retrieves from memory or storage archive the required version of the update packages 110a, 110b, 110c and subsequently transfers the desired update package 110a, 110b, 110c to the particular client device 104a, 104b, 104c. In one embodiment, the update server array 122 may automatically transfer the update packages 111a, 110b, 110c to the client devices 104a, 104b, 104c without a request from the client devices 104a, 104b, 104c.

In another aspect, the update package 110 may be sent from the update generator 100 to the update server array 122 through at least one of the above-mentioned communications media 112, which promotes increased availability of the update packages
110 a, 110b, 110c to the one or more client devices 104a, 104b, 104c. In one embodiment, the update server array 122 is a multi-platform computing device capable of conveniently storing a plurality of update packages 110a, 110b, 110c for the various client-based devices 104a, 104b, 104c and independently establishes communication with each client device 104a, 104b, 104c. The update server array 122 may recognize the one or more client devices 104a, 104b, 104c to determine the required and/or desired update packages 110a, 110b, 110c needed by the one or more client devices 104a, 104b, 104c. For example, the update package 110 may be sent to-the client device 104 and further processed by the client device 104 using software components capable of decoding the update package 110 and altering the operational software components designed and designated to be updated and/or converted. Aspects of the client side update process will be discussed in greater detail herein below. Although illustrated as separate computing components in FIG. 1B, it will be appreciated that the update server array 122 and update generator 102 may comprise a singular entity with the necessary scope and functionality to serve as both the update server array 122 and the update generator 102.

Alternatively, the update server array 122 may create a server manifest comprising a list of archived update packages 110a, 110b, 110c including operational software version information, which pertain to a wide range of particular client devices
104a, 104b, 104c depending on the identity, make, and model of the client devices 104a, 104b, 104c. Upon recognition of one or more client devices 104a, 104b, 104c, the update server array 122 may transfer the server manifest to the one or more client devices 104a, 104b, 104c. The one or more client devices 104a, 104b, 104c then review the manifest and submit a request for the update package 110a, 110b, 110c to be transferred from the update server array 122 to the one or more client devices 104a,
104b, 104c making the request.

In another embodiment, the update computing architecture of the update server array 122 includes an additional component referred to as a collector, which collects information and updates for other devices capable of being updated using at least one of the update packages 110a, 110b, 110c generated by the update generator 102. In this particular embodiment, the collector may communicate with both the update server array 122 and the one or more client devices 104a, 104b, 104c to determine which client devices 104a, 104b, 104c require updating and if any updates are available. The collector may additionally acquire the necessary updates and, at that time or at a later time, distribute them to the client devices 104a, 104b, 104c. In this manner, the large numbers of client devices 104a, 104b, 104c may be subsequently updated in such a way to distribute the bandwidth requirements over the update server array 122. Additionally, the update packages 110 may be scheduled for delivery at various times to stagger the distribution load so that the servers are not overrun by simultaneous update requests from large numbers of client devices.

In one aspect, this method of distributing updates comprises caching the information on one or more servers to scale down network traffic. Using this method, the `latest` update files can be stored on the servers and the update packages can be downloaded from the device servers directly by client/server communications without the need for additional communication between the server and the update store 133 or the update generator 102.

FIG. 1C illustrates still another embodiment of an update distribution system 130. The update distribution system 130 includes the update generator 102, the plurality of client devices 104a, 104b, 104c, and a component version of the update server array 132 that was previously illustrated in FIG. 1B. As in FIGS. 1A and 1B, the update server array 132 and client devices 104a, 104b, 104c may communicate via communication media 112a, 112b. 112c, respectively. The communication media 1112a,
112b, 112c may correspond, for example, to communication media 112 of FIG. 1A. The component version of the update server array 132 further comprises an update store 133, having a management component 134, and at least one update device server 136. In one aspect, the update store 133 archives a plurality of update packages transferred from the update generator 102.

In many circumstances, operational software systems require periodic updates from older versions to newer versions. In addition, multiple updated versions of operational software may be required throughout the life of a client device for reasons of adapting to advances in computing technology. To satisfy these requirements, the update generator 102 generates update packages as newer versions of operational system software become available and then transfers the plurality of update packages to the update store 133 for storage and archiving in a memory or storage component.

In an exemplary application, the update management system may be used in conjunction with over the air updating of portable electronic devices, such as cellular or mobile phones. Mobile communications technology is a rapidly changing field which strives to meet the rising demands and expectations of its users. Mobile phones are also micro-computing devices utilizing integrated operational system software. The operating software, throughout the life of the mobile phone, may require periodic software updates for increased adaptability to changes in wireless communications technology. Updating in the mobile communications industry is complicated by the presence of many different manufacturing entities with each having their own operational software systems and user functionality being integrated into various makes and models of mobile phones. In this circumstance, the update generator 102 is capable of meeting the adaptive demands of industry by generating a proper update package 110a,
110b, 110c relative to the newer versions of operational software onboard the client devices 104a, 104b, 104c, which pertain to the particular manufacturer's make and model of the mobile communications device.

Client-side Update Determination

In one aspect, the client device 104 establishes a communication link with the update store 133 and transfers identity information 113 including, type, model, and make of the device, and code version currently being used by the client device 104. The update store 133 responds by transferring the server manifest, to the client. As previously described the server manifest contains version information describing available update packages. Furthermore, the server manifest may describe the update package characteristics such as file size so that the client can determine if enough space is available in the client storage area to receive and unpack the update package. After comparing the available code versions described in the server manifest to the onboard code version found in the client device 104, further a request for the appropriate update package 110 may be submitted by the client device 104. Upon receive the request the update store 133 references and searches for the desired update package 110, which corresponds to the correct instruction set for proper conversion of the older code version to the requested newer code version. In one more aspect, the update store 133 receives the request submission, and the update management component 134 processes the request submission, and locates the desired update package 110 on the update store 133 or the update device servers 136. Once the particular update package 110 has been located, the update management component 134 references the desired update package 110 and directs the update device server 136 to establish a communication link with the client device 104 to transfer the desired update package 110 to the client device 104.

Server-Side Update Determination

In another embodiment, the client device 104 establishes a communication link with the update device server 136 and transfers identity information 113 including, type, model, and/or make of the device, as well as version of operational system software currently being used by the client device 104. The update device server 136a analyzes the identity information and checks the server manifest or queries the update store 133 for the presence of the update package 110. After comparing the available versions of operational software on the server manifest or update store 133 to the onboard version of operational software transferred by the client device 104, the update store 133 directs the transfer of the update package 110 to the client device 104.

In one aspect, the update package 110 is transferred from the update store 133 to the update device server (s) 136 for distribution to client devices 104 as requested. In this case, the update device server (s) 136 acts as gateways which transfer the update packages 110 to clients as requested by the update store 133. Use of the update device server (s) 136 desirably improves load balancing and reduces bandwidth limitations imposed by having many client devices 104 connected to the same update package provider.

In one aspect, if the particular update package 110 that is requested or determined to be required by the client device 104 is not available in the update store 133, then the update management component 134 may transfer a request to the update generator 102 to generate the particular update package 110. Once the update package 100 is generated, the update generator 102 transfers the update package 110 to the update store 133 for storage and request servicing. After saving the update package
110 in the memory or storage area of the update store 133, the update management component 134 may transfer the desired update package 110 to the update device server 136. Subsequently, the update device server 136 may establish communication with the client device 104b and transfer the requested update package to the client device 104.

FIG. 1D illustrates yet another embodiment of an update distribution system 140. The update distribution system 140 includes the update generator 102, a plurality of client devices 104a, 104b, 104c, 104d, 104e, 104f, 104g, 104h, 104i, and another embodiment of a component version of the update server array 142 that is similar in scope and functionality of the update server array 132 as illustrated in FIG. 1C. The update server array 142 includes the update store 133, comprising the update management component 134, and a plurality of update device servers 136a, 136b, 136c. The plurality of update device servers 136a, 136b, 136c are capable of establishing a communication link with the client devices 104a-104i via communication media 112a-112i, respectively, and may bi-directionally communicate with the client devices 104a-141i to send or receive version or manifest information. As in FIGS. 1B and 1C, the communication media 112a-112i may correspond, for example, to communication media 112 of FIG. 1A. This particular embodiment illustrates that the update management component 134 of the update store 133 may communicate and coordinate the activities of a plurality of update device servers 136a, 136b, 136c and direct the transfer of a plurality of archived update packages to the plurality of update device servers 136a, 136b, 136c. Advantageously, this particular embodiment illustrates the flexibility, effectiveness, and efficiency of the update distribution systems
100,120,130,140 to distribute a large quantity of update packages 104 over one or more hardwired or wireless communications mediums, such as the Internet or wireless local area networks (WLAN). This embodiment of the update distribution system 140 can desirably service the update requirements for a plurality of different client services. Furthermore, the update distribution system 140 can utilize a plurality of different communications means to exchange information and update packages with the client devices.

FIG. 2A illustrates an overview of an update query, retrieval and installation process or update installation process 200 that details the communication between the client devices and the update distribution system 140. The update installation process 200 commences in a start state 202 and subsequently proceeds to a state 204, where the client device 104 establishes a communication link with the update device server 136. The update installation process 200 then proceeds to a state 206 where the client device 104 polls the update device server 136 for the server manifest. In one embodiment, the server manifest may be transferred from the update store 133 to the update device server 136, or the update device server 136 may retain the sever manifest in an onboard memory or storage component for ease of reference. In one aspect, the polled server manifest comprises information used to determine the latest available version of the software, file system, or hardware to be updated. Additionally the server manifest may contain information that describes the size of the update package and other variables used to determine whether an available update is different from the existing file, software component, or firmware present in the client device 104. The polled server manifest may further include an update signature which identifies characteristics of the new code version.

Once the server manifest is transferred to and obtained by the client device 104, the update installation process advances to a state 208 where the client device 104 compares the update signature in the server manifest with that of the existing operational software present on the client device 104. A comparison process may be used by the client device 104 to determine, in a state 210, if the update package 104 should be downloaded from the update device server 136 and installed on the client device 104. After the comparison is completed, the update installation process 200 advances to the state 210. If the client device 104 determines that an update version of the operational software is not desired, needed, or required in the state 210, the update installation process 200 terminates in an end state 218 and may remain inactive until the next scheduled or user-prompted activation.

Alternatively, if the client device 104 determines that an update version of the operational software is desired in a state 210, then the client device 104 requests the update package 110 from the update device server 136 in a state 212. In the state 212, the update device server 136 transfers the request for the update package 110 to the update store 133, where the update management component 134 searches the update store 133 for an available version of the desired update package 110. Furthermore, if the archived version of the desired update package 110 is determined to exist and is available, then the desired update package 110 is retrieved from the archival memory or storage area of the update store 133 and transferred to the update device server 136 if necessary. Thereafter, the update device server 136 transfers the desired update package 110 to the client device 104. In a state 214, the client device 104 receives the update package 110, and the update installation process advances to a state 216 where the client device 104 subsequently installs the update package 110. Aspects of the installation operation will be discussed in greater detail herein below.

In another embodiment, when in the state 214, if the update management component 134 determines that the archived version of the desired update package 110 does not exist or is unavailable, then the update management component 134 sends a request for the desired update package 110 to be generated by the update generator 102. At this point in the update installation process 200, the client device may wait for the desired update package 110 to become available. While the client device 104 waits, the update generator 102 produces the desired update package 110 and transfers the update package 110 to the update store 133. When the update package 110 is available, the client device 104 receives the desired update package 110 for the subsequent installation in the state 216. The installation operation 216 will be discussed in greater detail herein below.

In one aspect, after retrieving and installing the desired update package 110 the update installation process 200 terminates in the end state 218. After updating to the desired version of the file or software component and performing other functions according to developer specifications, the client device 104 may proceed to check for additional updates that may be desirably applied to other file or operational software components. Thus, the update installation process 200 may be repeated periodically as needed or desired for additional update queries. In one exemplary update sequence, if the software component has been successfully updated from version 1 to version 2, the update installation process 200 will check for the availability of an additional version (i. e. version 3) from the update store 133 and proceed to retrieve and install these incremental updates until the file of software component has been updated to the most current version available.

Alternatively, in another embodiment, the update installation process 200 may recognize the presence of multiple available updates (versions) and proceed to update the file or component using the most current version available without sequentially applying each possible update package (i.e. version 1 updated directly to version 3). Following completion of the update cycle for a particular file or software component, the update installation process 200 may determine if other files or software components require updating. Further updates may be processed as before, beginning with the comparison of the update signature state 208 until all files have been updated, and wherein the client device 104 may terminate its operation in the end state 216 and remain inactive until the next activation of the update installation process 200. The client device 104 may be configured to query and retrieve updates automatically, or alternatively the update process may be a user initiated function.

It will be appreciated that the above-mentioned update installation process 200 may be simultaneously and/or separately applied to one or more client devices through one or more update device servers without departing from the scope of the present invention. Furthermore, the above-mentioned update installation process 200 may be applied to any of the above-disclosed embodiments of the update distribution systems 120,130,140 using a similar sequence of steps as described in connection with FIG. 2A or 2B.

In one aspect, if the update component 102 is scheduled to operate automatically, then the update component 102 may remain active in the background until the next scheduled operation or alternatively be activated at the time that the update installation process 200 is desirably initiated. The activities comprising the update installation process 200 may further be visible or transparent to the user, according to the developer's preference. Additionally, following the process of polling the server manifest in the state 206 and identifying a difference between the existing version of the file and the latest version available on the update device server 132 in the state 208, the client devices 104 may notify the user that an update is available and wait for permission to retrieve the update or alternatively, the client device may be configured to automatically retrieve the desired update package (either with or without notifying the user).

FIG. 2B illustrates another embodiment of an update installation process 250 that may be used in connection with the aforementioned update distribution systems described in FIGS. 1A and 1D. The update installation process 250 commences in a start state 252 and subsequently proceeds to a state 254, where the client device 104 establishes a communication link with the update device server 136. Subsequently, the update installation process 250 proceeds to a state 256 where the update device sever 136 requests an update information query from the client device 104. The update information query includes identity information 113, such as type, model, and make of the device, and version of operational software currently being used by the client device 104. In one embodiment, the identity information 113 may be automatically transferred from the client device 104 to the update device server 136 upon establishing the communication link. Additionally, the update information query may also include the update signature which identifies the characteristics of a particular file or update component in the new code version.

When the update information query is transferred to and obtained by the client device 104, the client device 104 responds by transferring the requested update information in the query to the client device 104. The update installation process 250
then advances to a state 258 where the client device 104 receives and processes the update information query by comparing the update signature of the new code version of the with that of the existing code version currently in use by the client device
104. A comparison process may be used by the client device 104 to determine, in the state 258, if the update package 104 should be transferred from the update store 133 and installed on the client device 104. After the comparison is completed, the update installation process 250 advances to a state 260 where the update client device 104 determines the availability of the update package 110 from the update information response. If a newer code version is not available in the update store 133, then the update installation process 250 terminates in an end state 280, and the update installation process 250 may remain inactive until the next scheduled or user-prompted activation.

Alternatively, in the state 260, if the client device 104 determines from the update information response that the updated code version is available in the update store 133, then the client device 104 may further determine, in a state 262, from the update information query whether or not the client device 104 has enough memory available to store the update package 110. If the client device 104 determines that enough memory or storage space is available in the client device 104 for the update package 110, then the update device server 136 processes the client update request in a state 264. The update device server 136 then transfers the update package 110 to the client device 104 in a state 266. After receipt of the update package 110, the update installation process advances to a state 268 where the client device 104 installs the update package 110. The update installation process 250 is then terminated in an end state 280 until another update request is made. Additionally, details of the update package installation procedure will discussed in connection with FIG. 10 herein below.

Alternatively, in the state 262, if the client device 104 determines that there is not enough memory or storage space available or allocated in the client device 104 to accommodate the update package 110, then the client device 104 submits a request, in a state 270 to perform an allocation procedure where additional memory or storage space is freed up to accommodate the download transfer of the update package 110. In one embodiment, to allocate space for the download transfer of the update package 104, the client device 104 may write current files stored in a first data area (i.e. RAM) to a second data area (i.e. onboard flash memory). Alternatively, the client device 104 may compress the files stored in the first data area to make more space available for the update package. To further allocate memory, the client device 104 may transfer files to the update device server 136 for temporary storage until the update package 110 is installed. It will be appreciated that a combination of the aforementioned memory allocation schemes may be used to create sufficient room to receive the update package 110. Additionally, other memory allocation schemes may be used without departing from the scope of the present invention.

When the client device 104 completes the space allocation in the state 270, the update installation process 250 advances to a state 272, where, if enough space is made available on the client device 104 for the download transfer, then the update installation process proceeds to the state 264 for the subsequent update request 264, update transfer and reception 266, and update installation 268. Otherwise, the update installation process proceeds to terminate in the end state 280, due to the determination by the update device server 136 that there is not enough space allocated on the client device 104 to accommodate the download transfer of the update package 110. In one embodiment, the update device server 136 may send the update package
110 to the client device 104 in subsections to accommodate the space limitations of the client device 104. The subsections are applied sequentially to complete the update process using a limited amount of available space on the client device 104.

In one embodiment, the installation procedure performs authentication and validation of the integrity of the update package 110 by the client device 104. Thereafter, the update package is saved to non-volatile memory or storage on the client device 104 and the client device 104 is rebooted if necessary. Subsequently, the update package 110 is then decompressed and the instruction set is executed to initiate the installation of the update. It should be appreciated that the above-mentioned installation procedure may be altered or rearranged without departing from the scope of the present invention.

In one embodiment, update packages 110 are made available to the update server array 122,132,142 and subsequently to the requesting client devices 104 through the use of an update generator 102 and associated processes. FIG. 3 illustrates an update creation process 300 used to form the update package 110. The update creation process 300 uses configuration parameters associated with the update generator 102 and information present in the existing code version, which is desirably updated to a newer code version. The update creation process 300 commences in a start state 302 and advances to a state 304, wherein an existing file, comprising the current code version is opened. The current code version comprises a file or image that is a representation of the information contained in the electronic device to be updated. In one aspect the current code version reflects the binary code or encoded information stored in the device which is identified and stored in the form of an image file. For example, in the case of a mobile phone, the current code version may reflect the contents of the memory or storage area to be updated. The contents of the memory or storage area may further comprise the operating system code, application code, firmware contents, or other instruction sets used by the electronic device to convey functionality.

One significant feature of the update management system and methods is that the update process operates in a code-independent manner. Updates are generated using images or simulated representations of the memory or storage area to be updated. Update operations need not operate at the instructional level but rather can operate at a high level (i.e. a file level) or at a lower level (where information comprising the instructions is represented in binary, hexadecimal, or other similar forms). The update process therefore recognizes the current code version based on a digital information sequence comprising a designated word sequence or pattern. In one aspect, the size or length of the work may be flexibly defined as a bit, byte, instruction, file, or other informational sequence which is subsequently compared to the desired code version represented by a second word sequence and differences between the two sequences are identified. Thus the update process is not necessarily limited to a particular convention such as determining which instructions need to be replaced to obtain the desired code version, but rather, what word sequences should be changed to transform the existing code version into the desired code version.

Upon opening the image of the current code version the update generator 102 subsequently compiles a collection of digital information sequences from the image for use in a state 306. In generating the update package 110, the collection of digital information sequences may be used to generate an image representing the desired second code version 108.

Details of how this collection of digital information sequences is used in instruction set generation and subsequent modification of the existing code version into the new code version will be described in greater detail with reference to FIGS. 5
and 6.

In the state 306, the update generator 102 pre-processes the existing image by searching for digital information sequences that will be used to build a hash table. The hash table includes a plurality of hash values that comprise addresses of particular digital sequences in the first code version that are stored in a data structure for subsequent lookup and retrieval. The hash values correspond to digital information sequences in the existing image, which may be used to build the newer code version. In one aspect, the hash array is formed from the existing code version and identifies strings of digital information sequences in the existing code version. Further details of the hash array will be discussed in connection with FIG. 4 below.

After building the hash array 330 from the existing code version in the state 306, the update creation process 300 proceeds to a state 308 where a new file is opened that will be used to store the instructions used to transform the first code version into the second code version. The new file eventually become the update package 110 which is made available to the servers for transfer to the clients when updating is requested or desired. The update creation process 300 then advances to a state 310 where the update package 110 is generated. As will subsequently be described in greater detail, the instruction set is formed using a plurality of sequence identification and transformation functions that identify operations, instructions, parameters, or digital information sequences which, when executed in an appropriate manner, will transform the existing code version into the updated code version in an efficient manner. During this state 310, the informational composition and sequence of the existing code version is assessed and instructions are identified to transform the existing code version into the new code version.

Following the completion of the code version analysis and instruction set generation in the state 310, the update creation process 300 proceeds to a state 312 where the generated instruction set may be encoded to provide a degree of security that prevents unauthorized access to the contents of the update instruction set. Additionally, the instruction set may be further compressed by utilizing various compression schemes, such as LZW compression, to reduce the overall size of the resulting update package 110. The compressed/encoded instruction set is then stored as the update package 110 in state 314 and may include stored header information, which is used to validate the contents of the update package 110, identify the version of the update, and/or similar functions. The update package 110 may further be transferred to the plurality of update device servers 136a, 136b, 136c in a state 314, where the update package 110 is published and made accessible to the plurality of client devices
104a-104i for downloading. After saving/publishing the update package 110, the update generation process 300 terminates in an end state 316.

FIG. 4 illustrates one embodiment of a hash array 330 discussed in connection with FIG. 3 above. The hash array 330 comprises a plurality of hash values 340-343 that are used to store and reference one or more addresses 350-356, which correspond to the position of a plurality of digital information sequences or words 360-366. In one aspect, the digital information sequences or words comprise words having known lengths or sizes. Each word 360-366 may further comprise one or more bits, bytes, or other recognizable quantum of information. The word length used in the update process need not necessarily be fixed and may instead be flexibly assigned as determined by the update management system or the manner in which information is stored in the electronic device.

In one aspect, the length of the words 360-366 for which hash values 340-343 are calculated is selected to be of a length recognized by the architecture of the electronic device. These hash values 340-343 are stored in the hash array 330 and used by the update generator to determine if a desired word required in the updated code version can be obtained from the current code image. In one aspect, the length of the words 360-366 used in creating the hash value 340-343 is selected to have a discrete word length comprising one or more bits, bytes, or other commonly used quantum of information. It will be appreciated however, that other word lengths can readily be used in generating the hash value 340-343.

By using a known word length for the determination of the hash value 340-343 the update generator can create a summary or database of words that can be found in the existing code version which may be copied and utilized in forming the new code version. Additional details of the implementation of the hash table and its use in generating the update package 110 will be described in greater detail in FIGS. 6A-6H herein below. In one aspect, the hash values of the hash array 330 are used to reference the words comprising the words by referring to the starting address for a particular sequence that is identified as desirably containing a string of information that can be used in construction of the new code version.

The addresses 350-356 are saved into the data structure of the hash array 330 as the calculated hash values 340343 which are referenced by the update generator 102 to form instructions that reference existing code section used during the update process. In one aspect, when developing the hash array 330, the update generator 102 assigns hash values for particular words that comprise distinct or desirable digital sequence characteristics, such as a unique sequences, frequently encountered sequences, and/or a difficult to reconstruct sequences. In one embodiment, the primary function of the hash array 330 is to efficiently locate `identical` word between a target sequence (e.g. a sequence required in the updated code version) and a source sequence (e.g. a sequence presently located in the existing code version). The hash array 330 is further used to determine the start address for the `identical ` word in the existing code version so that this word can be `recycled` or `reused` in the updated code version. Thus, words that are identified to already exist in the code need not be included in the update package but rather one or more instructions may instead be used to retrieve and/or copy the existing word information into new locations in the updated code. This feature substantially reduces the required size of the update package 110 as the instructions used are typically smaller than the corresponding sequence for which they identify. It will be appreciated that each hash value 240-343 may be accessed numerous times to generate the same word in one or more locations and can be used as needed to efficiently generate required words.

One desirable feature of the hash array 330 is that it serves as a "dictionary" of available digital information sequences or words present in the existing code version. The update generator uses these code sequences or words to produce the new code version by rearranging and copying this information. By "reusing" code in this manner, the update package is desirably reduced in size as instructions for code copying and rearrangement are typically significantly smaller in size compared to the literal code sequence or word. Thus, a single instruction may be able to produce code equivalent to many bits or bytes of information.

In the hash array 330 shown in FIG. 4, the address "a" corresponds to the address where a word 360 corresponding to the bit sequence "1100010" can be found in the previous code version. The code generator may specify an instruction that desirably accesses this index 340 in the hash array 330 and furthermore may specify a length of information that is to be copied from the word at this location. For example, bit sequences which may be obtained from the word at address "a" include "1","11","110","1100","11101","110101", and so forth. Similarly, the word at address "b" may be used to generate bit sequences including"1","10","101", "1010","1000","101000","1010001","10100011", and so.

By identifying words or sequences in the existing code version that can be used in the new code version the amount of information which must be contained in the update package 110 is desirably minimized. As previously noted, the sequence corresponding to each word which is addressed by way of example may instead represent other quantum of information including one or more bits, bytes, files or other recognized sizes and lengths of information. It will therefore be appreciated that these other configurations of information can be addressed in a similar manner (i.e., bit-wise addressing, byte-wise addressing, file-wise addressing, etc.)

In another aspect, one or more words, which may comprise bit or byte sequences, can be formed by linking information located at various addresses. For example, the hash value 342 corresponds to the linked address "d", "k", and "s" with each address associated with a particular work 362-364. In a manner similar to that described above, variable portions of each word from each address may be concatenated together to generate still further combinations of word patterns. In one aspect, the addresses for a particular hash value are associated using a linked list data structure. The association of addresses can be used to concatenate information located in close logical proximity as shown for the hash value 342 and may further associate disparately arranged information as shown by the hash value 343. This hash value 343 comprises the addresses "h" and "w" for the words 365,366 respectively which may be located in different sections of the memory or storage area that are desirably associated to form digital information sequences resulting from the combination of information located at these addresses. The hash value 343 may also be formed in a manner such that sequential row or bank numbers of the memory or storage area are arranged to create the desired sequence of information. For example a first bank number may correspond to a first address in the hash value 343, a second bank number may correspond to a second bank address, and so forth. It will be appreciated that the concatenation of address information may be applied in many different combinations using a plurality of addresses to generate large numbers of possible informational sequences that can be used to form the new code version. Additional details of the memory or storage bank arrangement, the formation and configuration of the instruction set using hash values 340-343, and the resultant generation of desirable digital information sequences using existing code will be described in greater detail herein below.

FIG. 5 illustrates one embodiment of an instruction set generation process 400, which is used by the update generator 102 to generate the instruction set used to convert the first code version into the second code version. In one aspect, this process 400 functionally describes the manner in which the instructions are selected for use in the update package 10. This process 400 further identifies a plurality of instructions that perform the code conversion or version update in an efficient manner. In one aspect, the instruction set generation sequence 400 assesses numerous combinations of instructions that may be used to perform the code conversion and desirably identifies instructional combinations that reduce the amount of information that must be included in the update package 110. This in turn reduces the size of the update package 110 and reduces the transmission time needed to send the update package 110. By using existing code sequences when possible, in combination with specialized instructions that may be applied to the code, the previous code version is desirably transformed into the new code version in a manner that further reduces the amount of information that must be included in the update package 110.

The instruction set generation sequence 400 commences in a start state 402 and then advances to a state 404 where the update generator 102 initializes a pointer corresponding to the beginning of the existing file or code version. The pointer maintains a reference position that may used by the sequence analysis functions to determine when the digital information sequence analysis is complete. In one aspect, the digital information sequence analysis comprises a plurality of comparison functions each used to analyze a corresponding instruction type. These instructions may include an existing sequence instruction, a run length instruction, a hash instruction, and a default instruction. It will be appreciated that the aforementioned instructions and corresponding comparison functions are but several of many possible instructions that may be used in the instruction set generation sequence and other instructions may be devised and used in conjunction with the update management system and methods.

At state 406, the comparison functions are applied against the code corresponding to location where the pointer indicates and a determination is made as to how much new code can be generated using each of the instructions related to the comparison functions. In one aspect, the comparison functions use the instructions to provide a separate method for representing particular code fragments. In some instances, one instruction will provide better performance than another instruction depending on the code composition. For example, based on a given code sequence present within the existing code version at the location of the pointer, the existing sequence may be able to translate 3 words of information, the run length function 5
words of information and the hash sequence function 8 words of information. At state 408, the process identifies which of the comparison function exhibits the best characteristics relative to the other comparison functions. Typically, the best result is identified as the comparison function that generates the largest code sequence using a single instruction or group of instructions. In the case of the example above, the hash sequence function exhibits the longest word representation (8 words) and would be preferentially selected over the other comparison functions which translate less code relative to the hash sequence function. Of course, for other code sequences, one of the other comparison functions may be more desirable and have the ability to translate a larger code section relative to the other comparison functions.

Upon selecting the "best result" from the comparison functions at state 408, the process 400 proceeds to a state 410 where a determination is made as to whether or not the identified comparison produces an efficient result. In one aspect, efficiency is measured as a function of the amount of code that can be represented by a single instruction. A threshold of efficiency is used to insure that the identified "best result" is at least as efficient or more efficient than a default instruction function comprising incorporating the literal string directly into the update package 110. If the identified best result function is more efficient than the default instruction then the instruction coding for the information sequence coded by the comparison function is incorporated into the update package 110 and the pointer is updated to the first section of information immediately following the code translated by the comparison function in a state 412. Otherwise, if the default instruction is determined to be more efficient than the "best result" function, then the default instruction is included in the update package 110 in state 414 and the pointer updated in a similar manner in state 412.

After updating the pointer in state 412, the process 400 determines if the pointer has reached the end of the file in state 416. If the pointer has not reached the end of the file, then the process proceeds to state 406 where the sequence analysis commences for the next code section and may be repeated as necessary using the updated pointer position as a reference. In this manner, the entire file is "stepped through" by progressively incrementing the pointer as the comparison functions are successfully implemented and the most efficient instruction selected. When the end of the file is reached, the instruction set generation process 400 advances to a state 408 where the process terminated and the update package 110 comprising the selected instructions determined in the previous steps is packaged and made ready for distribution.

As previously indicated, the digital information sequence functions update or change the pre-existing digital information sequences in an older code version, such as the first version 106 in FIG. 1, to updated digital information sequences in the newer code version, such as the second version 108 in FIG. 1. In one embodiment, the instruction set generation sequence 400 may use additional instructions for an increased conversion efficiency by providing other methods for updating the code version. Details of each of the disclosed comparison functions will be described in greater detail in connection with FIGS. 6A and 6D. In the following description and associated Figures, exemplary bit and byte sequences corresponding to different word lengths are shown. It will be appreciated that these examples represent but a few of the many possible embodiments of word lengths and sizes that may be used in conjunction with the update management system and methods.

FIG. 6A illustrates one embodiment of a run length encoding (RLE) instruction 500 that may be used in conjunction with the aforementioned instruction set generation process 400. A first word sequence 502 representative of a digital information sequences from the first code version 106, and a second word sequence 504 representative of a digital information sequence from the second code version 108 as shown. When the second word sequence 504 that starts at a particular position of the second code version 108 is determined by the update generator 102 to comprise consecutive series of a particular word 506, such as a value of "W1", then the RLE instruction 500 may be used for a specified word length (N) 508, such as in this case N=6, to generate the desired digital information sequence. The word length is the quantity of word components that are sequentially repeated without interruption by a different value. Using the RLE instruction, repeated word patterns can be readily reconstructed using a single instruction. This instruction desirably occupies less space in the update package compared to the corresponding number of words to be represented in the second code version. The RLE instruction 500 can further be used to specify that a particular word sequence in the first code version is overwritten or modified to form the second code version. Thus, as shown in the illustrated embodiment, the word pattern "W1, W2, W3, W4, W5, W6" in the first code version may be overwritten in the second code version to form the word pattern "W1, W2, W3, W4, W5, W6" . Alternatively, only a portion of the existing word pattern may be overwritten in the new code version by the consecutive word pattern or the consecutive word pattern may be concatenated on to an existing word pattern. Additionally, one or more word components may be specified by the word length 508a specified in the RLE instruction 500 therefore word patterns including "W1","W1, W1","W1, W1, W1", "W1, W1, W1, W1-"and so on can be generated using the RLE instruction with a different word length parameter.

In one aspect, the first word sequence 502 that starts at the same particular position of the digital information sequence from the first code version 106 is replaced with a repeating word sequence of an equivalent length in the second code version. Said another way, the RLE instruction 500 identifies word-wise repeating digital information sequences beginning at a particular position in the file code and replaces the pre-existing digital information sequence using a single instruction. Additionally, if the RLE instruction 500 is later determined to yield the "best" result, as described in the state 408 in FIG. 5 then the RLE instruction 500 for the repeating word-wise sequence 504 is stored in an instruction list along with other parameters, such as the desired number of repetitions 508 of the word. The instruction list represents the series of instructions that are identified by the sequence analysis and instruction set generation function 400 that is required to transform the first code version into the second code version using the update package 110.

One advantage to using the RLE instruction 500 is that consecutive strings of word-wise components in the digital information sequence may be easily placed in the newer code version with a single instruction. Another advantage of using the RLE instruction 500 is that this instruction is relatively simple to execute due to the repetitive nature of the consecutive word-wise string of the second word sequence 504, which will be used to generate the desired digital information sequence.

FIG. 6B illustrates one embodiment of an existing sequence (EXS) or duplicate instruction 510 where a first word sequence 512 representative of a digital information sequence from the first code version 106, and a second word sequence 514
representative of a digital information sequence from the second code version 108 are shown. If the first word sequence 512 that starts at a particular position of the digital information sequence from the first code version 106 is the same or substantially identical to the second word sequence 514 that starts at the same particular position of digital information sequence from the second code version 108, then the EXS instruction 510 may be used for a specified word length (N) 518, such as in this case N=4, to reflect the similarity. As previously shown for the RLE instruction 500, the EXS instruction 510 desirably comprises a word length parameter 518 which is used to determine the extent of the similarity between the first and the second code versions.

In one aspect, the EXS instruction 510 is used by the update generator 102 to identify the existing word sequence which remains unchanged between versions of the code and therefore does not need to be updated or altered during the update process. Furthermore, if the update generator 102 determines that the existing sequence instruction yields the "best" result during the digital information sequence analysis, then the EXS instruction 510 along with the specified word length 518a may be stored in the instruction list along with other parameters, such as the number of repetitions of the digital information sequence. One advantage to using the EXS instruction 510 is that pre-existing word-wise digital information sequences which remain unchanged may be identified and a single small instruction may be incorporated into the update package 110 to reflect the similarity rather than incorporating redundant or unnecessary code.

FIG. 6C illustrates one embodiment of a copy from address or hash (HSH) instruction 520. A first word sequence 522 representative of a digital information sequence from the first code version 106, and a second word sequence 524 representative of a digital information sequence from the second code version 108 is shown by way of example. If the first word sequence 522 that starts at a particular position of the digital information sequence at an address 526, such as in this case address "b", from the first version 106 of operational software code is the same or significantly identical to the second word sequence 524 that starts at a different position of digital information sequence from the second version 108 of operational software code, then the HSH instruction 520 may be used for a specified word length (N) 528, such as in this case N=6, to reflect the update package digital information sequence.

In one aspect, the hash sequence function finds words by calculating hash values for fixed length digital information sequences. The hash values are then compared to the hash table values. If the value of the calculated hash value matches that of a stored hash table value then the start address for the digital information sequence corresponding to the stored hash table value is obtained. When such a match has occurred, a more detailed scanning of the word at the specified address is then performed to determine the maximum length of the word which can be utilized. If the hash table contains more than one stored hash value that matches the calculated hash value, then each possibility may be evaluated and the longest match or most efficient match may be used as the result.

The HSH instruction 520 involves a hash sequence function, wherein the update generator 102 utilizes existing word sequences referenced by addresses stored in the hash table 330 to determine digital sequence matches corresponding to calculated hash values found in the hash table data structure. For example, if the update generator 102 determines that the hash sequence function yields the "best" result of the digital information sequence analysis, then the HSH instruction 520 along with the specified address location 526 and the specified word length 528 may be stored in the instruction list along with other parameters, such as the number of repetitions of the digital information sequence. One advantage to using the HSH instruction 520 is that pre-existing word-wise digital information sequences may be identified in the existing code where the hash table 330 acts as a dictionary of available word. The HSH instruction 520 therefore reflects the ability of the update generation process to recycle code sequences or words in a novel manner rather than including these sequences or words within the update package 110 directly. Another advantage of using the HSH instruction 520 is that this instruction 520 may be used to generate large sections of code by combining various code sections reflected by the addresses referenced in the hash table. For example, as shown in FIG. 6C, the word sequence "W3, W4, W5, W6, W7, W8, W9, W10" in the second code version may be desirably identified in the first code version at the address "b". The HSH instruction 520 uses this address as a reference and copies the code present at this location into the desired location in the second code version. The instruction to perform this operation is desirably smaller in size than incorporating the literal string referenced by the address. Thus, the instruction "HSH b, N" may be used to copy the entire contents of the string located at address "b" and having a length specified by the value of N (N=8
in the example to copy the string "W3, W4, W5, W6, W7, W8, W9, W10".

FIG. 6D illustrates one embodiment of a default (DEF) instruction 532. As previously indicated the DEF instruction 532 is applied by the instruction set generation process 400 when no other instruction can be found to efficiently represent the desired digital information sequence. The DEF instruction 532 is used to replace a digital information sequence from the first version 106 of operational software code with the literal contents of a string or other information sequence associated with the DEF instruction. In other words, the DEF instruction 530 identifies word-wise patterns of digital information sequences that do not match pre-existing digital information sequences in the file code of the first code version 106 and cannot be efficiently reconstructed using other instructions. If the DEF function 530 is determined to yield the "best" or most efficient result of the digital information sequence analysis, then the DEF instruction 530 for the patterned word-wise sequence 534 is stored in the instruction list along with the literal contents of the string or information sequence to be inserted. Thus, the instruction "DEF W15, W16, W17, W18, W19, W20" may be used to copy the literal contents of "W15., W16, W17, W18, W19, W20" into the desired location. One advantage to using the DEF instruction 530 is that non-existing strings of word-wise components in the digital information sequence may be readily inserted in the newer code version of with a single instruction that is desirably incorporated into the update package 110.

FIG. 7 illustrates one embodiment of a reconstructed digital information sequence 550, wherein the reconstructed sequence 550 may be obtained using an instruction set 552 comprising a plurality of instructions used to generate portions of the sequence 550. In the illustrated embodiment, the reconstructed sequence 550 is generated using word-wise instructions. The process of implementing the first instruction set 552 comprises sequentially applying the instructions 500,510, 520,530 to generate the desired word sequence 550. Following a step-wise execution of the instructions of the instruction set, the RLE instruction 500 generates a first bit sequence in the update file, which corresponds to the run length encoded bit sequence 504. The RLE instruction 500 generates the bit sequence "W1, W1, W1, W1, W1, W1, W1" based on the input parameters. Advancing to the next instruction, the EXS instruction 510 generates a second bit sequence, which corresponds to the duplicated bit sequence
514 "W1, W2, W3, W4". The EXS instruction does not copy or alter any bits in the specified region but rather identifies the pre-existing word pattern and leaves this sequence intact. The subsequent HSH instruction 520 generates a third word sequence, which corresponds to the copied word sequence 524 "W3, W4, W5, W6, W7, W8, W9, W10" from the specified address"b"526. Finally, the DEF instruction 530 generates a fourth word sequence, which corresponds to the added word sequence 534 "W15, W16, W17, W18, W19, W20." As previously indicated, the DEF instruction may be used to insert one or more word patterns into the word sequence that either are not found in the existing code version or cannot be efficiently constructed using the aforementioned comparison functions. The illustrated reconstructed word-wise sequence 550 is but one example of the implementation of the instruction set 552. It should be appreciated that the instruction set 552 may comprise one or more instructions 500,510,520,530
in various combinations that may be used to transform the existing code version into the desired code version. One advantage to creating the instruction set to represent the desired code version is that the update package 110 is relatively small compared to an update package that is composed exclusively of literal digital information sequences obtained from conventional differencing methodologies. As a result, transferring the relatively small update package image across a communications medium is more efficient than transferring larger literal updates used by conventional methods.

FIG. 8A illustrates one embodiment of the memory or storage architecture for a portable electronic device to be used in conjunction with the update management system. This architecture is representative of many conventional electronic devices including mobile phones, personal digital assistants, pagers, or other devices that are to be desirably updated using the update management system and methods.

In one aspect, the architecture 1000 comprises a non-volatile memory or storage area 1002 and a volatile memory or storage area 1004. The non-volatile area 1002 is used by the electronic device to store information in a semi-permanent state where the device may be powered down or turned off without loss of the information stored in this area 1002. The non-volatile area 1002 may be further logically subdivided to contain a code section 1006 and a data section 1008. The code section 1006 is responsible for storing information such as the system operating software or firmware code that provides the functionality for device operation. The data section 1008 stores non-essential or user-derived information or other information that may be desirably re-written or changed as necessary. In a typical mobile phone, the data section 1008 may contain information including phone numbers, addresses, or personal memos that are saved so that they may be retrieved when needed or desired without loss due to powering down of the electronic device.

Both the code and data sections 1006,1008 may be accessed and written to throughout the update process to modify existing code stored therein. The data section 1008 also provides an area of memory or storage space that may be used during the update process to store a copy of the update package 110 when it is received by the client. Furthermore, the data section 1008 may store information during the update to provide a degree of fault tolerance should the update operation be interrupted. Details of the fault-tolerant aspects of the update process will be described in greater detail in connection with FIGS. 9 and 10.

While the non-volatile memory or storage area is illustrated as having separate code and data sections, it will be appreciated that the update methods presented herein can readily be adapted to other memory or storage configurations. For example, the non-volatile storage area 1002 may comprise a hardware storage device such as a disk drive, optical drive, or other device implementation which may be used to store information in a non-volatile manner. Additionally, in the case of the non-volatile memory storage area, the memory configuration need not be logically subdivided into separate code and data sections in order to be used with the update management system and methods. It is conceived that the aforementioned memory or storage area configuration represents but one embodiment of an architecture that may be adapted for use with the present invention and other memory or storage areas architectures and configurations can readily be adapted in a similar manner by one of skill in the art.

In one aspect, the architecture of the electronic device specifies that the non-volatile