外部記憶装置

脳みそ小さすぎるからメモしとく

64bitUEFIでxv6を動かす方法(ブートローダー編)

xv6_uefi 自作OS

セキュリティキャンプ2018で32bitのxv6を64bitUEFIから起動したPiBVTです。(長い)

セキュリティキャンプの参戦記録ではなく、どのようにしてxv6を64bitUEFIから起動したのか書いていきたいと思います。 ブートローダー編とxv6編の2本立てで、今日はブートローダー編です。

続きを読む

リレー式計算機で円周率を計算する　番外編

リレー計算機

どうもお久しぶりです。PiBVTです。約4ヶ月ぶりの更新となります。

リレー計算機について

リレー計算機についてなのですが、一旦このプロジェクトは凍結したいと思います。 理由は以下のとおりです。

  • サークルのロボコンが忙しくなった。
  • Seccamp参加後、OS開発のほうが楽しくなっちゃった。

身勝手な理由であることは重々承知しているのですが、ご了承ください。

リレー計算機プロジェクトの再開時期としては、来年の春休み(2,3月)あたりを考えています。 それまでは、しばしお待ちください。

リレー式計算機で円周率を計算する　その2

リレー計算機

丸々1ヶ月ぶりの更新です。命令セットの決定とエミュレーターの作成は進めていたのですが、ブログ更新は完全に放置していました。 早速ですが、今回は計算アルゴリズムの大まかなフロー作成です。

ライプニッツの公式へ変更

前回の記事でマチンの公式を利用すると言っていたのですが、計画を変更しライプニッツの公式を利用することにしました。 理由は以下の計算結果が出たからです。

以下の結果は前回のN(分母)を1000に変更して計算したものです。

./leibniz
Step:252
3148

./machin
Step:5
3152

以上のような結果になったわけです。 何が問題かというと、前回分母を10000に設定したのはリレー計算機を16bitで作成すると考えていたからです。

しかし、8bitでも大変なのに16bitとなるとえげつない量のリレーが必要となり計画の達成が困難になることは明白です。 「多倍長計算」なども一応決めた命令セットをもとにアセンブラで書いてみたのですが、除算の手間を考えると現実的ではありませんでした。 そのため、Nを1000に変更してもライプニッツの公式で314が計算可能であることが分かったため、データバス幅を減らすべく、ライプニッツの公式を利用することにしました。

計算アルゴリズムの大まかなフロー作成

というわけで、ライプニッツの公式を利用することになりました。前回の計算プログラムから無駄な部分を省き改良したものが以下のとおりです。

int main(){
  int result=0;
  int u=1;
  int l=1;
  int step = 1;
  while(u != 0 && l != 0){
    u = 4000/(step*2-1);
    l = 4000/(step*2+1);
    result = u - l + result;
    step += 2;
  }
return result;
}

このプログラムを実行するために必要な命令は大きく分けて、「加算」・「減算」・「乗算」・「減算」・「分岐」 の5つです。1つずつ考えていくことにします。

加算

この命令に関しては何も言う必要は無いと思います。今回の計算に関しては4000以下つまり符号なしで12bitまでの加算が出来ることが求められます。

減算

加算と同様基本的な演算です。今回はデータバス幅の関係上、符号なしの数も扱いたいので補数による減算ではなく、減算器をハード的に実装することになります・

乗算

乗算は加算とシフト、AND命令で全て実現できるのですが、プログラムはかなり長いものになります。 そのため、今回は小さな乗算器をハード実装してソフトウェアで大きな数も扱えるようにする方法でいきます。

除算

除算をハードで実装するとなるとかなり大変なので、これは最初からソフトウェアでエミュレーションすることにします。 幸いなことに多倍長計算は扱わないので比較的に簡単にできそうな気はします。

分岐

このプログラムにおいて最も重要な命令です。whileループの条件式にNon Zero判定を利用し、 除算のソフトウェアエミュレーションでは2数の大小比較の分岐命令を必要とします。 大小比較は比較器によって行うことができますが、今回はリレー数も考慮して 減算命令と正数分岐、負数分岐、0分岐命令を利用することにします。

まとめ

エミュレーターやアセンブリで計算プログラムを書いてみた結果、以上のような方針で進めることにしました。 命令セットは大方完成しているのですが、さらに必要・不必要な命令がないか精査して正式に決定したあとで記事にしたいと思います。 エミュレーターも作っていたのですが、初めて作ったこともありスパゲティ状態なので0から作り直したいと思います。

リレー式計算機で円周率を計算する　その1

リレー計算機

サークルでの作業やら何やらで更新が遅れてしまいました。今回は使用する円周率計算公式の選定です。

円周率計算公式の候補

ライプニッツの公式

ライプニッツの公式(Wikipedia)

別名マータヴァ・ライプニッツ級数。円周率を求めるための公式の一つであるが、収束が非常に遅い(Wikipediaより)

1-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+\frac{1}{9}-\cdot\cdot\cdot = \frac{\pi}{4}

\sum_{n=0}^{\infty} \frac{(-1) ^ {n}}{2n+1} = \frac{\pi}{4}

マチンの公式

マチンの公式(Wikipedia)

グレゴリー級数を利用した、非常に収束の速い級数。1兆2411億桁まで計算したという記録もある。(Wikipediaより)

4\arctan\frac{1}{5} - \arctan\frac{1}{239} = \frac{\pi}{4}

をグレゴリー級数

\arctan x = \sum_{n=0}^{\infty} \frac{(-1)^{n}}{2n+1} x^{2n+1} = x - \frac{1}{3}x^{3} + \frac{1}{5}x^{5} - \frac{1}{7}x^{7} + \cdot\cdot\cdot

を利用することによって計算する。

実際に計算してみた

実際にテストプログラムを書き、計算してみました。固定小数点演算を前提とした計算のため、予め分子を10000倍し、項が1未満になった時点で計算を終了します。

ライプニッツの公式

プログラム

#include <stdio.h>
#define N 10000
#define MAX_STEP 200
int main(){
  int result=0;
  int step = 1;
  int u=1;
  int l=1;
  while(u >= 1 && l >= 1){
    u = (int)(N/(step*2-1));
    l = (int)(N/(step*2+1));
    result = u - l + result;
    step+=2;
    if(result*4 >= 31400 && result*4 < 31500){
      break;
    }
  }
  printf("Step:%d\n",(step+1)/2);
  printf("%d\n",result*4);
}

結果

Step:210
31400

目標値3.14を計算するまでに210ステップでした。

マチンの公式

プログラム

#include <stdio.h>
#define N 10000
#define MAX_STEP 200
int step=0;   
int test(int x){
    int a=x;
    int b=1;
    int pos=1;
    int ans;
    step++;
    ans=N/x;
    printf("Step:%d\n",step);
    int flag=1;
    while(pos>=1){
          a=a*x*x;
      b+=2;
      pos=N/(b*a);
      if(flag==0){
        ans+=pos;
            flag = 1;
      }else{
        ans-=pos;
            flag = 0;
      }
      step++;
      printf("Step:%d\n",step);
    };
    return ans;
}


int main(){
    printf("%d", 4*(4 * test(5) - test(239)));
    return 0;
}

結果

Step:5
31420

1つの項あたりの計算量がかなり異なるため一概には言えませんが、収束はかなり速いことが分かります。 計算誤差も桁数が増加した場合はマチンの公式のほうが有利であると考えられます。

まとめ

多倍長計算や乗算・除算の計算コストなどを全く考慮していないため、どちらの公式がいいとは言えませんが、桁数が増加した場合の誤差を考慮し、CPUエミュレータ作成まではマチンの公式を利用する方針とします。

（と言っても、利用する四則演算は変わらないんですけどね...)

リレー式計算機で円周率を計算する　その0

リレー計算機

リレー式計算機とは？

コンピュータ黎明期はダイオードとリレーによって構成されたコンピュータが主流でした。時代が進むに連れて素子は真空管・トランジスタ・LSIと微細化・省電力化が進み、今のような超小型ICが実現しました。今回はあえて時代に逆行し、リレーとダイオードを利用した計算機を自作したいと思います。CPUはもちろんRAMなどにもICは一切利用しません。具体的な目標としては、第一段階としては円周率3.14の計算です。第2段階では円周率10桁の計算を目標とします。（そういえば今日は円周率の日ですね）

目的

ロマン以外の何物でもない。

方針

以下のような工程で進めていくつもりです。

  1. 円周率計算公式の選定
  2. 計算アルゴリズムの大まかなフロー作成
  3. CPUの命令セット決定
  4. 命令セットに基づいたCPUエミュレーターの作成
  5. 専用アセンブラ作成
  6. プログラム作成
  7. CPUエミュレーター上でプログラムの検証
  8. 回路設計
  9. 回路に基づいたCPUシミュレータの作成
  10. CPUシミュレータ上での回路検証
  11. 組み立て
  12. 実働テスト

今現在2.計算アルゴリズムの大まかなフロー作成まで完了しているので近いうちに記事にします。 計画としては11月にある大学の学祭に間に合うようにするつもりです。