takeisa memo

2014年11月29日土曜日

[OCaml]XML Parser PXPを使ってみた(Bufferモジュールを利用)

前記事の、E_char_dataイベントで文字列を ^ で連結するやり方は効率が悪すぎた。

ブログ更新をtweetしていたら、@camloebaさんに Bufferがあることを教えていただいた。
いつもありがとうございます!

ということで、Bufferを使うように修正してみた。

修正後のプログラム

修正したのはparse関数だけ。

let parse element_func_list =
  let tags = Stack.create () in
  let element_func () =
    let item = List.find element_func_list ~f:(fun (element_list, _) ->
        Stack.to_list tags = element_list
      ) in
    match item with
      Some (_, func) -> Some func
    | None -> None in
  let in_content = ref false in
  let content = Buffer.create 1024 in
  let apply_func = ref (fun _ -> ()) in
  Pxp_ev_parser.process_entity config entry entmng (fun ev ->
      (* let event_string = Pxp_event.string_of_event ev in *)
      match ev with
        Pxp_types.E_start_tag (name, _, _, _) -> begin
          Stack.push tags name;
          (* print_endline @@ List.to_string (Stack.to_list tags) ~f:ident; *)
          match element_func () with
            Some func' -> begin
              apply_func := func';
              in_content := true
            end
          | _ -> ()
        end
      | Pxp_types.E_end_tag (name, _) -> begin
          ignore @@ Stack.pop_exn tags;
          if !in_content then
            begin
              !apply_func @@ Buffer.contents content;
              Buffer.clear content;
              in_content := false;
            end;
        end
      | Pxp_types.E_char_data str -> begin
          if !in_content then
            Buffer.add_string content str
        end
      | _ -> ())

このような修正は、動的な型の言語の場合、必要な修正箇所を見逃しやすいが、 OCamlのような静的な型の言語の場合は、コンパイルエラーで検出できるので非常にやりやすい。
Emacs+Tuaregでコード書いており、保存と同時にエラーがある行の色が変わるので、修正箇所は一目瞭然。

実行結果

satoshi@xubuntu:~/workspace/ocaml-try/pxp$ time ./parse_wiki > /dev/null

real    0m0.093s
user    0m0.081s
sys     0m0.011s

修正前は、

satoshi@xubuntu:~/workspace/ocaml-try/pxp$ time ./parse_wiki > /dev/null

real    0m3.361s
user    0m3.168s
sys     0m0.180s

およそ35倍速くなった!
これなら全く問題なし。
計測していないが、メモリの使用量も、かなり減ったはず。

なお、^による文字列連結に関しては、 Real World OCaml Chapter 3. Lists and Patternsの Performance of String.concat and ^ にも書かれていた。
^ を使うたびに文字列を生成するので、少しずつ文字列を連結して、大きな文字列を作る場合は、非常にパフォーマンスが悪い。

[OCaml]XML Parser PXPを使ってみた

OCamlのXML ParserであるPXPを使ってみた。

処理したXMLは日本語版Wikipediaの文書データ。
この文書データはここからダウンロードできる。

この文書データは、複数のpage要素からなり、 title要素にタイトル、 text要素に内容が書かれている。
今回は、このタイトルと内容を抜き出して、出力する処理を書いてみた。

PXPのインストール

PXPはopamでインストールできる。

$ opam install pxp

PXPについて

treeモードとeventモードがある。
treeモードでは、DOM treeを構築できるようだ。

やりたいことは大きなサイズの日本語版Wikipediaのデータをパースすること。
DOMを構築する必要はないので、eventモードを使う。

XML data as stream of events を参考にコードを書いてみる。

eventモードにはPush parsingとPull pasingの二種類のパース方法がある。
今回はPush parsingを利用した。

前準備

ここからWikipediaのデータをダウンロードする。
テストが簡単になるように、10ページ分だけ切り出したデータを作っておく。

$ grep -m 10 -n -F "</page>" jawiki-20141122-pages-articles.xml | cut -d: -f1 | tail -n 1 | xargs -I @ head -n @ jawiki-20141122-pages-articles.xml > jawiki_10.xml
$ echo "</mediawiki>" >> jawiki_10.xml

サンプルプログラム

内容を取り出したい要素と、その内容を取り出したときに呼ばれる関数を、処理関数parseに渡す方式で実装した。

let element_func_list = [
  (["title"; "page"; "mediawiki"], (fun content -> ..snip..));
  (["text"; "revision"; "page"; "mediawiki"], (fun content -> ..snip..))]

let () = parse element_func_list

parse_wiki.ml

open Core.Std

let config = let open Pxp_types in
  {default_config with encoding = `Enc_utf8}
               
let source = Pxp_types.from_file "/home/satoshi/Documents/jawiki/jawiki_10.xml"

let entmng = Pxp_ev_parser.create_entity_manager config source

let entry = `Entry_document []

let element_func_list = [
  (["title"; "page"; "mediawiki"],
   (fun content ->
      print_endline @@ sprintf "Title: %s" content));
  (["text"; "revision"; "page"; "mediawiki"],
   (fun content ->
      let max_length = 40 in
      let content' = 
        if String.length content > max_length then
          (String.slice content 0 max_length) ^ "..."
        else
          content in
      print_endline @@ sprintf "Text: %s" content'))]

let parse element_func_list =
  let tags = Stack.create () in
  let element_func () =
    let item = List.find element_func_list ~f:(fun (element_list, _) ->
        Stack.to_list tags = element_list
      ) in
    match item with
      Some (_, func) -> Some func
    | None -> None in
  let in_content = ref false in
  let content = ref "" in
  let apply_func = ref (fun _ -> ()) in
  Pxp_ev_parser.process_entity config entry entmng (fun ev ->
      (* let event_string = Pxp_event.string_of_event ev in *)
      match ev with
        Pxp_types.E_start_tag (name, _, _, _) -> begin
          Stack.push tags name;
          (* print_endline @@ List.to_string (Stack.to_list tags) ~f:ident; *)
          match element_func () with
            Some func' -> begin
              apply_func := func';
              in_content := true
            end
          | _ -> ()
        end
      | Pxp_types.E_end_tag (name, _) -> begin
          ignore @@ Stack.pop_exn tags;
          if !in_content then
            begin
              !apply_func !content;
              content := "";
              in_content := false;
            end;
        end
      | Pxp_types.E_char_data str -> begin
          if !in_content then
            content := !content ^ str
        end
      | _ -> ())

let () =
  parse element_func_list

実行結果

satoshi@xubuntu:~/workspace/ocaml-try/pxp$ ./parse_wiki
Title: Wikipedia:アップロードログ 2004年4月
Text: <ul><li>14:46 2004年4月30日 [[利用..
Title: Wikipedia:削除記録/過去ログ 2002年12月
Text: Below is a list of the most recent delet...
Title: アンパサンド
Text: {{記号文字|&amp;}}
[[Image:Trebuchet...
Title: Wikipedia:Sandbox
Text: #REDIRECT [[Wikipedia:サンドボック...
..snip..

エンコーディングの指定

<?xml 〜?>ディレクティブでUTF-8を指定してみたが、駄目だった。
configでエンコーディングを指定したら、正しく処理できた。

let config = let open Pxp_types in
  {default_config with encoding = `Enc_utf8}

自動でエンコーディングを認識させる方法はあるのかな？

文字列の連結処理

page要素10個分のxmlファイルのサイズは

-rw-rw-r-- 1 satoshi satoshi  533408 11月 28 23:56 jawiki_10.xml

たった500kb弱なのに、想定よりも処理に時間がかかっている。

satoshi@xubuntu:~/workspace/ocaml-try/pxp$ time ./parse_wiki > /dev/null

real    0m3.361s
user    0m3.168s
sys     0m0.180s

ちなみに実行環境はWindows8.1@Core i3のVirtualBox上のXubuntu14.04で、OCaml4.01.0を使っている。
重い環境だと思うが、メモリ不足にもなっていないのに、3秒以上もかかるのは何故だろう。
E_char_dataのイベントで文字を ^ で連結している処理が駄目なのかな？

      | Pxp_types.E_char_data str -> begin
          if !in_content then
            content := !content ^ str  ← ◆ここを () に変更
        end

文字列連結部分を () にしてみるとどうなるかな？

satoshi@xubuntu:~/workspace/ocaml-try/pxp$ time ./parse_wiki > /dev/null

real    0m0.087s
user    0m0.086s
sys     0m0.000s

おおよそ40倍早くなった。これが原因かー。
JavaのStringBuilderに相当するものは、OCamlでは何になるんだろう。

参考

2014年10月16日木曜日

[OS作成]30日でできる！OS自作入門 5日目 (3)

extern char hankaku_font[16 * 256];
で各文字のイメージを取得できるようになったので、

一文字を描画する関数 draw_char
文字列を描画する関数 draw_string

を作成し、画面に文字列を描画できるようにした。

void Main(void) {
..snip..
  draw_string(bootInfo->vram, bootInfo->scrnx, 8, 8, "ABC 123", COLOR_WHITE);
  draw_string(bootInfo->vram, bootInfo->scrnx, 31, 31, "Tiny OS.", COLOR_BLACK);
  draw_string(bootInfo->vram, bootInfo->scrnx, 32, 32, "Tiny OS.", COLOR_WHITE);
..snip..
}

void draw_char(char *vram, int width,  int x, int y, char c, char color) {
  int i, j;
  char img;
  char *vram_aux;
  char *font;
  font = hankaku_font + c * 16;
  vram += y * width + x;
  for (i = 0; i < 16; i++) {
    img = font[i];
    for (j = 0; j < 8; j++) {
      if ((img & 0x80) != 0)
    vram[j] = color;
      img <<= 1;
    }
    vram += width;
  }
}

void draw_string(char *vram, int width, int x, int y, char *string, char color) {
  char c;
  while ((c = *(string++)) != 0) {
    draw_char(vram, width, x, y, c, color);
    x += 8;
  }
}

次は変数の値をsprintfで表示できるようにするのだけど、sprintfを作るのは面倒なので、Haribote OSのものをそのまま使うことにしよう。

2014年10月13日月曜日

[OS作成]30日でできる！OS自作入門 5日目 (2)

フォントはfont.sで定義するようにした。
フォントイメージを定義したhankaku.txtからfont.sを生成するプログラムを作成した。

hankaku.txt OSASKの半角フォントを定義したファイルで、以下のような形式となっている。

char 0x61
........
........
........
........
........
.***....
....*...
.....*..
..****..
.*...*..
*....*..
*....*..
*...**..
.***.**.
........
........

font.s では、フォントの最初の文字(文字コード0x00)のアドレスをhankaku_fontとしてtinyos.cから参照できるようにする。
半角フォント1文字は16バイトからなり、256文字分定義する。

font.s

.file "font.s"

.global hankaku_font

 .data

hankaku_font:
 // char 0x00
 .byte 0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00
 // char 0x01
 .byte 0x00,0x00,0x38,0x44,0x82,0xaa,0xaa,0x82,0x82,0xaa,0x92,0x44,0x38,0x00,0x00,0x00
..snip..

font.sを生成するプログラムはOCamlで作成した。

makefont.ml

open Core.Std

let file_name = "hankaku.txt"

let is_skip_line line =
  let line' = String.strip line in
  line' = "" || String.get line 0 = '#'

let is_char_line line =
  try
    String.slice line 0 4 = "char"
  with
    _ -> false

let pattern_to_int p =
  String.fold p ~init:0 ~f:(fun acc c ->
      (acc lsl 1) + (if c = '*' then 1 else 0))

type parse_state = Init | Read_header | Read_data

let () =
  let lines = In_channel.read_lines file_name in
  let state = ref Init in
  List.iter lines ~f:(fun line ->
      if not (is_skip_line line) then
        if is_char_line line then begin
          if !state = Read_data then
            print_newline ();
          state := Read_header;
          print_endline ("\t// " ^ line);
          print_string "\t.byte "
        end
        else begin
          if !state = Read_data then
            print_string ",";
          state := Read_data;
          let img = pattern_to_int line in
          print_string ("0x" ^ (Printf.sprintf "%02x" img));
        end
    );
  print_newline ()

OMakeでfont.sを作成できるようにした。
$ omake font.s

ソースコードはgithubにコミットした。
https://github.com/takeisa/tinyos/tree/master/makefont

OCamlは、このような用途のプログラムも簡単に作成できる。
OCamlでの開発では、Emacs + Tuareg + merlin を使っているが、コード補完が効くし、REPLとしてutopが利用できるのでとても便利。

OCamlを使ってみたい人は、ここを参考に環境構築すれば良いですよ。

2014年10月11日土曜日

[OS作成]30日でできる！OS自作入門 5日目 (1)

筆者の独自ツールをそのまま使えば良かったんじゃないかと思いつつも、 Linux(Ubuntu14.04)の標準ツールだけで、OSを作成中。

静的なデータ領域の参照アドレスが正しくなるように、こちらのリンカスクリプトを参考にして、リンカスクリプトでbootpackのヘッダ部分を定義する方式に変更した。

tinyos_lnk.ls

OUTPUT_FORMAT("binary")

ENTRY("Main")

SECTIONS {
 .head 0x0 : {
  LONG(128 * 1024)      /* 0 : stack+.data+heap の大きさ（4KBの倍数） */
  LONG(0x54696e79)      /* 4 : シグネチャ "Tiny" */
  LONG(0)               /* 8 : mmarea の大きさ（4KBの倍数） */
  LONG(0x310000)        /* 12 : スタック初期値＆.data転送先 */
  LONG(SIZEOF(.data))   /* 16 : .dataサイズ */
  LONG(LOADADDR(.data)) /* 20 : .dataの初期値列のファイル位置 */
  LONG(0xE9000000)      /* 24 : 0xE9000000 */
  LONG(Main - 0x20)     /* 28 : エントリアドレス - 0x20 */
  LONG(24 * 1024)       /* 32 : heap領域（malloc領域）開始アドレス */
 }

 .text : { *(.text) }
 .data 0x310000 : AT ( ADDR(.text) + SIZEOF(.text) ) {
       *(.data)
       *(.rodata*)
       *(.bss)
 }
 .eh_frame : { *(.eh_frame) }
}

静的変数が正しく参照できなかったので、きっとdataセクションを0x310000にすれば良いのだろうなと思っていたのだけど、単純に .data 0x310000 と書くと、作成されるファイルのサイズが大きくなってしまい、FDイメージが作成できなかった。
ATでtextセクションの後ろにくるように指定でき、イメージを小さくできた。

このリンカスクリプトにより、次の静的変数は正しく参照できるようになった。

パレットの定義変数 static unsigned char table_rgb[16 * 3]
フォントA static char font_A[16]

文字Aが表示できたので、今日はここまで。

2014年10月5日日曜日

[OS作成]30日でできる！OS自作入門 4日目

やっと4日目だ。
4日目はパレットを設定し、デスクトップらしき画像を描画する。

最初、全てのパレット設定が黒になってしまった。
table_rgbが指し示すアドレスが正しくないようだ。
こちらのブログと同様にstaticを外したら、色が設定された。
tinyos.cのリスティングファイルを確認すると、staticを付けるとパレットの定義は、 dataセクションに格納されていた。
dataセクションのアドレスは boot.sで

 # +20 : .dataの初期値列がファイルのどこにあるか
 .int 0x10c8

と定義しているが、リンカスクリプトでdataセクションのアドレスを設定し、そのアドレスをboot.sにも設定すれば良いのだろうか。

qemuで実行した時のスクリーンショット。書籍と同じだ。

ソースが大きくなってきたのでgithubで公開する。こちらを参照。

アセンブラでC言語から呼べる関数を作るときの注意点

自由に使って良いレジスタ EAX,ECX,EDX だけ。
他のレジスタは値を変更してはならない。
戻り値はEAXレジスタに設定する。

オブジェクトファイルの逆アセンブル

objdumpコマンドを使う。

$ objdump -d func.o

func.o:     ファイル形式 elf32-i386

セクション .text の逆アセンブル:

00000000 :
   0: f4                    hlt    
   1: c3                    ret    

00000002 :
   2: 8b 4c 24 04           mov    0x4(%esp),%ecx
   6: 8a 44 24 08           mov    0x8(%esp),%al
   a: 88 01                 mov    %al,(%ecx)
   c: c3                    ret

GASでのEFLAGSレジスタのPUSH/POP

NASMでは、pushfd, popfd と書くが、GASではpushfl, popflと書く。

参考

2014年10月4日土曜日

[OS作成]30日でできる！OS自作入門 3日目 (8)

C言語から呼べる、アセンブラで作成した関数のリンクもうまくできたようだ。
やっと3日目が終了。長かった...

func.sに定義したio_hltで、hltを実行関数で、tinyos.cのMain関数から呼び出される。

最初、エラーもなく、コンパイル・リンクができたので、実行してみると、どうも挙動が変。
生成されたバイナリを見てみると、hltのコードが出力されていなかった。
原因がなかなか分からず、試行錯誤していたが、
.section .text
と書かなければならないところを、
.section text
と書いていたことが原因であった。
つまらないところで、手間取ってしまった。
でも、.section text と書いた場合、何を意味することになるのだろう。

ここまでのソースを書いておこう。
コードが多くなってきたので、今後はgithubを使おう。

Makefile

image_file=tinyos.img

image_file: ipl.bin tinyos.sys
 mformat -f 1440 -B ipl.bin -C -i ${image_file} ::
 mcopy tinyos.sys -i ${image_file} ::

ipl.bin: ipl.s ipl_lnk.ls
 gcc -nostdlib -o $@ -Tipl_lnk.ls ipl.s
 gcc -Tipl_lnk.ls -c -g -Wa,-a,-ad ipl.s > ipl.lst

tinyos.sys: boot.bin func.o tinyos.c
 gcc -m32 -S -c -nostdlib -Wl,--oformat=binary *.c
 gcc -m32 -c -g -Wa,-a,-ad tinyos.s > tinyos.lst
 gcc -m32 -c -nostdlib -Wl,--oformat=binary *.c -o tinyos.o
 ld -static -m elf_i386 -o tinyos.bin -e Main --oformat=binary tinyos.o func.o
 cat boot.bin tinyos.bin > $@

boot.bin: boot.s boot_lnk.ls
 gcc boot.s -nostdlib -Tboot_lnk.ls -o boot.bin
 gcc -Tboot_lnk.ls -c -g -Wa,-a,-ad boot.s > boot.lst

func.o: func.s
 as --32 -a -ad func.s > func.lst
 as --32 func.s -o func.o

img:
 make image_file

run:
 qemu-system-i386 -m 32 -localtime -vga std -fda ${image_file}

debug:
 qemu-system-i386 -m 32 -localtime -vga std -fda ${image_file} \
  -gdb tcp::10000 \
  -S

clean:
 rm tinyos.sys boot.bin
 rm *.o

boot.s

.set BOTPAK,  0x00280000 # bootpackのロード先
.set DSKCAC,  0x00100000 # ディスクキャッシュの場所
.set DSKCAC0, 0x00008000 # ディスクキャッシュの場所(リアルモード)

// BOOT_INFO
.set CYLS, 0x0ff0 # シリンダ数
.set LEDS,0x0ff1 # LEDの状態
.set VMODE, 0x0ff2 # ビデオモード
.set SCRNX, 0x0ff4 # 解像度X
.set SCRNY, 0x0ff6 # 解像度Y
.set VRAM, 0x0ff8 # VRAMの開始アドレス

.text
.code16

 // ビデオモードを変更する
 movb $0x00, %ah # VGA Graphics 320x200x8bit
 movb $0x13, %al
 int $0x10

 // 画面の状態を記録する
 movb $8, (VMODE)
 movw $320, (SCRNX)
 movw $200, (SCRNY)
 movl $0x000a0000, (VRAM)

 // LEDの状態を記録する
 movb $0x02, %ah
 int $0x16
 movb %al, (LEDS)

 // PICが割り込みを受け付けないようにする
 movb $0xff, %al
 outb %al, $0x21
 nop   # outは連続して使用しない
 outb %al, $0xa1
 cli   # CPUでも割り込み禁止

 // A20互換モードを無効にして1MB以上のアドレスにアクセスできるようにする
 call waitkbdout
 movb $0xd1, %al
 outb %al, $0x64
 call waitkbdout
 movb $0xdf, %al # A20を有効にする
 outb %al, $0x60
 call waitkbdout

 // プロテクトモードに移行する
.arch i486
 lgdt (GDTR0)
 movl %cr0, %eax
 andl $0x7fffffff, %eax # ページング禁止
 orl $0x00000001, %eax # プロテクトモード移行
 movl %eax, %cr0
 jmp pipelineflush
pipelineflush:
 movw $1*8, %ax
 movw %ax, %ds
 movw %ax, %es
 movw %ax, %fs
 movw %ax, %gs
 movw %ax, %ss

 // bootpackを転送する
 movl $bootpack, %esi # 転送元
 movl $BOTPAK, %edi # 転送先
 movl $512*1024/4, %ecx # 4で割っているのは4バイト単位で処理するため
 call memcpy

 // ディスクイメージを本来の位置へ転送する

 // ブートセクタ
 movl $0x7c00, %esi
 movl $DSKCAC, %edi
 movl $512/4, %ecx
 call memcpy
 
 // 残り
 movl $DSKCAC0+512, %esi
 movl $DSKCAC+512, %edi
 movl $0, %ecx
 movb (CYLS), %cl   # 読み込んだシリンダ数
 imull $512*18*2/4, %ecx # 1シリンダあたりのバイト数/4を掛ける
 sub $512/4, %ecx      # IPL分を引く
 call memcpy

 // bootpackを起動する
 movl $BOTPAK, %ebx
 movl 16(%ebx), %ecx
 addl $3, %ecx
 shrl $2, %ecx
 jz skip  # 転送するものがない
 movl 20(%ebx), %esi  # .dataのアドレス
 addl %ebx, %esi
 movl 12(%ebx), %edi # .data転送先
 call memcpy
skip: 
 movl 12(%ebx), %esp  # スタック初期値
 ljmpl $2*8, $0x0000001b
 
waitkbdout:
 inb $0x64, %al
 andb $0x02, %al
# inb $0x60, %al # 元のソースにはないコード
 jnz waitkbdout
 ret

memcpy:
 movl (%esi), %eax
 addl $4, %esi
 movl %eax, (%edi)
 addl $4, %edi
 subl $1, %ecx
 jnz memcpy
 ret

.align 16
 
GDT0:
 // GDTの構成
 // short limit_low, base_low
 // char base_mid, access_right
 // char limit_high, base_high
 
 // null selector
 .skip 8, 0x00
 // base=0x00000000 limit=0xcfffff access_right=0x92
 .word 0xffff, 0x0000, 0x9200, 0x00cf
 // base=0x00280000 limit=0x47ffff access_right=0x9a
 .word 0xffff, 0x0000, 0x9a28, 0x0047
 .word 0x0000
 
GDTR0:
 .word 8 * 3 - 1 # GDTのサイズ?
 .int GDT0

.align 16
bootpack:
 # + 0 : stack+.data+heap の大きさ（4KBの倍数）
 .int 0x00
 # + 4 : シグネチャ "Hari"
 .ascii "Tiny"
 # + 8 : mmarea の大きさ（4KBの倍数）
 .int 0x00
 # +12 : スタック初期値＆.data転送先
 .int 0x00310000
 # +16 : .dataのサイズ
 .int 0x11a8
 # +20 : .dataの初期値列がファイルのどこにあるか
 .int 0x10c8
 # +24 +28 のセットで 1bからの命令が E9 XXXXXXXX (JMP)になり、C言語のエントリポイントにJMPするようだ
 # +24 : 0xe9000000
 .int  0xe9000000
 # +28 : エントリアドレス-0x20
 .int 0x00
 # +32 : heap領域（malloc領域）開始アドレス
 .int 0x00

func.s

.file "func.s"
.section .text
.global io_hlt
 
io_hlt:
 hlt
 ret

tinyos.s

void io_hlt(void);

void Main(void) {
 fin:
  //__asm__("hlt\n\t");
  io_hlt();
  goto fin;
}

登録: 投稿 (Atom)