Method for reducing binary image update package sizes

• US 7,661,102 B2
• Filed: 08/20/2004
• Issued: 02/09/2010
• Est. Priority Date: 08/20/2004
• Status: Active Grant

• Current Assignee: Insignia Solutions Plc (America's Suppliers, Inc.)
• Original Assignee: Smith Micro Software Incorporated
• Inventors: Ogle, Andrew J.
• Primary Examiner(s): Zhen; Wei Y
• Assistant Examiner(s): Chen; Qing
• Application Number:
  US10/922,718
• Publication Number:
  US 20060039618A1
• Time in Patent Office: 1,999 Days
• Field of Search: 717/136, 717/140, 717158-159, 717168-178
• US Class Current: 717/168
• 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 convening an original image into a new image, said method implemented in a computing device and comprising:

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

b. Expressing the differences between the original image and the new image as an instruction set comprising at least one candidate COPY operation;

c. Re-expressing each candidate COPY operation as a RELOCATE operation, wherein each said RELOCATE operation comprises 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 at least one corresponding RELOCATE operation if each corresponding RELOCATE operation'"'"'s total length progresses further through the original and new images than a corresponding COPY operation;

e. Populating an address translation table which comprises a sorted list of original image addresses where each original image address is related to an associated delta value, wherein the corresponding image addresses in the new image are found by adding said associated delta value to each original image address of the sorted list of original image addresses; 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 pans of the original image we actually code and which are data.

4. The method of claim 1, wherein encoding a 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'"'"'s jump tables;

c. Examining the original image and new image'"'"'s 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 new image'"'"'s 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 original image and new image 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 a data item at a location representing corresponding addresses within the original image and new image;

e. Generating a new address translation table entry, 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 an original list;

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

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

g. Writing the two equal length 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 a 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.

11. A method of updating an original image to create a new image, said method implemented in a computing device and 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 original image addresses where each original image address is related to an associated delta value, wherein the corresponding image addresses in the new image are found by adding associated delta values to each original image address of the sorted list of original image addresses; 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 data values.

12. The method of claim 11, 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 data values.

13. The method of claim 12, wherein said decoding of each RELOCATE operation 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 data values; 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 data values.

14. A method for updating an original image into a new image, said method implemented in a computing device and comprising:

a. Generating an instruction set including one or more RELOCATE operations, wherein each RELOCATE operation performs a COPY operation of the same length as a complete RELOCATE operation, and each RELOCATE operation comprises 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;

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

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