JP4600342B2

JP4600342B2 - Data compression program

Info

Publication number: JP4600342B2
Application number: JP2006118544A
Authority: JP
Inventors: 忠久橋本
Original assignee: Funai Electric Co Ltd
Current assignee: Funai Electric Co Ltd
Priority date: 2006-04-21
Filing date: 2006-04-21
Publication date: 2010-12-15
Anticipated expiration: 2026-04-21
Also published as: JP2007293461A

Description

本発明は、電子機器等に搭載されるファームウェア等のデータをデータ圧縮するためのプログラムに関する。 The present invention relates to a program for compressing data such as firmware installed in an electronic device or the like.

現在、電子機器の多くは、ＣＰＵ、メモリ（ＲＯＭ、ＲＡＭなど）等を含むマイコンを搭載しており、電源投入時に各種デバイスの設定、状態チェック等の初期化処理などの所定の処理を行って、一連の処理完了後に使用可能状態になるようになっている。この際、予めＲＯＭ等に格納されている初期化プログラムが、ＲＡＭ等の主記憶装置上にロードされ、この初期化プログラムがＣＰＵによって実行されることにより、電子機器を構成する各種デバイスの初期化がなされる。 Currently, many electronic devices are equipped with a microcomputer including a CPU, memory (ROM, RAM, etc.), and perform predetermined processing such as initialization of various devices and status checks when the power is turned on. The system is ready for use after a series of processing is completed. At this time, an initialization program stored in advance in a ROM or the like is loaded onto a main storage device such as a RAM, and the initialization program is executed by the CPU to initialize various devices constituting the electronic device. Is made.

図８（ａ）は、従来の電子機器の制御部の構成を、（ｂ）は、従来の電子機器に組み込まれるファームウェアの格納状態を示す。従来の電子機器の制御部は、ＣＰＵ１００、ＲＡＭ２００、ＲＯＭ３００及びこれらを結ぶバス４００等からなり、予めＲＯＭ３００等に格納された初期化プログラムや動作プログラムに基いて、バス４００やＩ／Ｏポート（不図示）等のインターフェースを介して、各種デバイス（不図示）と相互にデータの授受を行い、それぞれのデバイスに動作指令したり、状態監視等を行ったりしつつ、電子機器全体の制御を行うようになっている。 FIG. 8A shows a configuration of a control unit of a conventional electronic device, and FIG. 8B shows a storage state of firmware incorporated in the conventional electronic device. A control unit of a conventional electronic device includes a CPU 100, a RAM 200, a ROM 300, a bus 400 connecting these, and the like. Based on an initialization program or an operation program stored in advance in the ROM 300 or the like, the bus 400 and an I / O port (not connected). Data is exchanged with various devices (not shown) via an interface (shown), etc., and the entire electronic device is controlled while commanding operations and monitoring the status of each device. It has become.

また、こうした電子機器の多くは補助記憶装置を持たないので、予めＲＯＭ３００にＩＰＬ（イニシャルプログラムローダ）３１０とファームウェア３１１が一体として格納されている。ＩＰＬ３１０は、起動時にＣＰＵ１００が最初に自動的に実行する領域に設けられているので、電子機器の電源が投入されると、まずＩＰＬ３１０が実行されて、ＩＰＬ３１０内のロードプログラム３１２によりＲＯＭ３００上に格納されたファームウェア３１１は、ＲＡＭ２００上にロードされる。そして、ＲＡＭ２００上にロードされたファームウェア３１１は、ＣＰＵ１００によって実行されて機器の起動処理や動作制御が行われる。 Since many of these electronic devices do not have an auxiliary storage device, an IPL (Initial Program Loader) 310 and firmware 311 are integrally stored in advance in the ROM 300. Since the IPL 310 is provided in an area that is automatically executed by the CPU 100 at the time of startup, when the electronic device is powered on, the IPL 310 is first executed and stored in the ROM 300 by the load program 312 in the IPL 310. The firmware 311 thus loaded is loaded onto the RAM 200. The firmware 311 loaded on the RAM 200 is executed by the CPU 100 to perform device activation processing and operation control.

一般的に、ＲＯＭは、ＲＡＭと比較して、容量あたりの価格が高く、また速度も遅いという欠点がある。また、近年では、電子機器の高機能化に伴い、機器を制御するファームウェア等のプログラムが大規模化し、プログラムサイズが大きくなる傾向がある。サイズの大きいプログラムをそのままＲＯＭ上に置くことは、高価なＲＯＭを大量に使うことになるため、機器のコストアップに繋がるという問題があった。こうした問題に対して、予めプログラムをデータ圧縮し、圧縮済プログラムをＲＯＭ上に格納しておき、圧縮済プログラムをデータ展開するルーチンを備えたＩＰＬによって、起動時に圧縮済プログラムを展開してＲＡＭ上に配置して、プログラムを起動・実行するという手法がとられるようになっている。 In general, ROM has the disadvantages that the price per capacity is higher and the speed is slower than RAM. In recent years, as electronic devices have higher functions, programs such as firmware for controlling the devices have become larger and the program size tends to increase. Placing a large-sized program on the ROM as it is requires a large amount of expensive ROM, leading to an increase in the cost of the device. For such problems, the program is compressed in advance, the compressed program is stored on the ROM, and the compressed program is expanded on startup by the IPL provided with a routine for expanding the data of the compressed program on the RAM. It is arranged to start and execute the program by placing it in the.

しかし、この一方で、プログラムをデータ圧縮することにより、機器の起動時にＲＯＭ上に格納された圧縮済プログラムをＲＡＭ上にデータ展開するのに必要な処理時間が長くなり、機器の起動が遅くなってしまうという問題があった。 On the other hand, however, by compressing the program data, the processing time required to expand the compressed program stored in the ROM onto the RAM at the time of starting the device becomes longer, and the starting of the device is delayed. There was a problem that.

電子機器等に搭載するプログラムにおけるこれらの問題の改善にあたって、例えば特許文献１では、プログラムの展開速度を高めるために、予めＲＯＭに格納した圧縮済システムプログラムを装置起動時にＣＰＵ及びデータ展開ハードウェア（ＣＯＤＥＣ）を用いて展開し、ＲＡＭ上に配置する構成としている。また、特許文献２では、ＣＰＵのマシンコードを、コードが意味する命令の性質によって複数のタイプに区分し、タイプ毎に異なる圧縮アルゴリズムを使用してマシンコードを圧縮して、ＲＯＭに保存するプログラムの圧縮率を高めている。この他に、プログラムコードの圧縮率を高める手法として、漢字コードやカラーコード等の入力データ長の規則性を柔軟に取込んで、複数バイト長のデータを効率よく圧縮する手法（特許文献３）、ＲＩＳＣＣＰＵにおいて、拡張命令コードで置換することにより、コードの冗長フィールドを除去したうえで、プログラムを圧縮する手法（特許文献４）、プログラムのコードを並べ替えることによって、プログラム境界の圧縮率の低下を抑える手法（特許文献５）等が、知られている。
特開２００２−３６６３６２号公報特開平１０−３２０１７２号公報特開平０５−１２８１００号公報特開２０００−２２２２０３号公報特開２００４−３２８０９７号公報 In order to improve these problems in a program installed in an electronic device or the like, for example, in Patent Document 1, in order to increase the development speed of a program, a compressed system program stored in a ROM in advance is loaded with a CPU and data development hardware ( CODEC) is used for development and placement on the RAM. Further, in Patent Document 2, a program for dividing a machine code of a CPU into a plurality of types according to the nature of an instruction meant by the code, compressing the machine code using a different compression algorithm for each type, and storing the program in a ROM The compression rate is increased. In addition to this, as a technique for increasing the compression rate of the program code, a technique that efficiently incorporates regularity of input data length such as Kanji code and color code, and efficiently compresses data of a plurality of bytes (Patent Document 3). In the RISC CPU, a method of compressing a program after removing a redundant field of the code by replacing with an extended instruction code (Patent Document 4), and rearranging the code of the program, the compression rate of the program boundary A technique for suppressing the decrease (Patent Document 5) and the like are known.
JP 2002-366362 A Japanese Patent Laid-Open No. 10-320172 JP 05-128100 A JP 2000-222203 A JP 2004-328097 A

これらのプログラムが搭載される電子機器において、プログラムのＲＯＭ上の容量、及び起動時のＲＡＭ上へのデータ展開速度は、いずれも機器のコストや性能に重要な影響を与えるものであり、トレードオフの関係にある両者を総合的な観点からバランスよく構成することが重要である。特許文献１及び２〜５に例示した手法は、いずれか一方に重点が置かれているもので、専用ハードウェアを用いることによってデータ展開処理速度の向上と引き換えにコスト上昇を招いたり、複雑なルールによりプログラムコードの圧縮率を高めたために、データ展開プログラムが複雑化し、データ展開に時間がかかったりして、コストと性能（データ展開速度）をバランスよく構成することが困難であった。 In an electronic device in which these programs are installed, the capacity of the program on the ROM and the speed of data development on the RAM at start-up both have a significant impact on the cost and performance of the device, and are a trade-off. It is important to make a good balance from a comprehensive point of view. The methods exemplified in Patent Documents 1 and 2 to 5 are focused on either one, and using dedicated hardware increases the cost in exchange for improving the data development processing speed, Since the compression rate of the program code is increased by the rules, the data expansion program becomes complicated and it takes time to expand the data, and it is difficult to configure the cost and performance (data expansion speed) in a balanced manner.

本発明は、上記の点に鑑みてなされたもので、電子機器に搭載されるマイコンのファームウェア等のプログラムコードをデータ圧縮するデータ圧縮プログラムにおいて、プログラムコードを搭載する機器のＣＰＵの命令コード長の特徴を利用して、従来のスライド辞書方式のデータ圧縮処理よりも高いデータ圧縮率を実現すると共に、単純なデータ展開処理により、高速にデータ展開可能な圧縮コードを生成することが可能なデータ圧縮プログラムを提供することを目的とする。 The present invention has been made in view of the above points, and in a data compression program for data compression of program code such as firmware of a microcomputer mounted on an electronic device, the instruction code length of the CPU of the device on which the program code is mounted is Data compression that enables higher data compression ratio than conventional slide dictionary type data compression processing by using features, and that can generate compression codes that can expand data at high speed by simple data expansion processing The purpose is to provide a program.

上記目的を達成するために請求項１の発明は、４バイト命令モードを有するＣＰＵが実行する機器制御用ファームウェアをデータ圧縮するために、コンピュータを、前記機器制御用ファームウェアを保持するデータ保持手段、前記機器制御用ファームウェアのデータ列のうち、現在データ圧縮処理の対象になっているデータ列（検索データ列）の一部を順次保持するパターン検索バッファ、前記機器制御用ファームウェアのデータ列のうち、既にデータ圧縮処理の対象になったデータ列の一部又は全部であるスライド辞書用のデータを保持するスライド辞書バッファ、前記パターン検索バッファの検索データ列と一致する一致データ列を前記スライド辞書バッファ内のデータから検索するパターン検索手段、及び前記パターン検索手段による検索結果を用いて、スライド辞書方式により前記制御機器用ファームウェアをデータ圧縮するデータ圧縮手段として機能させるためのデータ圧縮プログラムにおいて、前記データ圧縮手段は、前記機器制御用ファームウェアのデータを、第１のデータ形式、第２のデータ形式、及び第３のデータ形式に変換し、前記第１乃至第３の各データ形式は、データ形式識別用の識別データ領域を有し、前記第１のデータ形式は、１ビットの識別データ領域に加えて、データを非圧縮で保持する８ビットのデータ領域を有し、前記第２のデータ形式は、２ビットの識別データ領域に加えて、前記一致データ列の相対位置を示す１０ビットの位置データ領域と、前記一致データ列のデータ長を示す２ビットのデータ長領域とを有し、前記第３のデータ形式は、２ビットの識別データ領域に加えて、前記一致データ列の相対位置を示す６ビットの位置データ領域と、前記一致データ列のデータ長を示す２ビットのデータ長領域とを有し、前記データ圧縮手段は、前記パターン検索手段を用いて、前記スライド辞書バッファ内のデータから前記パターン検索バッファの検索データ列と一致するデータ列を全て検索して、前記検索の結果、前記スライド辞書バッファ内のデータの中に、前記検索データ列の先頭から２バイトのデータ列と一致するデータ列がない場合には、前記検索データ列のうちの先頭のバイトのデータに基いて、前記第１のデータ形式でデータを生成し、前記検索の結果、前記スライド辞書バッファ内のデータの中に、前記検索データ列の先頭から２バイトのデータ列と一致するデータ列がある場合には、前記一致データ列のうち最長のデータ列について、現在の検索位置からの相対位置が４の倍数となる位置にあるものが存在するか否かを判定して、前記判定の結果、存在するときは、前記最長の一致データ列に基いて、前記第３のデータ形式でデータを生成し、前記判定の結果、存在しないときには、前記最長の一致データ列に基いて、前記第２のデータ形式でデータを生成して、順次、前記機器制御用ファームウェア内のデータの圧縮処理を行うこととした。 In order to achieve the above object, the invention of claim 1 is directed to a data holding means for holding a computer to store the device control firmware in order to compress the device control firmware executed by the CPU having the 4-byte instruction mode. Of the device control firmware data sequence, a pattern search buffer that sequentially holds a part of a data sequence (search data sequence) that is currently subject to data compression processing, and among the device control firmware data sequence, A slide dictionary buffer that holds data for a slide dictionary that is part or all of a data string that has already been subjected to data compression processing, and a matching data string that matches the search data string in the pattern search buffer is stored in the slide dictionary buffer By pattern search means for searching from the data and the pattern search means In the data compression program for causing the control device firmware to function as a data compression unit for compressing the data for the control device by the slide dictionary method using the search result, the data compression unit stores the data of the device control firmware in the first The data format, the second data format, and the third data format are converted, and each of the first to third data formats has an identification data area for data format identification, and the first data format is In addition to a 1-bit identification data area, an 8-bit data area for storing data in an uncompressed state is included, and the second data format includes a 2-bit identification data area and the matching data string A third data format having a 10-bit position data area indicating a relative position and a 2-bit data length area indicating a data length of the matched data string; In addition to a 2-bit identification data area, the data includes a 6-bit position data area indicating a relative position of the matched data string, and a 2-bit data length area indicating a data length of the matched data string, The compression means uses the pattern search means to search all data strings that match the search data string in the pattern search buffer from the data in the slide dictionary buffer. As a result of the search, the compression means If there is no data string in the data that matches the 2-byte data string from the beginning of the search data string, the first data format is based on the data of the first byte of the search data string As a result of the search, data matching the 2-byte data string from the beginning of the search data string is included in the data in the slide dictionary buffer. If there is a data column, the longest data column of the matched data columns is determined whether or not there is a column whose relative position from the current search position is a multiple of four, and As a result of the determination, when it exists, based on the longest match data string, data is generated in the third data format, and as a result of the determination, when it does not exist, based on the longest match data string, Data is generated in the second data format, and data compression processing in the device control firmware is sequentially performed.

請求項２の発明は、４バイト命令モードを有するＣＰＵが実行する機器制御用ファームウェアをデータ圧縮するために、コンピュータを、前記機器制御用ファームウェアを保持するデータ保持手段、前記機器制御用ファームウェアのデータ列のうち、現在データ圧縮処理の対象になっているデータ列（検索データ列）を順次保持するパターン検索バッファ、前記機器制御用ファームウェアのデータ列のうち、既にデータ圧縮処理の対象になったデータ列の一部又は全部であるスライド辞書用のデータを保持するスライド辞書バッファ、前記パターン検索バッファの検索データ列と一致する一致データ列を前記スライド辞書バッファ内のデータから検索するパターン検索手段、及び前記パターン検索手段による検索結果を用いて、スライド辞書方式により前記制御機器用ファームウェアをデータ圧縮するデータ圧縮手段として機能させるためのデータ圧縮プログラムにおいて、前記データ圧縮手段は、前記機器制御用ファームウェアのデータを、第１のデータ形式、第２のデータ形式、及び第３のデータ形式に変換し、前記第１乃至第３の各データ形式は、データ形式識別用の識別データ領域を有し、前記第１のデータ形式は、１ビットの識別データ領域に加えて、データを非圧縮で保持する８ビットのデータ領域を有し、前記第２のデータ形式は、２ビットの識別データ領域に加えて、前記一致データ列の相対位置を示す１０ビットの位置データ領域と、前記一致データ列のデータ長を示すデータ長領域とを有し、前記第３のデータ形式は、２ビットの識別データ領域に加えて、前記一致データ列の相対位置を示す６ビットの位置データ領域と、前記一致データ列のデータ長を示すデータ長領域とを有し、前記第３のデータ形式のデータサイズは、前記第２のデータ形式のデータサイズよりも小さく、前記データ圧縮手段は、前記パターン検索手段を用いて、前記スライド辞書バッファ内のデータから前記パターン検索バッファの検索データ列と一致するデータ列を全て検索して、前記検索の結果、前記スライド辞書バッファ内のデータの中に、前記検索データ列の先頭から２バイトのデータ列と一致するデータ列がない場合には、前記検索データ列のうちの先頭のバイトのデータに基いて、前記第１のデータ形式でデータを生成し、前記検索の結果、前記スライド辞書バッファ内のデータの中に、前記検索データ列の先頭から２バイトのデータ列と一致するデータ列がある場合には、前記一致データ列のうち最長のデータ列について、現在の検索位置からの相対位置が４の倍数となる位置にあるものが存在するか否かを判定して、前記判定の結果、存在するときは、前記最長の一致データ列に基いて、前記第３のデータ形式でデータを生成し、前記判定の結果、存在しないときには、前記最長の一致データ列に基いて、前記第２のデータ形式でデータを生成して、順次、前記機器制御用ファームウェア内のデータの圧縮処理を行うこととした。 According to a second aspect of the present invention, there is provided a data holding means for holding the device control firmware in order to compress the device control firmware executed by the CPU having the 4-byte instruction mode, and the device control firmware data. A pattern search buffer that sequentially holds a data string (search data string) that is currently subject to data compression processing among the columns, and data that has already been subject to data compression processing among the data strings of the device control firmware A slide dictionary buffer that holds data for a slide dictionary that is a part or all of the column, a pattern search unit that searches the data in the slide dictionary buffer for a matching data string that matches the search data string in the pattern search buffer, and Using a search result by the pattern search means, a slide dictionary In the data compression program for causing the control device firmware to function as data compression means for compressing data according to the method, the data compression means converts the device control firmware data into a first data format and a second data format. , And the third data format, each of the first to third data formats has an identification data area for identifying the data format, and the first data format is a 1-bit identification data area. In addition, it has an 8-bit data area for holding data uncompressed, and the second data format is a 10-bit position indicating a relative position of the coincidence data string in addition to a 2-bit identification data area A third data format including a data area and a data length area indicating a data length of the coincidence data string, in addition to a 2-bit identification data area; A 6-bit position data area indicating the relative position of the matched data string; and a data length area indicating the data length of the matched data string; and the data size of the third data format is the second data format The data compression means uses the pattern search means to search all data strings that match the search data string in the pattern search buffer from the data in the slide dictionary buffer, and As a result, if the data in the slide dictionary buffer does not contain a data string that matches the 2-byte data string from the beginning of the search data string, the data in the first byte of the search data string Based on the result of the search, data in the slide dictionary buffer is included in the data in the slide dictionary buffer as a result of the search. If there is a data string that matches a 2-byte data string, the longest data string of the matched data strings is at a position where the relative position from the current search position is a multiple of four. If there is a result of the determination, data is generated in the third data format based on the longest match data string. Based on the longest matching data string, data is generated in the second data format, and data compression processing in the device control firmware is sequentially performed .

請求項１及び２の発明によれば、高速処理が可能なスライド辞書方式のデータ圧縮処理において、４バイト命令モードを有するＣＰＵが実行するプログラム中に４バイト間隔で出現する割合が高いデータ列について、データサイズが小さい圧縮データ形式（第３のデータ形式）を用いて高いデータ圧縮率で符号化し、その他のデータ列でデータ圧縮可能なものについては、従来のスライド辞書方式と同様な圧縮データ形式（第２のデータ形式）でデータ圧縮するようにした。これにより従来のスライド辞書方式のデータ圧縮処理よりも高いデータ圧縮率を実現することができる。また、圧縮コードの構成を３種類のデータ形式からなる単純なものとしたので、単純なデータ展開処理により、高速なデータ展開処理が可能となる。 According to the first and second aspects of the invention, in a slide dictionary type data compression process capable of high-speed processing, a data string having a high ratio of appearing at 4-byte intervals in a program executed by a CPU having a 4-byte instruction mode. Compressed data format similar to that of the conventional slide dictionary method for data that can be encoded with a high data compression rate using a compressed data format (third data format) with a small data size and can be compressed with other data strings Data compression is performed in (second data format). As a result, a higher data compression rate than the conventional slide dictionary type data compression processing can be realized. Further, since the configuration of the compression code is a simple one consisting of three types of data formats, high-speed data expansion processing can be performed by simple data expansion processing.

以下、本発明の一実施の形態に係る機器制御用ファームウェアのデータ圧縮を行うデータ圧縮プログラムについて、図１乃至図７を参照して説明する。まず、データ圧縮プログラムを動作させる装置、及びデータ圧縮された圧縮済ファームウェア５を搭載する電子機器の構成について図１を用いて説明する。図１（ａ）は、データ圧縮プログラム３を動作させるコンピュータ１の構成である。図１（ｂ）は、コンピュータ１において生成された圧縮済ファームウェア５を搭載する電子機器８の制御部の構成である。 Hereinafter, a data compression program for performing data compression of device control firmware according to an embodiment of the present invention will be described with reference to FIGS. First, the configuration of an apparatus that operates a data compression program and an electronic device that includes data-compressed compressed firmware 5 will be described with reference to FIG. FIG. 1A shows the configuration of the computer 1 that operates the data compression program 3. FIG. 1B is a configuration of a control unit of the electronic device 8 on which the compressed firmware 5 generated in the computer 1 is mounted.

コンピュータ１は、演算処理を行うＣＰＵ２と、ＨＤＤ（ハードディスク）６とを備えている。このＨＤＤ６には、ＣＰＵ２が実行するデータ圧縮プログラム３、データ圧縮の対象となる機器制御用ファームウェアとしてのファームウェア４、及び作成される圧縮済ファームウェア５が格納される。また、コンピュータ１は、処理中のデータを一時的に保存し、実行時にデータ圧縮プログラムがロードされるＲＡＭ７（データ保持手段）を備える。 The computer 1 includes a CPU 2 that performs arithmetic processing and an HDD (hard disk) 6. The HDD 6 stores a data compression program 3 executed by the CPU 2, firmware 4 as device control firmware to be subjected to data compression, and created compressed firmware 5. The computer 1 also includes a RAM 7 (data holding unit) that temporarily stores data being processed and is loaded with a data compression program at the time of execution.

データ圧縮プログラム３により生成された圧縮済ファームウェア５は、電子機器８の制御部において、電子機器８のＲＯＭ９にＩＰＬ１０と共に格納され、起動時に電子機器８に搭載されたＡＲＭＣＰＵ１１によって、ＲＡＭ１２上にデータ展開されて、実行処理されるようになっている。なお、ＡＲＭＣＰＵ１１は、ＡＲＭＭｏｄｅ命令とＴｈｕｍｂＭｏｄｅ命令の２種類の命令モードを有しており、ＡＲＭＭｏｄｅ命令は、４バイト命令であり、この命令モードによるプログラムは、プログラムデータ中に４バイト毎に同一のデータ列が現れることが多くなるという特徴がある。 The compressed firmware 5 generated by the data compression program 3 is stored together with the IPL 10 in the ROM 9 of the electronic device 8 in the control unit of the electronic device 8 and is stored in the RAM 12 by the ARM CPU 11 mounted on the electronic device 8 at the time of activation. It is expanded and executed. Note that the ARM CPU 11 has two types of instruction modes, an ARM Mode instruction and a Thumb Mode instruction. The ARM Mode instruction is a 4-byte instruction. The same data string often appears in

データ圧縮プログラム３は、実行時にＨＤＤ６からＲＡＭ７上にロードされる。データ圧縮プログラム３により使用されるＲＡＭ７上のメモリ空間には、データ圧縮処理の対象となるファームウェア４を格納するためのファームウェア格納領域７ａ、パターン検索バッファ７ｂ、スライド辞書バッファ７ｃ、圧縮済ファームウェア格納領域７ｄが配され、ファームウェア４は、ＨＤＤ６からファームウェア格納領域７ａにロードされる。 The data compression program 3 is loaded from the HDD 6 onto the RAM 7 at the time of execution. In a memory space on the RAM 7 used by the data compression program 3, a firmware storage area 7a for storing the firmware 4 to be subjected to data compression processing, a pattern search buffer 7b, a slide dictionary buffer 7c, a compressed firmware storage area 7d is arranged, and the firmware 4 is loaded from the HDD 6 to the firmware storage area 7a.

なお、データ圧縮プログラム３は、データ圧縮手法として、スライド辞書方式を採用している。このデータ圧縮プログラム３とＣＰＵ２とは、請求項におけるデータ圧縮手段及びパターン検索手段に相当する。 The data compression program 3 employs a slide dictionary method as a data compression method. The data compression program 3 and the CPU 2 correspond to data compression means and pattern search means in the claims.

次に、本実施形態におけるスライド辞書方式によるデータ圧縮について図２を参照して説明する。図２は、データ圧縮対象となるファームウェア４と、スライド辞書方式に用いるデータの関係及び構成を示す。スライド辞書方式によるデータ圧縮は、ファームウェア４の一部をスライド辞書領域４ａとし、スライド辞書領域の後ろに続く一部の領域をデータ圧縮処理対象領域４ｂとして、データ圧縮処理対象領域４ｂの検索データ列１３と同一のデータ列をスライド辞書領域４ａから検索し、一致データ列１４が見つかった場合は、一致データ列１４の相対位置（データ圧縮処理対象領域４ｂの先頭から一致データ列１４の先頭までのバイト数）と、一致データ列１４のデータ長を所定のデータ形式に変換し、検索データ列１３の単位圧縮データとするもので、スライド辞書領域４ａ及びデータ圧縮処理対象領域４ｂを、順次後方に移動させて、ファームウェア４全体についてデータ圧縮処理を行い、圧縮済ファームウェア５を生成する。 Next, data compression by the slide dictionary method in the present embodiment will be described with reference to FIG. FIG. 2 shows the relationship and configuration of the firmware 4 to be compressed and the data used for the slide dictionary method. In the data compression by the slide dictionary method, a part of the firmware 4 is set as the slide dictionary area 4a, and a part of the area following the slide dictionary area is set as the data compression process target area 4b. 13 is searched from the slide dictionary area 4a, and if the matching data string 14 is found, the relative position of the matching data string 14 (from the head of the data compression processing target area 4b to the head of the matching data string 14). The number of bytes) and the data length of the coincidence data string 14 are converted into a predetermined data format to form unit compressed data of the search data string 13, and the slide dictionary area 4a and the data compression process target area 4b are sequentially moved backward. The compressed firmware 5 is generated by performing data compression processing on the entire firmware 4.

本実施形態では、スライド辞書領域４ａをスライド辞書バッファ７ｃに、データ圧縮処理対象領域４ｂをパターン検索バッファ７ｂに、それぞれセットして処理を行う。なお、スライド辞書領域４ａは、領域サイズが２バイト〜１０２４バイトで、ＦＩＦＯ（Ｆｉｒｓｔ−ＩｎＦｉｒｓｔ−Ｏｕｔ）方式としており、処理開始時には、領域サイズが２バイトで、処理の進行に伴い、最終的には１０２４バイトとなり、それ以後は、最初のデータが順次押し出されるようになっている。 In this embodiment, the slide dictionary area 4a is set in the slide dictionary buffer 7c, and the data compression process target area 4b is set in the pattern search buffer 7b, respectively, for processing. The slide dictionary area 4a has an area size of 2 bytes to 1024 bytes and is a FIFO (First-In First-Out) system. At the start of the process, the area size is 2 bytes, and the final size is increased as the process proceeds. Is 1024 bytes, and after that, the first data is sequentially pushed out.

次に、第１〜第３のデータ形式１５ａ、１５ｂ、１５ｃについて、図３を参照して説明する。図３（ａ）、（ｂ）、（ｃ）は各々、データ圧縮処理において検索データ列１３が変換される３種類のデータ形式の構造をあらわす。データ圧縮処理においては、検索データ列１３を第１〜第３のデータ形式への変換し、単位圧縮データを生成する処理をデータ処理単位としており、単位圧縮データ毎の処理を繰返して、ファームウェア４全体のデータ圧縮を行っている。 Next, the first to third data formats 15a, 15b, and 15c will be described with reference to FIG. FIGS. 3A, 3B, and 3C each show structures of three types of data formats into which the search data string 13 is converted in the data compression process. In the data compression process, the search data string 13 is converted into first to third data formats, and the process of generating unit compressed data is used as a data processing unit. The process for each unit compressed data is repeated, and the firmware 4 The whole data is compressed.

各々のデータ形式１５ａ〜１５ｃは、それぞれのデータ形式を識別するための識別データ領域ＩＤを有している。第１のデータ形式としての非圧縮データ形式１５ａは、全体で９ビットのデータ領域を有し、データ領域の先頭から順に、１ビットの識別データ領域ＩＤと、ファームウェア４を非圧縮で格納する８ビットのコピーデータ領域ＣＰとを有する。 Each of the data formats 15a to 15c has an identification data area ID for identifying each data format. The uncompressed data format 15a as the first data format has a 9-bit data area as a whole, and stores the 1-bit identification data area ID and the firmware 4 in an uncompressed order sequentially from the top of the data area. And a bit copy data area CP.

非圧縮データ形式１５ａの識別データ領域ＩＤは常に「０」がセットされており、この後のコピーデータ領域ＣＰにファームウェア４内の１バイト（８ビット）のデータがそのまま格納されるようになっている。 The identification data area ID of the uncompressed data format 15a is always set to “0”, and 1-byte (8-bit) data in the firmware 4 is stored as it is in the subsequent copy data area CP. Yes.

第２のデータ形式としての第1圧縮データ形式１５ｂは、全体で１４ビットのデータ領域を有し、データ領域の先頭から順に、２ビットの識別データ領域ＩＤと、最長の一致データ列１４の相対位置を示す１０ビットの位置データ領域ＰＯＳと、そのデータ長を示す２ビットのデータ長領域ＬＮとを有する。第１圧縮データ形式１５ｂの識別データ領域ＩＤは、常に「１０」がセットされる。位置データ領域ＰＯＳには、最長の一致データ列１４の相対位置、すなわち検索データ列１３の先頭から、最長の一致データ先頭位置までのバイト数が相対位置データとして格納される。なお、位置データ領域ＰＯＳを１０ビットとしているので、最小値を１バイト（「００００００００００」）として、最大１０２４バイト（「１１１１１１１１１１」）までの相対位置を格納することができる。データ長領域ＬＮは、２ビットであるので、最長の一致データ列１４のデータ長を２バイト（「００」）〜５バイト（「１１」）の範囲で保持できるようになっている。従って、第１圧縮データ形式１５ｂでは、最長の一致データ列１４のデータ長に応じて、１４／１６〜１４／４０の範囲のデータ圧縮率を得ることができる。 The first compressed data format 15b as the second data format has a 14-bit data area as a whole, and the relative order of the 2-bit identification data area ID and the longest matching data string 14 in order from the top of the data area. It has a 10-bit position data area POS indicating the position, and a 2-bit data length area LN indicating the data length. The identification data area ID of the first compressed data format 15b is always set to “10”. In the position data area POS, the relative position of the longest match data string 14, that is, the number of bytes from the start of the search data string 13 to the longest match data start position is stored as relative position data. Since the position data area POS has 10 bits, the minimum value is 1 byte (“0000000”), and relative positions up to a maximum of 1024 bytes (“1111111111”) can be stored. Since the data length area LN is 2 bits, the data length of the longest matching data string 14 can be held in the range of 2 bytes (“00”) to 5 bytes (“11”). Therefore, in the first compressed data format 15b, a data compression rate in the range of 14/16 to 14/40 can be obtained according to the data length of the longest matching data string 14.

第３のデータ形式としての第２圧縮データ形式１５ｃは、全体で１０ビットのデータ領域を有し、データ領域の先頭から順に、２ビットの識別データ領域ＩＤと、最長の一致データ列１４の相対位置を示す６ビットの位置データ領域ＰＯＳと、そのデータ長を示す２ビット長のデータ長領域ＬＮとを有する。第２圧縮データ形式１５ｃの識別データ領域ＩＤは、常に「１１」がセットされる。位置データ領域ＰＯＳには、最長の一致データ列１４の相対位置、すなわち検索データ列１３の先頭から、最長の一致データ列１４の先頭位置までのバイト数が相対位置データとして格納される。なお、第２圧縮データ形式１５ｃは、検索データ列１３の先頭からの最長の一致データ列１４の相対位置が４、８、１２、…、２５６バイトのように４の倍数となっている場合にのみ用いられる。従って、位置データ領域ＰＯＳ内の６ビットの位置データは、最小値を４バイト（「００００００」）として、４バイト刻みに最大値２５６バイト（「１１１１１１」）までの相対位置データを格納することができる。データ長領域ＬＮは、２ビットであるので、最長の一致データ列１４のデータ長を２バイト（「００」）〜5バイト（「１１」）の範囲で保持できるようになっている。従って、このデータ形式では、最長の一致データ列１４のデータ長に応じて、１０／１６〜１０／４０の範囲の圧縮率を得ることができる。 The second compressed data format 15c as the third data format has a 10-bit data area as a whole, and the relative order of the 2-bit identification data area ID and the longest matching data string 14 in order from the top of the data area. It has a 6-bit position data area POS indicating the position, and a 2-bit length data length area LN indicating the data length. The identification data area ID of the second compressed data format 15c is always set to “11”. In the position data area POS, the relative position of the longest match data string 14, that is, the number of bytes from the beginning of the search data string 13 to the start position of the longest match data string 14 is stored as relative position data. The second compressed data format 15c is used when the relative position of the longest match data string 14 from the beginning of the search data string 13 is a multiple of 4, such as 4, 8, 12,. Only used. Therefore, 6-bit position data in the position data area POS can store relative position data up to a maximum value of 256 bytes ("111111") in 4-byte increments with a minimum value of 4 bytes ("000000"). it can. Since the data length area LN is 2 bits, the data length of the longest matching data string 14 can be held in the range of 2 bytes (“00”) to 5 bytes (“11”). Therefore, in this data format, a compression rate in the range of 10/16 to 10/40 can be obtained according to the data length of the longest matching data string 14.

次に、データ圧縮プログラム３の処理の全体の流れについて、図４を参照して説明する。以下の処理は、データ圧縮プログラム３に基いてＣＰＵ２が実行する。 Next, the overall processing flow of the data compression program 3 will be described with reference to FIG. The following processing is executed by the CPU 2 based on the data compression program 3.

まず、Ｓ１における初期化処理として、ＣＰＵ２は、スライド辞書バッファ７ｃ及びパターン検索バッファ７ｂ等の初期化を行う。データ圧縮処理は２バイト以上の最長の一致データ列１４を対象として行うので、最初のスライド辞書領域４ａは、ファームウェア４の先頭から２バイトの領域となる。そしてこのスライド辞書領域４ａの直後に続く５バイトの領域が最初のデータ圧縮処理対象領域４ｂとなり、それぞれの領域のデータが、スライド辞書バッファ７ｃ及びパターン検索バッファ７ｂにセットされる。 First, as initialization processing in S1, the CPU 2 initializes the slide dictionary buffer 7c, the pattern search buffer 7b, and the like. Since the data compression process is performed on the longest matching data string 14 of 2 bytes or more, the first slide dictionary area 4 a is an area of 2 bytes from the head of the firmware 4. The 5-byte area immediately following the slide dictionary area 4a becomes the first data compression process target area 4b, and the data of each area is set in the slide dictionary buffer 7c and the pattern search buffer 7b.

次に、ＣＰＵ２は、Ｓ２に示される一致データ列（一致バイト列）検出処理を行う。具体的には、ＣＰＵ２は、パターン検索バッファ７ｂの先頭２バイトの検索データ列１３と、スライド辞書バッファ７ｃ内のデータ列を順次比較して一致データ列１４の検出を行う。一致データ列１４が検出された場合、引き続き順次検索データ列１３を、パターン検索バッファ７ｂの先頭から最大５バイトまで１バイトずつ増やし、最長の一致データ列１４を全て検索し、抽出する。この処理によって、最長の一致データ列１４の相対位置と、データ長が得られる。 Next, the CPU 2 performs a matching data string (matching byte string) detection process shown in S2. Specifically, the CPU 2 detects the coincidence data string 14 by sequentially comparing the search data string 13 of the first 2 bytes of the pattern search buffer 7b and the data string in the slide dictionary buffer 7c. When the matching data string 14 is detected, the search data string 13 is successively incremented by 1 byte from the head of the pattern search buffer 7b to 5 bytes at the maximum, and all the longest matching data strings 14 are searched and extracted. By this process, the relative position and the data length of the longest matching data string 14 are obtained.

次に、ＣＰＵ２は、Ｓ３に示されるように、上記の検出処理で得られた結果から、上記の検出処理が完了した検索データ列１３を変換するデータ形式を選択し、選択されたデータ形式に変換された単位圧縮データを圧縮済ファームウェア格納領域７ｄの最後尾に追加する。そして、ＣＰＵ２は、スライド辞書領域４ａの最後尾を処理が完了したデータ圧縮処理対象領域４ｂの検索データ列末部まで移動させ、スライド辞書バッファ７ｃの内容をこのスライド辞書領域４ａに対応した内容に更新する。 Next, as shown in S <b> 3, the CPU 2 selects a data format for converting the search data string 13 for which the detection processing has been completed from the results obtained by the detection processing, and converts the data format to the selected data format. The converted unit compressed data is added to the end of the compressed firmware storage area 7d. Then, the CPU 2 moves the tail of the slide dictionary area 4a to the end of the search data string in the data compression processing target area 4b that has been processed, and changes the contents of the slide dictionary buffer 7c to the contents corresponding to the slide dictionary area 4a. Update.

次に、ＣＰＵ２は、Ｓ４に示されるパターン検索バッファ更新処理を実行する。具体的には、次の一致データ列検出処理におけるデータ圧縮処理対象領域４ｂは、パターン検索処理が完了した検索データ列１３の直後から５バイトの領域となるので、パターン検索バッファ７ｂに検索データ列１３の直後から５バイトの領域の内容がセットされる。 Next, the CPU 2 executes a pattern search buffer update process shown in S4. Specifically, the data compression process target area 4b in the next matching data string detection process is a 5-byte area immediately after the search data string 13 for which the pattern search process has been completed, so the search data string is stored in the pattern search buffer 7b. The contents of the 5-byte area immediately after 13 are set.

そして、ＣＰＵ２は、ファームウェア４の最後までデータ圧縮処理が完了すると（Ｓ５でＹＥＳ）、データ圧縮処理を終了し、そうでない場合は（Ｓ５でＮＯ）、Ｓ２の処理に戻る。 When the data compression process is completed up to the end of the firmware 4 (YES in S5), the CPU 2 ends the data compression process. Otherwise (NO in S5), the CPU 2 returns to the process of S2.

以後、Ｓ２〜Ｓ５の処理を繰返し、圧縮済ファームウェア５が、圧縮済ファームウェア格納領域７ｄに生成される。 Thereafter, the processing of S2 to S5 is repeated, and the compressed firmware 5 is generated in the compressed firmware storage area 7d.

次に、上記Ｓ２における一致データ列１４の検出処理について再度図２を参照して説明する。ＣＰＵ２は、スライド辞書バッファ７ｃ内にパターン検索バッファ７ｂの検索データ列１３と一致する一致データ列１４があるかどうかを検索し、検索結果を所定の形式に従って出力する。一致データ列１４の検索においては、パターン検索バッファ７ｂ中の検索データ列１３について最長となる一致データ列１４を全て検索する。この場合において、検索データ列１３は、常にパターン検索バッファ７ｂの先頭データから始まるデータ列としている。なお、最長の一致データ列１４が複数検出された場合、その相対位置が２５６バイト以下のときには、相対位置が４の倍数となるものが優先的に選択される。 Next, the detection process of the coincidence data string 14 in S2 will be described with reference to FIG. 2 again. The CPU 2 searches the slide dictionary buffer 7c for a matching data string 14 that matches the search data string 13 in the pattern search buffer 7b, and outputs the search result according to a predetermined format. In the search for the match data string 14, all the match data strings 14 that are the longest of the search data string 13 in the pattern search buffer 7b are searched. In this case, the search data string 13 is always a data string starting from the top data of the pattern search buffer 7b. When a plurality of longest matching data strings 14 are detected, when the relative position is 256 bytes or less, the data whose relative position is a multiple of 4 is preferentially selected.

次に、上記Ｓ３に示されるデータ圧縮処理とスライド辞書更新処理の流れについて、図５を参照して説明する。図５は、データ圧縮処理を行って単位圧縮データを生成し、スライド辞書更新する工程を示す。 Next, the flow of the data compression process and the slide dictionary update process shown in S3 will be described with reference to FIG. FIG. 5 shows a step of performing data compression processing to generate unit compressed data and updating the slide dictionary.

まず、ＣＰＵ２は、上記一致データ列検出処理の結果、一致データ列１４のデータ長が、２バイト以上であるかどうかにより、データを圧縮処理するかどうかの判定を行う。ＣＰＵ２は、上記一致データ列検出処理の結果、一致データ列１４のデータ長が２バイト未満の場合は（Ｓ１１でＮＯ）、検索データ列１３の先頭バイトのデータを非圧縮データ形式１５ａに変換し（Ｓ１３）、データ長が２バイト以上の場合は（Ｓ１１でＹＥＳ）、第１圧縮データ形式１５ｂ又は第２圧縮データ形式１５ｃへ変換する（Ｓ１２）。 First, the CPU 2 determines whether or not to compress data depending on whether or not the data length of the matched data string 14 is 2 bytes or more as a result of the matched data string detection process. When the data length of the coincidence data string 14 is less than 2 bytes as a result of the coincidence data string detection process (NO in S11), the CPU 2 converts the first byte data of the search data string 13 into the uncompressed data format 15a. (S13) If the data length is 2 bytes or more (YES in S11), the data length is converted to the first compressed data format 15b or the second compressed data format 15c (S12).

第１圧縮データ形式１５ｂ又は第２圧縮データ形式１５ｃに変換する場合、上記一致データ列検出処理で検出された最長の一致データ列１４の相対位置によって、いずれかの圧縮データ形式が選択される。すなわち、ＣＰＵ２は、最長の一致データ列１４の相対位置が、４の倍数であり、かつ２５６バイト以下である場合は（Ｓ１２でＹＥＳ）、第２圧縮データ形式１５ｃの圧縮データ形式を選択し（Ｓ１５）、これ以外の場合は（Ｓ１２でＮＯ）、第１圧縮データ形式１５ｂの圧縮データ形式を選択する（Ｓ１４）。 When converting to the first compressed data format 15b or the second compressed data format 15c, one of the compressed data formats is selected according to the relative position of the longest matched data string 14 detected in the matched data string detection process. That is, when the relative position of the longest matching data string 14 is a multiple of 4 and is 256 bytes or less (YES in S12), the CPU 2 selects the compressed data format of the second compressed data format 15c ( In other cases (NO in S12), the compressed data format of the first compressed data format 15b is selected (S14).

非圧縮データ形式１５ａが選択された場合、ＣＰＵ２は、パターン検索バッファ７ｂの先頭の１バイトを、非圧縮データ形式１５ａのコピーデータ領域ＣＰにセットし、生成した単位圧縮データを圧縮済ファームウェア格納領域７ｄの最後尾に追加する。 When the uncompressed data format 15a is selected, the CPU 2 sets the first byte of the pattern search buffer 7b in the copy data area CP of the uncompressed data format 15a, and generates the unit compressed data in the compressed firmware storage area. Add to the end of 7d.

第１圧縮データ形式１５ｂが選択された場合、ＣＰＵ２は、最長の一致データ列１４の相対位置及びデータ長を、それぞれ位置データ領域ＰＯＳ及びデータ長領域ＬＮにセットし、生成した単位圧縮データを圧縮済ファームウェア格納領域７ｄの最後尾に追加する。 When the first compressed data format 15b is selected, the CPU 2 sets the relative position and data length of the longest matching data string 14 in the position data area POS and the data length area LN, respectively, and compresses the generated unit compressed data Added to the end of the completed firmware storage area 7d.

第２圧縮データ形式１５ｃが選択された場合、ＣＰＵ２は、最長の一致データ列１４の相対位置及びデータ長を、それぞれ位置データ領域ＰＯＳ及びデータ長領域ＬＮにセットし、生成した単位圧縮データを圧縮済ファームウェア格納領域７ｄの最後尾に追加する。 When the second compressed data format 15c is selected, the CPU 2 sets the relative position and data length of the longest matching data string 14 in the position data area POS and the data length area LN, respectively, and compresses the generated unit compressed data Added to the end of the completed firmware storage area 7d.

最後に、ＣＰＵ２は、スライド辞書領域４ａを後方にスライドさせて、スライド辞書領域４ａの最後尾を処理が完了したデータ圧縮処理対象領域４ｂの検索データ列１３の末部に移し、スライド辞書バッファ７ｃの内容をこれに合わせて更新する（Ｓ１６）。 Finally, the CPU 2 slides the slide dictionary area 4a backward to move the end of the slide dictionary area 4a to the end of the search data string 13 of the data compression processing target area 4b that has been processed, and the slide dictionary buffer 7c. Is updated accordingly (S16).

次に、上記のデータ圧縮プログラム３により生成され、図１（ｂ）に示す電子機器のＲＯＭ９上に搭載された圧縮済ファームウェア５のＲＡＭ１２へのデータ展開処理の流れについて、図６、図７を参照して説明する。図６は、圧縮済ファームウェア５のデータ展開の処理の流れを示す。図７（ａ）〜（ｃ）は、圧縮済ファームウェア５の単位圧縮データのデータ展開処理について、展開データの対応付けをデータ形式毎に示す。 Next, FIG. 6 and FIG. 7 show the flow of data expansion processing to the RAM 12 of the compressed firmware 5 generated by the data compression program 3 and loaded on the ROM 9 of the electronic device shown in FIG. The description will be given with reference. FIG. 6 shows a flow of data expansion processing of the compressed firmware 5. 7A to 7C show the association of decompressed data for each data format in the data decompression processing of the unit compressed data of the compressed firmware 5.

圧縮済ファームウェア５のデータ展開処理は、圧縮済ファームウェア５の先頭から最後まで、順に単位圧縮データ毎に処理される。なお、以下の処理は、ＩＰＬ１０内のデータ展開処理プログラムに基き、ＡＲＭＣＰＵ１１が実行する。 Data decompression processing of the compressed firmware 5 is performed for each unit compressed data in order from the beginning to the end of the compressed firmware 5. The following processing is executed by the ARM CPU 11 based on the data expansion processing program in the IPL 10.

まず、ＡＲＭＣＰＵ１１は、初期化処理として、現在の処理位置を示すリードポインタの初期値のセット、データ展開後のファームウェア４のサイズ等を取得する（Ｓ２１）。 First, as an initialization process, the ARM CPU 11 obtains the initial value of the read pointer indicating the current processing position, the size of the firmware 4 after data expansion, and the like (S21).

次に、ＡＲＭＣＰＵ１１は、リードポインタが指し示す単位圧縮データの第１ビットが「０」であるか否かを判定し、第１ビットが「０」である場合（Ｓ２２でＹＥＳ）、単位圧縮データが非圧縮データ形式１５ａであると判定して、非圧縮データ展開処理（Ｓ２４）に移り、第１ビットが「０」でない場合は（Ｓ２２でＮＯ）、次の判定処理を行う（Ｓ２３）。 Next, the ARM CPU 11 determines whether or not the first bit of the unit compressed data indicated by the read pointer is “0”. If the first bit is “0” (YES in S22), the unit compressed data is determined. Is uncompressed data format 15a, the process proceeds to uncompressed data expansion processing (S24). If the first bit is not "0" (NO in S22), the next determination processing is performed (S23).

更にＡＲＭＣＰＵ１１は、この単位圧縮データについて、第２ビットが「０」であるか否かを判定し、第２ビットが「０」である場合（Ｓ２３でＹＥＳ）、単位圧縮データが、第１圧縮データ形式１５ｂであると判定し、第１圧縮データ展開処理（Ｓ２５）に移り、第２ビットが「０」でない場合（Ｓ２３でＮＯ）、単位圧縮データが、第２圧縮データ形式１５ｃであると判定し、第２圧縮データ展開処理（Ｓ２６）に移る。 Further, the ARM CPU 11 determines whether or not the second bit of the unit compressed data is “0”. If the second bit is “0” (YES in S23), the unit compressed data is the first compressed data. When it is determined that the compressed data format is 15b, the process proceeds to the first compressed data expansion process (S25), and when the second bit is not “0” (NO in S23), the unit compressed data is the second compressed data format 15c. And the process proceeds to the second compressed data expansion process (S26).

上記Ｓ２４の処理において、ＡＲＭＣＰＵ１１は、非圧縮データ形式１５ａのデータについては、図７（ａ）に示すように、単位圧縮データ中のコピーデータ領域ＣＰから非圧縮データのみを抽出し、このデータ列Ｄ０をＲＡＭ１２上のファームウェア格納領域１２ａの最後尾に追加する。 In the process of S24, the ARM CPU 11 extracts only the uncompressed data from the copy data area CP in the unit compressed data for the data of the uncompressed data format 15a as shown in FIG. The column D0 is added to the end of the firmware storage area 12a on the RAM 12.

上記Ｓ２５の処理において、ＡＲＭＣＰＵ１１は、第１圧縮データ形式１５ｂのデータについては、以下のように展開処理を行う。すなわち、図７（ｂ）に示すように、ファームウェア格納領域１２ａにおいて、現在処理中の単位圧縮データ（図中の１５ｂのデータ）中の位置データ領域ＰＯＳ及びデータ長領域ＬＮに格納された相対位置、データ長に基き、データ展開済のデータの最後尾を起点として、（相対位置＋１）バイト分手前の位置を先頭とし、（データ長＋２）バイト分のデータ列Ｄ１を抽出して、抽出されたデータ列Ｄ１をファームウェア格納領域１２ａの最後尾に追加する。 In the process of S25, the ARM CPU 11 performs the decompression process on the data in the first compressed data format 15b as follows. That is, as shown in FIG. 7B, in the firmware storage area 12a, the relative positions stored in the position data area POS and the data length area LN in the unit compressed data (15b data in the figure) currently being processed. Based on the data length, the data string D1 for (data length +2) bytes is extracted by starting from the end of the expanded data and starting from the position before (relative position + 1) bytes. The data string D1 is added to the end of the firmware storage area 12a.

上記Ｓ２６の処理において、ＡＲＭＣＰＵ１１は、第２圧縮データ形式１５ｃのデータについては、以下のように展開処理を行う。すなわち、図７（ｃ）に示すように、ファームウェア格納領域１２ａにおいて、現在処理中の単位圧縮データ（図中の１５ｃのデータ）中の位置データ領域ＰＯＳ及びデータ長領域ＬＮに格納された相対位置、データ長に基き、データ展開済のデータの最後尾を起点として、［４×（相対位置＋１）］バイト分手前の位置を先頭とし、（データ長＋２）バイト分のデータ列Ｄ２を抽出して、抽出されたデータ列Ｄ２をファームウェア格納領域１２ａの最後尾に追加する。 In the process of S26, the ARM CPU 11 performs a decompression process on the data in the second compressed data format 15c as follows. That is, as shown in FIG. 7C, in the firmware storage area 12a, the relative positions stored in the position data area POS and the data length area LN in the unit compressed data (15c data in the figure) currently being processed. Based on the data length, the data string D2 for (data length + 2) bytes is extracted starting from the end of the data that has been expanded and starting from the position before [4 × (relative position + 1)] bytes. Thus, the extracted data string D2 is added to the end of the firmware storage area 12a.

現在処理中の単位圧縮データのデータ展開処理が完了すると、圧縮済ファームウェア５の最後までデータ展開処理が完了したかを判定し（Ｓ２７）、最後まで完了していない場合は（Ｓ２７でＮＯ）、リードポインタを次の単位圧縮データに更新し、Ｓ２２に戻る。 When the data expansion process of the unit compressed data currently being processed is completed, it is determined whether the data expansion process has been completed to the end of the compressed firmware 5 (S27). If the data expansion process has not been completed (NO in S27), The read pointer is updated to the next unit compressed data, and the process returns to S22.

そして、ＡＲＭＣＰＵ１１は、圧縮済ファームウェア５の最後に至るまで順次単位圧縮データのデータ展開処理を行い、圧縮済ファームウェア５の最後まで到達した時点で（Ｓ２７でＹＥＳ）、データ展開処理を終了する。このようにして、ＡＲＭＣＰＵ１１は、ＲＯＭ９上にデータ圧縮されて格納されていた圧縮済ファームウェア５を、ＲＡＭ１２上にデータ展開する。データ展開されたファームウェア４がＡＲＭＣＰＵ１１によって実行されることにより、電子機器８の初期化等が行われ、使用可能状態となる。 Then, the ARM CPU 11 sequentially performs the data expansion processing of the unit compressed data until reaching the end of the compressed firmware 5, and ends the data expansion processing when reaching the end of the compressed firmware 5 (YES in S27). In this way, the ARM CPU 11 expands the compressed firmware 5 that has been compressed and stored in the ROM 9 on the RAM 12. When the firmware 4 in which the data is expanded is executed by the ARM CPU 11, the electronic device 8 is initialized and becomes ready for use.

以上のようにして、本発明に係るデータ圧縮プログラム３によって、ファームウェア４をデータ圧縮することにより、次のような効果を得ることができる。すなわち、電子機器８の制御部に搭載されたＡＲＭＣＰＵ１１の有する命令モード（４バイトのＡＲＭＭｏｄｅ命令）の特徴により、ＡＲＭＣＰＵ１１が実行するプログラムコード中には、４バイト単位に同じデータが出現する割合が高いので、相対位置を４ビット単位とする位置データ領域を持つ第２圧縮データ形式１５ｃを用いることにより、位置データ領域のデータ量（ビット数）を少なく抑えることができると共に、データ圧縮率を高めることができる。また、ＡＲＭＣＰＵ１１が実行する命令コードでは、Ｃｏｎｄｉｔｉｏｎビットやオペコード固有のビット列は、上位側のビットに集中しているため、４バイト単位のデータの出現頻度は更に高まり、データ圧縮率を更に高めることができる。そして、出現頻度の低い命令その他のコードについては、従来のスライド辞書方式と同様な第１圧縮データ形式１５ｂを用いてデータ圧縮することとしているので、全体として従来のスライド辞書方式のデータ圧縮処理よりも高いデータ圧縮率（約６３％）を実現することができる。 As described above, by compressing the firmware 4 with the data compression program 3 according to the present invention, the following effects can be obtained. That is, due to the feature of the instruction mode (4-byte ARM Mode instruction) of the ARM CPU 11 mounted on the control unit of the electronic device 8, the same data appears in units of 4 bytes in the program code executed by the ARM CPU 11. Since the ratio is high, by using the second compressed data format 15c having the position data area whose relative position is 4 bits, the data amount (number of bits) in the position data area can be reduced, and the data compression rate Can be increased. In addition, in the instruction code executed by the ARM CPU 11, the condition bits and the bit strings specific to the operation code are concentrated on the higher-order bits, so that the appearance frequency of 4-byte data is further increased and the data compression rate is further increased. Can do. And, for instructions and other codes with low appearance frequency, data compression is performed using the first compressed data format 15b similar to the conventional slide dictionary method. Higher data compression ratio (about 63%) can be realized.

しかも、データ圧縮に用いるデータ形式はこれら２個の圧縮データ形式１５ｂ、１５ｃに加えて、非圧縮データ形式１５ａの３データ形式として、データ形式数を限定し、生成される圧縮コードは単純な構造となるように構成されているので、データ展開処理を行うに際しても簡単なアルゴリズムの処理ルーチンにより展開処理することができるので、高速なデータ展開処理を行うことができる。 In addition to the two compressed data formats 15b and 15c, the number of data formats is limited as the data format used for data compression, and the generated compressed code has a simple structure. Therefore, even when the data expansion process is performed, the expansion process can be performed by a simple algorithm processing routine, so that a high-speed data expansion process can be performed.

また、ＡＲＭＣＰＵ１１の４バイト命令モードによらず、複数種類の命令モードや処理単位を有するＣＰＵの処理特徴によって、プログラムコード中に所定間隔で出現する割合が高いデータ列に対して、現在の検索位置からの相対位置に応じた複数の圧縮データ形式を設定し、これらの圧縮データ形式を用いてプログラムをデータ圧縮することにより、圧縮コードの構成が単純な構成となり、従来と同等以上のデータ圧縮率を実現すると共に、簡単なアルゴリズムの処理ルーチンにより展開処理することができるので、高速なデータ展開処理を行うことができる。 Also, regardless of the 4-byte instruction mode of the ARM CPU 11, the current search is performed on a data string having a high rate of appearing at predetermined intervals in the program code depending on the processing characteristics of the CPU having a plurality of types of instruction modes and processing units. By setting multiple compressed data formats according to the relative position from the position and compressing the program data using these compressed data formats, the configuration of the compressed code becomes simple and the data compression is equivalent to or better than before Since the rate can be realized and the development process can be performed by a processing routine of a simple algorithm, a high-speed data development process can be performed.

なお、本発明は、上記各実施形態の構成に限られず、発明の趣旨を変更しない範囲で種々の変形が可能である。 The present invention is not limited to the configuration of each of the embodiments described above, and various modifications can be made without departing from the spirit of the invention.

（ａ）は、本発明の実施形態に係るデータ圧縮プログラムを動作させるコンピュータの構成図、（ｂ）は、同コンピュータにおいて生成された圧縮済ファームウェアを搭載する電子機器の制御部の構成図。(A) is a block diagram of the computer which operates the data compression program which concerns on embodiment of this invention, (b) is a block diagram of the control part of the electronic device which mounts the compressed firmware produced | generated in the computer. データ圧縮対象であるファームウェアと、スライド辞書方式に用いるデータの関係及び構成を示す図。The figure which shows the relationship and structure of the data used for the firmware which is data compression object, and a slide dictionary system. （ａ）は、データ圧縮処理で使用する非圧縮データ形式のデータ構造を示す図、（ｂ）は、同第１圧縮データ形式のデータ構造を示す図、（ｃ）は、同第２圧縮データ形式のデータ構造を示す図。(A) is a diagram showing a data structure of an uncompressed data format used in data compression processing, (b) is a diagram showing a data structure of the first compressed data format, and (c) is a second compressed data. The figure which shows the data structure of a format. データ圧縮プログラムによるデータ圧縮処理の流れを示すフローチャート。The flowchart which shows the flow of the data compression process by a data compression program. データ圧縮処理、及びスライド辞書更新処理のフローチャート。The flowchart of a data compression process and a slide dictionary update process. 圧縮済ファームウェアのデータ展開処理のフローチャート。The flowchart of the data expansion process of the compressed firmware. （ａ）は、非圧縮データ形式のデータ展開における展開データとの対応付けを示す図、（ｂ）は、第１圧縮データ形式の同対応付けを示す図、（ｃ）は、第２圧縮データ形式の同対応付けを示す図。(A) is a diagram showing association with decompressed data in uncompressed data format data decompression, (b) is a diagram showing the same association in the first compressed data format, and (c) is second compressed data. The figure which shows the same association of a format. （ａ）は、従来の電子機器の制御部の構成図、（ｂ）は、従来の組込み機器のファームウェアの格納状態を示す図。(A) is a block diagram of the control part of the conventional electronic device, (b) is a figure which shows the storage state of the firmware of the conventional embedded device.

Explanation of symbols

１コンピュータ
２ＣＰＵ
３データ圧縮プログラム
４ファームウェア（機器制御用ファームウェア）
４ａスライド辞書領域
４ｂデータ圧縮処理対象領域
５圧縮済ファームウェア
７ａファームウェア格納領域
７ｂパターン検索バッファ
７ｃスライド辞書バッファ
８電子機器
１３検索データ列
１４一致データ列
１５ａ非圧縮データ形式（第１のデータ形式）
１５ｂ第１圧縮データ形式（第２のデータ形式）
１５ｃ第２圧縮データ形式（第３のデータ形式）
ＩＤ識別データ領域
ＣＰコピーデータ領域
ＰＯＳ位置データ領域
ＬＮデータ長領域 1 Computer 2 CPU
3 Data compression program 4 Firmware (firmware for device control)
4a Slide dictionary area 4b Data compression process target area 5 Compressed firmware 7a Firmware storage area 7b Pattern search buffer 7c Slide dictionary buffer 8 Electronic device 13 Search data string 14 Match data string 15a Uncompressed data format (first data format)
15b First compressed data format (second data format)
15c Second compressed data format (third data format)
ID Identification data area CP Copy data area POS Position data area LN Data length area

Claims

In order to compress the device control firmware executed by the CPU having the 4-byte instruction mode,
Data holding means for holding the device control firmware;
A pattern search buffer that sequentially holds a data string (search data string) that is currently subject to data compression processing among the data strings of the device control firmware;
A slide dictionary buffer that holds data for a slide dictionary that is part or all of a data string that has already been subjected to data compression processing among the data strings of the device control firmware
A pattern search unit that searches the data in the slide dictionary buffer for a matching data string that matches a search data string in the pattern search buffer, and a firmware for the control device by a slide dictionary method using a search result by the pattern search unit In a data compression program for functioning as data compression means for compressing data,
The data compression means converts the device control firmware data into a first data format, a second data format, and a third data format,
Each of the first to third data formats has an identification data area for data format identification,
In addition to the 1-bit identification data area, the first data format has an 8-bit data area for holding data uncompressed,
In addition to the 2-bit identification data area, the second data format includes a 10-bit position data area indicating the relative position of the matched data string, and a 2-bit data length area indicating the data length of the matched data string And
In addition to the 2-bit identification data area, the third data format includes a 6-bit position data area indicating the relative position of the matched data string, and a 2-bit data length area indicating the data length of the matched data string And
The data compression means includes
Using the pattern search means, search all data strings that match the search data string in the pattern search buffer from the data in the slide dictionary buffer,
As a result of the search, if there is no data string in the data in the slide dictionary buffer that matches the 2-byte data string from the beginning of the search data string, the first byte of the search data string Generating data in the first data format based on the data;
As a result of the search, if there is a data string that matches the data string of 2 bytes from the beginning of the search data string in the data in the slide dictionary buffer, the longest data string among the matched data strings , It is determined whether or not there is a position in which the relative position from the current search position is a multiple of 4,
As a result of the determination, if it exists, data is generated in the third data format based on the longest matching data string,
As a result of the determination, when it does not exist, data is generated in the second data format based on the longest matching data string,
A data compression program for sequentially compressing data in the device control firmware.

In order to compress the device control firmware executed by the CPU having the 4-byte instruction mode,
  Data holding means for holding the device control firmware;
  A pattern search buffer that sequentially holds a data string (search data string) that is currently subject to data compression processing among the data strings of the device control firmware;
  A slide dictionary buffer that holds data for a slide dictionary that is part or all of a data string that has already been subjected to data compression processing among the data string of the device control firmware;
  Pattern search means for searching for a matching data string that matches a search data string in the pattern search buffer from data in the slide dictionary buffer; and
  In the data compression program for functioning as the data compression means for compressing the firmware for the control device by the slide dictionary method using the search result by the pattern search means,
  The data compression means converts the device control firmware data into a first data format, a second data format, and a third data format,
  Each of the first to third data formats has an identification data area for data format identification,
  In addition to the 1-bit identification data area, the first data format has an 8-bit data area for holding data uncompressed,
  In addition to the 2-bit identification data area, the second data format has a 10-bit position data area indicating the relative position of the matched data string and a data length area indicating the data length of the matched data string. And
  In addition to the 2-bit identification data area, the third data format has a 6-bit position data area indicating the relative position of the coincidence data string and a data length area indicating the data length of the coincidence data string. And
  The data size of the third data format is smaller than the data size of the second data format,
  The data compression means includes
  Using the pattern search means, search all data strings that match the search data string in the pattern search buffer from the data in the slide dictionary buffer,
  As a result of the search, if there is no data string in the data in the slide dictionary buffer that matches the 2-byte data string from the beginning of the search data string, the first byte of the search data string Generating data in the first data format based on the data;
  As a result of the search, if there is a data string that matches the data string of 2 bytes from the beginning of the search data string in the data in the slide dictionary buffer, the longest data string among the matched data strings , It is determined whether or not there is a position whose relative position from the current search position is a multiple of 4.
  As a result of the determination, if it exists, data is generated in the third data format based on the longest matching data string,
  As a result of the determination, when it does not exist, data is generated in the second data format based on the longest matching data string,
  A data compression program for sequentially compressing data in the device control firmware.