1.c++数据结构的底层表述形式
1.内存中数据采用16禁制表示. 一字节=2个十六进制 , 一个16进制 = 4个二进制 二进制 = 一位 (so, 一个字节 = 8 bit) 2.无符号整数
以 unsigned int为例 , 32位系统中 占 4字节 = 8个十六进制 = 32 bit | 取值范围0x00000000 ~ 0xFFFFFFFF
2.1 有符号整数
最高位是----符号位, 为0表示正数,1表示负数, 负数在内存中以补码表示.需要转换成真值才能看到
补码的规则: 正数的补码于原码相同, 负数补码逐位取反,加1,符号位不变
2.2 浮点类型
划分为 定点实数存储方式 和 浮点实数存储方式 .
定点存储: 就是约定整数位和小数位的长度,比如用4字节存储实数, 可以约定 2个高字节防整数部分,2个低字节防小数部分
(优点:高效,缺点存储不灵活, 比如 65555.5 整数部分超过2字节)
浮点存储: 用一部分二进制位存放小数点的位置信息,称之为"指数域",其他数据位用于存储没有小数点时的数据和符号,称为"数据域",或"符号域"
(优点与上相反,由于Inter推出了浮点协处理器,于是效率提升了,普及开来称为现在通用方式,但是在条件恶劣的嵌入式开发任可看到)
值得注意: C++中 浮点数强制转换为整数,不会四舍五入,直接丢弃小数部分
浮点数的操作不会用到通用寄存器,而是用浮点协处理器
2.2.1 浮点数的编码方式
float 和 double 2种类型转换原理相同,但是编码方式有区别,
1. float 类型 IEEE 编码
占用4字节(32位) .最高位符号位,剩余31位中从右往左取8位用于表示指数,其余表示尾数
由 一位 符号位 + 8位 指数位 ,不足8位高位补零 + 尾数位 等于 小数前的二进制 + 小数后的二进制 然后去掉 高位的1 , 不足8位低位补零
2.3 字符串
ASCII 编码 占一字节 ,由 0 ~ 255 之间数字组成. char 定义
Unicode 占2字节 , 0 ~ 65535 wchar_t 定义
对于汉字,他们编码不同, ASCII 使用 GB2312-80 又名 汉字国标码, 保存了6763常用汉字,用2个字节表示一个汉字
Unicode 使用 UCS-2 编码, 最多存储65536字符,为了把所有汉字,火星文,等容纳进来, 用2个Unicode编码表示一个函数,称为UCS-4
0x4E00 到 0x9520 为汉字编码区,在UCS-2中, 烫 子编码为 0x70EB
2.表达式求值过程
4. 算术运算工作形式
ADD 加法运算 SUB 减法运算umul 有符号乘法 MUL 无符号乘法他们在汇编中,都先将内存地址中的数据给与通用寄存器,然后寄存器进行算术运算后在将结果返回内存地址编译器会优化算术操作,普遍有两种方式:常量传播 : 将编译期间可计算出结果的变量转换成常量常量折叠 : 表达式中多个常量进行运算时,编译器在编译期间计算出结果.乘法和除法运算将花费大量CPU周期,编译器会尽所能的将乘法和除法转换成加法Debug版和Release版,一个注重调试,一个注重运行速度,所有汇编代码有所不同4.1.2 算术结果溢出
数据经过算术运算后,超出占用位空间,则会数据溢出,溢出数据将被丢弃, 如果原数据为负数,溢出后 最高位符号位进位,此时,负数变成正数
而无符号位溢出后会从最大数变成最小数
4.1.3 自增自减
实际上 在一条代码中 a = b + (c++); 会分成2条汇编指令顺序执行,
如果c++ 就先执行 a = b+c , 然后执行 c +1 , 反之亦然
4.2 关系运算和逻辑运算
逻辑运算分 : 或运算 || , 于运算 && 和非运算 ! .
相对汇编指令如下:
条件跳转指令集 指令助记符 检查标记位 说明 JZ ZF == 1 等于0则跳转 JE ZF == 1 相等则跳转 JNZ ZF == 0 不等于0则跳转 JNE ZF == 0 不相等则跳转 JS SF == 1 符号为负则跳转 JNS SF == 0 符号为正则跳转 JP/JPE PF == 1 '1' 的个数为偶数则跳转 JNP/JPO PF == 0 '1' 的个数为奇数则跳转 JO OF == 1 溢出则跳转 JNO OF == 0 无溢出则跳转 JC CF == 1 进位则跳转 JB CF == 1 小于则跳转 JNAE CF == 1 不大于等于则跳转 JNC CF == 0 无进位则跳转 JNB CF == 0 不小于则跳转 JAE CF == 0 大于则跳转 JBE CF/ZF ==1 小于等于则跳转 JNA CF/ZF ==1 不大于则跳转 JNBE CF/ZF ==0 不小于等于则跳转 JA CF/ZF ==0 大于则跳转 JL SF != OF 小于则跳转 JNGE SF !== OF 不大于等于则跳转 JGE SF == OF 不小于则跳转 JLE ZF != OF 或ZF ==1 小于等于则跳转 JNG ZF != OF 或ZF ==1 不大于则跳转 JNLE SF == OF 或ZF ==0 不小于等于则跳转 JG SF == OF 或ZF ==0 大于则跳转
通常情况下这些跳转指令都与 CMP 和 TEST匹配出现
4.2.3 条件表达式
也称三目运算,根据表达式1得到的结果进行选择,如果真值,则选择执行表达式2,否则执行表达式3
表达式1 ? 表达式2 : 表达式3
4.3 位运算
二进制数据的运算称为位运算,位运算操作符有:
<< 左移运算,最高位左移到CF中,最低位补零
>> 右移运算,最高位不变,最低位右移到CF中
| 位或运算,在两个数的相同位上,只要有一个为1,则结果为1
& 位与运算,两个数相同的位上,同时为1时,结果才为1
^ 异或运算,两个相同位上,2个值同时为0,不同时为1
~ 取反运算,将操作数每一位上的1变0, 0变1
对应汇编指令
左移 SHL , 右移 SAR , 位或 OR , 位与 AND , 异或 XOR 取反 NOT
对于左移运算而言,无符号数和有符号数 的位移操作都一样, 但是右移则有变化,有符号数 对应指令为sar,可以保留符号位, 无符号位不需要符号位
所以直接使用 shr 将高位补零
4.4 编译器优化技巧
代码优化有3个目的 : #执行速度优化 #内存存储空间优化 #磁盘存储空间优化 #编译时间优化
编译器在工作过程中分为: 预处理>此法分析>语法分许>语义分析>中间代码生成>目标代码生成
一般在中间嗲吗生成和目标代码生成2个阶段优化,有几种方案.
#常量折叠
例: x = 1+2 ; 其结果可预测,必然是3,没必要生成加法指令, 直接 x =3;
#减少变量
例 x = j*2; y = j*2; if x> y ; 以后没有再也不引用x,y ,这时对x,y的比较等价于 i,j的比较,可直接生成if I>j
#公共表达式
例: x =i*2; y = i*2; ,可归并位 x = i*2 ; y = x;
#复写传播
例: x = a; ....; y = x +c; 如省略号表示的代码中没有修改x,则可直接用a代替x
#减支优化
将永远不可能被执行的代码内容去掉不编译
#强度削弱
用加法或者位移代替乘法,用乘法或者位移代替除法
#数学变化
例: x = a+0; x = a-0; x = a* 1; x = a/ 1; 这些都是代数恒等式,不会长生运算指令,直接x =a 即可
例; 想= a*y + b*y ; 等价 x = (a+b) * y;
#代码外提
这类优化一般存在于循环中,
while(x > y/2) {....}; 循环体内如没修改y 值,可做如下优化
t = y/2;
while(x>t)...
以上优化是中间代码阶段优化方案.一下生成目标代码,也就是二进制嗲吗是和设备有关的,这里基于32位 Pentium 微处理器的优化
4.4.1 流水线优化规则
1.指令的工作流程
1) 取指令 ~ CPU从高速缓存或内存取机器码
2)指令译码 ~分析指令的长度,功能和寻找方式
3)按寻址方式确定操作数 ,~操作数可以使寄存器,内存单元,或者立即数,如果操作数是内存单元,则要计算出有效地址
4)取操作数 ~按操作数存放的位置获得数值,并存放入零时寄存器
5)执行指令 ~由控制单元 CU 或者计算单元 ALU 执行指令规则的操作
6)存放计算结果
注: 1) 2) 5) 是必要步骤
2.流水线
由于每条指令的工作流程都是 取指令 ,译码,执行,会写等步骤构成,所以处理器厂商设计了多刘淑娴结构,也就是说 A流水线在处理过程中,B流水线可以提前对吓一跳指令做处理
Inter 采用长流水线设计,把每条指令划分很多阶段,使每个步骤工作内容很简单,从而容易设计电路,加快主频,缺点是如果执行一个跳转指令
他预先处理吓一跳指令,分析第一条指令完毕后才发现时跳转,于是要回滚操作,进行流水线冲洗.
AMD的设计理念是多流水线设计,每条指令工作阶段烧,但是流水线数量多,并行程序更高.缺点是同样的指令,由于划分工作跌段烧,每个阶段做的事情多,电路设计复杂,主频受到限制,处理器对流水线管理的成本也增大
5. 流程控制语句的识别
5.1 if 语句
if 语句的功能是先对运算条件进行比较,然后根据比较结果选择对应语句块来执行. if 语句只能判断 真 或 假 值
值得注意的是, 如果代码中 if( a== 0 ) ; 则汇编代码会使用 JNE 不等于则跳转,于代码刚好相反, if( a>0 ) , 反汇编代码回事 小于等于0
如果 if( a > 2) 对应汇编代码则回事 小于等于则跳转!!!! 一定要注意
C语言是根据代码行的位置来决定编译后的二进制代码地址的高低,低行数对应低地址,高行数对应高地址,所以有时候会使用标号相减得到代码段的长度
总结:
由此得出 if 语句的转换规则, 在转换成汇编代码后,由于 if 比较结果为假时,需要跳过if语句块内的代码,因此使用了相反的跳转指令
;先执行各类影响标志位的指令
;气候是各种条件跳转指令
jxx xxxx
5.4 switch 的真相
switch在分支语句较大于等于4,并且2个case值之间的差值小于等于6,就会制作一份case地址数组,称为case地址表,这个数组保存了每个case语句块的首地址,并且数组下表是0. , 这种方法称为线性组合优化
当2个case值之间间隔较大时,就可使用索引表的方式来优化,他有2张表,一章保存case语句块地址,一章case语句块索引
索引的大小等于 最大case值和最小case值得差,当差大于255时,这种优化方案也浪费空间,可通过树方式优化,
判定树优化: 将每个case值作为一个节点,从这些节点中找中间值作为根节点,以此形成二叉平衡树,以每个节点为判定值,大于和小于关系分别对应左子树和右子树,(这个所谓的中间值并不是所有case值得和除以2,而是最小case和最大case的中间)
5.7 do / while / for 的识别
1) do 先执行循环语句块,在比较,最后向上跳转
2) while 语句跟if差不多, 但是他会在最后加上向上跳转
5.8 编译器对循环结构的优化
do循环执行效率最高,while其次,为了提升while效率,可以转换成高效的do循环结构,,用If单分支结构在do循环结构语句外,由if判断是否执行循环体
for循环也能用此方法优化成do的方式
6. 函数的工作原理
6.1 栈帧的形成和关闭
栈帧的介绍:
栈在内存中是一块特殊的存储空间,它的存储原理是"先进后出",既先被存储的数据最后释放.汇编过程通常使用 PUSH 和 POP 指令对
栈空间执行数据压入和数据弹出操作
通过esp于ebp这2个栈指针寄存器来保存当前栈的其实地址与结束地址,有称为栈顶于栈底. 在栈结构中,每4个字节的栈空间保存一个数据
这样的数据被称为 栈帧.
栈帧的形成:
当栈顶指针 esp 小于 栈底 指针 ebp 时, 就形成了栈帧. 栈帧中可以寻址的数据有局部变量,函数返回地址,函数参数等
清楚栈空间,关闭栈帧,这一过程称为栈平衡,如果某一函数在开辟了新的栈空间后没有进行恢复,或者多度恢复,将会照成栈空间
的上溢或者下溢.
在进入某个函数前,一般会预先保存栈底指针 ebp 以便退出函数时 还原以前的栈底.
在退出函数时,会将栈底指针ebp与栈顶指针esp进行对比,检测当前栈帧是否正确关闭.如果不平衡,则调用 _chkesp函数
一下是一个最小c程序来说明
源码:
int main() { return 0; }
对应汇编代码
push ebp ; 进入函数后的第一件事情,保存栈底指针 ebp
mov ebp,esp; 调整当前栈底指针位置到栈顶
sub esp,40h; 抬高栈顶esp,此时开辟栈空间 0x40 ,作为局部变量的存储空间
push ebx; 保存寄存器ebx
push esi; 保存寄存器esi
push edi; 保存寄存器edi
lea edi , [ebp-40h] ; 取出次函数可用的栈空间首地址
mov ecx,10h; 设置ecx为 0x10
mov eax,0cccccccch ; 将局部变量初始化为0cccccccch
;根据ecx的值,将eax 中的内容,以4字节单位写到edi指向的内存中
rep stos dword prt [edi];
//..........下面是函数退出代码
xor eax,eax; 将eax清零
pop edi; ; 还原寄存器edi
pop esi; 还原寄存器esi
pop ebx; 还原寄存器ebx
add esp,40h 降低栈顶esp,此时局部变量空间被释放
cmp ebp,esp; 检测栈平衡,如果不等于则不平衡
call _chkesp(00401050); 进入栈平衡错误检测函数
mov esp,ebp; 还原esp
pop ebp
ret
6.2 调用方式的考察
汇编过程中通常使用 ret XXXX 来平衡栈空间,昂函数参数不定的时候,函数自身无法平衡所使用的栈空间大小,因此有了函数调用约定
VC++ 环境下有3种:
_cdecl ; c\c++默认调用方式,调用方平衡栈,不定参数的函数可以使用
_stdcall ; 被调用方平衡栈,不定参数的函数无法使用
_fastcall ; 寄存器方式传参,被调方平衡栈,不定参数的函数无法使用
使用方法在函数的返回值类型与函数名之间加上即可
_stdcall 方式调用函数的汇编代码
push 5 ; 传入参数,使用PUSH 指令 esp -4
call @ILT+10(一个函数地址) ; 没有 esp操作指令
_cdecl 方式调用
push 5;
call @ILT+10(一个函数地址) ;
add esp,4 ; esp +=4 ,平衡栈
除了这2种分别以外,很有可能其他汇编指令简介的对esp做加法,如 pop ecx 这样也能达到栈平衡,还需要结合函数执行中使用的栈空间
于函数结束时的栈平衡树进行对比,判断参数平衡
最后一种方式 _fastcall 效率最高, 唯独他可以利用寄存器传递参数,但是寄存器数目很少,而参数相比可以很多,所有这种方式只使用了
ecx 和 edx ,分别传递第一和第二参数,其余传递则转换成栈传参
6.3 EBP 或 ESP 寻址
int a = 1 ; mov dword ptr [ebp-4],1 注意是以 dword 四字节方式读写这个地址
char a = 2; mov byte prt [ ebp -8] , 2 注意是以byte方式读写这个地址
由此可见,局部变量通过栈空间来保存,并且是连续排列的方式存储在栈内
细心的人可以发现c++传参是从右往左一次入栈,采用正数标记法表表示局部变量便宜标号时,函数参数和局部变量都是正数
无法区分,所以使用负数标号法,正数是参数,负数是局部变量 , 0值就表示返回地址
使用push指令将数据压入栈中,而push指令将操作数赋值到栈顶,所以压入栈中的数据和原数据在不同地方,独立存在,
6.5 函数的返回值
函数调用结束后,ret指令为什么可以返回函数调用处的吓一跳指令,call 指令被执行后,改指令同时还会将下一条指令所在地址压入栈中
此时esp会减4,因为调用call指令后,有压栈操作.
在VC中,使用 eax来保存返回值,由于32位的eax只能保存4字节数据,因此大于4字节数据使用其他方法保存. sizeof(type)小于等于4的类型可以用欧诺个eax
Debug版本下,如果函数有返回值,那么通常在ret指令前会对eax赋值.
7. 变量在内存中的位置和访问方式
7.1 全局变量和局部变量
全局变量于常量有着相似的特征,都是在程序执行前就存在,PE文件中的只读数据节中,常量的节属性被修饰为不可写,二全部变量和静态变量则是可读写的.
全局变量在文件中的地址定位和常量相同,也需要减去基地址. 具有初始值的全局变量,在其值连接时被写入所创建PE文件中,当用户执行该文件时,操作系统先分析这个PE中的数据,将各个节点数据填入对应的虚拟内存地址中,吃时全局变量就存在了,等PE分析和加载工作完成后,才开始执行入口点的代码.
全局变量在内存中的地址顺序是先定义的变量在低地址,后定义的变量在高地址
7.2 局部静态变量工作方式
静态变量*部和全局,全局静态变量和全局变量类似,只是全局静态变量只能在本文件中使用,
局部静态变量在未进入作用于之前就已经存在, 汇编代码中,局部静态变量附近会有一个1字节的标志,通过位运算,将标志中的一位数据置1.以此判断局部静态变量是否初始化,由于1个字节占8位,所以这个标志可以同时表示8个局部静态变量的初始化状态
7.3 堆变量
堆变量最容易识别,在c\c++中,使用malooc 于 new 实现堆空间申请,free 于 delete 释放
保存堆空间首地址的变量大小为4字节指针类型 ,其范文方式按作用于来分. 他们的最终实现都是调用 _nh_malloc_dbg函数来实现
在申请对空间过程中调用了函数_nh_malloc_dbg ,其中使用 _CrtMemBlockHeader结构描述了堆空间的各个成员,在内存中,堆结构的每个节点都是使用双向链表的形式存储的,在_CrtMemBlockHeader结构中定义了前指针 pBlockHeraderPrev 和后指针 pBlockHeaderNext通过2个指针就可以遍历程序中申请的所有堆空间,成员iRequest记录了当前堆是第几次申请的. nDataSize 成员是堆空间数据大小
将获得的堆空间指针减4 得到 0xFDFDFD这是往上越界的检查标志, 减8 得到本次堆空间申请时第几次, 减16 得到本次申请堆空间的大小
减32得到上一个堆空间的首地址, 在堆数据的末尾,的4个字节是下一个堆空间的首地址
8. 数组和指针的寻址
虽然数组和指针都是针对地址操作,但是衙门有许多不同之处,数组是相同数据类型的集合,以现行方式连续存储在内存中,
指针而只是一个保存地址值得4字节变量,在使用中,数组名是一个地址常量值,保存数组首元素地址,不可修改,只能以此为基地址访问内存数据,
而指针却是一个变量.只要修改指针中所保存的地址数据,就可以随意访问
8.1 数组子函数内
数组中的数据在内存中的存储是线性连续的,其数据排列顺序由低地址到高地址,数组名称表示该数组的首地址,占用内存空间大小为
sizeof(数据类型) * 数组中元素个数,
字符串是最后一位数据使用0的数组, 为字符串数组赋值(初始化),其实就是赋值字符串的过程,不是单字节复制,而是每次复制4字节数据,2个内存的数据传递需要借用寄存器,而每个寄存器一次性可以保存4字节数据.
8.2 数组作为参数
当数组作为指针时,数组的下标值被省略了,这是因为,当数组作为函数形参时,函数参数中保存的是数组的首地址,是一个指针变量
虽然参数是指针变量,但需要特别注意的是,实参数组名为常量值,而指针或形参数组为变量,使用sizeof可以获取数组的总大小,而对于指针,或形参中保存的数组名,使用sizeof智能得到当前平台指针的长度
8.3 数组作为返回值
数组作为返回值于作为函数参数大同小异,都是将数组的手地址以指针的方式进行传递,不同之处是,当数组作为参数时,其定义所在的作用域必然在函数调用以外,,在调用之前就已经存在,