読者です 読者をやめる 読者になる 読者になる

再帰なしのマージソート

C言語で。 もう少し変数を減らせないものか。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


int merge_sort(int n, int *a)
{
  int *tmp_a, *src, *tgt, *tmp;
  int *sp_ed, *tp, *tp_ed;
  int *p1, *p1_ed, *p2, *p2_ed;
  int w;

  tmp_a = (int*) malloc(n * sizeof(int));
  if (tmp_a == NULL)
    return 1;

  src = a;
  tgt = tmp_a;
  for (w = 1; w < n; w += w) {
    tp = tgt;
    tp_ed = tp + n;
    p2_ed = src;
    sp_ed = src + n;
    while (tp < tp_ed) {
      p1 = p2_ed;
      p1_ed = p1 + w;
      if (p1_ed >= sp_ed) {
        while (p1 < sp_ed)
          *tp++ = *p1++;
        break;
      }
      p2 = p1_ed;
      p2_ed = p2 + w;
      if (p2_ed > sp_ed) { p2_ed = sp_ed; }
      while (p1 < p1_ed && p2 < p2_ed) {
        if (*p1 < *p2)
          *tp++ = *p1++;
        else
          *tp++ = *p2++;
      }
      if (p1 == p1_ed) {
        while (p2 < p2_ed)
          *tp++ = *p2++;
      } else {
        while (p1 < p1_ed)
          *tp++ = *p1++;
      }
    }
    tmp = src;
    src = tgt;
    tgt = tmp;
  }
  if (a != src) {
    memcpy(a, tmp_a, n * sizeof(int));
  }
  free(tmp_a);
  return 0;
}

int main(int argc, char** argv)
{
  int a[] = {12, 32, 0, 5, 10, -3, 10, 77};
  int i, n;

  n = sizeof(a) / sizeof(int);

  if (merge_sort(n, a))
    exit(1);

  for (i = 0; i < n; i++)
    printf("%d\n", a[i]);
}

関数呼び出し時のスタック操作

大雑把なメモ。

大事なレジスタがip、sp、bp。(GDBではrip、rsp、rbpになっている。)

ip(インストラクションポインタ)は次に実行する命令列のアドレスを格納している。
sp(スタックポインタ)は今のスタックフレームの上のほうを指している。(多分。)
bp(フレームポインタ)は今のスタックフレームの始まりっぽい位置を指している。

  • 関数を呼ぶ前に今から呼ぶ関数に渡す引数を今の関数のスタックフレームの上の方に準備する。
  • 関数を呼ぶ(call)と今のスタックフレームの上に関数から戻った後に実行する命令列のアドレスを格納。
  • ipを呼び出し先の関数の先頭命令アドレスに書き換え。
  • 呼び出し先の関数では、まず、戻り先命令アドレスの上にbpの値を格納(push bp)、フレームポインタの退避。
  • そしてbpの値をspの値で上書き(mov bp sp)。
  • 必要に応じて、spを上にずらす(sub sp 0x20)。

図で書くと下のようになる。

-------------- <--- sp
......
--------------
作業領域
-------------- <--- bp
退避されたFP
--------------
戻り先アドレス
--------------
引数1
--------------
引数2
--------------

bpは退避されたFP(フレームポインタ)が格納されているアドレスを指すようになっているようだ。(多分。)
あと、引数は必ずしもスタック領域を通じて渡されるわけでもなさそうだ。
簡単なプログラムを書いて確かめてみると、レジスタ経由で渡されている。

スタックポインタの位置とかずらし方とかがよくわからない。 呼び出し元に戻るときの詳しい処理もよくわからない。

Debug Hacks -デバッグを極めるテクニック&ツール

Debug Hacks -デバッグを極めるテクニック&ツール

GDB

GDBの基本的な操作メモ。

サンプル用のプログラム。(sample.c)

#include <stdio.h>

int sum(int a, int b)
{
  int c;
  c = a + b;
  return c;
}


int main(int argc, char** argv)
{
  int a = 10;
  int b = 20;
  int c;

  c = sum(a, b);
  printf("%d\n", c);
}

準備

デバック用にコンパイル。(実行ファイル、a.outが生成される。)

$ gcc -g sample.c

起動

GDBの起動。

$ gdb ./a.out

-qオプションを付けると起動時の煩わしい情報が表示されなくなる。

ソースコードの表示

list、でソースコードの表示。省略形は l。

(gdb) list
4       {
5         int c;
6         c = a + b;
7         return c;
8       }
9
10
11      int main(int argc, char** argv)
12      {
13        int a = 10;

詳しいオプション等はソース上の行の表示なんかがわかりやすそう。

アセンブリ言語の表示

disassemble <関数名>、でその関数のアセンブリ言語を表示。省略形 disas。

(gdb) disas main
Dump of assembler code for function main:
   0x00000000004004df <+0>:     push   %rbp
   0x00000000004004e0 <+1>:     mov    %rsp,%rbp
   0x00000000004004e3 <+4>:     sub    $0x20,%rsp
   0x00000000004004e7 <+8>:     mov    %edi,-0x14(%rbp)
   0x00000000004004ea <+11>:    mov    %rsi,-0x20(%rbp)
   0x00000000004004ee <+15>:    movl   $0xa,-0xc(%rbp)
   0x00000000004004f5 <+22>:    movl   $0x14,-0x8(%rbp)
   0x00000000004004fc <+29>:    mov    -0x8(%rbp),%edx
   0x00000000004004ff <+32>:    mov    -0xc(%rbp),%eax
   0x0000000000400502 <+35>:    mov    %edx,%esi
   0x0000000000400504 <+37>:    mov    %eax,%edi
   0x0000000000400506 <+39>:    callq  0x4004c4 <sum>
   0x000000000040050b <+44>:    mov    %eax,-0x4(%rbp)
   0x000000000040050e <+47>:    mov    $0x400628,%eax
   0x0000000000400513 <+52>:    mov    -0x4(%rbp),%edx
   0x0000000000400516 <+55>:    mov    %edx,%esi
   0x0000000000400518 <+57>:    mov    %rax,%rdi
   0x000000000040051b <+60>:    mov    $0x0,%eax
   0x0000000000400520 <+65>:    callq  0x4003b8 <printf@plt>
   0x0000000000400525 <+70>:    leaveq
   0x0000000000400526 <+71>:    retq
End of assembler dump.
(gdb) disas sum
Dump of assembler code for function sum:
   0x00000000004004c4 <+0>:     push   %rbp
   0x00000000004004c5 <+1>:     mov    %rsp,%rbp
   0x00000000004004c8 <+4>:     mov    %edi,-0x14(%rbp)
   0x00000000004004cb <+7>:     mov    %esi,-0x18(%rbp)
   0x00000000004004ce <+10>:    mov    -0x18(%rbp),%eax
   0x00000000004004d1 <+13>:    mov    -0x14(%rbp),%edx
   0x00000000004004d4 <+16>:    lea    (%rdx,%rax,1),%eax
   0x00000000004004d7 <+19>:    mov    %eax,-0x4(%rbp)
   0x00000000004004da <+22>:    mov    -0x4(%rbp),%eax
   0x00000000004004dd <+25>:    leaveq
   0x00000000004004de <+26>:    retq
End of assembler dump.

1行に1命令で表示されている。
左端の"0x00000000004004df"はその命令列が格納されているメモリアドレス(16進数)。
その次の"<+0>"は関数先頭の命令列のアドレスからその命令列のアドレスまでのオフセット。
これから命令列の長さもわかる。
例えば、sumの1つ目の命令列"push %rbp"は1バイト命令。sumの2つ目の命令列"mov %rsp,%rbp"は3バイト命令。

アセンプリ言語の表示形式変更

set disassembly-flavor <フレーバー名>、でアセンブリ言語のフォーマット(フレーバー)を変更。
デフォルトはattフレーバー。
intelフレーバーもある。

(gdb) set disassembly-flavor att
(gdb) disas sum
Dump of assembler code for function sum:
   0x00000000004004c4 <+0>:     push   %rbp
   0x00000000004004c5 <+1>:     mov    %rsp,%rbp
   0x00000000004004c8 <+4>:     mov    %edi,-0x14(%rbp)
   0x00000000004004cb <+7>:     mov    %esi,-0x18(%rbp)
   0x00000000004004ce <+10>:    mov    -0x18(%rbp),%eax
   0x00000000004004d1 <+13>:    mov    -0x14(%rbp),%edx
   0x00000000004004d4 <+16>:    lea    (%rdx,%rax,1),%eax
   0x00000000004004d7 <+19>:    mov    %eax,-0x4(%rbp)
   0x00000000004004da <+22>:    mov    -0x4(%rbp),%eax
   0x00000000004004dd <+25>:    leaveq
   0x00000000004004de <+26>:    retq
End of assembler dump.
(gdb) set disassembly-flavor intel
(gdb) disas sum
Dump of assembler code for function sum:
   0x00000000004004c4 <+0>:     push   rbp
   0x00000000004004c5 <+1>:     mov    rbp,rsp
   0x00000000004004c8 <+4>:     mov    DWORD PTR [rbp-0x14],edi
   0x00000000004004cb <+7>:     mov    DWORD PTR [rbp-0x18],esi
   0x00000000004004ce <+10>:    mov    eax,DWORD PTR [rbp-0x18]
   0x00000000004004d1 <+13>:    mov    edx,DWORD PTR [rbp-0x14]
   0x00000000004004d4 <+16>:    lea    eax,[rdx+rax*1]
   0x00000000004004d7 <+19>:    mov    DWORD PTR [rbp-0x4],eax
   0x00000000004004da <+22>:    mov    eax,DWORD PTR [rbp-0x4]
   0x00000000004004dd <+25>:    leave
   0x00000000004004de <+26>:    ret
End of assembler dump.

これは好みの問題?
どっちが主流なんだろう?

ブレークポイントと実行

break <関数名>、でその関数実行前のあたりにブレークポイントを設定。省略形はb。
run、でブレークポイントを設定したところまで実行。
nexti、で1命令実行。省略形はni。
nextiは関数呼び出しがあったときに関数の中に入らない。
関数の中に入りたかったら、step(省略形 s)。

(gdb) b main
(gdb) run
(gdb) disas main
Dump of assembler code for function main:
   0x00000000004004df <+0>:     push   rbp
   0x00000000004004e0 <+1>:     mov    rbp,rsp
   0x00000000004004e3 <+4>:     sub    rsp,0x20
   0x00000000004004e7 <+8>:     mov    DWORD PTR [rbp-0x14],edi
   0x00000000004004ea <+11>:    mov    QWORD PTR [rbp-0x20],rsi
=> 0x00000000004004ee <+15>:    mov    DWORD PTR [rbp-0xc],0xa
   0x00000000004004f5 <+22>:    mov    DWORD PTR [rbp-0x8],0x14
   0x00000000004004fc <+29>:    mov    edx,DWORD PTR [rbp-0x8]
   0x00000000004004ff <+32>:    mov    eax,DWORD PTR [rbp-0xc]
   0x0000000000400502 <+35>:    mov    esi,edx
   0x0000000000400504 <+37>:    mov    edi,eax
   0x0000000000400506 <+39>:    call   0x4004c4 <sum>
   0x000000000040050b <+44>:    mov    DWORD PTR [rbp-0x4],eax
   0x000000000040050e <+47>:    mov    eax,0x400628
   0x0000000000400513 <+52>:    mov    edx,DWORD PTR [rbp-0x4]
   0x0000000000400516 <+55>:    mov    esi,edx
   0x0000000000400518 <+57>:    mov    rdi,rax
   0x000000000040051b <+60>:    mov    eax,0x0
   0x0000000000400520 <+65>:    call   0x4003b8 <printf@plt>
   0x0000000000400525 <+70>:    leave
   0x0000000000400526 <+71>:    ret
End of assembler dump.
(gdb) ni
(gdb) disas main
Dump of assembler code for function main:
   0x00000000004004df <+0>:     push   rbp
   0x00000000004004e0 <+1>:     mov    rbp,rsp
   0x00000000004004e3 <+4>:     sub    rsp,0x20
   0x00000000004004e7 <+8>:     mov    DWORD PTR [rbp-0x14],edi
   0x00000000004004ea <+11>:    mov    QWORD PTR [rbp-0x20],rsi
   0x00000000004004ee <+15>:    mov    DWORD PTR [rbp-0xc],0xa
=> 0x00000000004004f5 <+22>:    mov    DWORD PTR [rbp-0x8],0x14
   0x00000000004004fc <+29>:    mov    edx,DWORD PTR [rbp-0x8]
   0x00000000004004ff <+32>:    mov    eax,DWORD PTR [rbp-0xc]
   0x0000000000400502 <+35>:    mov    esi,edx
   0x0000000000400504 <+37>:    mov    edi,eax
   0x0000000000400506 <+39>:    call   0x4004c4 <sum>
   0x000000000040050b <+44>:    mov    DWORD PTR [rbp-0x4],eax
   0x000000000040050e <+47>:    mov    eax,0x400628
   0x0000000000400513 <+52>:    mov    edx,DWORD PTR [rbp-0x4]
   0x0000000000400516 <+55>:    mov    esi,edx
   0x0000000000400518 <+57>:    mov    rdi,rax
   0x000000000040051b <+60>:    mov    eax,0x0
   0x0000000000400520 <+65>:    call   0x4003b8 <printf@plt>
   0x0000000000400525 <+70>:    leave
   0x0000000000400526 <+71>:    ret
End of assembler dump.

disasでアセンブリ言語を表示すると、次にどの命令を実行するかまで表示してくれる。
runしたあとに次の命令列が<+11>になっているのは、<+0>から<+11>までの命令列はCで書いた関数内の処理を実行する前に必要な関数呼び出し時の処理(関数プロローグ)だから。

レジスタの値を表示

info registors、でGDBで実行中のプログラムのレジスタの現在の値を表示する。省略形はi r。
info registors <レジスタ名1> <レジスタ名2> ....、でレジスタ名を指定できる。

(gdb) i r
rax            0xa      10
rbx            0x0      0
rcx            0x0      0
rdx            0x14     20
rsi            0x14     20
rdi            0xa      10
rbp            0x7fffffffe3c0   0x7fffffffe3c0
rsp            0x7fffffffe3c0   0x7fffffffe3c0
r8             0x3c4b98f300     258966352640
r9             0x3c4b20eac0     258958486208
r10            0x7fffffffe240   140737488347712
r11            0x3c4b61ec60     258962746464
r12            0x4003e0 4195296
r13            0x7fffffffe4d0   140737488348368
r14            0x0      0
r15            0x0      0
rip            0x4004ce 0x4004ce <sum+10>
eflags         0x202    [ IF ]
cs             0x33     51
ss             0x2b     43
ds             0x0      0
es             0x0      0
fs             0x0      0
gs             0x0      0
(gdb) i r rbp rsp rip
rbp            0x7fffffffe3c0   0x7fffffffe3c0
rsp            0x7fffffffe3c0   0x7fffffffe3c0
rip            0x4004ce 0x4004ce <sum+10>

メモリの内容表示

x/[表示数]<表示形式>[表示サイズ] <アドレス>、で<アドレス>から始まるメモリの中身を表示。
表示形式は0(8進数)、x(16進数)、u(符号なし10進数)、t(2進数)、c(ASCII文字表記)等がある。
表示サイズはb(バイト、1バイト)、h(ハーフワード、2バイト)、w(ワード、4バイト)等がある。
表示数は何個表示するか。

(gdb) disas main
Dump of assembler code for function main:
   0x00000000004004df <+0>:     push   rbp
   0x00000000004004e0 <+1>:     mov    rbp,rsp
   0x00000000004004e3 <+4>:     sub    rsp,0x20
   0x00000000004004e7 <+8>:     mov    DWORD PTR [rbp-0x14],edi
   0x00000000004004ea <+11>:    mov    QWORD PTR [rbp-0x20],rsi
   0x00000000004004ee <+15>:    mov    DWORD PTR [rbp-0xc],0xa
   0x00000000004004f5 <+22>:    mov    DWORD PTR [rbp-0x8],0x14
=> 0x00000000004004fc <+29>:    mov    edx,DWORD PTR [rbp-0x8]
   0x00000000004004ff <+32>:    mov    eax,DWORD PTR [rbp-0xc]
   0x0000000000400502 <+35>:    mov    esi,edx
   0x0000000000400504 <+37>:    mov    edi,eax
   0x0000000000400506 <+39>:    call   0x4004c4 <sum>
   0x000000000040050b <+44>:    mov    DWORD PTR [rbp-0x4],eax
   0x000000000040050e <+47>:    mov    eax,0x400628
   0x0000000000400513 <+52>:    mov    edx,DWORD PTR [rbp-0x4]
   0x0000000000400516 <+55>:    mov    esi,edx
   0x0000000000400518 <+57>:    mov    rdi,rax
   0x000000000040051b <+60>:    mov    eax,0x0
   0x0000000000400520 <+65>:    call   0x4003b8 <printf@plt>
   0x0000000000400525 <+70>:    leave
   0x0000000000400526 <+71>:    ret
End of assembler dump.
(gdb) x/x $rbp - 0xc
0x7fffffffe3e4: 0x0000000a
(gdb) x/u $rbp - 0xc
0x7fffffffe3e4: 10
(gdb) x/4xb $rbp - 0xc
0x7fffffffe3e4: 0x0a    0x00    0x00    0x00
(gdb) x/x $rbp - 0x8
0x7fffffffe3e8: 0x14
(gdb) x/u $rbp - 0x8
0x7fffffffe3e8: 20

"$rbp - 0xc"で$rbpレジスタの内容をメモリアドレスとして解釈し、そこから0xcだけ引いたアドレス、という意味になる。
"$rbp - 0xc"にはプログラム中でaに代入した10が、"$rbp - 0x8"にはプログラム中でbに代入した20が格納されていることがわかる。
"$rbp - 0xc"の内容をバイトごとに表示すると"0x0a 0x00 0x00 0x00"となっており、4バイトまとめて表示したときと0x0aの位置が入れ替わっている。 このことからこのCPUがリトルエンディアンであることがわかる。

メモリセグメント

メモリセグメントのメモ。

プロセスが扱うメモリ領域はその用途によって複数のセグメントに分けられている。

  • テキスト(コード)セグメント
  • データセグメント
  • bssセグメント
  • ヒープセグメント
  • スタックセグメント

(上のセグメントほど、メモリアドレスが小さい。)

テキストセグメントにはプログラムの命令列が含まれている。 安全性のため、この領域はRead Only。

データセグメントには初期化済みの大域変数が含まれている。

bssセグメントには初期化されていない大域変数が含まれている。

ヒープセグメントはプログラム実行中に動的にメモリを確保するときに使われる。 なので、ヒープセグメントは動的に領域が増えていき、メモリアドレスが大きい方へ増えていく。

スタックセグメントは局所変数や関数の引数渡し、関数の作業領域などに使われる。 関数が呼ばれるとスタックセグメントにスタックフレームが積まれていく。 なので、スタックセグメントも動的に領域が増えていき、メモリアドレスが小さい方へ増えていく。

GlassFishでMySQLを使う準備

GlassFishMySQLを使おうと思ったら、コンパイルは通ったが、アクセスしたときに「適切なJDBCドライバーが見つかりません」みたいな感じで怒られた。

JDBCのjarを適切な場所に配置しれやらないといけないようだ。

JDBCのjarを<GlassFishのインストールディレクトリ>/glassfish/domains/<対象ドメイン>/lib/ext 以下に置いてやる必要がある。

例えば、GlassFishを/opt/glassfish4にインストールしていて、ドメイン domain1 で、MySQLのドライバー(v5.1.35)を使う場合。

$ cp mysql-connector-java-5.1.35.jar /opt/glassfish4/glassfish/domains/domain1/lib/ext/

でOK。(必要に応じてroot権限が必要かもしれない。)

その後、ドメインを再起動。(これもroot権限が必要かもしれない。)

$ asadmin restart-domain

参考:Java EE 7 検証環境をつくる MySQL へのjdbc接続をGlassFish v4 に作成

JavaのArrays.asListが固定長な理由

Java

テストを書くときなどは特定の要素が入ったListがほしいことがあります。

普通だと以下のように書きます。

import java.util.ArrayList;
import java.util.List;

List<String> strs = new ArrayList<String>();
strs.add("hoge");
strs.add("foo");
strs.add("bar");

でもこれは面倒。

Arrays.asListを使うと以下のようにもっと簡潔に書くことができます。

import java.util.Arrays;
import java.util.List;

List<String> strs = Arrays.asList("hoge", "foo", "bar");

このArrays.asListで生成したListは要素を追加したり、削除したりできません。
(addとかremoveとかを呼び出すとUnsupportedOperationExceptionが投げられます。)

なんでだろう思ってたんですが、実装が違ったんですね。
Arrays.asListのコードは以下のようになっています。(openjdk 8u40より抜粋)

public class Arrays {

    /* 中略 */

    public static <T> List<T> asList(T... a) {
        return new ArrayList<>(a);
    }

    /* 中略 */

}

ArrayListを返していますが、このArrayListjava.util.ArrayListではなくて、java.util.Arraysクラスのstaticな内部クラスのArrayListです。

public class Arrays {

    /* 中略 */

    private static class ArrayList<E> extends AbstractList<E>
        implements RandomAccess, java.io.Serializable
    {
        private static final long serialVersionUID = -2764017481108945198L;
        private final E[] a;

        ArrayList(E[] array) {
            a = Objects.requireNonNull(array);
        }

        @Override
        public int size() {
            return a.length;
        }

        @Override
        public Object[] toArray() {
            return a.clone();
        }

        @Override
        @SuppressWarnings("unchecked")
        public <T> T[] toArray(T[] a) {
            int size = size();
            if (a.length < size)
                return Arrays.copyOf(this.a, size,
                                     (Class<? extends T[]>) a.getClass());
            System.arraycopy(this.a, 0, a, 0, size);
            if (a.length > size)
                a[size] = null;
            return a;
        }

        @Override
        public E get(int index) {
            return a[index];
        }

        @Override
        public E set(int index, E element) {
            E oldValue = a[index];
            a[index] = element;
            return oldValue;
        }

        @Override
        public int indexOf(Object o) {
            E[] a = this.a;
            if (o == null) {
                for (int i = 0; i < a.length; i++)
                    if (a[i] == null)
                        return i;
            } else {
                for (int i = 0; i < a.length; i++)
                    if (o.equals(a[i]))
                        return i;
            }
            return -1;
        }

        @Override
        public boolean contains(Object o) {
            return indexOf(o) != -1;
        }

        @Override
        public Spliterator<E> spliterator() {
            return Spliterators.spliterator(a, Spliterator.ORDERED);
        }

        @Override
        public void forEach(Consumer<? super E> action) {
            Objects.requireNonNull(action);
            for (E e : a) {
                action.accept(e);
            }
        }

        @Override
        public void replaceAll(UnaryOperator<E> operator) {
            Objects.requireNonNull(operator);
            E[] a = this.a;
            for (int i = 0; i < a.length; i++) {
                a[i] = operator.apply(a[i]);
            }
        }

        @Override
        public void sort(Comparator<? super E> c) {
            Arrays.sort(a, c);
        }
    }

    /* 中略 */

}

addとかromoveがオーバーライドされていません。
なので、addとかremoveを呼び出すと継承元のクラスAbstractListのaddとかremoveが呼び出されるんですが、 それらはUnsupportedOperationExceptionを投げるようになっているというわけです。

アルジャーノンに花束を / ダニエル・キイス

読書(小説)

とってもいい本でした。
知能は元に戻ってしまったけれども逆に人間性を取り戻した主人公に切なさを感じました。

アルジャーノンに花束を〔新版〕(ハヤカワ文庫NV)