simotin13's message

simotin13といいます。記事の内容でご質問やご意見がありましたらお気軽にコメントしてください\^o^/

ARMの命令セットの条件指定について

ARMの命令セット(v7)について調べていたので備忘録のためメモを残しておきます。

■ARMv7のマニュアル

https://www.macs.hw.ac.uk/~hwloidl/Courses/F28HS/Docu/DDI0406C_C_arm_architecture_reference_manual.pdf

とりあえず命令セットのところを読んでみる。
参考用に簡単な加算と条件分岐を含むコードを書いてみる。

■サンプルコード hoge.c

int add(void)
{
    int a = 0;
    a += 0x10;
    if ( a == 0x10) {
      return a;
    }
    return 0;
}


$ arm-linux-gnueabi-gcc -g -c hoge.c
$ arm-linux-gnueabi-objdump -S hoge.o


■サンプルアセンブラコード

00000000 <add>:
int add(void)
{
   0:   e52db004        push    {fp}            ; (str fp, [sp, #-4]!)
   4:   e28db000        add     fp, sp, #0
   8:   e24dd00c        sub     sp, sp, #12
    int a = 0;
   c:   e3a03000        mov     r3, #0
  10:   e50b3008        str     r3, [fp, #-8]
    a += 0x10;
  14:   e51b3008        ldr     r3, [fp, #-8]
  18:   e2833010        add     r3, r3, #16
  1c:   e50b3008        str     r3, [fp, #-8]
    if ( a == 0x10) {
  20:   e51b3008        ldr     r3, [fp, #-8]
  24:   e3530010        cmp     r3, #16
  28:   1a000001        bne     34 <add+0x34>
      return a;
  2c:   e51b3008        ldr     r3, [fp, #-8]
  30:   ea000000        b       38 <add+0x38>
    }
    return 0;
  34:   e3a03000        mov     r3, #0
}
  38:   e1a00003        mov     r0, r3
  3c:   e24bd000        sub     sp, fp, #0
  40:   e49db004        pop     {fp}            ; (ldr fp, [sp], #4)
  44:   e12fff1e        bx      lr

条件指定について

ARMの命令のうち、最上位の4bitは条件指定のビット(cond)として割り当てられているそうです。

f:id:simotin13:20180606010019p:plain

アセンブラを見るとこのcondビットはほぼほぼ1111(0xE..)になっていることが多い。
ここまでは過去の経験として知っていたのですが、このcondビットの意味がいまいちよく分かっていませんでした。※そういえばpine64のダンプとか読んだときも少し調べていました。

mcommit.hatenadiary.com

結論ですが、ARMでは(ほとんどの)命令に対して実行するかしないかの条件をつけることができるそうです。これだけだとピンとこないのですが、条件と言うのは要するにフラグレジスタの各種フラグビット(ゼロフラグとかキャリーフラグ...etc)に応じて実行するかしないかを命令に対して指定できるという意味になります。

実際に、上記のhoge.oの逆アセンブルですとbneだとcondは1になっています。
条件指定実行ができるということは
addとかmov命令をフラグレジスタの値を元に実行するかしないか切り替えれるというような意味だと思います。*1

というわけで実際にどの命令で条件指定が可能なのか、適当に試してみたいと思います。

が、今日眠いので続きは明日にします。

[2018/06/06 追記]

条件実行について更に調べてみた続きです。

mcommit.hatenadiary.com

*1:なんかrubyの後置記法みたいでおしゃれ

スタックの状態を可視化するWebツールを書いてみた。

Webページ上でStackの状態を可視化するコードを書いてみました。

stack viewer

Stackを可視化するツール自体に目新しい感じはしないのですが、Web上でこういうツールってありそうでなかったので作ってみました。
かなりざっくりしたものですが、よかったら使ってください。

個人的なニーズとして普段Cとかアセンブラをガチでデバッグするとき、紙のノートにスタックの状態を書きながらデバッグしたりしているのですが、ノートだと動的にイメージし続けるのが辛いのであると便利な気がします。*1

課題

現状だと、pushするたびにページが下に伸びていくのでなんかしっくりこない気もするので、時間があるときに改善したいと思います。*2

その他

ついでにずっとほったらかしにしていたホームページも書き換えてみました。シンプルにindex.htmlだけにしてみました。

mcommit toppage

*1:GDBを使うとスタックとかレジスタの状態を見ることはできますが、いかんせんCUIなのが地味で直感的じゃない気がしていました

*2:もちろんpushはスタックトップに積まれて、popはスタックトップから取り出されていくのでご安心ください

構文解析ハンズオン 関西出張版に参加させて頂きました

lang-impl.connpass.com

参加させて頂きました。

良かった点

久しぶりにパーサ系のコード書きました。普段パーサ系のコードを書くことはあまりありませんが、時々必要に迫られるときがあるので定石やいろいろなテクニックや流行とか知っておくというのは大切な気がします。ハンズオンでいろいろ実際に書いてみるというのは自分にはぴったりでした。

あと、普段は再帰を使ってコードを書く機会が少ないので再帰を使うちょうどよい練習になりました。

苦労した点

Javaのコード書くのが久しぶりすぎてやばかった・・・
事前にJavaでハンズオンをするので環境を用意しておいてくださいと告知があったのですが、環境は構築していましたが、心と体の準備が追い付いていませんでした。
Javaはもう何年も書いていないけどまぁなんとかなるだろう」と思っていたら、コード書くのと実行するのに戸惑いました。やはり事前に復習をしておけばよかったように思います。

構文解析について思ったこと

パーサを書く場合に気を付けないといけないポイントとして、パースをする際の入出力と内部状態をしっかりと把握しておく必要があると思います。
入出力と状態は、

入力

  • 文字列

出力

  • 解析結果(AST)
  • 解析の成否(正常に解析できたのか、解析できなかったのか)

パーサ内部で保持する状態

  • 現在の解析位置
  • 入力文字列長

のような構成になります。

再帰下降的にパースする場合、各非終端記号に対応する関数は呼び出し元に

  • 解析結果(AST)
  • 解析の成否(正常に解析できたのか、解析できなかったのか)

を返す必要があります。

パーサを作る時に話がややこしくなるのは出力が複数存在するというのが1つの要因なのかなと思いました。
例えば戻り値をASTとした場合、解析の成否の情報は戻り値以外の方法で返す必要があります。

例外がサポートされている言語だと例外が1つの選択肢としてありますが、その場合例外クラスの設計をきちんと考えておく必要があります。
NULLやそれに類するものがある言語であれば戻り値のASTがNULLであれば解析異常とするのもありかなと思います。*1

Rubyで式の構文解析をしてみた

復習がてらハンズオンの課題の数式の解析コードを書いてみました。

gist.github.com

書いてみて気づいたこと

上記コードを書いていて気づいたのですが、入力が不正な場合の異常系に対応できていません。
非終端記号に対応する各関数は、解析異常時はnilを返すというポリシーで実装してみたのですが、再帰下降型で書くと想定していない文字が出てきたときに関数レベルではエラーハンドリングができないです。やはり字句解析フェーズがないというのはつらい気がする。
この辺は好みだと思いますが、個人的には先に入力を全てレキサーにかけるのが好きです。*2

再帰か状態遷移か

再帰を使わず状態遷移で書けば、適切に入力を弾けるので、仕様が小さくて手書きでパーサを書くのであれば状態遷移の方がいいようにも思いました。*3

再帰を使うメリットは何か考えてみたのですが、コードが短くなるというのはあるかも知れません。あと仕様が大きくなると状態遷移を考えるのがかえって面倒になる気がする。デバッグは状態遷移の方が断然しやすい気がしました。*4

今後やってみたいこと

パーサジェネレータを書く

パーサ系の実装についてはパーサジェネレータを書いてみたいです。*5
あまり難しくないはずですがBNFパーサを書かないといけないというところでいつも面倒くさくなって挫折してしまいます・・・あと、懇親会でPEGというものを教えてもらったので勉強してみると何か開けてきそうな気がしました。

関数型言語でパーサを書く

勉強会や懇親会でもイミュータブルとかパーサコンビネータの話題が挙がっていましたが、オブジェクト指向言語に囚われずに関数型の頭で何かパーサを書いてみたいです。

その他

ハンズオンの課題でJSONのパーサを書こうというのがありましたが、twitterで最近JSONのパーサに関して面白そうな論文が紹介されていました。

https://www.microsoft.com/en-us/research/publication/mison-fast-json-parser-data-analytics/

ざっと読んでみたところ

  1. JSONニーズ高まってて大きなデータ扱うことが増えてきたけど、パース遅いので何とかせねば。
  2. どうやってやるか→投機的解析と並列化で高速化してみた。
  3. やってみた結果→いい感じ。CSVとかHTMLとかXMLにも適用したい。

といった感じでしょうか。rustのプロジェクトが実装になるのかな。

github.com

解析する際にDBのようにインデックスをつけたり、SIMDとビット演算を使った並列化したりするらしい。
大量のデータとか扱う機会があれば、SIMDGPUFPGAあたりをデータの解析を目的として勉強してみたいです。

感想

勉強会も懇親会も色々と勉強になることが多かったです。

参加して思ったのは、構文解析を短い時間で「理解する、誰かに教える」というのは結構難しいのではないかと思いました。勉強会への参加だけでなく予習とか復習が欠かせない気がします。
あと、勉強会だと主催者の方や周りの詳しい方に質問できるので、やはりこういった場があるのはいいなぁと感じます。

kmizu様、チューターの皆様、いろいろ教えてくださった参加者の皆様、会場を使わせて頂いたはてな様、ありがとうございました。

*1:もしかしたら複数のオブジェクトを返せる言語(goとか!?)というのはパーサを書くのに向いているのかもしれない。Rubyでも複数返せるけど、そういう場合はなぜかHashを使いたくなる

*2:パーサに渡った時点で不正な文字が登場しないことが保証されるので

*3:組込だとスタックサイズの見積りの事情により再帰が使えない場合がある

*4:再帰のパースをデバッグする場合はログをしっかりと入れておかないとデバッグが難しいです

*5:せっかく勉強会に参加して気持ちが高ぶったので

Goでバイナリファイルを読み込んでHexダンプしてみた

最近触り始めたGo言語で、勉強としてバイナリファイルを読み込んでHexダンプしてみました。
バイナリファイルといってもfile.Readを使った読み込みなのでバイナリかどうかはあまり関係ないかもしれない。

package main

import (
  "fmt"
  "os"
)

func main() {
  argc := len(os.Args)
  if argc < 2 {
    fmt.Println("input file name.")
    return
  }

  filename := os.Args[1]
  f, err := os.Open(filename)
  if err != nil {
    fmt.Println("err:", err)
    return
  }

  c := make([]byte, 1)
  var buf []byte
  size := 0
  for {
    len, r_err := f.Read(c)
    if len == 0 {
      break
    }
    size += len
    if r_err != nil {
      fmt.Println("err:", err)
      return
    }
    buf = append(buf, c[0])
  }

  fmt.Printf("size:[%d]\n", size)
  for i := 0; i < size; i++ {
      fmt.Printf("%02X ", buf[i])
      if i % 16 == 15 {
        fmt.Println("")
      }
  }
}

感想

Go言語的な書き方がよくわからない

なんとなくC言語っぽく書いてみたけど、Go言語的に正しい書き方がよくわからない。
特にファイルから全データをリードする場合C言語だと大抵、EOFまで1byteずつreadするけどgoでもそんなのりでいいのかな・・・

配列とslice

RubyのArray的なのが使いたいけどgoだと配列とsliceを組み合わせて使うみたい。
sliceって機能と名前があってない気がする。

そもそも、goって名前自体英語だと普通の動詞になるので検索性がよくない。
例えば、for文について調べようとしたら

f:id:simotin13:20180326011052j:plain

みたいな結果になった。やはり名前重要。

参考

Go言語を勉強するにあたって「基礎からわかるGo言語」を手元に置いて読んでいます。

改訂2版 基礎からわかる Go言語

改訂2版 基礎からわかる Go言語

この書籍では前半で言語の基本的な機能について解説されていて、後半で逆引きサンプルが載っているのでかなり役に立っています。
今のところやりたいことに合わせて前半と後半をいったり来たりしながら読んでいます。

goらしい書き方についてはこの書籍だけでは掴めないので、go好きな人が書いたコードとかもっと読んだり写経した方がよさそう。

レジスタの値を取得するx86のアセンブラ関数を書いてみた

前回書いたPINE64+の続きとして、とりあえずBROMの処理が終わった状態でCPUがどうなっているか知りたいのですが、難航しています。

mcommit.hatenadiary.com

BROMのコードのダンプを見た結果、コプロセッサの設定とかをしていることは分かりましたがどうも追いきれないところもあるのでとりあえずCPUのレジスタの値をUARTでダンプ出力とかしてみたいと思いました。

レジスタを直接触るためにはアセンブラでコードを書く必要があり、少しハードルはあがります。
といってもARMのABIを理解して、出力したいレジスタからMOV命令で汎用レジスタにコピーするだけなのでそこまでは難しくはないはずです。

が、とりあえず練習もかねてx86で試してみました。

ABI的にポインタで渡す変数がスタックトップの次にあることを前提としています。関数側ではEBPの設定とかしないようにしたので、スタックトップはリターンアドレスになります。抜けるときもret命令だけで問題ありません。

reg.asm

section .text
global get_eax
global get_ecx
global get_edx
global get_ebx
global get_ebp
global get_esi
global get_edi
global get_esp
global get_eip

get_eax:
    mov ebx, [esp+0x04]
    mov [ebx], eax
    ret

get_ecx:
    mov eax, [esp+0x04]
    mov [eax], ecx
    ret

get_edx:
    mov eax, [esp+0x04]
    mov [eax], edx
    ret

get_ebx:
    mov eax, [esp+0x04]
    mov [eax], ebx
    ret

get_ebp:
    mov eax, [esp+0x04]
    mov [eax], ebp
    ret

get_esi:
    mov eax, [esp+0x04]
    mov [eax], esi
    ret

get_edi:
    mov eax, [esp+0x04]
    mov [eax], edi
    ret

get_esp:
    mov eax, [esp+0x04]
    mov [eax], esp
    sub [eax], dword 0x08
    ret

get_eip:
    mov eax, [esp]
    mov ebx, [esp+0x04]
    mov [ebx], eax	; return address on stack frame.
    ret

呼び出す側は、

main.c

#include <stdio.h>
#include <stdint.h>

extern void get_eax(uint32_t *reg);
extern void get_ecx(uint32_t *reg);
extern void get_edx(uint32_t *reg);
extern void get_ebx(uint32_t *reg);
extern void get_ebp(uint32_t *reg);
extern void get_esi(uint32_t *reg);
extern void get_edi(uint32_t *reg);
extern void get_esp(uint32_t *reg);
extern void get_eip(uint32_t *reg);

int main(int argc, char **argv)
{
    uint32_t eax, ecx, edx, ebx, esp, ebp, esi, edi, eip;

    get_eax(&eax);
    get_ecx(&ecx);
    get_edx(&edx);
    get_edx(&ebx);
    get_ebp(&ebp);
    get_esi(&esi);
    get_edi(&edi);
    get_esp(&esp);
    get_eip(&eip);

    printf("eax: [%08X]\n", eax);
    printf("ecx: [%08X]\n", ecx);
    printf("edx: [%08X]\n", edx);
    printf("ebx: [%08X]\n", ebx);
    printf("ebp: [%08X]\n", ebp);
    printf("esi: [%08X]\n", esi);
    printf("edi: [%08X]\n", edi);
    printf("esp: [%08X]\n", esp);
    printf("eip: [%08X]\n", eip);
    return 0;
}

のような感じで、ポインタ引数で受け取ることを想定した関数にしてみました。
※最初戻り値で作ってみたのですが、戻り値だとEAXが取れなくなってしまいます。
まだ全関数のデバッグはできていませんが、問題なく動いていそうです。

ビルドは、


$ nasm -f elf reg.asm
$ gcc main.c reg.o
のような感じです。nasmを使う場合は -f でフォーマットを指定する必要があります。

getがなんとなく書けたのでついでにsetも書きたい。それができたらARMv7版も書いてみよう。