JavaScriptでわかる!組込みプログラミングの神髄

第3回処理をまとめて、細かく実行するには

はじめに

この特集もいよいよ最終回となりました。今回は、⁠まとめて処理」「細かく処理」にするテクニックを2つ紹介します。とくに最後のものは「リングバッファ」と呼ばれ、組み込みシステムではよく使われるものです。

では、さっそく見ていきましょう。

時間がかかる処理の例

前回まで取り上げてきたサンプルプログラムは「ある時間待つ」というものでした。たとえばメトロノームは、拍子のタイミングを待ったり、キーリピートのタイミングを待ったりという処理でした。

今回扱うのは「時間がかかる処理」です。キー入力を待っている間に、できるだけ進めておきたいような処理です。たとえば電子辞書などでは、文字を入力している途中でも検索結果が表示される、インクリメンタルサーチ機能があります。また、かな漢字変換でも、変換キーを押す前に辞書を先読みして、応答を早くしています。

時間がかかる処理のサンプルとして、素因数分解を取り上げてみました。素因数分解というのは、たとえば「12 =2 * 2 * 3」というように自然数を素数の積に分けるものです。SSL通信のような公開鍵暗号にも、素因数分解の性質が利用されています。

リスト1 fipn.html
<HTMLM><HEAD><TITLE>factorization in prime numbers</TITLE>
<SCRIPT type="text/javascript"><!--

var        inputnumber = 0;
var        current = 0;
var        divider = 0;

function        int_t0()
{
        for (var i=0; i<100; i++) {
                if (divider == 0)
                        return;
                if (divider > current) {
                        document.getElementById("output").innerHTML += ";";
                        divider = 0;
                        return;
                }
                if ((current % divider)) {
                        divider++;
                        continue;
                }
                current /= divider;
                s = document.getElementById("output").innerHTML;
                if (s != "")
                        s += " * ";
                s += divider;
                document.getElementById("output").innerHTML = s;
        }
}

function        press(val)
{
        if (val < 0)
                inputnumber = 0;
        else
                inputnumber = inputnumber * 10 + val;
        document.getElementById("input").innerHTML = inputnumber + " = ";
        document.getElementById("output").innerHTML = "";
        current = inputnumber;
        divider = 2;
}

function        init()
{
        setInterval(int_t0, 100);
}

// --></SCRIPT>
</HEAD><BODY onload="init()">
<H1>factorization in prime numbers</H1>

<P><SPAN id="input">
<SCRIPT type="text/javascript"><!--
document.write(inputnumber);
// --></SCRIPT>
</SPAN><SPAN id="output"></SPAN></P>

<P><BIG><BIG>
<SCRIPT type="text/javascript"><!--
for (var i=0; i<10; i++)
        document.write('<SPAN onmousedown="press(' + i + ')">[' + i + ']</SPAN>');
// --></SCRIPT>
<SPAN onmousedown="press(-1)">[C]</SPAN>
</BIG></BIG></P>


</BODY></HTML>

テンキー部分をクリックすると、数字が入力されます。同時に計算が行われ、進行状況が表示されます。計算途中でさらに数字を入力すると、最初から計算をしなおします。

プログラムは、100ミリ秒ごとのタイマー割り込みで100回の計算を行い、リターンしています。つまり、1秒に1000回計算を行うことになります。組込みシステムの場合はタスクを利用して行うことが多いのですが、OSがない環境で優先度を扱う場合は、このように処理を分割しなければならないこともあります。

処理を分割するやり方ですが、関数からリターンしても、次に関数が呼ばれたときに続きの計算ができるように、計算の進行をグローバル変数に保存しています。関数からいったんリターンしないといけないので、再帰処理などはグローバル変数をスタックとして使い、関数そのものを再帰呼び出ししないように直す必要があります。

計算途中で数字が入力されたときは、グローバル変数をリセットして、次のタイマー割り込みのときに最初から計算されるようにします。もしタイマー割り込みではなく、タスクでこれを行っている場合は、グローバル変数に「設定が変更されたフラグ」を用意し、計算の途中でときどきこれをチェックして、必要ならば計算をやり直すようにします。

ソートアルゴリズムの比較デモ

ちょっと特殊な例ですが、ソートアルゴリズムをグラフィカルに表示するデモです。これは別のところで公開したものですが、JavaScriptだけでできています。

バブルソート、選択ソート、マージソート、クイックソートの4つについて、ソートのようすを棒グラフで表示しています。

同時進行させるには、それぞれのアルゴリズムを1ステップずつ進めないといけないのですが、1ステップで行う比較や交換の回数は、ソートアルゴリズムによって異なります。各アルゴリズムを1ステップずつ実行したのでは、公平な比較になりません。そこで、比較や交換のたびにカウンタを増やし、タイマー割り込みの都度、どのアルゴリズムも同じだけカウンタが進むように調整しています。

キューイングの例

最後に、キューイングの例を見てみましょう。入力をいったん溜めておき、少しずつ処理したいことがあります。バッファリングとかキューイングと呼ばれるものです。オブジェクト指向言語では、配列などを使って簡単に実現できますが、組込みシステムではメモリ容量が厳しいため、そんな贅沢はできません。

そこで、リングバッファという仕組みがよく使われます。リングバッファは、配列変数、読み込み位置、書き込み位置という3つの変数で、入れた順に取り出せるFIFOバッファを作ることができます。この仕組みをJavaScriptのプログラムで見てみましょう。

リスト2 dial.html
<HTMLM><HEAD><TITLE>dial</TITLE>
<SCRIPT type="text/javascript"><!--

var        buffersize = 80;
var        buffer = new Array(buffersize);
var        rpos = 0;
var        wpos = 0;

function        putbuffer(val)
{
        buffer[wpos++] = val;
        if (wpos >= buffersize)
                wpos = 0;
}

function        getbuffer()
{
        var        val = buffer[rpos++];
        if (rpos >= buffersize)
                rpos = 0;
        return val;
}

function        isempty()
{
        return (rpos == wpos);
}

function        int_t0()
{
        if (isempty())
                return;
        if ((getbuffer()))
                document.getElementById("box").style.background = "#ff0";
        else
                document.getElementById("box").style.background = "#000";
}

function        press(val)
{
        for (var i=0; i<val; i++) {
                putbuffer(1);
                putbuffer(0);
        }
        putbuffer(0);
        putbuffer(0);
        putbuffer(0);
        putbuffer(0);
        putbuffer(0);
}

function        init()
{
        setInterval(int_t0, 200);
}

// --></SCRIPT>
</HEAD><BODY onload="init()">
<H1>dial</H1>

<DIV id="box" style="width:50px; height:50px; background:#000;">
</DIV>

<P><BIG><BIG>
<SCRIPT type="text/javascript"><!--
for (var i=1; i<=10; i++)
        document.write('<SPAN onmousedown="press(' + i + ')">[' + (i % 10) + ']</SPAN>');
// --></SCRIPT>
</BIG></BIG></P>


</BODY></HTML>

このサンプルプログラムは、押した数字の数だけ、四角が点滅するというものです。昔の電話をご存じの方は、ダイヤルパルスというとわかりやすいかも知れません。1を押すと1回点滅し、9を押すと9回、0を押すと10回点滅します。点滅が終わる前に次の数字を押しても、きちんと記憶しているため、間を置いて次の点滅がはじまります。

リングバッファの仕組みは以下の通りです。まず、読み込み位置rposと書き込み位置wposは、最初は両方とも0です。rposとwposが同じときは、バッファにデータはありません。また、この状態では、配列変数buffer[]は初期化されていません。データを追加するときは、buffer[wpos]にデータを格納して、wposを1増やします。もしwposが配列変数のサイズを超えた場合は、0に戻します。これで、wposとrposが同じでなくなったので、buffer[rpos]からデータを読み込み、rposを1増やします。wposにrposが追いつけば、データを全部読み込んだことになります。

プログラムですが、わかりやすさを優先して、点灯を1、消灯を0として格納するようにしました。数字の3を押したときに、1、0、1、0、1、0、0、0、0、0、のような点滅データを追加します。タイマー割り込みでは、1つずつ読み出して、四角の点滅に反映させます。データさえ用意できれば、モールスのような点滅パターンも作ることができます。

今回はオーバーフローの対策をしていないので、連続していくつもキーを押すと、最初に入力したデータが途中で上書きされてしまいます。バッファのサイズを変えることで、どれくらい蓄積できるかを変更することができます。オーバーフローを防ぐには、wposとrposから空きの数を計算したり、いくつ空きがあるのかという変数を用意したりして、追加しようとするデータが入りきるかどうかをチェックします。

終わりに

3回に渡ってお送りしてまいりました「JavaScriptでわかる! 組込みプログラミングの神髄⁠⁠、いかがでしたでしょうか。

今から四半世紀も昔、みんなが雑誌のBASICのリストを見てキーボードから打ち込んでいた時代には、こういったプログラミングテクニックは当たり前でした。その頃はゲームプログラムが多かったのですが、敵キャラを1ステップ動かし、自分を1ステップ動かし、背景を1ステップ動かしという処理の繰り返しでゲームを作っていました。そのままでは当然、敵の数が増えるとゲームのスピードが遅くなるわけで、プログラミングにはさまざまなテクニックが要求されました。

現在はCPUも速くなり、マルチタスクやスレッドも当たり前に使えます。古いテクニックは多くの分野では必要なくなりました。しかし、高度な機能が使えないような環境であっても、極論すればifとgotoさえ使えるなら、複数の処理を同時進行させることができるのです。

これらのテクニックが、みなさんのプログラミングの範囲を広げる一助となれば、これにまさる喜びはありません。最後までお読みいただき、ありがとうございました。

おすすめ記事

記事・ニュース一覧