Tociyuki::Diary RSSフィード

tociyuki による Perl・Ruby・C++・C で書き散らしたコードを中心に、日常雑記も混在 : B  F  twitter  GitHub  CPAN  本館  公開鍵
 | 

2014年09月06日

[][]符号なし加算の桁あふれと符号なし減算の桁借り

C 言語のほとんどの実装は、符号なし整数を剰余項として扱うだけで、桁あふれの発生を通知する機構を持つ数値型を提供していません。剰余項の加算の桁あふれは範囲チェックをすり抜ける原因になり、桁あふれを無視したことがセキュリティ・ホールになった事例がいくつも報告されています。桁あふれ判定はプロセッサの演算回路に必須の機能なので、ハードウェアは桁あふれの有無を加算時に常にチェックしています。ですが、ハードウェアで検出されている桁あふれの有無を C 言語で変数へ得るにはインライン・アセンブラの助けが必要になります。例えば、x86 アーキテクチャの場合、GNU C のインライン・アセンブラでプロセッサのキャリーフラグを読み出すことで、桁あふれと桁借りを変数に求めることができます。

    uint32_t carry;   /* 0: 桁あふれなし, 1: 桁あふれあり */
    uint32_t borrow;  /* 0: 桁借りなし, 1: 桁借りあり */
    uint32_t x;
    uint32_t y;

    /* 半加算  carry, x = x + y; */
    __asm__ volatile (
    "xorl    %0, %0\n\t"
    "addl    %2, %1\n\t"
    "rcll    %0"
    :"=&r"(carry),"+r"(x):"r"(y));

    /* 全加算  carry, x = x + y + carry; */
    __asm__ volatile (
    "shrl    %0\n\t"
    "adcl    %2, %1\n\t"
    "rcll    %0"
    :"+&r"(carry),"+r"(x):"r"(y));

    /* 半減算  borrow, x = x - y; */
    __asm__ volatile (
    "xorl    %0, %0\n\t"
    "subl    %2, %1\n\t"
    "rcll    %0"
    :"=&r"(borrow),"+r"(x):"r"(y));

    /* 全減算  borrow, x = x - y - borrow; */
    __asm__ volatile (
    "shrl    %0\n\t"
    "sbbl    %2, %1\n\t"
    "rcll    %0"
    :"+&r"(borrow),"+r"(x):"r"(y));

桁あふれビットを演算回路が必ず発生させているとはいえ、設計との兼ね合いで読み出せないアーキテクチャも存在します。なので、移植性を重視するなら、ソフトウェアだけで桁あふれをや桁借りを判定する方法が必要になります。

carry と borrow をソフトウェアだけで得るには、The GNU MP Bignum Library にならって、剰余項の加算の性質を使います。つまり、R の剰余項同士の加算で桁あふれが生じるときは、加える数が R の補数で負数としてふるまうため、引き算することを利用します。結論をてっとり早く書くと、足した結果が減っていれば桁あふれが生じていることになります。桁借りの理屈は単純で引く数の方が大きいと桁借りになります。C 言語は、条件式が真のときは値は 1 になって、偽のときはゼロになるという bool 型と整数型を混同できる困った性質をもつので、それを使います。

    /* 半加算  carry, x = x + y; */
    x += y;
    carry = (x < y);

    /* 全加算  carry, x = x + y + carry; */
    x += carry;
    carry = (x < carry);
    x += y;
    carry += (x < y);

    /* 半減算  borrow, x = x - y; */
    borrow = (x < y);
    x -= y;

    /* 全減算  borrow, x = x - y - borrow; */
    y += borrow;
    borrow = (y < borrow);
    borrow += (x < y);
    x -= y;

証明を略しますが、全加算と全減算の 2 つの条件判定は、両方とも偽か、いずれか一方が真になることはありますが、両方とも真になることはありえません。そのため、carry と borrow はゼロか 1 の値しかとりません。この手のイディオムは、コンパイラが検出して、x86 の場合はインライン・アセンブラの簡潔で高速なコードを生成してくれるとありがたいのですが、GNU C と Clang/LLVM は、そこまでは気をきかせてくれないようです。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/tociyuki/20140906/1410012689
 |