C++ における整数型の怪と "移植性のある" オーバーフローチェッカー (第3回 : C言語の整数の性質を知る)

# はじめに

第3回は、割と独立性の強い回です。連載を読んでいない人でも大丈夫……なようにしたいです。

この連載では、C++ の整数型の奇妙な特性、そしてその中で整数オーバーフローを引き起こさないためのオーバーフローチェッカーをどう書くか、について主に解説しています。

第3回は、当初符号付きオーバーフローチェッカーのさわりに入っていく予定でしたが、自作の整数オーバーフローチェッカーである ZSafeInt を記述する間に当初私が持っていた整数演算の知識だけでは追いつかなくなりました。@k-satoda 氏の入れ知恵もあり、整数演算の厳密な挙動を観察した結果……これはもう1回書かないと、という風になってしまいました。

第3回では、C言語および C++ における、整数演算の基礎知識について改めてまとめてみようと思います。

なお、[第2回][article_02]で出した練習問題の答えは[第4回][article_04]で発表します。


# 連載インデックス

[article_01]: http://qiita.com/a4lg/items/541c9d9dd5d874eeef2f
[article_02]: http://qiita.com/a4lg/items/3b92538049969715bf10
[article_03]: http://qiita.com/a4lg/items/9546ea49b8c1f98e6603
[article_04]: http://qiita.com/a4lg/items/68b7fab23678b5354b01
[article_05]: http://qiita.com/a4lg/items/bc4d2cfbce22fe749589

* 第1回 : [整数型の怪と対策の不足][article_01]
* 第2回 : [符号無し整数型のチェック][article_02]
* 第3回 : [C言語の整数の性質を知る][article_03]
* 第4回 : [符号付き整数型のチェックと動機の動機][article_04]
* 第5回 : [続・符号付き整数型のチェック][article_05]


# 練習問題 3 : ウノミにできないビット反転

(答えはこの回の下の方で出しますが、答えのようなものはこの回の途中で出てきます)

`uint8_t` は無条件に定義されることが約束されている型ではありませんが、この問題ではそれが定義されているものとします。

このとき、次のコードは必ず実装依存の挙動を含みます。さて、その理由は何故でしょう?

```cpp
uint8_t ones_complement(uint8_t value)
{
	return ~value;
}
```


# 整数演算の前に起こる型変換

実は、組み込み演算のほとんどが実際の演算を行う**前に**次のような型変換を行います。

* 整数昇格 (Integral Promotion)
* 通常の算術変換 (Usual Arithmetic Conversions)

が、まずはこれらを解釈するために必要になる 整数変換ランク (Integer Conversion Rank) について見ていきましょう。


# 整数変換ランク (Integer Conversion Rank)

全ての組み込み整数型には、処理系によって割り当てられた整数変換ランク (Integer Conversion Rank; 以後 "ランク") というものが割り当てられています。C++14 においてこれを決定するルールのうち重要な部分は次の通りです (いずれも引用ブロックは ISO/IEC 14882:2014 のセクション 4.13、第1 パラグラフより引用、翻訳の上、場合によって表現を変更しました)。

> 全ての符号付き整数型 (`char` が符号付きの場合、`char` と `signed char` を除く) には、異なるランクが割り当てられる。これは 2 つの型が同じ表現を持っていたとしても同様である[^1]。

[^1]: `typedef` にはこの条件は適用されません。あくまで、組み込みで定義された符号付き整数型が該当します。

これは、`signed char` や `short`、`int`、`long` などが異なるランクを持っていることを保証します。ただし `char` が符号付きである場合、`signed char` と `char` は同じランクを持っていても構いません (というより、後述の規定により同じランクを持っていなくてはなりません)。

> ある符号付き整数型のランクは、全てのより小さなサイズの符号付き整数型より大きい。

サイズ、という概念が曖昧ですが、ここは素直に読み解いてみましょう。広い表現可能範囲を持つ型は狭いものより大きなランクを持ちます。

> 次の整数型については、大きな順に次のランクが割り当てられる。
>
> * long long int
> * long int
> * int
> * short
> * signed char

組み込みの符号付き整数型について、そのランクの序列がどのようになっているかを指定します。おそらく、皆さんが予想された通り。

> 全ての符号無し整数型のランクは、対応する符号付き整数型のランクと同一である。

これにより、`unsigned char`、`unsigned int` などの型のランクとその序列が定義されます。"対応する符号付き整数型" という表現が見えますが、これは 3.9.3 第3 パラグラフにおいて、"それぞれの標準符号付き整数型について、対応する (だが異なる) 標準符号無し整数型が存在する" と定義されていることと関連しています[^2]。

[^2]: また、拡張整数型についても符号付きのものに対応する (異なる) 符号無し型が存在することが規定されています。

この規定により、例えば次のような対応を持つことになります。同じ行に記した型は、同じランクを持ちます。

| ランク | 標準符号付き整数型 | 標準符号無し整数型 |
|--------|------------------|-------------------|
| 大きい | long long | unsigned long long |
|| long | unsigned long |
|| int | unsigned |
|| short | unsigned short |
| 小さい | signed char | unsigned char |

> `char` のランクは `unsigned char` および `signed char` と同一である。

ここで、前述の小さな穴が塞がれます。

> `bool` のランクは、あらゆる標準の整数型より小さい。

標準の整数型 (standard integer types) は、上の表に記された 10 個の型のことを指します。`bool` のランクは、これらより小さくなければなりません。

> `char16_t`、`char32_t` および `wchar_t` については、背後にある整数型と同じランクを持つ。

`char` 以外の文字型に対する定義です。C++ 規格書内において `char16_t` の背後にあるのは `uint_least16_t`、`char32_t` の背後にあるのは `uint_least32_t` であると定義されているので、これらの型と同じランクを持ちます。

`wchar_t` と背後にある型との関連は C++ 規格書でもその背後にある C 規格書でも十分に定義されておらず[^3]、他の整数型どれかと関連付けられている程度に覚えておけば OK です。

[^3]: `wint_t` が定義されているではないかと思った方、不正解。`wint_t` は `wchar_t` とほぼ同じく拡張文字セット (extended character set) の全てのメンバーを格納できる型として定義されており、サイズの大小については規定されていない (よって C++ 規格書内の "背後にある型" (underlying type) としての条件を一般には満たせない) のです。

なお、これら 3 つの型と `bool` そして `char` は C++ 規格定義上の整数型 (integer types) ではなく、より広い (integer types を含む) integral types の一員です。

> _略記_: `rank(T1) > rank(T2)` かつ `rank(T2) > rank(T3)` ならば、`rank(T1) > rank(T3)`。

これは、ランク同士が全順序の性質を満たすことを保証します。つまり、コンパイラ内ではこのような順序をグラフのポインタのようなものではなく単純な整数として現すことができます。


## やはり C++ の怪 : 整数変換ランクと C++ にない規定

上では "サイズ" というものを深読みせず素直に表現可能範囲と関連付けましたが、……実のところそれを保証できるわけではありません。そしてサイズと表現可能な値の範囲が対応しない場合、面倒なことが起こります。これが起こりうるのは、C99 において定義されている次のような規定が抜けているからです。

> ある整数型と同じ符号 _(訳注: の有り無し)_ および異なる整数変換ランクを持つ別の整数型があったとき、小さなランクを持つ型の範囲は大きなランクを持つ型の範囲の一部である。

つまり、C99 では符号無し、符号付きのそれぞれについて、表現可能な範囲とランクが直結することを規定しているわけです。

なお、C++ でも限定的な規定? (すぐ下で記述) があり、int や unsigned int より小さい型では普通の算術演算による問題が生じることはありません (無いはず……です)。またそれより大きな型でも、この規定を暗黙の内に仮定しないと整数の変換周りで悲惨なことになることから、おそらく……定義が飛ばされているだけなのだと思います。


# 整数昇格 (Integral Promotion)

さて、ほとんどあらゆる演算子の使用において、この昇格というものが先立って行われます。整数型については、暗黙の型変換が行われるわけです。ルールは次の通り。

> `bool`、`char16_t`、`char32_t`、`wchar_t` を除くランクが `int` より下の整数型を持つ prvalue は、
>
> * `int` が元の型の全ての値を表現できるなら `int` の
> * そうでなければ `unsigned int` の
>
> prvalue に変換することが可能である。

これを間接的に確認してみましょう。

```cpp
#include <type_traits>

/* ... */

signed char c1 = /* ... */;
signed char c2 = /* ... */;
// (c1 * c2) の型をチェックする
static_assert(std::is_same<decltype(c1 * c2), int>::value, "signed char 同士の掛け算の結果は int");
```

上の `static_assert` は成功するはずです。これは概ね次の理由によります。

1. 掛け算の前に、両方のオペランドに対して整数昇格が行われる (`signed char` → `int`)
2. 掛け算の結果は、後述する "通常の算術変換" の結果 (整数昇格後に両オペランドの型が同じであるため)、両オペランドと同じ `int` 型になる

これは小さな符号無し整数型を扱う上では注意しなければならない点で、不注意だと容易に実装依存の挙動を作りこんでしまいます。

> `char16_t`、`char32_t` および `wchar_t` 型の prvalue は、次のうち値の範囲がすべて表現可能な最初の型 (もし存在する場合) となる。
>
> * int
> * unsigned
> * long
> * unsigned long
> * long long
> * unsigned long long
>
> 値の範囲がすべて表現可能な型が上のリストになかった場合、元の型の背後にある型の prvalue に変換される。

また、

> `bool` 型の prvalue は、`false` が 0、`true` が 1 と対応する `int` 型の prvalue に変換される。

これらは最初のルールで明記されなかった `bool`、`char16_t`、`char32_t`、`wchar_t` 型に対するルールです。

この他にも列挙型やビットフィールド型に対する整数昇格のルールがあるのですが、ここでは省略します。ともかく、落とし穴を避けるために覚えておくことは次の 2 つです。

1. int や unsigned int よりも小さな整数型は演算**前**に int や unsigned int 型に変換される。
2. その際、変換前の型に符号がなかったとしても変換後につくことがある。


# 通常の算術変換 (Usual Arithmetic Conversions)

さらに、四則演算や比較のような二項演算では、整数昇格を行った後でさえ左右の型が異なるという場合があります。C++ では特定の算術演算において、この "通常の算術変換" を行うことにより、演算に用いる共通型 (演算においては演算結果の型にもなる) を決める必要があります。

このルールのうち、整数型のみが関わる部分について見てみましょう。

> 整数昇格が両方のオペランドに対して実行され、昇格されたオペランドに対して次のルールを適用する。
>
> 1. 両方のオペランドが同じ型である場合、さらなる変換は実行されない。
> 2. _(上記に当てはまらず)_、両オペランドともに符号無し整数型であるか両オペランドともに符号付き整数である場合、小さなランクを持つオペランドの型が大きなランクを持つオペランドの型に変換される。
> 3. _(上記に当てはまらず)_、符号無しであるオペランドの型が符号付きオペランドの型のランク以上である場合、符号付きオペランドは符号無しオペランドの型に変換される。
> 4. _(上記に当てはまらず)_、符号付きオペランドの型が符号無しオペランドの型の値をすべて表現できる場合、符号無しオペランドが符号付きオペランドの型に変換される。
> 5. 上記すべてに当てはまらない[^4]場合、両方のオペランドが、符号付きオペランドの型 (符号付き整数型) に対応する符号無し型に変換される。

[^4]: 符号付きオペランドの型が符号無しオペランドの型の値を十分に表現できず、にも関わらずランクでは上に位置しているとき。

最初の 4 つに該当する例を見てみましょう (掛け算を用いているのは、足し算などにあるポインタ加算などの特殊ルールを見ないようにするためです)。

```cpp
#include <cstdint>
#include <type_traits>

int i1, i2;
unsigned u1, u2;
long l1, l2;

uint32_t u32_op;
int64_t  s64_op;

// ルール 1 (同じ型 2 つの共通型は、その文字通り共通する型)
static_assert(std::is_same<decltype(i1 * i2), int>::value, "int 同士の共通型は int");
// ルール 2 (両方とも符号付きもしくは両方とも符号無しなら、共通型は大きなランクの方)
static_assert(std::is_same<decltype(i1 * l1), long>::value, "int と long との共通型は long");
// ルール 3 (符号無しオペランドの型のランクが符号付きオペランドの型以上ならば符号無しを選択)
static_assert(std::is_same<decltype(i1 * u1), unsigned>::value, "int と unsigned との共通型は unsigned");
// ルール 4 (符号付きの方が符号無しオペランドの型の表現可能範囲をカバーできるなら、符号付きを選択)
// 注: ここでは、uint32_t と int64_t に対しては整数昇格を行っても元の型のままと仮定 (環境依存!)
static_assert(std::is_same<decltype(u32_op * s64_op), int64_t>::value,
	"我々がよく知る処理系の多くでは、uint32_t と int64_t との共通型は int64_t");
// ルール 5 はおそらく読者のよく使う環境では再現できない
```

5 つのルールのうちルール 3 とルール 5 では場合によっては意図しない (符号付きから符号無しへの) 型の変換が行われ、いずれも共通型は符号無しになることが分かります。ルール 3 が関わる具体例について見てみましょう。

```cpp
#include <limits>
#include <type_traits>

static_assert(std::numeric_limits<unsigned>::max() == 0xfffffffful, "次のデモは unsigned が 32-bit であることを仮定");

static_assert(std::is_same<decltype(unsigned(0x80000000ul) * int(-1)), unsigned>::value,
	"int と unsigned との共通型は unsigned");
static_assert(unsigned(0x12345678ul) * int(-1) == unsigned(0xedcba988ul),
	"int(-1) が unsigned(0xfffffffful) に変換され (C++ 規格規定と上記 assert による)、"
	"0x12345678 と掛けられた結果は unsigned 型の 0xedcba988 になるはず");
```

このように、見方によっては予期しない値となります。


# 算術演算子と、使われるルール

| 演算 | 結果の型 |
|------|---------|
| `+a` | `a` の整数昇格型 |
| `-a` | `a` の整数昇格型 |
| `~a` | `a` の整数昇格型 |
| `a + b` | 通常の算術変換に従う |
| `a - b` | 通常の算術変換に従う |
| `a * b` | 通常の算術変換に従う |
| `a / b` | 通常の算術変換に従う |
| `a % b` | 通常の算術変換に従う |
| `a & b` | 通常の算術変換に従う |
| `a ^ b` | 通常の算術変換に従う |
| `a ` &#x7c; ` b` | 通常の算術変換に従う |
| `a << b` | `a` の整数昇格型 (`b` も内部的に整数昇格を受ける) |
| `a >> b` | `a` の整数昇格型 (`b` も内部的に整数昇格を受ける) |

これらの他に、通常の算術変換が行われる演算子があります (結果の型はいずれも `bool` です)。

* `a == b`
* `a != b`
* `a < b`
* `a > b`
* `a <= b`
* `a >= b`

`!a` は、`a` を `bool` 型に変換した後に反転を行います。`a || b` や `a && b` のような演算子も、`a` と `b` を `bool` 型に変換してから演算します。そのため、整数昇格や通常の算術変換は行われません。

また `a++`、`++a`、`a--`、`--a` といったインクリメント/デクリメント演算子の返す値の型は、`a` の型をベースにしています。ここでも、整数昇格や通常の算術変換は行われません。


# あとがき / 次回予告

普通の算術演算子でも、罠が結構あるんですね……。これは別に C/C++ だけに限った話ではなく、C# などでも小さな型の演算結果が `int` になるなどの罠があるわけです。こういうことがある、というのは覚えていて損ではないでしょう。

次回こそ符号付き整数のオーバーフローチェッカーについて書き始めたいです。


# 解答 3 : ウノミにできないビット反転

答えは、`uint8_t` 型から `int` 型への変換が行われ、それに対してビット反転が成されてしまうから、でした。

```cpp
uint8_t ones_complement(uint8_t value)
{
	return ~value;
}
```

この中身を詳しく見ていきましょう。

1. `uint8_t` 型の `value` を `int` 型に変換する 
2. `int` 型の値を用いてビット反転を行う
3. ビット反転を行った結果 (`int` 型) を `uint8_t` 型に変換する
4. `uint8_t` 型の値を返す

このうち問題となるのがステップ 2 と、それに続く 3 です。

ステップ 2 で反転するオペランドはステップ 1 で変換された `int` 型の値です。その結果、ビット反転の値が実装依存の値となってしまいます。

その実装依存の値を無理に考えた場合……2 の補数表現が使われていた場合、ステップ 3 の変換 (こちらは C++ 規格でキッチリ決まっている) の結果、ぱっと見では正しい値が返されることが考えられます。しかし、それは実装依存の挙動の結果である、ということに注意すべきです。

例えば 1 の補数表現環境で引数に 0 を与えた場合、予期している `0xff` ではなく 0 を得ることすら考えられるのです。

対処としては、`unsigned` 以上の大きさの符号無し整数型に変換してから演算を行うか、もしくは `0xff` との XOR を取る、というものがあります。こちらであれば、`int` 型への変換が挟まっても問題になりません。対策例は次の通り。

```cpp
uint8_t ones_complement(uint8_t value)
{
	return value ^ UINT8_C(0xff);
}
```