NJUPT-CSAPP/复习资料/A.tex

\documentclass[UTF8,punct=kaiming]{ctexart}
\usepackage{amsmath}
\usepackage[a4paper,left=2cm,right=2cm,top=2.5cm,bottom=2.5cm]{geometry}
\usepackage{multicol}
\usepackage{makecell}
\usepackage{fancyhdr}
\usepackage{hyperref}
\usepackage[type={CC},modifier={by-sa},version={4.0},lang={chinese-utf8}]{doclicense}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage[many]{tcolorbox}
\usepackage{multirow}
\usepackage{listings}
\input{insbox}

\setlength{\parindent}{0pt}

\hypersetup{hidelinks,
	colorlinks=false,
	allcolors=black,
	pdfstartview=Fit,
	breaklinks=true}

\pagestyle{fancy}
\fancypagestyle{myfancypagestyle}{
    \fancyhf{}
    \fancyhead[L]{计算机系统基础\uppercase\expandafter{\romannumeral1\relax} 考试用资料}
    \fancyhead[R]{Made with $\heartsuit$ by \href{https://kagurach.uk/}{kagura} and \href{https://nkid00.name/}{nkid00} \& licensed under \doclicenseNameRef}
    \fancyfoot[C]{\thepage}
    \renewcommand{\headrulewidth}{0.4pt}
    \renewcommand{\footrulewidth}{0pt}
}
\pagestyle{myfancypagestyle}

\tcbuselibrary{listings}
\tcbset{colback=white,boxrule=0.3mm,enhanced,size=small}

\lstset{basicstyle=\ttfamily,columns=fullflexible}

\setlength{\columnsep}{1cm}
\setlength{\columnseprule}{0.4pt}

\begin{document}

\section{数据表示与存储} 
\subsection{数据的类型及大小}
\begin{table}[h]
    \begin{tabular}{|c|c|c|c|c|}
    \hline
    类型    & 字节数 & 最小值 & 最大值(signed) & 最大值(unsigned) \\ \hline
    \texttt{char}   & 1   & \(-128\)  & \(127\)  & \(255\)\\ \hline
    \texttt{short}  & 2   & \(-32768\) & \(32767\) & \(65535\)\\ \hline
    \texttt{int}    & 4   & \(-2147483648\) & \(2147483647\) & \(4294967295\) \\ \hline
    \texttt{long}   & \multirow{2}{*}{8}   & \multirow{2}{*}{\(-9223372036854775808\)} & \multirow{2}{*}{\(9223372036854775807\)} & \multirow{2}{*}{\(18446744073709551615\)} \\
    \cline{1-1} \texttt{void*}  & & & & \\ \hline
    \texttt{float}  & 4   & $1.17549\times10^{-38}$  & $3.40282\times10^{38}$ & --- \\ \hline
    \texttt{double} & 8   & $2.22507\times10^{-308}$ & $1.79769\times10^{308}$ & ---\\ \hline
    \end{tabular}
\end{table}

\subsection{计算值域}
T: 用 $n$ 位表示数字
\begin{align*}
\text{(signed) T}  \quad  & \text{可表示} \quad -2^{n-1} \sim ~ 2^{n-1}-1 \\
\text{(unsigned) T} \quad & \text{可表示} \quad 0 \sim 2^{n}-1
\end{align*}

\subsection{补码}

\begin{multicols}{2}
    \qquad 对应正数补码的“各位取反、末位加1” 
    \begin{align*}
        +23 & = \texttt{00010111} \\
        \text{按位取反} & = \texttt{11101000} \\
        & + \hspace{0.3em}\phantom{0000000}\texttt{1} \\
        -23_{\text{补码}} & = \texttt{11101001} 
    \end{align*}

    \columnbreak

    \qquad 模($2^n$)减去该负数的绝对值
    \begin{align*}
        & \texttt{100000000} \\
        - \hspace{0.5em} & \phantom{\texttt{0}}\texttt{00010111} \\[-1em]
        & \hspace{-1em}\rule{2.5cm}{0.02em} \\[-0.5em]
        & \phantom{\texttt{0}}\texttt{11101001}
    \end{align*}
    
\end{multicols}

\subsection{GDB查看数据}

\texttt{>(gdb) x/4xb} \\[1em]
\begin{minipage}{12cm}
\begin{multicols}{2}
    \texttt{b} - byte (8-bit value) \\
    \texttt{h} - halfword (16-bit value) \\
    \texttt{w} - word (32-bit value) \\
    \texttt{g} - giant word (64-bit value) \\
    \texttt{o} - octal \\
    \texttt{x} - hexadecimal \\
    \texttt{d} - decimal \\
    \texttt{u} - unsigned decimal \\
    \texttt{t} - binary \\
    \texttt{f} - floating point \\
    \texttt{a} - address \\
    \texttt{c} - char \\
    \texttt{s} - string \\
    \texttt{i} - instruction 
\end{multicols}
\end{minipage}

\newpage

\subsection{浮点数}

\vspace{-1cm}

\InsertBoxR{0}{\tcbox[blank]{\begin{tabular}{|c|c|c|c|c|}
\hline 二进制位数 & s 符号位 & exp 指数 & frac 尾数 & 总计 \\
\hline \texttt{float} & 1 & 8 & 23 & 32 \\
\hline \texttt{double} & 1 & 11 & 52 & 64 \\
\hline
\end{tabular}}}

\vspace{1cm}

浮点数表示为 $(-1)^s \cdot M \cdot 2^E$

\InsertBoxR{0}{\tcboxmath{\begin{matrix}
    & \text{偏置值 Bias} & E\ \text{的范围} \\
    \texttt{float} & 127 & \left[-126, 127\right]\\
    \texttt{double} & 1023 & \left[-1022, 1023\right]\\
\end{matrix}}\hspace{1.5cm}}

\vspace{-1em}

\subsubsection{规格化数 $ \text{exp} \ne 0$ 且 $\text{exp} \ne 11 \dots 1$}

$\text{偏置值 Bias} = 2^{k-1}-1$ , \(k\) 为 exp 的二进制位数

$\text{exp} \ = \ E \ + \text{Bias} \quad E \in \left[1 - \text{Bias}, \text{Bias}\right]$


\begin{multicols}{2}
    例1:十进制整数$\rightarrow$二进制浮点数
    \begin{align*}
        \text{float} \ F   &= 15213.0 \\
        \text{化为二进制数:} \\
        15213_{10}  &= 11101101101101_{2} \\
                    &= 1.1101101101101_{2} \ \times  \ 2^{13} \\
        \text{计算 frac:} \\
                M   &= 1.\underbar{1101101101101}_{2} \\
                \text{frac} &= \underbar{1101101101101}0000000000_{2}\\
        \text{计算 exp:} \\
                E   &= 13 \qquad \text{来自化为二进制时的指数}  \\
                \text{Bias} &= 127 \\
                \text{exp} &= 140 = 10001100_{2}
    \end{align*}
结果：\\
\(\begin{matrix}
    0 & 10001100 & 11011011011010000000000 \\
    \text{s} & \text{exp} & \text{frac}
\end{matrix}\)

\columnbreak
    例2: 二进制浮点数$\rightarrow$十进制数
    
    无符号数，4位阶码(Bias\(=7\))，3个小数位 \\

    \quad \(\begin{matrix}
        1001 & 111 \\
        \text{exp} & \text{frac}
    \end{matrix}\) \\[0.5em]

    \(\begin{aligned}
        \text{计算} \space E &= \text{exp} - \text{Bias} & \\
          &= 1001_2 - 7_{10} \\
          &= 2_{10}
    \end{aligned}\) \\[0.5em]

    计算 \(M = 1.\underbar{frac} = 1.\underbar{111}\) \\[0.5em]

    化为十进制:

    \(\begin{aligned}
        1.111 \times 2^2 & = 111.1_2 \quad \text{小数点右移2位} \\
        & = \frac{15}{2}  = 7.5
    \end{aligned}\)
\end{multicols}

\InsertBoxR{0}{\tcboxmath{\begin{matrix}
    \text{非规格化数} \  E = 1 - \text{Bias} \\
    \begin{matrix}
        \texttt{float} & -126 \\
        \texttt{double} & -1022 \\
    \end{matrix}
\end{matrix}}
\hspace{2cm}}
\vspace{-5mm}

\vspace{-0.3em}

\subsubsection{非规格化数 $\text{exp} = 0$}

frac \(= 00\dots0\) 表示 0

frac \(\ne 00\dots0\) 表示接近 0 的小数 $(-1)^s \cdot M \cdot 2^{E}$

\vspace{-0.3em}

\subsubsection{特殊值 $\text{exp} = 11 \dots 1$}

\begin{multicols}{2}

frac \(= 00\dots0\) 表示 \(\infty\)

frac \(\ne 00\dots0\) 表示 NaN

\columnbreak

\(1.0 / 0.0 = −1.0 / −0.0 = + \infty\)

\(1.0 / −0.0 = - \infty\)
 
\(\sqrt{–1.0} = \infty - \infty = \infty \times 0 = \text{NaN}\)

\end{multicols}

\subsubsection{舍入(到偶数)}

\begin{table}[h]
\begin{tabular}{|ccc|}
\hline
末两位 & 动作  & 例子（保留一位小数） \\ \hline
01    & 舍   &  $11.0\underbar{01}_2 \to 11.0_2$ \\ \hline
11    & 入   &  $10.0\underbar{11}_2 \to 10.1_2$ \\ \hline
10    & \makecell[c]{强迫结果为偶数(末尾为0)\\010舍 , 110入} &\makecell[c]{$10.0\underbar{10}_2 \to 10.0_2$ \\ $10.1\underbar{10}_2 \to 11.0_2$}   \\ \hline
\end{tabular}
\end{table}

\pagebreak

\InsertBoxR{0}{\tcboxmath{\begin{matrix}
    \text{寻址模式} & \text{p. 121} \\
    \text{栈帧结构} & \text{p. 164} \\
    \text{gdb 操作} & \text{p. 194} \\
\end{matrix}}\hspace{2cm}}

\vspace{-1.5em}

\section{程序的机器级表示}

\subsection{计算数组元素的地址}

\begin{multicols}{2}
计算 \texttt{T* D[R][C]} 元素 \texttt{D[i][j]}的地址： \\
\(\texttt{\&D[i][j]} = \texttt{\&D[0][0]} + \texttt{sizeof(T)} \times \left(C \cdot i + j\right)\) \\
假设 \texttt{sizeof(T) = k}, 将 \texttt{D[i][j]} 复制到 \%eax 中 \\
\texttt{asm: D in \%rdi , i in \%rsi , j in \%rdx }

\columnbreak
\texttt{1 \ leaq (\%rsi,\%rsi,\$C-1), \%rax       \\
2 \ leaq (\%rdi,\%rax,\$k), \%rax  \\
3 \ movl (\%rax,\%rdx,\$k), \%rax  \\
}
结果为 \texttt{D + k $\cdot$ C $\cdot$ i + k $\cdot$ j} \\
即 \texttt{D + sizeof(T) $\times$ (C $\cdot$ i + j)}
\end{multicols}

\vspace{-2.5em}

\section{链接}
\vspace{-1.5em}
\subsection{符号表 (.symtab)}
\vspace{-1em}

\begin{table}[h]
    \begin{tabular}{l|c|c|c|l}
    \hline
    C语言表示 & 类型 & 符号强度 & 节 & 说明\\ \hline
    \texttt{void swap();} & 全局 & 强 & \texttt{.text} & 非静态函数 \\ \hline
    \texttt{int *bufp0 = \&buf[0]} & 全局 & 强 & \texttt{.data} & 初始化为其他值的全局变量\\ \hline
    \texttt{int a = 0;} & 全局 & 强 & \texttt{.bss} & 初始化为 0 的全局变量 \\ \hline
    \texttt{int *bufp1;} & 全局 & 弱 & \texttt{COMMON} & 未初始化的全局变量 \\ \hline
    \texttt{extern int buf[];}  & 外部 & --- & \texttt{UNDEF} & \makecell[l]{
        未解析的引用符号 \\
        位于实际定义所在位置
    } \\ \hline
    \begin{lstlisting}[language=C,gobble=8]
        void p() {
          static int i = 1; }
    \end{lstlisting}
    & 局部 & --- & \texttt{.data} & 初始化为其他值的静态局部变量 \\ \hline
    \begin{lstlisting}[language=C,gobble=8]
        void p() { static int i;
          static int j = 0; }
    \end{lstlisting}
    & 局部 & --- & \texttt{.bss} & \makecell[l]{未初始化的静态局部变量 \\ 初始化为 0 的静态局部变量} \\ \hline
    \begin{lstlisting}[language=C,gobble=8]
        static void q() {
          int j = 2; }
    \end{lstlisting}
    & --- & --- & --- & \makecell[l]{链接不涉及静态函数\\链接不涉及非静态局部变量} \\ \hline
    \end{tabular}
\end{table}

\vspace{-2em}
\subsection{链接顺序}
\vspace{-0.5em}

\texttt{\$ gcc -static -o prog2c main2.o ./libvector.a} \\
E 将被合并以组成可执行文件的所有目标文件集合\\
U 当前所有未解析的引用符号的集合\\
D 当前所有定义符号的集合\\
开始 E、U、D为空，首先扫描 \texttt{main2.o}，将其加入 E，将未找到的符号加入 U, 定义的符号加入 D。 \\
再扫描 \texttt{./libvector.a}，将匹配到的 U 中的符号转移到 D 并加入到 E， 同时将未找到的符号加入 U。 \\
最后搜索标准库 \texttt{libc.a}，处理完\texttt{libc.a}时，U一定是空的，D中符号唯一，否则错误。

\vspace{-1em}
\subsection{重定位}
\vspace{-0.5em}

\begin{itemize}
    \item 重定位 PC 相对引用(\texttt{R\_X86\_64\_PC32}): \\
    重定位值 \( =\texttt{ADDR(r.symbol)} - \underbrace{\left(\texttt{ADDR(.text)} + \texttt{r.offset}\right)}_{\text{重定位值的地址}} + \texttt{r.addend}\)

    在asm中表示为 \texttt{4004de: e8 \underbar{05 00 00 00} \quad callq 4004e8 <sum>}

    \item 重定位绝对引用(\texttt{R\_X86\_64\_32}): \\
    重定位值 = \(\texttt{ADDR(r.symbol)} + \texttt{r.addend}\) \\
    在asm中直接以其绝对地址表示\texttt{4004d9: bf \underbar{18 10 60 00} \quad mov \$0x601018 \%edi}

\end{itemize}


\newpage

\end{document}