バイナリ(2進数)でのデータ表現

2進数と符号化

ここでも説明しましたが， コンピュータの中のデータは，どんな種類のデータ(例えば，整数，文字， 音声，画像)であっても， 機械語命令であっても，すべて0と1だけで表現されています．

そして，そのためにデータの種類ごとに2進数での表現方法，つまり符号化 (encoding)の方法が定められています． 例えば，

• 文字UをASCII文字として符号化すると，01010101になります．
• pushq %rbpをx86-64の機械語命令として符号化すると，01010101になります．

おや，どちらも同じ01010101になってしまいました． この2進数がPなのかpushq %rbpなのか，どうやって区別すればいいでしょう？ 答えは「これだけでは区別できません」です．

別の手段（情報）を使って，いま自分が注目しているデータが， 文字なのか機械語命令なのかを知る必要があります． 例えば，この後で説明する.textセクションにある 2進数のデータ列は「.textセクションに存在するから」という理由で 機械語命令として解釈されます．

以下では，整数(特に2の補数による負の数の表現)， ASCII文字コード，機械語命令の符号化などを説明します．

2進数と10進数と16進数

位取り記数法

• 10進数で \( 234 \) という数字の値は \[ 2\times 10^2 + 3\times 10^1 + 4\times 10^0 = 200 + 30 + 4 = 234 \]

• 2進数で \( 1101 \) という数字の値は (2進数→10進数の変換)

\[ 1\times 2^3 + 1\times 2^2 + 0\times 2^1 + 1\times 2^0 = 8+4+0+1=13 \]

• 一般的に，n進数で \( d_m d_{m-1} \cdots d_2 d_1 d_0 \) という数字の値は \[ \sum_{i=0}^m d_i\times n^i = d_m\times n^m + d_{m-1}\times n^{m-1} + \cdots d_2\times n^2 + d_1\times n^1 + d_0\times n^0 \]

  • この「数字を並べる記法」を位取り記数法 (positional notation)という．
  • nを底 (base), あるいは基数 (radix)と呼ぶ．

• 16進数も同様

  • 0から9，AからFまでの数字を使う．Aは10，Bは11，\(\cdots\)，Fは15を表す．
  • 16進数で \( 1\mathrm{F}4 \) という数字の値は (16進数→10進数の変換) \[ 1\times 16^2 + \mathrm{F}\times 16^1 + 4\times 16^0 = 256 + 240 + 4 = 500 \]
  • 2進数は表記が長くなるため，16進数を使って短く表記すると便利(だから使う)．

対応表

変換方法

2進数→16進数，16進数→2進数

• 最下位ビットから4桁ずつまとめる(上位ビットには0を埋める)． 4ビットごとに16進数にすれば良い(10進数ではこの方法は使えない)

10進数→2進数

• 割り算を使う方法

  • 0になるまで繰り返し2で割り，余りを逆順に並べる．
  • 例: 13を2進数に変換

  \[ \left. \begin{align} 13\div 2 = 6 \cdots 1 \\ 6\div 2 = 3 \cdots 0 \\ 3\div 2 = 1 \cdots 1 \\ 1\div 2 = 0 \cdots 1 \end{align} \right\} 余りを下から上に並べて 1101 \]

  • これでうまくいく理由は以下の計算と同じだからです

\[ \begin{eqnarray} 13 &=& 2\times6 + \textcolor{red}{1} \\ &=& 2 \times (2 \times 3 + \textcolor{green}{0}) + \textcolor{red}{1}\\ &=& 2 \times (2 \times (2 \times 1 + \textcolor{blue}{1}) + \textcolor{green}{0}) + \textcolor{red}{1}\\ &=& 2 \times ( 2 \times (2 \times (2 \times 0 + \textcolor{magenta}{1}) + \textcolor{blue}{1}) + \textcolor{green}{0}) + \textcolor{red}{1}\\ &=& 2 \times ( 2 \times (2^2 \times 0 + 2^1 \times \textcolor{magenta}{1} + 2 ^0 \times \textcolor{blue}{1}) + \textcolor{green}{0}) + \textcolor{red}{1}\\ &=& 2 \times ( 2^3 \times 0 + 2^2 \times \textcolor{magenta}{1} + 2^1 \times \textcolor{blue}{1} + 2^0 \times \textcolor{green}{0}) + \textcolor{red}{1}\\ &=& 2^4 \times 0 + 2^3 \times \textcolor{magenta}{1} + 2^2 \times \textcolor{blue}{1} + 2^1 \times \textcolor{green}{0} + 2^0 \times \textcolor{red}{1}\\ &=& (2進数で)\textcolor{magenta}{1}\textcolor{blue}{1}\textcolor{green}{0}\textcolor{red}{1}\\ \end{eqnarray} \]

• 2のべき乗を使う方法

  • 大きい2のべき乗から順番に， 例えば，\(2^3=8\)を引けたら，\(2^3\)の位を1にする． 0になるまで繰り返す．
  • 例: 13を2進数に変換

\[ \left. \begin{eqnarray} 13 - 2^3 &=& 5 \rightarrow 2^3の位は1 \\ 5 - 2^2 &=& 1 \rightarrow 2^2の位は1 \\ 1 - 2^1 &=& 引けない \rightarrow 2^1の位は0 \\ 1 - 2^0 &=& 0 \rightarrow 2^0の位は1 \end{eqnarray} \right\} 上から下に並べて 1101 \]

• bcコマンドを使う方法

  • bcは電卓コマンド．

    $ bc
    1+2*3+10/5
    9
    ^D         (ctrl-dで終了)
    $
    

  • 例: 10進数 13を2進数に変換

    $ bc
    obase=2  (出力の底を2に変更)
    13
    1101     (13の2進数は1101)
    ^D
    $
    

  • 例: 16進数 1F4 を2進数に変換

    $ bc
    obase=2    (出力の底を2に変更)
    ibase=16   (入力の底を16に変更，入力の底の変更は出力の後が良い)
    1F4
    111110100  (1F4の2進数は111110100)
    ^D
    $
    

用語: ビット，バイト，LSB，MSB

ビットとバイト

• ビット (bit)

  • ビットはコンピュータが扱うデータ量の最小単位．binary digit の略．
  • 2進数のひと桁が1ビット．1ビットで0か1かの2通りの状態を表現．

• バイト (byte)

  • 通常，8ビットのこと

• ビットやバイトはレジスタやメモリなどの記憶領域の容量の単位としても使われます
  • レジスタ%raxは8バイトのデータを格納できます．
  • (バイトアドレッシングの)メモリは1つのアドレスごとに1バイトのデータを格納できます

MSBとLSB

• ビット列で最左のビットを最上位ビット (MSB, most significant bit)といいます
• ビット列で最右のビットを最下位ビット (LSB, least significant bit)といいます
• 多倍長データの最上位バイト (most significant byte)と 最下位バイト (least significant byte)も略称がMSBとLSBなので， どちらを指すかは要注意です

ビットの呼び方

• LSBから左に(0から始めて)0ビット目，1ビット目，...，7ビット目と呼ぶことが多いです (例えばIntelのマニュアルで Intel 64 and IA-32 Architectures Software Developer Manuals)
• 0から数え始めることを0オリジン (zero-origin)，あるいは0ベース (zero-based)といいます

ワード，ロング，クアッド

• ワード，ロング，クアッドのサイズはアーキテクチャ依存です． x86-64では，それぞれ，2バイト，4バイト，8バイトになります．
• C言語の整数型やポインタ型のサイズはプラットフォーム依存です． 最近主流のLP64データモデルでは， 上記の通り，intは4バイト，longとポインタは8バイトになります．
• GNUアセンブラでは次の表記等でデータのサイズを指定します．
  • アセンブラ命令で整数データを出力する際には， サイズに応じて，.byte，.word，.long，.quadを使います
  • 多くの機械語命令でオペランドのサイズを命令サフィックスで指定します． 例えば，movqは オペランドのサイズが8バイトであることを示します

<stdint.h>

• 符号あり

• 符号なし

• <stdint.h>は標準ヘッダファイルで，固定長の整数や 符号の有無を確実に扱いたい時に便利です．

文字コード

文字コードとは

• 文字コード = 各文字を区別するために，重複無く割り振った番号です
  • ASCIIコードで文字Aの文字コードは(7ビットの)65
  • ASCIIコードで文字9の文字コードは(7ビットの)57

// ascii.c
#include <stdio.h>
int main ()
{
    printf ("'%c', %d\n", 'A', 'A');
    printf ("'%c', %d\n", '9', '9');
}

$ gcc -g ascii.c
$ ./a.out
'A', 65
'9', 57

• 文字コードにはいろいろな種類がありますが，GNUアセンブラではASCIIコードのみを使います．

• 文字コードはフォント(書体)や文字の大きさの情報は含んでいません．

  

  例えば，上図の文字Aはフォントも大きさも異なりますが， どちらもASCIIコードでは同じ「7ビットの65」です．

ASCIIコード

ASCIIコード表

• 128個の文字を扱うコード体系
  • 通常，MSBを0にした1バイトデータとして扱う
• 英字アルファベット，数字，記号，制御文字 (control character)を含む

制御文字

• 制御文字は出力装置に(文字表示以外の)動作を要求します

  • 例: 改行文字 ^J (line feed, C言語では\n)は端末ディスプレイに改行を要求する． 「次に表示する位置を変更する」という動作を要求しています．

  • 例: エスケープ文字 ^[で始まる文字列 ^[[7mは文字反転， ^[[0mは元に戻すというANSIエスケープシーケンスです． 「次に表示する文字と背景の色を変更する」という動作を要求しています．

    $ echo -e "aaa \E[7mbbb\E[0m ccc"
    aaa bbb ccc
    $ cat
    aaa  ^[[7mbbb  ^[[0mccc     (ctrl-vを押してからエスケープキーを入力)
    aaa  bbb  ccc
    

    echoコマンドの-eは「バックスラッシュによるエスケープを解釈する」というオプションです．また，\Eはbashでエスケープ文字を表すエスケープシーケンスです． ほとんどの端末ソフトで文字列bbbと背景色の色が反転します． catコマンドの場合は，ctrl-vを押してからエスケープキーを押すと エスケープ文字が入力できて，^[と表示されます(2文字に見えますがこれで1文字です)．

  • ASCIIの以下の制御文字は覚えておきましょう．

    制御文字	意味	C言語のエスケープ文字	キーボード中のキー
    ^@	ヌル文字	\0
    ^D	End of File (EOF)
    ^H	Back Space (後退)	\b	Back Space
    ^I	Horizontal Tab (水平タブ)	\t	Tab
    ^J	Line Feed (改行)	\n
    ^M	Carriage Return (復帰)	\r	Enter
    ^[	Escape (エスケープ)		Esc
    ^?	Delete (削除)		Delete

ctrl-j や ctrl-m で改行できる(ことが多い)理由

• 歴史的な話ですが，ctrlキーを押しながら，あるキー(例えばj)を押すと， jのASCIIコード(2進数8ビット表記で 01101010)の 上位３ビットをゼロにした 00001010 (つまり改行文字 ^J)を入力できました．
• そのなごりで，今でもctrl-jやctrl-mを押すとEnterキーの入力と同じ動作を するソフトウェアが多くあります． 同様に，ctrl-iでTabを，ctrl-[でEscapeを，ctrl-hでBack Spaceを 入力できるソフトウェアが多いです．
• もちろん，現在ではキーの処理はソフトウェアごとに自由に決められるので， ctrl-jで常に改行できるわけではありません．

ファイルの改行文字

• LinuxやmacOSのファイルでは，通常，ファイル中の改行を Line Feed (^j, LF)の1文字で表します． 一方，Windows では Carriage Return (^m, CR)とLine Feed (^j, LF)の2文字で表すことが多いです． (ファイル中の改行文字はエディタの設定で通常，変更可能)．

• このため，Windows で作成したファイルを Linux で開くと， 行末に ^M が見えることがあります．「改行が CR LF なんだな」と思って下さい．

  $ ❶ cat foo2.txt
  hello
  byebye
  $ ❷ cat -v foo2.txt
  ❸ hello^M
  byebye^M
  
  $ ❹ od -c -t x1 foo2.txt
  0000000   h   e   l   l   o ❺ \r  \n   b   y   e   b   y   e  \r  \n
           68  65  6c  6c  6f    0d  0a  62  79  65  62  79  65  0d  0a
  0000017
  

  • 例えば，改行が CR LF なファイルfoo2.txtを用意して， ❶ catで表示すると普通に表示されますが， ❷ -vオプション(制御文字を可視化)を使うと，❸^Mが表示されました．
  • ❹ odコマンドを使っても，CRの存在を確認できます (❺ \r)．

文字集合と符号化方式，UnicodeとUTF-8

GNUアセンブラではASCIIコードのみを使用するので， この節の話はスキップ可能です．

• ASCIIコードでは文字コード(文字の背番号，コードポイント)をそのままバイナリ表現として使っていました．
• 一方，多くの文字コード体系では文字集合と符号化方式を区別しています．

  • 例えば，Unicodeは(ほぼ世界中の)文字を定める文字集合です． Unicodeで日本語の「あ」のコードポイントは0x3042です．

  • UTF-8はUnicodeの符号化方式の一つです． UTF-8で「あ」をバイト列に符号化すると，0xE3，0x81，0x82になります． (Unicodeの他の符号化方式として，UTF-16やUTF-32もあります)．

    

    $ cat a.txt
    あ
    $ od -t x1 a.txt
    0000000 e3 81 82 0a
    0000004
    

    odコマンドで確かめると「あ」が0xE3，0x81，0x82のバイト列と確認できます． 最後の0x0Aは改行文字 (\n)ですね．

  • 1110や 10を使う理由は あるバイトが文字の最初のバイトなのか，２バイト目以降なのかを簡単に 区別できるからです． また，1バイトの文字 (例えば A)と混同する心配もありません．

  • UTF-8はASCIIと互換性があるのが大きな利点です． ASCIIコードで書かれたテキストはそのままUTF-8として処理できます．

符号なし整数

符号なし整数のビット表現

• 2進数の各桁をそのままビット表現とする
  • 例: 2を8ビットの符号なし整数で表現すると， 2の2進数は10なので，00000010 になる． (余った上位ビットに0を入れることに注意)

符号なし整数の一覧表

• 前半

• 後半

符号なし整数の扱える範囲

• 固定長の整数の範囲は有限
  • 例: 8ビット符号なし整数が表現できる範囲は \(0\)から\(255\)まで
• 一般に\(n\)ビット符号なし整数の範囲は \(0\)から\(2^n-1\)まで
• (符号なしなので当然ですが)負の値は表現できない

符号なし整数の最大値と最小値のビットパターン

• 見やすさのため8ビットごとにスペースを入れてます
• 最小値は全てのビットが0，最大値は全てのビットが1
• 32ビット符号なし整数の最大値は約42.9億．現在の世界の人口(約80億人)を数えられない

符号なし整数のオーバーフロー

• 演算の結果，表現できる範囲を超えた場合をオーバーフロー (overflow)と言う．
• 8ビット符号なし整数が表現できる範囲は0から255まで(復習)
• 例: 8ビット符号なし整数の255に1を足すと，256は表現できる範囲外なので， オーバーフローして結果は0になる

// overflow1.c
#include <stdio.h>
#include <stdint.h>
int main ()
{
    uint8_t x = 255;    
    x++;
    printf ("%d\n", x);
}

$ gcc -g overflow1.c 
$ ./a.out
0

• 例: 8ビット符号なし整数の0から1を引くと，-1は表現できる範囲外なので， オーバーフローして結果は255になる

// overflow2.c
#include <stdio.h>
#include <stdint.h>
int main ()
{
    uint8_t x = 0;
    x--;
    printf ("%d\n", x);
}

$ gcc -g overflow2.c 
$ ./a.out
255

• 8ビット符号なし整数のオーバーフロー時の動作: 0から255までの範囲に収まるように，256で割った余りを計算結果とする (これはC言語規格の定義とも合致する)．
• 一般的には\(n\)ビット符号なし整数の場合， オーバーフローの結果は，\(0\)から\(2^n-1\)の範囲に収まるように， \(2^n\)で割った余りを計算結果とする．

キャリーとボロー

• キャリー (carry)は繰り上げ，ボロー(borrow)は繰り下げのこと

• 符号なし整数のオーバーフローはキャリーやボローの有無でチェックできる

• 例: 8ビット符号なし整数で255+1を計算すると，キャリーが発生する

  

• 例: 8ビット符号なし整数で0-1を計算すると，ボローが発生する

  

• x86-64では符号なし整数のオーバーフローは， キャリーフラグ(CF)で検出できる． キャリーやボローが発生するとキャリーフラグが立つから．

  • cf. x86-64では符号あり整数のオーバーフローは， オーバーフローフラグ(OF)で検出できる

符号あり整数，2の補数

符号あり整数のビット表現

• 非負(0か正数)の数は2進数の各桁をそのままビット表現， 負の数は2の補数 (two's complement)を使う

  • MSBは符号ビットになる．0なら非負，1なら負になる．
  • 2の補数以外にも負の数の表現方法はある． 2の補数を使う理由は，(1) 減算を加算処理で行えるから， (2) x86-64が2の補数を使っているからです．

• 例: 8ビットの符号あり整数の場合，

  • 前半の00000000〜01111111を0と正の数に， 後半の10000000〜11111111を負の数にする．
  • 例えば，126に対する(8ビットの場合の)2の補数は130(=256-126)なので， 130の2進表記 10000010 を -126 のビット表現とする．

一覧表

• 前半 (0と正の数)

• 後半 (負の数)

2の補数と1の補数

• 2の補数とは(キャリーを無視して)加算して全てのビットが0になる数です

  • 例: 8ビットの場合，126 (2進数で 01111110)の2の補数は10000010 (=130)です． 01111110+10000010=00000000になるからです(キャリーを無視すれば)． \(126+130=256=2^8\)

    

• 1の補数とは(キャリーを無視して)加算して全てのビットが1になる数です

  • 例: 8ビットの場合，126 (2進数で 01111110)の1の補数は 10000001 (=129)です． 01111110+10000001=11111111になるからです． \(126+129=255=2^8-1\)

    

• 2の補数の求め方: 各ビットを反転してから，LSBに1を加えれば良い

  

• 一般的に，\(n\)進数に対して，\(n\)の補数と，\((n-1)\)の補数が存在します

  • \(n\)の補数は「足すとちょうど桁が上がる数」です． 10進数で2桁の数を考える時，\(65\)に対する10の補数は\(35\)になります． 足すと\(100\)になるから．
  • \(n-1\)の補数は「足してもギリギリ桁が上がらない数」です． 10進数で2桁の数を考える時，\(65\)に対する9の補数は\(34\)になります． 足すと\(99\)になるから．

符号なし整数と符号あり整数の関係

• 8ビットの場合，符号なし整数の128〜255の範囲のビット表現を， 符号あり整数の-128〜-1の範囲にシフトしたことになる．

  

• シフトの幅がどれもちょうど256であることがポイント．

• 「130を足す」のと「126を引く」のは同じ

  • 8ビット整数の場合，256を足しても引いても値は変化しませんよね． キャリーやボローとしてはみ出るだけだからです．
  • 例えば，1 + 256 = 1 ですし，1 - 256 = 1 です． (数式ではこれを \(1 + 256 \equiv 1 \pmod {256}\) と書きます． 「256で割った余りで考えれば，同じ値である」という意味です． ここでは単に = を使います)．
  • ですので，4 - 126 = 4 + (-126) = 4 + 256 + (-126) = 4 + 130 となります．

• 時計で考えると分かりやすいかも．時計の上で，「7時間足す」のと「5時間引く」のは同じ．

  

扱える範囲

• 例: 8ビット符号あり整数が表現できる範囲は \(-128\)から\(127\)まで
  • \(128\)まででは無いのはプラス側にはゼロ (0)があるから
• 一般に\(n\)ビット符号なし整数の範囲は \(-2^n/2\)から\(2^n/2-1\)まで
  • \(n\)ビットの場合，\(2^n\)通りの数が扱える． 正と負で半分ずつ使ってる (\(2^n/2\))が， 正の方はゼロ (0)があるので \(-1\)となる．

最大値と最小値のビットパターン

• 見やすさのため8ビットごとにスペースを入れてます
• 最小値はMSBが1でそれ以外の全ビットが0，最大値はMSBが0でそれ以外の全ビットが1

x86-64は符号の有無を気にせず加算する→どちらの結果も正しい

• 2の補数の利点 = 足し算回路で引き算ができる

• 例: 31-126は，31と -126 のビット表現の加算で計算できる．

  • つまり 00011111 + 10000010 = 10100001 = -95
  • この結果が 31 + 130 = 10100001 = 161 の結果と，ビット表現が一致することに注意
  • これは当然で，8ビットの場合，31 + (-126) = 31 + 256 + (-126) = 31 + 130 だから
  

• 実際，x86-64は整数が符号ありか符号なしかを区別せずに加算している． 計算結果はどちらに対しても正しい．

  • プログラマ(あるいはコンパイラ)は符号ありか符号なしかを意識する必要がある． 符号あり・符号なしでビット表現が意味する値が変わるし (上の例では161か-95か)， オーバーフローの判定にキャリーフラグ(CF)とオーバーフローフラグ(OF)の どちらを使うべきかを判断する必要があるから．

符号あり整数のオーバーフロー

• 8ビット符号あり整数の64に64を足すと，オーバーフローして結果は-128になる (64 + 64 = 128 は８バイト符号あり整数が表現可能な-128〜127の範囲を超えている)．

  

• C言語の規格上，符号あり整数のオーバーフローは未定義動作(undefined behavior)． つまり，符号あり整数をオーバーフローさせてはいけない．

  • 未定義動作を含むプログラムに対して，コンパイラはどのように振る舞っても良い．
    • コンパイルエラーにしても良いし，実行するたびに異なる結果を出力するコードを出力しても良いし，それっぽい答え(ここではオーバーフローしたビット表現)を出力しても良い
  • ここでは-128の結果を得たが，C言語の規格上，他の結果がでる可能性がある

符号あり整数では，オーバーフローとキャリーの有無は関係ない

• 符号あり整数ではオーバーフローとキャリーの有無は関係ありません

  
  • 例: 8ビット符号あり整数で，64+64=128 は，表現可能な-128〜127を超えているのでオーバーフロー発生．しかしキャリーは0
  • 例: 8ビット符号あり整数で，(-1)+(-1)=-2は，表現可能な-128〜127の範囲内なので オーバーフローは発生していない．しかしキャリーは1

• このため，x86-64では符号あり整数のオーバーフローを(キャリーフラグ(CF)ではなく) オーバーフローフラグ(OF)で検出する

  • 一方，符号なし整数のオーバーフローは キャリーフラグ(CF)で検出する

• なお人間が判断する場合は以下で簡単に判定できる

  • 正と正の数同士(どちらもMSBは0)を足して，負になったら(MSBは1)オーバーフロー発生
  • 負と負の数同士(どちらもMSBは1)を足して，正になったら(MSBは0)オーバーフロー発生
  • 正と負の数同士の足し算では決してオーバーフローは発生しない

C言語で整数計算に注意が必要な場合

符号あり整数のオーバーフロー (未定義動作)

// overflow4.c
#include <stdio.h>
#include <stdint.h>
int main ()
{
    int32_t x1 = 10 * 10000 * 10000; // 10億
    int32_t x2 = 15 * 10000 * 10000; // 15億
    int32_t x3 = x1 + x2; // オーバーフロー
    printf ("%d\n", x3); // -1794967296
}

$ gcc -g overflow4.c
$ ./a.out
-1794967296

• 符号あり整数のオーバーフローはセキュリティ上の脆弱性になるため避けるべきです． -ftrapvオプションをつけると符号あり整数のオーバーフロー時に トラップが発生します． 試した所，シグナルSIGABRTが発生してプログラムは終了しました．

$ gcc -g -ftrapv overflow4.c
$ ./a.out
Aborted

絶対値を計算できない数がある

// overflow5.c
#include <stdio.h>
#include <stdint.h>
int main ()
{
    int8_t  x1 = -128;
    int16_t x2 = -32768;
    int32_t x3 = -2147483648;
    x1 = -x1;
    x2 = -x2;
    x3 = -x3;
    printf ("%d, %d, %d\n", x1, x2, x3);
}

$ gcc -g overflow5.c
$ ./a.out
-128, -32768, -2147483648

• 符号あり整数で表現可能な最小の数は絶対値を計算できません．
• 例えば8ビット符号あり整数-128の絶対値は計算できません． 絶対値の128が，表現可能な範囲-128〜127を超えてしまうからです．
• この場合もオーバーフローが起きているので未定義動作となります．

符号ありと符号なしを混ぜると直感に反する結果になる

// signed-unsigned.c
#include <stdio.h>
#include <stdint.h>
int main ()
{
    int32_t x1 = -1;
    uint32_t x2 = 0;
    printf ("%d\n", x1 < x2); // 0
}

$ gcc -g singed-unsigned.c
$ ./a.out
0

• これはオーバーフローではなくC言語の規格に関する話です．
• 上のsigned-unsigned.cを実行すると0が返りました． (-1 < 0は真なので1が返って欲しいのに)．
• これは違う型同士の演算ではC言語ではまず型を同じにするためです (通常の算術型変換といいます)． この場合は-1を符号なしに変換します． その結果，0xFFFFFFFFという大きな正の数になり， 0xFFFFFFFF < 0を比較して0が返るわけです．
• この問題があるため，C言語では符号ありと符号なしを混ぜて使うことを避けるべきです．
  • 通常は符号ありの整数を使う
  • ビット演算をしたい場合などに限定して符号なしの整数を使う (符号あり整数へのビット演算は(未定義動作ではないが) 処理系定義の動作を引き起こす場合があるため)．

機械語命令の符号化

覚える必要はありません

• 機械語命令の符号化方法はCPUごとに異なります
• x86-64の機械語命令の符号化方法はx86-64のマニュアル Intel 64 and IA-32 Architectures Software Developer Manualsに書いてありますし，アセンブラが自動変換してくれるので，私達は覚える必要は全くありません
• とはいえ，「機械語命令も2進数で符号化されている」ことを確認するために， 機械語命令の符号化をちょっとだけ見てみましょう

概要

• x86-64はCISC (complex instruction set computer)なので， 「1つの命令で複雑な処理をする」という設計哲学です． そのため命令は可変長(1バイト〜15バイト)で複雑です． 一方，RISC (reduced instruction set computer)では命令長は固定長で， 1命令が処理する内容は単純なことが多いです．

命令フォーマット

• 上図はx86-64の基本的な命令フォーマットです(この図と異なる例外的な命令もあります)．
• 命令プリフィクス (instruction prefix)には例えばLOCKプリフィクスがあります． LOCKプリフィクスはメモリアクセスをアトミックにする効果がありますが， LOCKプリフィクスをつけて良い命令は一部に限定されています． また，以下ではREXプリフィクスも登場します．
• ModR/MバイトとSIBバイトは， アドレッシングモード，レジスタやメモリオペランドを指定します．
• 変位(displacement)と即値(immediate)はどちらも定数です． pushq 4(%rsp)の4が変位，pushq $4の4が即値です．

処理方向ビット

• 2つのオペランドを持つ多くの命令で， 1バイトのオペコードの (LSBを0ビット目と数えて)1ビット目が処理方向ビット(operation direction bit)になります．
• 処理方向ビットが0の時，代入の方向はreg→r/mになります． 一方1の時，代入の方向はr/m→regになります．
• 例えば，上図で movq r64, r/m64のオペコードはREX.W 89， movq r/m64, r64のオペコードはREX.W 8Bです． 確かに，処理方向ビットがそれぞれ0と1になっています． (REX.Wは命令プリフィクスで，オペランドサイズを64ビットにします)．

REXプリフィクス

• REXプリフィクスはx86-64で追加された1バイト長の命令プリフィクスです．
• GNUアセンブラが自動挿入するので，アセンブリコードでプログラマが 明示的にREXプリフィクスを記述する必要は通常はありません．
• REX.Wはオペランドサイズを64ビットにします．
• REX.R，REX.X，REX.Bはレジスタを指定する際に使われます． これらの値が1の時，新しいレジスタ%r8〜%r15を指定したことになります．

ModR/MバイトとSIBバイト

• ModR/Mバイトは上図のように分割されてます．

• ModR/MのModフィールドの意味は上記のとおりです．

$ gcc -g movq-10.s
$ objdump -d ./a.out
0000000000001129 <main>:
  1129: 4c 89 c0             	mov %r8,%rax        # Mod=11，レジスタ
  112c: 4c 89 00             	mov %r8,(%rax)      # Mod=00, メモリ参照，変位無し
  112f: 4c 89 40 08          	mov %r8,0x8(%rax)   # Mod=01，メモリ参照，変位1バイト (0x08)
  1133: 4c 89 80 e8 03 00 00 	mov %r8,0x3e8(%rax) # Mod=10, メモリ参照，変位4バイト (0xE8, 0x03, 0x00, 0x00)

• ModR/MのRegフィールドはREX.Rの1ビットと合わせて，レジスタを指定します(以下の表参照)．

• オペランドが1つの時はRegフィールドはレジスタの指定ではなく， オペコードの一部として使われることがあります(なので図中でOpcodeと書いています)．

• ModR/MのR/MフィールドはREX.Bの1ビットと合わせて，レジスタやメモリ参照を指定します．
  • Mod=11の時はR/Mフィールドは下の表のレジスタを指定します．
  • Mod\(\neq\)11の時はR/Mフィールドは下の表のメモリ参照を指定します．
    • ただし，R/M=100の時はSIBバイトを使うことを意味します． また，R/M=101の時は%rip相対アドレッシングを使うことを意味します． R/M=101の時，(本来はMod=00は変位無しですが) Mod=00でもMod=10でも変位が4バイトになります．

• SIBの各フィールドは，Scale，Indexレジスタ, Baseレジスタを指定します． (例えば，メモリ参照 (%rax, %rbx, 2)で， %raxがBaseレジスタ，%rbxがIndexレジスタ，2がScaleです)．

$ gcc -g movq-11.s
$ objdump -d ./a.out
0000000000001129 <main>:
  1129: 4c 89 05 e8 03 00 00 	mov  %r8,0x3e8(%rip)
  1130: 4e 89 84 48 e8 03 00 	mov  %r8,0x3e8(%rax,%r9,2)
  1137: 00 

• mov %r8, 0x3e8(%rip)の機械語バイト列を見てみます

  • Mod=00で，メモリ参照，変位は4バイトを意味します(これはR/M=101の時の例外)．
  • REX.R=1とReg=000で，%r8レジスタを意味します．
  • R/M=101で，%rip相対アドレッシングを意味します．
  • 89はmovqのオペコードです． 処理方向ビットが0なのでRegをR/Mに代入を意味します．
  • 最後の4バイト (E8 03 00 00)は4バイトの変位です．

• movq %r8, 0x3e8(%rax,%r9,2)の機械語バイト列を見てみます

  • Mod=10で，メモリ参照，変位は4バイトを意味します．
  • REX.R=1とReg=000で，%r8レジスタを意味します．
  • R/M=100で，SIBバイトの使用を意味します．
  • Scale=01で，0x3e8(%rax,%r9,2)の2を意味します．
  • REX.B=0とBase=000で，Indexレジスタとして%raxを使用します．
  • REX.X=1とIndex=001で，Baseレジスタとして%r9を使用します．

• SIBバイトのBaseフィールドはREX.BとともにBaseレジスタを指定します． ただし，❶❷の部分が特別扱いです．

  • ❶❷の101かつMod=00の場合，(%rbp)というメモリアクセスではなく， 32ビットの変位のみでのメモリアクセスになります．
  • 例えば，movq %r8,0x1000の機械語バイト列は 4c 89 04 25 00 10 00 00になります． Mod=00, Base=101となっていますね．

• SIBバイトのIndexフィールドはREX.Xと合わせて，Indexレジスタを指定します．

  • ただし%rspは指定不可です

データの変換

ゼロ拡張

• ゼロ拡張 (zero extension)は上位ビットを0で埋めてビット列を大きくする変換．
• 符号なし整数をゼロ拡張すると，値は変化しない．
  • 例: 2バイトの符号なし整数65535をゼロ拡張で4バイトに変換しても，値は変化しない．

符号拡張

• 符号拡張 (sign extension)は
  • 上位ビットを元データのMSBで埋めてビット列を大きくする変換．
  • つまり，正の場合は0を，負の場合は1を上位ビットに埋める．
• 符号あり整数を符号拡張すると，値は変化しない．

• 符号あり整数をゼロ拡張すると，値が変化する．

movz␣␣，movs␣␣命令

• movz␣␣はゼロ拡張をしてデータをコピーする命令 (move with zero extension)
• movs␣␣は符号拡張をしてデータをコピーする命令 (move with sign extension)
• 通常，値を変化させたくないので，符号なし整数にはmovz␣␣を使い， 符号あり整数にはmovs␣␣命令を使う．

切り詰め (truncation)

• 切り詰め = 上位ビットを捨ててビット列を小さくする変換
• 符号あり整数を切り詰めると，正負が変わることがある

#include <stdio.h>
#include <stdint.h>
int main (void)
{
    int32_t i = 100000;
    int16_t s = i;
    printf ("%d\n", s);
}

$ gcc -g trunc.c
$ ./a.out
-31072

• 4バイトから2バイトへ切り詰めは， 例えば，%eaxに値を入れて，%axで値を取り出せば可能．

# asm/trunc2.s
    .text
    .globl main
    .type main, @function
main:
    movl $100000, %eax
    movw %ax, %bx
    ret
    .size main, .-main

$ gcc -g trunc2.s
$ gdb ./a.out -x trunc2.txt
Breakpoint 1 at 0x1131: file trunc2.s, line 8.
Breakpoint 1, main () at trunc2.s:8
8	    ret
$1 = -31072
# -31072 が出力されれば成功

メモリレイアウト

多バイト長データはメモリの連続領域に格納

• 通常，メモリはバイトアドレッシングです． つまり，1つの番地ごとに1バイトの情報を格納できます．
• 多バイト長データ(2バイト以上のデータ)をメモリに格納する時は， メモリの連続領域を使ってデータを格納します．
  • 上図では4バイトのデータ 0x11223344をメモリの1000〜1003番地を使って格納していることを示しています．
  • このデータを読み書きする場合は，先頭番地の1000番地を使います．

バイトオーダとエンディアン

• 多バイト長のデータをメモリに格納するには1バイトごとに分割して格納します． 多バイト長のデータをバイト単位で格納する順序をバイトオーダ(byte order)といいます．

• 多バイト長データで最下位のバイトをLeast Significant Byte (LSB)， 最上位のバイトをMost Significant Byte (MSB)と呼びます．

  • 例えば，0x11223344という4バイトのデータのLSBは0x44，MSBは0x11です．

• 多バイト長データをメモリに格納する時，

  • LSBから先にメモリに格納する方法を
    リトルエンディアン
    (little endian)
  • MSBから先にメモリに格納する方法をビッグエンディアン (big endian) と呼びます．

アラインメントとパディング

アラインメント

• アラインメント (境界調整，alignment)とは， 特定のアドレス(例: 16の倍数のアドレス)にデータを格納することです
  • 16の倍数のアドレスに格納することを， 16バイト境界 (16-byte boundary)に格納する，という言い方もします．
• ABIはアラインメントを守ることを プログラムに要求します．このお約束をアラインメント制約といいます． 上の表は System V ABI (AMD64) が定めるアラインメント制約です．
  • スタックフレームの16バイト境界への制約は call命令実行時に%rspの値が16の倍数であることを要求しています．

アラインメント制約に違反すると最悪，クラッシュする

• アラインメント制約に違反すると，実行速度が遅くなったり， Segmentation faultなどの実行時エラーが生じます(例: AVX命令のmovdqa)． このため，コンパイラはアラインメント制約を満たすコードを出力します． 人手でアセンブリコードを書く場合は， プログラマがアラインメント制約を守るよう注意する必要があります．

アラインメント調整 (.align)とパディング

• アラインメント制約はアセンブラ命令.alignを使って満たせます (他にも .skip, .space, .zeroなどのアセンブラ命令でも可能です)．

  char x1 = 10;
  int  x2 = 20;
  

      .globl  x1
      .data
      .type   x1, @object
      .size   x1, 1
  x1:
      .byte   10
      .globl  x2
    ❶.align 4
      .type   x2, @object
      .size   x2, 4
  x2:
      .long   20
  

  
  • 例えば，上のchar型のx1とint型のx2というグローバル変数の宣言があった場合，コンパイラは上のようなアセンブリコードを出力します．
  • 仮にx1を1000番地に配置したとすると，そのまま次の領域にx2を配置すると x2は1001番地に配置することになります． 1001番地は4バイト境界(4の倍数のアドレス) ではないのでアラインメント制約違反になってしまいます．
  • これを避けるため❶.align 4というアセンブラ命令を使用します． .align 4は「次に出力するアドレスを4の倍数になるよう(最小限増やして)調整しろ」という意味です．その結果，x2のアドレスは1004番地になります．
  • なお未使用の1001〜1003番地のメモリ領域のことをパディング(詰め物，padding)といいます．

構造体のパディング

// asm/struct3.c
struct foo {
    char x1;
    int x2;
};
struct foo f = {10, 20};

    .globl  f
    .data
    .align 8            # 構造体全体を8バイト境界に配置
    .type   f, @object
    .size   f, 8
f:
    .byte   10          # f.x1
    .zero   3           # 3バイトのゼロを出力(3バイトのパディング)
    .long   20          # f.x2

• アラインメント制約のために，構造体の中にもパディングが生じます
• 上の例ではchar型のx1とint型のx2の間に3バイトのパディングができています
• 構造体の先頭にパディングが入ることはありません． 一方，構造体の末尾にパディングが入ることはあります(次の節で説明)

配列のためのパディング

• (構造体にはパディングが生じますが)配列にはパディングは入りません． 配列のすべての要素は常にぴったりくっついて， メモリ上で連続したアドレスに格納されます． 例えば，int a1 [3]; のメモリレイアウトは以下の図になります． (配列の各要素(ここではint)もアラインメント制約を満たしています (ここではアドレスが4の倍数になっています))

  

• これは2次元配列になっても同じです． 例えば，int a2 [2][3];のメモリレイアウトは(C言語では)以下の図になります．

  

• 「じゃあ，サイズが5バイトの構造体を作って，その構造体の配列を定義したら， その配列の要素はアラインメント制約を満たせないのでは?」

  答えは「はい，満たせなくなります．ですので，(構造体中にint型など アラインメント制約を持つメンバーがある場合は)サイズが5バイトの構造体は作れません」「その場合は構造体のお尻にパディングが入ります」． (なお構造体のメンバーがcharやchar[]など，どの場所にも置けるデータのみの 場合は5バイトの構造体を作れます)．

// asm/struct4.c
#include <stdio.h>
struct foo2 {
    int x2;
    char x1;
};
struct foo2 f = {10, 20};
int main ()
{
    printf ("%ld\n", sizeof (struct foo2));
}

    .globl  f
    .data
    .align 8
    .type   f, @object
    .size   f, 8  # 構造体全体のサイズは8バイト
f:
    .long   10
    .byte   20
    .zero   3     # 構造体のお尻に3バイトのパディングが入っている

実際にやってみると，構造体のお尻に3バイトのパディングが入りました．