111qqz的小窝

老年咸鱼冲锋!

【施工完成】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个涉及浮点数的问题之后补。

 

补上三个涉及浮点数的问题…比较无聊,按照IEEE754操作即可.

 

 

 

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的代码,用于调试。

 

吐槽下hahide的文档…各种函数全靠试…

试了好久得到的,opencv Mat转halide::buffer的办法:

 

可能会报错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()

 

 

 

【施工完毕】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.

READ MORE →

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

如果想研究c语言中变长参数的具体实现,可以参考 也谈C语言变长参数

参考资料:

Variable numbers of arguments