System and method for compressing and decompressing a binary code image

[0002] This present invention relates to software image processing. More specifically, it relates to a system and method for compressing and decompressing a binary code image.

[0003] Executable code or executable images are files, such as, files ending with extensions for example, but not limited to, “.exe” and “.bin.” There is a growing need to maintain multiple executable images in different devices or systems in case of potential damage during normal use or image upgrades. To facilitate the need to maintain redundant or otherwise multiple executable images, either a device's storage space is increased by a factor of two or more, or the image size is reduced. However, it is typically cost prohibitive to increase the storage space of a device. Thus, the reduction in image size, such as, by compressing the software image is a viable solution.

[0004] Compression techniques currently in use may only result in a file half the size of the original, typically resulting in undesirable transmission speeds. As a result, new technology such as interactive communication services, requiring larger data files to be stored or transmitted over a network, are possibly limited due to digital data storage size and transmission efficiency. Executable images represented by binary code and hereinafter referred to as “binary code images” must be compressed to travel over the network or be stored in a memory element efficiently. Binary code images are data files consisting of a sequence of 8-bit data or executable code. Binary format is generally used to represent object code which are program instructions translated into a machine-readable form, or data in a transmission stream. Traditional methods typically compress data in a single contiguous stream. However, the nature of binary data, more specifically binary code images does not lend itself well to this methodology, since it includes operation codes mixed in with operands. Operation code is a portion of a machine or assembly language instruction that specifies the type of instruction and the structure of the data on which it operates. The operands are the objects of the computer instruction or mathematical operation. There are few matches between the operation codes and operands, making the compression of a binary code image difficult. As a result, compression ratios for binary code images are less than desirable, making transmission over a network or storage of the image inefficient.

[0005] Thus, there is a need to efficiently compress, and subsequently decompress or reconstruct binary code images to enable additional storage capability and to facilitate the transmission of the images over different networks.

[0006] The system and method for compressing and decompressing a binary code image is predicated on the recognition that binary code images are an intermingling of operation codes and operands. Many of the operation codes have similar patterns, while many of the operands have similar patterns. The system and method for compressing and decompressing a binary code image groups the binary code image data to take advantage of the similar patterns present amongst operation codes and similar patterns present amongst operands.

[0007] In accordance with one aspect of the present invention, a method for compressing and decompressing a binary code image includes the step of receiving an input of a binary code image and preprocessing the binary code image which includes parsing the image in a columnar format to match operating codes with operating codes and operands with operands. The method includes the step of compressing the preprocessed columnar data using one of a plurality of compression models and codes. The method then includes transferring the compressed image over a network or to a memory device. The method further includes receiving the compressed image and processing the compressed image prior to decompressing the compressed image to yield a reconstructed image.

[0008] In accordance with another aspect of the present invention, a system for compressing and decompressing a binary code image includes a first preprocessor to format the binary code image; a first processor to compress the formatted binary code image, a transmission channel or memory device used to channel or store the compressed image; and a second processor to reconstruct or decompress the image.

[0009] In a preferred embodiment, the compression and decompression are performed by the same processor, thus the first and second processors are the same processor. In another preferred embodiment, the first processor and second processor are separate and process the image in two different devices or systems.

[0010] The foregoing and other objects, features and advantages of the system and method for compressing and decompressing a binary code image will be apparent from the following more particular description of preferred embodiments of the system and the method as illustrated in the accompanying drawings in which like reference characters refer to the same parts throughout the different views.

[0011] Preferred embodiments of the present inventions are described with reference to the following drawings, wherein:

[0012] FIG. 1ais a diagram illustrating an exemplary memory image of an executable binary code image;

[0013] FIG. 1bis a diagram illustrating a memory image evaluated in contiguous order;

[0014] FIG. 1cis a diagram illustrating a memory image evaluated in a columnar order in accordance with a preferred embodiment of the present invention;

[0015] FIG. 2 is a top-level flow diagram illustrating the system and method for transferring a binary code image in accordance with the present invention;

[0016] FIG. 3 is a flow diagram illustrating a preferred embodiment of a method for compressing a binary code image in accordance with the present invention;

[0017] FIG. 4 is a listing of an exemplary set of instructions for preprocessing a binary code image prior to compressing the image in accordance with a preferred embodiment of the present invention;

[0018] FIG. 5 is a listing of an exemplary set of instructions for compressing a binary code image in accordance with a preferred embodiment of the present invention;

[0019] FIG. 6 is a flow diagram illustrating a preferred embodiment of a method for decompressing a binary code image in accordance with a preferred embodiment of the present invention; and

[0020] FIG. 7 is a listing of an exemplary set of instructions for decompressing a binary code image in accordance with a preferred embodiment of the present invention.

[0021] The system and method of the present invention is directed to compressing and decompressing a binary code image to facilitate transferring the binary code image over a data network or to a storage device. The system and method of the present invention includes preprocessing the binary code image, compressing the preprocessed image, transferring the compressed image over a transmission channel or to a memory device and subsequently decompressing the binary code image to reconstruct the binary code image.

[0022] FIG. 1aillustrates an exemplary memory image 10 of an executable binary code image. The memory image 10 is shown in hexadecimal form for readability. Hexadecimal form uses sixteen rather than base ten for representing numbers. The hexadecimal system uses the digits 0 through 9 and the letters A through F (uppercase or lowercase) to represent the decimal numbers 0 through 15. One hexadecimal digit is equivalent to 4 bits, and 1 byte can be expressed by two hexadecimal digits. The memory image 10 constitutes a portion of the digital memory typically found in a device handling binary images. The memory image 10 labeled having columns 12 and rows 14 may have a more or less number of columns and rows depending on factors such as the available memory size of the device and the size of the binary code image itself.

[0023] The binary code image may include operation codes and operands. An operation code typically is a portion of a machine language instruction that specifies the structure of the data on which it operates such as, for example, a group of bits representing the binary code image. An operation code may specify an operation such as adding, subtracting, shifting, or complement commonly referred to as a computer's instruction set. When an operation code is detected by a control unit for example, an arithmetic logic unit (ALU), the control unit typically executes the instruction embedded in the binary image, for example, a sequence of control words are applied to perform the intended operation. Therefore, the operation code of an instruction set typically specifies the operation to be performed. The operation codes of the binary code image are typically represented in a columnar format. The number of columns or bits required for the operation code of instruction is typically a function of the total number of operations in the instruction set. For example, the operation code may consist of at least m bits for up to 2^mdistinct operations.

[0024] The operation code specifies an operation to be performed on the operands which are the objects of the instruction or operation. The operands in FIG. 1aare located in columns 18 onwards after the operation codes represented in column 16 of the binary code image. Remaining columns in (i.e., those columns that are not made up of operands or operation codes) may consist of data typically stored in memory registers relating to the stored binary code image.

[0025] Referring to FIG. 1b, the data stream 10 illustrated in FIG. 1ais evaluated in a contiguous order and the resultant data stream 20 is typically blocked into groups of bytes such as, block 22. For example, the first row of the binary code image is analyzed and blocked into blocks of eight bytes. This process continues until all of the rows have been evaluated. However, when analyzing the data stream in a contiguous order, there are few block to block matches found since the operands and the operation codes are mixed together to represent the binary code image.

[0026] FIG. 1c, illustrates the data stream 10 represented in FIG. 1aevaluated in a columnar order and separated into blocks of bytes. In a preferred embodiment of the present invention, the operation codes are grouped preferably with other operation codes and the operands are grouped preferably with other operands. By parsing the data in a columnar format there are characteristically more block to block matches, increasing the compression ratio. Furthermore, the data is parsed into data stream portions where a data stream portion 32 is formed from columns preferably in-groups of three. That is, the first column and the fourth column may make up one data stream portion 32, the second column and the fifth column may make up a second data stream portion 34, and the third column and the sixth column may make up a third data stream portion 36. By formatting and arranging the data in this way, the three data stream portions 32, 34, 36 may be processed in parallel by the system and method for compressing and decompressing a binary code image as described in further detail hereinafter. A greater or lesser number of data stream portions may be used depending on the size of memory or the available size of the image being processed.

[0027] FIG. 2 illustrates a top-level flow diagram of the system and method 50 for compressing and decompressing a binary code image in accordance with the present invention. To save storage space or to provide an efficient method to transmit large image files over a network, a binary code image is preferably sent to the system of the present invention that compresses the file into a more compact form. The system and method 50 shown in FIG. 2 may be applied to a device, for instance, in which executable software images referred to as binary code images are preferably used, such as the memory image 10 shown in FIG. 1a. The present invention may be suitably employed to transmit signals over networks, such as Local Area Networks (LAN), Metropolitan Area Networks (MAN), Wide Area Networks (WAN), Personal Area Networks (PAN) and circuit switched networks, for example, or direct end-to-end connections, as well as with other transmission protocols.

[0028] The operating environment for the system to compress and decompress a binary code image of the present invention includes a processing system with at least one Central Processing Unit (CPU) and maybe a memory system. In accordance with the practices of persons skilled in the art of computer programming, the present invention is being described with reference to acts and symbolic representations of operations that are performed by the processing system, unless indicated otherwise. Such acts and operations are sometimes referred to as being “computer-executed”, or “CPU executed.”

[0029] It will be appreciated that the acts and symbolically represented operations include the manipulation of electrical signals by the CPU. An electrical system with data bits causes a resulting transformation or reduction of the electrical signal representation, and the maintenance of data bits at memory locations in the memory system to thereby reconfigure or otherwise after the CPU's operation, as well as other processing of signals. The memory locations where data bits are maintained are physical locations that have particular electrical, magnetic, optical, or organic properties corresponding to the data bits.

[0030] The data bits may also be maintained on a computer readable medium including magnetic disks, optical disks, organic disks, and any other volatile or non-volatile mass storage system readable by the CPU. The computer readable medium includes cooperating or interconnected computer readable media, which exist exclusively on the processing system or is distributed among multiple interconnected processing systems that may be local or remote to the processing system.

[0031] The system and method for compressing and decompressing a binary code images in accordance with the present invention includes a preprocessing step 52 once the binary code image is received. The preprocessing step 52 includes evaluating the raw data to determine the length of raw data, memory required for a table, number of and width of columns required, construction and outputting of a header, division of memory into a number of columns, selection of a hash function based on memory size and initializing of the compression table memory.

[0032] The method 50 further includes the step 54 of compressing the processed image using a first processor that provides a compression function that results in a compressed image. Further, the compressed image is transferred per step 56 to a memory storage device or a transmission channel. The method further includes the step 58 of decompressing the compressed image using a second processor that provides a decompression function.

[0033] In a preferred embodiment, the first processor performs the compression function, per step 54, preferably by processing the memory image 10 in parallel. The output of the compression function, the compressed data, is transferred into a storage device or a transmission channel. The storage device may include any device in which the digitally compressed data may be stored in such as, for example, but not limited to, a random access memory (“RAM”), a buffer, and an electrically erasable programmable read-only memory (“EEPROM”). The transmission channel may include, but is not limited to, a data bus internal to a computer or processor, a telephone line, a cable, and may include electromagnetic transmission such as radio frequency or infrared transmission. The second processor receives the compressed image from the transmission channel, usually through an interface internal to a computer or an interface external to a computer such as any LAN device, a cable modem or Digital Subscriber Line (DSL) modem and performs a decompression function on the compressed image per step 58. The resultant decompressed image may be viewed, stored, or further processed.

[0034] FIG. 3 illustrates a flowchart of a method 80 for compressing data in accordance with a preferred embodiment of the present invention. At step 82, the setup or preprocessing process preferably includes initialization of a memory storage device, initialization of the image data, and preprocessing of the image data. The setup process per step 82 retrieves the binary code image from either a memory storage unit, a buffer, a transmission channel, or from any device connected to the preprocessor and having an uncompressed binary code image therein. Once the image is retrieved the step 82 of setup may generate a header to be stored with the resultant compressed data. The header preferably contains information that may be used to decompress the data, such as, for example, image size including the number of columns of data and the size, such as, the width of the data columns. Setup preferably initializes the compression table memory, selects a hash function, and divides available compression memory according to a number of columns of data.

[0035] FIG. 4 is a listing of exemplary instructions that pertain to the setup process in accordance with a preferred embodiment of preprocessing the binary code image in accordance with the present invention.

[0036] Referring back to FIGS. 1aand 1c, the data is separated into data stream portions for example, data streams portions 32, 34, 36. The binary code image data is divided into a prescribed number of columns, preferably in-groups of three. That is, the first column and the fourth column may make up one data stream portion, the second column and the fifth column may make up a second data stream portion, and the third column and the sixth column may make up a third data stream portion and so on. Each data stream portion, is made up of multiple columns as illustrated in the three data stream portions shown in FIG. 1c, and is grouped into blocks of bytes, preferably having 7 bytes in one block. The creation of multiple data stream portions facilitates the processing of the multiple data stream portions in parallel by the compression process in accordance with the present invention. A greater or lesser number of data stream portions may be used depending on the size of the memory or the size of the image being processed. Parallel processing involves the processor reading the first byte of each data stream portion concurrently. The compression function then processes the first byte of each data stream portion simultaneously until the image data is compressed. Thus, the compression function preferably reads N data bytes, where N refers to the number of data stream portions that are available for processing. In FIG. 1c, there are three data stream portions 32, 34, 36 illustrated although more or less number of data stream portions may be used.

[0037] The compression function preferably performs predictive compression by creating a table, such as, the compression table preferably initialized by the setup process in step 82. In lossless or reversible compression, the task of modeling is typically split into two steps. In the first step, a predictive compression model is used to predict binary code values and replace them by the error in the prediction. If prediction is based on previously transmitted values, then knowing the prediction error and the prediction scheme, the receiver can recover the value of the original binary code. In the second step, a prediction error model is constructed, which is used to drive a variable length coder for encoding prediction errors.

[0038] The compression table includes hash values based upon the hash of previous characters, such as, previous characters that may include previous blocks of image data that have been processed. A hashing function is a transformation that maps an identifier to a numerical value. Hashing is used to convert an identifier or key, meaningful to a user, into a value for the location of the corresponding data in a structure, such as the compression table. The compression function then preferably groups the information bytes (i.e., bytes containing binary code image data) with an assigned flag byte wherein the flag byte preferably precedes the information data. Each bit of the flag byte corresponds to one byte of the seven bytes of information data to provide the decompression function with necessary information for reconstructing the data into the image. A greater or lesser number of information bytes and flag bytes may be used to accommodate larger or smaller blocks of data in accordance with the present invention.

[0039] For example, referring back to the flowchart illustrated in FIG. 3, the first byte of each data stream is read by the compression function and compared to the table referred to as the compression table per step 84. A data byte match is determined per step 86. If the hash value of the first byte of information data is not present in the compression table per step 88, then the hash value is placed into the compression table, a corresponding bit in the flag byte is set to logic 0 and the first byte is output to the transmission channel. If the hash value of the first byte is present in the compression table, for example, the compression function has processed this particular hash value before, then the corresponding flag bit is set to logic 1 per step 90, and the byte is not output to the transmission channel. Thus, the flag byte is made up of logic 1's and logic 0's depending on if the corresponding information byte has been processed before or not. The compression function processes each byte of information data until the length of each data stream portion has expired as determined per step 92, whereupon the compression function is completed.

[0040] An exemplary listing of the instructions to perform the compression function in a first processor in accordance with a preferred embodiment is shown in FIG. 5. There are many different compression models and codes and corresponding hash functions known in the art that may be used to hash the binary code image data in accordance with the present invention. The compression function may create a hash value by utilizing codes such as, but not limited to, all the Huffman codes such as, the adaptive Huffman code; Golomb code; Rice code; and all Ziv-Lempel (LZ) codes or all the LZW codes. The hash function may be chosen so as to tailor the function to the specific binary code image data. Particular coding schemes such as the Huffman codes may utilize a pre-defined encoding table that remain the same regardless of the information being compressed. A pre-defined encoding table may assist the compression and decompression functions to agree on the binary codes used to represent each character or group of characters.

[0041] An exemplary data stream that may be compressed using the system and the method of the present invention may be represented as follows:

[0042] 4141 4141 4141 41 4141 4141 4141 41

[0043] 4141 4141 4141 41 4141 4141 4141 41

[0044] 4142 4142 4142 41 4241 4241 4241 42

[0045] 7878 7878 7878 78

[0046] Compressing the above binary code image data using the system and method of the present invention outputs the following:

[0047] 604141414141 604141414141 6f41 6f41 414241424142 604241424142 607878787878

[0048] wherein,

[0049] flag=0x60−2 bytes (5 and 6) in this block were guessed correctly.

[0050] File: 4141414141

[0051] Compression table: 4141

[0052] flag=0x60−2 bytes (5 and 6) in this block were guessed correctly.

[0053] File: 4141414141

[0054] Compression table: 4141

[0055] flag=0x6f−6 bytes (0-3, 5 and 6) in this block were guessed correctly.

[0056] File: 41

[0057] Compression table: 41414141 4141

[0058] flag=0x6f−6 bytes (0-3, 5 and 6) in this block were guessed correctly.

[0059] File: 41

[0060] Compression table: 41414141 4141

[0061] flag=0x41−2 bytes (0 and 6) in this block were guessed correctly.

[0062] File: 4241424142

[0063] Compression table: 4142

[0064] flag=0x60−2 bytes (5 and 6) in this block were guessed correctly.

[0065] File: 4241424142

[0066] Compression table: 4142

[0067] flag=0x60−2 bytes (5 and 6) in this block were guessed correctly.

[0068] File: 7878787878

[0069] Compression table: 7878

[0070] FIG. 6 illustrates a flowchart of a preferred embodiment of a method 170 for decompressing an image in accordance with the present invention. The step of setup 172 preferably includes initialization of a memory storage device, initialization of the compressed image data, and preprocessing of the image data. The step of setup 172 retrieves the compressed binary code image from either a memory storage unit, a buffer, a transmission channel, or from any device connected to the processor executing the decompression function. Once the compressed image is retrieved, the step of setup 172 may utilize a header preferably generated by the compression function. The header contains information used to decompress the compressed data such as the original image size including the number of columns of data and the size of the data columns. The step of setup 172 preferably initializes a decompression table memory (decompression table), selects a hash function based upon the table memory size, and divides available decompression memory according to the number of columns of data.

[0071] After the data has been processed in step 172, it is ready to be decompressed to reconstruct the contiguous data. The decompression function reads the flag byte of the first data block per step 174. The method 170 then, determines if a flag bit is set per step 176. If the flag bit is set (i.e., equal to logic 1), then the decompression function places the hash value into decompression table and outputs the data per step 178. The decompression function processes each byte of information data until the length of each data stream portion has expired as determined per step 180. If the flag bit is not set (i.e., equal to logic 0), then the decompression function outputs the data directly per step 182. After the first block has been processed, the decompression function moves to the next block and examines the flag byte, thus repeating the process again. It should be noted that similar to the compression function, decompression of different data stream portions of the compressed image may occur in parallel. The decompression function reads the flag byte and processes the data blocks accordingly until the last flag byte is read whereupon the decompression function checks for left over data referred to as residual data per step 184. Residual data maybe defined as data that has a lesser number than the number of prescribed bytes, such as, for example, less than 7 bytes in a preferred embodiment. If residual data exists, the decompression function outputs the residual data per step 186. FIG. 7 is an exemplary listing of instructions to perform the decompression function in accordance with a preferred embodiment of the present invention.

[0072] The theoretical maximum compression ratio achieved using the system and method for compressing and decompressing a binary code image in accordance with the present invention is 8:1. The system and method of the present invention yields better compression ratios when used with Reduced Instruction Set Computers (RISC) which are microprocessors that are designed to perform a smaller number of types of computer instructions so that they can operate at a higher speed. The lesser the number of instructions, the greater is the probability of finding a match in the columns of image data.

[0073] It should be understood that the programs, processes, methods and systems described herein are not related or limited to any particular type of computer or network system (hardware or software), unless indicated otherwise. Various types of general purpose or specialized computer systems may be used with or perform operations in accordance with the teachings described herein.

[0074] In view of the wide variety of embodiments to which the principles of the present invention can be applied, it should be understood that the illustrated embodiments are exemplary only, and should not be taken as limiting the scope of the present invention. For example, the steps of the flow diagrams may be taken in sequences other than those described, and more or fewer elements may be used in the block diagrams. While various elements of the preferred embodiments have been described as being implemented in software, in other embodiments in hardware or firmware implementations may alternatively be used, and vice-versa.

[0075] It will be apparent to those of ordinary skill in the art that methods involved in the system and method for compressing and decompressing a binary code image may be embodied in a computer program product that includes a computer usable medium. For example, such as, a computer usable medium can include a readable memory device, such as a hard drive device, CD-ROM, a DVD-ROM, or a computer diskette, having computer readable program code segments stored thereon. The computer readable medium can also include a communications or transmission medium, such as, a bus or a communication link, either optical, wired or wireless having program code segments carried thereon as digital or analog data signals.

[0076] The claims should not be read as limited to the described order or elements unless stated to that effect. Therefore, all embodiments that come within the scope and spirit of the following claims and equivalents thereto are claimed as the invention.