KR100849301B1 - Apparatus and method for efficient generation of delta files for over-the-air upgrades in a wireless network - Google Patents

Abstract

The present invention relates to a method and apparatus for generating a composite delta file based on differences between an original binary file and an upgraded binary file. Such a compound delta file creation method comprises the steps of: 1) segmenting an original binary file into a plurality of first segments of size N; 2) segmenting the upgraded binary file into a plurality of second segments of size N; 3) detecting a first set of differences between the first segment from the original binary file and the first segment from the upgraded binary file; And 4) generating a first delta file from the detected first set of differences. The method includes 4) detecting a second set of differences between the second segment from the original binary file and the second segment from the upgraded binary file; And 5) generating a second delta file from the detected second set of differences. Combine the first and second delta files to produce a composite delta file.

Over-the-Air Upgrade, Delta Files, Original Binary Files, Upgraded Binary Files, Segments, Segmented Linkers, Segmented Delta Files Generator

Description

EFFECTIVE GENERATION AND METHOD FOR EFFECTIVE DELTA FILE FOR OVER- THE-AIR UPGRADE IN WIRELESS NETWORK

The present invention relates generally to wireless communications, and more particularly to a technique for efficiently generating a delta file for over-the-air upgrade of a wireless mobile station.

Wireless service providers and wireless equipment manufacturers are constantly working to make wireless equipment and services as convenient, user-friendly and affordable as possible. One important aspect of such efforts is the over-the-air of fixed wireless terminals as well as wireless mobile stations such as mobile phones, wireless personal digital assistants (PDAs), wireless handheld computers, two-way pagers, and the like. (OTA) Includes upgrades. Over-the-air (OTA) upgrades, sometimes called firmware over-the-air (FOTA) upgrades, allow mobile station users to upgrade operating systems stored in wireless mobile stations, including bug fixes, and upgraded software. This is a relatively new procedure that allows you to download and install a new version of the included software.

Software upgrades are typically delivered to mobile stations in the form of delta files. Since the mobile station contains a copy of the original file (or old file), it is desirable to replace the original file with the upgraded file (or new file). However, many software programs and other files are so large that they are generally impractical, even if it is not impossible to deliver the entire upgraded file over the air. To overcome that problem, OTA upgrade operations often use delta files. Such delta files are created by detecting differences between the original file and the upgraded file. The detected differences are then used to generate a delta file, which contains data and instructions that can be used to convert the original file into an upgraded file. When delivering a delta file to a wireless mobile station, instructions in the delta file are executed and the data from the delta file is used to modify (or patch) the original file, thereby converting the original file into an upgraded file at the mobile station. The advantage of such a method is that the delta file is typically much smaller than either the original file or the upgraded file.

There are many ways to generate delta files. However, each of these methods suffers from one or more serious disadvantages. The conventional delta file generation algorithm, also known as the "greedy" algorithm, proposed by Reichenberger is suitable for generating delta files of the smallest possible size theoretically. However, such a greedy algorithm cannot be used for virtually any file whose size is larger than 4 megabytes (4 Mb) because of the time it takes to create a delta file. The greedy algorithm requires O (n ² ) memory and execution time, where n is the sum of the old and new files. If the value of n is large, it may take several hours or even days to complete the creation of the delta file.

Another common delta file generation algorithm is the x delta introduced by Josh MacDonald. The x delta algorithm runs in linear time, but the delta file size is much larger than the greedy algorithm. It is a problem with wireless applications because wireless service providers may place restrictions on the delta file size. In addition, the delta file application software (eg, "patch client") running in the mobile station will have a distracting flash memory sector write pattern. It results in an increase in patch application time. Wireless service providers generally impose strict limits on patch application time (eg, less than 10 minutes). An additional problem with distracting flash memory sector write operations is that the wear of the physical flash memory portion will result. As noted, flash memory has a limited erase-write cycle (eg, about 10,000).

Finally, the xdelta command assumes that reconstruction of the upgraded file from the original file does not occur in place. The upgraded file is assumed to be separate and distinct from the old file. At the end of the reconstruction, the old file is deleted, leaving only the upgraded file. Therefore, while creating an upgraded file, you need a flash memory size that is twice the size of an image file.

The vcdiff proposed by Kiem Phong Vo is another linear time algorithm similar to the x delta algorithm. As a result, the vcdiff algorithm suffers from similar drawbacks that harm the x delta algorithm. Finally, the rsync algorithm introduced by Andrew Tridgell is designed to minimize the amount of traffic exchanged between client and server. However, the rsync algorithm does not optimize anything else. Therefore, its use in firmware over-the-air (FOTA) applications is very limited.

Also, prior art algorithms for generating delta files have disadvantages due to the way that conventional linker programs generate original binary files and upgraded binary files, and generate delta files from them. The linker takes the object files and creates an executable file. More specifically, the linker takes as input one or more object files, libraries, and address details from a memory map input file to produce an output file suitable for execution. However, in typical linkers, the executable output has a monolithic attribute. Executable output does not have deterministic ordering of functions, variables, etc. Such details are left completely up to the linker.

Current linkers have no order in selecting object files. Moreover, the order in which the read-write data ("RW data") are collected is also not defined (ie, random). Due to the inherent nature of instruction sets, such as the ARM microprocessor instruction set, branch instruction encoding, jump instruction encoding, and function call instruction encoding change when the address references to those instructions change. When new software modules are added to or deleted from the file (due to bug fixes, etc.), the executable output changes the jump instruction, branch instruction, and function call instruction.

Such changes are continued back to other modules due to the intra-module reference. As a result, such successive changes result in completely different binaries (original binary file and upgraded binary file). It makes the delta file generated between the original binary file and the upgraded binary file very large. Thus, existing linkers not only maintain the spatial locality of the references in the software code, but also actually continually change the changes. Thus, relatively small changes in the software result in large changes in the executable output. Such properties are very inadequate for generating delta files for FOTA applications.

Accordingly, there is a need in the art for an improved apparatus and method for generating delta files for performing over-the-air upgrades of wireless mobile stations. In particular, there is a need for a delta file generation method that provides an optimal balance between the size of the delta file and the time spent generating the delta file. More specifically, there is a need for an improved linker that prevents small changes in the software file from continuing to large changes in the final executable output.

The present invention provides an improved algorithm for generating delta files from the upgraded file and segments of the original file in near linear time. Such algorithms also take advantage of the spatial locality of references that exist in binary code (object code). In addition, the present invention can be implemented in linear time and space based on a greedy file (or another delta algorithm). In addition, the present invention produces delta files that reduce the number of flash memory write operations compared to other prior art algorithms.

The present invention also provides an improved linker that uses spatial locality of references in the object code to produce better executable output. Such an improved linker automatically preallocates spaces between object codes (ie modules, functions) to accommodate future software extensions. The improved linker also analyzes previous executable output (ie, the original binary file) to preserve the address assignments of functions and variables, thereby minimizing changes between two sequential executable files.

In order to address the above-mentioned deficiencies of the prior art, the present invention primarily aims to provide a method for generating a composite delta file based on differences between the original file and the upgraded file. According to a preferred embodiment of the present invention, such a compound delta file creation method comprises the steps of: 1) segmenting an original binary file into a plurality of first segments of size N; 2) segmenting the upgraded binary file into a plurality of second segments of size N; 3) detecting a first set of differences between the first segment from the original binary file and the first segment from the upgraded binary file; And 4) generating a first delta file from the detected first set of differences.

1 illustrates an exemplary wireless network capable of upgrading a mobile station using a space efficient delta file generation algorithm in accordance with the principles of the present invention;

2 shows selected portions of an upgrade server in accordance with the principles of the invention;

3 illustrates a composite delta file in accordance with an exemplary embodiment of the present invention;

4 is a flow diagram illustrating a new algorithm for generating delta files in accordance with the principles of the present invention.

According to one embodiment of the invention, the method of generating a composite delta file comprises: 4) detecting a second set of differences between a second segment from an original binary file and a second segment from an upgraded binary file; And 5) generating a second delta file from the detected second set of differences.

According to another embodiment of the present invention, the method of generating a compound delta file further includes combining the first delta file and the second delta file to generate a compound delta file.

According to another embodiment of the present invention, the method of generating a compound delta file further includes transmitting the compound delta file to a target device including a copy of the original file.

According to another embodiment of the present invention, the method of generating a composite delta file comprises: generating data verification values from a first delta file and a second delta file; And adding the data verification value to the compound delta file.

According to another embodiment of the invention, the data verification value comprises a cyclic redundancy check (CRC) value.

According to another embodiment of the present invention, generating the first delta file and generating the second delta file use the greedy algorithm to generate the delta files.

According to another embodiment of the present invention, segmenting the original binary file comprises a sub-step of segmenting the original binary file based on a memory map input file associated with the target device.

According to one embodiment of the invention, segmenting the upgraded file includes sub-segmenting the upgraded binary file based on a memory map input file associated with the target device.

In order to address the above-mentioned deficiencies of the prior art, the present invention is primarily directed to providing a segmentation linker that generates an upgraded file suitable for replacing a copy of an original binary file installed on a target device from the original binary file. According to a preferred embodiment of the present invention, the segmentation linker receives as inputs a plurality of objects, an original binary file, and a memory map input file associated with a target device, but with a space of reference of the code in the original binary file. Keep at least some of the locality intact in the upgraded binary file.

According to one embodiment of the invention, the segmentation linker further receives as input a linker guidelines file that defines the layout of objects with spatial locality of reference in the original binary file.

According to another embodiment of the present invention, the present segmentation linker uses a linker guidelines file to limit the propagation of consecutive address references in the upgraded binary file.

According to another embodiment of the present invention, the segmentation linker uses the linker guidelines file to maintain the order of objects with spatial locality of reference in the original binary file in the upgraded binary file.

According to another embodiment of the present invention, the segmentation linker pre-allocates space between objects and modules in the upgraded binary file using the linker guidelines file.

According to another embodiment of the present invention, the segmentation linker reserves space between objects and modules in the upgraded binary file based on the number of external functions and objects outside the address space of the modules and objects. Assign.

According to another embodiment of the present invention, the segmentation linker pre-allocates space between objects and modules in the upgraded file based on the heuristic values provided by the programmer.

According to one embodiment of the invention, the segmentation linker maintains the address assignments of variables and functions in the upgraded file using information from the original binary file.

Prior to undertaking the detailed description of the invention below, it may be desirable to disclose the definitions of specific words and phrases used throughout this patent application specification. The terms "include and comprise", as well as derivatives thereof, mean inclusion, not limitation. The term "or" encompasses the meaning of "and / or". The phrases "associated with" and "associated therewith", as well as derivatives thereof, include "include", "be included within", and "interconnect with." ), "Contain", "be contained within", "connect to or with", "couple to or with", "be communicated" communicable with "," cooperate with "," interleave "," juxtapose "," be proximate to "," be bound to or with) "," Have "," have a property of "and the like. The term “controller” means any device, system, or component thereof that controls one or more operations, which device may be implemented in hardware, firmware, software, or a combination of two or more thereof. It should be noted that the functionality associated with any particular controller can be centralized or distributed locally or remotely. Such definitions of specific words and phrases are defined throughout this patent specification, and those of ordinary skill in the art, in many cases, although not in many cases, words and phrases in which such definitions are so defined. It should be understood that this applies to future use as well as to future use.

Hereinafter, exemplary embodiments of the present invention will be described in detail with reference to the accompanying drawings. In the following description and the annexed drawings, detailed descriptions of well-known functions and configurations that may unnecessarily obscure the subject matter of the present invention will be omitted.

The various embodiments used in describing the principles of the invention in the Figures 1-4 and the present patent application, which will be discussed hereinafter, are merely illustrative and should not be construed as limiting the scope of the invention. . Those skilled in the art will appreciate that the principles of the present invention may be implemented in any wireless network suitably established.

1 illustrates an exemplary wireless network in which a mobile station can be upgraded using a space efficient delta file generation algorithm in accordance with the principles of the present invention. The invention is implemented in an upgrade server (not shown) interworking wireless network 100 by the Internet or a similar wide area IP network. Alternatively, the upgrade server may work with the wireless network 100 by means of a public switched telephone network (PSTN).

The wireless network 100 includes a plurality of cell sites 121-123 each including one of the base stations (BS) 101, 102, 103. The base stations 101-103 communicate with a plurality of mobile stations (MS) 111-114, for example, via code division multiple access (CDMA) channels according to the IS-2000 standard (ie, CDMA2000). In a preferred embodiment of the present invention, mobile stations 111-114 may simultaneously receive data traffic and / or voice traffic over two or more CDMA channels. Mobile stations 111-114 may be any suitable devices (e.g., conventional mobile phones, PCS handsets, personal digital assistant (PDA) handsets) capable of communicating with base stations 101-103 via wireless links. , Portable computers, telemetry devices).

The invention is not limited to mobile devices. The present invention also includes other types of wireless access terminals, including fixed wireless terminals. For simplicity, only the mobile station will be shown and discussed later. However, the use of the term "mobile station" in the claims and in the following description is intended to refer to the strict meaning of mobile devices (e.g., mobile phones, wireless laptops) and fixed wireless terminals (e.g., a wireless monitor) It should be understood that the intention is to cover everything.

The dotted lines represent schematic boundaries of the cell sites 121-123 where the base stations 101-103 are located. Cell sites are shown in approximately circular form for illustrative purposes only. It will be appreciated that cell sites may have other irregular shapes depending on the cell configuration selected and natural and artificial obstacles.

As is well known in the art, each cell site 121-123 consists of a number of sectors, where a directional antenna that cooperates with the base station illuminates each sector. 1 illustrates a base station in the center of a cell. An alternative embodiment may place directional antennas at the corners of the sectors. The system of the present invention is not limited to any particular cell site configuration.

In one embodiment of the present invention, each BS 101, 102, 103 consists of a base station controller (BSC) and one or more base station transmit / receive subsystems (BTSs). Base station controllers and base transceiver stations are well known to those skilled in the art. A base station controller is a device that manages wireless communication resources, including base station transmit and receive subsystems, for designated cells in a wireless communication network. The base station transmit / receive subsystem includes RF transceivers, antennas, and other electrical equipment located at each cell site. Such equipment may include air conditioning units, heating units, power supplies, telephone line interfaces, and RF transmitters and RF receivers. For simplicity in describing the operation of the present invention, the BS 101 is collectively referred to as base station transmit / receive subsystems in each cell 121, 122, 123 and base station controllers associated with the respective base station transmit and receive subsystems. , BS 102, and BS 103, respectively.

BS 101, BS 102, and BS 103 communicate voice over communication line 131 and mobile switching center (MSC) 140 between each other and a public switched telephone network (PSTN) (not shown). And transmit data signals. BS 101, BS 102, and BS 103 also transmit data signals, such as packet data, to the Internet via communication line 1310 and packet data server node (PDSN) 150. Packet control functions ( PCF) unit 190 controls the flow of data packets between base stations 101-103 and PDSN 150. PCF unit 190 is part of PDSN 150 and is part of MSC 140. Or as a stand-alone device in communication with PDSN 150 as shown in Figure 1. Communication line 131 is configured with MSC 140 and BS 101, BS 102, and BS 103. A connection path is also provided for the control signals transmitted between the connection path, which establishes a connection to voice and data circuits between the MSC 140 and the BS 101, BS 102, and BS 103. do.

The communication line 131 may be any suitable connection means such as a T line, a T line, an optical fiber link, a network packet data backbone connection path, or any other type of data connection path. The communication line 131 connects each vocoder in the BSC to an exchange element in the MSC 140. Connection paths through the communication line 131 transmit analog voice signals or digital voice signals in pulse code modulation (PCM) format, Internet protocol (IP) format, asynchronous transmission mode (ATM) format, and the like.

MSC 140 is a switching device that provides coordination between services and subscribers in wireless networks and external networks such as PSDN or the Internet.

MCS 140 is well known to those skilled in the art. In some embodiments of the invention, the communication line 131 may be a plurality of different links where each data link associates one of the BS 101, BS 102, and BS 103 with the MSC 140. have.

In such exemplary wireless network 100, MS 111 is located at cell site 121 and is in communication with BS 101. MS 113 is located at cell site 122 and is in communication with BS 102. MS 114 is located at cell site 123 and is in communication with BS 103. The MS 112 is located close to the edge of the cell site 123 and is moving towards the cell site 123 as indicated by the directional arrows close to the MS 112. At a particular point in time, as MS 112 moves out of cell site 121 into cell site 123, a handoff occurs.

Mobile stations 111-114 are upgraded by an upgrade server (not shown) that generates delta files in accordance with the principles of the present invention. The space efficient delta files are sent from the upgrade server to the base stations 101-103 and then to the over-the-air mobile stations 111-114.

2 shows selected portions of an upgrade server 200 in accordance with the principles of the present invention. Upgrade server 200 may include object files 205, link guidelines 210, segmentation linker 215, memory map input file 220, upgraded binary file (or new binary file) 235, A segmentation delta file generator 245, and a compound delta (Δ) file 250. Segmentation linker 215 is an application program that takes object files 205, libraries, and address details as input to generate an executable file, that is, an upgraded binary file 230. As will be discussed in more detail below, in a preferred embodiment of the present invention, the segmentation linker 215 uses the memory map input file 220 and the linker guidelines file 210 as additional inputs for reference in software. The upgraded executable binary file 230 is generated based on the spatial locality.

According to the principles of the present invention, segmentation delta file generator 245 segments delta files in time and space efficiently by segmenting each of upgraded binary file 230 and original binary file 235 into multiple segments. Create Segmented delta file generator 245 then generates a number of delta files from those segments from upgraded binary file 230 and original binary file 235. Subsequently, segmentation delta file generator 245 combines the plurality of delta files so generated into compound delta file 250 (or macro delta file 250), which compound delta file 250 is assigned to mobile stations. Are sent to 111-114.

To achieve the foregoing, segmentation delta file generator 245 uses memory map input file 220 as input to determine how to segment delta files. Typically, a linker program, such as segmentation linker 215, uses memory map input file 220 to generate an executable function file from object files. The memory map input file 220 defines how to use the memory space of the target device (in this case, the mobile station). The memory map input file 220 thus defines, for example, the address space of flash memory and random access memory (RAM) at the mobile station 111 and, for example, of data files, programs, boot ROM, free space, and stack boundaries. Define locations.

Typically, the linker uses the memory map input file 220 to create an executable file from the object files and safely stores the executable file in memory on the target device without overwriting other required files. The segmentation delta file generator 245 also uses the memory map input file 220 to generate segmentation delta files in accordance with the principles of the present invention. The segmented delta files can then be combined into a compound delta file (or macro delta file), and a cyclic redundancy check (CRC) field can be added to verify the data contained in the compound delta file. As described above, the time required to generate a delta file according to the prior art greedy algorithm increases exponentially as the combined size of the upgraded file and the original file increases. In accordance with the principles of the present invention, segmenting upgraded and original files and then generating segmented delta files requires much less processing time than generating a single delta file directly from the entire upgraded and original files. It takes Conflicting the present invention is that the complex delta files produced by the present invention are somewhat larger than the full size upgraded file and the minimum size delta file generated by the conventional greedy algorithms that operate on the original file.

3 illustrates an exemplary composite delta file 250 in accordance with an exemplary embodiment of the present invention. Such compound delta file 250 includes individual delta files 311-316 and a CRC field 317. Each of the delta files 311-316 is created from one segment from the upgraded binary file 230 and one segment from the original binary file 235. After segmentation delta file generator 245 generates delta files 311-316, segmentation delta file generator 245 calculates a CRC value for all of delta files 311-316, and the The calculated CRC value is appended to the delta files 311-316 in the CRC field 317. Then, the composite delta file 250 is sent to the mobile stations 111-114.

4 shows a flow diagram 400 illustrating a new algorithm for generating delta files in accordance with the principles of the present invention. Initially, segmentation delta file generator 245 splits the original (old) binary file 235 and the upgraded (new) binary file 230 into segments of size N (process step 405). According to a preferred embodiment of the present invention, the segmentation delta file generator 245 determines the value of N according to the flash sector sizes of the memory in the mobile stations 111-114. The segmentation delta file generator 245 determines the flash sector size according to the information contained in the memory map input file 220.

Next, for each segment, segmentation delta file generator 245 executes a conventional delta file generation algorithm, such as the greedy algorithm, to calculate delta commands and data for each segment (process step 410). Segmented delta file generator 245 eliminates write conflicts in the delta command so that the delta file can be applied in place at the target mobile station (process step 415). Segmented delta file generator 245 then encodes the delta file command and data (process step 420). The segmentation delta file generator 245 repeats process step 410, process step 415, and process step 420 until all segments of the original binary file 235 and the upgraded binary file 230 have been processed (process step 425). ).

The present invention takes advantage of the spatial coherence in the original binary file 235 and the upgraded binary file 230 because blocks of code are mostly identical at the same offsets in the two related files. In other words, two similar versions of the same software typically show high similarity with similar offsets in the code. The present invention may apply the known "grid algorithm" (by Reichenberger) to calculate the deltas, but other well known algorithms may be used. The present invention provides most of the advantages of the delta file size that is still theoretically optimal while providing an improvement over the greedy algorithm. By executing the COPY and ADD commands together at the end of each segment, the number of flash write operations is minimized. Conventional delta patch algorithms require a two-pass approach to handling COPY and ADD instructions separately. Since the present invention has a nearly linear resource demand (memory and time), large binaries (e.g.> 4MB) will be executed in a deterministic amount of time.

By using the segmentation linker (or smart linker) in accordance with the principles of the present invention, the quality of the delta files generated by the segmentation delta file generator 245 is further improved. The present invention adds additional intelligence to the segmentation linker to maintain the spatial locality of the reference between the original binary file 235 and the upgraded binary file 230. It is mainly done to limit the propagation of consecutive address references.

The segmentation linker 215 receives linker guidelines file 210 in addition to receiving object files 205, memory map input file 220, upgraded binary file 230, and original binary file 235 as input. ) Is also received as an additional input. According to a preferred embodiment of the present invention, the linker guidelines file 210 consists of a script that describes objects with spatial locality of reference. Segmentation linker 215 uses linker guidelines file 210 to maintain the order specified by the software programmer.

In addition, segmentation linker 215 uses linker guidelines file 210 to pre-allocate spaces between objects and modules (including functions). Such pre-allocated spaces may be referred to as "holes." Segmentation linker 215 calculates the pre-allocated space based on the amount of non-local symbol references, ie the number of external functions and variables outside of the module (or object code). Only segmentation linker 215 knows the number and type of non-local references. Thus, segmentation linker 215 uses that information to produce better executable output (ie, upgraded binary file 230).

The amount of pre-allocated space (or holes) may be modified by the heuristic value provided by the programmer, accepting future changes to those functions / purpose files. Thus, if the software is modified in the future, eg due to bug fixes, the hole space ensures that changing the addresses of functions and variables in one module is not contiguous to another module. Segmentation linker 215 also examines previous executable output (ie, original binary file 235) to maintain the same address assignments to variables and functions. It further reduces subsequent changes.

As a result, the segmentation linker 215 generates a binary output file (ie, an upgraded binary file 230) that is ideally suited for FOTA application, because the upgraded binary file 230 and the original binary file 235 This is because the differences between two sequential executable outputs, such as), tend to be relatively small. Thus, the size of the delta file generated by the segmentation delta file generator 245 (or any other conventional delta file generator) is minimized.

While the present invention has been described with exemplary embodiments, various changes and modifications may be suggested to one skilled in the art. It is intended that the present invention cover such changes and modifications as come within the scope of the appended claims. Therefore, the scope of the invention should not be defined by the described embodiments, but should be determined by the equivalent of claims and claims.

The present invention can be applied to the field of wireless communication, in particular when the wireless terminal is upgraded through an over-the-air scheme.

Claims (30)

In the method of generating a compound delta file, Segmenting the original binary file into multiple segments of size N, Segmenting the upgraded binary file into multiple segments of size N, Detecting differences between a first segment of segments segmenting the original binary file and a second segment of segments segmenting the upgraded binary file; Generating a first delta file from the differences between the detected first and second segments. The method of claim 1, Detecting differences between a third segment of segments segmenting the original binary file and a fourth segment of segments segmenting the upgraded binary file; Generating a second delta file from the differences between the detected third segment and the fourth set. The method of claim 2, And combining the first delta file and the second delta file to generate a composite delta file. The method of claim 3, And transmitting the compound delta file to a target device that stores a copy of the original file for the compound delta file. The method of claim 4, wherein Generating data verification values for both the first delta file and the second delta file; And adding the generated data verification value to the compound delta file. The method of claim 5, And the data verification value comprises a cyclic redundancy check (CRC) value. The method of claim 6, And the first delta file and the second delta file are generated using a greedy algorithm. The method of claim 7, wherein Segmenting the original binary file, Sub-segmenting the original binary file using a memory map input file for the target device; The size N of the segments segmented from the original binary file is determined by the sector size of the flash memory provided in the target device. The method of claim 8, Segmenting the upgraded binary file, Sub-segmenting the upgraded binary file using a memory map input file for the target device; The size N of the segments segmented from the upgraded binary file is determined by the sector size of the flash memory provided in the target device. The method of claim 9, The target device comprises a wireless mobile station, And wherein the composite delta file is transmitted to the wireless mobile station via a wireless network. In the recording medium recording the data structure of the complex delta file, Segment the original binary file into a plurality of segments of size N, segment the upgraded binary file into a plurality of segments of size N, and segment the first binary file with the first segment and the upgrade Detecting the differences between the second ones of the segmented binary files, and generating and storing a first delta file from the differences between the detected first and second segments. Recording medium recording the data structure of a file. The method of claim 11, wherein the recording medium, Detect differences between a third segment of segments segmenting the original binary file and a fourth segment of segments segmenting the upgraded binary file, and detect the difference between the detected third segment and the fourth segment Recording medium recording a data structure of a complex delta file, wherein a second delta file is generated from the differences. The method of claim 12, wherein the recording medium, And recording the data structure of the composite delta file by combining the first delta file and the second delta file. delete The method of claim 13, wherein the recording medium, And generating a data verification value for both the first delta file and the second delta file, and adding the generated data verification value to the composite delta file. The method of claim 15, And the data verification value comprises a cyclic redundancy check (CRC) value. The method of claim 16, And the first delta file and the second delta file are generated using a greedy algorithm. The method of claim 17, wherein the recording medium, Segment the original binary file into the plurality of segments using a memory map input file for the target device, And a size N of the segments is determined by a sector size of a flash memory provided in the target device. 19. The method of claim 18, wherein the recording medium, Segment the upgraded binary file into a plurality of segments using a memory map input file for the target device, And the size N of the segments is determined by a sector size of a flash memory provided in the target device. The method of claim 19, The target device comprises a wireless mobile station, And the composite delta file is transmitted to the wireless mobile station via a wireless network. In a device that generates a complex delta file, Receiving the original binary file and a memory map input file for the target device as inputs, and maintaining at least some of the spatial locality of the reference corresponding to the code in the original binary file in the upgraded binary file; A segmentation linker that uses the upgraded binary file to create an upgrade file for replacing a copy of the original binary file stored on the target device; Segment each of the original binary file and the upgrade binary file into a plurality of segments, generate a plurality of delta files from the segments segmented from the original binary file and the upgraded binary file, and generate the plurality of deltas And a segmentation delta file generator that combines the files into one compound delta file for transmission to mobile stations. The method of claim 21, wherein the segmented linker, And further receiving as a input a linker guidelines file that defines the layout of the objects having spatial locality of the reference in the original binary file. The method of claim 22, wherein the segmented linker, And use the linker guidelines file to limit propagation of consecutive address references in the upgraded binary file. The method of claim 23, wherein the segmented linker, And use the linker guidelines file to maintain the order of objects having spatial locality of the reference in the original binary file in the upgraded binary file. delete delete delete delete delete delete

Images