4

次のようなコードを書きました。(問題がどこにあるかわからないため全部引用します)

#include <stdint.h>
#include <inttypes.h>
#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

struct player {
    uint_fast8_t card;
    uint_fast8_t rank;
};

static uint_fast8_t get_card_power(const char *card_string);
static void show_result(const struct player *player_list);
static uint_fast8_t get_max_card_power(uint_fast8_t *card_left, uint_fast8_t card);

int
main(void)
{
    struct player player_list[] = {[51] = {0, 0}};
    // struct player *player_list = calloc(52, sizeof(struct player));
    // assert(NULL != player_list);
    for (uint_fast8_t i = 0; i < 52; ++i) {
        char card[2];
        int scanf_count = scanf("%2s", card);
        assert(1 == scanf_count);
        player_list[i].card = get_card_power(card);
    }
    uint_fast8_t current_card = 0;
    uint_fast8_t current_rank = 1;
    uint_fast8_t max_card_power = 13;
    uint_fast8_t card_left[] = {0, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4};
    while (true) {
        for (uint_fast8_t i = 0; i < 52; ++i) {
            if (0 < player_list[i].rank) {
                continue;
            }
            if (current_card < player_list[i].card) {
                player_list[i].rank = current_rank++;
                if (52 < current_rank) {
                    show_result(player_list);
                    exit(EXIT_SUCCESS);
                }
                current_card = player_list[i].card;
                max_card_power = get_max_card_power(card_left, current_card);
                if (max_card_power <= current_card) {
                    current_card = 0;
                }
            }
        }
    }
    return 0;
}

static uint_fast8_t
get_card_power(const char *card_string)
{
    assert(NULL != card_string);
    if (0 == strcmp(card_string, "10")) {
        return 8;
    }
    static const uint_fast8_t card_power_map[] = {['3'] = 1, ['4'] = 2, ['5'] = 3, ['6'] = 4, ['7'] = 5, ['8'] = 6,
            ['9'] = 7, ['J'] = 9, ['Q'] = 10, ['K'] = 11, ['A'] = 12, ['2'] = 13};
    assert(0 <= *card_string);
    assert(*card_string <= 'Q');
    uint_fast8_t ret = card_power_map[(unsigned char) *card_string];
    assert(0 < ret);
    return ret;
}

static void
show_result(const struct player *player_list)
{
    assert(NULL != player_list);
    for (uint_fast8_t i = 0; i < 52; ++i) {
        assert(0 < player_list[i].rank);
        int printf_count = printf("%" PRIuFAST8 "\n", player_list[i].rank);
        assert(0 <= printf_count);
    }
}

static uint_fast8_t
get_max_card_power(uint_fast8_t *card_left, uint_fast8_t card)
{
    assert(NULL != card_left);
    assert(0 < card_left[card]);
    --card_left[card];
    for (uint_fast8_t i = 13; 1 <= i; --i) {
        if (0 < card_left[i]) {
            return i;
        }
    }
    assert(false);
    return 0;
}

このコードはある「オンラインハッカソン」、具体的には https://paiza.jp/poh/hatsukoi/challenge/hatsukoi_clothes5 の回答です。回答はtextareaに貼り付けて提出し、後述しますがこの回答は正解です。

さて、問題なのは、このコードの動作です。
上記サイトでは「提出前動作確認」として1つの入力に対して出力が正しいか確認できます。
私はこのコードを書いて、手元でその入力を用いて正しい出力が得られることを確認しました。
そこでサイトで「提出前動作確認」を行ったところ、不正解となりました。
printf()による地道なデバッグの結果、どうも同サイトに提出して動作させるとplayer_list[i].cardが意図しない値になっているようなのです。
この変数は最初のforループ内で定義され、以降は参照しかされません。
かつこれを与えるget_card_power()は内部でassert()により、0より大きい値しか返さないことが保証されています。
しかしなぜかこの変数が0になることがあるようです。そのタイミングは不定で、デバッグ用printf()を仕込むタイミングで変わってきます。

この現象に気が付き、コメントアウトされているように配列ではなくcalloc()にて領域を確保するようにしたところ、正常に動作し正解となりました。

そこで質問ですが、このような動作をする原因は何が考えられるでしょうか。
サイト管理者に聞いたほうがわかるかとも思いますが、「ここで未定義の動作をする可能性がある」といった一般的な理由があれば、サイト管理者に聞くようなことではないと考えています。

なおサイト上の動作環境は

  • gcc 4.8.2 (C99)
  • メモリサイズ 512 MiB

とのみ示されています。
私の手元の環境は gcc 4.8.4 (ubuntu) です。

1
  • 1
    @metropolis -fsanitize=addressを使うことで手元で領域外アクセスを検出できました。ただし-lasanが必要であったのと、例示されたほどわかりやすいエラー出力ではありませんでした(gccのバージョンによる?)が、検出出来るだけでも助かります。ありがとうございます。
    – quasar
    Commented 2016年6月26日 12:48

2 件の回答 2

10

既にクローズされていますので参考までに。

gcc には sanitize オプションというものがありまして、その内の一つに配列変数などの宣言領域を超えるアクセス(out-of-bounds access)を実行時に検出する機能があります。具体的には -fsanitize=address を付けてコンパイルします。

$ gcc -std=gnu99 -Wall -fsanitize=address -g cloth.c -o cloth
$ ./cloth
4
=================================================================
==26858==ERROR: AddressSanitizer: stack-buffer-overflow on address 0xbfe95522 ...
WRITE of size 3 at 0xbfe95522 thread T0
    #0 0xb71e211b  (/usr/lib/i386-linux-gnu/libasan.so.3+0x4311b)
    #1 0xb71e2cab in __isoc99_vscanf (/usr/lib/i386-linux-gnu/libasan.so.3+0x43cab)
    #2 0xb71e2d27 in __interceptor___isoc99_scanf (...
    #3 0x804892f in main cloth.c:26  <== "int scanf_count = scanf("%2s", card);"
    #4 0xb7001636 in __libc_start_main (/lib/i386-linux-gnu/libc.so.6+0x18636)
    #5 0x8048780  (cloth+0x8048780)

Address 0xbfe95522 is located in stack of thread T0 at offset 194 in frame
    #0 0x804886a in main cloth.c:20  <== "main function frame"

  This frame has 3 object(s):
    [32, 136) 'player_list'
    [192, 194) 'card' <== Memory access at offset 194 overflows this variable
    [256, 270) 'card_left'

char card[3]; に修正すると、上記のエラーメッセージは出力されなくなります。

ところで、scanf(3) の書式文字列には POSIX.1-2008 において導入された m modifier を使うことができます。この場合、配列変数を用意する必要がなくなります。ただ、下記に引用した文章に書かれてある通り、確保したメモリ領域を free(3) で解放する必要はあります。

scanf(3)

DESCRIPTION

An optional 'm' character. This is used with string conversions (%s, %c, %[), and relieves the caller of the need to allocate a corresponding buffer to hold the input: instead, scanf() allocates a buffer of sufficient size, and assigns the address of this buffer to the corresponding pointer argument, which should be a pointer to a char * variable (this variable does not need to be initialized before the call). The caller should subsequently free(3) this buffer when it is no longer required.

char *buf;
scanf("%ms", &buf);
      :
free(buf);
2
  • 2
    示していただいたscanf(3)の説明を見ると、mmodifierはPOSIXに準拠していれば使える(GNU拡張ではない)ように見えるのですがいかがでしょうか?
    – quasar
    Commented 2016年6月26日 12:51
  • 1
    @quasar すみません、「POSIX.1-2008 instead 〜」の部分を読み飛ばしていました。後ほど修正します。
    – user39889
    Commented 2016年6月26日 13:09
9

他にも何かあるかもしれませんが、少なくともここ:

        char card[2];
        int scanf_count = scanf("%2s", card);

"%2s"を使用するなら、バッファは3バイト(以上)必要ですから、ここで隣接する領域(何かの自動変数の一部である可能性が高い)を破壊してしまいます。char card[3];に変更した場合の動作はどうなりますか?

1
  • char card[3];とすることにより正常動作するようになりました。 見落としていたのが恥ずかしい。しかし質問してよかったと思いました。 ありがとうございます。
    – quasar
    Commented 2016年6月26日 6:25

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。