Method for reducing binary image update package sizes

• US 20060039618A1
• Filed: 08/20/2004
• Published: 02/23/2006
• Est. Priority Date: 08/20/2004
• Status: Active Grant

• Current Assignee: Insignia Solutions Plc (America's Suppliers, Inc.)
• Original Assignee: Insignia Solutions Plc (America's Suppliers, Inc.)
• Inventors: Ogle, Andrew J.
• Granted Patent: US 7,661,102 B2
• Time in Patent Office: Days
• US Class Current: 382/236
• CPC Class Codes: G06F 8/658 Incremental updates; Differential updates

Abstract

A system and method for reducing the update package size used to convert an original image into a new image based on the differences between the two images. From comparison of original and new images, an update package is generated which includes ADD and COPY operations. This design introduces a RELOCATE operation. The update encoder attempts to re-express submitted COPY operations with one or more RELOCATE operations whose total length exceeds that of the original COPY. If this is the case, the RELOCATE operation(s) have progressed further through the images than the original COPY operation, thus producing a smaller update package. Each individual RELOCATE operation includes a number of instructions and a number of data items to be relocated.

Claims

1. A method for converting an original binary image into a new binary image, said method comprising:

a. Determining differences between the original image and the new images by a binary comparison thereof;

b. Expressing the differences between the original image and the new image as a set of instructions comprising one or more candidate COPY operations;

c. Re-expressing each candidate COPY operation as a RELOCATE operation, wherein each said RELOCATE operation comprising two operands whereby a first operand expresses a number of instructions to be relocated and a second operand expresses a number of data values to be relocated;

d. Replacing in the instruction set each candidate COPY operation with one or more corresponding RELOCATE operations if said RELOCATE operation'"'"'s total length progresses further through the original and new images than the corresponding COPY operation;

e. Populating an address translation table which comprises a sorted list of addresses and delta values corresponding to the original image and the new image; and

f. Encoding an update package to include (i) the instruction set comprised of a plurality of COPY and RELOCATE operations and (ii) the address translation table.

2. The method of claim 1 whereby said update package is decoded and applied to the original image to create the new image.

3. The method of claim 1, wherein said re-expressing comprises analysis of the original image and new image and/or of information from link maps yielding detailed information relating which parts of the image are actually code and which are data.

4. The method of claim 1, wherein encoding the COPY operation is followed by encoding one or more RELOCATE operations into the update package.

5. The method of claim 1, wherein encoding a plurality of consecutive RELOCATE operations are grouped between BEGIN/ENDRELOCATE operation pairs.

6. The method of claim 1, wherein said populating comprises pre-loading the address translation table with an outline of code/data movement, using original firmware symbolic information, by matching symbols between link maps for the original image and new image, deriving an associated delta from the differences in their addresses, and associating relocation type HINT for each pre-loaded entry.

7. The method of claim 1, wherein said populating adds relocation HINTS to address translation table entries further comprises:

a. Identifying commonly occurring compiler-generated ‘

switch’

constructs;

b. Matching switch constructs from the original image and new image;

c. Examining the original image and new image jump tables ensuring same size;

d. Extracting associated code entry points from their jump tables;

e. Generating new address translation table entries, one for each entry in the jump table; and

f. Associating relocation type HINT for each new address translation table entry.

8. The method of claim 1, wherein said populating pre-loads address translation table entries relating movement of data areas within the images further comprises:

a. Identifying commonly occurring load register instructions where the value being loaded is itself an address;

b. Matching identical load register instructions from the original image and new image;

c. Calculating the address being loaded in the original image and new image and determining that they both fall within their corresponding images;

d. Determining a 32-bit value of the data item at that location representing corresponding addresses within the original image and new image;

e. Generating new address translation table entries, for each corresponding address; and

f. Associating relocation type HINT for the new address translation table entry.

9. The method of claim 1, wherein said encoding the address translation table employs compressing the contents further comprises:

a. Discarding address/delta pairs of type HINT;

b. Removing consecutive entries having the same deltas except for the first entry in each sequence;

c. Splitting the address translation table into two equal length lists, one containing addresses, and the other containing corresponding deltas;

d. Expressing each list as a list of difference values where each value is the difference between two consecutive entries in the original list;

e. Shifting all resulting values 1-bit to the right;

f. Encoding values in the resulting lists using variable length encoding, including a leading zero byte on values where the original value was odd; and

g. Writing the two lists into the update package using a standard compression library.

10. The method of claim 1, wherein said populating employs multiple pass differencing further comprises:

a. Discarding the update package generated after the first run of a BDE;

b. Retaining contents of the address translation table constructed during a first differencing pass as a pre-populated form;

c. Modifying retained address translation table entries of type REQUIRED to type HINT;

d. Processing the same original image and new image using a second differencing pass; and

e. Adding entries to the address translation table during the second differencing pass.

12. The method of claim 10, wherein said applying further comprises:

a. Extracting the address translation table from the update package;

b. Processing each operation contained within the update package in sequential order; and

c. Decoding each RELOCATE operation according to addresses/delta information read from the address translation table.

11. A method of updating an original image to create a new image, said method comprising:

a. Generating an update package by comparing the original image and the new image and using result of said comparison to encode an instruction set comprised of;

i. A plurality of operations, including at least one RELOCATE operation comprising two operands whereby a first operand expresses a number of instructions to be relocated and a second operand expresses a number of data values to be relocated, and

ii. An address translation table comprising a sorted list of addresses and delta values corresponding to the original image and the new image; and

b. Applying the update package by interpreting the instruction set to direct the updating of the original image to create the new image in an order specified by the plurality of operations and associated address translation table values.

13. The method of claim 11, wherein said decoding of RELOCATE operations further comprises:

a. Copying instructions from the original image to new image, relocating any transfers of control found within those copied according to the addresses/delta information read from the address translation table; and

b. Copying data from original image to new image relocating each item according to the addresses/delta information read from the address translation table.

14. A method for updating an original image into a new image, said method comprising:

a. Generating an instruction set including one or more RELOCATE operations, wherein each said RELOCATE operation performs a COPY operation of the same length as the complete RELOCATE operation, then patching all branch instructions within a copied code section and all data values within a copied data section using information from an address translation table;

b. Populating the address translation table with a sorted list of addresses and delta values, whereby each address relates to the original image and the corresponding new image address is found by adding the delta value to the address; and

c. Encoding to create an update package comprising the instruction set and the address translation table.

15. A method for creating and applying an update package to efficiently modify an original image to create a new image, wherein said new image is generated by applying instructions contained within said update package modifying an original image, said method comprising:

a. Applying a differencing technique to the original image and new image;

b. Identifying distinctive patterns of code/data sections common to the original image and new image;

c. Moving code/data sections common to the original and new image;

d. Identifying transfers of control within said moved code/data section;

e. Expressing moving said code/data sections through the address space to form the new image;

f. Building the update package containing instructions to direct movement of said code/data sections and any associated transfer of control within moved sections.

16. The method of claim 15, wherein said expressing further comprises:

a. Copying said common code/data sections; and

b. Patching all transfer of control instructions within the code section and data values within the data section.