JP3610381B2 - Data compression device - Google Patents

Description

[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a data compression apparatus, and is particularly suitable for application to high-speed compression processing using a Ziv-Lempel code (LZ code).
[0002]
[Prior art]
In the conventional LZ encoding, there is one in which the appearance position of past data is searched using a hash table. In addition, there has been a method of speeding up the compression processing by using a hard comparator system that compares past data and input data in units of 1 byte.
[0003]
[Problems to be solved by the invention]
However, the hash table method has a problem that the processing speed is slow. In addition, the hard comparator method is a comparison in units of 1 byte, and there is a problem that processing cannot be performed at a processing speed higher than the operation clock. Further, the conventional method has a problem that the maximum compression rate of the blank area at the time of printing is low.
[0004]
Therefore, an object of the present invention is to provide a data compression apparatus capable of performing data compression at high speed.
[0005]
[Means for Solving the Problems]
In order to solve the above-described problem, according to the present invention, comparison means corresponding to all appearance positions of past input data to be compared is provided.According to one aspect of the present invention, the number of repetitions of the same input data string is output as a code of the input data string.
[0006]
As a result, the longest match length and the longest match position can be obtained from the past data string by one-time comparison operation between the past input data string and the current input data string. When determining the coincidence position, it is not necessary to repeatedly perform comparison processing while changing the appearance positions of past data strings one by one, so that data compression using the LZ code can be performed at high speed.Furthermore, since the same input data string is repeated for the blank portion at the time of printing, it is possible to efficiently perform the data compression of the blank portion.
[0007]
According to one aspect of the present invention, the bit length of the data area storing the longest match length and the longest match position is the same as the bit length of the input data.
As a result, when the current input data string and the past input data string match, an LZ code is output. When the current input data string and the past input data string do not match, the current input data remains unchanged. Even when the data is output, the raw data and the LZ code can be output on the same data format, and efficient data compression can be performed.
[0008]
Further, according to one aspect of the present invention, a shift corresponding to the coincidence length of past input data and current input data is performed using a barrel shifter.
As a result, it is possible to shift the matching length of the past data string and the current input data string at a time, and it is possible to perform data compression using the LZ code at high speed.
[0010]
DETAILED DESCRIPTION OF THE INVENTION
A data compression apparatus according to an embodiment of the present invention will be described below with reference to the drawings. FIG. 1 is a diagram for explaining a data compression method according to the first embodiment of the present invention. In FIG. 1, an input data string in units of 1 byte is compared with a past input data string. If there is a past input data string that matches the current input data string, flag data indicating whether or not they match is set to “1”. Then, the longest match length of the portions that match the input data string is replaced with the match position pos and the match length len.
[0011]
For example, “02, 05, 08, 0C, 0B, 0A, 03, 04, 05,...” Is input as the past input data string (indicated by hex), and “0A” is input as the current input data string. , 0B, 0C, 1A, 1B, 0D,... ”Are input, the current input data string is compared with the past input data string. If the longest match data is limited to 8 bytes, 1 byte of flag data and 8 bytes of data D0 to D7 are prepared. Link with bit value. Then, if the “0A, 0B, 0C” portion of the current data string matches the past data string, the seventh bit of the flag data is set to “1”. Further, the upper 3 bits of the data D0 are assigned to the match length len, and the lower 5 bits of the data D0 are assigned to the match position pos, and the match position pos = 5 and a code representing the matching length len = 3 are output as data D0.
[0012]
Next, the current input data string and the past input data string are shifted by the matching length len = 3. Then, the current input data string “1A, 1B, 0D,...” After the shift is replaced with the past input data string “0C, 0B, 0A, 03, 04, 05,. Compare with Here, the data “1A” in the current input data string does not match any data in the past data string. In this case, the sixth bit of the flag data is set to “0” and the code of “1A” of the current input data string is output as data D1 as it is. “1A” is 1-byte data, and the data indicating the match length len and the match position pos is also 1 byte. For this reason, it becomes possible to use the areas of data D0 to D7 storing data indicating the match length len and the match position pos when the input data is stored as it is in the data D0 to D7. It can be used effectively. The above processing is performed on the data D0 to D7 to generate 72-bit output data in which 1-byte flag data and 8-byte compressed data form one set.
[0013]
FIG. 2 is a block diagram showing a system configuration of a data compression apparatus according to an embodiment of the present invention. In FIG. 2, a program 2 of the CPU 1 and a work RAM 3 are provided, and the CPU 1 controls the compression circuit 6 via the I / O ports 4 and 5. The control of the compression circuit 6 by the CPU 1 is data input / output control using the Dreq signal and the Dack signal, and the end signal is used for the end. Further, the data input Din to the compression circuit 6 is 64 bits, and the data output Dout from the compression circuit 6 is 72 bits (in FIG. 2, the bold line indicates data in byte units. FIGS. 5 to 10 below). , FIG. 13, FIG. 18 and FIG. 19 are also the same). The compression circuit 6 performs data compression using the LZ code. Here, the compression circuit 6 is provided with a comparator that searches the past input data Din for a match with the current input data Din for all appearance positions of the past input data Din to be compared. .
[0014]
FIG. 3 is a flowchart showing a data input sequence of the data compression apparatus of FIG. In FIG. 3, every time there is an iDreq (data input request) from the compression circuit 6 (step S1), the CPU 1 outputs 8-bit input data Din to the compression circuit 6 and outputs iDack (data input permission). (Step S2). When the output of all data to be compressed is completed (step S3), the CPU 1 outputs iEND (end of data input) to the compression circuit 6 (step S4).
[0015]
FIG. 4 is a flowchart showing a data output sequence of the data compression apparatus of FIG. In FIG. 4, every time there is a kDreq (data output request) from the compression circuit 6 (step S11), the CPU 1 reads out 72-bit output data Dout from the compression circuit 6 and outputs kDack (data output permission). 6 (step S13). The CPU 1 continues the above processing until it receives kEND (end of data output) from the compression circuit 6 (step S14).
[0016]
FIG. 5 is a block diagram showing the configuration of the compression circuit 6 of the data compression apparatus according to the first embodiment of the present invention. In FIG. 5, an input FIFO 11 is an 8-byte FIFO, and holds input data Din input to the compression circuit 6 as a current input data string. The slide FIFO 12 is a 32-byte FIFO, and holds data iFD0 output from the input FIFO 11 as a past input data string.
[0017]
The search circuit 13 compares the current input data strings iFD0 to iFD7 held in the input FIFO 11 with the past input data strings SFD0 to SFD31 held in the slide FIFO 12. If there is a matching part, the matching position Match-Pos and the matching length Match-Len in the past input data strings SFD0 to SFD31 are output, and Match Flag = 1 is set. On the other hand, if there is no matching part, Match Flag = 0.
[0018]
Here, the search circuit 13 includes a comparator corresponding to the appearance positions of all data in the past input data strings SFD0 to SFD31. Then, by supplying the current input data iFD0 to iFD7 to all the comparators at a time, the current input data string iFD0 to iFD7 and the past input data string SFD0 to SFD31 are compared once, The coincidence position Match-Pos and the coincidence length Match-Len are calculated. As a result, when the match position Match-Pos and the match length Match-Len with the past input data strings SFD0 to SFD31 are calculated, it is necessary to perform comparison processing while passing the past input data strings SFD0 to SFD31 one by one. The match position Match-Pos and the match length Match-Len can be calculated at high speed.
[0019]
The output circuit 14 generates 1-byte compressed data including a match position Match-Pos and a match length Match-Len when Match Flag = 1, and 1 when output from the input FIFO 11 when Match Flag = 0. By using the byte data iFD0 as it is, 9-byte output data Dout is generated in which 1-byte flag data and 8-byte compressed data form one set. And based on the communication result of kDreq, kDack, and kend signal with CPU1, output data Dout is transmitted to CPU1.
[0020]
The sequencer 15 performs data input / output control of the input FIFO 11, the slide FIFO 12, and the output circuit 14 based on the communication results of the iDreq, iDack, and iend signals with the CPU 1.
[0021]
FIG. 6 is a block diagram showing a configuration example of the input FIFO 11 of the compression circuit 6 of FIG. 6, latches 21a to 21c for 8 bytes are provided, and each of the latches 21a to 21c is connected to the next stage latches 21a to 21c via selectors 22a, 22b,. When Shift Mode = 0, each selector 22a, 22b,... Selects the data Din input to the input FIFO 11 and outputs it to the latches 21a to 21c at the next stage. On the other hand, when ShiftMode = 1, the input data iFD0 to iFD7 output from the previous stage latches 21a to 21c are selected and output to the next stage latches 21a to 21c. The latches 21a to 21c hold the input data iFD0 to iFD7. When Shift Mode = 1, every time i-sftCLK is input, the currently held input data iFD0 to iFD7 are shifted to the next stage latches 21a to 21c via the selectors 22a, 22b,. To do. On the other hand, when Shift Mode = 0, the data Din input to the input FIFO 11 is latched by the latches 21a to 21c selected by L0 to L7.
[0022]
FIG. 7 is a block diagram showing a configuration example of the slide FIFO 12 of the compression circuit 6 of FIG. In FIG. 7, latches 31a to 31c for 32 bytes are provided, and each latch 31a to 31c is connected to the latches 31a to 31c in the next stage. Here, the latches 31a to 31c hold the past input data SFD31 to SFD0, and every time s-sftCLK is input, the past input data SFD31 to SFD0 currently held are latched at the next stage 31a to 31c. Shift to.
[0023]
FIG. 8 is a block diagram showing a configuration example of the search circuit 13 of the compression circuit 6 of FIG. In FIG. 8, current input data iFD0 to iFD7 held in the input FIFO 11 and past input data SFD31 to SFD0 held in the slide FIFO 12 are input to the comparison unit 41. Then, the present input data iFD0 to iFD7 and the past input data SFD31 to SFD0 are compared, and the matching lengths len1 to 31 corresponding to the positions of the past input data SFD31 to SFD0 are output. The priority encoder 42 selects the longest match length Match_len from the match lengths len 1 to 31. When the longest match length Match_len is 2 or more, Match_Flag = 1 is output, and the longest match length Match_len and the longest match position Match_pos are output. On the other hand, if the longest match length Match_len is 1 or less, Match_Flag = 0 is output.
[0024]
FIG. 9 is a block diagram illustrating a configuration example of the comparison unit 41 of the compression circuit 6 of FIG. In FIG. 9, the comparison unit 41 is provided with 31 comparators 51a to 51c, and each comparator 51a to 51c corresponds to each appearance position of the past input data SFD31 to SFD0. Here, there are 32 input data SFD31 to SFD0 in total, but since there is no need for comparators corresponding to the appearance positions where the match length is 1, the total number of comparators 51a to 51c may be 31. Further, in order to compare the current 8 input data iFD0 to iFD7 at a time, only 31 2 × 8 input comparators 51c are required, but the portions corresponding to the appearance positions of the past input data SFD6 to SFD1 Have only 7 to 2 past input data SFD31 to SFD0 as comparison controls. Therefore, the comparators 51a, 52b,... Corresponding to the appearance positions of the past input data SFD6 to SFD1 may be 2 × 2 inputs to 2 × 7 inputs, respectively. Each of the comparators 51a to 51c compares the current input data iFD0 to iFD7 with the past input data SFD31 to SFD0, and outputs the matching lengths len1 to 31 at that time.
As described above, the comparison unit 41 includes comparators 51a to 51c for comparing the current eight input data iFD0 to iFD7 with the continuous eight of the past 32 input data SFD31 to SFD0. Are provided corresponding to all the appearance positions of the past input data SFD31 to SFD0. Therefore, when the longest matching position between the current input data iFD0 to iFD7 and the past input data SFD31 to SFD0 is detected, the current input data iFD0 to iFD7 is shifted and compared with the past input data SFD31 to SFD0. This eliminates the need for repeated operations, and allows the longest match position and longest match length to be detected by a single comparison process.
[0025]
FIG. 10 is a block diagram illustrating a configuration example of the comparator 51c of the comparison unit 41 in FIG. In FIG. 10, the comparator 51c inputs the current eight input data iFD0 to iFD7 to A0 to A7, and inputs the continuous eight of the past 32 input data SFD31 to SFD0 to B0 to B7. To do. Then, the current eight input data iFD0 to iFD7 are compared with the eight consecutive input data SFD31 to SFD0 in the past, and the matching length len at that time is output. Here, since the match length len can take a value from 0 to 8, the number of bits of the match length len is 3 bits.
[0026]
FIG. 11 is a diagram illustrating an example of output data of the comparator 51c in FIG. In FIG. 11, the number of matched bytes is encoded as a match length len and output. Here, since 1-byte match has no compression effect, 0 is output.
[0027]
FIG. 12 is a block diagram showing a configuration example of the priority encoder 42 of the search circuit 13 of FIG. In FIG. 12, the priority encoder 42 includes a maximum match length calculation unit 61. The maximum match length calculation unit 61 outputs the maximum match length Match_len among the 31 match lengths len1 to 31 and gives the maximum match length Match_len. The longest match position Match_pos is selected from i1 to i31 and output. The maximum match length Match_len is also output to the comparator 62, and the comparator 62 compares the maximum match length Match_len with 0. When the maximum match length Match_len = 0, the comparator 62 outputs 1, the output from the comparator 62 is inverted by the inverter 63, and Match_Flag = 0 is output. On the other hand, when the maximum match length Match_len is not 0, the comparator 62 outputs 0, the output from the comparator 62 is inverted by the inverter 63, and Match_Flag = 1 is output. FIG. 13 is a block diagram illustrating a configuration example of the output circuit 14 of the compression circuit 6 of FIG. In FIG. 13, a latch 73 for storing 8-bit Match_Flag and latches 74a-74c for storing 8-byte compressed data D0-D7 are provided. The value of Match_Flag output from the priority encoder 42 is output to the latch 73 and also to the sequencer 71 and the selector 72. When Match_Flag = 1, the selector 72 outputs the maximum match length Match_len and the longest match position Match_pos output from the priority encoder 42 to the latches 74a to 74c. On the other hand, when Match_Flag = 0, the selector 72 outputs the 8-bit raw data Dtru output from the input FIFO 11 to the latches 74a to 74c.
[0028]
Each time the put signal is output from the sequencer 15, the sequencer 71 sequentially selects F7 and LD0, F6 and LD1,..., F0 and LD7, stores Match_Flag for 8 bits in the latch 73, and 8 The bytes of compressed data D0 to D7 are stored in the latches 74a to 74c. When 8-bit Match_Flag is stored in the latch 73, and when 8-byte compressed data D0-D7 are stored in the latches 74a-74c, the 72-bit data is output as Dout and KDreq. Is output to the CPU 1. Then, when the CPU 1 captures 72-bit output data Dout and the CPU 1 outputs KDack, the output circuit 14 captures KDACK output from the CPU 1 and repeats the above output operation until jEND is output from the sequencer 15. . Thereafter, when jEND is output from the sequencer 15, the output circuit 14 outputs kEND to the CPU 1 and ends the output operation.
[0029]
FIG. 14 is a flowchart showing the operation of the sequencer 15 of the compression circuit 6 of FIG. In FIG. 14, when the compression circuit 6 performs a compression operation, the sequencer 15 outputs a reset signal to the input FIFO 11 and the slide FIFO 12, and clears the latches 21a to 21c and the latches 31a to 31c (step S21). Next, the shift mode of the input FIFO 11 is set to 0 (step S22), and the selectors 22a, 22b,... Of the input FIFO 11 are switched to the data Din input mode, and n = 0 is set (step S23). Next, iDreq is output to the CPU 1 (step S24). When iDack is returned from the CPU 1 (step S25), L7 to L0 are sequentially output to the input FIFO 11 (steps S26 to S28). The input data Din is latched by the latches 21a to 21c. On the other hand, when iEND is output from the CPU 1 while waiting for an iDack response from the CPU 1 (step S29), jEND is output to the output circuit 14 (step S30).
[0030]
Next, when 8-byte input data Din is latched in the latches 21a to 21c of the input FIFO 11 (step S28), a put signal is output to the output circuit 14 (step S31). Next, when the Match Flag output from the search circuit 13 is 1 (step S32), the shift mode is set to 1 and the i-sftCLK and s-sftCLK are output only the maximum match length Match_len times, whereby the input FIFO 11 The data iFD0 to iFD7 latched in the latches 21a to 21c are shifted by Match_len times, and the data SFD31 to SFD0 latched in the latches 31a to 31c of the slide FIFO 12 are shifted only Match_len times (step S33). Then, Match_len is set in the count (step S34). On the other hand, when the Match Flag output from the search circuit 13 is 0 (step S32), the shift mode is set to 1 and the i-sftCLK and s-sftCLK are output only once, whereby the latches 21a to 21 of the input FIFO 11 are output. The data iFD0 to iFD7 latched in 21c are shifted only once, and the data SFD31 to SFD0 latched in the latches 31a to 31c of the slide FIFO 12 are shifted only once (step S35). Then, 1 is set in count (step S36).
[0031]
Next, the shift mode of the input FIFO 11 is set to 0 (step S37), and the selectors 22a, 22b,... Of the input FIFO 11 are switched to the data Din input mode. Next, iDreq is output to the CPU 1 (step S38). When iDack is returned from the CPU 1 (step S39), L (7-count) is output to the input FIFO 11 (step S40), and empty due to data shift. The new input data Din is latched in the L (7-count) th latches 21a to 21c. By performing the above processing for the count of the number of shifts of the input FIFO 11 (steps S41 and S42), the latches 21a to 21c that have become empty due to the shift of the data iFD0 to iFD7 are set to Fill. When the latches 21a to 21c become Fill, the process returns to Step S31, and the put signal is output to the output circuit 14. On the other hand, when iEND is output from the CPU 1 while waiting for an iDack response from the CPU 1 (step S43), jEND is output to the output circuit 14 (step S44).
[0032]
FIG. 15 is a flowchart showing the operation of the sequencer 71 of the output circuit 14 of FIG. In FIG. 15, n = 0 is set (step S51), and when a put signal is output from the sequencer 15 (step S52), F (7-n) and LDn are output (step S53). The above processing is performed for 8-bit Match_Flag and 8-byte compressed data D0 to D7 (steps S52 to s55), and 8-bit Match_Flag is stored in the latch 73 and 8-byte compressed data D0 to D7. When D7 is stored in the latches 74a to 74c, the 72-bit data is output as Dout and KDreq is output to the CPU 1 (step S56). When the CPU 1 outputs KDack (step S57), the above output operation is repeated until jEND is output from the sequencer 15 (step S58). Thereafter, when jEND is output from the sequencer 15, kEND is output to the CPU 1 (step S59), and the output operation is terminated.
[0033]
As described above, according to the data compression apparatus according to the first embodiment of the present invention, the comparison search is performed by arranging in parallel the comparators corresponding to all the data of the past input data string to be compared. It can be completed in one time, and processing can be performed at high speed. Further, by making the longest matching string 8 bytes, it is possible to generate efficient compressed data.
[0034]
Next, a data compression apparatus according to the second embodiment of the present invention is described. The shift of all data during matching in the first embodiment is performed as many times as the number of matched characters. If the number of matched characters is large, it takes time to shift the data. Therefore, in the second embodiment of the present invention, instead of using a simple shift register to shift the number of matched characters, a barrel shifter is used to perform a shift for a plurality of characters in a single shift operation. Speed up the shift operation.
[0035]
FIG. 16 is a block diagram showing a configuration example of the barrel shifter of the data compression apparatus according to the second embodiment of the present invention. In FIG. 16, the barrel shifter is provided with a selector 82 for setting the output of flip-flops 81a to 81c n bytes before to the current flip-flop 81d. This barrel shifter is provided in the input FIFO 11 in FIG. 6 and the slide FIFO 12 in FIG. As a result, it is possible to shift the data iFD0 to iFD7 latched in the latches 21a to 21c of the input FIFO 11 only by Match_len and output only by outputting i-sftCLK and s-sftCLK once. The data SFD31 to SFD0 latched in the latches 31a to 31c of the FIFO 12 can be shifted by Match_len, and a shift process of a plurality of bytes can be performed at high speed.
[0036]
Next, a data compression apparatus according to the third embodiment of the present invention is described. In the first embodiment of the present invention, when data compression is performed on the blank portion, the 8-byte data in the blank portion is compressed into 1-byte data. However, in the margin part, the same data often appears repeatedly over several hundred bytes. For this reason, it is inefficient to apply the data compression method of the first embodiment as it is to the blank portion. Therefore, in the third embodiment of the present invention, an additional circuit for detecting repetition of the same data over a plurality of bytes is provided. Then, the repetition rate is encoded with respect to repeat data such as a blank portion, thereby improving the compression rate.
[0037]
FIG. 17 is a diagram for explaining a data compression method according to the third embodiment of the present invention. In FIG. 17, the input data string in 1-byte units is compared with the past data string. Then, it is checked whether or not all the current 8-byte input data strings match the last input data in the past. Here, when all the current 8-byte input data strings match the last input data in the past, the flag data is set to “1”, and the current input data string is shifted by 8 bytes. The number of times the current input data string for 8 bytes matches the last input data in the past is counted. Then, the count value CNT at that time is encoded.
[0038]
Here, when encoding repetitive data, the data structure used when encoding the input data with the matching length len and the matching position pos is used as it is. That is, the identification information of repeated data is stored in the storage area of the matching length len, and the repeated count value CNT of 8-byte data is stored in the storage area of the matching position pos. Here, in the encoding method of FIG. 1, since the raw data is output as it is when the match length len = 1, the code with the match length len = 1 is not used as shown in FIG. 11. Therefore, a code with a matching length len = 1 is used to identify repetitive data in the blank portion.
[0039]
For example, the last data string (indicated by hex) (appearance position 0) is “00” and the current data string is “00, 00, 00, 00, 00, 00, 00, 00”. "..." is input. When it is confirmed that all the input data “00, 00, 00, 00, 00, 00, 00, 00” for the current 8 bytes matches the last input data “00” in the past, The seventh bit of data is set to “1”. Further, 1 is stored in the area (upper 3 bits) of the match length len of the data D0, and 1 is stored in the area (lower 5 bits) of the count value CNT of the data D0. Next, the current input data string is shifted by 8 bytes, and it is checked whether or not all the input data strings for the current 8 bytes after the shift match the last input data “00” in the past. If they match, the count value CNT of the data D0 is increased by 1. The above operation is continued until all input data strings for the current 8 bytes do not coincide with the last input data in the past, and all the input data strings for the current 8 bytes after the shift are in the last of the past. If it matches the input data, the count value CNT of the data D0 is incremented by one. When all the current 8-byte input data strings do not coincide with the last input data in the past, the count-up of the count value CNT of the data D0 is finished, and the sign of the current input data string at that time is the data D1. To store. The above processing is performed on the data D0 to D7 to generate 72-bit output data in which 1-byte flag data and 8-byte compressed data form one set.
[0040]
As described above, when the current input data string is shifted by 8 bytes, as long as the input data “00” corresponding to the blank portion continues, the count value CNT of the data D0 only increases by one, and the blank portion data. For storing the data D1 to D7. For this reason, it is possible to efficiently perform the data compression of the margin part. In the embodiment of FIG. 17, only 5 bits are prepared for storing the count value CNT. Therefore, when the count value CNT is 32 or more, the count value CNT cannot be incremented any more, so the next data D1 It is necessary to store the margin data in the area of D7. However, the compression effect is 32 times as much as the case of using the LZ code.
[0041]
FIG. 18 is a block diagram showing a configuration example of a comparator of a data compression apparatus according to the third embodiment of the present invention. This comparator is for checking whether or not all the current 8-byte input data strings match the last input data in the past. In FIG. 18, the comparator 91 is supplied with the current input data iFD0 to iFD7 output from the input FIFO 11 and the past last input data SFD0 output from the slide FIFO 12. When all the current input data iFD0 to iFD7 coincide with the past last input data SFD0, Rep-Flag = 1 is set, and all the current input data iFD0 to iFD7 are the last last input data. If it does not match the data SFD0, Rep-Flag = 0 is set.
[0042]
FIG. 19 is a block diagram showing a configuration example of the output circuit of the data compression apparatus according to the third embodiment of the present invention. 19, the output circuit 14 ′ is newly provided with selectors 101 to 103, an adder 104, a comparator 105, an inverter 106, and an AND circuit 107 with respect to the output circuit 14 of FIG. The value of Rep-Flag output from is supplied to the sequencer 71 ′ and the selector 101.
[0043]
The sequencer 71 ′ first sets Sel_Repin = 0. When Rep-Flag = 0, the output data from the selector 72 ′ is selected by the selectors 101 and 102. Then, according to the value of Match-Flag, the maximum match length Match_len and the longest match position Match_pos or raw data Dthru are supplied to the latches 74a 'to 74c'.
[0044]
On the other hand, when Rep-Flag = 1 when Sel_Repin = 0, the selectors 101 and 102 select 8-bit data “00100001”. Then, by outputting LDn, the 8-bit data is stored in the nth latches 74a 'to 74c'. Here, the upper 3 bits of the 8-bit data represent identification information of repeated data, and the lower 5 bits represent the number of repetitions CNT of 8-byte data. Therefore, by storing the 8-bit data “00100001” in the latches 74a ′ to 74c ′, information that the repeated data of 8 bytes data appears once is stored.
[0045]
Next, when Rep-Flag is 1 when the put signal is output from the sequencer 15, the sequencer 71 'sets Sel_Repin = 1, Sel_D = n, and outputs LDn. As a result, the data Dn latched in the nth latches 74 a ′ to 74 c ′ is selected by the selector 103, and 1 is added to the data Dn by the adder 104. A value obtained by adding 1 to the data Dn is selected by the selector 102, and the addition result is latched in the nth latches 74a 'to 74c'. As a result, the number of repetitions CNT of the data Dn latched in the nth latches 74a 'to 74c' can be increased by one. Here, the comparator 105 monitors the addition result output from the adder 104. When the number of repetitions CNT stored in Dn reaches 32, the comparator 105 notifies the sequencer 71 'via the AND circuit 107. When the sequencer 71 ′ receives notification that the number of repetitions CNT stored in Dn has reached 32, the sequencer 71 ′ performs the above operation on the (n + 1) th latches 74 a ′ to 74 c ′. When 8-bit Match_Flag is stored in the latch 73 ′ and the 8-byte compressed data D0 to D7 are stored in the latches 74a ′ to 74c ′, the 72-bit data is output as Dout. At the same time, KDreq is output to the CPU 1.
[0046]
FIG. 20 is a flowchart showing the operation of the sequencer 71 'of the output circuit 14' of FIG. In FIG. 20, Sel_Repin = 0 is set (step S61), and n = 0 is set (step S62). Next, when a put signal is output from the sequencer 15 (step S63), it is determined whether Rep-Flag = 1 (step S64). If Rep-Flag = 0, F (7-n) and LDn are set. Output (step S65). The above processing is performed on 8-bit Match_Flag and 8-byte compressed data D0 to D7 (steps S63 to S67), and 8-bit Match_Flag is stored in the latch 73 ′ and 8-byte compressed data D0. When .about.D7 are stored in the latches 74a 'to 74c', these 72-bit data are outputted as Dout and KDreq is outputted to the CPU 1 (step S68).
[0047]
On the other hand, if Rep-Flag = 1 in step S64, Sel_Repin = 0 is set (step S72), and F (7-n) and LDn are output (step S73). Next, when the put signal is output from the sequencer 15 (step S74), it is determined whether Rep-Flag = 1 and CNT of Dn is smaller than 32 (step S75). If Rep-Flag = 1 and CNT of Dn is smaller than 32, Sel_D = n and Sel_Repin = 1 are set (step S76). By setting Sel_D = n and Sel_Repin = 1, Dn among D0 to D7 stored in the latches 74a ′ to 74c ′ is selected by the selector 103, and a value obtained by adding 1 by the adder 104 is selected by the selector 103. It is selected at 102 and returned to the latches 74a ′ to 74c ′. Then, by outputting LDn (step S77), a value obtained by adding 1 to Dn is latched in the latches 74a 'to 74c' in which Dn is stored. The above operation is performed every time a put signal is output from the sequencer 15, and when Rep-Flag = 0 or the CNT of Dn becomes 32 or more, the process proceeds to step S66 and n is increased by 1. On the other hand, if jEND is output from the sequencer 15 while waiting for the output of the put signal in step S74 (step S78), kEND is output to the CPU 1 (step S71), and the output operation is terminated.
[0048]
Next, when the CPU 1 outputs KDack (step S69), the above output operation is repeated until jEND is output from the sequencer 15 (step S70). When jEND is output from the sequencer 15, kEND is output to the CPU 1 (step S71), and the output operation is terminated.
[0049]
In the above-described embodiment, data compression has been described. However, it may be applied to data expansion. In the above-described embodiment, an example in which 8-bit data is processed in units of 8 bytes has been described. In the above-described embodiment, the case where the current 8-byte data is compared with the past 32-byte data is shown, but other data may be used. For example, the current 16 bytes of data may be compared with the past 64 bytes of data.
[0050]
【The invention's effect】
As described above, according to the present invention, the comparison between the current input data and the past input data is performed in the past by providing the comparison means corresponding to all the appearance positions of the past input data to be compared. It is possible to perform simultaneously on all appearance positions of the input data, and the longest match length and the longest match position in the LZ code can be obtained by a single comparison operation between the past data string and the current input data string. Therefore, data compression using the LZ code can be performed at high speed.
[0051]
Also, according to one aspect of the present invention, the raw data and the LZ code are mixed on the same data format by matching the bit length of the area storing the match length and the appearance position with the bit length of the input data. Output, and data compression can be performed efficiently.
[0052]
Further, according to one aspect of the present invention, the past input data string and the current input data string are matched by performing a shift corresponding to the matching length of the past data string and the current input data string by using the barrel shifter. A long shift can be performed at a time, and data compression by the LZ code can be performed at high speed.
[0053]
Also, according to one aspect of the present invention, it is possible to efficiently compress the data in the blank portion during printing by outputting the number of repetitions of the same input data string as the code of the input data string.
[Brief description of the drawings]
FIG. 1 is a diagram for explaining a data compression method according to a first embodiment of the present invention.
FIG. 2 is a block diagram showing a system configuration of a data compression apparatus according to an embodiment of the present invention.
FIG. 3 is a flowchart showing a data input sequence of the data compression apparatus of FIG. 2;
4 is a flowchart showing a data output sequence of the data compression apparatus of FIG. 2;
FIG. 5 is a block diagram showing a configuration of a compression circuit of the data compression apparatus according to the first embodiment of the present invention.
6 is a block diagram illustrating a configuration example of an input FIFO of the compression circuit in FIG. 5;
7 is a block diagram illustrating a configuration example of a slide FIFO of the compression circuit of FIG. 5;
8 is a block diagram illustrating a configuration example of a search circuit of the compression circuit of FIG. 5;
9 is a block diagram illustrating a configuration example of a comparison unit of the compression circuit of FIG. 5;
10 is a block diagram illustrating a configuration example of a comparator of the comparison unit in FIG. 9;
11 is a diagram illustrating an example of output data of the comparator in FIG. 10;
12 is a block diagram illustrating a configuration example of a priority encoder of the search circuit in FIG. 8. FIG.
13 is a block diagram illustrating a configuration example of an output circuit 14 of the compression circuit 6 in FIG. 5. FIG.
14 is a flowchart showing the operation of the sequencer 15 of the compression circuit 6 of FIG.
15 is a flowchart showing the operation of the sequencer 71 of the output circuit 14 of FIG.
FIG. 16 is a block diagram showing a configuration example of a barrel shifter of a data compression apparatus according to a second embodiment of the present invention.
FIG. 17 is a diagram for explaining a data compression method according to a third embodiment of the present invention.
FIG. 18 is a block diagram illustrating a configuration example of a comparator of a data compression apparatus according to a third embodiment of the present invention.
FIG. 19 is a block diagram showing a configuration example of an output circuit of a data compression apparatus according to a third embodiment of the present invention.
20 is a flowchart showing the operation of the sequencer 71 'of the output circuit 14' of FIG.
[Explanation of symbols]
1 CPU
2 programs
3 RAM
4, 5 I / O port
6 Compression circuit
11 input FIFO
12 slide FIFO
13 Search circuit
14, 14 'output circuit
15, 71 Sequencer
21a-21c, 31a-31c, 81a-81d flip-flop
22a, 22b, 72, 82, 72 ', 101-103 selector
41 comparison part
42 priority encoder
51a to 51c, 62, 91, 105 comparator
61 Maximum match length calculator
73, 74a-74c, 73 ', 74a'-74c' Latch
104 adder
106 Inverter
107 AND circuit

Claims (3)

An input means for inputting current input data, a holding means for holding past input data, and provided corresponding to all occurrence positions of past input data to be compared with the current input data , Comparison means for obtaining the longest match length and the longest match position by simultaneously comparing the present input data and the past input data with respect to all appearance positions of the past input data, and the same input data data compression apparatus for a counting means for counting the number of repetitions of the column, that Ru and output means for outputting the number of repetitions as the code of the input data sequence characterized. The data compression apparatus according to claim 1, wherein a bit length of a data area storing the longest match length and the longest match position is the same as a bit length of input data. The input means and the holding means include a barrel shifter that performs byte shift of a data string, and the barrel shifter shifts the current input data and the past input data by a matching length at a time. The data compression apparatus according to claim 1 or 2.

Images