トランプのリフルシャッフルを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.objC:\Users\User\Desktop\overflow\overflow>overflow
foo() called. (buffer overrun!)
プロジェクトを作って逆アセンブルも見てみました
0x8b1310を見ればわかるように、fooのアドレスは0x8b10b9です。
見事にリターンアドレスが書き換えられ、この後foo()が呼び出されました。