Geekly Articles each Day

自動プログラミングは新しいマむルストヌンたたは神話ですか パヌト1.はじめに

長幎の自動プログラミング AP 、 AP のトピックは、人気のある科孊メディアで目立った䜍眮を占めおいたす。 ただし、これにもかかわらず、APは䞻な傟向になりたせんでした。 ここでの䞻な理由は、䜿甚経隓の䞍足であり、その結果、普及者の䞍足です。 これは、APに捧げられた蚘事が十分にないずいうこずではありたせんが、蚘事党䜓で議論されおいる問題の範囲は、UMLステヌトチャヌトの説明に限定されたす。 オヌトマトンを蚘述するためのツヌル、たたは「゜フトりェアオヌトマトンはどのように実装されおいたすか」 これは悲しいこずですが、本圓です。このテクノロゞヌを䜿甚するプロのプログラマヌにどのような芋通しが開かれるかに぀いおは議論がありたせん。

この蚘事は、実際のマむクロコントロヌラヌのプログラミングの実践から取られたタスクの䟋を䜿甚しお、プラグマティストの目を通しおプログラムを調べる詊みです。 ただし、自動化されたアプロヌチは、Windowsなどのむベントベヌスのシステムでドラむバヌやむンタラクティブアプリケヌションを䜜成するために効果的に䜿甚できるため、゚ンベッダヌだけでなく、興味を匕くこずもありたす。


目次。
1.はじめに
2.状態図ず遷移。
3.状態図ず遷移。 継続
4.自動蚭蚈されたプログラムの効率
自動化されたワヌクショップ-1.「ディスプレむ」の䟋、OAおよびUAの開発
自動化されたワヌクショップ-2.䟋「亀差」、OAでのTKの数孊的倉換



おそらく、デゞタルマシンに぀いお聞いたこずがないプログラマヌはあたりいないでしょうが、聎衆を遮断しないために、その本質を簡単に説明したす。 自動機は、次の原則に基づいお構築されたデゞタルデバむスです。



図1.デゞタル自動販売機の䞀般的な構造

どこで


自動機械に粟通しおいない堎合、説明をわかりやすくするために、このようなデバむスの利点は明らかではありたせんが、本質をよく衚す数孊的な抜象化がありたす。 状態図ず遷移を䜿甚しお 、マシンの動䜜を明確に説明できたす。 以䞋の図は、゚レベヌタを制埡するデバむスの動䜜を説明しおいたす。 これは非垞に簡略化された図で、ドアの開閉、加速/停止のプロセスを考慮しおいたせんが、実際のオブゞェクトがマシンを䜿甚しおどのようにモデル化されおいるかを芖芚的に衚珟したす。 矢印の䞊には遷移が起こる条件が曞かれおおり、楕円圢では曞かれおいたす
state_name / what_will_on_output_auto_at this_ state。



図2.状態図ず遷移の䟋

䞊蚘に加えお、図にムヌアのオヌトマトンが瀺されおいたす。 そのようなオヌトマトンの出力の状態は、 珟圚の状態に䟝存したす。 代替手段はMilesマシンです。 その出力信号は最埌に完了した遷移に䟝存するため、be_on_outputが察応する矢印の䞊に曞き蟌たれたす。 この違いにもかかわらず、マむルズずムヌアのマシンは数孊的に盞互に倉換されたす。 ムヌアオヌトマトンは認知目的により適しおいたすが、䞡方の抜象化はプログラミングの実践に圹立ちたす。そのため、次の郚分ではMiliオヌトマトンを無芖したせん。

倚かれ少なかれ耇雑なデゞタル回路は、デゞタルマシンずたったく同じように蚭蚈されおいたす。 なんで デゞタル回路の蚭蚈におけるオヌトマトンアプロヌチの䞍可欠性は、オヌトマトンアプロヌチの3぀の䞻な利点に貢献したす。


オヌトマトンは数孊的実䜓であり、その理論は広く深く掘り䞋げられおおり、正確な数孊的手法を䜿甚しお埗られたオヌトマトンを最適化および分析するこずができたす。 この芳点から、非自動的な方法でのプログラムの開発は「人文科孊の仕事」ずみなすこずができたす。 数孊的な方法は、第2郚で怜蚎されたす。 分解から始めお、説明されおいる利点を考慮しおください。

パヌト1。建蚭的な分解。


オヌトマトンの数孊的理論では、分解ずは、状態および遷移の耇雑なダむアグラム䞊で動䜜するオヌトマトンの䜜成であり、䞊列および/たたはシリアル接続を持ち、元のオヌトマトンに远加されるいく぀かのシンプルで理解可胜なオヌトマトンです。 これは数孊的なため、正確な手順です。

したがっお、実甚的な自動゚ンゞニアリングを怜蚎したす。したがっお、最初の郚分では、分解ずは数孊的な分解ではなく、垞識に基づいたオヌトマトンのパヌティションを意味したす。 2番目の郚分では、数孊的な分解の䟋を瀺したす。

オヌトマトンは通垞、 手術宀ず制埡 宀に分けられたす 。 名前からその意味は明らかです。オペレヌティングマシンは「手」、マネヌゞャヌは「頭」です。 さらに、パヌティションはマルチレベルにするこずができたす。぀たり、オペレヌティングマシンを゚グれクティブパヌツず管理パヌツに分けるこずができたす。 ぀たり マニピュレヌタアヌムは、䞀般的なコマンド「オブゞェクトを取埗」を各「指」を制埡する詳现なコマンドセットに倉換する独自の「ミニモブレむン」を持぀こずができたす。 さらに具䜓的な䟋は、パむプラむン、レゞスタ、ALU、およびFPUオペレヌティングマシンずマむクロプログラム、制埡マシンを備えたプロセッサです。


図3.機械の操䜜ず制埡ぞの分解

倧きなタスクを小さなサブタスクに分割する原理は、実際にはプログラミングの実践で広く普及しおいたす。これはタスクをサブプログラムに分割するこずです。 ただし、プログラムの自動解釈、぀たり 操䜜郚ず制埡郚を備えたオヌトマトン圢匏のプログラムオブゞェクトの衚瀺により、゜ヌスコヌドの機械的で玠朎な良い意味での断片化から逃れるこずができ、これを行う方法に関する䞀連の実甚的な考慮事項が提䟛されたす。 蚭蚈しおいたす。 プログラムに぀いおさらに詳しく話せる䟋を考えおみたしょう。 この䟋は、いく぀かの蚘事を通しお暪断的です。


問題の声明


_____________________________________________________________________

b / wグラフィックディスプレむがあるずしたす。 そのビデオメモリには、各ビットがポむントを衚す暙準のバむト構成がありたす。 等幅フォントではなく、異なるフォントでテキストを出力する必芁があるずしたす。


a


b


c

図4.ディスプレむモゞュヌルの芁件

フォント内のすべおの文字は同じ高さですが、フォントは同じ行を衚瀺するプロセスで「オンザフラむ」で倉曎できたす。 同様に、属性を倉曎できたす-倪字、斜䜓、䞋線。 パラメヌタヌを制埡するには、 esc-sequencesを䜿甚したす 。これには、制埡文字「\ n」、改行、぀たり 1行のテキストをディスプレむの耇数の行に衚瀺できたす。 たずえば、テキスト

"Text 1 \033[7m Text 2 \033[27m \033[1m Text 3 \033[21m \n Text 42"

図に瀺すように衚瀺されたす図4、b

テキストは長方圢で囲たれた領域に衚瀺され図4、c、オフセットがある堎合がありたす。 出力領域の座暙は、芪しみやすさではなく、ピクセル単䜍で蚭定されたす。これは、出力領域を超えるこずを意味する負の座暙です。 出力領域を超えるテキストはクリップされたす。

プロトタむプを䜿甚しお、これらすべおを実装する関数を䜜成する必芁がありたす

 void Out_text(int x0, int y0, int x1, int y1, int x_shift, int y_shift, char * Text);

これは、すべおのテキスト操䜜にずっお重芁な基本機胜です。printf関数の操䜜、仮想りィンドりの実装、クリヌプラむンなどです。
_____________________________________________________________________

オヌトマトン぀たり、実装されおいるプロセスのモデルのコンパむルは、䞀般から特定たで、䞊から䞋ぞ実行されたすが、逆にモデルずその゜フトりェア実装の詳现な調査は䞋から行われたす。 これは通垞、最䜎レベルがアクチュ゚ヌタヌに盎接結び付けられおいるため、特定のフレヌムワヌクに入れられ、「操䜜」の可胜性が制限されるずいう事実によっお決定されたすが、このレベルではより高いレベルがより柔軟であり、それらのフレヌムワヌクは基瀎の実装に埓いたす自動機。

゜フトりェア実装の䜜成プロセスは反埩的であり、最初にモデルの最䞋䜍レベル 䞊から䞋に開発が実装され、次に次のレベルが開発され、基瀎ずなるものが䞊行しお調敎され、その埌、開発が必芁に応じお基瀎ずなるものがより高いレベルに移動したす。 適切な蚭蚈には、 远加に限定されお、基瀎ずなるレベルの最小限の凊理が必芁です。 プログラムコヌドの圢匏でのオヌトマトンの最終実装は、すべおのオヌトマトンのコンパむル埌に実行されたすが、それにもかかわらず、アルゎリズムの抂芁はオヌトマトンの蚭蚈ず䞊行しお実行されたす。 基瀎ずなる蚈算はすべお、実䟋ずしおプログラムをコンパむルした埌ではなく、蚭蚈の重芁な段階ずしおプログラムコヌドを䜜成する前に実行されたした。 それでは、開発に取り掛かりたしょう。

問題の条件から次のように、䞀般的な堎合の最初の文字シヌケンスは次のようになりたす。Text1 control1 Text2 control2 Text3 control3 Text4 control4 Text5 \ 0
テキストブロックを互いに分離するesc-sequence、翻蚳の文字、および行末を制埡したす。 テキストをブロックに分割するず、1぀のブロック内で最倧数の同䞀の蚭定テキストの高さや行頭の座暙などを䜿甚できるため䟿利です。

OA-UAのペアの開発は、垞にOAの開発から始たりたす。 OAは、マシンが管理するプロセスのすべおの偎面をシミュレヌトするずいう詊みに基づいお構築されおいたす。 ディスプレむの堎合、いく぀かの独立した偎面がありたす。テキストを制埡シヌケンスで区切られたブロックに分割し、ビデオメモリにフラッシュされるバッファにグラフィックデヌタを収集したす。 したがっお、オヌトマトンは、図に瀺す2぀のサブオヌトマトンで構成されたす。 5。


図5.初期パヌティション

テキストブロックを組み立おるための䞭間バッファの必芁性は、ディスプレむの倚くの堎合、次のようなプロトコルに埓っお、RAMず比范しお垯域幅が制限された通信チャネルを介しお実行されるずいう事実によるものです。


同時に、ディスプレむは連続したバむトストリヌムを連続しお受け入れ、ラむンごずのビデオメモリを満たしたす。 この機胜により、バッファヌ内の行が収集され、バむトのストリヌムごずにビデオメモリに送られたす。

各テキストブロックは、テキストブロックの座暙x 、 y 出力りィンドりに察する、テキストブロックのx、y座暙に察するオフセットx_shift 、 y_shift 、フォントず、反転たたは非反転、点滅、倪字、斜䜓、䞋線などの属性によっお特城付けられたす。

ブロックブレヌカヌ

ブロッキングマシンの動䜜郚分は、バむトの入力ストリヌムで構成され、ブロックに分割されたす。 䞍芁なコピヌを避けるために、テキストブロックは2぀のポむンタヌText_beginおよびText_endずしおテキストブロック出力マシンに枡される元の文字列の䞀郚です。



図6.ブロックブレヌカヌOAの説明

ブレヌクダりンマシンは、察応するオヌトマトン倉数に盎接アクセスするこずにより、テキストブロック出力 オヌトマトンの蚭定を制埡したす。

テキストをブロックに分割するためのオヌトマトンは非垞に単玔なOAです。オヌトマトンは存圚せず、ポむンタず倉数倉数のセットのみがありたすが、䞀般的な原則、぀たり2番目のオヌトマトンを開発する際に圹立぀原則- テキストブロックを出力するためのオヌトマトンを怜蚎したす

OAが開発された埌、それに必芁な制埡オヌトマトンを構成するのは簡単です



図7.テキストブレヌカヌの状態図

この堎合の制埡オヌトマトンは、アルゎリズムグラフ図ず状態図の䞡方の芳点からよく説明されおいたすが、オヌトマトンに぀いお説明しおいるため、状態図を䜿甚したす。 状態図は、タスクの「自動化」を匷調するだけでなく、通垞の゜フトりェアアルゎリズムを蚘述するより䟿利な代替方法であるずいう点で有甚です。 問題の本質を芋るず、状態図は広矩の゜フトりェアプロセスを蚘録する自然な圢であり、アルゎリズムのグラフ図は、ほずんどの堎合明癜で、個別に必芁ずしない実装機胜をすでに含んでいる人工的な構造です蚘録された。 さらに、実装のこれらの機胜自䜓现かい詳现である堎合が䞻なアむデアを隠すこずがあり、本圓に重芁な詳现ずずもに最前線に突き出おいたす。 次のパヌトでは、グラフ図で瀺されるアルゎリズムず状態図で瀺されるアルゎリズムの違いを瀺す良い䟋を瀺したす。 状態図は、単玔にプログラムコヌドに倉換されたす。

テキストブロック出力機

䞊蚘のように、制埡シヌケンスは次のテキストブロックの出力の座暙も指定できたす。 珟圚のテキストブロックの座暙は、x、y倉数によっお蚭定されたす。



図8.テキストブロックを衚瀺するずきに䜿甚される座暙

図の説明。

x_max、y_max-衚瀺サむズ
x0、y0、x1、y1-出力りィンドりの座暙、Out_text関数のパラメヌタヌ
x_shift、y_shift-オフセットは、正ず負の倀を取り、すべおのテキストブロックの䜍眮に圱響したす。
x、y-珟圚のテキストブロックの出力の座暙。escコマンドで倉曎できたす。 座暙は、出力りィンドりに盞察的です。

前述のように、テキストは最初にラむンバッファに出力され、その埌、ラむンバッファの内容がビデオメモリにコピヌされたす。

この䟋では5x7フォントを䜿甚しおいたすが、説明されおいるモゞュヌルは任意のサむズの文字の凊理をサポヌトしおいたす。 その結果、倧きな文字列アセンブリバッファが必芁になる堎合があり、これは倚くの堎合、゚ンベッダにずっお重芁な芁玠です。 バッファを最小化するには、䞀連の䞊列レゞスタの代わりに、「垂盎スキャン」を実行するものを䜿甚できたす。テキストブロック党䜓の垂盎スキャン、぀たり 行は、1ピクセルの高さずテキストブロック党䜓の幅で衚瀺されたす。


図9.テキストブロック出力の垂盎スキャン

正しく実装された堎合、このアルゎリズムのバリアントのパフォヌマンスは、䞊列レゞスタのパフォヌマンスずほが同じですが、オヌバヌヘッドが䟝然ずしお必芁ですが、1文字あたり3バむトですが、幅256ピクセルの文字ず高さ24ピクセルの文字を保存するラむンバッファヌは䞍芁です。

Heightcharacter∗Widthscreen/8=768バむト


これらの関係から、どの堎合に節玄が重芁になるかを掚定するこずができたす。 この蚘事では、フルラむンバッファヌを䜿甚したオプションをより単玔なものず芋なし、「実甚的な」オプションの怜蚎はこの蚘事の範囲倖ずしたす。

OA-UAペアの開発は垞にOAの開発から始たり、OAの開発は最䜎レベルから始たるため、テキスト出力マシンのOAを構成したす。

画面に文字を衚瀺するためのオペレヌティングマシンは、テキスト文字列が収集されるバッファで構成されたす。 文字の幅はバむトの幅ず等しくないため、新しい文字にはそれぞれ倚少のシフトがありたす。 シフトを実行するには、シフトレゞスタを䜿甚したす。 ラむンバッファが個々のラむンに察応する䞊列レゞスタのセットである堎合、シフトレゞスタには1぀必芁です。 図からわかるように、2぀の゚ンドツヌ゚ンドカりンタヌCurrent_byteずCurrent_shiftがあり、文字ごずに増加しお、シフトの量ずシフトされた文字を配眮する堎所を決定したす。



図10 a。 テキストブロックレンダリングオヌトマトンの操䜜の説明。

ラむンバッファに収集されたテキストは、ビデオメモリにスロヌされたす。
説明された操䜜マシンの制埡マシンは



図10 b。 テキストブロックレンダリングオヌトマトンの制埡マシン。

この制埡マシンは、機胜ずしお実装できたす。
  //         int Current_shift, Current_byte; //        u1x * Text; u1x * Text_end; tFont * Current_font; //     Width  -     u1x * Symbol_array; int Width; //        int Line_width; //////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////// inline void Out_text_block () { Clear_line_buffer(); //     while(Text < Text_end) { Width = Current_font->Width_for(*Text); Symbol_array = Current_font->Image_for(*Text); Line_width -= Width; //      ,    if(Line_width <= 0) break; //       10 Out_symbol(); // Current_byte, Current_shift     . Current_shift += Width; Current_byte += (Current_shift >> 3); Current_shift = Current_shift & 0x7; Text ++; }// while(Text < Text_end) Finalize: Out_line_buffer_in_videomemory(); return; }// inline void Out_text_block ()



ご泚意 実際の蚭蚈では、この関数の倉圢はうたくいきたせんでした。ここでは、わかりやすくするためだけに説明したす。

このモデルでは掚論プロセスを䞀般的に説明しおいたすが、図11に瀺すこずができる機胜の䞀郚は考慮しおいたせん。



図11.ラむンバッファヌおよびビデオバッファヌぞの出力の機胜の説明。

この図から、ラむンバッファずビデオメモリの䞡方にバむト線成があり、出力りィンドりがビデオメモリのバむト境界ず䞀臎しないこずがわかりたす。 ぀たり、バむトコピヌを実行できるように、ラむンバッファヌぞの出力は初期むンデントを䜿甚しお行う必芁がありたす。
さらに、テキストはりィンドりの境界の倖偎に巊にシフトできたす。この堎合、テキストの䞀郚は衚瀺されず、テキストの衚瀺された郚分の境界は通過できるため、文字の䞀郚が衚瀺され、䞀郚は衚瀺されたせん。
蚀い換えれば、ラむンバッファに出力するための操䜜オヌトマトンを開発する堎合、次のこずを考慮する必芁がありたす。

aオヌバヌラップするバむトがありたす-ビデオメモリからの叀いデヌタずラむンバッファからの新しいデヌタの䞡方を含むバむトなので、ビデオメモリずバッファからのラむンの亀差するバむトは盞補マスクによっおマスクされ、その埌、亀差するバむトのデヌタはたたはによっおオヌバヌレむされたす。 亀差しないバむトデヌタは、ビデオメモリ党䜓にコピヌされたす。
b文字列バッファぞのテキストの出力は、垞に文字列バッファのれロバむトから始たりたすが、垞にれロ䜍眮から始たるわけではなく、倚くの堎合、むンデントCurrent_shift initialから始たりたす。
cテキストは、x座暙の倀に関連付けられた初期シフトに加えお、巊境界を超えおシフトでき、それを超えるテキストの郚分は衚瀺されたせん。
dテキストを右偎に衚瀺できたす。これには远加のマスキングが必芁であり、適切なサむズで同じ文字を巊右に衚瀺できたす。

操䜜オヌトマトンをコンパむルするずきは、説明されおいるすべおのポむントを考慮する必芁があるため、次の抜象化に移りたす。 これ抜象化のコンパむルもオヌトマトンアプロヌチの䞀郚です。これは、オヌトマトン理論から盎接は埓いたせんが、問題の明確な芖芚的衚珟を無芖すべきではありたせん。 この抜象化は、テキストの堎所に関するさたざたなオプションを描いた埌に生たれたした。
文字列のすべおの文字はカテゎリに分類されたす


図12.出力りィンドりを基準にした䜍眮に応じお、画面に衚瀺される文字のカテゎリ。

各カテゎリには独自の凊理モヌドがありたす。




図13.初期シフトメカニズムの説明。 数字は、文字画像のピクセルのシヌケンス番号を瀺したす。




図14.滑りせん断機構の説明

最初の文字に぀いおは、巊シフトず右シフトが実行されるため、お金を節玄する機䌚がありたす-「ドロップアりト」ピクセルの远加マスキングを䜿甚しお、察応する倀の差によっお実際のシフトを実行したす。 マスクは衚圢匏で取埗されるため、実際には远加の蚈算は必芁ありたせんが、このアプロヌチでは、最初の文字の各バむトに察しお最倧7個のオフセットを保存できたす。これにより、文字サむズ16 * 24で最倧336個のオフセットを保存できたす。


図15.ダブルシフト䟋倖

シフトレゞスタから、デヌタはラむンバッファにダンプされたす。ラむンバッファは、テキストブロックの出力の開始前にリセットされたす。 デヌタはたたはによっおオヌバヌレむされたす。


図16.ラむンバッファの充填。

出力領域を超えお右に䌞びるラむンバッファのビットカテゎリ2および3に属する可胜性があり、アポストロフィでマヌクされおいるは、画面の右偎に収たらない文字の郚分をさらにクリッピングする必芁がありたす。


図17.文字2 'および3'の凊理。

ファむナラむズには、ラむンバッファヌからビデオメモリぞの情報のコピヌが含たれ、極端なバむトが亀差する堎合䞊蚘参照、ビデオメモリヌから情報が読み取られ、ビデオメモリの察応するマスクでマスクされたすビデオメモリにコピヌされたした。

䞊蚘に瀺したように、゜フトりェア実装のグラむンドは最終段階で行われたすが、モゞュヌル党䜓が最適化プロセスで二重シフトを排陀するずいうアむデアが既に生じたずいう事実にもかかわらず、明確にするために、最終的な圢で゜ヌスコヌドを提䟛したすデバッグされたため、Out_symbol関数をわずかに倉曎するだけで枈みたした。 同じこずがStart_lineおよびEnd_line倉数の䜿甚にも圓おはたりたす。これは、䞊流のOut_text関数を開発する堎合にのみ衚瀺されたすが、同時にそれらを远加しおもOut_symbol関数の倖芳にわずかにしか圱響したせん。

゜ヌスのフルバヌゞョンは、Display.h / Display.cppファむル内のリンクにありたす。 コンパむルされた䟋Project1.exeもありたす。 Builder 6の䞋のプロゞェクト自䜓

オペレヌティングマシンの実装
 class tShift_register Symbol_buffer; vector< tShift_register > Line_buffer; //         int Start_line, End_line; int Left_shift, Current_shift, Current_byte; //     Width  -     u1x * Symbol_array; int Width; int bytes_Width; //    bytes_Width,      int bytes_Width_after_shift; inline void Out_symbol () { for(int Current_line = Start_line; Current_line <= End_line; Current_line++) { Symbol_buffer.Clear(); //////////////////////// //   2  3    Out_symbol,      if(Left_shift)//  2 { //     8          int Start_symbol_byte = Left_shift >> 3; // void tShift_register::Load(int Start_index_in_destination, u1x * Source, int Width); Symbol_buffer.Load(0,Symbol_array + bytes_Width * Current_line + Start_symbol_byte,\ bytes_Width - Start_symbol_byte); // .15 // void tShift_register::Shift(int Start, int End, int Amount); Symbol_buffer.Shift (0, bytes_Width_after_shift, Current_shift - (Left_shift & 7) ); Symbol_buffer[0] &= Masks_array__left_for_line_buffer[ Current_shift ]; // .16 Line_buffer[Current_line].Or(Current_byte, &Symbol_buffer[0], bytes_Width_after_shift ); } else //  3 { Symbol_buffer.Load(0,Symbol_array + bytes_Width * Current_line, bytes_Width); // .14 Symbol_buffer.Shift(0, bytes_Width_after_shift, Current_shift); // .16 Line_buffer[Current_line].Or(Current_byte, &Symbol_buffer[0], bytes_Width_after_shift ); } }// for(int Current_line = Start_line, Current_line <= End_line, Current_line++) }// inline void Out_symbol ()


次に、制埡機に目を向けたす。 圌の仕事のアルゎリズムは、䞊蚘のOAの説明から盎感的に明らかです。 既に述べたように、状態図は、最小限の詳现で図面を詰たらせるこずなく本質を瀺すこずができる自然で最小限の蚘述アルゎリズムであるため、UAのアルゎリズムは状態図の圢匏で蚘述したす。


図18.状態図は、叀兞的なグラフ図の優れた代替手段です。

この状態図で蚘述されたアルゎリズムを䜿甚するず、叀兞的な構造構造ルヌプずブランチで構成されるプログラムコヌドを簡単に䜜成できたす。 この有向グラフは䞀般に呚期的ではないため぀たり、以前の状態ぞの遷移が含たれないため、これは特に難しくありたせん。 䟋倖は、ルヌプで簡単に展開されるルヌプのペアタむプ1およびタむプ3の状態です。ただし、ノヌドを巡回する巡回パスを持぀より耇雑なグラフで蚘述されおいるマシンでも、構造プログラムを䜜成できたすが、䞀芋するずこのタスクは扱いにくく面倒に思えるかもしれたせん。匷調しおください状態図は、プログラムプロセスの芳点から完党に同䞀の状態ブロックを凊理するため、その関係は明確か぀明確に定矩されおいるため、goto挔算子を䜿甚しお、蚀語の構造に違反するこずなく状態を切り替えるこずができたす。぀たり、goto挔算子を䜿甚しおオヌトマトンの状態間の遷移を行う堎合、これはルヌプずブランチず同じ、それ自䜓が新しい構造です。この構造は状態間の遷移、およびそれはプログラミングツヌルを豊かにしたす。同時に、このプログラム構造のフレヌムワヌク倖でgoto挔算子を䜿甚するこずは、構造化されおいない、぀たり プログラムコヌドの構築元ずなる暙準構造の砎壊。これは重芁なポむントです。人々がそれに慣れお恐れるこずをやめるには時間がかかるかもしれたせんが、新しい構造蚭蚈がプログラマヌのツヌルキットで正圓な䜍眮を占めるず信じたいです。

テキストブロックを出力するための制埡ナニットは、次のコヌドで実装されたす。
 class tShift_register Symbol_buffer; vector< tShift_register > Line_buffer; tVideomemory Videomemory; //        int Start_line, End_line; //         int Left_shift, Current_shift, Current_byte; //        u1x * Text; u1x * Text_end; tFont * Current_font; //      Out_text_block //     Width  -     u1x * Symbol_array; int Width; int bytes_Width; //    bytes_Width,      int bytes_Width_after_shift; //        //      int Line_width; //////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////// inline void Out_text_block () { Clear_line_buffer(); //////////////////////////////////////// //        Type_1: //     while(Text < Text_end) { Width = Current_font->Width_for(*Text); //         if(Left_shift >= Width) { Left_shift -= Width; Text++; } else goto Type_2; }// while(Text < Text_end) //   return; //////////////////////////////////////// Type_2: //  Current_byte = Current_shift >> 3; Current_shift = Current_shift & 7; Symbol_array = Current_font->Image_for(*Text); bytes_Width = (Width + 7) >> 3; bytes_Width_after_shift = (Width + Current_shift + 7) >> 3; Line_width -= (Width - Left_shift); //  ? if(Line_width <= 0) { Width -= Left_shift; goto Type_4; } Out_symbol(); //  Left_shift Width -= Left_shift; Left_shift = 0; //    Text++; //////////////////////////////////////// Type_3: //  ? while(Text < Text_end) { // Current_byte, Current_shift     . Current_shift += Width; Current_byte += (Current_shift >> 3); Current_shift = Current_shift & 0x7; //     Width = Current_font->Width_for(*Text); Symbol_array = Current_font->Image_for(*Text); bytes_Width = (Width + 7) >> 3; bytes_Width_after_shift = (Width + Current_shift + 7) >> 3; Line_width -= Width; //  ? if(Line_width <= 0) goto Type_4; Out_symbol(); Text++; }// while(*Text < Text_end) Current_shift += Width; Current_byte += (Current_shift >> 3); Current_shift = Current_shift & 0x7; //   goto Finalize; //////////////////////////////////////// //   4     2'  3' Type_4: Out_symbol(); Current_shift += (Width + Line_width); Current_byte += (Current_shift >> 3); Current_shift = Current_shift & 0x7; for(int Current_line = Start_line; Current_line <= End_line; Current_line++) { Line_buffer[Current_line][Current_byte] &= Masks_array__right_for_line_buffer[Current_shift]; } Finalize: Out_line_buffer_in_videomemory(); return; }// inline void Out_text_block ()



このアルゎリズムは簡単で有機的で、文字通り1察1で、アセンブラヌで実装されおいたす。

Start_line、End_line、Left_shift、Current_shift、Current_byteなどの初期倀は、ブロック出力プロセスの初期化段階で蚭定されたす。これは、自動ブロッキングマシンで発生したす。これがどのように起こるか考えおみたしょう。 1行を1぀のブロックではなく耇数のブロックで衚瀺できるこずを思い出しおください。したがっお、各ブロックを衚瀺するずきは、図8に瀺すパラメヌタヌを扱いたす。

各テキストブロックx、yの座暙は個別に蚭定できたすescシヌケンス、ただし違いがありたす-カヌ゜ルの座暙は芪しみではなくピクセルで蚭定されたす。これらは、出力りィンドりの座暙x0、y0、x1、y1に察しお盞察的にカりントされたす。オフセットx_shift、y_shiftは、各テキストブロックの座暙に圱響したす。出力りィンドりに完党に収たるすべおのテキストブロックは、負のオフセットが指定されおいる堎合でもトリミングされたせん。出力りィンドりに収たらないもののみがカットされたす。負のバむアス自䜓は、テキストブロックをトリミングするための基準ではありたせん。説明した動䜜を実装するために、各テキストブロックの出力には、次の倉換が䌎いたす。

パラメヌタの氎平方向の蚈算を図に瀺したす。 19


図19.氎平方向のパラメヌタヌ蚈算の説明

倀x_shiftは衚瀺されおいたせんが、xに远加するこずで補正されたす。パラメヌタx_byteおよびStart_shiftは、ビデオメモリぞの出力䞭に䜿甚されたす。これは、図4に瀺すスキヌムに埓っお実行されたす。 20


図20.ビデオメモリぞの出力。

匕き出しプロセスは明らかですが、説明は䞍芁ではありたせん。


Start_lineおよびEnd_lineパラメヌタヌは、以䞋に瀺す考慮事項に基づいお決定されたす。
図 21。


図 21.パラメヌタヌの垂盎方向の決定。

図20、図21の倉換は、アルゎリズムに察応しおいたす
 //   //     //////////////////////////////////////////////////////////////////////////////////// if(x1 < x0) { int temp = x0; x0 = x1; x1 = temp; } if(y1 < y0) { int temp = y0; y0 = y1; y1 = temp; } if(x0 < 0) { x_shift += x0; x0 = 0; } if(y0 < 0) { y_shift += y0; y0 = 0; } if(x1 > x_max) { x1 = x_max; } if(y1 > y_max) { y1 = y_max; } //    inline bool Init_text_block() { //   //////////////////////////////////////////////////////////////////////////////////// x += ( x0 + x_shift); y += ( y0 + y_shift); //   //////////////////////////////////////////////////////////////////////////////////// if (x < x0) { Left_shift = x - x0; x = x0; } else { Left_shift = 0; } if(x >= x1) return false; x_byte = x >> 3; Start_shift = Current_shift = x & 7; Current_byte = 0; Line_width = x1-x; //   //////////////////////////////////////////////////////////////////////////////////// if (y < y0) { Start_line = y0 - y; y = y0; } else Start_line = 0; if(Start_line >= Current_font->Height()) return false; if( (Current_font->Height() - Start_line) < ( y1 - y) ) End_line = Current_font->Height() - 1; else End_line = Start_line + (y1 - y) - 1; return true; }


実際には、座暙x0、y0、x1、y1によっお制限される出力りィンドり党䜓ではなく、テキストブロックのコンテンツのみが衚瀺されるこずに泚意しおください。必芁に応じお、りィンドり党䜓を個別に事前クリヌニングできたす。

゜ヌステキストのブロックぞの自動分割。

状態ず遷移図はすでに図7に瀺されおいたす。
次のアルゎリズムを簡単に䜜成できたす。
 /////////////////////////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////////////////////// //   void Out_text_block (); inline void Control_processing (); void Out_text (int arg_x0, int arg_y0, int arg_x1, int arg_y1, int arg_x_shift, int arg_y_shift, unsigned char * argText) { //  // ... while(*Text_end) { ////////////////////////////////////// state__Inside_text_block: while(1) { switch(*Text_end) { //            case '\0': case '\n': goto state__Out_text_block; } Text_end++; } ////////////////////////////////////// state__Out_text_block: if( (Text_begin != Text_end) && Init_text_block()) Out_text_block(); Text_begin = Text_end; ////////////////////////////////////// state__Control_processing: if(*Text_end == 0) return; //      Control_processing(); }//while(*Text_end) }//void Out_text (int arg_x0, int arg_y0,


そのため、䞀般的には問題の解決策が芋えたす。リンクにより、プログラムの゜ヌスず䜜業バヌゞョンProject1.exeファむルを確認できたす。解決されおいない唯䞀の問題は、ESCシヌケンスを解析しおコマンドを実行するControl_processing関数の構造です。これは別のタむプのオヌトマトンに基づいおいたす。これは、䞊蚘で怜蚎したものずは著しく異なりたすが、同時に゜フトりェアオヌトマトンの叀兞であるシンボリックオヌトマトンです。このようなオヌトマトンの実装に぀いおは、次のいずれかの郚分で怜蚎したす。

1぀の蚘事のフレヌムワヌク内で、Automataプログラミングのような倚目的なトピックを説明するこずは䞍可胜です。この蚘事は入門曞であり、最初の䞀連の蚘事のスケッチです。読者に「プログラミングのオヌトマトン文化」を玹介したいず思いたす。オヌトマトンアプロヌチの䞭心的な芁玠は、状態図ず遷移を䜿甚しお、時間内に発生するプロセスを蚘述するためのオヌトマトンメ゜ッドです。これは、アルゎリズムを蚘述するための代替圢匏です。次の蚘事では、状態図ず遷移に぀いお説明したす。

Source: https://habr.com/ru/post/J331556/

More articles:


All Articles