emmm,被朋友问到你的博客都快长草了。。。怎么这么久都不写东西了。。。
其实是由于某种原因。。。迁移到了github pages
2019 to do list
BattleBlock Theater linux下无法启动的解决办法 （ void* MemoryBlock::Alloc(unsigned int): Assertion failed ）
在steam上买了 BattleBlock Theater， 官方说支持linux，但是却无法启动。
在steam里启动看不到log,于是找到游戏的安装目录。
/home/coder/.steam/steam/steamapps/common/BattleBlock Theater
在终端下启动，报错:
BattleBlockTheater: /media/BGBS/BBT_Linux/Core/MemorySystem.cpp:161: void* MemoryBlock::Alloc(unsigned int): Assertion `(!”Got request for zero bytes!”)’ failed.
^C[1] 22303 abort (core dumped) ./BattleBlockTheater
google了一下发现这似乎是游戏本身的bug,这里有一个workaround
办法是使用hex editor将游戏的可执行文件中， 从offset 0x24F2BE 开始的6个字节替换成0x90
我使用的hex editor 是hexcurse, 这里有一个使用指南 可以参考。
【施工中】MIT 6.828 lab 3: User Environments
JOS的environments基本可以理解成”process”进程的同义词，但是由于”process”是一个unix术语，因此使用environment这个词．
Part A: User Environments and Exception Handling
查看 kern/env.c文件，看到三个全局变量:
|
1 2 3 4 5 6 7 8 9 |
struct Env *envs = NULL; // All environments struct Env *curenv = NULL; // The current env static struct Env *env_free_list; // Free environment list |
envs会在JOS启动后会指向一个Env structures的数组，表示JOS中的全部environments. 理论上，JOS kernel最多能支持NENV个同时运行的environments. 但是实际上不会远不会达到这个数量．
env_free_list是一个链表结构，用来存放当前没有在运行的Env structure.. 和page_free_list 类似．
curenv表示的是当前正在运行的environment,当JOS刚刚启动，第一个environment运行之前，curenv的值为NULL.
【施工完成】CSAPP data lab
CSAPP第二章的内容以前组成原理基本都学过…所以就简单翻了翻。
对应的lab是用位运算实现各种有的没的…
题目基本都很tricky…
除了用到一些常规的位运算性质，还用到了一些奇怪的条件:
- ~0x7FFFFFFF = 0x7FFFFFFF + 1
- 0xFFFFFFFF +1 = 0x00000000
-
0 == ~0+1
唯一让我觉得比较有趣的是how many bits这道题
题目要求是给一个32-bit signed int,问最少用多少位能得到它的补码表示。
考虑正数，显然，高位的连续的多个0是不必要的，只需要一个符号位的0即可。
那么对于负数，高位的连续的多个1也是不必要的。 原因是，-2^k + 2^(k-1) = -2^(k-1),也就是说，去掉两个连续的1中高位的那个，数值没有改变。
我们可以将正数和负数统一来看，都是找到最高位的0和1的交界。
这可以通过和相邻的位置求异或，找到最高位的1的方式来实现。
接下来就是如何找一个数的最高位的1的位置了。
方法是构造一个单调的函数f,假设最高位位置为a,那么f((a,32))=0,f([0,a])=1.
然后在函数f上二分。
全部问题的代码如下,思路写在注释里了。还有3个涉及浮点数的问题之后补。
|
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 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 |
/* * bitXor - x^y using only ~ and & * Example: bitXor(4, 5) = 1 * Legal ops: ~ & * Max ops: 14 * Rating: 1 */ /* 0 0 -> 0 0 1 -> 1 1 0 - > 1 1 1 - > 0 */ // ~(~a & ~b)&~(a&b) int bitXor(int x, int y) { int ans = ~(~x & ~y)&(~(x&y)); // printf("%d\n",ans); return ans; } /* * tmin - return minimum two's complement integer * Legal ops: ! ~ & ^ | + << >> * Max ops: 4 * Rating: 1 */ /* 0X10000000 */ int tmin(void) { int ans = 0x1 << 31; return ans; } //2 /* * isTmax - returns 1 if x is the maximum, two's complement number, * and 0 otherwise * Legal ops: ! ~ & ^ | + * Max ops: 10 * Rating: 1 * 0x7FFFFFFF */ int isTmax(int x) { /* 大体思路首先是根据，如果x是最大值0x7FFFFFFF,那么~x和x+1(自然溢出)应该相等。 不能用等号，但是我们可以用异或。x==y 等价于 !(x^y). 因此有了后半段!(x+1)^(~x) 但是满足这个条件的还有-1,也就是0xFFFFFFFF,因此我们需要排除掉-1. 还是用异或的性质，这回是0异或者任何数都等于其本身。 因此如果x为-1，那么前后两部分都为1，结果为0. 如果x为TMAX,那么前面为0，后面为1，结果为1. 如果x为其他任何数，前后结果都应为0. 结果为0。 */ return (!(x+1))^!((x+1)^(~x)); } /* * allOddBits - return 1 if all odd-numbered bits in word set to 1 * where bits are numbered from 0 (least significant) to 31 (most significant) * Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1 * Legal ops: ! ~ & ^ | + << >> * Max ops: 12 * Rating: 2 */ // 理解错误。误以为是要求当前长度x的所有奇数位上都是1. // 实际上要求和x的长度无关，而是要求[0,31]中，所有奇数位上都是1. int allOddBits(int x) { int half_mask = (0xAA<<8) | 0xAA; int mask = (half_mask<<16) + half_mask; // printf("mask:%08X x:%08x %08x\n",mask,x,x&mask); return !((x&mask)^mask); } /* * negate - return -x * Example: negate(1) = -1. * Legal ops: ! ~ & ^ | + << >> * Max ops: 5 * Rating: 2 */ int negate(int x) { return ~x + 1; } //3 /* * isAsciiDigit - return 1 if 0x30 <= x <= 0x39 (ASCII codes for characters '0' to '9') * Example: isAsciiDigit(0x35) = 1. * isAsciiDigit(0x3a) = 0. * isAsciiDigit(0x05) = 0. * Legal ops: ! ~ & ^ | + << >> * Max ops: 15 * Rating: 3 */ /* 把0-9的二进制写出来，发现0-7占满了3bit的二进制的8种组合。 因此考虑只判断8和9两种4bit的情况 构造mask,不在意的bit的位置放0，在意的bit位置放1. */ int isAsciiDigit(int x) { int mask = 0x0E; int ones = x&mask; int ones_3 = ones >> 3; int tens = x>>4; // printf("x: %08x tens: %08x ones:%08x\n",x,tens,ones); int ones_ok = (!(ones^0x8)) | (!ones_3); int tens_ok = !(tens^0x3); return ones_ok & tens_ok; } /* * conditional - same as x ? y : z * Example: conditional(2,4,5) = 4 * Legal ops: ! ~ & ^ | + << >> * Max ops: 16 * Rating: 3 */ /* 关键思路是0xFFFFFFFF和0x00000000之间差了1. 而这两个数一个是全部位置都取的mask,一个是全部位置都不取的mask. */ int conditional(int x, int y, int z) { return z^(!x + ~0 )&(y^z); } /* * isLessOrEqual - if x <= y then return 1, else return 0 * Example: isLessOrEqual(4,5) = 1. * Legal ops: ! ~ & ^ | + << >> * Max ops: 24 * Rating: 3 */ /* 大体思路是，符号位相同和符号位不同分别考虑 符号位相同: 考虑差的符号位。 符号位不同: 当x<0,y>=0时结果为1. */ int isLessOrEqual(int x, int y) { int minus = y + (~x+1); int s_x = (x>>31)&1; int s_y = (y>>31)&1; int s_minus = (minus>>31) & 1; return (s_x&(!s_y))| (!(s_x^s_y)&!s_minus); } //4 /* * logicalNeg - implement the ! operator, using all of * the legal operators except ! * Examples: logicalNeg(3) = 0, logicalNeg(0) = 1 * Legal ops: ~ & ^ | + << >> * Max ops: 12 * Rating: 4 */ /* 0 == ~0+1 -2147483648 = ~-2147483648+1 满足 x == ~x+1 重点是x和~x+1的符号位相同，如果都是0那么x=0,如果都是1那么x=-214783648` */ int logicalNeg(int x) { int s1 = (x>>31)&1; int s2 = ((~x+1)>>31)&1; // printf("s1: %d s2:%d %d %d\n",s1,s2,s1|s2,~(s1|s2)); // 1 + negate(0) -> 1 // 1 + neagate(1) -> 0 return 1+(1+~(s1|s2)); } /* howManyBits - return the minimum number of bits required to represent x in * two's complement * Examples: howManyBits(12) = 5 * howManyBits(298) = 10 * howManyBits(-5) = 4 * howManyBits(0) = 1 * howManyBits(-1) = 1 ??? should be 2? * howManyBits(0x80000000) = 32 * Legal ops: ! ~ & ^ | + << >> * Max ops: 90 * Rating: 4 */ /* 思路似乎可以转化成判断一个数（可正可负）的最高位的1的位置。 判断最高位1用二分的办法。 构造一个单调的函数，假设最高位位置为a,那么f((a,32))=0,f([0,a])=1. 被 howManyBits(-1)==1 困扰了好久，实际上就是0x1，只有一位，改位就是符号位的情况。 */ int howManyBits(int x) { int n = 0 ; x^=(x<<1); n += (!!( x & ((~0) << (n + 16)) )) << 4; // 看高16位是否为0，是的话区间为[0,16),否的话为[16,32) // printf("n:%d\n",n); // printf("%d\n",!!(x & ((~0) << (n + 16)))); n += (!!( x & ((~0) << (n + 8)) )) << 3; // printf("n:%d\n",n); n += (!!( x & ((~0) << (n + 4)) )) << 2; // printf("n:%d\n",n); n += (!!( x & ((~0) << (n + 2)) )) << 1; // printf("n:%d\n",n); n += (!!( x & ((~0) << (n + 1)) )); // printf("n:%d\n",n); // int s = (x>>31)&1; // int ret = n+1+((1^s)&(!!x)); // // printf("x:%d ret:%d\n",x,ret); return n+1; } |
补上三个涉及浮点数的问题…比较无聊，按照IEEE754操作即可．
|
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 |
//float /* * floatScale2 - Return bit-level equivalent of expression 2*f for * floating point argument f. * Both the argument and result are passed as unsigned int's, but * they are to be interpreted as the bit-level representation of * single-precision floating point values. * When argument is NaN, return argument * Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while * Max ops: 30 * Rating: 4 */ unsigned floatScale2(unsigned uf) { int exp_ = (uf & 0x7f800000) >> 23; int s_ = uf & 0x80000000; if (exp_ == 0) return (uf << 1) | s_; if (exp_ == 255) return uf; ++exp_; if (exp_ == 255) return 0x7f800000 | s_; return (uf & 0x807fffff) | (exp_ << 23); } /* * floatFloat2Int - Return bit-level equivalent of expression (int) f * for floating point argument f. * Argument is passed as unsigned int, but * it is to be interpreted as the bit-level representation of a * single-precision floating point value. * Anything out of range (including NaN and infinity) should return * 0x80000000u. * Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while * Max ops: 30 * Rating: 4 */ int floatFloat2Int(unsigned uf) { int s_ = uf >> 31; int exp_ = ((uf & 0x7f800000) >> 23) - 127; int frac_ = (uf & 0x007fffff) | 0x00800000; if (!(uf & 0x7fffffff)) return 0; if (exp_ > 31) return 0x80000000; if (exp_ < 0) return 0; if (exp_ > 23) frac_ <<= (exp_ - 23); else frac_ >>= (23 - exp_); if (!((frac_ >> 31) ^ s_)) return frac_; else if (frac_ >> 31) return 0x80000000; else return ~frac_ + 1; } /* * floatPower2 - Return bit-level equivalent of the expression 2.0^x * (2.0 raised to the power x) for any 32-bit integer x. * * The unsigned value that is returned should have the identical bit * representation as the single-precision floating-point number 2.0^x. * If the result is too small to be represented as a denorm, return * 0. If too large, return +INF. * * Legal ops: Any integer/unsigned operations incl. ||, &&. Also if, while * Max ops: 30 * Rating: 4 */ unsigned floatPower2(int x) { int exp = x + 127; if (exp <= 0) return 0; if (exp >= 255) return 0x7f800000; return exp << 23; } |
manjaro /archlinux 下 steam 文明5/6(civilization V/VI)的运行方法
系统版本为Manjaro 18.0.3 Illyria
运行文明5比较容易，只需要设置启动选项为:
LD_PRELOAD=/usr/lib32/libopenal.so.1 %command%
文明6运行会报错 undefined symbol: FT_Done_MM_Var
解决办法是 在终端中用如下办法运行steam:
LD_PRELOAD=/usr/lib/libfreetype.so steam
【试工中】 halide学习笔记
Halide is a programming language designed to make it easier to write high-performance image and array processing code on modern machines.
halide有两个特性比较吸引人。一个是对于各种平台架构的支持。
- CPU architectures: X86, ARM, MIPS, Hexagon, PowerPC
- Operating systems: Linux, Windows, macOS, Android, iOS, Qualcomm QuRT
- GPU Compute APIs: CUDA, OpenCL, OpenGL, OpenGL Compute Shaders, Apple Metal, Microsoft Direct X 12
另一个是把计算什么和怎么计算(何时计算)分离开来。
可以直接参考tutorials 来学习
下面是一段将Halide Buffer转化成opencv Mat的代码，用于调试。
|
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 |
// Include some support code for loading pngs. // #include "halide_image_io.h" #include <iostream> #include "para_norm.h" #include "HalideBuffer.h" #include "clock.h" #include "halide_image_io.h" // for Halide::tools to load image. just for debug #include <opencv2/opencv.hpp> // to show image // #include "Halide.h" using namespace std; using namespace cv; using namespace Halide; using namespace Halide::Runtime; // using namespace Halide::Tools; void convertHalide2Mat(const Buffer<uint8_t> &src, cv::Mat &dest) { if (dest.empty()) dest.create(cv::Size(src.width(), src.height()), CV_MAKETYPE(CV_8U, src.channels())); const int ch = dest.channels(); if (ch == 1) { for (int j = 0; j < dest.rows; j++) { for (int i = 0; i < dest.cols; i++) { dest.at<uchar>(j, i) = src(i, j); } } } else if (ch == 3) { for (int j = 0; j < dest.rows; j++) { for (int i = 0; i < dest.cols; i++) { dest.at<uchar>(j, 3 * i + 0) = src(i, j, 2); dest.at<uchar>(j, 3 * i + 1) = src(i, j, 1); dest.at<uchar>(j, 3 * i + 2) = src(i, j, 0); } } } } int main(int argc, char **argv) { Halide::Runtime::Buffer<uint8_t> input = Halide::Tools::load_image("/data/github/learnhalide/png.png"); cv::Mat Img; convertHalide2Mat(input,Img); cv::imshow("debug", Img); cv::waitKey(0); return 0; } |
吐槽下hahide的文档…各种函数全靠试…
试了好久得到的,opencv Mat转halide::buffer的办法:
|
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 |
cv::Mat image = cv::imread("/data/github/learnhalide/png.png"); cv::imshow("input",image); cv::waitKey(0); halide_buffer_t buffer; // memset(&buffer, 0, sizeof(buffer)); buffer.host = image.data; printf("image.data %d %d %d\n",image.data[0],image.data[1],image.data[2]); printf("buffer.host %d %d %d\n",buffer.host[0],buffer.host[1],buffer.host[2]); // 数据没有copy过来 buffer.type = halide_type_t(halide_type_uint,8); buffer.dimensions = 3; buffer.dim = (halide_dimension_t *)malloc(3*4*sizeof(uint32_t)); buffer.dim[0].extent = image.cols; buffer.dim[1].extent = image.rows; buffer.dim[2].extent = image.channels(); buffer.dim[0].min = buffer.dim[1].min = buffer.dim[2].min = 0; buffer.dim[0].stride = image.step1(1); buffer.dim[1].stride = image.step1(0); buffer.dim[2].stride = 1; Halide::Runtime::Buffer<uint8_t> input(buffer); printf("input buffer:%d %d %d\n",input.width(),input.height(),input.channels()); // printf("%d\n",input(2,2)); const halide_buffer_t * raw_buffer = input.raw_buffer(); printf("raw buffer: %d %d %d\n",raw_buffer->host[0],raw_buffer->host[1],raw_buffer->host[2]); cv::Mat Img; convertHalide2Mat(input, Img); printf("Mat(%d %d)\n", Img.cols, Img.rows); cv::imshow("debug", Img); cv::waitKey(0); |
可能会报错Error: Constraint violated: input.stride.0 (3) == 1 (1),原因是:
We have a default constraint of stride==1 on the innermost dimension, so that vectorization works out well
Constraint violated: f.stride.0 (2) == 1 (1) #3109
解决办法是(对于AOT的编译方式):
ImageParam input(type_of<uint8_t>(), 3);
input.dim(0).set_stride(Expr());
一种更简便的opencv Mat得到halide buffer的办法. 一个关键的问题是opencv Mat的memory layout是Interleaved的方式，也就是如下:
// RGBRGBRGBRGBRGBRGBRGBRGB
// RGBRGBRGBRGBRGBRGBRGBRGB
// RGBRGBRGBRGBRGBRGBRGBRGB
// RGBRGBRGBRGBRGBRGBRGBRGB
但是Halide::buffer的默认memory layout是Planar的方式：
// RRRRRRRR
// RRRRRRRR
// RRRRRRRR
// RRRRRRRR
// GGGGGGGG
// GGGGGGGG
// GGGGGGGG
// GGGGGGGG
// BBBBBBBB
// BBBBBBBB
// BBBBBBBB
// BBBBBBBB
因此需要用到函数
make_interleaved()
|
1 2 3 4 5 6 7 8 |
cv::Mat image = cv::imread("/data/github/learnhalide/png.png"); Halide::Runtime::Buffer<uint8_t> input = Halide::Runtime::Buffer<uint8_t>::make_interleaved(image.data,1240, 460, 3); |
【施工完毕】MIT 6.828 lab 2: Memory Management
2019年2月24:完成了除了”Challenge”以外的全部练习和问题. 总共花费15个小时.
2019年2月26:完成”Challenge 2″(应该是最简单的一个orz，只花了不到一个小时)
Part 1: Physical Page Management
操作系统必须时刻追踪哪些物理内存在使用，哪些物理内存没有在使用。
一个问题是，
Ex 1. In the file kern/pmap.c, you must implement code for the following functions (probably in the order given).
boot_alloc()
mem_init() (only up to the call to check_page_free_list(1))
page_init()
page_alloc()
page_free()check_page_free_list() and check_page_alloc() test your physical page allocator. You should boot JOS and see whether check_page_alloc() reports success. Fix your code so that it passes. You may find it helpful to add your own assert()s to verify that your assumptions are correct.
C语言变长参数
说起C语言的变长参数，可能听起来比较陌生，因为很少会需要自己实现。不过想一下scanf和printf，参数个数的确是不固定的。
stdarg.h 中提供以一套机制来实现变长参数。以及，要说明的是，变长参数不是什么黑魔法，原理依赖于stack frame的结构，具体可以参考x86-calling-conventions 简单来说，由于函数参数入栈的顺序是固定的，因此一旦我们知道某函数帧的栈上的一个固定参数的位置，我们完全有可能推导出其他变长参数的位置
在实现上，需要了解的是：
- va_list，一个类型，可以看做是变长参数列表；
- va_start，用来初始化变长参数列表的宏，声明为void va_start( va_list ap, parm_n ); ap为va_list变量，parm_n为变长参数前一个变量（C语言要求至少有一个named variable作为函数的parameter)
- va_arg,用来得到下一个参数的宏，声明为T va_arg( va_list ap, T ); 返回的类型取决于传入的类型T。特别注意:”If va_arg is called when there are no more arguments in ap, the behavior is undefined.”
- va_end ,用来将va_list释放的宏。
下面看一个例子就明白怎么用了orz
|
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 |
#include <stdio.h> #include <stdarg.h> /* print all args one at a time until a negative argument is seen; all args are assumed to be of int type */ void printargs(int arg1, ...) { va_list ap; int i; va_start(ap, arg1); for (i = arg1; i >= 0; i = va_arg(ap, int)) printf("%d ", i); va_end(ap); putchar('\n'); } int main(void) { printargs(5, 2, 14, 84, 97, 15, -1, 48, -1); printargs(84, 51, -1); printargs(-1); printargs(1, -1); return 0; } output: 5 2 14 84 97 15 84 51 1 |
如果想研究c语言中变长参数的具体实现，可以参考 也谈C语言变长参数
参考资料:
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)
对于如下这段代码:
|
1 2 3 4 5 6 7 8 9 10 11 12 |
int callee(int, int, int); int caller(void) { return callee(1, 2, 3) + 5; } |
调用过程如下:
|
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 |
caller: ; make new call frame ; (some compilers may produce an 'enter' instruction instead) push ebp ; save old call frame mov ebp, esp ; initialize new call frame ; push call arguments, in reverse ; (some compilers may subtract the required space from the stack pointer, ; then write each argument directly, see below. ; The 'enter' instruction can also do something similar) ; sub esp, 12 : 'enter' instruction could do this for us ; mov [ebp-4], 3 : or mov [esp+8], 3 ; mov [ebp-8], 2 : or mov [esp+4], 2 ; mov [ebp-12], 1 : or mov [esp], 1 push 3 push 2 push 1 call callee ; call subroutine 'callee' add eax, 5 ; modify subroutine result ; (eax is the return value of our callee, ; so we don't have to move it into a local variable) ; restore old call frame ; (some compilers may produce a 'leave' instruction instead) ; add esp, 12 ; remove arguments from frame, ebp - esp = 12. ; compilers will usually produce the following instead, ; which is just as fast, and, unlike the add instruction, ; also works for variable length arguments ; and variable length arrays allocated on the stack. mov esp, ebp ; most calling conventions dictate ebp be callee-saved, ; i.e. it's preserved after calling the callee. ; it therefore still points to the start of our stack frame. ; we do need to make sure ; callee doesn't modify (or restores) ebp, though, ; so we need to make sure ; it uses a calling convention which does this pop ebp ; restore old call frame ret ; return |
在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. 所以。。这其实是个链表啊！
参考资料:
What is exactly the base pointer and stack pointer? To what do they point?
【施工完成】MIT 6.828 lab 1: C, Assembly, Tools and Bootstrapping
花费了30+小时，终于搞定了orz
Part 1: PC Bootstrap
The PC’s Physical Address Space
8086/8088时代
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
+------------------+ <- 0x00100000 (1MB) | BIOS ROM | +------------------+ <- 0x000F0000 (960KB) | 16-bit devices, | | expansion ROMs | +------------------+ <- 0x000C0000 (768KB) | VGA Display | +------------------+ <- 0x000A0000 (640KB) | | | Low Memory | | | +------------------+ <- 0x00000000 |
由于8086/8088只有20跟地址线，因此物理内存空间就是2^20=1MB.地址空间从0x00000到0xFFFFF.其中从0x00000开始的640k空间被称为”low memory”，是PC真正能使用的RAM。从 0xA0000 到 0xFFFFF 的384k的non-volatile memory被硬件保留，用作video display buffers和BIOS等。
优化学习笔记(1):Loop unrolling
迫于生计，最近要学习halide
先去学习/复习一下常见的编译优化技巧。
loop unrolling，也就是循环展开，顾名思义，就是把循环展开来写。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
normal loop: int x; for (x = 0; x < 100; x++) { delete(x); } after loop unrolling: int x; for (x = 0; x < 100; x += 5 ) { delete(x); delete(x + 1); delete(x + 2); delete(x + 3); delete(x + 4); } |
循环展开是一种优化，可以手动实现也可以编译器自动实现。
为什么要将循环展开？
- 循环每次都需要判断终止条件，展开后可以消除这部分开销。
- 减少分支预测开销。循环里的分支是指“跳出循环”还是“进行下一次迭代”
- vectorization
123456789101112131415161718192021222324252627for (int y = 0; y < 4; y++) {for (int x_outer = 0; x_outer < 2; x_outer++) {// The loop over x_inner has gone away, and has been// replaced by a vectorized version of the// expression. On x86 processors, Halide generates SSE// for all of this.int x_vec[] = {x_outer * 4 + 0,x_outer * 4 + 1,x_outer * 4 + 2,x_outer * 4 + 3};int val[] = {x_vec[0] + y,x_vec[1] + y,x_vec[2] + y,x_vec[3] + y};printf("Evaluating at <%d, %d, %d, %d>, <%d, %d, %d, %d>:"" <%d, %d, %d, %d>\n",x_vec[0], x_vec[1], x_vec[2], x_vec[3],y, y, y, y,val[0], val[1], val[2], val[3]);}}zhichi
可以看到最里面一层循环被展开以实现向量化.向量化是一种优化计算的手段。该优化的实现基于SIMD 和Advanced_Vector_Extensions(AVX)指令集架构的支持。 - 消除和loop counter(i)有关的除法计算。
1234567891011for (int fused = 0; fused < 4*4; fused++) {int y = fused / 4;int x = fused % 4;printf("Evaluating at x = %d, y = %d: %d\n", x, y, x + y);} - 消除循环内部的分支。比如loop counter奇数和偶数时会进入不同的分支，那么将循环展开后，就消除了该分支。
有什么缺点？
- 代码体积增加了。这对于嵌入式设备等往往是不可接受的。
- 代码可读性变差了。
- 单一指令可能会使用更多的寄存器，导致性能下降。
- 如果循环内部包含函数调用，那么和函数的内联(inline)优化会有冲突。原因是，循环展开＋函数展开…代码的体积会爆炸。
参考资料
- Optimizing subroutines in assembly language An optimization guide for x86 platforms(chapter 12.12)
- Loop unrolling
【施工中】MIT 6.828 Operating System Engineering 学习笔记
这课稍微有点硬核…感觉基础稍微有些不扎实就做不下去orz.
网上似乎是有博客写了6.828的学习笔记，不过我更希望自己能够独立完成，二手的知识，谁知道是对的错的呢…况且课程本身给的参考资料应该还是足够多的。
环境的话，手头没有ubuntu系统，恰好半年前剁了阿里云的轻应用服务器，就在上面做吧。
为了这门课，我读了/计划读以下书籍（随时更新）。大概也是为了检查一遍自己的知识体系。
- Operating Systems: Three Easy Pieces 已读完，大概需要120小时
- PC Assembly Language 6.828给的汇编参考书籍
每个lab用到的网页形式的参考资料，会在每个lab的博客中分别给出。
最后，放一段《游褒禅山记》中的文字，与君共勉！
夫夷以近，则游者众；险以远，则至者少。而世之奇伟、瑰怪，非常之观，常在于险远，而人之所罕至焉，故非有志者不能至也。有志矣，不随以止也，然力不足者，亦不能至也。有志与力，而又不随以怠，至于幽暗昏惑而无物以相之，亦不能至也。然力足以至焉，于人为可讥，而在己为有悔；尽吾志也而不能至者，可以无悔矣，其孰能讥之乎？
codeforces round 530 div2
A,B,C:都很简单，不说了。
D:一棵树，给出树的结构，以及从树根到某个深度为偶数的节点的路径和，问能否构造一种所有节点点权和最小的树，输出最小点权和。
思路：
容易知道，如果想要点权和最小，那么尽可能让靠近树根的点承担更多的点权。
具体做法是，bfs，对于每个节点u，取其儿子中最小的S值求节点u的信息。
比赛的时候wa16…最后发现是答案要用long long存…因为单个路径和是<=1E9的。。多个加起来会超过int… 长时间不打连这种常见的坑都不敏感了啊。。。
|
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 |
#include <bits/stdc++.h> #define PB push_back #define fst first #define sec second #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define ms(a,x) memset(a,x,sizeof(a)) typedef long long LL; #define pi pair < int ,int > #define MP make_pair using namespace std; const double eps = 1E-8; const int dx4[4]={1,0,0,-1}; const int dy4[4]={0,-1,1,0}; const int inf = 0x3f3f3f3f; const int N=1E5+7; int n; vector<int>edge[N]; int s[N]; int d[N]; bool vis[N]; int a[N]; // void dfs(int u,int dep) // { // int siz = edge[u].size(); // for (auto v: edge[u]) // { // dfs(v,dep+1); // } // } int bfs() { ms(d,-1); ms(vis,false); queue<int>Q; Q.push(1); //root vis[1] = true; d[1] = s[1]; while (!Q.empty()) { int u = Q.front();Q.pop(); // cout<<"u:"<<u<<" "<<Q.size()<<endl; int min_sum_in_leaf = inf; bool even = false; // cout<<"v seq:"; for ( auto v: edge[u]) { // cout<<v<<" s[v]:"<<s[v]<<" "; if (s[v]==-1) { Q.push(v); d[v] = d[u]; even = true; } if (s[v]!=-1) min_sum_in_leaf = min(min_sum_in_leaf,s[v]); } cout<<endl; if (even) continue; // cout<<"min_sum_in_leaf:"<<min_sum_in_leaf<<endl; // cout<<"u:"<<u<<" d[u]:"<<d[u]<<endl; if (d[u]>min_sum_in_leaf) return -1; //不可能 if (min_sum_in_leaf==inf) { // a[u] = continue; } a[u] = min_sum_in_leaf - d[u]; d[u] = min_sum_in_leaf; for ( auto v: edge[u]) { a[v] = s[v] - d[u]; d[v] = s[v]; // cout<<"v:"<<v<<" a[v]:"<<a[v]<<" d[v]:"<<d[v]<<endl; Q.push(v); } } return 0; } int main() { #ifndef ONLINE_JUDGE freopen("./in.txt","r",stdin); #endif cin>>n; for ( int i = 2 ; i <= n ; i++) { int x; cin>>x; edge[x].push_back(i); } for ( int i = 1 ; i <= n ; i++) cin>>s[i]; // for ( int i = 1 ;i <= n ; i++) cout<<"s[i]:"<<s[i]<<endl; ms(a,0); a[1] = s[1]; LL ans = bfs(); if (ans==-1) { puts("-1"); } else { for ( int i = 1 ; i <= n ; i++) { // cout<<i<<":"<<a[i]<<" d:"<<d[i]<<" s:"<<s[i]<<endl; ans = ans + a[i]; } cout<<ans<<endl; } #ifndef ONLINE_JUDGE fclose(stdin); #endif return 0; } |
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的情况…既然如此，不如暴力。
枚举的话我记得有三种方法来着。。。但是已经不记得怎么写了。。所以用了最朴素的办法。。。
|
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 |
#include <bits/stdc++.h> using namespace std; const int inf = 0x3f3f3f3f; #define ms(a,x) memset(a,x,sizeof(a)) typedef long long LL; int n; int a[30]; vector<int>bin; void cal( int x) { bin.clear(); while (x>0) { bin.push_back(x%2); x/=2; } while (bin.size()<n) { bin.push_back(0); } } int main() { cin>>n; for ( int i = 1 ; i <= n ; i++) cin>>a[i]; if (n==1) { puts("NO"); return 0; } int total = 1 << n; for ( int i = 0 ; i < total ; i++) { cal(i); int ang = 0; // for ( auto x : bin) cout<<x; // cout<<"bin size:"<<bin.size()<<endl; for ( int j = 0 ; j < bin.size() ; j++ ) { int x = bin[j]; // cout<<"x:"<<x; if (x==0) ang = ang + a[j+1]; else ang = ang - a[j+1]; } // cout<<endl; if (ang%360==0) { puts("YES"); return 0; } // cout<<endl; } puts("NO"); return 0; } |
C: 给出n(n<=1E5)个括号序列,括号序列可能不合法，现在要从这n个括号序列中，组成尽可能多的有序二元组，使得有序二元组的括号序列合法，并且每个括号序列只能出现在一个有序二元组中，现在问最多能组成多少这样的有序二元组。
思路：我们先考虑一下怎样的两个括号序列组成的有序二元组才是合法的有序序列。容易想到的是，如果两个括号序列本身都是合法的，那么组合在一起也一定是合法的。进一步，对于本身不合法的括号序列，容易知道，其必须只有一种没有完成匹配的括号方向，且该括号方向的数量与相反括号方向的数量相同，才能完成匹配。
因此做法是，对于括号序列预处理，得到该括号序列的状态（本身匹配为0，正数代表'(‘的个数，负数代表’)’的个数，如果有两个方向同时存在，则直接舍弃掉，因为这种括号序列不可能组成合法的括号序列。预处理之后，用multiset搞一下。
代码写得比较乱…flag存的时候其实没必要存index…
|
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 |
#include <bits/stdc++.h> using namespace std; const int inf = 0x3f3f3f3f; #define ms(a,x) memset(a,x,sizeof(a)) typedef long long LL; const int N=1E5+7; int n; string st[N]; // 0 for just ok, '-' for num of ), '+' for num of ( vector< pair<int,int> >flag; // <id,state> void solve(int index,string str) { stack<char>S; for ( auto ch : str) { if (S.empty()) { S.push(ch); continue; } if (S.top()=='('&&ch==')') { S.pop(); continue; } S.push(ch); // cout<<"S.size():"<<S.size()<<endl; } if (S.empty()) //自己匹配 { flag.push_back(make_pair(0,index)); // cout<<"empty stack here . just match"<<endl; return; } int state = 0; // cout<<"S.size():"<<S.size()<<endl; int siz = S.size(); while (!S.empty()) { char x = S.top(); // cout<<"x:"<<x<<endl; S.pop(); if (state==0) { if (x=='(') state = 1; else state = -1; } else { if (state==1&&x==')') return ; if (state==-1&&x=='(') return; } } state = state*siz; // cout<<"state in function"<<state<<endl; flag.push_back(make_pair(state,index)); } int main() { cin>>n; for ( int i = 1; i <= n ; i++) cin>>st[i]; for ( int i = 1; i <= n ; i++) { solve(i,st[i]); } if (flag.size()==0) { puts("0"); return 0; } int ans = 0 ; int cnt = 0; // cout<<"flag size:"<<flag.size()<<endl; for ( auto pi:flag) { // cout<<"state:"<<pi.first<<endl; if (pi.first==0) cnt++; } ans = ans + cnt/2; multiset<int>posi,nega; set<int>setposi; for (auto pi:flag) { if (pi.first>0) { posi.insert(pi.first); setposi.insert(pi.first); } else if (pi.first<0) nega.insert(pi.first); } for ( auto x:setposi) { int tmp = min(posi.count(x),nega.count(-x)); if (tmp==0) continue; // coutcoutcout<<"x:"<<x<<" "<<posi.count(x)<<" "<<nega.count(-x)<<endl; ans = ans + tmp; } cout<<ans<<endl; return 0; } |
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的博客。。。
|
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 |
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int mod = 1E9 + 7; LL n; int k; vector<pair<LL, int>> fac; //分解质因数 int mul(LL a, LL b) { // cout<<"a:"<<a <<" b:"<<b<<" a*b "<< (int)((LL)a * b % mod)<<endl; return (int)((LL)a * b % mod); } void add (int &a,int b) { // cout<<"a:"<<a<<" b:"<<b<<endl; a = a + b; if (a>=mod) a-=mod; } int ksm(int a, LL b) { int ret = 1; while (b > 0) { if (b & 1) ret = mul(ret, a); a = mul(a, a); b = b >> 1; } return ret; } int inv(int a) { return ksm(a, mod - 2); } int main() { cin >> n >> k; for (LL i = 2; i * i <= n; i++) { int cnt = 0; if (n % i == 0) { while (n % i == 0) { n /= i; cnt++; } fac.push_back(make_pair(i, cnt)); } } if (n > 1) { fac.push_back(make_pair(n, 1)); } // check // for ( auto & p:fac) cout<<p.first<<" "<<p.second<<endl; int ans = 1; for (auto &p : fac) { int tot = p.second; vector<vector<int>> dp(k + 1, vector<int>(tot + 1, 0)); dp[0][tot] = 1; for (int i = 0; i < k; i++) { for (int j = 0; j <= tot; j++) { int cur = mul(dp[i][j], inv(j + 1)); // cout<<"cur:"<<cur<<endl for (int t = 0; t <= j; t++) { add(dp[i+1][t],cur); } } } int sum = 0; int P = 1; for (int j = 0; j <= tot; j++) { add(sum,mul(P, dp[k][j])); P = mul(P, int(p.first % mod)); } // cout<<"sum:"<<sum<<endl; ans = mul(ans, sum); } cout << ans << endl; return 0; } |