2014-08-26

x86アセンブリ言語に関するメモ

バイナリ

x86系マイクロプロセッサの持つ主なレジスタ

レジスタ名	呼び名	主な機能
EAX	アキュムレータ	算術演算の結果を格納
EBX	ベースレジスタ	メモリアドレスを格納
ECX	カウントレジスタ	ループ回数をカウント
EDX	データレジスタ	データを格納
ESI	ソースインデックス	データ転送元のメモリアドレスを格納
EDI	ディスティネーションインデックス	データ転送先のメモリアドレスを格納
EBP	ベースポインタ	データの格納領域のメモリアドレスを格納
ESP	スタックポインタ	スタック領域のメモリアドレスを格納

主な命令

命令	使用例	意味	詳細
MOV	MOV EAX,ECX	EAX = ECX	ECXの値をEAXに格納
MOVZX	MOVZX_EAX,ECX	EAX = ECX	MOVのサイズが違うレジスタにコピーするとき用いる版
ADD	ADD EAX,ECX	EAX += ECX	EAXにECXを加算
SUB	SUB EAX,ECX	EAX -= ECX	EAXからECXを減算
MUL	MUL EAX,ECX	EAX *= ECX	EAXにECXを乗算
DIV	DIV EAX,ECX	EAX =EAX / ECX	EAXをECXで割って,商をEAXに,余りをEDXに格納
		EDX = EAX % ECX
INC	INC EAX	EAX++	EAXに1を加算
DEC	DEC EAX	EAX--	EAXに1を減算
XOR	XOR EAX,ECX	EAX = EAX ^ ECX	EAXとECXの各ビットごとに排他的論理和を取り,結果をEAXに格納
LEA	LEA EAX,[ECX+4]	EAX = ECX + 4	ECX+4(アドレス値)をEAXに格納
CMP	CMP EAX,ECX	if(EAX==ECX)_ZF=1	EAXとECXの値を比較してフラグに反映
		else ZF = 0	EAXとECXが等しければZF=1,EAXとECXが等しくなければ、ZF=0
TEST	TEST EAX,EAX	if(EAX==0) ZF = 1	EAXの値を0と比較してフラグに反映
		else ZF = 0	EAXが0と等しければZF=1,EAXが0でなければZF=0
JE(JZ)	JE 041001000	if(ZF == 1)	ZFが1なら041001000にジャンプ
		GOTO 041001000
JNE(JNZ)	JNE 041001000	if(ZF == 0)	ZFが0なら041001000にジャンプ
		GOTO 041001000
JMP	JMP 041001000	GOTO 041001000	無条件で041001000にジャンプ
CALL	CALL lstrcmpW	lstrcmpW()	lstrcmpw関数の呼び出し
PUSH	PUSH 00000001		スタックへ00000001を格納
POP	POP EAX		スタックからEAXへ値を取得
NOP	NOP		何もしない
SAR	SAR EAX		EAXを右にシフトする,すなわち2で割る
RET	RET		処理を呼び出し元に戻す

豆知識

XOR EAX,EAX は MOV EAX,0 と同様の働きをする。
dword ptr は、指定されたメモリアドレスから4バイトのデータを読み出すことを示す。

例えば、

MOV DWORD PTR SS:[EBP-8],1

の場合ベースポインタのアドレス-8から4バイトまでのデータに整数値1を格納している。

2014-07-23

Pythonで16進文字列をintに変換

Python

16進文字列からint

基数を指定してintにパースすればいい。

>>> s = 'abcdef'
>>> print int(s, 16)
11259375

ちなみにインタラクティブシェルなら0xからはじめた16進文字列を入力すれば10進数にしたものを返してくれる。

>>> 0xdeadbeef
3735928559

intから16進文字列

hex()を使う

>>> a = 111223
>>> print hex(a)
0x1b277

先頭に0xがつくのがいやならformatメソッドを使うとよい

>>> a = 111223
>>> print format(a, 'x')
1b277

こうなふうに先頭2文字を削除するという手もある

>>> a = 111223
>>> print hex(a)[2:]
1b277

フォーマット指定子(%記法)を使ってもいい

>>> a = 111223
>>> print '%x' % a
1b277

2014-05-18

簡単なタイピングゲーム

C言語

はじめに

　C言語で簡単なタイピングゲームを作ってみた。
　Visual C++でビルドすることを前提としてる。

コード

/*typing_cui1.c*/
#include <time.h>
#include <conio.h>
#include <ctype.h>
#include <stdio.h>
#include <string.h>
 
#define Qnumber 20
 
int main(){
 
    int i, stage, miss = 0, alpsum = 0;
    char *japanese[Qnumber] = { 
        "交わした約束忘れないよ",
        "目を閉じ確かめる",
        "押し寄せた闇",
        "振り払って進むよ",
        "いつになったらなくした未来を",
        "私ここでまた見ることできるの？",
        "溢れ出した不安の影を",
        "何度でも裂いて",
        "この世界歩んでこう",
        "とめどなく刻まれた",
        "時は今始まり告げ",
        "変わらない思いをのせ",
        "閉ざされた扉開けよう",
        "目覚めた心は走り出した",
        "未来を描くため",
        "難しい道で立ち止まっても",
        "空はきれいな青さで",
        "いつも待っててくれる",
        "だから怖くない",
        "もう何があっても挫けない"
    };
    char *roman[Qnumber] = {
        "kawasitayakusokuwasurenaiyo",
        "mewotojitasikameru",
        "osiyosetayami",
        "huriharattesusumuyo",
        "ituninattaranakusitamiraiwo",
        "watasikokodematamirukotodekiruno",
        "ahuredasitahuannnokagewo",
        "nandodemosaite",
        "konosekaiayundekou",
        "tomedonakukizamareta",
        "tokihaimahajimarituge",
        "kawaranaiomoiwonose",
        "tozasaretatobiraakeyou",
        "mezametakokorohahasiridasita",
        "miraiwoegakutame",
        "muzukasiimitidetatidomattemo",
        "sorahakireinaaosade",
        "itumomattetekureru",
        "dakarakowakunai",
        "mounanigaattemokujikenai"
    };
    double time;
    clock_t start, end;
 
    for (i = 0; i < Qnumber; i++)
        alpsum += strlen(roman[i]);
 
    printf("スペースキーで開始です。\n");
    while (_getch() != ' ')
        ;
 
    start = clock();
 
    for (stage = 0; stage < Qnumber; stage++){
 
        printf("%s\n", japanese[stage]);
        fflush(stdout);
 
        int len = strlen(roman[stage]);
        for (i = 0; i < len; i++){
            int ch;
            do{
                ch = _getch();
                if (isprint(ch)){
                    _putch(ch);
                    if (ch != roman[stage][i]){
                        miss++;
                        _putch('\b');
                    }
                }
            } while (ch != roman[stage][i]);
        }
        printf("\n");
    }
 
    end = clock();
 
    time = (end - start) / CLOCKS_PER_SEC;
 
    printf("\n%.2ftypes/sec\n%.1ftypes/min\nmiss types:%d\n", alpsum / time, alpsum / time * 60,miss);
 
    return 0;
}

入力されるアルファベットも指定しているのでかなり手抜き。
_getch()や_putch()など標準Cでは定義されてない関数を使っているので例えばgccでコンパイルしようとするとエラーになる。

参考

新版明解C言語　中級編

作者: 柴田望洋
出版社/メーカー: ソフトバンククリエイティブ
発売日: 2008/10/22
メディア: 単行本
購入: 1人クリック: 10回
この商品を含むブログ (3件) を見る

2014-05-16

C言語でchar型を返す関数。

C言語ポインタ

はじめに

　C言語で文字列が与えられたときそれを逆順したものを返す関数をなぜか作りたくなった。

ポインタを使う

　文字列を返す関数を作るときはintやdoubleなどと同じように何も考えず

間違え

char hoge(char fuga){
//何らかの処理
return fuga;
}

のようにしてはダメ。

C言語の文字列はchar型の配列であるため、その配列の先頭の要素のアドレスを指すポインタを返すようにする。

正解

char *hoge(char *fuga) {
//何らかの処理
return fuga;
}

サンプルコード

ポインタについての理解を助けるためのサンプルコードを添付した。

単に配列変数を指定するとその配列の先頭のアドレスを示すことが確認できる。

scanf("%s", str); などのように int や double と違い変数の先頭に & をつけなくて良いのはそのため。

冗長になるだけであるが scanf("%s", &str[0]); のように書くこともできる。

実装例1

配列のi番目と(文字列の長さ-1-i)番目の要素を(文字列の長さ÷2)回入れ替えてる。

char *reverse(char *s) {
    int i;
    char tmp;
    for (i = 0; i< strlen(s)/2; i++) {
        tmp = s[i];
        s[i] = s[strlen(s)-1-i];
        s[strlen(s)-1-i] = tmp;
    }
    return s;
}

実装例2

文字列の先頭を指すポインタと末尾を指すポインタを使って文字を入れ替えている。

使用例

例えばこの問題の仕様に合わせるのであれば、

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

char *reverse(char *s) {
    int i;
    char tmp;
    for (i = 0; i < strlen(s)/2; i++) {
        tmp = s[i];
        s[i] = s[strlen(s)-1-i];
        s[strlen(s)-1-i] = tmp;
    }
    return s;
}

int main() {
    char str[21];

    fgets(str, sizeof(str), stdin);
    printf("%s\n", reverse(str));

    return 0;
}

こんな風に使える。

終わりに

　ポインタを全然理解していなかったため、こんな簡単な処理をするだけの関数を書くのにかなり時間がかかってしまった。

2014-05-06

尺取法についてのあれこれ

競プロ C言語

はじめに

尺取法というものを知った。

尺取法の概要

JOI用語集によると、

配列に対して二つのインデックスを持ち、条件に応じて片方を進める操作を繰り返すことで答えを得る方法のこと。尺取虫の動きにちなんで名付けられた。DPの一種ともとれる。またキューの実装も尺取法の一種である。

とのこと。

例えば、AtCoder Regular Contest 022のB問題はこの尺取法を使って解くことができる。

問題の概要

問題文

高橋君は細長いお菓子を持っています。このお菓子は Ncm の長さのお菓子で、 1cm ごとにブロックに分かれています。それぞれのブロックには $10^5$ 種類の味うちのいずれかの味がついていて、左端から i 番目のブロックには $A_i$ 番目の味がついています。
高橋君はこのお菓子から、出来るだけ長い「同じ味のブロックが 2 つ以上含まれない、ひと繋がりになった部分」を切り出したいと思っています。最大で何 cm の部分を切り出すことが出来るでしょうか。ただし、切る場所はブロックとブロックの境界の部分のみとします。

入力

入力は以下の形式で標準入力から与えられる。
$N\\ A_1\ \ \ A_2\ \ \ .\ .\ .\ A_N$

1 行目には、お菓子の長さを cm 単位で表した整数 $N(1\leq N\leq 10^5)$ が与えられる。

2 行目には、お菓子の各ブロックの味の情報を表す N 個の整数が空白区切りで与えられる。このうち i 番目の整数 $A_i(1\leq A_i\leq 10^5)$ は、左端から i 番目のブロックの味が $Ai$ 番目の味であることを表す。

出力

高橋君がこのお菓子から切り出すことの出来る「同じ味のブロックが 2 つ以上含まれない、ひと繋がりになった部分」の最大の長さを cm 単位で表す 1 つの整数を 1 行に出力せよ。出力の末尾に改行をいれること。

入力例1

7
1 2 1 3 1 4 4

出力例1

3

入力例2

1
100

出力例2

1

要約するとこの問題は、
長さNの数列Aにおいて、同じ数字を2つ以上含まない最長の区間を求めろということ。

実装

Cで実装してみる。

/*http://arc022.contest.atcoder.jp/tasks/arc022_2*/
#include <stdio.h>
#define max(a, b) ((a > b) ? a : b)
 
int main(){
  int N, A[100001], S[100001]={0};
  int ans=0, r=0, l;
 
  scanf("%d", &N);
 
  for(l=0; l<N; l++) scanf("%d", &A[l]);
 
  for(l=0; l<N; l++){
    while(r<N && S[A[r]]==0){
      S[A[r]]++;
      r++;
  }
  ans = max(ans, r-l);
  S[A[l]]--;
}
 
  printf("%d\n", ans);
 
  return 0;
}

重要なのは13行目から20行目までのfor文の中の処理。
確かに尺取虫のような動きをしている。

参考

http://www.slideshare.net/chokudai/arc022