111qqz的小窝

老年咸鱼冲锋!

x86 calling conventions

x86的调用约定主要说的是这几件事:

  • The order in which atomic (scalar) parameters, or individual parts of a complex parameter, are allocated
  • How parameters are passed (pushed on the stack, placed in registers, or a mix of both)
  • Which registers the called function must preserve for the caller (also known as: callee-saved registers or non-volatile registers)
  • How the task of preparing the stack for, and restoring after, a function call is divided between the caller and the callee

调用约定实际上并不唯一

我们比较关注gcc编译器下的cdecl(C declaration)

对于如下这段代码:

调用过程如下:

在c语言中,函数的参数被以从右向左的顺序压入栈,也就是最后一个参数最先入栈。

这里是栈指的是调用栈(Call_stack)

调用栈的结构如下(注意此图的栈是从下往上增长的,这与通常情况并不相符,不过不影响此处的说明),这是在调用的DrawSquare函数中调用DrawLine函数时的情景

stack frame通常按照入栈顺序(写在前面的先入栈)由三部分组成(可能某部分为空):

  • 函数的参数值(以从右向左的顺序入栈)
  • caller的地址值,为的是调用函数之后能继续执行caller其余的代码。
  • 函数的局部变量

 

接下来我们看一下调用过程对寄存器的影响。这里暂且不提eax寄存器通常用来保存结果之类,主要想谈谈调用过程对sp和bp两个寄存器的影响。

sp是stack pointer,保存的是当前栈顶地址

bp是base pointer(就是stack frame中的frame pointer), 值为函数刚刚被调用时的栈顶位置。

bp这个寄存器的作用主要是比较方便,因为如果只有stack pointer,那么在函数里面,stack pointer也是可能变的,显然不如使用base pointer方便。

具体来说,在使用base pointer的情况下,函数的返回地址永远为ebp + 4,第一个参数的地址为ebp+8,第一个局部变量的地址为ebp-4

而且使用bp的情况下,回溯调用栈会变得非常方便。

At ebp is a pointer to ebp for the previous frame (this is why push ebp; mov ebp, esp is such a common way to start a function).  This effectively creates a linked list of base pointers.  This linked list makes it very easy to trace backwards up the stack.  For example if foo() calls bar() and bar() calls baz() and you’re debugging baz() you can easily find the parameters and local variables for foo() and bar().

为什么ebp指向的内容是上一个 stack frame中的ebp?我们看push ebp; mov ebp esp这两条指令。push ebp相当于先esp-=4,然后将ebp放到esp所指向的位置。接着mov ebp esp,相当于把当前的esp,也就是上一个ebp所在的位置,赋值给新的ebp.  所以。。这其实是个链表啊

 

 

参考资料:

x86 calling conventions

Stack_register

Call_stack#STACK-FRAME

What is exactly the base pointer and stack pointer? To what do they point?

All About EBP

 

 

【施工完成】MIT 6.828 lab 1: C, Assembly, Tools and Bootstrapping

花费了30+小时,终于搞定了orz

 

Part 1: PC Bootstrap

The PC’s Physical Address Space

8086/8088时代

由于8086/8088只有20跟地址线,因此物理内存空间就是2^20=1MB.地址空间从0x00000到0xFFFFF.其中从0x00000开始的640k空间被称为”low memory”,是PC真正能使用的RAM。从 0xA0000 到 0xFFFFF 的384k的non-volatile memory被硬件保留,用作video display buffers和BIOS等。

READ MORE →

优化学习笔记(1):Loop unrolling

迫于生计,最近要学习halide

先去学习/复习一下常见的编译优化技巧。

loop unrolling,也就是循环展开,顾名思义,就是把循环展开来写。

循环展开是一种优化,可以手动实现也可以编译器自动实现。

为什么要将循环展开?

  • 循环每次都需要判断终止条件,展开后可以消除这部分开销。
  • 减少分支预测开销。循环里的分支是指“跳出循环”还是“进行下一次迭代”
  • vectorization

    可以看到最里面一层循环被展开以实现向量化.向量化是一种优化计算的手段。该优化的实现基于SIMD 和Advanced_Vector_Extensions(AVX)指令集架构的支持。
  • 消除和loop counter(i)有关的除法计算。
  • 消除循环内部的分支。比如loop counter奇数和偶数时会进入不同的分支,那么将循环展开后,就消除了该分支。

有什么缺点?

  • 代码体积增加了。这对于嵌入式设备等往往是不可接受的。
  • 代码可读性变差了。
  • 单一指令可能会使用更多的寄存器,导致性能下降。
  • 如果循环内部包含函数调用,那么和函数的内联(inline)优化会有冲突。原因是,循环展开+函数展开…代码的体积会爆炸。

参考资料

 

【施工中】MIT 6.828 Operating System Engineering 学习笔记

课程主页

这课稍微有点硬核…感觉基础稍微有些不扎实就做不下去orz.

网上似乎是有博客写了6.828的学习笔记,不过我更希望自己能够独立完成,二手的知识,谁知道是对的错的呢…况且课程本身给的参考资料应该还是足够多的。

环境的话,手头没有ubuntu系统,恰好半年前剁了阿里云的轻应用服务器,就在上面做吧。

为了这门课,我读了/计划读以下书籍(随时更新)。大概也是为了检查一遍自己的知识体系。

每个lab用到的网页形式的参考资料,会在每个lab的博客中分别给出。

最后,放一段《游褒禅山记》中的文字,与君共勉!

夫夷以近,则游者众;险以远,则至者少。而世之奇伟、瑰怪,非常之观,常在于险远,而人之所罕至焉,故非有志者不能至也。有志矣,不随以止也,然力不足者,亦不能至也。有志与力,而又不随以怠,至于幽暗昏惑而无物以相之,亦不能至也。然力足以至焉,于人为可讥,而在己为有悔;尽吾志也而不能至者,可以无悔矣,其孰能讥之乎?

 

codeforces round 530 div2

A,B,C:都很简单,不说了。

D:一棵树,给出树的结构,以及从树根到某个深度为偶数的节点的路径和,问能否构造一种所有节点点权和最小的树,输出最小点权和。

思路:

容易知道,如果想要点权和最小,那么尽可能让靠近树根的点承担更多的点权。

具体做法是,bfs,对于每个节点u,取其儿子中最小的S值求节点u的信息。

比赛的时候wa16…最后发现是答案要用long long存…因为单个路径和是<=1E9的。。多个加起来会超过int…  长时间不打连这种常见的坑都不敏感了啊。。。

 

codeforces hello 2019

好久没玩cf了,竟然还能涨分(虽然我用的小号Orz)

三题,D应该是数学+DP…数学实在是忘干净了。。。

前面三题大体还好,都是1A,不过因为没有提前配置环境。。耽误了一些时间。。。

A:给出一个扑克牌x,和另一个包含5个扑克牌的集合。问扑克牌x是否和扑克牌集合中至少一张扑克牌的花色或者数字相同。

不多说了。

B:一块钟表(只有一个指针),初始指向12点,需要拨动指针恰好n次(n<=15),每次可能顺时针,也可能逆时针,拨动的角度范围在[1,180],问是否有一种方案,使得拨动n次后,指针回到12点。

思路:观察下数据范围,n最大才15,最多也不过2^15的情况…既然如此,不如暴力。

枚举的话我记得有三种方法来着。。。但是已经不记得怎么写了。。所以用了最朴素的办法。。。

C: 给出n(n<=1E5)个括号序列,括号序列可能不合法,现在要从这n个括号序列中,组成尽可能多的有序二元组,使得有序二元组的括号序列合法,并且每个括号序列只能出现在一个有序二元组中,现在问最多能组成多少这样的有序二元组。

思路:我们先考虑一下怎样的两个括号序列组成的有序二元组才是合法的有序序列。容易想到的是,如果两个括号序列本身都是合法的,那么组合在一起也一定是合法的。进一步,对于本身不合法的括号序列,容易知道,其必须只有一种没有完成匹配的括号方向,且该括号方向的数量与相反括号方向的数量相同,才能完成匹配。

因此做法是,对于括号序列预处理,得到该括号序列的状态(本身匹配为0,正数代表'(‘的个数,负数代表’)’的个数,如果有两个方向同时存在,则直接舍弃掉,因为这种括号序列不可能组成合法的括号序列。预处理之后,用multiset搞一下。

代码写得比较乱…flag存的时候其实没必要存index…

D:初始一个数n(n<=1E15),k次操作,每次操作等概率将当前的数变为其因子中的一个。问k次操作之后,结果的期望是多少。

在@适牛的指导下,以及参考了官方题解。。写了出来。。

dp还是太弱了。。。。

比较重要的一点是,不需要考虑所有因子,只需要考虑质因子。

质因子的个数不超过50个(因为 2^50 > 1E15)

另外一个重要的是,对于每一个质因子的概率是积性函数,可以乘在一起。

因此问题变成了,对于一个质因子唯一的n,如何算所求的期望。

我们考虑dp[i][j]表示第i次操作后,质因子还剩j个的概率。

显然dp[0][tot]=1,其中 p^tot = n,p为某个质因子。

转移方程为:

dp[i][j] = sum(dp[i-1][jj]) (j=<jj<=tot)

然后最后结果的期望就是:sum(dp[k][j]*p^j) (0=<j<=tot)

还有一点,由于题目的输出要求,需要用到费马小定理求个逆元。。。

逆元相关的参考 acdreamer的博客。。。

 

 

 

 

2019 to do list

  • Operating Systems: Three Easy Pieces
  • fluent python
  • 《计算机网络:自顶向下方法》
  • 《mysql必知必会》
  • PC Assembly Language ( for mit 6.828 )