五ロ はじめて学ぶプロク、ラー ニンク、 List 3 プログラムの説明 それて、は , List 3 を簡単に説明します。コ メントを参考にしながらプログラムを読ん て、ください 引数のチェック ( 17 ~ 19 行目 ) を行ったあ と , 第 1 引数て与えられるファイルをテキス トファイル読み込みモードてオープンし ( 20 ~ 23 行目 ) , 第 2 引数て与えられるファイ ルをテキストファイル書き込み更新モード てオープンします ( 24 ~ 27 行目 ) 。 まず , 第 1 引数て与えられるファイル ( 仮 に Iist3. dat とする ) から int 型の数とカンマて、 区切られた文字列を別々に読み込みます ( 29 , 30 行目 ) 。それを第 2 引数て与えられる ファイル ( 仮に Iist3. srt とする ) に書式に従っ てコピーします。このプログラムては , 最 初の 6 カラムに数を書き込み , その後に ( カンマ ) を書き込んだ後 , さらに文字列を 書き込みます ( 31 , 32 行目 ) 。文字列はヾ \ n 〃 を含めて 73 カラムとします ( 合計 80 カラム ) 。 73 カラムに満たない文字列は後ろにスペー スを挿入して 73 カラムにします ( Fig. 2 参 照 ) 。 テキストファイルを行単位てソートする ために各領域 ( 1 行ずつ ) を同じ大きさにしま もし 1 行ごとにデータの大きさが ( つ まり , 読み込むデータと書き込むデータの 大きさが ) 異なっていると , テキストファイ ルを行ごとにソートしたときにデータがわ からなくなってしまいますね。 次に , 数字を基準にして単純選択ソート て行ごとに並び換えします ( Fig. 3 参照 ) 。ま ず , Iist3. srt をリワインドしてファイルポ インタを先頭にもってきます ( 35 行目 ) 。外 側のループの先頭を表すファイル位置を pout に保持して ( 37 行目 ) , list3. srt の第 1 行目の 数を bigge 「に , 文字列を big buf に読み込み ます ( 39 , 40 行目 ) 。 内側のループの先頭位置を pin に保持し ( 41 行目 ) , ファイル位置の更新用に pin を pout next に保存しておきます ( 42 行目 ) 。この内側 のループの先頭位置 pin は , 外側のループの はじめて学ぶ C プログラミング 125 / * 外側ループの次の先頭位置の保存 * / pout-next P ln : / * 単純選択ソートの内側のループ * / , &data ) ! ニ E0 F ) { / * 次の数の読み込み * / while ( fscanf( fout, fgets( buf, MAX, fout ) : / * 次の文字列の読み込み * / fgetpos( fout, &pin-next ) : / * 位置の取得 ( 内側ループの次の先頭 ) * / i f ( data > b i gger ) { / * 数の比較 * / fsetpos( fout, &pout リ / * 比較元のファイル位置の設定 * / fprintf( fout, "%6d,%s , daCa, buf ) : / * データの入れ換え * / fsetpos( fout, &pin ) ; / * 比較先のファイル位置の設定 * / fprintf( fout, "%6d,%s", bigger, big-buf ) : / * データの入れ換え * / / * 極大値データの入れ換え ( 数 ) * / bigger data; strcpy( big-buf, buf ) : / * 極大値データの入れ換え ( 文字列 ) * / fsetpos( fout, &pin-next ) : / * 位置の設定 ( 次の内側ループへ ) * / / * 内側ループの位置の更新 * / pin_next; clearerr( fout ) : / * EOF のクリア * / fsetpos( fout, &pout_next ) : / * 位 . 置の設定 ( 次の外側ループへ ) * / / * 外側ループのファイル位置の更新 * / pout = pout-next; / * ファイルのクローズ * / 42 : 43 : 44 : 45 : 46 : 48 : 49 : 50 : 52 : 53 : 55 : 56 : 57 : 59 : 60 : fc lose ( f i n ) : fclose( fout ) : 67 : / * ェラー処理をする関数 er r * / 68 : void err( const char *fi le-name ) char delext[ 9 ] : 70 : i nt i : / * プログラム名から、語尾 . EXE を削除する * / for ( i i 十十 , file_name 十十 ) 74 : 0 : *f i I e name ! = delext[ i ] *f i 1 e name : del ext [ i ] 76 : 77 : / * プログラムの使用法を stde rr に出力 * / 78 : fprintf( stderr, " 使用法 : %s filel d ・ irectry(fiIe2) く ret>Yn ” ex i t ( 1 ) : 80 : 82 : P ln delext ) : 80 カラム 73 カラム 6 カラム 0 C 0 0 E 0 tn 0 C N 0 0 CO っ ) 0 0 0 -c 0 C 0 0 0 0 0 Q) 6 0 4- っ 4 6 6 9 6 8 8 3 1 3 4 6 8 4 6 2 5 4 2 っ 4

型構造体も必要に応じて ma Ⅱ oc することに しましよう。 この凵 ST 型構造体がメモリ上て実際に双 方向リストを形成した状態を示したのが Fig. 3 , この双方向リストをヒープにアロケート して追加する操作をする関数が List 2 てす。 ところ <Fig. 3 をよく見ると , もう少し効 率を上げることがてきる点があるのてすが , わかりますか ? そうてす , p 汁てす。凵 ST 型 構造体も文字列データもいずれもヒープ上 にアロケートされるのてすから , わざわざ 別の場所に ma Ⅱ oc してポインタてさしてや るのてはなく , ひとつのデータ構造にまと めてやれば pt 「はいらなくなります。そのう えデータのアクセスもポインタを通すのて、 はなく直接参照になりますから多少は高速 になるてしよう。 しかし , C 言語ては可変長の構造体を宣言 する方法はありません。何とか C をごまかす という呼び出してアロケートされた構造体 は Fig. 5 のようになります。 このように , 構造体宣言の最後に要素数 Fig. 3 双方向リスト ・ Ptr SUCC ・ pred "data string 1 " ことがてきればいいのてすが・・・ こて 要素が 0 個の配列のテクニックを使うのて す。 このテクニックを使って書き直した構造 体が List 3 てす。ここて要素が 0 個の配列は サイズが 0 てアドレスだけをもっことを思い 出してください。 sizeof( 凵 (T) は dat [ 0 ] を 除いたポインタふたっ ( p 「 ed と succ ) の大き さになります。そのうえ , dat は構造体のメ ンバてすから , 凵 ST 型構造体 x に対して x. dat とすることがてき , Fig. 4 に示すアドレスと なります。このアドレスに文字列を保存す ることがてきれば , うまくごまかすことが てきるというわけてす。 この構造体を使って List 2 の allocList() 関 数を書き直すと List 4 となります。 ma Ⅱ oc の パラメータになっている式に注意してくだ さい。 sizeof ( 凵 ST ) のほかに必要になるエリ アの大きさは , 文字列データの長さ strl en(dat) とターミネータのヌル文字 ( ' \ 0 ' ) の 1 バイトて、す。文字列の長さは , 呼び出しの たびに違っていても , 最適な大きを計算 しますからムダはありません。 allocList("heIIo world") ; 118 CMAGAZINE 1990 11 Fig. 4 Fig. 5 構造体 x X. dat- → x. pred X. SUCC 訓 ocList でアロケートされた構造体 ” hello wo 日 d ” 1 —>dat → X. SUCC x. pred 双方向リストのテータ構造 0 の配列を入れておき , ma Ⅱ oc て文字列を含 んだ大きさの連続したメモリ領域を確保す ることて可変長構造体をシミュレートする ・ pred SUCC ・ ptr data string 2 ” sizeof(LIST) これをひとつの 構造体だと考える 1 : 2 : 3 : 4 : typedef struct 1 ist struct I ist struct I ist *pred; *SUCC : Char い ST : *ptr; / * 前へのリンク / * 次へのリンク / * データへのポインタ * /

Fig. ROM 化 0 考察 0T田0M と EPROM PROM の主流の品種は EPROM ( 紫外線 消去型 ) て、すが , 近年 , バイボーラ PROM の ように 1 回だけプログラミングて、き , 単価も 安い OTPROM ( ワンタイムプログラマプル ) も普及してきています。デバイス単価は EPROM より OTPROM のほうが安く , EPROM のようにデータをプログラミングす る前のイレーズ ( 消去 ) 作業の必要はありま せんが , 初期不良を取り除くため , スクリ ニング ( 高温べーキング ) という追加作業 が必要て、す。 Fig. 3 をみていただけると ,OTPROM は EPROM に比べ , プログラミング作業全体に 要する時間が多いことがわかると思います。 また , EPROM て、あればイレーザーと PROM プログラマが必要て、 , OTPROM の場合 , PROM プログラマとエージング装置が必要 - ーー 3.5 P/astic Leaded Chip Carrier 1 PROM の種類 Sma// Out/ine Package Lead/ess Ch1P Carrier て、す。 書き込み用ツ—) レ モリセルに照射することにより , メモリを ガラスの窓を通して波長 2537A の紫外線をメ EPROM 用イレーザーは , EPROM の石英 消去する装置て、す。普及型として 8 ~ 10 個を 同時に消せる小型のものから 300 個を同時に 消せる大型のものまて、 , 消去する個数別に PROM プログラマメーカーて、販売していま す (Fig. 4 参照 ) 。 PROM プログラマはマイクロプロセッサ を動かすための高級言語て、ある C 言語や BASIC て、作ったプログラムをマイクロプロ セッサにも理解て、きる機械語に変換した内 容を PROM に書き込む装置て、す。 PROM プログラマの種類としては , EPROM, バイボーラ PROM, PLD など多 品種に書き込め開発用に適している 1 個書き のユニバーサルタイプ (Fig. 5 参照 ) や EPRO M のみ多量に書き込めコストパフォーマン スにすぐれた , 量産ライン用に適している 8 ~ 16 個書きのギャングタイフ。があります (Fig. 6 参照 ) 。 田 OM プログラマの性能 現在普及している PROM プログラマは 1 個 書きのユニバーサルタイプ , 8 ~ 16 個書きの Fig. 2 小型化する ROM Current Approach 42.0 (32pin package) 物■圏劇・一一に■劇ー■に劇・ : 17.8 EPROM 十 Socket 2.8 42.0 15.2 Piastic DIP No Socket Change pattern layout 8 ℃ 4.5 SOP 14.1 2.6 OTPo 「 MROM OTP 十 MROM in SOP 特集 ROM 化プログラミング考察 77

次の先頭位置 pout next となっています。 list3. srt の 2 行目の数 data ( 44 行目 ) と文字列 buf ( 45 行目 ) を読み込みます。 内側ループの次の位置 pin next を確保しま す ( 46 行目 ) 。 data と bigge 「を比較して ( 47 行 目 ) , もし data のほうが大きかったら , pout の位置に data と buf を書き込み ( 48 , 49 行 目 ),pin の位置に bigger と big_buf を書き込 みます ( 50 , 51 行目 ) 。さらに , bigger と big buf のそれぞれに data と buf を代入して極大 値を更新します ( 52 , 53 行目 ) 。そして , 46 行目て確保した pin next を用いて , ファイル を元の位置 , つまり内側ループの次を指す ように設定します ( 54 行目 ) 。 これて、 , 単純選択ソートの内側のループ のファイル位置が , 次の位置 ( 行 ) を示すよ うになります。この処理を EOF まて、繰り返 すことにより Iist3. srt の第 1 行目には最大値 のデータが入ることになります。 内側のループを抜けた後 , ファイル終了 指示子の EOF 指示をクリアします ( 58 行 目 ) 。次に , 前に保持しておいた pout next を用いて , 外側のループて list3. srt の次の行 ( 2 行目 ) を指します ( 59 , 60 行目 ) 。 29 行目の fo 「ループて , list3. srt が i 行あることが求め られているのて , この外側ループを i ー 1 回繰 り返せばソートてきるのてす ( 38 行目 : i は i をデクリメントした値が式の値てすね ) 。 最後にファイルをクローズして , プログ ラムを終了します ( 63 , 64 行目 ) 。 関数 e 「「はプログラムの使用法を標準工ラ ー出力に出力してプログラムを終了します ( 68 ~ 81 行目 ) 。プログラム名を出力する際 に , 語尾 ! EXE" を削除しています。 関数 enter space は文字列の後ろにスペー スを埋め込み文字列 n 〃を含めて MAX ー 1 行にします ( 84 ~ 94 行目 ) 。 関数 fscanf について 文字列を入力するときに , fscanf("%d %s" &data, buf ) ; としなかったのはなぜてしょラか。わざわ ざ fge 熔を用いたのには理由があります。関 126 CMAGAZINE 1990 11 List 3 83 : / * スペースを埋め込む関数 enter_space * / 84 : void enter_space( char *s ) 86 : 88 : 89 : 90 : 92 : 93 : 0 0 i 十十 , S 十十 ) ー 2 : i 十十第 S 十十 ) = 0 : く MAX / * 改行コード ' Yn ' の付加 * / / * 文字列の終わり ( ・ \ 0 ・の付加 ) * S 十十 Fig. 3 単純選択ソート ( List 3 37 ~ 61 行目 ) big buf bigger 39 行目 40 行目 4 : 8 : 6 2 ー 4 ー K : u :mti : k : 0 ー 0 ー t : 0 : 44 行目 45 行目 data buf 47 行目で data と bigge 「の比較 , data のほうが大きいので pout の位置に data と buf を書き込む ( 48 ~ 51 行目 ) pin の位置に bigger と big-buf 外側ループ 1 内側ループ 2 内側ループ 1 外側ループ 1 pout 41 , 42 行目 P1n pout- next pi n-next bigger 52 行目 2 : 4 : 6 : 8 : 0 い 2 K ー u lm ⅱー k ー 0 ーー G ー 0 ー t ー 0 ー T ー 0 ー s : h : i 45 行目 44 行目 buf data このようにして 44 ~ 57 行目のループで一番大きいテータ bigge 「と big-buf を求める 外側ループ 2 内側ループ 1 / big-buf 53 行目 pout pout- next Ptn pi n-next ら 6 行目 46 行目 bigger 39 行目 big-buf 40 行目 4 : 6 : 8 0 : 4 い 2 K ー u lmli ー k ー 0 ーー G ー 0 ー t ー 0 lTlo Ⅲ : リ■ k 0 IT : a : h l,a : 「 45 行目 44 行目 data buf pout の位置をすらして 44 ~ 57 行目のループ処理を行うと大きい順に並び換 えが完成する 60 行目 41 , 42 行目 46 行目 pout Pln pout-next pin-next

ROM 化 プログラミング 考察 この方法は初期値をもっ変数が少ない場 値が必要な変数に初期値を設定します 0List て、きません。 4 て、は変数は初期値をもたない変数となりま合に有効て、 , コンパイラの生成するメモリ それて、は応用問題て、す。 List 2 のプログラ すから RAM 上に領域がとられるため書き換配置にそれほどくわしくない場合にも有効 ムは ROM 化てきるて、しようか 0List 2 のプ て、す。 ログラムて、は変数 data はスタック上に領域 えが可能となります。 を確保します。スタックは当然 RAM て、すか バッテリノヾックアップ領域や定数領域の参照 ら , 書き換えは可能て、す。したがって List 2 のプログラムは ROM 化可能て、す。 て、は同じような List 3 のプログラムは ROM 化て、きるて、しようか 0List 3 の変数 data は初 期値をもったデータとなり , ROM 上に置か れるため書き換えがて、きません。したがっ て ROM 化て、きないことになります。 初期値をもつテータに 対処する方法 初期値をもったデータが書き換えて、きな いといわれても , 初期値をもった変数を使用 する場合もあるて、しよう。その場合には以 下のような対処法があります。 ( 1 ) 初期化関数で初期値を設定する List 4 のような初期化関数を作成して初期 Fig. 4 C M ー 68K の C コンバイラの メモリ配置 lSt / * 生産オータ・数 Max. * / . 1 : #define NMAX 1000 2 : #define FALSE 0 ( ! FÅLSE ) / * 真 * / 3 : #define TRUE 4 : 5 : struct mc=const { / * マシン定数 * / 6 : uns igned udatal : 7 : uns igned udata2 ; 8 : 9 : uns igned udatan : 12 : struct order { char cdatal[ 5 ] : char cdata2[ 5 ] : 15 : char cdatan[ 5 ] : unsigned udatal : uns i gned udata2; uns igned udatan : 20 : 22 : 23 : struct mc_const *pconst 24 : struct order *porder 25 : int flagl, fIag2; 26 : 27 : void func() 28 : { 29 : i nt n ; 30 : if ( pconst->udata2 flagl : TRUE; 32 : 33 : e 1 S e flagl ニ FA し SE; 34 : for ( n = 0 ; n く NMAX; n + + ) { if ( porder[ n ]. udata2 36 : fIag2 ニ TRUE; e 1 se 38 : fIag2 ニ FA し SE; 39 : 40 : 41 : 42 : } / * 生産オー第 * / / * 入力テ、、一タ ( ASCII ) * / ( struct mc-const * ) 0X10000 し : / * マシン定数 * / / * 生産オー * / ( struct order * ) 0X20000 い 下位アドレス TEXT セグメント (ROM) ニ 200 ) DATA セグメント (ROM) DATA セグメントに生成 List 6 BSS セグメント (RAM) : DATA セク・メント * / / * datal int datal 2 : 3 : int func() static int data2 20 : 5 : 6 : func2( "stringsYn" ) : return( 0 ) : 8 : / * data2 : DATA セク・メント * / : DATA セク・メント * / / * "stringsyn" スタック領域 (RAM) 上位アドレス 特集 ROM 化プログラミング考察 39

可変長構造体 学 本ロ 0 五ロ 乗松保智 C 言語には実行時に大きさが決定されるような可変長の構造 体を作る構文はありません。しかし , 配列を使ったトリック でこれをシミュレートすることかできます。今回はこの可変 長構造体について説明します。また , 便利な ( ? ) マクロ集を おまけにつけます。 Fig. 2 int array[O] ; 要素 0 個の配列 たとえば int 型のオプジェクト 10 個からな る配列を使いたいときには , int ar 「 ay [ 10 ] のように宣言します。にと当〃てはさま れた定数が確保される要素の数を指定して なぜこのような ANSI 規格外の例をもち出 は配列の先頭の要素を指しています。 います。このときにはメモリ上には Fig. 1 の してきたかというと , 実は 0 要素配列を使う ては要素の数を 0 にするとどうなるてしょ ように配列の領域が割り当てられます。そ ことがてきるとちょっとおもしろいことが の大きさは sizeof(int) * 10 ノヾイトて , array てきるのてす。実際 , 多くの処理系は要素 int array [ 0 ] Fig. 1 intarray[lo]; と書いた場合てす。 Fig. 1 の要素の部分を 0 数 0 の配列を許します。 個にしてみると , Fig. 2 のようになります。 array → 長構造体 要素 0 個の配列の大きさは sizeof(int) * 0 てす から 0 バイトてす。つまり a 「「 ay はメモリ上に はまったく場所をとらないオプジェクトと こて頭の体操てす。 【問題】可変長文字列をデータとしても なり , そのくせ array 自身は存在しないオプ ジェクトの先頭アドレスを指していること つ双方向リストを表現するためのデータ構 造を考えなさい。 になります。 可変長文字列を効率よく保存するために これはいったいどういう意味なのてしよ うか。結論からいうと , 意味はありません。 は , ma Ⅱ oc ( ) 関数を使ってヒープエリアにデ ータを溜めていくのがよいてしよう。 ANSI 規格は要素数 0 の配列は許していない また , 双方向リストてすから , 文字列デ のてす。すくなくとも , ひとつの要素が必 ータのほかにもリストを構成するためのポ 要だということになっています。 これ インタがふたっ必要てすね。これらを考え ては , ここて話が終わってしまいますから , とりあえず ANSI 規格は忘れましよう。 ると List 1 のような構造体になります。凵 ST C 言語雑学講座 117 a 「「 ay →ー -4 要素は存在しない一 a 「「 ay は存在しないオプジェクトを指している a 「 ray は先頭の要素を指している

フォントは Fig. 1 のような文字フォントが 出力されます。また , 大きさを任意に変化 させた記述もて、きます。また , 少女丸文字 も混在させることがてきます。ただし , ひ らがな , カタカナに限定されています。別 に少女丸文字だからといって , おおきな文 字を使用て、きないということはありません。 これらのフォントはドライバが自動的に拡 大などを行い , 表示印刷するようにプログ ラムされています。 独自のフォントを使用したい場合はドラ イバの一部を C 言語て記述し , それを組み込 んて使用することすら可能なのてす。 ASCII 版日本語 Tex がフォントをドライバに依存 していることは , 大きなメリットになって いますが , 機種依存性を著しく高めるデメ リットもあります。この丸文字などの X68000 独自のフォントを使用した DVI ファイルを流 通させるのは避けるべきだと考えています。 ドライバて明朝体フォントのひらがな , カタカナを丸文字に置き換えて印字するこ とと , ソース自体てフォントを切り替えて 丸文字を混在させることは , まったく意味 が異なるのて、誤解のないようにお願いしま す。前者の場合は , TOWNS のドライバて も出力てきるはずてす ( まだ確認はしていま せん ) 。当然 , TeX の特長てある美しい数式 の出力も可能てす ( Fig. 2 を参照してくださ い ) 。また , 化学式を記述する chemTeX や 楽譜を記述するための MuTeX ( Fig. 3 を参照 してください ) もあります。 TeX はドキュメント処理システムとして は強力なのてすが , 絵などを挿入する処理 はあまり得意てはありません。そこて、 , \ special コマンドを用いて , ポストスクリプ トて図形を挿入することが行われています が , X68000 の TeX てはこの機能とは異なる Human68k の title. sys 形式のグラフィックデ ータを , この \special コマンドて挿入印字 することが可能 ( 当然 , 文書のポータビリテ ィはありません ) てす。 Fig. 4 を参照してください。このように美 しくグラフィックを挿入して使用すること もて、きます。この例てはちょうどドットの 白黒が反転していますのて、 , 反転挿入を指 定して取り込み印刷を行っています。 この機能も「 X68000 のグラフィック機能を TeX て、利用てきたら・・・・・」という願望から , 川本氏にお願いしてインプリメントしてい ただいた機能て、す ( 画像データから図形をう まく挿入するマクロを , 自動生成するプロ グラムを私が作る約束だったのて、すがいま ・ 0Fig. 4 の絵はそのプロトて挿入し だに・ ました ) 。 X68000 の TeX て、はこのようなドラ イバの拡張により下手なワープロより , 多 彩な表現が可能となっております。 TeX 辺のユーティリティ TeX のフォントを生成する METAFONT (METAFONT は Addison Wesley Publish ingCo. の商標てす ) は , 前述の前田氏の手に より X68000 に移植されています。 フォントを生成する作業は相当繁雑て、す が , これも川本氏の手により一連の生成作 業を自動て、行うバッチファイル群が公開さ れ , 作業は簡易になっています。ただ , 時 間が非常にかかるのて , 夜バッチを起動し ておき , 終夜作業てフォントを作成する方 もいらっしやるようてす。 GNU ダイジェストを TeX て、処理するマク ロバッケージ TeXinfo. TeX も GNU ソフトと ともに入手てきます。そのほかには dvi ファ イルを通常のプレーンテキストに , ある程 度 TeX て、フォーマットされたイメージを保 Fig. 1 使用フォント例 ( 180D 曰のドットプリンターで印字したもの。 360D 曰のプリンターで出力すればずっときれいになります ) 私の X68000 で現出来るフォントで、文章を少し書いてみます。 ゴチックフォントではこの対のようなフォントが出力されます。また、大きさを任 意に刻ヒさせてできます。これはゴチックの例ですが明朝体でも可す。い 邑ん、ゆういなしうじよまもしも屬在させることができます。ただし、レらな な、わタわナに限定はされています。別に蚌だからきなもじをで きないということはありません。これらのフォントはドライバが自動で等を行い、 表ー刷するよらにプログラムされています。 Conference Room 143

けて、も Fig. 8 のように数多く市販されていま す ( 注 2 ) 。また , LSIC-86 や ROMableC8086 のように C コンパイラに ROM 化ツールが付 属している場合も少なくありません。これ らは大きく分けると ①リンカが付属しており OB 」ファイルから H EX ファイルを生成するもの ② EXE ファイルから HEX ファイルを生成す るもの の 2 種類に分かれます。 OBJ ファイルから HEX ファイルを生成す るもののほうが各セグメントを特定のアド レスに割り付ける際の自由度が大きいのて、 すが , リンカが用意されているため , ROM 化ツールのバグが多い可能性があります。 筆者もその昔 , 86 系の ROM 化環境を構築し たときに OBJ ファイルから HEX ファイルを 生成する ROM 化ツールを採用しましたが , バグの多さに悩みました ( バグも一度対処法 を見つければその後はなんとかなるのて、す が ) 。そのためその後 , 再度依頼を受けて EXE ファイルから各セグメントを特定のアドレ スにロケートして HEX ファイルに変換する ツールを自作して活用してもらっています す。 ( 注 2 ) ( 注 3 ) 。 化ツールを使用するものとして話を進めていきま 以下では Fig. 8 に示すようななんらかの ROM 9 に示します ( コラム 1 参照 ) 。 MS ー C の標準的なセグメントの配置を Fig. M 5.1 のメモリ配置 きないことをお詫びいたします。 でに投稿すみであったため , 今回触れることがで ットに変換するツールはインターフェース誌にす す。筆者の作成した EXE ファイルから HEX フォーマ ( 注 3 ) 今回はこの ROM 化ツールの話は省略しま プログラムコードが置かれるセグメント て、す。この部分は当然 ROM 上に割り付けま す。スモールモデルとコンノヾクトモデルて、 は TEXT となり合計て 64K バイト以下になり ます。ミディアムモデル , ラージモデノレ , ヒ ュージモデルて、は f ⅱ e TEXT のようにファイ ル名 ( モジュール名 ) が付加され , モシュー ルごとに最大 64K バイトとなります。 FAR DATA セグメント 初期値をもった fa 「データのセグメントて、 す。ただし , static な fa 「データは初期値をも たなくてもクラスが 'FAR DATA' となりま Fig. 13 Fig. 14 ミティアムモテルのセグメントの配置 下位アドレス ↑ 个 DGROUP 上位アドレス 'CODE' 'DATA' 'BSS' ープ 'STACK' fa 「ヒープ —STACK near ヒ —BSS —DATA ???—TEXT コンノヾクトモテルのセグメントの配置 下位アドレス DGROUP ↓ 上位アドレス 'CODE' 'DATA' 'BSS' 'STACK' fa 「ヒープ —STACK —BSS —DATA —TEXT CS ファイルことに 64K バイト以下 <—DS, SS 64K ノヾイト以下 CS 64K バイト以下 DS 64K 八イト以下 64K ノヾイト以下 48 . TEXT セグメント CMAGAZINE 1990 11

す。以下の Fig. 10 ようなコーディングを行 うとこのセグメントが生成されます。 初期値をもたない③と⑤が混ざっている ため , 対処が難しくなりますが , ③と⑤の 書式を使用しなければこのセグメントを ROM 領域に割り当てることにより対処可能て、す。 FAR DATA セグメントの初期値を ROM に置 いてスタートアップルーチンて、 RAM 上に転 送するツールもあるようて、すが , そこまて、 する意味があるかどうかは疑問て、す ( fa 「デー タにするということは合計て、 64K バイトを超 えるような配列の可能性が高いため , ROM Fig. 15 Fig. 16 ージモデルのセグメントの配置 下位アドレス DGROUP 上位アドレス ???—TEXT —DATA —BSS —STACK far ヒープ ヒュージモテルのセグメントの配置 下位アドレス ???—TEXT ???—DATA —STACK far ヒー ↓ 上位アドレス 'CODE' 'DATA' 'BSS' 'STACK' 'CODE' 'DATA' 'STACK' プ ファイルことに 64K 八イト以下 1- ー D S 64K バイト以下 ↓ SS 64K 八イト以下 ファイルことに 64K 八イト以下 ファイルことに 64K 八イト以下 64K ノヾイト以下 注 ) 1 . ? ? ? ー TEXT などの ? ? ? はファイル名になる。 2. ???_TEXT セグメント : プログラムコード た範囲が 64K 八イト以下の設定になる。 セグメントが DGROUP に属するが , ー STACK セグメントまてを含め 3. スモールモテルとミティアムモテルでは一 DATA セグメントと一 BSS トに組み込まれている。 ただし , ヒュージモテルは一 BSS セグメントか ? ? ? ー DATA セグメン —BSS セグメント : 非初期化テータ ???—DATA セグメント : 初期化テータ ROM 化 考察 プログラミン トて、す。以下のようなコーディングを行う 初期値をもたない HUGE データのセグメン HUGE BSS セグメント 利用することがて、きます (Fig. 11 ) 。 数用の ROM が離れた位置にある場合などに に割り付けることがて、きるため , マシン定 FAR DATA セグメントは任意のアドレス になります ) 。 と RAM に二重に割り付けられメモリが無駄 FAR BSS セグメント ります。 このセグメントは RAM 上に置くことにな int huge fhugepub [Ox8000] : とこのセグメントが生成されます。 特集 ROM 化プログラミング考察 49 なコーディングを行うとこのセグメントが 定数の nea 「セグメントて、す。以下のよう CONST セグメント る必要はありません。 から , 転送するプログラムを新たに記述す ルーチンのソースリストが付属しています す。 ROM 化ツールては通常スタートアップ ーチンて、 RAM 上に転送する必要がありま め , 初期値を ROM に置きスタートアップル このセグメントは DGROUP に属するた func( " DATA" ) ; static int nea 「 fstatdat=10 ; int near fpubdat=10 : このセグメントが生成されます。 て、す。以下のようなコーディングを行うと 初期値をもった neari•—タのセグメント DATA セグメント 11 ) 。 る領域などに使用すると便利て、す (Fig. て、きるため , 生産オーダをバックアップす ントは任意のアドレスに割り付けることが HUGE BSS セグメントと FAR BSS±グメ ります。 このセグメントは RAM 上に置くことにな int fa 「 ffa 「 pub ・ このセグメントが生成されます。 て、す。以下のようなコーディングを行うと 初期値をもたない fa 「データのセグメント

キー x のハッシュ値 h ( x ) て示されるバケッ トがすてにふさがっている場合 , 再ハッシ ュ手順にしたがって , 次々と別のバケット を調べていきます。再ハッシュを k 回行って 得られるハッシュ値を hk(x) と書くことにし 再ハッシュ手順とは , バケット hl (x), h2 (x), h3 ( x ) ・・・・・・を順番に調べることてす。そ の途中て , 空のバケットに出会ったら , そ のバケットにデータをセットします。もし , 再ハッシュを B 回 ( B はバケットの個数 ) 繰り 返しても空のバケットが見つからなければ , ハッシュ表が満杯なのてこれ以上データを 登録することはてきません。 探索するときは , まずキー x のハッシュ値 h(x)< 示されるバケットを調べます。もしそ のバケットのデータが与えられたキーをも っているなら , それが探しているデータて す。そうてなければ , 再ハッシュの手順に したがって , バケット h1(x),h2(x),h3(x) ・・ を順番に調べます。与えられたキーをもつ データがあれば , そのデータが探している データてす。もし途中て空のバケットに出 会ったら , そのキーをもつデータは存在し ことになります。 再ハッシュの手順としてもっとも簡単な のは , hk(x) (h(x) + k) mod B とするものてす。これは , キー x の所属すべ きバケットから , 次のバケット , その次の バケットと順番に調べることを意味してい ます。 こて , オープンアドレス法はどのよう なものかを理解するために , 実際に簡単な 例を見てみましよう。 10 個のバケットをも つハッシュ表にデータを登録することを考 えます。ここて , キーの値が a て、あるデータ を「データ a 」と呼ぶと約束しましよう。デー タとハッシュ値の対応は Fig. 2 ( a ) のとおり てすが , そのうち a ~ e の 5 つのデータをこの 順序て登録します。 まず最初にデータ a ( キーの値が a てあるデ ータ。以下同様 ) を登録します。 a のハッシ 84 CMAGAZINE 1990 11 ュ値は 1 て、バケット 1 は空なのて , a をバケッ ト 1 に登録します。同様にして , データ b, c をそれぞれバケット 5 と 8 に登録します。 こまては , 衝突しないて無事にデータを登 録てきました。 次はデータ d の番てす。 d のハッシュ値は 5 てすが , これはデータ b と衝突します。そ こて再ハッシュを行います。先ほどの再ハ ッシュ手順から , hl (d) = (h(d) + 1 ) mod 10 ( 5 十 1 ) mod 10 6 となるのて , バケット 6 を調べます。このバ ケットは空なのて , データ d はバケット 6 に 登録します。最後にデータ e てすが , バケッ ト 6 はすてにふさがっているのて , 結局バケ ット 7 に登録します。ハッシュ表の内容は最 終的に Fig. 2 ( b ) のようになります。 この状態てデータ b を探索します。 b のハ ッシュ値は 5 なのて , まずバケット 5 を調べ ます。バケット 5 にはデータ b が登録されて いるのて , 探索は成功てす。 次にデータ e を探索してみます。 e のハッ シュ値は 6 てすが , バケット 6 に登録がされ ているデータは d てす。てすから , 再ハッシ ュ手順にしたがって , バケット 7 , 8 ・・・・・・を 順番に調べることになりますが , バケット 7 に e が入っているのて、 , 結局探索は成功し ます。 今度は , データ f を探索してみましよう。 f のハッシュ値は 6 てすが , バケット 6 にはす てに d が登録されています。てすから , 再ハ ッシュ手順にしたがって , バケット 7 , 8 ・・ を順番に調べます。バケット 7 , 8 にはそれ ぞれデータ e , c が入っていて , バケット 9 は 空なのて , データ f はハッシュ表には登録さ れていないことがわかります。 次に削除について考えましよう。チェイ ン法ては , 削除の操作は連結リストからセ ルを取り除くだけてす。これに対して , オ ープンハッシュ法ては削除は少しトリッキ ーになっています。 Fig. 2 ( b ) の状態からデータ d を削除してみ ます。ただたんにデータ d の入っているバケ ットを空にすると , Fig. 2 ( c ) のようになりま す。しかし , これては探索がうまくいかな くなります。たとえば , Fig. 2 ( c ) のハッシュ 表に対してデータ e を探索してみます。 e の ハッシュ値は 6 なのてバケット 6 を調べます が , そこは空になっています。てすから , こて探索は打ち切られてしまい , データ e は登録されていないことになってしまいま す。 この不都合を避けるには , バケットの状 態として「空」「データが入っている」のほか に , 新たに「削除ずみ」という状態を導入し ます。そして , データを削除するときには , バケットに「削除ずみ」という印をつけます。 探索を行うときには , 「削除ずみ」の印のっ いているバケットをスキップします。つま り , あたかも「バケットにデータが入ってい るが , キーの値が一致しない」かのように扱 うわけてす。 Fig. 2 ( b ) の状態からデータ d を削除する と , ( 正しくは ) Fig. 2 ( d ) のようになります。 こて , データ e を探索してみましよう。 e のハッシュ値は 6 てすから , バケット 6 を調 べます。バケット 6 には「削除ずみ」のマーク がついているのて , 次のバケット 7 を調べる とデータ e が見つかります。 挿入を行うときには , 「削除ずみ」のバケ ットは , 「空」のバケットと同様に扱います。 たとえば , Fig. 2 ( d ) の状態てデータ f を挿入 するとき , f のハッシュ値は 6 てすから , バケ ット 6 を調べます。バケット 6 には「削除ずみ」 のマークがついていますから , タ f を登録します。 プログラム オープンアドレス法の ケット ) はキーとデータからなります。つま プンアドレス法ては , ハッシュ表の要素 ( バ は KEY 型 , データは DATA 型とします。オー 書いてみましよう。先ほどと同様に , キー オープンアドレス法によるプログラムを