kk Blog —— 通用基础


date [-d @int|str] [+%s|"+%F %T"]
netstat -ltunp
sar -n DEV 1

64位汇编参数传递

64位汇编

当参数少于7个时， 参数从左到右放入寄存器: rdi, rsi, rdx, rcx, r8, r9。
当参数为7个以上时， 前 6 个与前面一样， 但后面的依次从 “右向左” 放入栈中，即和32位汇编一样。

参数个数大于 7 个的时候
H(a, b, c, d, e, f, g, h);
a->%rdi, b->%rsi, c->%rdx, d->%rcx, e->%r8, f->%r9
h->8(%esp)
g->(%esp)
call H

Linux (and Windows) x86-64 calling conventionhas the first few arguments noton the stack, but in registers instead
See http://www.x86-64.org/documentation/abi.pdf (page 20)
Specifically:
If the class is MEMORY, pass the argument on the stack.
If the class is INTEGER, the next available register of the sequence %rdi, %rsi, %rdx, %rcx, %r8 and %r9 is used.
If the class is SSE, the next available vector register is used, the registers are taken in the order from %xmm0 to %xmm7.
If the class is SSEUP, the eightbyte is passed in the next available eightbyte chunk of the last used vector register.
If the class is X87, X87UP or COMPLEX_X87, it is passed in memory.
The INTEGERclass is anything that will fit in a general purpose register

【x86_64 Assembler Calling Convention】

1、x86_64 registers

2、x86_64寄存器特性表

3、特性要点：

　　1）常用寄存器有16个，分为x86通用寄存器以及r8-r15寄存器。
　　2）通用寄存器中，函数执行前后必须保持原始的寄存器有3个：是rbx、rbp、rsp。rx寄存器中，最后4个必须保持原值：r12、r13、r14、r15。
保持原值的意义是为了让当前函数有可信任的寄存器，减小在函数调用过程中的保存&恢复操作。除了rbp、rsp用于特定用途外，其余5个寄存器可随意使用。
　　3）通用寄存器中，不必假设保存值可随意使用的寄存器有5个：是rax、rcx、rdx、rdi、rsi。其中rax用于第一个返回寄存器（当 然也可以用于其它用途），rdx用于第二个返回寄存器（在调用函数时也用于第三个参数寄存器）。rcx用于第四个参数。rdi用于第一个参数。rsi用于 第二个函数参数。
　　4）r8、r9分配用于第5、第6个参数。

常用汇编指令对标志位的影响

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185

加法指令 ADD (addition)
指令对标志位的影响：
                     CF=1   最高有效位向高位有进位
                     CF=0   最高有效位向高位无进位
                     OF=1   两个同符号数相加（正数+正数 或 负数+负数），结果符号与其相反。
                     OF=0   两个不同符号数相加，或同符号数相加，结果符号与其相同。

带进位加法指令 ADC (add with carry)
指令对标志位的影响：
                     CF=1   最高有效位向高位有进位
                     CF=0   最低有效位相高位无进位
                     OF=1   两个同符号数相加，结果符号与其相反，
                     OF=0   两个同符号数相加，或同符号相加，结果符号与其相同

加1指令 INC (increament)
指令对标志位的影响：
                     对CF无影响
                     OF=1   两个同符号数相加，结果符号与其相反，
                     OF=0   两个同符号数相加，或同符号相加，结果符号与其相同。
 
减法指令 SUB (subtract)
指令对标志位的影响：
                     CF=1 二进制减法运算中最高有效位向高位有借位（被减数小于减数，不够减的情况）
                     CF=0 二进制减法运算中最高有效为向高位无借位（被减数〉=减数，够减的情况）
                     OF=1 两数符号相反（正数-负数，或负数-正数），而结果符号与减数相同。
                     OF=0 同符号数相减时，或不同符号数相减，其结果符号与减数不同。

带借位减法指令 SBB (subtract with borrow)
指令对标志位的影响：
                     CF=1 二进制减法运算中最高有效位向高位有借位（被减数小于减数，不够减的情况）
                     CF=0 二进制减法运算中最高有效为向高位无借位（被减数〉=减数，够减的情况）
                     OF=1 两数符号相反（正数-负数，或负数-正数），而结果符号与减数相同。
                     OF=0 同符号数相减时，或不同符号数相减，其结果符号与减数不同。

减1指令 DEC (decrement)
指令对标志位的影响：
                     对CF无影响
                     OF=1 两数符号相反（正数-负数，或负数-正数），而结果符号与减数相同。
                     OF=0 同符号数相减时，或不同符号数相减，其结果符号与减数不同。
                    
比较指令 CMP (compare)
指令对标志位的影响：
                     CF=1 二进制减法运算中最高有效位向高位有借位（被减数小于减数，不够减的情况）
                     CF=0 二进制减法运算中最高有效为向高位无借位（被减数〉=减数，够减的情况）
                     OF=1 两数符号相反（正数-负数，或负数-正数），而结果符号与减数相同。
                     OF=0 同符号数相减时，或不同符号数相减，其结果符号与减数不同。

求补指令 NEG (negate)
指令对标志位的影响：
                     CF=1 　不为0的操作数求补时
                     CF=0 　为0的操作数求补时
                     OF=1    操作数为-128（字节运算）或操作数为-32768（字运算）
                     OF=0    当求补运算的操作数不为－128（字节）或－32768（字）时

无符号乘法指令 MUL (unsigned multiple)    有符号乘法指令 IMUL(signed muliple)
指令对标志位的影响：乘法指令只影响标志位CF和OF，其他条件码位无定义。
                     MUL指令的条件码设置为：
                     CF OF=0 0 乘积的高一半为0（字节操作的（AH）或字操作的（DX））
                     CF OF=1 1 乘积的高一半不为0
                     IMUL指令的条件码设置为：
                     CF OF=0 0 乘积的高一半为低一半的符号扩展.
                     CF OF=1 1 其他情况

无符号数除法 DIV (unsigned divide)     带符号数除法 IDIV (singed divide)
指令对标志位的影响：不影响条件码。

逻辑与 AND (logic and)
指令对标志位的影响：
                     指令执行后 CF 和 OF 置零，AF无定义。
                     PF=1 结果操作数中1的个数为偶数时置1
                     PF=0 结果操作数中1的个数为奇数时置0

逻辑或 or (logic or)
指令对标志位的影响：
                     令执行后 CF 和 OF 置零，AF无定义。
                     PF=1 结果操作数中1的个数为偶数时置1
                     PF=0 结果操作数中1的个数为奇数时置0

逻辑非 NOT (logic not)
指令对标志位的影响：对标志位无影响

异或 XOR (exclusice or)
指令对标志位的影响：
                     令执行后 CF 和 OF 置零，AF无定义。
                     PF=1 结果操作数中1的个数为偶数时置1
                     PF=0 结果操作数中1的个数为奇数时置0

测试指令 TEST
指令对标志位的影响：
                     令执行后 CF 和 OF 置零，AF无定义。
                     PF=1 结果操作数中1的个数为偶数时置1
                     PF=0 结果操作数中1的个数为奇数时置0

逻辑左移 SHL (shift logical left)
指令对标志位的影响：CF=移入的数值
                     OF=1 当cnt=1时，移动后最高位的值发生变化。
                     OF=0 当cnt=1时，移动时最高位的值未发生变化。

逻辑右移 SHR (shift logical right)
指令对标志位的影响：CF=移入的数值
                     OF=1 当cnt=1时，移动后最高位的值发生变化。
                     OF=0 当cnt=1时，移动时最高位的值未发生变化。

算术左移 SAL (shift arithmetic left)
指令对标志位的影响：CF=移入的数值
                     OF=1 当cnt=1时，移动后最高位的值发生变化。
                     OF=0 当cnt=1时，移动时最高位的值未发生变化。

算术右移 SAR (shift arithmetic right)
指令对标志位的影响：CF=移入的数值
                     OF=1 当cnt=1时，移动后最高位的值发生变化。
                     OF=0 当cnt=1时，移动时最高位的值未发生变化。

循环左移 ROL (rotate left)
指令对标志位的影响：CF=移入的数值
                     OF=1 当cnt=1时，移动后最高位的值发生变化。
                     OF=0 当cnt=1时，移动时最高位的值未发生变化。

循环右移 ROR (rotate right)
指令对标志位的影响：CF=移入的数值
                     OF=1 当cnt=1时，移动后最高位的值发生变化。
                     OF=0 当cnt=1时，移动时最高位的值未发生变化。

带进位的循环左移 RCL (rotate left through carry)
指令对标志位的影响：CF=移入的数值。
                     OF=1 当cnt=1时，移动后最高位的值未发生变化。
                     OF=0 当cnt=1时，移动后最高位的值发生变化。
                     SF、ZF、PF标志位不受影响。

带进位的循环右移 RCR (rotate right through carry)
指令对标志位的影响：CF=移入的数值。
                     OF=1 当cnt=1时，操作数最高位的值未发生变化。
                     OF=0 当cnt=1时，操作数最高位的值发生变化。
                     SF、ZF、PF标志位不受影响。

串传送 MOVSB / MOVSW (move string byte/word)
指令对条件码的影响：不影响条件码。

存串 STOSB / STOSW (stroe from string byte/word)
指令对条件码的影响：不影响条件码。

取串LODSB / LODSW (load from string byte/word)
指令对条件码的影响：不影响条件码。

串比较 CMPSB / CMPSW (compare string byte/word)
指令对条件码的影响：
                     CF=1 二进制减法运算中最高有效位向高位有借位（被减数小于减数，不够减的情况）
                     CF=0 二进制减法运算中最高有效为向高位无借位（被减数〉=减数，够减的情况）
                     OF=1 两数符号相反（正数-负数，或负数-正数），而结果符号与减数相同。
                     OF=0 同符号数相减时，或不同符号数相减，其结果符号与减数不同。

串扫描 SCASB / SCASW (scan string byte / word)
指令对条件码的影响：
                     CF=1 二进制减法运算中最高有效位向高位有借位（被减数小于减数，不够减的情况）
                     CF=0 二进制减法运算中最高有效为向高位无借位（被减数〉=减数，够减的情况）
                     OF=1 两数符号相反（正数-负数，或负数-正数），而结果符号与减数相同。
                     OF=0 同符号数相减时，或不同符号数相减，其结果符号与减数不同。

条件转移指令
指令的汇编格式及功能    根据条件码的值转移：
49、JZ(JE) OPR        ZF=1
50、JNZ(JNE) OPR   ZF=0
51、JS OPR             SF=1
52、JNS OPR           SF=0
53、JO OPR             OF=1
54、JNO OPR          OF=0
55、JP OPR             PF=1
56、JNP OPR           PF=0
57、JC OPR             CF=1
58、JNC OPR          CF=0

比较两个无符号数，根据比较的结果转移
59、JB(JNAE,JC)   OPR   CF=1         被减数小于减数则转移
60、JNB(JAE,JNC) OPR   CF=0         被减数大于或等于减数则转移
61、JBE(JNA) OPR      CF或ZF=1      被减数小于或等于减数则转移
62、JNBE(JA) OPR      CF或ZF=0      被减数大于减数则转移

比较两个带符号数，根据比较结果转移
63、JL/JNGE OPR       SF异或OF=1           被减数小于减数则转移
64、JNL/JGE           SF异或OF=0               被减数不小于减数则转移
65、JLE/JNE           (SF异或OF)与ZF=1     被减数不大于减数则转移
66、JNLE/JG           (SF异或OF)与ZF=0     被减数大于减数则转移

根据CX寄存器的值转移
67、JCXZ              (CX)=0               CX内容为零 则转移

两个数只出现一次

problem

一个数组，其中只有两个数只出现一次，其余数皆出现偶数次。
设计Time: O(n) 的算法得出那个只出现一次的数。

answer

再因为a和b不等，那么ab必然不为0。
那么ab这个数上面必然能够找到一个二进制位是1
在这个二进制位上，a和b不等。
根据这个二进制位，将各元素中在这位上为1的分派到左边，为0的分派到右边，形成两个子数组。

可以证明，
1）这两个数组分别包含a和b。
2）每个数组中除了a或b之外的所有元素都是成对出现的。