JPH08139610A - Device and method for compressing program - Google Patents

Abstract

PURPOSE: To provide a program compressor which can improve compressibility by dividing data to be compressed into prescribed constitutive units and performing entropy compression with the plural prescribed constitutive units as one symbol. CONSTITUTION: Since an instruction code and an address code are contained in one word length of the object code of a program, when one word length of the object code is divided into the prescribed constitutive units such as byte units, for example, there is fixed correlation between the divided data. Therefore, with the plural pieces of divided data as one symbol, the data of 16 bits are divided into the data of preceding 8 bits and the data of following 8 bits, for example, and converted into a pattern (a, b) (symbol) composed of a value (a) shown by the data of preceding 8 bits and a value (b) shown by the data of following 8 bits and entropy compression is performed to that pattern. Thus, the correlation between data is stereotyped to the fixed pattern so that the compressibility can be considerably improved.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a program compressing apparatus and a program compressing method capable of improving the compression rate in compressing program data and the like.

[0002]

2. Description of the Related Art Generally, a Huffman table 204 is created in advance using the program data 200, and FIG. 28 is a flowchart showing a method for creating the Huffman table 204. In the prior art, as shown in FIG.
The bit is taken out and input to the data counter 201. The data counter 201 counts the number of appearances of the input data, and outputs the result as a count result 202. The Huffman table generator 203 generates and outputs the Huffman table 204 in a state in which a shorter code is assigned to a value having a larger count number in the count result 202.

Next, a compression method will be described. FIG. 29
2 is a flowchart showing a conventional compression method.
The Huffman table 204 in FIG. 9 is created by the method shown in FIG. At the time of conventional compression, FIG.
As shown in FIG. 9, first, 8 bits are sequentially extracted from the program data 200 and input to the Huffman encoder 205. The Huffman encoder 205 refers to the data in the Huffman table 204 and outputs the Huffman code assigned to the input value as compressed data 206.

[0004]

By the way, in a general program such as C language, an object code set according to a certain rule (grammar) is usually used. Here, in the conventional compression method shown in FIGS. 28 to 29, the object code of the program is divided into fixed-length data, and the divided data is entropy-compressed as one symbol. That is, since the compression was performed without using the correlation between the divided data, if this was uniformly processed and the Markov model was set, the data distribution would be averaged and a characteristic Markov model could be formed. become unable. For this reason, the data appearance frequency (appearance probability) becomes a low level, and efficient decoding may not be possible during decoding.

In view of the above problems, it is an object of the present invention to provide a program compression device and a program compression method that can improve the compression rate.

[0006]

The problem solving means according to claim 1 of the present invention compresses an object code of a program including an instruction code and an address code, and compresses data to be compressed into a predetermined constituent unit. And conversion means for converting the plurality of predetermined constituent units into one symbol, and compression means for entropy-compressing the symbols.

The problem solving means according to claim 2 of the present invention is
A first object compression method for compressing an object code of a program including an instruction code and an address code, wherein the data to be compressed is divided into first block data of one word length
Dividing means for dividing the first block data into second block data of a predetermined constituent unit, and outputting a plurality of the second block data as a vector, and the vector Vector quantizing means for quantizing a representative vector appropriately selected from a predetermined codebook and outputting the representative vector, and outputting an index corresponding to the representative vector as one component of compressed data; Vector difference means for calculating the difference between the output of the dividing means and the representative vector and outputting it as another component of the compressed data.

The problem solving means according to claim 3 of the present invention is
A method for compressing an object code of a program including an instruction code and an address code, wherein a dividing means for dividing data to be compressed into block data of a predetermined structural unit and a correlation between the block data are analyzed beforehand. Prediction means for outputting a data prediction value based on the prediction table created in, the block data, and calculates the difference between the data prediction value corresponding to the block data, the index corresponding to the data prediction value And a difference unit that outputs the difference as a component of the compressed data.

The problem solving means according to claim 4 of the present invention is
The method includes a conversion step of dividing an object code of a program including an instruction code and an address code into predetermined constituent units, converting the plurality of predetermined constituent units into one symbol, and a compression step of entropy-compressing the symbols. .

The problem solving means according to claim 5 of the present invention is
A first dividing step of dividing an object code of a program including an instruction code and an address code into first block data of one word length, and dividing the first block data into second block data of a predetermined structural unit A second dividing step of outputting a plurality of the second block data as a vector, quantizing the vector into a representative vector appropriately selected from a predetermined codebook, and outputting the representative vector, and A vector quantization step of outputting an index corresponding to a representative vector as one component of compressed data, and a difference between the output of the second division step and the representative vector is calculated and output as another component of compressed data. And a vector subtraction step.

The problem solving means according to claim 6 of the present invention is
A data prediction value based on a dividing step of dividing an object code of a program including an instruction code and an address code into block data of a predetermined structural unit, and a prediction table created in advance by analyzing correlation between the block data. And a difference between the block data and the data prediction value corresponding to the block data is calculated, and the index and the difference corresponding to the data prediction value are combined as a constituent element of compressed data. And a difference step of outputting.

[0012]

In the program compression apparatus and the program compression method according to claim 4 of the present invention, since one word length of the object code of the program includes the instruction code and the address code, the object code 1
When the word length is divided into predetermined constituent units such as byte units, there is a certain correlation between the divided data. Therefore, if a plurality of pieces of divided data are entropy-compressed as one symbol, the correlation between the data is classified into a certain pattern, so that the compression rate can be dramatically improved.

In the program compressing apparatus and the program compressing method according to claim 5 of the present invention, since one word length of the object code of the program includes the instruction code and the address code, the object code 1 When the word length is divided into predetermined constituent units such as byte units and the divided data is quantized into a vector, the vector is not uniformly distributed in the vector space, but has a biased distribution. Therefore, the compression ratio can be dramatically improved by quantizing the vector into the biased center of gravity vector and using the data indicating the center of gravity vector and the quantization error as the compressed data.

In the program compressing apparatus and the program compressing method according to claim 6 of the present invention, since one word length of the object code of the program is composed of an instruction code and an address code, one word of the object code When the length is divided into predetermined constituent units such as byte units, there is a correlation between the divided data. Therefore, another divided data can be predicted from one divided data with a very high probability, and the compression error can be dramatically improved by entropy compressing the prediction error.

[0015]

【Example】

{First Embodiment} <Structure> FIG. 1 is a functional block diagram showing a program compression apparatus according to a first embodiment of the present invention. The program compression apparatus according to the present embodiment adjusts the number of bits of the last data of the program data 10, and a converter 12 that outputs the data from the file end adjuster 11 by dividing the data into two parts. (Conversion means) and a Huffman encoder 13 (compression means) for entropy-compressing the output data from the converter 12 with reference to the Huffman table 14.

The file end adjuster 11 outputs the input 16-bit data as it is until the program data 10 reaches the file end.

The converter 12 is a file end adjuster 1.
16-bit data output from 1 is divided into front 8-bit data and rear 8-bit data, and a pattern (a, b) (symbol) composed of a value a indicated by the front 8-bit data and a value b indicated by the rear 8-bit data And output it. Note that a and b are integers in the range of 0 to 255, respectively, and the same applies to a and b described below.

The Huffman table 14 in FIG. 1 is created in advance as shown in FIG. 2 using the program data 10. The program data 30 in FIG. 2 is the same as the program data 10 in FIG. Also, 31
Is a file end adjuster for adjusting the number of bits of the last data of the program data 30 and is similar to the file end adjuster 11, but has an additional bit number 35.
Is different from the file end adjuster 11 described above. Reference numeral 32 denotes a converter that outputs the data from the file end adjuster 31 by dividing the data into two parts before and after, and is the same as the converter 12. And 33 is the converter 3
2 is a pattern counter for counting the number of appearances of the patterns output from 2, and 36 is a Huffman table generator that outputs a list of correspondences between patterns and their Huffman codes as a Huffman table 37 based on the count result 34 from the pattern counter 33. is there.

Next, a decoding unit for decoding the compressed data will be described with reference to FIG. The Huffman table 24 and the compressed data 26 in FIG. 3 are the same as the Huffman table 14 and the compressed data 15 in FIG. 1, respectively. The additional bit number 25 in FIG. 3 is the same as the additional bit number 35 in FIG. Reference numeral 23 in FIG. 3 denotes a Huffman decoder that outputs a pattern (a, b) to which the Huffman code is assigned when the data from the compressed data 26 matches the Huffman code of the Huffman table 24, and 22 outputs from the Huffman decoder 23. Pattern (a, b)
An inverse converter for outputting a single data by combining the elements a and b of the above, and a file end adjuster 21 for adjusting the number of bits of the last data.

<Huffman Table Creating Method> As shown in FIG. 2, when creating the Huffman table 37, first, 16 bits from the beginning of the program data 30 are extracted and input to the file end adjuster 31. At this time, the input 16-bit data is output as it is until the program data 30 reaches the file end.

The converter 32 divides the 16-bit data input from the file end adjuster 31 into front 8 bits and rear 8 bits, and a pattern composed of a value a indicated by the front 8 bit data and a value b indicated by the rear 8 bit data. It is converted into (a, b) and output. FIG. 4 shows the relationship between 16-bit data and pattern (a, b).

The pattern (a,
In b), the number of appearances is counted by the pattern counter 33. From the above program data 30 to the pattern counter 3 until no data remains in the program data 30.
Repeat the process up to 3.

However, the final data of the program data 30 is adjusted in the number of bits by the file end adjuster 31. That is, when the final data input from the program data 30 to the file end adjuster 31 is less than 16 bits, the file end adjuster 31 outputs 16 bits.
Bit data having a value of "0" is added and output after the data that has been input so as to be bits is insufficient. Then, the number of added bit data of “0” value is output as the additional bit number 35. FIG. 5 shows data output from the file end adjuster 31 when the final data D1 of the program data 30 is 11 bits. D2 in FIG.
Indicates the data to be added, and the final data D1 is 1
Since it is 1 bit, "0" is set to 16 bits
Five bit data of value are added. in this case,
The value output by the file end adjuster 31 as the additional bit number 35 is "5". If the final data of the program data 30 is 16, the file end adjuster 31 converts the input 16 bits of the final data as it is to the converter 32.
And outputs the value “0” as the additional bit number 35.

In this way, all the data of the program data 30 is converted into the file end adjuster 31 and the converter 3.
After being counted by the pattern counter 33 through 2,
The pattern counter 33 outputs the counted result as the count result 34.

When the count result 34 is input to the Huffman table generator 36, the Huffman table generator 36 outputs a list of correspondences between the patterns (a, b) and the Huffman codes as a Huffman table 37. At this time, the Huffman code is not generated for the pattern that has not been counted even once by the pattern counter 33.

<Compression Method> Next, the compression method in this embodiment will be described with reference to FIG. The Huffman table 14 in FIG. 1 is a Huffman table created by the above Huffman table creating operation. First, 16 bits are extracted from the program data 10 and input to the file end adjuster 11. The file end adjuster 11 outputs the input 16-bit data as it is until the program data 10 reaches the file end.

Next, the converter 12 divides the 16-bit data output from the file end adjuster 11 into front 8-bit data and rear 8-bit data, and the value a indicated by the front 8-bit data and the rear 8-bit data are divided. The pattern (a, b) having the indicated value b is converted and output.

The pattern (a,
b) is input to the Huffman encoder 13. The Huffman encoder 13 refers to the Huffman table 14 and outputs the Huffman code assigned to the input pattern (a, b) as compressed data. Huffman encoder 1
The Huffman code output from 3 is compressed data 15 in sequence.
Becomes

The above process is repeated until the program data 10 reaches the file end. However, the final data of the program data 10 is adjusted in the number of bits by the file end adjuster 11. That is, when the final data of the program data 10 is less than 16 bits, the file end adjuster 11 adjusts the data length to 16 bits by adding bit data of "0" value after the input final data. And output. The final data output from the file end adjuster 11 becomes the compressed data 15 via the converter 12 and the Huffman encoder 13 as described above. This is the end of the compression process.

<Decoding Method> Next, the decoding method of the data compressed by the above compression method will be described with reference to FIG. First, the Huffman decoder 23 sequentially extracts the compressed data 26 and checks whether or not there is a matching Huffman code in the Huffman table 24. If a matching Huffman code is found, the pattern (a, b) to which the Huffman code is assigned is output. The pattern (a, b) output from the decoder 23 is converted into 8-bit data by a and b by the inverse converter 22, and 16-bit data is output in total. The relationship between the pattern (a, b) and 16-bit data at this time is as shown in FIG. The 16-bit data output from the inverse converter 22 is input to the file end adjuster 21 as shown in FIG.

The file end adjuster 21 does not do anything if the input data is not the last data.
6-bit data is output as it is. The 16-bit data output from the file end adjuster 21 becomes the decoded data 20 sequentially. The above process is repeated until there is no data in the compressed data 26.

On the other hand, when the last data is input to the file end adjuster 21, the file end adjuster 21 adds 25 additional bits from the end of the input 16-bit data.
The number of bits given by is deleted and output. When the value of the additional bit number 25 is "0", the input 16-bit data is output as it is. In this way, the final data output from the file end adjuster 21 is the decoded data 2
It becomes 0, and the decoding process ends.

{Second Embodiment} <Structure> FIG. 6 is a functional block diagram showing a program compression apparatus according to a second embodiment of the present invention. Reference numeral 41 in FIG. 6 is a file end adjuster (first dividing means) for repeatedly taking out a predetermined number of bits of data from the program data 40 and adjusting the bit number of the last data, and 42 is output from the file end adjuster 41. A vector generator (second dividing means) that divides the data into four to generate and outputs a four-dimensional vector, 44 is a codebook for the input vector
, A vector quantizer (vector quantizing means) for quantizing into a quantized representative vector, 43 is a four-dimensional vector component which is an input from the vector generator 42, and a quantizer which is an input from the vector quantizer 44. A residual calculator (vector that calculates the error of four types of components (first component, second component, third component, and fourth component) of two vectors from the components of the representative vector to generate compressed data. Difference means).

The file end adjuster 41 outputs the input 16-bit data as it is until the program data 10 reaches the file end.

The vector generator 42 divides the 32-bit data output from the file end adjuster 41 into 8-bit data as shown in FIG. 7, and divides the 4-bit divided 8-bit data into components. Generates and outputs a four-dimensional vector.

The residual calculator 43 is configured to output, as compressed data, a quantization error generated when a four-dimensional vector generated from 32 bits of program data is quantized by the vector quantizer 44 into a quantized representative vector. To be done.

The codebook 45 shown in FIG. 6 is used for vector quantization, and is composed of 256 four-dimensional vectors and indexes corresponding to each of them, as shown in FIG. There is. D3 in FIG. 8 indicates a component of a four-dimensional vector. The code book 45 is created in advance using program data to be compressed,
The program data 60 in FIG. 9 is the same as the program data 40 in FIG. Further, 61 in FIG. 9 is a file end adjuster which adjusts the last data number of the program data and outputs an additional bit number 65, and 62 is a four-dimensional division of the data output from the file end adjuster 61 into four. A vector generator that generates a learning sequence 63 of vectors, and a codebook generator 64 that inputs the learning sequence 63 and generates a codebook 66 suitable for the learning sequence 63.

FIG. 10 is a diagram showing the decoding process of this embodiment. Codebook 56 and compressed data 5 in FIG.
7 is the same as the codebook 45 and the compressed data 46 in FIG. 6, and the number of additional bits 55 is the same as the number of additional bits 65 in FIG. Furthermore, 5 in FIG.
4 is a vector dequantizer that searches the codebook 56 for an index that matches the input data, and sends the quantized representative vector of the index to a residual adder 53, which will be described later. A residual adder that divides and generates a four-dimensional vector (residual) and adds the value from the vector dequantizer 54 to it, 52 represents the four-dimensional vector output from the residual adder 53 into one data A converter 51 for converting is a file end adjuster for adjusting the number of bits of data at the file end of the compressed data 57.

<Codebook Generation Method> At the time of codebook generation, as shown in FIG. 9, first, 32-bit data is extracted from the program data 60 and input to the file end adjuster 61. The file end adjuster 61 outputs the input 32-bit data as it is until the program data reaches the file end. The vector generator 62 divides the 32-bit data output from the file end adjuster 61 into four 8-bit data as shown in FIG. 7, and generates a four-dimensional vector having the four 8-bit data as four components. To generate. FIG. 11 shows the correspondence between the 32-bit data input to the vector generator 62 and the vector components generated from the 32-bit data.

The four-dimensional vector output from the vector generator 62 sequentially becomes the learning series 63, and the process from the program data 60 to the learning series 63 is repeated until the program data 60 has no data. However, at the file end of the program data 60, the file end adjuster 61 adjusts the number of output data. That is, when the final data of the program data 60 input to the file end adjuster 61 is less than 32 bits,
The file end adjuster 61 adds bit data having a value of "0" after the input data and outputs the bit data so that the output becomes 32-bit data. Further, the number of "0" value bits added at that time is output as the additional bit number 65. When the final data of the program data 60 is 32 bits, the file end adjuster 61 outputs the input 32-bit data as it is, and outputs the value “0” as the additional bit number 65. FIG. 12 shows the data output from the file end adjuster 61 when the final data D4 extracted from the program data 60 is 24 bits. D5 in FIG. 12 indicates the data to be added. Since the final data D4 is 24 bits, 8 bit data of "0" value are added to make the total 32 bits.

The final data of 32 bits output from the file end adjuster 61 becomes a learning sequence 63 via the vector generator 62 as described above. The learning sequence 63 thus generated is a set of four-dimensional vectors. The codebook generator 64 generates a codebook 66 suitable for the learning series 63 by analyzing the distribution of the learning series 63 in the four-dimensional vector space.

<Compression Method> Next, the compression method of this embodiment will be described. As shown in FIG. 6, first, the program data 4
The 32-bit data from 0 is taken out and input to the file end adjuster 41. The file end adjuster 41 is similar to the file end adjuster 61 of FIG. 9, but does not output the number of additional bits. The file end adjuster 41 outputs the input 32-bit data as it is until the program data 40 reaches the file end. The vector generator 42 of FIG. 6 divides the 32-bit data output from the file end adjuster 41 into 8-bit data as shown in FIG. 7, and divides the 4-bit divided 8-bit data into four components. Generates and outputs a dimension vector. The four-dimensional vector output from the vector generator is input to the vector quantizer 44 and the residual calculator 43. The vector quantizer 44 quantizes the input vector into a quantized representative vector selected from the codebook 45 by a method described later.

Next, a method of selecting the quantized representative vector will be described. First, the distortion amount given by the following mathematical expression (Equation 1) is calculated from the quantized representative vector and the input vector at the index “0” of the codebook shown in FIG. 8, and the value of the distortion amount and the index value “ Save 0 ".

[0044]

[Equation 1]

Next, the distortion amount given by the above mathematical expression (Equation 1) is calculated from the quantized representative vector at the index "1" and the input vector, and is compared with the stored distortion amount value. If the calculated strain amount value is smaller than the stored strain amount value, the stored strain amount value and index value are deleted, and the input vector and the index “1” are stored. The distortion amount value with the quantized representative vector and the index value “1” are newly stored. If the calculated strain value is equal to or greater than the stored strain value, do nothing. Similarly, the strain amount given by the above equation (Equation 1) is calculated from the quantized representative vector and the first vector at the index “2” in the same manner, and the calculated strain amount value is the stored strain amount value. If it is smaller than the above, the stored strain amount value and index value are deleted, and the calculated strain amount value and index value “2” are newly stored. If the calculated strain amount value is equal to or smaller than the stored strain amount value, nothing is done and the calculation of the strain amount value with the quantized representative vector at the next index is performed. The same applies to index "255" and so on.

When the calculation of the distortion amount of all the quantized representative vectors and the input vector of the codebook 45 of FIG. 6 is completed in this way, the stored distortion amount is among all the calculated distortion amounts. The smallest and stored index is the index of the quantized representative vector that gives the smallest amount of distortion. In this way, the vector quantizer 44 quantizes the input vector into the quantized representative vector selected by the above method, and outputs the quantized representative vector and its index. Since the index is an integer in the range of "0" to "255", it is output as 8-bit data. The quantized representative vector output from the vector quantizer 44 is input to the residual calculator 43. The residual calculator 43 receives the components of the four-dimensional vector, which is the input from the vector generator 42, and the vector quantizer 44.
The error of the first component, the error of the second component, the error of the third component, and the error of the fourth component of the two vectors are calculated from the components of the quantized representative vector which is the input from , A total of 20 bits are output as compressed data. That is, the residual calculator 43 outputs, as compressed data, a quantization error that occurs when the vector quantizer 44 quantizes a four-dimensional vector generated from 32 bits of program data into a quantized representative vector. The 32 bits of the program data 40 are compressed into 28 bits of data, which is the sum of the output of the vector quantizer 44 and the output of the residual calculator 43. 28 bits of this compressed data are shown in FIG.
8 bits (D8) from the beginning are output of the vector quantizer 44 (index of the quantized representative vector) as shown in FIG.
And the following 20 bits (4 × 5 bits: D9 to D1
2) is the output (quantization error) of the residual calculator 43. The 28 bits of compressed data become the compressed data 46 in sequence.

<Decoding Method> Next, a method of decoding the data compressed by the above compression method will be described. As shown in Figure 10,
First, extract 28-bit data from compressed data 57,
The 8-bit data from the beginning is input to the vector dequantizer 54, and the remaining 20-bit data is input to the residual adder 53. The residual adder 53 divides the input 20-bit data into 5-bit data and generates a 4-dimensional vector having four 5-bit data as four components.

The vector dequantizer 54 uses the codebook 5
An index that matches the input 8-bit data is searched from 6 and the quantized representative vector of the index is sent to the residual adder 53. The residual adder 53 adds the four-dimensional vector generated from the compressed data and the four-dimensional vector which is the input from the vector dequantizer 54, and outputs the result. The four-dimensional vector output from the residual adder 53 is converted into 32-bit data by the converter 52 as shown in FIG.

The file end adjuster 51 uses the compressed data 5
The number of bits of data is adjusted at the file end of 7 and the input from the converter is made at other than the file end.
2-bit data is output as it is. 32 bits output from the file end adjuster 51 are sequentially decoded data 50
Becomes In the decoding process of the last 28 bits of the compressed data 57, the file end adjuster 51 inputs 32
The bit number given by the additional bit number 55 is deleted from the end of the bit data and output. This completes the decoding process.

{Third Embodiment} <Structure> FIG. 15 is a functional block diagram showing a program compression apparatus according to a third embodiment of the present invention. In this embodiment, the data previously input to the counter 91 (see FIG. 17) described later is referred to as current data, and the data input next to the current data is referred to as next data.
Reference numeral 71 in FIG. 15 is a predictor (prediction means) that searches for current data that is equal to the data in the prediction table 75 and outputs a predicted value corresponding to the current data, and 72 is the value of the program data 70 and the predicted value of the predictor 71. , A run length converter for converting the data output from the subtractor 72 into a predetermined run length pattern (see FIG. 16), and 74 an input run length pattern. Is a Huffman encoder, and the other part is encoded into data of a predetermined bit. In addition,
Each of the predictor 71 and the subtractor 72 functions as a dividing unit that takes out (data divides) the data of the program data 70 as 8-bit block data. That is, the predictor 71 of this embodiment has both the functions of the predicting means and the dividing means, and the subtractor 72 has both the functions of the difference means and the dividing means.

Here, the prediction table 75 shown in FIG.
The Huffman table 76 is created in advance using the program data 70 as shown in FIGS. 17 and 18. The program data 90 of FIG. 17 is shown in FIG.
Is the same as the program data 70. Reference numeral 91 in FIG. 17 is a counter for counting the value of the next input next data with respect to the previously input current data, and 93 is the most appearance for each current data based on the count result 92 of the counter 91. It is a prediction table generator that selects one frequently-used next data and sets respective prediction values.

Further, FIG. 18 is a diagram showing a process of creating a Huffman table. Program data 1 of FIG.
00 is the same as the program data 70 of FIG. 15, and the prediction table 106 of FIG. 18 is created by the above method. Reference numeral 101 in FIG. 18 is the prediction table 10.
It is a predictor that searches for the same as the data of the program data 100 out of the current data of 6 and outputs the predicted value corresponding to it, and has the same function as the predictor 71 in FIG. Reference numeral 102 denotes a subtracter that outputs the difference between the value from the program data 100 and the predicted value from the predictor 101, and has the same function as the subtractor 72 in FIG. 103 is a run length converter that converts the data output from the subtractor 102 into a predetermined run length pattern (see FIG. 19), and 104 is a counter that counts the number of appearances of the run length pattern output from the run length converter 103. , 105 are Huffman table generators that generate shorter Huffman codes for run-length patterns having a larger number of counts of the input count results and output a list of correspondences between run-length patterns and Huffman codes as a Huffman table 107.

Furthermore, FIG. 20 is a diagram showing the decoding process of this embodiment. The prediction table 85, the Huffman table 86, and the compressed data 87 in FIG. 20 are the same as the prediction table 75, the Huffman table 76, and the compressed data 77 in FIG. 15, respectively. Reference numeral 84 is a Huffman decoder that decodes the compressed data 87 into a predetermined run length pattern when the Huffman table 86 matches the Huffman code. Reference numeral 83 is a predetermined run length pattern output from the Huffman decoder 84. An inverse converter for converting into a predetermined data sequence and outputting one data at a time, 81 is a prediction table 8
A predictor that searches for a current data equal to the input data from 5 and outputs a prediction value corresponding to the current data. Reference numeral 82 adds and outputs the input from the inverse converter 83 and the input from the predictor 81. It is an adder.

<Method of Creating Prediction Table> Next, a method of creating the prediction table 75 will be described with reference to FIG. First, 8 bits of the program data 90 are input to the counter 91. Then counter 9 again
Input 8 bits of the program data 90 to 1. The counter 91 counts the value of the next input next data with respect to the previously input current data in the count table shown in FIG. The values in the vertical direction of the count table in FIG. 21 represent the values of the current data, and the values in the horizontal direction represent the values of the next data.

Subsequently, when 8-bit data as program data 90 is input to the counter 91, the counter 91 erases the previous value of the current data, and instead uses the value of the next data as the current data, and the newly input value. Is the next data. Then, the value of the next data for the current data is counted in the count table of FIG. Further, when 8-bit data as the program data 90 is input to the counter 91, the counter 91 erases the current data in the same manner as described above, instead, the value of the next data is used as the current data, and the newly input data is used as the next data. , The value of the next data for the current data is counted in the count table of FIG. The above process is repeated until the program data 90 is empty.

When the program data 90 has no data, the counter 91 outputs the count result in the count table of FIG. 21 as the count result 92. The prediction table generator 93 reads the count result 92, first selects the next data with the largest count number from the next data of “0” to “255” for the current data “0”, and then the prediction table shown in FIG. Set to the predicted value corresponding to the current data 0. Next, the next data having the largest number of counts is selected from the next data of “0” to “255” for the current data “1” and set as the prediction value corresponding to the current data “1” of the prediction table of FIG. To do. Similarly, the prediction table of FIG. 22 is completed up to the current data “255”, and the prediction table 94 is obtained.

<Method of Creating Huffman Table> Next, a method of creating the Huffman table 76 will be described. FIG.
As shown in FIG. 8, first, 8-bit data of the program data 100 is taken out, and the predictor 101 and the subtractor 10
Enter 2.

The subtractor 102 outputs the first input data as it is. On the other hand, the predictor 101 searches the prediction table 106 for the current data equal to the input data, and outputs the prediction value corresponding to the current data. At this time, the next 8-bit data from the program data 100 is simultaneously input to the predictor 101 and the subtractor 102. The subtractor 102 outputs the difference between the value input from the program data 100 and the predicted value input from the predictor 101.

Similarly, the predictor 101 uses the prediction table 1
The current data that is equal to the input data is searched from 06, and the predicted value corresponding to the current data is output. At the same time, the next 8-bit data from the program data 100 is input to the predictor 101 and the subtractor 102. The subtractor 102 calculates and outputs the difference between the value input from the program data 100 and the value input from the predictor 101. The same applies until the program data 100 is empty.

The data output from the subtractor 102 is converted into a run length pattern described later by the run length converter 103. Run length pattern is continuous "0"
And the values that are not “0” that follow it are collectively represented as (n, g). Here, the variable n represents the number of consecutive "0" s, and the variable g represents the group number of a value which is not "0" following the consecutive "0" s. The group number is a numerical value given in the group number table of FIG.
The method of converting a data string into the above run length pattern will be described below. FIG. 19 shows, as an example, a data string and a data string converted into a run length pattern. The head data “12” of the data string in FIG. 19 has a run length pattern (0, 4) because there is no single “0” immediately before and the group number of 12 is 4.
In the subsequent data string “0, 0, 55”, the number of consecutive “0s” immediately before the value “55” which is not “0” is 2 and 5
Since the group number of 5 is 6, the run length pattern is (2, 6). The next data "-254" is
Since there is no 1 "0" consecutive immediately before, and the group number of -254 is 8, the run length pattern (0,
8). Similarly, the next data string “0, 3” is
Since there is one “0” immediately before the value “3” that is not “0” and the group number of 3 is 2, the run length pattern (1, 2) is obtained. In this way, the data string output from the subtractor 102 is sequentially converted into a run length pattern by the run length converter 103. However, subtracter 10
When the data string output from 2 ends with continuous "0" s, the continuous "0s" are collectively set as a run length pattern (0,0).

The run length pattern output from the run length converter 103 is input to the counter 104, and the number of appearances thereof is counted. Counter 10
When the count of all the run length patterns output from the run length converter 103 is completed, 4 sends the count result to the Huffman table generator 105.

The Huffman table generator 105 generates a shorter Huffman code for a run length pattern having a larger number of counts of the input count result, and outputs a list of correspondences between run length patterns and Huffman codes as a Huffman table 107.

<Compression Method> Next, the compression method will be described. FIG. 15 is a diagram showing a compression method. The prediction table 75 and the Huffman table 76 in FIG. 15 are created by the above-described method. First, the program data 70
The 8-bit data is taken out and input to the predictor 71 and the subtractor 72. The subtractor 72 outputs the first input data as it is. On the other hand, the predictor 71 searches the prediction table 75 for current data equal to the input data, and outputs a prediction value corresponding to the current data. At the same time, the next 8-bit data from the program data 70 is input to the predictor 71 and the subtractor 72. The subtractor 72 outputs the difference between the value input from the program data 70 and the predicted value input from the predictor 71. Next, similarly, the predictor 71 searches the prediction table 75 for current data equal to the input data, and outputs the prediction value corresponding to the current data. At the same time, the next 8-bit data from the program data 70 is input to the predictor 71 and the subtractor 72. The subtractor 72 uses the program data 70
The difference between the value input from and the value input from the predictor 71 is calculated and output. The same applies until the program data 70 is empty.

The data output from the subtractor 72 is converted into a run length pattern described later by the run length converter 73. The run length pattern is a combination of consecutive "0" and the following non- "0" values (n, g) "x".
It is expressed as. Here, the variable n represents the number of consecutive "0" s, the variable x represents a value that is not "0" following the consecutive "0" s, and the variable g represents the group number of the variable x described below. The same applies to the variables n, g, and x described in. The group number is a numerical value given in the group number table of FIG.

Next, a method of converting a data string into the above run length pattern will be described. FIG. 16 shows, as an example, a data string and a data string converted into a run length pattern. The first data "1" of the data string in FIG.
2 ”is the run length pattern (0, 4)“ 12 ”because there is no single“ 0 ”immediately before and the group number 12 is 4. In the data string "0, 0, 55" that follows the number "0", which is immediately before the value "55" that is not "0", is 2, and the group number of 55 is 6, so the run length pattern (2 , 6) "55"
Becomes In the next data "-254", since there is no single "0" immediately before and the group number of -254 is 8, the run length pattern (0,8) "-25
4 ”. Similarly, the next data string “0, 3” is
Since there is one "0" immediately before the value "3" that is not "0" and the group number of 3 is 2, the run length pattern (1, 2) is "3".

The run length pattern output from the run length converter 73 is input to the Huffman encoder 74. The Huffman encoder 74 encodes (n, g) of the input run length pattern (n, g) "x" into a Huffman code and "x" into g-bit data. FIG. 13 shows a run length pattern and compressed data corresponding thereto. In FIG. 13, D6 is a Huffman code and D7 is g.
Bit data is shown respectively. Huffman encoder 7
The output of 4 becomes compressed data 77 in sequence.

<Decoding Method> Next, a decoding method of the data compressed by the above method will be described. As shown in Figure 20,
The Huffman decoder 84 sequentially takes out the data from the compressed data 87 and checks whether or not there is a matching Huffman code in the Huffman table 86. If a matching Huffman code is found, the extracted compressed data is converted into a pattern (n, g) to which the Huffman code is assigned, and further g-bit data is extracted from the compressed data 87 to obtain a run length pattern (n, g). g) Output "x".

The inverse converter 83 converts the run length pattern (n, g) "x" output from the Huffman decoder 84 into a data string of n pieces of 0 data and data of value x, and outputs one data at a time. FIG. 16 shows a run length pattern and a data string corresponding to it. The data output from the inverse converter 83 is input to the adder 82. The adder 82 outputs the first input data as it is. The output of the adder 82 becomes the decoded data 80 sequentially, and the same data is input to the predictor 81 on the one hand. Predictor 81
Searches for the same current data as the input data in the prediction table 85, and outputs the predicted value corresponding to the current data. At this time, the data is next input from the inverse converter 83 to the adder 82 at the same time. If there is no data to be output to the inverse converter 83, the data is extracted from the compressed data 87, and the Huffman decoder 84 and the inverse converter 83 are used as described above.
To generate a data string.

The adder 82 adds the input from the inverse converter 83 and the input from the predictor 81 and outputs the result. On the other hand, the output of the adder 82 becomes the decoded data 80, and the same value is input to the predictor 81. The same procedure is followed for compressed data 87.
Iterate until there is no more data, and finish decoding.

{Modification} (1) Although the program data is compressed in the first, second, and third embodiments described above, it may be other kinds of data such as image data. May be.

(2) Although the original data was compressed as a natural binary number in the above-described first, second and third embodiments, the original data is converted into a gray code in units of 4 bits. After that, a method of performing each compression may be used. A part of the gray code is shown in FIG.

(3) In the first embodiment, the program data was converted into the pattern (a, b) by grouping the 8-bit data adjacent to each other in order from the front, but as shown in FIG. Are arranged in a 32-bit width, each line is divided into four, and the first 8 bits and the third 8 bits are set as one set, and the second 8 bits and the fourth 8 bits are set as one set. ). Further, as shown in FIG. 26, a method of arranging program data in a 32-bit width and dividing each line into four to form 8-bit data adjacent to each other in the vertical direction, or one or more intervals in the vertical direction You may use the method of grouping the data which put the.

(4) In the second embodiment, the quantization error of the four-dimensional vector is set to 5 bits for one component. However, the maximum value of the first component of the quantization error of the four-dimensional vector and the second component If the maximum value, the maximum value of the third component, and the maximum value of the fourth component are calculated and each component is compressed to the number of bits that can represent the maximum value, the compression rate can be further improved. it can. Further, it is desirable that the codebook has a size suitable for the learning sequence.

(5) In the second embodiment, the quantization error of each component of the four-dimensional vector is directly used as the compressed data, but the quantization error of each component of the four-dimensional vector is further processed by the Huffman code using the Huffman table. It may be a method of converting. The compressed data in that case is as shown in FIG. Figure 2
D13 in 7 is the index of the quantized representative vector, D
14 to D17 are Huffman codes.

(6) In the third embodiment, the 8-bit data immediately adjacent to the 8-bit data is predicted, but instead of this, every other 8-bit data is predicted. Alternatively, a method of predicting 8-bit data every two bits may be used.

[0076]

According to claim 1 and claim 4 of the present invention, since the one word length of the object code of the program includes the instruction code and the address code, the one word length of the object code is expressed in byte units. When the data is divided into predetermined constituent units, there is a certain correlation between the divided data. From this, it is possible to dramatically improve the compression rate by categorizing the correlation between data into a certain pattern by entropy-compressing a plurality of divided data as one symbol. There is.

According to claims 2 and 5 of the present invention,
Since the 1-word length of the program's object code includes the instruction code and the address code, the 1-word length of the object code is divided into predetermined constituent units such as byte units, and the divided data is quantized into vectors. Then, the vector is not uniformly distributed in the vector space, but has a biased distribution. Therefore, by quantizing the vector into the biased centroid vector and using the data indicating the centroid vector and the quantization error as the compressed data, the compression rate can be dramatically improved.

According to claims 3 and 6 of the present invention,
Since one word length of the object code of the program is composed of an instruction code and an address code, if one word length of the object code is divided into predetermined constituent units such as byte units, there is a correlation between the divided data. . Therefore,
There is an effect that it is possible to predict one divided data from another divided data with a very high probability, and by entropy compressing the prediction error, the compression rate can be dramatically improved.

[Brief description of drawings]

FIG. 1 is a functional block diagram showing a program compression device according to a first embodiment of the present invention.

FIG. 2 is a block diagram showing an apparatus for creating a Huffman table according to the first embodiment of the present invention.

FIG. 3 is a block diagram showing a program decoding device of a first exemplary embodiment of the present invention.

FIG. 4 is a diagram showing a correspondence between a part of program data and its conversion data in the first embodiment of the present invention.

FIG. 5 is a diagram showing final data of program data and data added thereto in the first embodiment of the present invention.

FIG. 6 is a functional block diagram showing a program compression device according to a second embodiment of the present invention.

FIG. 7 is a diagram showing a part of program data and a method of dividing the program data according to a second embodiment of the present invention.

FIG. 8 is a diagram showing a codebook according to a second embodiment of the present invention.

FIG. 9 is a block diagram showing an apparatus for creating a codebook according to a second embodiment of the present invention.

FIG. 10 is a block diagram showing a program decoding device according to a second embodiment of the present invention.

FIG. 11 is a diagram showing correspondence between a part of program data and components of a four-dimensional vector generated from the program data according to the second embodiment of the present invention.

FIG. 12 is a diagram showing compressed data for 32 bits of program data in the second embodiment of the present invention.

FIG. 13 is a diagram showing compressed data according to the third embodiment of the present invention.

FIG. 14 is a diagram showing compressed data according to the second embodiment of the present invention.

FIG. 15 is a functional block diagram showing a program compression device according to a third embodiment of the present invention.

FIG. 16 is a diagram showing a data string and its run length pattern in the third embodiment of the present invention.

FIG. 17 is a block diagram showing an apparatus for creating a prediction table according to the third embodiment of the present invention.

FIG. 18 is a block diagram showing an apparatus for creating a Huffman table according to a third embodiment of the present invention.

FIG. 19 is a diagram showing a data string and its run length pattern in the third embodiment of the present invention.

FIG. 20 is a block diagram showing a program decoding device according to a third embodiment of the present invention.

FIG. 21 is a diagram showing a count table in the third embodiment of the present invention.

FIG. 22 is a diagram showing a prediction table according to the third embodiment of the present invention.

FIG. 23 is a diagram showing a group number table in the third embodiment of the present invention.

FIG. 24 is a diagram showing correspondence between a gray code and a decimal number or a binary number.

FIG. 25 is a diagram showing a part of program data and a method of dividing the program data according to the second embodiment of the present invention.

FIG. 26 is a diagram showing a part of program data and a method of dividing the program data according to the second embodiment of the present invention.

FIG. 27 is a diagram showing compressed data according to the second embodiment of the present invention.

FIG. 28 is a diagram showing a method of creating a Huffman table in a conventional example.

FIG. 29 is a diagram showing a compression method in a conventional example.

[Explanation of symbols]

10, 30, 40, 60, 70, 90, 100, 200
Program data 11, 21, 31, 41, 51, 61 File end adjuster 12, 32, 52 Converter 13, 74, 205 Huffman encoder 14, 24, 37, 76, 86, 107, 204 Huffman table 15, 26,46,57,77,87,206 Compressed data 20,50,80 Decoded data 21 File end adjuster 22,83 Inverse converter 23,84 Huffman decoder 24 Huffman table 25,35,55,65 Number of additional bits 33 pattern counter 34,92,202 count result 36,105,203 Huffman table generator 42,62 vector generator 43 residual calculator 44 vector quantizer 45,56,66 codebook 53 residual adder 54 vector inverse Quantizer 63 Learning sequence 64 Codebook generator 7 , 81, 101 predictor 72,702 subtractor 73,103 run length converter 75,85,94,106 prediction table 82 adder 91,104 counter 93 prediction table generator 201 Data Counter

[Procedure amendment]

[Submission date] December 7, 1994

[Procedure Amendment 1]

[Document name to be corrected] Drawing

[Name of item to be corrected] Figure 3

[Correction method] Change

[Correction content]

[Figure 3]

[Procedure Amendment 2]

[Document name to be corrected] Drawing

[Name of item to be corrected] Figure 5

[Correction method] Change

[Correction content]

[Figure 5]

[Procedure 3]

[Document name to be corrected] Drawing

[Name of item to be corrected] Figure 6

[Correction method] Change

[Correction content]

[Figure 6]

[Procedure amendment 4]

[Document name to be corrected] Drawing

[Name of item to be corrected] Fig. 10

[Correction method] Change

[Correction content]

[Figure 10]

[Procedure Amendment 5]

[Document name to be corrected] Drawing

[Name of item to be corrected] Fig. 20

[Correction method] Change

[Correction content]

FIG. 20

[Procedure correction 6]

[Document name to be corrected] Drawing

[Correction target item name] Fig. 22

[Correction method] Change

[Correction content]

FIG. 22

[Procedure Amendment 7]

[Document name to be corrected] Drawing

[Correction target item name] Fig. 23

[Correction method] Change

[Correction content]

FIG. 23

Claims (6)

[Claims] 1. A method for compressing an object code of a program including an instruction code and an address code, wherein data to be compressed is divided into predetermined constituent units, and a plurality of the predetermined constituent units are made into one symbol. A program compression device comprising conversion means for converting and compression means for entropy compressing the symbols. 2. A first dividing means for compressing an object code of a program including an instruction code and an address code, wherein the data to be compressed is divided into first block data of one word length; A second dividing means for dividing one block data into second block data of a predetermined constitutional unit, and outputting a plurality of the second block data as a vector, and the vector appropriately from a predetermined codebook Vector quantizing means for quantizing the selected representative vector and outputting the representative vector, and outputting an index corresponding to the representative vector as one component of compressed data; output of the second dividing means and the representative Program compression provided with vector difference means for calculating a difference with a vector and outputting it as another component of compressed data Location. 3. A program for compressing an object code of a program including an instruction code and an address code, wherein a dividing means for dividing data to be compressed into block data of a predetermined structural unit and a correlation between the block data are provided. A prediction unit that outputs a data prediction value based on a prediction table created in advance by analyzing, the block data, and a difference between the data prediction value corresponding to the block data is calculated, and the data prediction is performed. A program compression apparatus comprising: an index corresponding to a value; and a difference unit that outputs the difference as a component of compressed data. 4. A conversion step of dividing an object code of a program including an instruction code and an address code into predetermined constituent units and converting a plurality of the predetermined constituent units into one symbol, and entropy compressing the symbols. A program compression method comprising a compression step. 5. A first dividing step of dividing an object code of a program including an instruction code and an address code into first block data of one word length, and the first block data of a second block of a predetermined constitutional unit. A second dividing step of dividing the block data into a plurality of the second block data as a vector, and quantizing the vector into a representative vector appropriately selected from a predetermined codebook, A vector quantization step of outputting the index corresponding to the representative vector as one component of compressed data, and a difference between the output of the second division step and the representative vector to calculate the compressed data. And a vector difference step of outputting as a component of the program compression method. 6. A division step of dividing an object code of a program including an instruction code and an address code into block data of a predetermined structural unit, and a prediction table created in advance by analyzing a correlation between the block data. A prediction step of outputting a data prediction value based on the block data, while calculating the difference between the block prediction data and the data prediction value corresponding to the block data, the index corresponding to the data prediction value and the difference of the compressed data A program compression method comprising a difference step of outputting together as a component.