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

2014-04-22

数学の粘度のやつ

数学 Python C言語

はじめに

　学校でS先生からマーティン・ガードナーの最難問というものを紹介された。問題の概要は次の通り。

ある数の粘度は、すべての桁を掛けて出る答えが1桁になるまでにかかる積算の回数で表す。それぞれの桁の数を掛け算して出るのが2番目の数で、そのまた全桁の数を掛けて出るのが3番目の数…こうして1桁の数が出るまでやり、出るまでに重ねた掛け算の回数を数えるのだ。
例えば、77は粘度4だ。なぜなら1桁になるまで4回掛け算しなきゃならないからね（77-49-36-18-8）。粘度1で一番小さい数は10、粘度2で一番小さい数は25、粘度3で一番小さい数は39、粘度4の最小数は77だ。では、粘度5で一番小さい数は何？

※Marthin Gardner(1914-2010)はアメリカの数学者兼科学記者。多くの数学パズルを残した。

今回はこの問題をプログラムを使って解いた。言語はCとPython

整数nの粘度を求めるプログラム

　この問題を解く前段階として整数nが入力として与えられたとき整数nの粘度を求めるプログラムを書いた。

Python

#-*- coding: utf-8 -*-

def mul(a):
    b = 1
    while True:
        b *= a%10
        a /= 10
        if a == 0:
            return b
def nend(a):
    nend = 0
    while True:
        if len(str(a)) == 1 and nend == 0:
            return 0
        elif len(str(a)) >= 2:
            a = mul(a)
            nend += 1
        elif  len(str(a)) == 1:
            return nend
n = int(raw_input("整数nを入力してください:"))
print "整数nの粘度は%dです。" % nend(n)

#include <stdio.h>

int mul(long long int a)
{
    int b = 1;
    while(1){
        b *= a%10;
        a /= 10;
        if(a == 0)
            return b;
    }
}
int nend(long long int a)
{
    int nend = 0;
    while(1){
        if(a/10 < 1 && nend == 0)
            return 0;
        else if(a/10 >= 1){
            a = mul(a);
            nend++;
        }
        else if(a/10 < 1)
            return nend;
    }
}
int main()
{
    long long int n;
    printf("整数nを入力してください:");
    scanf("%lld",&n);
    printf("整数nの粘度は%ldです。",nend(n));
    return 0;
}

粘度nの最小値を求めるプログラム

Python

#-*- coding: utf-8 -*-

def mul(a):
    b = 1
    while True:
        b *= a%10
        a /= 10
        if a == 0:
            return b
def nend(a):
    nend = 0
    while True:
        if len(str(a)) == 1 and nend == 0:
            return 0
        elif len(str(a)) >= 2:
            a = mul(a)
            nend += 1
        elif  len(str(a)) == 1:
            return nend
n = 1
i = 1
while True:
    if nend(n) == i:
        print "粘度%dの最小値は%dです" % (i,n)
        i += 1
    if i==8:
        break
    n += 1

#include <stdio.h>

int mul(long long int a)
{
    int b = 1;
    while(1){
        b *= a%10;
        a /= 10;
        if(a == 0)
            return b;
    }
}
int nend(long long int a)
{
    int nend = 0;
    while(1){
        if(a/10 < 1 && nend == 0)
            return 0;
        else if(a/10 >= 1){
            a = mul(a);
            nend++;
        }
        else if(a/10 < 1)
            return nend;
    }
}
int main()
{
    long long int n=1;
    int i=1;
    while(1){
        if(nend(n) == i){
        printf("粘度%dの最小値は%ld\n",i,n);
        i++;
        }
        if(i==10)
            break;
        n++;
    }
    return 0;
}

　このプログラム実は少し手を抜いています。というのは粘度nの最小値 < 粘度n+1の最小値という条件を勝手つけてしまっています。(実際にはそれでも問題ないのかもしれませんが証明してないので手抜き)
実行すると問題の答えの粘度5の最小値は679だとわかります。
分ったところまで粘度nの最小値を貼っておきます。(あってるかはわからない)
ちなみに粘度9はそこそこの性能のPCでも1分近く(もしくはそれ以上)かかりました。(Pythonの場合)
粘度10はCで書いてかつ、そこそこの性能のPCでも5分～10分くらいかかりました。

粘度1の最小値は10
粘度2の最小値は25
粘度3の最小値は39
粘度4の最小値は77
粘度5の最小値は679
粘度6の最小値は6788
粘度7の最小値は68889
粘度8の最小値は2677889
粘度9の最小値は26888999
粘度10の最小値は3778888999

参考

http://www.gizmodo.jp/2013/08/_so_you_th.html?utm_source=rss20&utm_medium=rss

2014-04-12

CTFの過去問を解いてOllyDbgの使い方を覚える。

バイナリ CTF

はじめに

　デバッガの使い方が全然わからなかったので、Hack.lu CTF 2013のRoboAuthという問題で練習しました。
この問題は、パスワードを探すというとてもシンプル内容なので練習にはちょうどいいかなと思います。

問題の概要

問題文は以下の通り

RoboAuth (Category: Reversing) Author(s): cutz
Oh boy, those crazy robots can't catch a break! Now they're even stealing our
liquid gold from one of our beer tents! And on top of that they lock it behind
some authentication system. Quick! Access it before they consume all of our
precious beverage!
Download: https://ctf.fluxfingers.net/static/downloads/roboauth/RoboAuth.exe
Flag: password1_password2

問題ファイルのリンクが切れていた場合は下記のアーカイブにある問題データを利用できる。
http://shell-storm.org/repo/CTF/Hacklu-2013/Reversing/RoboAuth-150/

使ったツール

OllyDbg

最も有名なデバッガで日本では"折井さん"の愛称で親しまれている。
日本語化パッチも公開されている。

IDAPro5.0(Freeware版)

高機能な逆アセンブラ。

手順

　exeファイルなのでDOSから実行してどんな挙動をするのか確かめる。
f:id:kira000:20140408183249p:plain
コンソールからパスワードを入力するタイプの非常にシンプルなプログラムだと分かる。

次にOllyDbgを起動。(右クリックして管理者として実行)
RoboAuth.exeをOllyDbgで開く。
f:id:kira000:20140412173410p:plain

OllyDbgの画面構成

左上:逆アセンブルコード
左下:メモリダンプデータ
右上:レジスタ(CPUが内部にもつ記憶領域。変数みたいなもん)
右下:現在のスタック(一時的にデータを格納するメモリ領域。スタック内のデータはESPレジスタに格納される。)

よく使うショートカット

F2：ブレークポイント設定/解除
F7：詳細ステップ実行(ステップイン：関数内部まで入り実行)
F8：ステップ実行(ステップオーバー：関数呼び出しを1命令として実行)
F9：デバッギー実行
Ctrl+F2:再スタート
F12：デバッギー実行一時停止
Ctrl+F9：リターンまで実行
Alt+F9：ユーザーコードまで実行(システムDLL内から抜ける際等に使用)
Space：アセンブル
Ctrl+E：バイナリデータの編集
Ctrl+G：アドレスを指定して移動
ESC：詳細自動ステップ実行の停止

同時にIDA Proも起動しRoboAuth.exeを開く。
f:id:kira000:20140412002638p:plain

Strings windowのYou passed level1!というところをダブルクリック
f:id:kira000:20140412003038p:plain

DATA XREF: sub_401627+54Eというところをダブルクリック(DATA XREFは外部参照という意味)
f:id:kira000:20140412003610p:plain

一度目の認証でputsやscanfがcallされているアドレス値がわかったので次はOllyDbgで最初にputsが使われているアドレス値に移動する。

具体的にはCtrl+Gしてアドレスのところで00401B3Eを指定する。
f:id:kira000:20140412004031p:plain

F2キーで00401B3Eをブレークポイントに設定しF9でデバッギー実行する。
その後、F8でステップ実行していきscanfがcallされているところでパスワードに"AAAAAAAAAA"と入力してみる。
f:id:kira000:20140412004509p:plain

さらにF8でステップ実行を進めていくとEAXレジスタに"r0b0RUlez!"という文字列が格納されているのが見つかる。
f:id:kira000:20140412004952p:plain
その後もF8でステップ実行を続けるとプログラムは終了する。

ここで"r0b0RUlez!"という文字列が正しいパスワードかどうかDOSから実行し確かめるてみる。
f:id:kira000:20140411021500p:plain
一つ目のパスワードは"r0b0RUlez!"であると確認できた。

またIDAに戻り、二度目の認証が行われているアドレス値を探す。
scanf関数を目印にして探した。
f:id:kira000:20140412005504p:plain

もう一度OllyDbgに戻りCtrl+F2で再スタートする。
このときOllyDbgの本体があるフォルダ内に"filename.bak"や"filename.udd"のようなファイルがあれば削除する。(今回はRoboAuth.bakやRoboAuth.uddなどがあれば削除する。)
さっきと同じようにCtrl+Gで00401B3Eに移動しF2でブレークポイントを設定。
もう1回Ctrl+Gしてアドレスは004015B2を指定して移動。F2で004015B2にもブレークポイントを設定。
その後004015B2以降の逆アセンブルコードを読んでいくと0040161F番地にCC INT3というコードがある。
f:id:kira000:20140412012356p:plain

これはint 3hを使ったアンチデバッグらしい。(詳しいことは知らない)
これを無視させるためにOllyDbgのオプション>>解析詳細設定>>例外項目へと移動し、
以下の(プログラムに渡す)例外項目を無視する:
というところのINT3ブレークにチェックを入れる。
f:id:kira000:20140412012811p:plain

少し戻って004015B2番地(2度目の認証の部分)の逆アセンブルコードをもう一度読んでみる。

004015B2   E8 D1640000      CALL <JMP.&msvcrt.scanf>
004015B7   A1 98AD4000      MOV EAX,DWORD PTR DS:[40AD98]
004015BC   894424 04        MOV DWORD PTR SS:[ESP+4],EAX
004015C0   8D45 E0          LEA EAX,DWORD PTR SS:[EBP-20]
004015C3   890424           MOV DWORD PTR SS:[ESP],EAX
004015C6   E8 7CFFFFFF      CALL RoboAuth.00401547
004015CB   85C0             TEST EAX,EAX
004015CD   75 0D            JNZ SHORT RoboAuth.004015DC
004015CF   A1 A4AD4000      MOV EAX,DWORD PTR DS:[40ADA4]
004015D4   890424           MOV DWORD PTR SS:[ESP],EAX
004015D7   E8 B4640000      CALL <JMP.&msvcrt.puts>

004015C6番地のCALL RoboAuth.00401547の部分が怪しいので、Ctrl+Gで00401547へ移動しブレークポイントに設定。

00401547   55               PUSH EBP
00401548   89E5             MOV EBP,ESP
0040154A   EB 22            JMP SHORT RoboAuth.0040156E
0040154C   8B45 08          MOV EAX,DWORD PTR SS:[EBP+8]
0040154F   0FB610           MOVZX EDX,BYTE PTR DS:[EAX]
00401552   8B45 0C          MOV EAX,DWORD PTR SS:[EBP+C]
00401555   0FB600           MOVZX EAX,BYTE PTR DS:[EAX]
00401558   83F0 02          XOR EAX,2
0040155B   38C2             CMP DL,AL
0040155D   74 07            JE SHORT RoboAuth.00401566
0040155F   B8 01000000      MOV EAX,1
00401564   EB 17            JMP SHORT RoboAuth.0040157D
00401566   8345 08 01       ADD DWORD PTR SS:[EBP+8],1
0040156A   8345 0C 01       ADD DWORD PTR SS:[EBP+C],1
0040156E   8B45 0C          MOV EAX,DWORD PTR SS:[EBP+C]
00401571   0FB600           MOVZX EAX,BYTE PTR DS:[EAX]
00401574   3C 02            CMP AL,2
00401576  ^75 D4            JNZ SHORT RoboAuth.0040154C
00401578   B8 00000000      MOV EAX,0
0040157D   5D               POP EBP
0040157E   C3               RETN

F9でデバッギー実行し、一度目の認証で正しいパスワードを入力しもう一度F9。
二度目の認証で"AAAAAAAAAA"と入力し、そこからはサブルーチン内の処理も追いたいのでF7で詳細ステップ実行していく。

00401555   0FB600           MOVZX EAX,BYTE PTR DS:[EAX]

でのEAXレジスタが002BFDCC番地の値となっているので、そこを右クリックしダンプ画面へというところをクリックする。
f:id:kira000:20140412020409p:plain
すると左下のダンプデータのところに"u1nnf2lg"という文字列が見つかった。

00401558   83F0 02          XOR EAX,2
0040155B   38C2             CMP DL,AL

はEAXレジスタの値(u1nnf2lg)を2とXORした値とDLの値を比べている。
したがってパスワードはu1nnf2lgのそれぞれの文字について2とXORして出てきた文字列になる。

Python

s = 'u1nnf2lg'
Flag = '' 

for i in s:
    Flag += chr(ord(i)^2)

print Flag

Python(ワンライナー)

print "".join(chr(ord(i)^2) for i in 'u1nnf2lg')

C言語

#include <stdio.h>

int main()
{
    char *s = "u1nnf2lg";

    while (*s) {
        printf("%c", *s^2);
        s++;
    }

    printf("\n");

    return 0;
}

実行結果

w3lld0ne

確かめる。
f:id:kira000:20140412022039p:plain

Flagは"r0b0RUlez_w3lld0ne"であることが分った。

終わりに

アセンブリ言語もデバッガの使い方もまだまだ全然分からないのでこれから勉強していきたいです。

参考にした書籍

楽しいバイナリの歩き方(技術評論社)

たのしいバイナリの歩き方

作者: 愛甲健二
出版社/メーカー: 技術評論社
発売日: 2013/08/22
メディア: 単行本（ソフトカバー）
この商品を含むブログ (12件) を見る

いまどきのアセンブラプログラミング-Windowsプログラム解析・開発の独習

いまどきのアセンブラプログラミング―Windowsプログラム解析・開発の独習

作者: 橋本和明,山本洋介山,leye,イシサキ
出版社/メーカー: 毎日コミュニケーションズ
発売日: 2003/10
メディア: 単行本
クリック: 12回
この商品を含むブログ (19件) を見る

kira924ageの雑記帳

簡単なタイピングゲーム

はじめに

コード

参考

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

はじめに

ポインタを使う

サンプルコード

実装例1

実装例2

使用例

終わりに

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

はじめに

尺取法の概要

問題の概要

問題文

入力

出力

入力例1

出力例1

入力例2

出力例2

実装

参考

数学の粘度のやつ

はじめに

整数nの粘度を求めるプログラム

粘度nの最小値を求めるプログラム

参考

CTFの過去問を解いてOllyDbgの使い方を覚える。

はじめに

問題の概要

使ったツール

手順

終わりに

参考にした書籍

参考にしたサイト