トランプのリフルシャッフルをCで書いた

最近トランプのリフルシャッフルにはまってまして、聞くところによると完全に交互に噛み合わせるパーフェクトシャッフルを8回繰り返すと元の並びに戻るとか。リフルシャッフルのパーフェクトシャッフルをC言語で検証。
ちなみにトランプの英語表記はPlaying card - Wikipedia, the free encyclopediaが大いに参考になりました。

まずはトランプを構造体で定義し、ジョーカーを除いた52枚のトランプのデッキも定義する。

enum SUIT {
    SPADES,
    DIAMONDS,
    CLUBS,
    HEARTS
};

struct PlayingCard {
    enum SUIT suit;
    int rank;
};

struct CardDeck {
    struct PlayingCard parts[52];
};

CardDeck構造体をポインタで受けて新品のトランプを作る関数を作る。rankは便宜上1をエース、11をジャック、12をクイーン、13をキングと読み替えることにする。

void InitDeck(struct CardDeck* deck)
{
    int i, j;

    for(i = 0; i < 4; i++)
        for(j = 0; j < 13; j++)
        {
            deck->parts[i*13+j].suit = (enum SUIT)i;
            deck->parts[i*13+j].rank = j + 1;
        }
}

渡されたデッキをn回パーフェクトなリフルシャッフルする関数を作る。

void PerfectShuffle(struct CardDeck *deck, int n)
{
    int i, j;
    struct CardDeck tempdeck;

    for(i = 0; i < n; i++)
    {
        tempdeck = *deck;
        for(j = 0; j < 52; j++)
            deck->parts[j] = tempdeck.parts[j % 2 ? 26+j/2 : j / 2];
    }
}

stdio.hをインクルードして確認用のmain関数を適当に書く。書き方的にはここが一番うまくないと思います。

int main(void)
{
    int i, n;
    struct CardDeck deck;

    InitDeck(&deck);

    printf("How many times do you want to Shuffle? ");
    scanf("%d", &n);

    PerfectShuffle(&deck, n);

    for(i = 0; i < 52; i++) {
        switch(deck.parts[i].rank) {
        case 1:
            printf("Ace   ");
            break;
        case 11:
            printf("Jack  ");
            break;
        case 12:
            printf("Queen ");
            break;
        case 13:
            printf("King  ");
            break;
        default:
            printf("%-5d ", deck.parts[i].rank);
        }
        printf("of ");
        switch(deck.parts[i].suit) {
        case SPADES:
            printf("Spades");
            break;
        case HEARTS:
            printf("Hearts");
            break;
        case DIAMONDS:
            printf("Diamonds");
            break;
        case CLUBS:
            printf("Clubs");
            break;
        default:
            printf("UNKNOWN");
        }
        putchar('\n');
    }

    return 0;
}

そして、結果がこれで元に戻りました。

How many times do you want to Shuffle? 8
Ace   of Spades
2     of Spades
3     of Spades
4     of Spades
5     of Spades
6     of Spades
7     of Spades
8     of Spades
9     of Spades
10    of Spades
Jack  of Spades
Queen of Spades
King  of Spades
Ace   of Diamonds
2     of Diamonds
3     of Diamonds
4     of Diamonds
5     of Diamonds
6     of Diamonds
7     of Diamonds
8     of Diamonds
9     of Diamonds
10    of Diamonds
Jack  of Diamonds
Queen of Diamonds
King  of Diamonds
Ace   of Clubs
2     of Clubs
3     of Clubs
4     of Clubs
5     of Clubs
6     of Clubs
7     of Clubs
8     of Clubs
9     of Clubs
10    of Clubs
Jack  of Clubs
Queen of Clubs
King  of Clubs
Ace   of Hearts
2     of Hearts
3     of Hearts
4     of Hearts
5     of Hearts
6     of Hearts
7     of Hearts
8     of Hearts
9     of Hearts
10    of Hearts
Jack  of Hearts
Queen of Hearts
King  of Hearts

DXライブラリで角丸四角形を描く

要するに某アニメのEDで見た

こういうのがやってみたかっただけという。

作ったのがこれです。ろくなエラー処理してません。正方形前提なので縦横の長さが違うと失敗します。

int DrawRoundBox( int x1 , int y1 , int x2 , int y2 , int Color )
{
    int result = -1;
    int r = static_cast<int>(((x2 - x1) * 0.17 )/ 2);

    if(x2 - x1 != y2 - y1) return result;

    /* 四隅の円 */
    if((result = DrawCircle(x1 + r,     y1 + r,     r, Color, TRUE)) != 0)
        return result;
    if((result = DrawCircle(x2 - r - 1, y1 + r,     r, Color, TRUE)) != 0)
        return result;
    if((result = DrawCircle(x1 + r,     y2 - r - 1, r, Color, TRUE)) != 0)
        return result;
    if((result = DrawCircle(x2 - r - 1, y2 - r - 1, r, Color, TRUE)) != 0)
        return result;

    /* 円に被らない長方形 */
    if((result = DrawBox(x1, y1 + r, x2, y2 - r, Color, TRUE)) != 0)
        return result;
    if((result = DrawBox(x1 + r, y1, x2 - r, y2, Color, TRUE)) != 0)
        return result;

    return result;
}

描画イメージはこのように、四隅に適当な大きさの円を描いてからそれに被らない長方形を縦横それぞれ描いています。

適当に敷き詰めたらこんな感じになりました。まあいい感じ。

バッファオーバラン

2年以上放置してからの新しい記事。

gets()やscanf()がオーバーフローを起こすだのと世間で噂のバッファオーバラン。具体的にどうコードが実行されるのか謎だという方は結構いるんじゃないでしょうか。
いきなりですが、バッファオーバランの実験をしてみました。最適化しないでコンパイルしたらたぶん動きます。
バッファオーバーランが起こるとfoo()が呼び出され終了コード1で終了します。起こらなければ"The program is going to exit normally."と表示され終了コード0で終了します。

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

int i;  // overrun()内で宣言するとa[]のオーバーフローで上書きされる可能性がある

// foo()はどこからも呼び出されていない
void foo()
{
    printf("foo() called. (buffer overrun!)\n");
    exit(1);
}

void overrun()
{
    int a[1];

    for(i = 0; i < 5; i++)
        a[i] = (int)foo;    // foo()のアドレスを代入
}

int main(void)
{
    overrun();

    puts("The program is going to exit normally.\n");
    return 0;
}

Visual Studio 2012 x86 Nativeのプロンプトでコンパイル。

C:\Users\User\Desktop\overflow\overflow>cl -W4 overflow.c
Microsoft(R) C/C++ Optimizing Compiler Version 17.00.60315.1 for x86
Copyright (C) Microsoft Corporation. All rights reserved.

overflow.c
Microsoft (R) Incremental Linker Version 11.00.60315.1
Copyright (C) Microsoft Corporation. All rights reserved.

/out:overflow.exe
overflow.obj

C:\Users\User\Desktop\overflow\overflow>overflow
foo() called. (buffer overrun!)

プロジェクトを作って逆アセンブルも見てみました


0x8b1310を見ればわかるように、fooのアドレスは0x8b10b9です。
見事にリターンアドレスが書き換えられ、この後foo()が呼び出されました。