特集 3 ペク村レ量子化のレゴリスム 少し長いですが , Fig. 8 のようになります。 何が悲しくて , こんな複雑なことをする のでしよう。読者のおしかりを受ける前に G アルゴリズムの考え方を説明しておき ます。この手順はあとで参照してください。 画像の色をただ 1 色に量子化するなら , 色の重心を代表色に選びます。もし 2 色を 配分できるような場合 , どうしますか ? その場合は , どこでもいいから適当に 2 色 を決定します。これはふざけているわけで Fig. 6 階層型クラスタリングの処理手順 ( 1 ) すべての色に関して個数を数える ( 2 ) ある色に注目し , ほかの色との量子化誤差を調べる ( 3 ) 処理 ( 2 ) をすべての色に対して行う ( 4 ) 量子化誤差が最小となる色のペアと尸を探す ( 5 ) 0 と尸の重心色 / を求め , 夜と尸を削除してから / を加える ( 6 ) 色数がひとつ減る , 目的の色数に減るまで ( 2 ) へ戻って繰り返す 階層型クラスタリングのサンプルコード / / 階層型クラスタリングで色の集合を決定する #include <stdio. h> #include く string. h> #include <stdlib. h> #define NUM—COLOR 256 typedef struct tagBGRE{ unsigned char mg,r,e; BGRE ー typedef struct tagCRASTER { unsigned char b,g,r,reserved ・ unsigned 土 n セ pai てーP0町 unsigned ー ong pair—dif , n ー CRST ー / * 2 乗テーブル * / long POW2[ 256 long NumberOfCraster; / * クラスタ総数 * / / * クラスタ配列 * / CRST* crst ー BGRE bgre[NUM-COLOR]; / * 色集合格納用 * / VOid weight—median—color(CRST* dst, CRST* CRST* src2) { srcl , dst—>n = srcl->n 十 src2->n; dst->b = (srcl->b * srcl->n 十 src2->b * src2 dst—>g = (srcl->g * srcl->n 十 src2—>g * src2 dst->r = ( s て cl - > て * srcl—>n 十 s て c2 ー > て * src2 long square ( CRST* 引 pha , CRST* betha ) { て eturn 8W2 [ abs(alpha->b ー betha->b) ] 十 pow2[ abs(alpha->g - ] 十 pow2[ abs(alpha->r - betha->r) ] / / 重み付き量子化誤差を求める関数 卩 long distortion(CRST* cl, CRST* c2) CRST gamma; weight—median—col 0 て ( &gamma , cl , c2 return s し ( (double)square(cl,&gamma) ) * cl->n 十 sqrt( (doubIe)square(c2,&gamma) ) * c2->n ・ / / 全ての色同士での距離演算を行う、上限は NumberOfCraster / / で与えられクラスタは c て s セ [ ] で与えられると仮定している long find—best—pair—l st ( void ) ヨ unsigned long root—distortion = Oxffffffff; unsigned long 土乃 , de lta , て 00t ー POS 土 t 土 on = pu セ s ( ”クラスタの距離関係を解析しています ... ” fo て ( 土 = の土く NumberOfCraster; 土十十 ) { printf( ” parse %lu/%lu c 引 0 て基 r ” , i,NumberOfCraster); crst[i] . pair—dif = 0xffffffff; crst[i] . pair—pos = 0 ー fo て ( = j<NumberOfCraster; j 十十 ) { if ( 土 ! = delta = distortion(crst 十 j, 0 て s し十 if (delta く crst[i] . pair-dif) { crst[i] ・ pair—dif = delta; c て s し [ 幻・ pair—pos = お ヨ ヨ 物 return て 00t ー POS 土 t 土 on ー 3 〃色空間を最大 NUM-COLOR に併合する。 CRST* load-symb01(FILE* bmpfile, long* IpResult); void merge—coIor(FILE* bmpfile) long 土 , ,alpha'betha,remain; CRST gamma; / / ad ー s 川 bo Ⅱ ) は画像の読み込みを行う関数 if ( ! (crst = load-symbol(bmpfile, &NumberOfCraster) ) ) { puts( "Fatal error: no memory" 潺 曲 0 て t ( remain = NumberOfCraster ー alpha = find—best-pair—lst( while (remain > NUM-COLOR) { betha = crst[alpha] ・ pa 土て一 po 町 weight—median—co ー or ( &gamma , crst 十 a ー pha , crst 十 betha ); crst[betha] . n = memcpy(crst 十 alpha, &gamma, sizeof gamma); alpha = find—best—pair—2nd(aIpha, betha); remain— (i=j=0; 土 <NUM ー COLO 新土 + + ) { / * 色集合を転送する * / fo て if ( c て s セは ] . n = continue ー bgre[j] . b = crst[i] . bgre[jl ・ g = crst[i] て e [ j ] . て = crst[i] / / を返す、高速化の為に重心色を元の場所に書き戻してある long find—best—pair-2nd(Iong alpha, long betha) unsigned long root—di stortion = 0xff f fffff; unsigned long 土 , j,delta,root—position = 0 ー puts ( n クラスタを併合しています ... ″ for (i=0; i<NumberOfCraster; 土十十 ) { printf(" Merge %lu/%lu c 引 or 基て” , i,NumberOfCraster); if (crst[i] . n ー 0 ) continue ー if ( 土 ! = a lpha ) { if ( c て s セ [ 幻 . pair—pos ! = alpha & & crst[i] ・ pair—pos ! = betha) continue ー crst[i] . pair—dif = Oxffffffff; crst[i] . pair—pos = の fO て ( j=O; く NumberOfCraster; j 十十 ) { = Ⅱ crst [ ] . n - 0 ) continue ー delta = d 土 s セ 0 てセ土 on ( c て st 十 j , c て st 十土 if (delta く crst[i] . pair—dif) { crst[i] . pair—dif = delta; crst[i] . pair—pos = コー = alpha & & く alpha){ if (delta く crst[j ] . pair-dif) { crst[j ] . pair—dif = delta; crst[j ] . pair—pos = alpha ・ if (crst[i] . 土て一 dif くて 00t ー d 土 st0 て t 土 on ) { て 00 セー d 土 stO てセ土 on = crst[i] . pair—dif; root—position = 1 ー if (crst[i] . pair-dif くて 00 セー dist0 土 on ) { て 00 セー distor セ土 on = crst[i] . pair—dif; て 00 し一 POS 土セ ion = 土ー return root—position ー / / 距離の統計を更新、関数は最小の併合誤差をもつべアの添字 特集 3 べクトル量子化のアルゴリズム 65

第 卩 卩 ヨ 朝 ヨ ヨ 卩 LBG アルゴリズムのサンプルコード #include く stdlib. h> #include く stdio . h> #include く time . h> #include く math. h> / * G アルゴリズムで色集合を決定する * / static unsigned long POW2 [ 256L S / * 24 byte * / unsigned long count,differ; unsigned long bsum,gsum,rsum; unsigned char b'%r,e; typedef struct tagCRASTER { typedef struct tagBGRE { unsigned char } BGRE; static unsigned long previous—distortion; static int CO ー or—count ー static CRST crst[256]; static BGRE p 引 e とセ e ー tab 厄 [ 256 / * crst [ n ] の累積変数をクリアする * / VOid c ー ear—craster ( int n ) crst[n] . bsum = crst[nl . gsum = crst[n] crst[n] . count = 0 ー crst[n] . differ = の / * L アルゴリズム初期設定 * / void init—lbg—algorithm(void) int i ー previous—distortion = OXFFFFFFFF ・ col 0 て一 coun に = 25 randomize ( fo て ( 土 = 土く 25 研 i 十十 ) { . rsu.m ヨ ヨ 宿 3 3 卩 crst[i] . b = (unsigned)rand( ) 宅 25 研 crst[il . g = (unsigned)rand() 25 研 c て s 幻 . て = (unsigned)rand() 25 研 clear—craster(i); 8W2 [ 幻 = i * / * 2 乗計算の高速化の為に * / / * 現在の領域表の色をパレットに保管しておく * / palette—table[i] . e = palette-table[i] . r = crst[i] palette—table[i] . g = crst[i] palette—table[i] . b = crst[i] . fo て (i=0; i く 25 研土 + + ) { int i; void keep—pa lette ( void ) int find—color(int b, int g, int て , unsigned long* lpResult) * 迄は余裕で誤差の累積を保持できる。 * / * 緩和する為に 2bit の下駄を履かせておく。無符号 32bit 整数なら 300 万画素程度 / * 領域表 c て st [ ] から最も近い色を探す。誤差は平方根を取るが、整数化の誤差を unsigned long lval,minmum—distortion = OxFFFFFFFF ・ minimum—position = i; minimum—distortion = lval; if (lval く minimum—distortion) { 十 pow2[ 曲 s ( c て st [ 幻 . て - て ) 十 8W2 [ abs(crst[i] . g ー g) ⅳ引 = pow2[ abs(crst[i] . b ー b) fo て ( 土 = i く c 引 0 て一 coun 土十十 ) { 土 , minimum_position=O ー *IpResuIt = (unsigned long) if (lpResult) { unsigned long distortion; VOid sampIing(FILE* bmpfile) / * 画像ファイルから色を読み領域表から最良近似候補を割り出す * / return minimum—position ー sqrt( (double) (minimum-distortion くく 4 ) long current—location = ftell (bmpfile); fo て int b,g,r,x; 迂 ( ( て = getc(bmpfile)) = = EOF) break; if ()g = getc(bmpfile)) = = EOF) break; if ( (b = getc(bmpfile) ) = = EOF) break; 特集 3 ペク村レ量子化のレゴリスム / * 追加領域には重心色を代表値に設定 * / for (r=0,w=color—count; remain>0; remain——) if (remain > color_count) remain = color—count; remain = 256 - co て一 co 聞 / * 分割しても元の倍を超えない為に * / qsort(crst, color—count = W, Sizeof(CRST) , sort—subfunc); if (sum—of—differ) { *sum—of—differ = sumdif; } memcpy(crst 十 w, c て s に十て , sizeof(CRST) ); sumdif 十 = crst[r] . differ; 0 ) continue; if (crst[rl . count fo て ( w = て = のてく 25 て十十 ) { w,r,remain; unsigned long sumdif = の void update—craster(unsigned long* sum—of—differ) / * 余剰があれば現存工ントリを前に詰め、末尾に分割工ントリを追加 * / / * 実質的に使用しているエントリを数えて、余剰クラスタを求める。 * / て eturn 0 ー if ( lp->differ > rp->differ) return ー if (lp->differ く rp->differ) return 十 CRST* rp = (CRST*)r; CRST* ゆ = (CRST*) 嵭 土 n セ sort—subfunc ( const void* し const VOid* て ) / * 累積誤差の降順に整列する為の下請け * / fseek(bmpfile, current—location, SEEK—SET); crst[il . differ 十 = distortion; crst[i] . count 十 = 1 ー crst[i] . rsum 十 = (unsigned long)r; crst[i] . gsum 十 = (unsigned long)g; crst[i] . bsum 十 = (unsigned long)b; 土 = find—color(b,g,r, &distortion); c ー ear—craster ( て十十 . rsum / crst[r] . count; . gsum / crst[r] . count; crst[w] . b = crst[r] . bsum / crst[r] . count; / * 色集合を決定するモジュール。少なくとも色数が 256 色よりも color—count = w; while (r く color—count) clear—craster(w 十十 crst[w] . て = crst[r] crst[wl ・ g = crst[r] unsigned ー ong current—differ = OXFFFFFFFF ー void Ibg—main(FILE* bmpfile) * 多いという前提でエラーチェックを省いている。 * / INCREASE : update—craster ( &current—differ sampling(bmpfile); do { / * クラスタ数が 256 で安定する迄はここでループして色を増やす * / while い done){ init—lbg—algorithm( pu セ s ( ”画像をサンプリングしています ... ” int i,done = 0 ー while ( c 引 0 て一 coun しく 256 ) / * 以前よりも良い色集合が得られたらそれを覚えておく * / if (current—differ く previous—distortion) { previous—distortion = current—differ ー keep—pal ette ( / * ここからが重心に収束させていくステップ * / for printf( ″累積誤差は %lu です洋セ t て” , current—differ); sampling(bmpfile); for (current—differ=0, i=0; i く 25 i 十十 ) { / * 移籍により余剰色ができたら色を増やすステップへ戻る * / 0 ) { goto INCREASE; } if (crst[i] . count current—differ 十 = c て s し [ 幻 . differ; if (current—differ > previous—distortion) {done 十 break;} previous—distortion = current—differ; keep palette( 特集 3 べクトル量子化のアルゴリズム 67

ひつばく なく中間値です。これは量子化の際に評価 があるとすれば高いビットレートの量子化 ておくとメモリを逼迫し , ロードするとき の対象となるのは純粋なべクトル距離のみ ですが , 低い圧縮率を実現するためにべク に作ったのではかなり時間がかかります。 であり , 重み ( 度数 ) は常に 1 であると仮定 トル量子化を使う人はいないでしようから , こらへんはもう少し研究の余地がありそ されるからです。木構造べクトル量子化の 気にすることはないでしよう。 うです。 探索方法は近似的に最良の結果を得られま 注意すべきはべクトル木の格納のために 総和クラス分割法 す。これは選ばなかったほうの部分木に最 べクトル表の倍のメモリが必要となる点と , 良近似候補が存在していた可能性を否定で 木の形成に時間がかかるという点です。 きないからですが , この精度の劣化は量子 メモリについてはあまり問題にはならな 総和クラス分割法は , 変換表探索や木構 化損失によって大部分が相殺されます。し いでしよう。べクトル木はあらかじめ作っ 造探索のように精度の劣化を招きません。 たがって , 低いビットレートでの量子化に ておいてもよいし , べクトル表のロードの また計算時間も全探索よりは少なくなるの おいてはあまり間題にはなりません。問題 ときに作ってもよいのですが , 作り置きし で , 全探索を使う場合には , この手法を必 ず併用すべきです。 Fig. 10 木構造べクトル量子化の処理手順 べクトル距離は差の 2 乗和で与えます。 耳タコかもしれませんが , これは重要なこ 〇べクトル木の初期設定 とです。ある入力べクトルをベクトル集合 ( 1 ) べクトル表のすべてのべクトルを葉としてべクトル木に配置する のどれかの要素に量子化する場合 , 最良近 ( 2 ) 現存する節 ( ノード ) のなかで距離が最小となるべアを選ぶ 似べクトルは入力べクトルと近い場所に存 在します。当たり前ですね。距離が近いな ( 3 ) 新たに節を作り , そのペアを左右の枝べクトルとする らべクトル同士の成分も似た値をとるはず ( 4 ) 節のべクトルには , 枝べクトルの中間べクトルを持たせる です。これも当たり前です。ならば , 最良 ( 5 ) 元のペアを以降の探索から除外し , この節を表に加える 近似べクトルと入力べクトルの成分の総和 ( 6 ) 節がひとつ ( 根 ) になるまで ( 2 ) へ戻って繰り返す も近い値を持つはずですね ? つまりべク 〇木構造べクトル量子化の量子化手順 トル表の集合を成分の総和に従って分類 ( 1 ) 注目ノードをベクトル木の根とする し , おのおのをグループ化すれば最良近似 ( 2 ) 入力べクトルを節の左右の子べクトルと比較 候補は入力べクトルの成分の総和に近いグ ( 3 ) 距離の近いほうの枝に進む ループから見つかる確率が高くなります。 ( 4 ) それ以上たどれなくなるまで ( 2 ) に戻って繰り返す 総和クラス分割法は , この考え方が基本で ( 5 ) 入力べクトルを現在位置のべクトルに量子化する す。 賢明な読者はこういうでしよう。「総和 変換表探索を使ったサンプルコード / * 変換表を使う最良近似候補の探索 * / typedef struct tagBGR{ unsigned char b,g,r; } BGR ・ static unsigned short pow2 [ 256 ]; static unsigned char x ね t [ 4096 / * パレットから最良近似色を選ぶ ( 最良探索 ) * / int find—C010r(BGR* cc, int b, int g, int て ) unsigned long lval,diff = 0xffffffff; int i , pos ー fo て (i=0; 土く 25 研 i 十十 ) { lval = (unsigned long)pow2[ abs(b - cc[i] . b) 十 (unsigned Iong)pow2[ abs(g - cc[i] ・ g) 十 (unsigned Iong)pow2[ 曲 s ( て - cc は ] . て ) if ( ⅳ引く diff ) { pos = if ((diff = ⅳ引 ) = 0 ) break; 4 ヨ / * 画像を量子化する * / VOid decrease(FILE* tofile, FILE* bmpfile, BGR* cc) int c , b 円 , ら / * 最初に変換表を初期設定しておく * / fo て (c=0; c く 25 研 c 十十 ) pow2[c] ( て = のてく = 25 て十 = 17 ) fo て (g=O; g く = 25 g 十 = 17 ) fo て for ( トの b く = 25 b + = 17 ) { / * こで最良探索を行う * / xIat[ic4096(b,g,r)l find—color(cc, b,g,r); fo て if ( (b = getc(bmpfile) ) = = EOF) break; if ( (g = getc(bmpfile) ) = = EOF) break; if ( ( て = getc(bmpfile)) = = EOF) break ・ //putc(find—color(cc,b,g,r), セ ofi 厄 putc( x ねセ [ 土 C4096 ( b , g 洋 ) ] , し of e 生 を一 ス ン しイよ 1 よ 1 宀 十 の 9 ( ( ( ・ 1 4 = 2 土 .A てて 70 C MAGAZINE 2000 7

特集 3 ペク村レ量子化のレゴリスム の近いところから見つかりやすいのはわか った。しかし結局は全部のべクトルを調べ ることにならないか ? 」・・・・・たしかにこれ では時間を短縮できそうもありませんが 適当な段階で探索を打ち切れるとしたら ? たとえば , 総和が 1 だけ違うクラスに属 するべクトルとの距離が 1 未満になること はありえません。同様に , 総和が 2 だけ違 うクラスには , 距離が 2 未満となるべクト ルは存在しません。帰納的に考えて , ある 総和差のクラスに属するべクトルとの距離 が固有の距離よりも小さくなることはあり ません。だとすれば , クラスごとに全探索 を行い , 現在までに見つかっている最良近 似候補との距離がクラスに固有の距離より 小さくなれば , その時点で探索は完了です。 成分ができるだけ近い値になるよう平坦化 間を改善するかは情報によって異なります それよりも総和差の大きいクラスには , 現 すればよいのです。つまり , すべての成分 在の最良候補よりも距離が近くなるべクト が , フルカラー画像の 8 ビット減色に限定 差の絶対値の差が 1 以下であることを義務 ルは存在しないからです。 すれば , 全探索の半分程度の時間で探索を 付けます (List 5 ) 。 完了できるようです。これは LBG アルゴリ 成分の総和差に固有の最小距離の求め方 ズムでのべクトル探索に応用すれば , 量子 は簡単です。 2 乗和を最小とするには , 各 総和クラス分割法がどの程度まで探索時 総和クラス分割法を使ったサンプルコード 3 / * 総和クラス分割法によるべクトルの探索 * / #include く stdio. h> #include く stdlib. h> #include く string. h> #define DIM #def ine SAMPLE—BIT #def ine SAMPLE—MAX #define NCLASS #define CODEBOOK—SIZE ョ typedef struct tagCRASTER{ struct tagCRASTER* next; ヨ unsigned char sampIe[DIM]; unsigned long sumval [DIM]; unsigned long count,differ; CRST ー static CRST crst[CODEB(X)K. -SIZE] ,*index[NCLASS]; static long sumdif [ NCLASS ]; static int unsigned pow2[SAMPLE—MAX 十 1島 void init—table( ) unsigned long rem , div; int for ( 土 = i<SAMPLE—MAX 十 i 十十 ) pow2 [ 幻 = 土 * for (i=0; i<NCLASS; i 十十 ) { / * 総和の差に応じた最小誤差を出す * / rem = 土宅 DIM; div = 土 / DIM; sumdif[i] = DIM*div*div 十 2*rem*div 十 rem; Fig. 11 次近傍探索アルゴリズムの処理手順 ( a ) べクトル索引の初期設定 ( 1 ) コードブックの 1 べクトルに関して , ほかの全べクトルとの距離を求める ②索引表を割り当て , 距離の昇順にべクトル索引を整列する ( 3 ) 処理 ( 1 ) , ( 2 ) をすべてのべクトルに対して行う ( 4 ) べクトル表からゼロべクトルにもっとも近いべクトルを選び , Z と置く ( b ) べクトル索引によるべクトル探索 ( 1 ) 入力べクトル S と Z との距離を日とする ② Z に対応する索引表から . Z に近い順番にべクトル D を取り出す ( 3 ) D が Z よりも S に近ければ , Z を D に置き換えて ( 1 ) へ戻る ④距離 ZD が 2 日未満で , なおかっ距離 SD が日以上なら ( 2 ) へ戻る ⑤ Z を最良近似候補として終了 / * サンプル成分同士の差の 2 乗和を求める * / unsigned long て ms(unsigned char sl[ ] , unsigned char s2[ ] ) long unsigned sum = 0 ー int 土ー ヨ for (i=0; i く DIM; i 十十 ) sum 十 = (long)pow2[abs(s1[il ー s2 は ]) sum ー / * 一番近いべクトルを探してくる * / int find—vector(unsigned char sample[ ] ) unsigned long dif , memdif=0xFFFFFFFF ・ int i,absvaI,base=O,mempos=O; CRST* cc ー 1 fo て (i=0; 土く DI 場 i 十十 ) base 十 = sample[i]; fo て (absval=0; absval<NCLASS; absval 十十 ) { if (memdif く sumdif[absval ] ) break ・ cc = (base 十 absval く NCLASS) ? index[base 十 absvall : NULL• while (cc){ if ( (dif = rms(sample, cc->sample) ) く memdif) { mempos = CC - crst; = 0 ) break; if ( (memdif = dif) CC = cc—>next ー cc = (base-absval > = 0 ) ? index[base-absval ] : NULL ・ while (cc){ if ( (dif = rms(sample, cc → sample) ) く memdif) { = CC - crst; = 0 ) break; if ( (memdif = dif) CC = CC—>next ー / * 3 dimention / * 8bit sample / * 765 class / * 256 c 引 0 て / * 次のエントリへのポインタ / * べクトル代表値 / * べクトル成分の累積値格納用 * / / * 出現度数と誤差累積値格納用 * / 3 8 ( ( 1 くく SAMPLE—BIT) ー 1 ) / * 255 ( SAMPLE—MAX*DIM ) 256 / * べクトル表を更新する度に呼び出すこと * / void update—chain ( ) int i , j , / * 同じ総和値を持つ工ントリの芋蔓を作る * / memset(index, NULL, sizeof index); fo て (i=0; i<CODEW)K-. SIZE; i 十十 ) { fo て (k=0,j=0; j<DIM; 十十 ) k 十 = crst[i] . sampletjl; crst[i] . next = index[k]; index[k] = &crst[il; 特集 3 べクトル量子化のアルゴリズム 71

えでべクトル量子化します。単純に量子化 (T) やウェープレット変換など直交変換を 平均値分離正規化 VQ するだけでは復元の際に誤差が累積されて , かけて , 重みの同じ係数同士を個別にべク トル量子化します。しかし , 複数のべクト べクトル成分の平均値を求め , 成分値を とんでもないことになるので , べクトル標 平均値との差に変換したうえで , 差分だけ 本を読み込む際に隣接画素の距離が 1 とな ル表が必要となるので , プログラムを作る で構成されるべクトルを量子化します。平 る順番で画素を取り出します。ヒルベルト のはたいへんです。実際には音声符号化な 均値は DPCM などで符号化します。平均差 曲線などがよいでしよう。差分で構成され どに試験的に採用されているにすぎません。 はデルタと同様に出現頻度が 0 に偏る傾向 るデルタベクトルの次数を D とすれば , さ 特徴抽出べクトル量引ヒ らに成分の総和を加えた D + 1 次元のべクト を持つのでコードブック収録べクトル数を ルとして量子化します。デルタサムを加え 多くの画像から統計的なデータを抽出し 大幅に減らせます。しかし , 平均値 + べク るのは入口と出口で大幅な濃淡の変動を発 トル符号を同時に送出するために符号化の て作成した汎用コードブックを使う方法で 効率は悪化しますが , 平均値成分は圧縮し 生させないために , 差分の変動範囲を拘束 す。汎用コードブックはさらに情報源とな やすいデータなので深刻に考える必要はあ った画像に適用して , どの程度の頻度で参 しているのです。 りません。たとえば 4X4 画素の領域の平均 平均値分離正規化 VQ と違って平均値を 照しているかの統計をとり , 頻繁に使われ 色をとって ( 縦横 1 / 4 に縮小 ) , 縮小画像を 8 送出する必要がなく , 符号化効率は向上し ている候補だけを選び出して最終的な汎用 ますが , 処理時間が増加します。消極的な ビットに量子化してから Pi / GIF などの画像 コードブックとします。 デイザだと見ることもできるし , 直流成分 画像を量子化する場合は , 汎用コードプ 圧縮フォーマットで伝送することもできま を除去した交流分のみを圧縮する重み付け ックで量子化を行い , 量子化誤差の大きか す。この提案はコードブックの大きさを現 べクトル量子化だということもできます。 実的なサイズに拘束するための工夫だと考 ったべクトルだけを抜き出して特徴量とし , えられます。 これらで構成される小コードブックを作っ 重み付けべクトル量ヒ て汎用コードブックに連結した合成コード デルタ拘束べクトル量子化 これは Tw ⅲ VQ などでも採用される基本 ブックで量子化を行います。小コードブッ 技術です。具体的には離散コサイン変換 ( D 画像を直前画素とのデルタに変換したう クは出力される圧縮画像ファイルの付加情 報として符号化されます。 色差成分を間引く例 圧縮比も画質もよいのですが , 圧縮に時 間がかかるのが難点です。しかし , 何度も / * YUV に変換して色差を間引き 12 次元から 6 次元に減らす * / int round ( int 土 ) 画像を復元するが , 圧縮は行わない HTML if (i く 0 ) return の て eturn (i > 255 ) ? 255 プラウザなどに応用が期待できます。 CD- int g' int て ) void rgb2yuv(unsigned char yuv[ 3 ] , int b, ROM べースの百科事典などもよいかもしれ long sy = ( 十 19595L * r 十 38470 も * g 十 7471 も * b ) >> 1 の ません。 long su = ( -11052L * て - 21697L * g 十 32748 も * b ) 〉〉 1 研 long sv = ( 十 32756L * r - 27429L * g - 5327 も * b ) > > 1 研 ⅵ 0 ] = て 0 聞 d ( sy 潺 yuv[l] = round()u 十 128 ); yuv[2] = round()v 十 128 long biWidth ) load—sample(unsigned char* scanline' FILE* bmpfile' int unsigned char* bufl = malloc(biWidth*3); unsigned char* buf2 = malloc(biWidth*3); unsigned char tes し [ 3 * 4 int x,retval=EOF; if (bufl & & buf2) { fread(buf1,3,biWidth,bmpfiIe); fread(buf2,3,biWidth,bmpfiIe); fo て (x=0; x<biWidth; x 十 = 2 ) { rgb2yuv(test 十 0 , buf1[x*6 十 0],buf1[x*6 十 11,buf1[x*6 十 2] rgb2yuv(test 十 3 , buf1[x*6 十 31,buf1[x*6 十 4] ,buf1[x*6 十 5] rgb2yuv(test 十 6 , buf2[x*6 十 0],buf2[x*6 十 1] ,buf2[x*6 十 2] rgb2yuv ( test 十 9 , buf2[x*6 十 3],buf2[x*6 十 4] , buf2 [ x * 6 十 5 ] scanline[x*6 十 0] = test [ 0 / * YO * / scanIine[x*6 十 1] scanIine[x*6 十 2] scanline[x*6 十 3] (test[ll + test[4] + test[7]+test[10]) scanIine[x*6 十 4] (test[2] 十 test[51 十 test[8] 十 test[lll) scanline[x*6 十 5] 3 6 まとめ ページ数の都合で収録できなかった部分 は付録 CD - ROM に収録しました。本稿がさ らなる研究の呼び水となれば幸いです。 筆者はソフトウェアやアルゴリズムの特 午制度に反対しているひとりです。技術は 共有により価値を増幅でき , 独占は決して 人類の利益とはなりません。ゆえに本稿で 説明した技術はすでに特許が認可されてい るものを除いて , 特許の申請と認可を禁止 させていただきます。筆者は発案者として 技術の使用を許諾する権限を持ちますが , ほかの発明者の自由まで左右する権利は持 たないからです。この権利は著作権によっ 一三ロ if (bufl) free(bufl); if (buf2) free(buf2); retval; return 74 C MAGAZINE 2000 7

lndows 用 68000 工ミュレータの 仕組み プリケーションのなかで floa 皀 x の動作時間 呼び出します。 EX68 ではこの未定義命令を レーションを行うのではなく , ソフトウェ の占める割合に影響されるので , 通常のア 解釈する時点でフックし , 直接対応する アドライバをフックして List 13 のように Pen ードルーチンを実行するように プリケーションではほとんど変化が見られ ⅱ um 内蔵 FPU を呼び出す処理を行います。 Pentium コ この場合 , X68000 上のプログ ないと思います。しかし , 浮動小数点演算 これによって , 浮動小数点の演算において しています。 ラムからはこの未定義命令が MC68000 の組 を多用するレイトレーシングのようなプロ 高速工ミュレーションが可能になります。 グラムでは画像生成速度は 6 ~ 7 倍程度に上 X68000 では MC68000 の未定義命令 [ 注 4 ] を み込み命令であるかのように見えます。 X68 000 内のデバッガで浮動小数点の演算をス がる場合があります。 使い割り込みを発生させて演算ドライバを テップ実行すると単一の命令として動作し IOCS フックによるキーボード & マウス [ 注 4 ] MC68000 では未定義命令は将来の拡張用 ていることが確認できます。 と定義されているが , ソフトウェアによる拡張も インタフェイスの実現 想定されている。実際 , X68000 で演算ドライバ 以上のようにパフォーマンスの向上を狙 が行っているのがソフトウェアによる命令の拡張 こで行ったエミュレータによるフック処理 で , って IOCS をフックした場合の効果はどの程 キーボードとマウスの工、 ミュレーション はプロセッサ内の命令を拡張したことに相当す 度あるでしようか ? これは , X68000 のア では , 山 Pentium の FPU を使うことで浮動小数点演算を高速化する / / 浮動小数点演算ドライバをフックして pe れ t 土の FPU を使う / / do 面厄 long 間の相互変換用 typedef Ⅷ土 on ( double struct { long )dbls; / / 日。 long 間の相互変換用 typedef union { oa し f ・ struct 地 ng } f10 / 作 E00 ″ 0 = DO * DI C = 1 : e てて 0 て / / 号付き整数乗算 void 乢け -asm { = btr dword ptr tMPÜ. -srJ,bF6—C e てて 0 て mov eax,dword ptr [MPU. —dl 0 eax,dword ptr [MPU.—d 十 4] •x dl mov dword p セて CMPU 、—d],eax gts dword ptr tMPU. —srl ,bF6—C 起てて or れ oer て : //FEOI -asm { dword 0 セ r tMPU. ーSてしbを6ーC btr ;no e て ro て eax,dword ptr MPU. -dj ;d0 mov ecx,dword ptr U. ー d 十 4 ] ー dl moV ;test d1 ecx , ー 0 て ;zero divide ~ ! e て ror edx , edx XO て は lag ? 0 て nS om aec ;ff. .ff edx idiV [MPU. -å],eax dword ptr mOV jno noeg d 0 て d ptr [MPU. —srl ,bF6-C bts noerr : 精度門 db regl 洋 eg 土 n セ e てて一 MPU.—sr=MPU. —sr&(-1-F6—C-F6—V); regl. h=MPU. —d[0]; regl. I=MPU. —d 1 reg2. h=MPU. —d 2 ・ reg2. I=MPU. -d[3]; regl. d 十 =reg2. d ・ err=—s tatusfp ( ト 迂 ( e て r & ( ーⅧ D FLO 川ー 0 R 恥 ow ) ) —clearfp( MPÜ 9 ヨ = F6 ー if にて r&EM—OVERFLOWY MPU. —srl=F6—V; MPÜ. —d[0 :regl. h; MPU,—d[1 て egl ・ 11 //2c / / 倍精度減 void DSUB( ) db regl , て eg2; 土 n し e てて一 MPU. —sr=MPU. sr & ( ト F6 ー 0 6 ーⅵ朝 regl. h=MPU. ーa[0嵭 て egl. ト PU. ー d [ 1 で eg2. h ドÜ. ー d [ 2 ・ て eg2. ト U. ー d [ 3 ・ 一 regl. d-=reg2. d ・ e てて = sta usfp( if にてて & 7 ー UND を LO ー 0 LOW ) ) —clearf ( ) MPU. srfÄ_c ー if ( arr&EM- VERFLOW ) MPU,—sr =F6—V; 第 P び . ー引円 = = 0q1. h ー MPU. —d[l て egl. 嶹 〃 2d / / 精度乗 dbls て egl , て eg2 を 土 n し err ー MPU. —sr=MPU. ーSて&(ー1-F6ーC-F6こV場 regl. h=MPU.—d[0 reg1.l=MPU. —d[l reg2. h=MPU. —d 2 reg2. I=MPU. —d 3 ー regl. d*=reg2. d ・ err——statusfp ( if ( e て ( ーリ ND 駅 FLO ー OV をも OW ) ) -clearf ( ) ・ MPU. —s て f=F&_C; if ( err&EM-OVERFLOW ) MPU. —srl=F6—V; Ü. ー d [ 0 トて egl. MPU. ーd[1トてeg1. 嵭 庸精度 dbls regl,reg2; int e てて一 MPU. —sr=MPU. —sr& ( -1-F6—C-F6—V-F6—Z regl. h=MPU. —d 0 reg1.l=MPU. —d 1 reg2. h=MPU. —d[2 て eg2. I=MPU. —d[ 3 regl. d/=reg2. d ・ err= statusfp ( if ( 阯 r & ( ー UND 駅 FLO 川ー OV F も 0 ー ZEROD Ⅳ IDE ) ) clearf ( ) ・ üPU. srf=Fé C ・ if ()r て &EM—äEkODIVIDE) MPU. —srl=F6—Z ・ if ( err&EM- VERFLbW ) MPU. —sr =F6—V ー ー d [ 円 = , 0g1. MPU. MPU. -d[l = て egl. 嵭 0 / / 0 厄 a て 0 矼 y nom: •edx. eax/ecx に > d0 //cl ear cary overflow! ー error //clear cary 特集 2 Windows 用 X68000 工ミュレータの仕組み 55

用している方法は、、仮想のビデオ回路の垂直 仮想マシンの動作時間と実時間との同期が すが , 水平同期信号 31.5 lz は垂直同期信号 同期信号を利用して同期させる " というもの できたので , この時間を基準として , さらに 55.46Hz から計算して , 工ミュレータ内部の各デバイスの時間を合わ で , この部分が仮想時間と実時間との間を調 31500 / 55.46 = 568 せます。たとえば , 画面モードにより違いま となります。この場合 , 垂直同期期間のマス 停する基準になります。 インストラクションデコードテーブルの作成と登録 マルチメディアタイマによる速度調節 / / インストラクションデコードテープル ULONG inst—tta [ INSTTBLDEFJ; ULONG inst—tbI[INSTDEF]; buss—read byte—read[jMPTBLSIZE]; buss—read word—read[JMPTBLSIZE]; buss—read long—read[JMPTBLSIZE]; buss—write byte—write[JMPTBLSIZE]; buss—write word—write[JMPTBLSIZE]; buss—write long—write[JMPTBLSIZE]; ULONG word-read-adr[JMPTBLSIZE]; / / インストラクションデコード用のデーブルをイリーガルインストラクションで初期化する void s—i Ⅱ e ( void ) memset(inst—tbl, 0 ,sizeof(ULONG)*INSTDEF),' for (i 咢の土く = 5553 土十十 ) inst-tta[il=(ULONG)-t; inst—tblt0 十 IX—INSTJ = (ULONG) &illegal—instruction; #if DEBUG inst—tbItO 十 IX—DISAJ = (ULONG) &d—illegal; #endif inst—åndex=2 ー #define IX—INST 0 *define IX—DISA 1 #define IX—SRC 2 #define IX-READ 3 #def ine IX-DEST 4 #define IX—WRIT 5 #define IX—FLAG 4 #define SET-INST( 1 ) inst—tbl[ind 十 IX—INST] = (ULONG) PI #def ine DI SASS ( pl 土 ns セユはれd 十 IX—DISAJ ー = (ULONG) PI #define IDX edi #define IDX—INST4 (IDX 十 IX—INST*4) #define IDX—DISA4 ( IDX 十 IX—DISA*4) #define IDX—SRC4 ( IDX 十 IX—SRC*4) #define IDX—READ4 ( IDX 十 IX—READ*4) #define IDX—DEST4 (IDX 十 IX—DEST*4) #define IDX—WRIT4 ( IDX 十 IX—WRIT*4) #define IDX—OPT4 (IDX 十 IX—OPT*4) #define IDX—FLAG4 ( IDX 十 IX—FLAG*4) #define MOVEFLAG( 1 ) -asm mov eax,dwo て d ptr [ U. —sr ] —asm and eax, fffffff0h% —asm 0 て eax,dword ptr [ pl ] —asm mov dword p ヒて tMPU. —srl,eax #define nake -declspec( naked ) 〃インストラクションの検索テープルに領域を確保する ULONG cur-index; ÜLONG new—ind0(ULONG inst,ULONG size) inst-tta[inst]=inst-index*4 十 (ULONG)inst—tbI; cur—index=inst—index ー inst—index 十 =(size 十 1潺 return cur—index ー 〃マルチメディアタイマ void CALLBACK timer—int(UINT a,UINT b,ULONG c,ULONG d,ULONG e) 土 n セ土 , mode; ULONG sum; X6. timer.work=0; if ( (MPU. cycle. count 十 MPU. cycle. ℃肛)>0) time—count 十 X6. clk. time—synctttime—count&31)=MPU. cycle. C0リn切 / / 十 U. Cle. cur; dtime—count 十十一 draw-hi st [ dtime—count&127 ] =X6. vsync—up; MPU. cycle. count=0; if ( X6. c て tc. て eg [ 2 の & 0X10 ) / / 31k mode=l; //HRL ドットクロック切り替え else åf (X6. sys. てeg[7ー]&2) 〃 24k mode=2; 土 n し cl ock—base; if (X6. cfg—opt.mincIockY ock ー base = 1818 工 8 / cl ock—base=18181 if ( X6. cfg—opt. int—speed ト / / 55 一定速度スイッチ sum= for(i=0 ・土く 32 ・土十十 ) sum4=X6. clk.time synct[il ・ MPU. cycle. ibase=(sum7vsync—raée[mode * 10 if ( MPU. 0Y0 厄 . 土・ 0 = clock ー 00 * 2 / 2)} MPU. cycle.ibase= cIock—base*2/2); / / 固定速度 MPU. cycle. ibase= (cIock—base*10*2/20); if (X6. rtc. request) X6. system—reqYäb—INT-BREAK; / / 256k 〃 1.75M void clk: :start-timer( ) int cap TIMECAP c ー if timer-id) return ー cap=timeGetDevCaps(&tc, SizeOf(TIMECAPS) if (cap!=0) " タイマーが ULL MessageBox ' タイ一割り麥ません。基 0 タイ一を解放して 68 を再起動してください。 return ー //address //cur index / / fo て next nake void i-moveq( ) -asm { = 2 の fftsync<( int )tc. er 土 0 醴土 n ) sync=tc. wPeriodMin; X6. timer. div=20/sync; X6 北土 me て . work = timer—id=timeSetEvent ( c , tc. wPeriodMin , (void (—stdcall *ff{nsigned int,unsi ed int , unsi ned lon unsigned long,unsigned %ng) )timer—intt 0 , T?ME PER1bIC); if (timer-id==0) MessageBox ( NULL " time = 敗しました。タイマーを解放して 58 を再起動してください。 ー OK return ー init—synct ( void clk: :end—timer( ) (timer id) timeKillEvent(timer—id); timer—id=0; ー即値 mov eax,dword ptr [ IDX-READ4J mov ebx,dword tr [ IDX—SRC4) ーレジスタ Dx ・即値を Dx へ mov dword p して ebx ,eax ーフラグの合成 MOVEFLAG ( IDX—FLAG4 mov eax ー 4 ret / / テーブルに登録 void s-moveq ( void ) fo て ( 土 n datareg ま datareg く = 7 ー datareg 十十 ) for (int number = -12 number く = 12 number 十十 ) 土北 op ー code = 0X7000 十 (datareg くく 9) 十 (number& 0xff) ・ / / 2 次テーラル確保 int ind = new-ind0(op—code, IX-FLAG); SET—INST( i_moveq); / / 実行ルーチン登録 / / フラグ設定 SET-FSZ(ind 十 IX—FLAG number); inst—tbl[ind 十 IX—SRCf = (ULONG) &MPU. —d[dataregl; inst-tbl[ind 十 IX—READ] number; #if DEBUG DISASS(d—moveq); #endif 46 C MAGAZINE 2000 7

でメソッド呼び出し自身を同じ理由で中 22 i2d 実引数の評価 断終了する。 15 oad—l ( 1 ) k + m て , それぞれの実引数のコンバイル結果 myF00. baz(k + m. k* m); の呼び出しにおい Fig. 8 List 2 のコンバイル結果 このようすを list 2 で示そう。 list 2 をコン 変換が行われている。 各実引数の評価が終了した時点ですでに型 いる。ただし , 現行の SDK 系処理系では , の型に「メソッド呼び出し変換」が使われて に決定されたメソッドシグネチャの仮引数 仮引数に代入される時点で , コンパイル時 ード呼び出し」によって型変換される。この 果は , あとで述べる第 5 ステップ「実際のコ と順に評価される。かっ , 各引数の評価結 の伝統に従って , 実引数並びは左から右へ う ( 実引数が存在していればであるが ) 。 Java 次に , 実引数に指定された式の評価を行 ( 2 ) k * m 18 i21 17 iadd 16 iload—2 20 iload—2 19 iload—l 21 実引数の型変換 Java フロクラミングリファレンス 詳説 JDK 解体新 パイルし , その結果を JDK の jav 叩コマンド で J 、盟の機械語 ( バイトコード ) へ逆アセン プルして表示したのが Fig. 8 である。 で「 i21 」が「 int to long 」の型変換命令であり , 「 i2d 」が同じく「 int double 」の型変換命令で ある。このように , ひとつの実引数につい て式の評価とその結果の仮引数の型への変 換を行い , そのあと次の実引数の評価に移 行していることがわかる。 なお , 実引数評価が途中で中断終了した 場合には , それ以降の実引数の評価は行わ ず , 直ちにメソッド呼び出し自身を同じ理 由で中断終了する。 メソッドのアクセス可能性の検査 先に説明したように , あるメソッドがア クセス可能であるかどうかの検査はコンパ イル時に行っている。その結果アクセス可 能なメソッドだけを呼び出すようになって いるのだが , このチェックは実行時にも行 われることになっている。そうしなければな らない理由は , メソッドを呼び出す側のコ ードと , 呼び出されるメソッドを定義して いるコードとは , 必ずしも同じコンパイル単 位に属しているとはかぎらないからである。 たとえば , ふたつのコンパイル単位 ( ソー スファイルと考えてよい ) があって , 一方 ( FI. java ) で定義しているメソッド m を他方のフ ァイル ( .java ) のなかのコードから呼び出 しているとしよう。 .java をコンパイルす るには , F1.java をコンパイルしたクラスフ ァイルが必要になる ( それは必ずしも FI. / * も土Sし2. java * / * 実引数の型変換 class F00 ( protected VOid baz(long n, d0 面厄 d) ( System. 0uしPて土n凵n(”F00. baz(" 十 n 十” class L 土 s し 2 ( pub lic s し北土 c void main ( S セて加 g け args ) ( 土 n し k = 100 , m = 3 の F00 myFOO = new F00 ( 潺 myF00. baz(k 十 m, k * m); 1 16 C MAGAZINE 2 0 7 ”十 d 十つ” class とはかぎらない ) 。呼び出し側のコー ドが存在する F2.java をコンパイルした時点 では , FI. java のなかで定義される m はアク セス可能であり ( たとえば public 属性が与え られていた ) , したがって F2. java は支障な くコンパイルできたとする。ところがその あと F1.java を修正し , m がアクセス不可能 に書き換えられたとする。その場合 , F2. java をコンパイルしたクラスファイルが古 いバイナリのままであれば , それは m がア クセス可能であるとして呼び出そうとする こで矛盾が起きることになる。し ので , たがって , 実行時に何らかの検査が必要に なるのである。 メソッドのコードの特定 このステップが , latebind を実現する部 分であり , 詳細を Fig. 9 に示す。この部分の 言語仕様は , JDKI. 0 から 1.1 へとバージョン アップされる過程で変更を受けている。 両者のもっとも大きな違いとして , JDK 1.0 のメソッド検索ルールでは実行時のオプ ジェクトのクラス型 R からメソッド検索を 開始し , コンパイル時に決定した該当メソ ッドの定義クラス T までを検索の範囲と限 定していた。これに対して JDK 1.1 以降のル ールでは , クラス T とは無関係にルートク ラスである Object までを検索の対象とする ように変わったことである。 この変更の影響を , List3 で説明しよう。 List3 の a—d は , 四つの独立したコンパイ ル単位である。ただし , a ~ c までが一連の クラス階層を形成している。そして階層の 中間のクラス Bar においてメソッド hello が 定義されている。 List3d では , クラス Lis Bar 型の変数に List3Baz 型のインスタンス を代入し , それを通して he Ⅱ。メソッドを呼 び出している。このプログラムの動作結果 は Fig. 10 に示すとおりである。 以下の議論では List3. java は再コンパイ ルしないことを前提とする。まず , List 3b , 3c を修正して , それぞれ List3e, 3f とし , List3Bar.java で定義していた he110 メソッド を , クラス List3Baz へ移動させたらどうな

J a プログラミングリファレンス 詳説解体新ロ キだあキー 式 (Expression) ( 7 ) 第 38 回 オブジェクト指向言語として , Java におけるメソッドの呼び出しは非常に 重要な地位を占めている。前回はメソッド呼び出しに対するコンバイラの処 理について説明したが , 今回はその補足をしつつ , 引き続き説明を行う。 メソッド呼びし ~ コンパイル時の作業 オプジェクト指向言語は表現能力が高い といわれているが , その理由の一端として late b ⅲ d ⅲ g ( 遅延結合 ) があげられる。これ は , 実行時にどの型 ( クラス ) のオプジェク トを通じてメソッドを呼び出したかに応じ て , 具体的に呼び出すメソッドを定めるメ カニズムである。 Java の場合 , メソッド呼 び出しに関してコンパイル時に行われる作 業は , Fig. 1 の (a) に示したとおり , 大きく 三つのステップに分かれる。 メソッド名と呼び出し対象の型の決定 Java のメソッド呼び出しにおいてコンパ Fig. 1 メソッド呼び出しに関して必要な作業 ( a ) コンバイル時に行う作業 ( I) メソッド名と , そのメソッドを呼び出す 対象の型の決定 ( 2 ) メソッドのシグネチャの決定 ( 3 ) メソッド呼び出しの妥当性の検査 ( b ) 実行時に行う作業 . ( 1 ) メソッド呼び出しの対象となるオブジェ クトの特定 ( 2 ) 実引数の評価 ( 3 ) メソッドのアクセス可能性の検査 ( 4 ) メソッドのコードの特定 ( 5 ) 実際のコード呼び出し イル時にまず行うのは , メソッド名の特定 と , そのメソッドがどの型 ( クラスまたは インタフェイス ) に対して呼び出されるの かを決める作業である ( その結果 , 不正な 呼び出しと判断されることもある ) 。これは メソッド呼び出しの具体的な記述に依存す るため , ソースコードの解析が必要になる。 これについては前回詳しく説明した。 たとえば , 「 java. lang. Math. abs(x) 」という メソッド呼び出しでは , その時点で「 java 」 という識別子が変数として宣言されてい るかどうかで , 「 java. lang. Math 」の部分の 構文的な解釈が「フィールド名」なのか あるいは「型名」なのかが変わる。その結 果によって , メソッド「 abs 」を呼び出すべ き型が違ってくる。 このように , Java ではピリオドで識別子 を連結した被修飾名 (qualified name) を名 前として利用できるため , ある名前が与 えられたときに , それが何を意味してい るかの決定には意味情報 ( その時点でどの ような識別子が何と宣言されているか ) が 必要になる。 メソッドシグネチャの決定 次に行うのは , どのメソッドを起動する かを決定するために先のステップで決定さ れた呼び出し対象のクラス型あるいはイン タフェイス型の定義を検索し , 適用可能で アクセス可能なメソッドを探す作業である。 それには , メソッド名と実引数の型およ び個数の情報を用いる。あるメソッド呼び 出しに対して特定のメソッドが適用可能で あるためには , 以下の条件を同時に満たし ていなければならない。 ( 1 ) 実引数の個数が仮引数の個数に一致 していること ( 2 ) 各実引数が , 「メソッド呼び出し変換」 に従って仮引数に変換可能であること こで , 「メソッド呼び出し変換」が何で あるかについては前回に説明したが , 復習 のため Fig 認 ~ 4 に概要を示した。メソッド 呼び出し変換は代入変換の四つのルールか ら最後のひとつを削除したものであり , し たがって Fig. 2 の三つのルールは , 代入変 換のうち最初の三つのルールと同じである。 代入変換の削除された第 4 のルールは , Fi g. 4 に示したものだ。 Java ではサフィックス の付いていない整定数 ( たとえば「 10 」 ) の型 は , あくまでⅲ t である。したがって , もし も b が byte 型の変数とすると , 「 b = 10 」とい う代入は , int から b への基本縮小変換が こで , Java では暗黙の縮小 必要になる。 変換は一般的には禁止されているので , 本 来このような代入は「 b = ( b e ) 10 」と記すの が筋である。だが , このようなケースでい ちいち明示的にキャストして「 ( b e ) 10 」と 記すのはめんどうであるから , 代入されて Java プログラミングリファレンス詳説 JDK 解体新書 113

づ 0 グラミングの根朝 ハードウェア をメインメモリに置く方式 ・ページング方式 プログラムの構造に関係なく , プログ ラムを一定サイズに分割し ( これをベ ージと呼ぶ ) , 必要なページだけをメイ ンメモリに置く方式 セグメント方式は , プログラムがいまど このメモリを使っているかというセグメン トを意識したプログラミングが必要になり , これがけっこうやっかいです。 Wmdows で はページング方式が採用され , プログラム の物理的位置を気にせずにプログラミング 今回の仮想記憶の説明のなかに 終わりに できるようになっています。 106 C MAGAZINE 2 開 0 7 ガラス製の窓からメモリ IC のチップに紫 ・ EPROM 【 Erasable PROM 】 データを書き込める ROM ROM ライタという装置を使って , 任意に ・ PROM 【 ProgramabIe 日 OM 】 S などで使われる き込んでしまう ROMO 大量生産される BIO メモリ IC の製造時に記録するデータを書 ・マスク ROM クセス時間を高速化した DRAM データの出力時間を延長することで , ア ・ EDO DRAM 【 Extended Data Out DRAM 】 パソコンのメインメモリとして使われる は低速だが , 低価格。大容量化できるので , リフレッシュが必要なためアクセス時間 ・ DRAM 【 Dynamic RAM 】 モリなどに使われる は高速だが , 高価。小容量のキャッシュメ リフレッシュが不要なためアクセス時間 ・ SRAM 【 Static RAM 】 ◎メモリ旧の種類 ードウェアの重要な構成要素です。 は CPU やメモリと同様 , コンピュータのハ ディスクが登場しました。ハードディスク コラム 構造体のアライメント メモ屮 C には , 1 バイトずつアドレスが割 り振られていますが , CPU の種類によって 一度にアクセスできるバイト数は異なりま す。この CPU が一度にアクセスできるバイ ト数のことを「ワード」と呼びます。これは , 一般に C 言語の i 猷型に相当します。 すなわち , 16 ビット CPU では 1 ワード = 1 6 ビット ( 2 バイト ) , Pentium などの 32 ビット CPU では 1 ワード = 32 ビット ( 4 バイト ) とな っています。このため , 構造体のメンバも それぞれ 4 バイト単位に区切られていれば , アクセスがもっとも効率的に行えます。 コンパイラのオプションには , 構造体の メンバの隙間に空の領域を埋め込み , メン バの格納位置を 4 バイト境界に揃えるもの があります。 Visual C + + では , / Zp4 オプシ ョンを指定することで , 4 バイト境界になり ます (Fig. 4 ) 。 Fig. 4 4 バイト境界で格納されるメンバの例 ( Visua ℃ + + の場合 ) 構造体の宣 struct MyStruct{ short Mem1 : long Mem2; }val; メモリ上の配置 4 バイト 4 バイト 尼 p4 オプション 用語解説 外線を照射することで内容を消去し , 再度 データの書き込みが行える ROM ・ EEPROM 【 Electronic Erasable ROM 】 電気的に内容を消去し , 再度データの書 き込みが行える ROM ・フラッシュメモリ 一括してデータの書き込みや消去が行え る EEPROM0 安価なため , メモリカードな どで使われる ◎メインメモリの形状 ・ SIMM 【 Single lnLine Memory Module 】 複数のメモリ IC をひとつの基盤に装備し , 基盤の単位で数十 M バイトのメモリを増設 できるもの ・ DIMM 【 DuallnLine Memory Module 】 目的は SIMM と同じだが , 基盤の形状や セグメント方式で , セグメントをハード ・ロールイン / ロールアウト ◎仮想記憶 ピンの数が異なる vaI.Mem1 の領域 vaI.Mem2 の領域 で , アクセス時間を高速化する手法 個々のバンクを平行してアクセスすること 複数の単位にれをノヾンクと呼ぶ ) に分割し , メインメモリを独立してアクセスできる ・メモリインタリーブ ド I / 0 というものもある モリのアドレスに割り当てるメモリマップ 域を割り当てる。周辺機器との人出力をメ ションなど , 目的に応じて特定のメモリ領 S , OS , ビデオメモリ , およびアプリケー うに分割して使用するかを示すもの。 BIO CPU に接続されたメモリ全体を , どのよ ・メモリマップ ◎そのほか むこと スクからメインメモリに読み出す / 書き込 ページング方式で , ページをハードディ ・ページイン / ページアウト き込むこと ディスクからメインメモリに読み出す / 書