Category Archives: 7. Programming

【C语言深入】陷阱:数组溢出导致内存被意外修改

C语言的指针在提供编程便利的同时,却带来了很多潜在的内存安全问题。见以下例子:

#include <stdio.h>

int main() {

	char string_buff[12];
	unsigned int i_not_zero = 0xFF;

	sprintf(string_buff, "Hello,world!");

	printf("i = %x\r\n", i_not_zero);

	return 0;
}

该程序(不正确)的输出为:

i = 0

上述代码使用sprintf修改了string_buff指针所指向的char型数组。但是由于在申明数组长度的时候,没有考虑到字符串结束符’\0’,所以实际写入时不慎篡改了下一位内存地址的内容(此例中为i_not_zero, 使用MinGW gcc)。在实际程序中,此类bug一般很难被发现,尤其是还有其他程序在正常修改该值时,一般先会去排查和该变量有关的程序。

这只是一个因为不慎所导致的内存溢出问题,而在一些极端的黑客代码中,经常会见到通过内存变量和函数的指针地址反向访问、修改堆栈,从而获得系统的权限。可见指针作为C语言的一个重要(但是晦涩的)组成部分,无形中降低了系统的可靠性和安全性,需要挑战programmer的debug能力。

【C语言深入】陷阱:数组指针作为函数参数返回

再来看一个指针问题,同样的来自一个本科生的代码。这段代码想要实现将一个全是小写字母的字符串转换成对应的大写字母字符串:

char *covert_to_upper_case(char *string) {
    char p[100];
    int i = 0;
    
    for(; i < strlen(string); i++ ) {
            p[i] = string[i] - ('a' - 'A'); 
    }
    p[i] = '\0';
    
    return p;
    
}

然而这段代码没有能实现期望的功能。原因如下:

  1. 主程序调用convert_to_upper_case()函数后,堆栈为p分配了内存空间;
  2. 函数体正确修改了p对应字符数组的内容,并将p的首地址作为指针返回;
  3. 函数返回后,所有临时变量从堆栈中弹出,包括p[100];
  4. 主程序得到返回的指针,对其进行解析。然而指针指向的字符数组此时已经从堆栈中弹出,解析后的数据无法被定义。

要想正确实现对应的功能,应该将目标指针作为额外参数传递给该函数,并由上层调用者提供内存空间的创建。当然也可以使用malloc()将内存分配在堆中,但是需要注意使用对应的free()释放空间,否则会有内存泄露的问题。

【C语言深入】指针的一个错误赋值

关于指针总是有说不完的故事。

最近给本科的学生带Embedded System课程设计,遇到了一个非常奇怪的bug。有一段代码需要实现I2C通信,核心代码已经由软件库提供了,学生只需要设置结构体后调用API即可。一个学生的代码是这样的:

struct I2C_CONFIG {
  // ...
  char *i2c_buff;
  int length;
  // ...
};

struct I2C_CONFIG cfg;
char *i2c_buff;

void I2C_init() 
{
  // ...
  cfg.buff = i2c_buff;
  cfg.length = sizeof(buff);
  // ...
}

void I2C_send(new_buff)
{
  // ...
  i2c_buff = new_buff;
  I2C_MasterTransferData(LPC_I2C1, cfg);
  // ...
}

初看一下没有什么问题:在I2C_init()函数中首先对结构体cfg进行初始化,而在I2C_send()函数中设置了需要发送的数据指针,之后使用I2C的API发送数据。

因为代码一直无法实现期望的功能,我又仔细看了一下其中的蹊跷。我注意到,这段代码中使用了一个中间变量:char *i2c_buff。在I2C_init()中虽然将cfg.buff指向了i2c_buff,但是因为cfg.buff本身也是指针变量,而非”指向指针的指针”,所以这里只实现了简单的按值传递,即将i2c_buff的值 (初始值为0) 赋给了cfg.buff。之后虽然在I2C_send()中修改了临时变量i2c_buff指向的位置,但却没有影响到cfg.buff中的内容,cfg.buff依然指向之前i2c_buff初始化时指向的内存地址,所以需要发送的缓冲指针new_buff其实并没有传递给之后的I2C_MasterTransferData()函数!为了解决这个问题,必须将更改后的i2c_buff的值再次赋给cfg.buff,即:

void I2C_send(new_buff)
{
  // ...
  i2c_buff = new_buff;
  cfg.buff = i2c_buff;
  I2C_MasterTransferData(LPC_I2C1, cfg);
  // ...
}

另外这段代码还有一个不容易注意的bug,就是在I2C_init()中使用了sizeof()来判断buffer的大小。因为sizeof()函数得到的只是数据类型的大小,所以对于指针char *i2c_buff来说,sizeof(i2c_buff) = 4,而不会返回buffer的实际大小。指针的大小并不等于指针指向缓冲的大小!

【C语言深入】C/C++变量命名规范

目前主流的C/C++命名风格有两种:一种是Windows风格的匈牙利命名法,主要是采用类型前缀 + 变量名首字母大写,另一个就是Unix/Linux命名习惯。我自己采用的是基于Unix的变种,融合了匈牙利命名法的一些优点,在这里分享给大家。

变量名的组成:(模块名) +  (作用域) + (类型前缀) + 变量名 + (变量名后缀),解释如下:

  • 变量名 以小写的英文字母构成,词与词之间用下划线连接,如key_value, data_src; 不可使用数字,不混用大小写;
  • 模块名 声明该变量属于的模块,防止模块与模块的命名冲突。如timer_prescalar_value, DMA_channel_name等;
  • 作用域前缀 (Scope Prefix) 标注变量的作用域,提高代码可读性:
    g_: 全局变量;
    n_: 局部变量;
    t_: 中间变量;
    s_: static静态变量;
  • 类型前缀 (Type Prefix) 指明变量的数据类型:
    ptr_: 指针变量,在程序中临时需要使用指针时,也常简写为p_,如*p_src;
    h_: 句柄,如h_file;
    n_: 整形,s_: 短整形,l_: 长整形, u_: 无符号整型,可增加数据位数,如u32;
    ch_: 字符型变量;
    f_: 浮点,d_: 双精度浮点;
    b_: boolean;
    by_: byte字节型(关注数据的位特性,需要位操作的情况下使用);
    reg_: 表示寄存器;
  • 后缀 (Suffix) 指明变量的性质:
    _src: 源,_dst: 目的;
    _str: 字符串;
    _t: 在声明数据类型时使用,表示为自定义的数据类型,如u32_t;
    _st: 表示为结构体;
    _buff: 数据缓冲, msg_buff;
    _arr, _a, _m: 数组或矩阵;

变量名的取名规则:

  • 循环控制变量 i, j, k, m, n,除循环控制外应避免使用这些变量名称;
  • 函数名 使用(模块名 + )动词 + 名词的形式,同样小写 + 下划线:sys_find_file(), IO_get_data(). 后者因为IO为专用名词故破例使用大写;
  • 类名或结构体名 使用首字母大写加下划线连接:如Mystring, Datetime_type;
  • 私有类成员 Private使用下划线_前缀,如_data_src_ptr, _init_module();
  • 宏定义或常量 使用全部大写:如MAX_NUMBER, LOOP_NUMBER;
  • 缩写 使用能广泛接受的缩写:如add, ans, avg, chk, cnt, col, ctrl, def, del, dst, disp, err, freq, idx, init, len, min, max, mid, msg, num, opt, pos, ptr, recv, res, ret, src, str, sub, num, ts (timestamp), val等。

本网站的所有实例代码和项目程序都将按此命名规范进行编写。

【C语言深入】C语言的函数指针

函数指针是C语言指针中的一个分支:函数指针是指向函数地址的指针。和一般的指针一样,函数指针可以大大增强编程时的灵活性。这篇博文根据我的理解,简单介绍了自己对于函数指针的理解。

一、函数名的本质

在介绍函数指针之前,我们先来理解一下究竟什么是函数。以下一段代码定义了名为fun1(),接受int并返回int参数的函数:

int fun1(int x) {	// fun1是函数名
	return x + 1;	// 函数体
}

从一般的理解角度来看,fun1是函数的函数名。之所以要定义函数名,是因为在程序的其他位置要调用该函数时,可以直接使用这个别名。这种使用别名的方法和变量相似,但又不完全一样。对一个变量x而言,其意义如下:

物理地址 数值  说明
0x20000000        30 <– x是该数值单元的别名

x是内存单元0x20000000所对应的内存单元。此处x = 30,而x的地址&x = 0x20000000.

那么对一个函数而言,函数名又代表什么呢?假设之前的fun1函数在编译后被放置在0x08000200地址,则fun1对应的内存结构如下所示:

物理地址 数值 说明
fun1 (0x08000200) fun1_entry <– fun1是函数的入口地址

在这里,函数名代表一个记录了函数入口地址的存储单元的物理地址。可见,函数名的本质是地址。在编译阶段,函数名被转化成为对应的地址。在使用 xxxx() 函数调用的语法时,该地址被载入程序计数器PC,函数参数及当前现场被弹入堆栈。最后进行函数的实际跳转和执行。

二、函数指针是什么

对于一般变量而言,指针可以指向变量的地址,并修改变量的内容:

物理地址 数值  说明
0x20000000         30 <– x是整形变量
0x20000004  0x20000000 <– p是指向x的指针

这里p是指向x的指针,(即p = &x)。此时p的内存单元所存储的是x单元的物理地址,通过 *p 解析地址之后就可以访问或修改x单元的内容。同样的,函数也有其对应的指针 – 函数指针。函数指针是一种特殊的指针,其指向的对象不是变量而是函数。函数指针指向目标函数的入口地址(首地址)。这里我们定义一个指向fun1函数的函数指针pf:

int fun1(int);		// fun1是一个(含int输入参数和int返回参数的)函数
int (*pf)(int);		// pf是(指向返回int型,含int参数函数的)函数指针
pf = &fun1;

/* 也可以直接写成: */
int (*pf)(int) = &fun1;

/* 如果需要调用函数指针对应的函数,可以写为:*/
(*pf)();		// 等价于fun1()

到这里,我们回顾上一节中说到的函数名。其实函数名也可以理解成为const型的函数指针。所以在c语言中,以下调用也是合法的:

(*fun1)()		// 等价于fun1()
pf = fun1		// 等价于pf = &fun1;
/* 但是fun1的值不能被修改 */
fun1 = fun2		// 错误!fun1是const类型的指针

函数指针的声明较为冗长,如果需要定义多个同类型的函数指针。可以通过typedef定义一个函数指针类型,从而进行简化:

typedef int (*PF)(int); // 声明PF是一个函数指针类型
PF pf1 = fun1;
PF pf2 = fun2;

三、函数指针的应用场景

以上说明了如何定义函数指针,下面介绍函数指针的应用场景。函数指针最常见的应用还是作为回调函数的参数。一般在事件驱动的程序框架中,当对应事件发生时,需要触发对应的处理函数。以下代码实现了在初始化阶段,将事件与对应的处理函数关联(假设set_event_callback()是实现该功能的系统函数):

typedef int (*CALLBACK)(int);

#define EVENT_1		(0x01)
#define EVENT_2		(0x02)

int set_event_callback(const int e, CALLBACK);

void init_callbacks() {
	CALLBACK pf1, pf2;
	set_event_callback(EVENT_1, pf1);
	set_event_callback(EVENT_2, pf2);
}

在set_event_callback中,函数指针pf作为参数传递给函数使用。在基于事件编程的框架中(如一般的GUI库),函数指针经常以作为回调函数的方式出现。函数指针的另一个应用就是,根据当前程序进程的不同,要在不同条件下调用不同的处理函数:

void change_function(int nEvent, PF *ppf) {

	switch (nEvent) {
		case 0: 
			*ppf = fun1;
			break;
		case 1: 
			*ppf = fun2;
			break;
		default:
			*ppf = fun3;
	}
}

这里利用了函数指针指向的函数是可以改变的(而非函数名是const型的)。change_function() 将函数指针的地址(指向函数指针的指针)作为参数传入,并根据当前nEvent的情况更改原函数指针指向的函数。

函数指针的另一个应用场景,是允许程序在只知道函数物理地址(但不知道具体的函数名)的情况下进行函数跳转。相信大家都还记得这个经典的C语言面试题:

(*(void(*)(void))0)();
// 或
((void(*)(void))0)();

此语句的本质就是将0内存位置强制转换成为了函数指针,并调用了该函数指针指向的函数。以下代码解释了此处是如何将0地址转换成函数指针的:

typedef void (*PF)(void);

// (*(void(*)(void))0)() 等价于
(*(PF)0)()
// 或
((PF)0)()

函数指针的更高级用法就是组成函数指针数组,或和指向函数指针的指针配合使用。在此不再继续介绍,感兴趣的读者可自行研究。

参考资料

[1] Kenneth A.Reek, C和指针(第二版), 2008, 人民邮电出版社

[2] Brian W. Kernighan / Dennis M. Ritchie, The C Programming Language (Second Edition), 1989, Prentice Hall

[3] C语言中文网,C语言函数名与函数指针详解http://c.biancheng.net/cpp/html/496.html

Processing | 用递归创造复杂图形

在Processing中想要创作复杂的图形元素,除了可以使用循环结构外,还可以使用递归 (recursion) 。递归是一种在函数执行时调用自身的一种特殊设计方法,递归可以解决很多循环结构无法解决的问题,同时在代码实现上也极为简洁。

为了可以更直观的了解什么是递归,这里先给出一个例子:

// Recursive Circle
// YunFei
void setup() {
  size(420, 420);
  drawCircle(400);
}

void draw() {
  noLoop();
}

void drawCircle(float radius) {

  if (radius < 10) {
    return;
  }

  ellipse(width/2, height/2, radius, radius);

  drawCircle(radius - 20);
}

该代码生成的图形如下:
20150312224944

在上例中,drawCircle() 函数在返回前再次调用了drawCircle(),同时半径参数减小了20。所以drawCircle(400)会调用drawCircle(380),drawCircle(380)绘制完毕后又会调用drawCircle(360),… …,直到drawCircle(20)调用drawCircle(0)。此时,因为radius小于给定的容限(radius < 10),drawCircle(0)直接执行了return语句返回了该函数,从而不会再继续调用drawCircle(-20)。随着drawCircle(0)的返回,其余函数也逐级返回,直到所有嵌套的函数完全结束。

递归虽然相比循环在代码上更为简洁,但是设计难度却大于循环结构。设计递归时有两个注意点:
1)是程序的规模要不断减小 (此处每次radius – 20),否则程序会陷入死循环无法退出;
2)有一个合适的中止条件 (此处为radius < 10),一般来说小于某个容限值比等于某个极限值更为可靠。

下面以一个更复杂的例子,树型分形,来展现递归的美妙(代码修改于Daniel Shiffman, The Nature of Code):

// Recursive Tree
// YunFei
void setup() {
  size(500, 500);
  background(255);
  translate(width/2, height);
  stroke(0);
  drawBranch(150);
}

void draw() {
  noLoop();
}

void drawBranch(float len) {
  float theta = PI/6;

  strokeWeight(2);
  line(0, 0, 0, -len);

  translate(0, -len);

  len *= 0.66;

  if (len > 10) {
    pushMatrix();
    rotate(theta);
    drawBranch(len);
    popMatrix();    

    pushMatrix();
    rotate(-theta);
    drawBranch(len);
    popMatrix();
  }
}

实现的效果如下:
20150312232827

以上分形图形随着枝的逐层生长,分支的数量呈指数倍、而非线性增长,循环结构无法解决该问题。可见,灵活使用递归可以创造更为复杂的图形元素。实际上,递归更多情况下被用于求解数学问题,如最为经典的牛顿迭代法求解方程,就可以使用递归函数来计算。

Processing | The Tree of Mind

九月底我的硕士课程就正式开始了,学业一直比较繁忙,没有精力进行新的研究。近日略有饶兴,抽空重新温习了一下Processing,下一步准备用Processing和Kinect完成一些交互艺术设计。

这个作品历时两天,用了800个粒子做随机运动动态生成。粒子的运动规律是由固定的方向矢量和柏林随机噪声叠加而成的。固定的方向矢量是为了能在自由运动的同时,保证运动的大体角度,从而从总体上呈现出绽放的效果;而之所以选用柏林噪声是因为这种随机运动更加自然,不会产生位置上的突变和跳动。

processing_mindtree

Revision History >>

04/19/2016    因为视频时间较短,将视频做成了gif,方便预览。

关于编程语言的选择与体会

从我最早接触编程至今已有近10年时间,当时是在初中时,通过文曲星编写了几款基于文字和简单图形的游戏。高中时因没有相关条件与指导,慢慢就荒废了下来,中途曾经因为计算机考试学过一段时间VB,但就当时的知识能力,并没有学习的很深入。上大学以后,学校开设了C语言和VB的相关课程,加之之后对单片机和嵌入式系统的狂热,让我更加深入的接触了计算机编程的原则与方法。

我虽然不是计算机专业出生,但在学习、工作中还是经常会接触到程序编程。我主要使用的依然是C语言,但是因为涉猎较广,还是接触了很多其他的编程语言。这里,我想把所有使用过的编程语言的优缺点罗列、整理一下,作为一次回顾。

BASIC:较为古老的编程语言,开发环境是基于命令行的,条件、跳转很不方便,现在已经很难见到。

VB:可视化BASIC,在BASIC上作了大量拓展,可以快速构建一个图形用户界面,但是能实现的功能比较简单。在工控上经常能见到,老工程师都会。

C:C语言作为基础性语言,广泛用于单片机与Linux编程中,其直接操作内存和硬件的特性,使其非常适合编写系统底层程序。C语言可以很好的完成单一任务,如一个算法的验证,但无法完成框架复杂性高、以及需要图形界面的场合。

C++:面向对象,结构化的语言,相比C语言可以实现更加清晰的程序框架。一般使用Visual C++作为开发环境,配合MFC程序框架可以实现功能复杂、通用性好的Windows程序。网上很多源代码都是基于VC的,但是其开发效率有点低下,并且实现复杂的图形界面比较困难。

C#:新一代的编程语言,结合了C++的面向对象以及VB的可视化开发的优点,又可以说是一种类JAVA语言。C#的开发效率高,图形绘制,数据库的功能强大,但目前对我来说的阻碍是很多开源软件对其的支持还不够,就如Win7一样兼容性还不够,随着时间的推移这个矛盾应该会逐步化解,我也准备逐步由C++转向C#开发。

Java:我接触Java并不多,初步感觉其对象化实现的很好。Java之所以生命力顽强,是因为其基于虚拟机的特性。虽然这降低了系统的运行效率,但是却实现了跨平台支持。目前由于Android开发的火热,很多人都在从事Java开发,我最近也有打算了解一下Android开发,届时也可以更深入的了解Java语言。

Lua:强大的脚本语言,初步体验了一下,感觉其扩展性、灵活性非常好,但是脚本语言与一般编程语言在设计思路上有一些不同,对我来说有一些难用。

Shell:Linux下的脚本语言,可以实现BATCH批量操作,甚至很多复杂的程序也可以通过Shell实现。

Matlab:擅长矩阵运算,建模能力强大,主要实现算法验证。但不适合用于设计大型程序,与一些上位机有接口,其作为一个组件使用可能更合适。

Python (修订于: 2017-05-12):目前最主流的科学计算脚本语言。相对MATLAB,Python有强大的开源社区支持,通过NumPy + SciPy + Matplotlib可以实现近似Matlab的科学运算编程。而DeepLearning的相关库 (TensorFlow, Theano, Keras) 也都有Python的对应版本。

【C语言深入】陷阱:一个Break在if语句中的误用

C语言以高效著称,但其也存在很多晦涩的语法。让我们来看下面这段(真实的)代码:

switch (cmd) {
	case 0: break;
	case 1:
		if (bReceived == 1) {
			if (bNotReady == 0) {
				break; // 此处的break有误
			}
			do_something();
		}
		// 本意是满足条件跳出if, 不执行do_something()
		do_otherthing();
		break;
	default:
		break;
}// 却意外地跳出了switch, 从而没有执行do_otherthing()

以上代码的break意外跳出了case语句。之所以会产生这样的错误,是因为break在for和while中有类似的应用。我的这位朋友是在没有意识的情况下写出了上面这段代码。不仅如此,编译器(甚至高级的排错工具)对此也不会产生疑问,因为break在case语句之中是可以合法存在的。这里我用VS 2010测试了一下,如果该语句不在case语句下,编译器会提示break用法错误。

该错误可以通过将if的逻辑反转来解决:

switch (cmd) {
	case 0: break;
	case 1:
		if (bReceived == 1) {
			// 如果bNotReady == 0,将不执行do_something()
			if (bNotReady != 0) {
				do_something();
			}
		}
		do_otherthing();
		break;
	default:
		break;
}

 

【修订历史】

2015/12/02: V1.1 增加了对原代码的分析说明,增加了修改后的代码。

【C语言深入】陷阱:一个优先级导致的BUG

虽然我在工作中已经非常注意优先级的问题,可还是不小心犯了一个优先级导致的错误:

while (USART1->SR & USART_SR_RXNE == 0);

这句话的本意是等待SR寄存器的某位变为1才继续往下执行,而实际上,因为”==”的优先级大于”&”,这句话等同于:

while (USART1->SR & (USART_SR_RXNE == 0));
//而 (USART_SR_RXNE == 0) 一直不成立,从而这句话等价于:
while (USART1->SR & 0);

即 while (0); 所以每次执行到该句话时,不管当前SR寄存器的内容是什么,都会直接跳过while。为了防止出现优先级错误,正确的写法应该是:

while ((USART1->SR & USART_SR_RXNE) == 0);

与此类似的错误还有:

nValue = nByte << 3 + 8;

这句语句的本意是将nByte左移3位后的值加上8赋给nValue,然而实际上因为算术运算符”+”的优先级大于以为运算符”<<“,于是这句话变为:

nValue = nByte << (3 + 8);

// 即
nValue = nByte << 11;

可见优先级关系在这里导致了完全错误的结果。