程序代码

程序代码（共9篇）

程序代码 篇1

0 引 言

高性能并行计算是现代科学研究、工程技术开发和大规模数据处理的关键技术,而并行编译系统是并行计算机系统软件中十分重要的一部分,提高并行编译技术对充分利用并行机资源和提高并行机效率起着十分重要的作用。

并行编译器包括前端处理和后端处理两部分:前端处理主要包括逻辑上的并行识别、计算和数据划分、依赖关系识别;后端处理主要是并行代码的自动生成,代码生成的关键在于如何高效地生成同步通信代码。

并行程序中的通信主要由四部分组成:数据初始分布通信、计算前的数据准备通信、计算过程中的同步通信以及数据收集通信。初始数据分布通信是在进行数据的初始分布过程中引起的通信。由于初始分布中数据划分和计算划分不能做到完全对齐所引起的通信称之为数据准备通信。同步通信是在进行并行计算过程中产生的通信。数据收集通信是所有进程计算结束后,主进程把所有进程的计算结果收集起来得到程序的最终执行结果时所引起的通信。本文重点讨论计算中的同步通信问题。

在文献[1]中对代码生成和通信优化做了介绍,但对具体如何实现没有讨论,本文则提出利用命名的线性不等式系统来表示数组数据空间、循环迭代空间、虚拟处理器空间和物理处理器空间,并建立了它们之间的内联关系,在此基础上给出了同步通信代码的自动生成算法。

1 计算划分

在分布式存储的大型计算机中,循环级的并行性一般是通过对循环嵌套迭代空间进行计算划分并将循环迭代分布到多个进程同时执行来实现的。下面给出与计算划分相关的定义。

定义1 迭代空间 迭代空间I表示一个循环边界是循环索引的线性函数且深度为m的循环嵌套,该空间是一个m维多面体。循环嵌套的每个迭代对应多面体中的一个整数点,即一次计算操作,用索引向量undefined表示。

定义2 处理器空间P 处理器空间P表示一个n维的处理器数组。

定义3 计算划分[4]C 计算划分undefined是满足特定关系的迭代和处理器对undefined的集合,处理器undefined执行迭代undefined当且仅当undefined。其中U是一个扩展的幺模矩阵,undefined是整数向量,B是整数矩阵,undefined是符号向量,undefined。

在计算划分C中,U指示计算划分是对迭代空间的哪些维进行划分以及是正分还是斜分;undefined给出分块的大小;undefined是偏移的大小。计算划分在代码生成的前一遍自动生成。

2 读写依赖关系与LWT树

计算中的同步通信由读写依赖关系和计算划分共同确定,对依赖关系有如下定义。

定义4[5] 嵌套循环L中的语句T的一个实例T(j)和语句S的一个实例S(i),如果存在一个存储单元M满足下述条件,则称语句T的实例T(j)依赖于语句S的实例S(i):

(1) S(i)和T(j)都引用(读或写)M;

(2) 在程序串行执行时,S(i)在T(j)之前执行;

(3)在程序串行执行时,从S(i)执行结束到T(j)开始执行前,没有其他实例对M进行写操作。

一对语句实例可以用4种不同的方式引用相同的存储单元,因此有4种类型的依赖关系:

① 如果S(i)写M而T(j)读M,则T(j)流依赖于S(i);

② 如果S(i)读M而T(j)写M,则T(j)反依赖于S(i);

③ 如果S(i)写M而T(j)也写M,则T(j)输出依赖于S(i);

④ 如果S(i)读M而T(j)也读M,则T(j)输入依赖于S(i)。

在这4种依赖关系中,④不会影响程序的并行化,不会引起通信,②和③的依赖关系是可以消除的,也不会引起通信,只有①需要通信,本文中的同步通信即指由流依赖所引起的通信。

在进行依赖关系分析时,用LWT树来表示数据之间的读写关系,每对读写对对应一棵LWT树。LWT树是一棵二叉树,表示精确的数据流信息,是描述从读操作实例到提供该读操作所读数据的最后一次写操作实例的映射关系。若读、写分别用循环索引undefined和undefined表示,则该函数的定义域是所有满足循环边界限制的undefined的集合。LWT树包括根节点、叶节点和内节点,内节点是对读undefined进一步的限制,叶节点又分为⊥节点和非⊥节点,表示了不同的依赖关系。

LWT[3]树把循环嵌套划分为以其每个叶节点的内容(contexts)ι为元素的集合,undefined。如果一个contextι∈I中迭代所读的值是在循环中产生的,则存在最后写关系undefined,且读迭代undefined所读值在写迭代undefined中产生},其中undefined和undefined是线性函数。

对给定的读迭代,从LWT知道一个写迭代undefined修改了undefined所读的数据且undefined是修改该数据的最后一个写操作,因此可以定义一个写迭代和读迭代之间的函数来表示undefined到undefined之间的关系,记为L,这样就可以通过LWT计算出两次引用之间的数据流依赖向量。

定义5 最后写关系LasarLasar是从读数组访问undefined和读迭代undefined到写数组访问undefined和写迭代undefined的映射,undefined当且仅当undefined;undefined;undefined;undefined且undefined使得undefined;undefined;undefined,其中undefined和undefined是读写访问函数。

由定义5知道,如果写迭代undefined和读迭代undefined都访问同一数组元素undefined之前执行,而且在undefined之间不存在其他迭代修改数组元素undefined则undefined之间存在最后写关系。

通过建立LWT树的方法可以将依赖关系精确到具体数值,这就为各进程之间的通信提供了关键依据。依赖关系分析是在代码生成的前一遍自动生成的。

3计算代码和计算中同步通信代码的自动生成

在并行程序代码自动生成中将涉及到多个多维整数空间,包括数组数据空间、循环迭代空间、虚拟处理器空间和物理处理器空间等。定义1和定义2分别给出了循环迭代空间和处理器空间的定义,下面给出数据空间的定义:

定义6 一个m维的数组A[n0][n1]…[nm-1],li≤ni≤ui,0≤i≤m-1,定义了一个m维的数据空间,该空间每一维的上下界即是数组每一维的上下界li和ui。

用命名的符号系数不等式系统统一表示这些空间,该不等式系统由多个不等式组成,每个不等式表示一种变量之间的关系,每个变量表示的即是空间的某一维。变量的所有可能的整数解的集合用n维离散的笛卡尔空间表示(n是变量数),所有满足该不等式系统的解都与笛卡尔空间中的一个整数点相对应。

计算代码和同步通信代码的自动生成过程分三部分:生成数据的接收和解包代码、生成计算代码、生成数据打包和发送代码。自动代码生成的关键是在程序的什么地方插入何种方式的通信代码?首先判断是否需要进行同步通信,如果LWT树中读的数据不在当前进程则需要通信,且利用计算划分来确定应该与哪个进程进行通信。

定理1 计算划分C满足最后写关系μ的通信集是undefined的集合,其中,undefined。

定理1所处理的是LWT树中的非⊥节点,根据LWT提供的读写依赖关系和读写变量所在

迭代的取值范围以及计算划分来判断两个迭代之间是否需要进行通信,见图1[1]。从图中可以看出,读/写迭代通过计算划分C分布到不同的进程pr和ps,两者之间通过LWT树联系在一起,若undefined则需要通信。

对于每一个物理进程mypid,通过以下算法判断是否需要发送数据给其他进程。

算法输入:计算划分C、依赖关系LWT、处理器空间P、迭代空间I

算法输出:并行同步通信代码和计算代码

算法描述:

(1) 建立虚拟拓扑结构把当前进程的标识mypid转换为多维坐标表示的pids;

(2) 通过计算划分和循环迭代范围得到参与计算的进程范围Pe;

(3) 如果pids∉Pe则不需要通信,否则;

(4) 根据计算划分C得到pids的迭代范围is;

(5) 根据LWT树中非⊥节点提供的读写依赖关系信息得到与is对应的ir;

(6) 依据ir和计算划分C得到ir所在的进程pidr;

(7) 比较pidr和pids是否是同一进程,如果二者相同则不需要同步通信,否则;

(8) 产生同步发送代码:打包数据并发送给pidr。

相应的,进程也需要判断是否需要接收其他进程发送来的数据:

(9) 通过建立的虚拟拓扑结构把当前进程的标识mypid转换为多维坐标表示的pidr;

(10) 通过计算划分和循环迭代范围得到参与计算的进程范围Pe;

(11) 如果pidr∉Pe则不需要通信,否则;

(12) 根据计算划分C得到pidr的迭代范围ir;

(13) 根据LWT树中非⊥节点提供的读写依赖关系信息计算出ir对应的is;

(14) 依据is和计算划分C得到is所在的进程pids;

(15) 比较pidr和pids是否是同一进程,如果二者相同则不需要同步通信,否则;

(16) 产生同步接收代码:接收pids发送来的数据并解包数据。

最后生成计算代码,根据上一遍提供的计算划分C和循环迭代I的边界信息计算出执行计算的进程范围,再依据分块执行的原理把计算分布到各进程执行。

4 实例分析

以下例来说明上面的算法:

例1 for(i=0;i<=N-1;i++)

for(j=i;j<=N-1;j++)

for(k=N-1;k>=i;k--)

a[j][k][i]=a[j][k][i]+a[i][k][j]*a[j][i][k]/a[i][j][k];

该例计算划分C:pid0=-k,pid1=i;迭代空间I:0≤i≤N-1;i≤j≤N-1;i≤k≤N-1,LWT树见图2。从图中可以知道数组引用a[j][k][i]和a[i][j][k]之间存在读写依赖关系,其依赖关系为:ks=-jr;js=ir;is=kr。

设N=4,则由计算划分C和迭代空间I可以计算出虚拟处理器空间P为-3≤pid0≤0,0≤pid1≤3。在生成同步通信代码时,首先判断是否需要进行通信,如果需要通信则产生同步通信代码。以pidr0=-2,pidr1=1为例来说明,根据计算划分C知道ir=1;kr=2;ir≤jr≤3,进而根据LWT树提供的读写依赖关系得到is=2;js=1;-3≤ks≤-1。得到写迭代之后,再根据计算划分C就可以找到该写迭代所在的进程为-3≤pids0≤-1,pids1=2。最后比较pids和pidr是否是同一进程,不是则产生两个进程之间的同步通信代码。此例pidr≠pids,则两个进程之间需要通信,进程pids产生同步发送代码,进程pidr产生同步接收代码。

5 总结与展望

本文主要讨论串行程序并行化中涉及到的计算代码和计算中同步通信代码的自动生成。文中所介绍的算法已在SUIF编译架构上实现,并利用ppopp benchmark程序集进行了验证,实验结果表明该算法能够正确生成计算代码和同步通信代码,但在该算法中未对同步通信的优化进行处理。下一步将主要研究计算中同步通信的优化问题,如多维并行条件下的计算和通信的重叠等。

摘要：简要介绍了并行编译中的计算划分和依赖关系分析,提出如何利用计算划分和依赖关系自动生成并行程序中的计算代码和同步通信代码。

关键词：计算划分,依赖关系,最后写树,同步通信

参考文献

[1]Amarasinghe S P,Lam M S.Communication optimization and CodeGeneration for distributed memory machines.In the Proceedings of TheACMSIGPLAN′93 Conference on Programming Language Design andImplementation,Albuquerque,New Mexico,June,1993:126-138.

[2]Ferner G S.The Paraguin compiler Message-passing code generation u-sing SUIF.In the Proceedings of the IEEE SoutheastCon 2002,Colum-bia,SC,April 5-7,2002:1-6.

[3]Maydan D E,Amarasinghe S P,LamMS.Array data-_flowanalysis andits use in array privatization.In the Proceedings of ACMSIGP-LAN-SI-GACTSymposium on Principles of Programming Languages.Charles-ton,South Carolina,January 10-13,1993:2-15.

[4]Anderson J M,Lam M S.Global Optimizations for Parallelism and Lo-cality on Scalable Parallel Machines.In Proceedings of the SIGPLAN′93 Conference on Program Language Design and Implementation,June1993.

[5]沈志宇,胡子昂,廖湘科,等.并行编译方法[M].北京:国防工业出版社,2000.

程序代码 篇2

1、顺序查找

int search(ET v[], int n , ET x){ int k=0;while(k

2、二分法查找

int bsearch(ET v[] , int n, ET x){ int i, j, k;while(i<=j){ k=(i+j)/2;if(x==v[k])return k;if(x

3、分块查找

struct indnode { int key;int k;};int insearch(ET v[], struct indnode s[], int n, int m, ET x){ int i, j, t;i=0;j=m-1;while(i<=j){ t=(i+j)/2;

if(x<=s[t].key)j=t-1;

else if(x>s[t].key)i=t+1;} if(it)j=-1;return(j);}

二、排序

1、双向冒泡

void bubsort(ET p[], int n)

{ int m, k, j, i;ET d;

k=0;m=n-1;

while(k

if(p[i]>p[i+1])

{ d=p[i];p[i]=p[i+1];p[i+1]=d;m=i;} j=k+1;k=0;for(i=m;i>=j;i--)

if(p[i-1]>p[i])

{ d=p[i];p[i]=p[i+1];p[i+1]=d;k=i;} } }

2、快速排序1 void qksort(ET p[], int m, int n){ int i;if(n>m)

{ i=split(p, m, n);

qksort(p, m, i-1);qksort(p, i+1, n);}

return;} static int split(ET p[], int m , int n){ int I, j, k, u;ET t;i=m-1;j=n-1;k=(i+j)/2;if(p[i]>=p[j]&&p[j]>=p[k])u=j;else if(p[i]>=p[k]&&p[k]>=p[j])u=k;else u=i;t=p[u];p[u]=p[i];while(i!=j){ while(i=t)j=j-1;if(i

while(i

if(i

3、快速排序2 void quicksort(int p[],int left,int right){

int i, j, t;

i=left;j=right;t=p[i];

while(i

{

}

p[i]=t;

outtable(p);

if(left

if(j

4、直接插入排序

void insort(ET p[], int n)

{ int j, k;ET t;

for(j=1;j

{ t=p[j];

k=j-1;

while(k>=0 && p[k]>t)

{ p[k+1]=p[k];k=k-1;}

p[k+1]=t;} }

5、希尔排序

void shlsort(ET p[], int n){ int h, j, k;ET t;

h=h/2;

while(h>0)

{ for(j=h;j<=n-1;j++)

{ t=p[j];

k=j-h;

while(k>=0 && p[k]>t)

{ p[k+h]=p[k];k=k-h;}

p[k+h]=t;} h=h/2;} }

6、选择排序

void select(ET p[], int n){ int i, j, k;ET d;for(i=0;it))j--;if(i

p[i]=p[j];i++;

} while((i

} for(j=i+1;j7、堆排序

void heap(ET p[], int n){ int i, k;ET t;

k=n/2;

for(i=k-1;i>=0;i--)sift(p, n-1, i);

for(i=n-1;i>=1;i--)

{ t=p[0];p[0]=p[i];p[i]=t;

sift(p, i-1, 0);

}

return;}

static sift(ET A[], int n, int m)

{ int j;ET t;

t=h[m];j=2*(m+1)-1;while(j<=n){ if(j

程序代码转换技术的研究与实现 篇3

代码抄袭是程序设计课程中经常出现的一种行为,针对这种情况,一些机构开始对程序代码抄袭检测技术进行了研究。目前程序代码抄袭检测技术可由两部分组成:第一部分,对程序代码进行形式的转换,即程序代码转换技术。第二部分,对转换后的形式利用相似度算法进行比较并计算相似度。

程序代码转换技术是指把一个程序看成一个文本串,再通过一定的文法分析将这个文本串转换成描述程序基本信息的标记串。对程序相似性的比较则就变成比较两个程序串的相似性。目前,已存在多个较有效的抄袭检测系统,如:Jplag,MOSS,YAP等等,这些系统多数是先对程序代码进行转换,将程序转换成标记串序列,最后再进行相似度计算从而判别其相似程度。但这些系统对如何把程序代码进行转换并没有详细的介绍因此本文针对这种情况设计了一个实验系统来实现程序代码转换技术。

2、程序代码转换技术的实现

2.1 程序代码预处理

首先要对程序代码做预处理。预处理是指去掉那些在程序中存在,但对程序无影响的信息,如程序中的注释语句、连续的空格、空行等,这样可以减小程序代码的长度,也可使程序在转换后的字符串标志的长度减少,从而减少计算相似度所用的时间。

2.2 词表

程序代码转换是以建立词表为基础的,程序代码中的词表指程序语言中的关键字、标识符、操作符等关键信息加入到转换词表。本文以C语言的程序为例,以TXT文本数据的形式存储到词表中,C语言中的关键字、标识符、操作符等关键信息如赋值运算符表算术运算符表:+,-,*,/,%,++,--;关键字表:auto,break,case,char,do,else等;预定义标识符表:alloc.h,assert.h,bios.h,dir.h等。所使用的词条多数由自己整理、修改后成形,因此可以根据不同的程序语言随时添加、删除、修改词表里的词。

词表规则描述如下:将词表中的词条的按照英文字母表的排列顺序进行排序,每行只能有一个关键词条和一个对应的转换标志串。运算符表示为“运算符相应的英文大写”如“+”定义为PLUS。关键字、预定义符表示为“关键字的开头第一个大写字母开头+阿拉伯数字”,遇到开头大写字母重复,就将后面的数字以字母顺序逐步加1以示区分。如auto定义为A1;break定义为B1;case定义为C1,char定义为C2等等。

2.3 KR串匹配算法

本文运用字符串匹配算法中的KR字符串精确匹配算法来对预处理后的程序代码与词表中的词条进行匹配,若完全匹配则将其转换成相应的标志。

该算法的基本思想是把长度为m的模式串按照某个函数计算得到一个对应的散列值,这个函数叫做散列函数(或者称作指印函数)。把文本串中每长度为m的子串也按照这个函数计算得到一个对应的散列值。则只有那些与模式串具有相同散列值的文本子串才有可能与模式串匹配。如果文本子串的散列值与模式串的散列值不相同的话,那么该文本子串与模式串一定不匹配。

2.4 系统界面

实验系统的主界面如图1所示。在该界面中,用户只需将要转换的源程序代码拷贝到“源程序”的窗口中,点击“转换”按钮,就会在“转换结果”窗口中显示出源程序转换后的字符串形式。

3、实验及结果

由于学生的程序作业有一定的特点:简单,代码不长,解题算法较单一。因此本实验以学生的C语言程序作业为实验数据,任意选取30份程序作业,使用已有的Jplag系统从相似度的度量结果对本实验进行了测试。首先将30份学生作业通过本实验系统转换成字符串标志后由Jplag系统测试,得到的程序代码相似度度量值如图2。

其次将相同的学生作业直接由Jplag系统测试,其相似度度量值如图3。

由统计结果分布图显示,两种方式下的相似度度量的结果是相同的。可知本试验系统转换输出的字符串标志结果是可行的。而且,就相似度计算的准确度来看与未经转换的结果相同。

4、结论

本文参考了现有的程序相似度判别系统的相关技术,对利用字符串匹配算法来实现程序代码分词转换技术进行了研究。并通过一个实验系统实现了将程序代码转换成标志串的功能。此外,若对实验系统中的词表进行更换,该实验系统就可用于其他的转换情况,如中英文转换等等。

摘要：程序代码转换技术是程序代码抄袭检测技术中的一个重要部分。程序代码转换技术就是把一个程序看作一个文本串,然后再通过一定的文法分析将这个文本串转换成描述程序基本信息的标记串的过程。目前已有多个较有效的抄袭检测系统,如:Jplag,MOSS,YAP等等,但是这些系统中对如何把程序代码进行转换成串的,并没有详细的介绍。本文针对这种情况设计了一个实验系统来实现程序代码转换技术,并进行了验证。

关键词：程序代码转换技术,程序代码抄袭检测技术,词表,字符串匹配算法

参考文献

[1]Herbert Schildt著.戴健鹏译.C语言大全(第二版)[M].北京:清华大学出版社,1994.

程序员善待你的代码 篇4

作为一个好的程序员必须有以下的习惯，以及对待自己代码象孩子，老婆一样，我们要爱惜我们的代码，同时也要让代码走正确的路。毫无疑问，程序员是善于思考问题的一族。一个程序的编写都是通过：思考、设计、编写、调试、测试以及运行这些基本的阶段。但大部分程序员都有一个问题就是不太愿意测试自己的代码。他们草草的调式完成以后就认为工作结束，测试那是测试人员的工作。按照理论上，如果代码存在问题，那么测试人员和最终的用户肯定可以发现这些 BUG，而等待哪个时候再返回来查找问题到底错在什么地方确实代价不小，其代价有： 1． 影响了程序员自己的声誉 2． 影响了产品的质量 3． 影响了客户的信任度

4． 这个时候再 DEBUG 难度增大了许多。

大的不说，就说多自己声誉的影响吧。如果你的程序总会有这样那样的 BUG，你得到收益会减少，即使你写了很多代码。其实最后一点也很重要；在我们面对一块代码的时候，什么方法都好办，但如果将这块代码防到庞大的系统中之后，简单的问题也难以被立即找出来。为了自己考虑，节省自己 DEBUG 的时候，我们应该让我们的程序尽量没有 BUG。

那么怎么样才能保证自己的代码没有 BUG 来？ 程序员必须克服一些自身的致命缺点才能够从根本上解决这个问题。那么这个问题是什么？前面我们已经提到，程序员对自己的代码都非常宽容，认为那是正确的没有问题。实际上这种想法比较正常，程序是通过程序员思考和设计之后才写出来，程序员不会将自己认为不正确的东西写到代码里，而到这个时候都一直假设程序是正确的；但人非圣贤，怎么可能不犯错误来。实际上程序员在对待其他程序员时候的态度就很好，带着一种挑剔和学习的态度；但一旦对待自己的代码就很难这么做；这就是最致命的。程序员也必须对自己的代码带着挑剔和学习的态度；这个基础是假设自己的代码是错误的，然后需要做的是怎么样证明自己的代码是正确的。程序员自身可以在程序生成的每个阶段做这些工作：仔细的设计（这个时候画点时间是值得的，必须保证我们对自己的程序有清晰的轮廓后才能开始动手写）、编写代码时、单元测试（单元测试的重要性就不在赘婿了）、功能测试。仔细的设计：这个的仔细是说在程序员编写代码之前，其必须对代码的整个结构以及逻辑结构有明确的清晰的了解，只有这个时候才可以去写代码。这里没有谈到文档，但我说到了一定要清晰的思路，但清晰的思路不是每个人都可以在脑袋中直接形成的，很多人都是普通人，没有办法在脑袋瓜中把所有问题都想清楚，那么就记下来，特别对于复杂的逻辑。

编写代码：对于没有把握的代码，例如：新设计的算法，最好保证其正确性。可以单独将这部分测试，这可以让代码模块化的同时又保证了代码的正确性。一句话：少量的代码保证质量还是比较简单的。单元测试：单元测试的重要性不在赘叙了，现在也有许多工具可以帮助程序员并减少工作量。

功能测试：程序员保证自己代码质量的最后一关；为了做这样的工作我们可能必须写一些代码来测试，甚至是测试工作。使用大量的 CASE 来测试，以及错误的 CASE。这里和测试人员的测试不同之处在于：仍然让程序员的注意力放在其自己的代码范围内，减小了排错的难度。

如果你通过了以上的步骤都找不出你程序中有任何问题的话，那么我想你的程序应该足够健壮了。其实还有一点必须说明的就是：代码 REVIEW。

程序代码 篇5

随着社会经济以及科学技术的迅速发展, 为了扩大社会效益、提高人才培养率, 科技与教育的结合程度越来越高。近年来, 在高等院校教育机制日臻完善的前提下, 社会对学校创新人才的培养越来越重视, 对学校教师的课程设计以及学生程序设计实践课的要求也越来越高。要实现知识结构多元化, 就要对相关设施进行剽窃检测, 从而保证高质量教育人才培养与时代发展接轨。程序代码相似度的识别是近年来维护知识产权、尊重原创、倡导自主创新社会价值引导的重要环节。对程序代码形似度度量进行分析研究, 符合教育现代化的要求。

1 程序代码相似度度量

程序代码具备特有的运作规范, 对程序代码的修改若不能按照程序运行的规范模式进行, 就会影响甚至终止程序运行。代码相似度是指两个程序彼此之间重合率的高低, 百分之百的重合率即代表着完全抄袭, 两个程序代码形似度的高低就可以反映出抄袭情况。

程序代码相似度度量有属性检测和结构检测两种。早在20世纪70年代初, 就有学者研究阻止大规模拷贝程序的技术和软件, 出现了一批比较典型的程序源代码剽窃检测系统[1]。这些检测系统就是早期程序代码相似度度量的雏形。随着科学技术的进步以及信息技术等发展, 程序代码相似度度量由原始简单检测向着用更精准的字符串规范表示程序结构, 选择高效迅速的字符串重合匹配算法的方向发展, 程序代码相似度度量算法研究不断健全和完善。这些研究与实践应用在减少相似度度量的时间长度, 提高相似度度量的精准性方面取得了很大的成效。

属性检测在对每个程序进行检测时, 分别设计4个统计值:X1=单一操作符的数量, X2=单一操作数的数量, Y1=所有操作符的总量, Y2=所有操作数的总量。根据这4个基本赋值统计结果, 定义X=X1+X2作为词汇量, Y=Y1+Y2作为执行长度, 再根据以上数据计算出程序的容量V=Ylog2 (X) , 然后将这些数据结果进行整合生成一个特征向量M (X, Y, V) 。为每个待检测其重复率的程序都建立一个特征向量之后, 再计算每两个向量之间的距离。若检测的两个程序的特征向量之间的距离很小, 就可以认为这两个程序重复率很高, 进而检查对这两个程序之间是否存在抄袭。

结构检测是根据程序的结构来度量两个程序之间的相似度, 这就要求对被检测程序的内部构成进行分析。在这种检测方法中, 要明确程序语言规范, 将程序语言按照某种标准转化成单一字符串, 然后通过某种算法对这些字符串进行比较, 从而判断两个程序之间的重复率。

2 算法

由于属性检测技术存在着遗漏和忽略程序结构信息的弊端, 在检测过程中的错误率较高, 因此在近来开发的检测系统中多使用结构检测方法。算法就是结构检测系统的核心环节。

算法是将程序代码的字符串中的每个字符逐一进行对比, 通过对比检测出程序代码中相同字符的数量, 从而判断程序代码的抄袭率。由于字符串中字符量大, 在程序代码相似度度量过程中, 检测难度和复杂度大, 时间长, 效率低。如果把字符串划分为N个不同的小字符串, 对每个小字符串重新赋值, 那么重合的字符串就可以被同一简单值表示, 这样便减小了检测单位, 降低了检测的复杂程度, 必然可以提高检测效率。

在实际重复率检测过程中, 对检测的程序一般不进行精准匹配检测, 所以, 算法在程序代码相似度度量中的应用率越来越高, 对其进行研究可以提高程序代码相似度度量的质量和效率。

3 算法在程序代码相似度度量中的应用

3.1 代码分割

将被检测的程序代码进行有效分割, 把长字符串划分成多个可以赋值的子串, 具有精准重合和模糊重合的程序代码就会被同一值表示。将两个待检测程序的代码按统一标准分割, 在检测时就可以很快的将具有相同赋值的字符串查找出来, 对具有相同赋值的字符串所表示的程序结构和程序步骤进行抄袭度对比, 便可以得到相关数据。代码分割可以有效地缩减检测程序的单位, 从而减少检测时间提高检测效率。

3.2 特征向量相似度的获取

代码分割后, 将程序按结构划分为不同的信息序列。提取出来的程序结构信息和基本结构元素相结合, 就可以形成一个特征向量, 这个向量就是待检测程序所对应的特征向量。以此类推, 每个待检测程序都可以通过这种方法来生成特征向量。特征向量降低了检测的复杂度和检测单位, 对于快速准确的检测程序的重合程度和重复率帮助很大。

3.3 程序结构相似度的获取

经过属性度量的方法可以获取程序对的标准规范赋值标识符序列, 应用动态规划算法的思想中最长公共子序列算法计算出最优值, 进而得到最长公共标识符子序列, 其他个别情况下可以用自底向上建立地推关系地计算方法计算最优值来提高算法的效率。

由算法LCTS_LENGTH计算得到的数组可用于表示建立的快速构造表的最长公共标识符子序列。在特殊情况下, 可以用递归算法来设计程序的运行构造表。

对于改变关键字的拷贝问题、更改引用文章、调换文章段落、更换新的赋值表示、改变程序代码的顺序、改变程序代码字符串组合的程序语言的顺序、对表达式中的操作符和操作数的顺序进行调换和改变、数据类型转换等更改方式的一种或几种共用进行修改后, 得到的程序对在属性相似度检测中能够检测出较高的重合率, 即相似度较高。但某些情况下, 两个程序的相似度偏高却与其属性检测相关度低, 就必须结合结构相似度来对两个程序的相似度进行考察。

程序结构相似度的获取能够为高效查重和反抄袭提供技术支持, 程序结构相似度的获取有效的弥补了属性检测存在的不能识别结构重合的弊端, 是整体相似度检测的关键环节。

4 结论

程序代码相似度度量技术在检测抄袭率方面发挥着重要的作用, 将算法应用于程序代码相似度度量中, 能够实现对待检测程序的自动化精准复制检测, 从而提高创新水平和社会效益。

参考文献

[1]于海英.程序代码相似度度量的研究与实现[J].计算机工程, 2010 (2) :45-47.

[2]邓爱萍.程序代码相似度度量算法研究[J].计算机工程与设计, 2008 (9) :4636-4639.

程序代码 篇6

早期的嵌入式装置由于内存、空间等资源有限, 通常采用汇编语言实现相关程序功能, 之后硬件升级换代, 逐渐转入到C语言开发。在复杂的应用领域, 由于C代码量大, 如果手工编写, 存在维护、理解困难的情况。图形化编程是一种面向对象的软件开发方法, 用各种编程符号块搭建程序模型, 用图形化页面设计应用功能, 并将图形程序转换并编译为目标代码, 随后下载到嵌入式装置运行。与传统的手工编写全部代码的方式相比, 图形化编程采用经过测试验证的模块化功能符号搭建程序功能, 开发效率高, 维护调试 方便 ,直观易懂, 已经在电力系统保护测控装置中进行了应用[1,2,3,4,5]。文献 [1] 以Java语言构建一套图形化编程系统, 编程符号块按照IEC 61850的逻辑节点模型设计, 已在中低压微机保护中研发进行了应用。文献 [2] 论述了图形化平台微机保护系统的结构功能、保护元件库的构成, 并对图形化编程和常规编程进行了比较。文献 [3] 介绍了护测控装置配套软件PCS-Ex-plroe研发版本的设计思路 , 将保护测控功能进行模块化设计 ,并结合IEC61850标准进行逻辑节点建模, 用图形化元件的方式实现可视化配置建模, 是一种免编译的配置集成方法。文献 [4] 介绍了基于IEC61131-3标准的可编程功能在变电站中的实现方案、软件功能模型、执行器软件的设计方法, 并在备自投装置中进行了实现。文献 [5] 介绍了该继电保护软件平台的结构, 包括集成环境、装置信息配置工具、编程开发工具、逻辑编译器等功能。

在图形化编程平台软件中, 代码生成是个关键步骤, 如何将图形化的页面程序转换为不同硬件能运行的目标代码尚未有文献专题阐述。先简要介绍跨平台图形化编程平台软件的模块划分, 重点介绍代码生成的若干技术, 包括图形化编程符号的建模方法、图形化符号的拓扑排序算法, 最后介绍了基于开放API接口和脚本调用的代码生成方法、。该方法可灵活定义符号功能, 可形成适合交直流保护测控、柔性输电控制、电力电子等不同场合使用的高质量C代码。

2 图形化编程工具概要

图形化编程工具由图形编辑模块、编程符号库、代码生成模块、编译链接模块、 调试下载模块组成。软件采用C++开发, 界面和图形库基于QT4.7实现, 支持Windows/Linux环境下运行。软件按照分层结构组织应用程序, 以图形化方式展现程序逻辑。图形化编程软件5个主要模块功能如下:

(1) 图形程序编辑模块 : 按照装置-插件-应用的层次结构管理页面程序, 一个工程管理若干个插件, 一个插件管理若干元件, 一个元件管理若干页面。在页面内实例化编程符号块, 按照逻辑关系, 绘制符号间输入输出连线。图形编辑模块支持符号的复制、粘帖、删除、 移动、缩放、取消、恢复等编辑功能。

(2) 编程符号库 : 各种保护逻辑、运算等编程符号块符号文件, 通过符号编辑器设计编程符号块, 可定义代码行为、数据属性、图形外观等内容。

(3) 代码生成模块 : 该模块解析图形页面 , 形成适合不同应用场景运行的C代码。

(4) 编译链接模块: 该模块通过分析C文件依赖关系, 形成Makefile, 并调用交叉编译器将C程序编译链接成目标文件。

(5) 调试下载模块 : 和装置进行通信 , 下载目标文件。并支持以可视化的方式进行图形程序的调试, 在连接线上显示变量实时运行值。

3 图形化程序代码生成技术

图形化代码生成的主要技术包括: 编程符号块的XML建模方法、图形页面的的拓扑排序算法、代码文本形成方法等。

3.1 编程符号块 XML 建模方法

图形化编程采用功能符号作为编程的最小粒度单元, 编程软件提供了常用的符号库, 当面向不同的装置应用时, 存在一些特殊功能需求的需要扩展新的符号块实现, 为方便应用开发人员能基于符号编辑器开发专有的符号块, 需提供一种简单、通用、可扩展的符号建模方法。已有的一些建模方法, 代码体受制于特定格式, 或目标代码受限于专用的编译器[1,2,3,4]。提出一种容易扩展、方便维护的符号块建模方法 , 基于XML的建模方式 , 将编程符号块分为图形表示和代码实体定义两部分。

编程符号块的图形信息包括: 输入输出管脚信息、包围矩形外框信息、在框内显示的参数值、名字等文本内容, 还包括一些个性化的辅助图形信息, 将这些基本图元组合为一个整体。以逻辑与符号OR2的图形为例, XML图形数据建模如下:

其中input表示输入, 有形参名为in1、in2的两个输入点,output表示输出点 , 有名字为out1的输出点 , x表示左上角横坐标, y表示左上角纵坐标, w表示宽度, h表示高度, na表示变量名字, tv表示字符串, text表示文本, rect表示矩形。

常规符号 块的代码 对应1个C函数、以 及相关私 有变量, 在代码实体文件中定义符号的数据和函数。符号的代码基于CDATA整段文本描述, 依次可划分: 帮助文本段、in-clude文件段、参数声明段、 符号变量定义段、变量初始化设置段、功能函数定义段、 脚本段 (可选), 采用类C语言描述, 在后端处理时主要进行形参-实参变量名替换、参数值替换、 条件编译语句处理。例如以某监视块为例, 其代码行为建模如下:

应用人员只需编写上述格式的文本段, 符号编辑器可以分析该文本, 提取符号输入、输出、参数等接口, 根据变量个数自动形成符号的默认图形, 形成符号的图形和代码XML描述文件。

3.2 页面符号排序算法

拓扑排序: 由某个集合上的一个偏序得到该集合上的一个全序, 这个操作称之为拓扑排序[6]。在图形化代码生成中 ,拓扑排序指分析编程符号间的连接关系, 决定符号的执行调用顺序。全序: 设R是集合X上的偏序, 如果对每个x,y∈X必有x Ry或者y Rx, 则称R是集合X上的全序关系[6]。

搭建完图形程序后, 需要对图形页面进行排序, 图形化程序的符号执行顺序是代码生成的关键步骤。已经介绍的排序算法有: 基于符号的拓扑图转换为AOV网、人工指定顺序[1]。基于AOV网的方法, 是把图形符号之间拓扑连接关系用有向图表示, 在图中用顶点表示活动, 用弧表示活动间优先关系。在AOV网中, 不应该出现有向环, 这意味着某项活动以自己为先决条件, 程序的执行流图存在闭环死锁依赖, 但实际应用中图形程序中往往存在反馈闭环, 这需要在排序时进行破环处理。人工指定顺序存在的问题是当图形化页面数量很多时, 设置维护的工作量很大, 例如在编程中间插入一个符号时, 需要手工调整后续符号的排序值。提出一种图形化图形程序的自动化排序算法, 先按照任务队列中页面调度顺序决定页面之间的执行顺序, 实现粗粒度排序, 然后在单页面内, 按照符号位置坐标和输入输出依赖关系形成符号执行顺序。该算法由3个步骤实现。

(1) 将图形化页面的坐标原点设置为图形页面左上角 , x坐标从左到右递增, y坐标从上到下递增, 使用插入排序算法, 先将符号按照y坐标进行升序排序, 当符号的y坐标相同时, 按照符号的x坐标升序排列。这种从左到右、从上到下的初步排序, 符合图形化图形程序的机器视觉。

(2) 图形化页面程序的闭环检测和破环处理。利用符号之间输入输出点的拓扑连接关系形成符号的前驱链表和后继链表, 通过某符号的后续链表递归遍历, 若可回溯到源符号,则存在闭环。如果存在破环符号, 定义如下处理原则: 弱化约束条件, 如果符号存在一个未知的输入, 可优先输出。

(3) 将经过破环处理后的符号间拓扑连接关系转换成改进的AOV网, 按照符号的拓扑依赖关系形成前驱链表和后继链表。在AOV网中以深度优先的法则选一个没有前驱的顶点并输出; 从图中删除该顶点和所有以它为尾的弧; 迭代处理每个节点, 直到处理完页面上的所有符号。

在图1中, 存在4个跨页面连接输入变量, 输入点都为0, 都满足执行条件 , 根据位置初排结果 , in0、in1、in2、in3可先执行 (实际等效于置后续连接输入点处于已知状态)。A、B、C都有1个输入点处于未知 , 并存在闭 环 , 此时弱化 约束, 降格为有1个输入未知的符号可排序, 结合位置初排结果, 最终编程符号块执行顺序为A、B、C。

3.3 基于 C++API 和 Python 混合调用的代码生成技术

3.1节介绍的编程符号块 , 有Rule可选字段 , 对于常规的逻辑、数学运算符号, 可以为空, 但存在一些编程符号, 其代码不一定能用一个任务函数表示, 对应的代码可能是在分布中系统初始化中、或者有部分设置信息需关联输出到配置文本、IEC 61850建模文件中, 此时需要编程软件具有较强的灵活性, 即代码生成工具能提供一些开放的接口, 可以在符号脚本段中调用, 工具通过解释执行脚本段, 完成相关功能。QT库的QObject类和派生类有property属性和c++slot接口 ,可以在Python解释引擎中注册相关实体对象, 在脚本中调用注册对象的API接口, 脚本执行后, 后端处理器输出文本内容, 从而实现灵活可定制的代码输出功能。

以装置为例, 其类定义如下, 其中inst Name为装置实例名属性, get Board Num()是返回插件个数的接口, get Board Num()、get Inst Name()、set Inst Name() 等属性操作、公共slot函数都可作为API服务接口, 在脚本中使用。

基于C++API和Python混合调用的代码生成的关键技术如下:

1) 定义可编程对象和API函数。可编程对象定义包括 :装置 (app)、插件 (board)、元件 (comp)、页面 (page)、符号(sybl)、代码生成器 (coder), 在脚本执行前 , 往脚本引擎中注册这些实体对象, 即可调用相关API服务接口。这些对象的提供的典型slot接口包括:

1装置app-slot: 装置管理若干插件, 可被脚本访问的slot有获取插件个数、根据名字、 槽号查找插件实例 ; 返回整个工程的路径、文件名等信息。

2插件board-slot: 插件管理若干元件, 提供的slot有获取插件的CPU型号、返回元件个数、基于元件名查找元件实例;在插件范围内查找某个指定的符号。

3元件comp-slot: 元件管理若干页面, 提供的slot有获取元件的结构名、实例名、返回页面个数、基于页面名查找页面实例等。

4页面page-slot: 页面管理若干符号和连接线 , 提供的slot有获取页面名、页面任务等级、 符号个数、基于符号ID或序号查找符号实例等。

5符号sybl-slot: 编程符号开放的接口有: 返回输入、输出、参数个数, 根据名字查找变量; 获取符号的ID、排序序号; 根据输入输出点获取关联的连接线对象等。

6代码生成 器coder-slot: 往各子文 本段落的 添加、前置等。

2) 在符号脚本段中调用注册对象的API函数。以一个设置插件4个等级任务周期的符号为例, 其功能是根据4个参数值, 输出4个系统软件定义的全局变量:

上述文本中, sybl是当前符 号块 , get Set Value是开放的API函数 , 返回参数设置值。

3) 启动脚本引擎执行脚本。脚本引擎基于基于Python-Qt2.0库开发 , 封装了相关执行接口 , 执行1个符号脚本的关键伪代码为:

4) 后端输出代码文本 , 将元件对应的c文件的代码文本划分为COMP_VAR (变量定义)、LOCAL_FUNC (局部函数)、PAGE_NEW ( 页面构造 函数 ) 、PAGE_INIT ( 页面初始 化函数)、PAGE_RUN (页面运行函数)、COMP_NEW (元件构造函数)、COMP _INIT (元件初始化函数)、COMP TASK (元件任务函数) 等段落进行组织, 顺次输出相关内容。

4 结语

基于XML的编程符号块函数建模方法, 将编程符号块函数分为若干段, 用C语言编写其中的代码段, 成员变量定义灵活、易于移植, 使功能函数适合多种CPU运行。一种图形化程序拓扑排序算法, 先以位置视觉进行初步排序, 并自动检测闭环和进行破环处理, 最后按照数据流依赖关系形成运行符号执行调用顺序, 无需人工干预过程, 提高了编辑效率。基于C++API和Python调用的代码生成方法, 能去除对系统软件的接口耦合, 并可在多个的应用场景下使用。本方法形成的代码在多个直流保护控制工程 (例如哈郑直流工程、舟山柔性输电控制工程)、SVC、SVG、SFC等电力电子应用程序开发中进行了成功应用。

摘要：研究了嵌入式装置图形程序代码生成的技术,采用XML描述编程符号块,基于数据流依赖对图形符号进行拓扑排序,通过C++开放接口和Python脚本调用相结合形成代码,最终形成高质量的C代码。介绍的图形化代码生成技术已经在保护控制程装置中进行了批量应用。

程序代码 篇7

覆盖测试通常分为三步: (1) 对源程序进行代码插桩; (2) 编译插桩后的代码, 并运行生成的可执行文件; (3) 获取并分析插入的信息[2]。由此可见, 代码插桩贯穿覆盖测试的始终, 是实现覆盖测试的关键步骤, 其原理是根据程序流程结构在程序中的特征点, 即函数入口、出口和程序分支插桩代码, 然后编译执行, 同时记录历史数据[3]。因此在源程序中如何正确找出函数入口、出口和程序分支的位置又是插桩程序的重中之重。找出函数入口、出口、分支位置是通过词法语法分析程序实现的[4]。

通常, 词法语法分析程序需要找出关键字、标示符、常数、运算符等信息, 形成符号表, 并分析变量定义、赋值、运算等过程形成语法树[5]。但在插桩程序中, 词法语法分析程序只需找出正确的插桩位置, 并不一定会用到上述的所有信息, 例如变量赋值, 初始化等信息对识别函数入口、出口、分支位置几乎没有帮助。这些信息的获取会影响到插桩器的效率, 在大型工程中更为明显。针对这一问题, 本文所设计的插桩器使用了一种更为精简的词法语法分析方法:把程序分为函数内与函数外两部分, 通过检测左右大括号是否匹配, 以及if, else等极少部分关键字来判断当前位置是否为覆盖测试所需的插桩位置。

使用这种分析方法不需要识别出所有词素, 只需要判断读入的词素是否为插桩程序所关注的几种关键字, 如果是就进行相应处理, 若不是就读下一词素, 并不需要为了检错, 生成词法单元而对每个词素进行完整的分析。因此, 在词素被遍历完一遍之前就有可能被提前排除, 从而减小代码插桩的时间, 而所关注的关键字越少, 越短, 词素被提前排除的可能性就越大, 例如, 如果所关注的关键字中没有以b开头的, 当遇到第一个字符为b的词素时就可以一步排除。把整个代码分为函数内和函数外两部分。一方面可以确定函数入口、出口的位置, 另一方面可以根据函数内部外部所关注的关键字不同把所关注的关键字分为两个集合, 分别确定正则表达式, 进一步减少每张表中的关键字的数量。

1 插桩位置的判断

1.1 字符位置的判断

在C语言中函数的定义只能定义在所有函数的外部, 而分支只出现在函数内部。如果当前字符出现在函数内部就进行分支判断。如果当前字符位置为函数外部, 则记录当前字符, 遇到空格, 回车等分割符则重新记录, 即将进入函数时, 保存记录, 这一记录为将要进入函数的函数名。

C语言中函数的定义包括 (1) 返回值类型; (2) 函数名, 用于之后的函数调用; (3) 参数类型与参数名, 描述了函数所需的数据; (4) 函数主体, 实现函数的功能。函数的一般形式[6]:

返回值类型函数名 (形参)

{函数主体}。

C语言中用左右括号包含起来的语句被称作语句块, 函数内部可以有多个语句块, 函数主体部分也可以看成一语句块。除去注释与字符串常量外, 所有出现字符’{‘, 在之后必然会出现’}’与之对应。从一个函数开始, 到这个函数结束, 除去注释与字符串常量外的左右大括号个数必然相等。当左右括号个数相等的时候, 这个函数必然已经结束, 当前位置必然是在函数外部。定义一变量x初值为0, 遇到字符’{‘时自加, 遇到字符’}’时自减, 当x的值变为0时, 就可以判断出当前位置为函数外部。在函数外部, 出现字符’{‘, ’}’的地方可能为函数也可能为结构体定义部分, 因此不能简单地使用’{‘作为进入函数内部的判断标准, 还需要配合左右小括号进行判断:左右小括号匹配后紧跟着出现’{‘才可以判断为进入函数内部, 过程如图1所示。

1.2 函数入出口位置的判断

进入函数之后, 最先遇到的通常变量的定义部分, 在某些编译器中, 允许变量定义出现在某些语句之后, 但作用域只从定义的位置开始, 这种情况可以直接在字符’{‘后插入探针函数, 但某些编译器中不允许在变量定义之前出现语句, 只需插入类似于int a=pro () ;就可以避免, 假设探针函数的返回值为int类型, 函数名为pro () 。为了保证与编译器无关性, 本文采用第二种方法。在x=1的情况下, 遇到return或者’}’即为函数出口位置。

1.3 程序分支位置的判断

程序分支只能出现在函数内部, 在进入函数内部后, 开始判断。这一过程需检测到的关键字有if、else、switch、case、for、while, 同时也要排除字符串常量的干扰。

2 Dfa状态转换表的建立

通过以上分析, 这种词法语法分析需要检测出 () {来判断函数入口, return判断函数出口。if, else, 等关键字来判断程序分支, 还需要消除来自, 注释, 字符串常量的干扰。

用正则表达式表示如下。

函数外部:

函数入口处:) L*{其中L={‘t’, ’n’, ’’};

字符常量: (') (Σ1) * (') ;

字符串常量: (″) (Σ1) * (″) ;

注释: (//) (Σ) * (n) 和/* (Σ) **/其中 (″) 表示字符”, 为字符串常量的开始或结尾, (//) 表示字符/, 为注释的开始。 (') 为字符’表示字符常量的开始与结尾, Σ表示基本符号集, Σ1表示基本符号集与转义字符的并集。

函数内部:if、else、switch、case、for、while、return。

所有所需的正则表达式都在读入程序前可以确定, 因此为了避免在插桩程序中建立状态转换表的时间开销, 可以用另一程序推导出dfa状态转换表, 然后在插桩程序中直接使用这些数据。本文中所建立的状态转换表是类似于一种散列表的数据结构, 插桩程序可以快速地查找当前状态下, 对应字符的下一状态。

为了方便生成状态转移表, 在编程处理时把各个正则表达式转换为如下形式:

其中字符?表示上文中的 (Σ) *, 空格表示上文中的L, ~表示上文中的 (Σ1) *。

生成状态转换表的过程主要包括三部分, 程序流程图如图2所示。

(1) 对读入的字符做基本处理:由于代码中大部分字符对应的ascii码集中在32~126, 可以通过字符ascii码减去32来计算在状态转换表中的位置, 另外给't'赋值95, 'r'赋值96, 'n'赋值97。根据上文中字符串数组key1的定义, 字符?与空格都包含一定的语法含义, 在读入这两种字符时应该设置对应标志变量。对应于流程图开始之后的前三步。

(2) 填写状态转换表。本文使用类似于子集归纳法的方法给各个状态赋值。对应于流程图中的第一处判断。

(3) 根据各个语法标志变量的值修改状态转换表。上文key1中的字符空格表示空格, 制表符, 换行符构成集合的幂运算;字符?表示基本字符集的幂。包括了或运算与幂运算。假设r=s*, 则对应的nfa状态转移图如图3所示:i, f为N (r) 的开始结束状态, 从开始可经过零次, 一次或多次的N (s) 到达结束状态f。假设r=s|t, 对应的nfa状态转移图如图4所示:i可以经过N (s) 和N (r) 任何一条路径到达f[7]。在本文中, 程序读入字符?后记录当前状态st, 后开始读后边字符直到结束, 再把从tr数组中从st到结束状态之间所有集合中元素所对应的0状态都改为st, 以实现正则表达式的幂运算。

生成的部分结果如图5所示, 共有47个状态, 状态0表示拒绝, "//?n"的接受状态为1, ""?""的接受状态为2, 以此类推。

3 插桩器的实现

3.1 插桩器实现

代码插桩的目的是为了获取源代码运行时的信息以进一步发现错误, 优化代码。为了避免插桩器直接对源代码进行修改而影响后续工作, 插桩器会将插桩后的代码写入另一文件中。

一个大型的工程中通常包括许多.c和.h文件以及一些其他的文件, 例如Linux下的makefile, vc的资源文件等, 为了保证插桩后的副本能够正确运行, 这些文件也需要复制到副本中。而且这些文件也经常按照不同功能放在不同的文件夹下, 这就需要插桩程序能够遍历整个工程文件中所有的子文件夹, 并区分出c文件和其他文件。插桩流程图, 插桩器界面如图6所示:为了对最终的数据分析, 还需要建立一张表描述插桩信息与函数名, 分支的对应关系。

插桩器使用c++语言编写, 编译器为vs2010。插桩过程为:打开c代码文件, 添加包含探针程序的头文件, 然后按照上文所讲方法寻找函数入口, 同时记录所遇到的字符, 遇到空格重新记录。当判断为进入函数后, 把所记录的字符串, 即函数名写入list.txt文件中, 同时换用表tr2[][]进行状态转换。当前状态转为0后只进行字符的读写操作直到空格, 制表符, 换行, 运算符等字符时状态改为起始状态。当状态转换为for、while、if等关键字的接受态时, 开始等待左右小括号的匹配, 左右小括号匹配后排除掉空格, 制表, 换行符号, 若读入的第一字符为{, 则直接写入插桩信息, 若不是, 则通过调整文件指针当前读写位置, 写入{, 再插入插桩信息, 并在第一个;处写入}。若为else, do则跳过左右小括号匹配过程, 直接判断第一个字符是否为{, 处理方法类似。若接受态为default:则直接写入插桩信息。若接受态为case则等待第一个:后写入插桩信息。若接受态为return, 则调整当前读写位置写入插桩信息, 后写入return, 并当前位置到函数结束过程中出现;的次数, 遇到return重新记录, 如果多于两次则在函数结束的}前再次写入插桩信息。以上过程都需要排除字符常量, 字符串常量的干扰。

图7为对linux内核中kernal/trace文件夹插桩的结果。左边为插桩前, 右边为插桩后, 图8为生成的函数索引表。

3.2 复杂度分析

在编译器中, 使用DFA匹配串x的时间复杂度为O (|x|) , 使用本文所述方法, 只有遇到需要关注的关键字时才达到这一复杂度, 对于其他词素, 理想情况下1步就可以排除, 最坏情况:词素与最长关键字相似, 如:某用户自定义标示符为default (∑) *形式, 也只需要8步就可以排除。把代码分为函数内外两部分, 可进一步扩大这一优势, 例如, 在函数内部key2[]数组中, 存在关键字if的匹配过程, 以i开头的词素需要读入i从状态st1转换到st2, 再进行判断, 在函数外部key2[]数组中, 读入i, 就可以一步排除。同时使用生成好的状态转换表, 省去了O (|r|3) 的时间开销。

4 结束语

本文所设计的插桩器主要通过以下四方面来提高插桩速度: (1) 词法, 语法分析简单, 可以减少状态转换所用的时间; (2) 词法语法分析所用的正则表达式可以提前确定, 编写插桩程序时可直接使用推导出的dfa状态转换表, 以消除dfa建立的时间; (3) 对函数内部外部分别建立状态转换表, 可以进一步简化状态转换过程, 以减少时间开销; (4) 状态转换表是一种散列表, 只需通过减法运算就可以知道下一状态在表中的位置。但插桩器可在与平台无关性方面进一步改进, 例如虽然可以对linux系统下c代码插桩, 但目前还不能根据配置信息进行条件预编译的判断, 会把探针函数插在一些不会被编译到的地方, 一定程度上影响之后的数据分析。

摘要：设计了一种用于覆盖测试的代码插桩器。重点介绍了一种高效的词法语法分析方法:通过所读入的左右大括号是否匹配把整个代码分为函数内部和外部, 根据这两部分感兴趣的关键字不同建立不同的DFA状态转换表, 使每个词素能够用最少的状态转换次数判断出是否为所关注的关键字, 减少状态转移的时间复杂度。使用已生成的状态转换表, 消除了建立DFA的时间开销。描述了状态转换表的生成过程, 插桩器的实现过程以及运行结果。

关键词：覆盖测试,代码插桩,词法语法分析

参考文献

[1] 单景辉, 姜瑛, 孙萍.软件测试研究进展.北京大学学报, 2005;41 (1) :134—136

[2] 晏华, 袁海东, 尹立孟.代码自动插装技术的研究与实现.电子科技大学学报, 2002;31 (1) :62—66

[3] 张荣, 王曙燕.基于插桩技术的动态测试研究与实现.现代电子技术, 2011;4 (37) :50—55

[4] 马桂杰, 蒋昌俊, 刘吟, 等.基于插桩技术的并行程序性能分析方法设计和实现.计算机应用研究, 2007;10 (24) :225—227

[5] 乔文东, 万晓东, 嵌入式软件覆盖测试工具的研究.计算机测量与控制, 2007;15 (9) :1238—1240

[6] 谭浩强.C程序设计教程.北京:清华大学出版社, 2007:140—143

程序代码 篇8

关键词：LPC2000,次级启动加载程序,Secondary Boot Loader,IAP,代码升级

引言

本文虽然是针对NXP (恩智浦公司) 的LPC2000系列, 但使用IAP技术对内部闪存进行编程却适用于几乎所有的NXP ARM MCU系列, 包括Cortex-M0 LPC1100以及Cortex-M3LPC1300/1700等系列。

在大多数的LPC2000器件内部, 存在着一个被称为“主启动加载程序 (Primary Boot Loader) ”的固件, 它在每次上电或复位时被首先运行。本文所讲的“次级启动加载程序”实际上是一段用户自己写的代码 (烧写在用户闪存区) , 在执行完主启动加载程序后被执行, 提供给用户一个选择, 是继续执行当前的应用程序还是对当前应用程序进行更新。

在应用编程 (In Application Programming, IAP) 是指在用户应用程序运行时, 对内部闪存执行擦除或编程操作, 它是对用户代码进行升级的一个关键技术。

LPC2000 IAP介绍

扇区 (Sector)

IAP操作都是基于“扇区 (Sector) ”的, 这就意味着即使仅仅需要更新一个字节的代码, 也要将该字节所在的整个扇区擦除。因此, 用户应该将待更新的代码和其它代码放在不同的扇区, 以免误擦除。

IAP的应用领域

使用IAP技术, 可以对用户代码进行升级, 也可以把内部闪存当成类似EEPROM来存储数据。

当用户应用程序运行时, 用户可以对程序的一部分进行更新, 就像在线升级病毒库一样, 而不必将硬件电路断电甚至将芯片取下来放到专门的编程器上去重新烧写代码。

当数据存储器使用, 可以减少PCB板面积、降低成本。由于作为数据存储的扇区会被擦除, 因此不能将这些扇区和存放用户应用程序的扇区重叠。另外, 闪存的擦除和编程次数也是有一定限制的, 过于频繁的擦除或编程会影响闪存的寿命。对于LPC2000芯片来说, 至少可以稳定擦写十万次, 数据至少可以保存20年。

如何使用IAP

关于I A P的详细说明、各种命令码、返回码和参数格式, 可以参考LPC2000系列的用户手册。下面重点介绍一下如何使用IAP。

使用流程

图1是使用IAP对闪存进行擦写和编程的基本步骤。

定义系统参数:在调用IAP命令前, 有一些参数必须事先设置好, 这包括系统时钟、IAP调用的入口地址、存放输入参数和输出参数的变量。

选择扇区:在对任何扇区进行擦除或编程前, 必须选择 (准备) 这些扇区, 当然, 也可以一次选择多个扇区。

擦除扇区:在对闪存的指定扇区进行编程前, 必须先擦除这些扇区。如果这些扇区已经被擦除, 则不必再擦除了。可以一次对多个扇区进行擦除。

编程扇区:在这个阶段, 数据将被从SRAM写入闪存中的指定地址。这里有几个要特别注意的地方:

●只能将位于片内SRAM内的数据写入片内闪存;

●位于片内闪存的写入地址必须是256字节对齐;

●片内SRAM必须位于局部总线 (Local Bus) , 这就意味着有两块SRAM区域 (供USB和以太网使用) 内的数据不能被直接写入闪存;

●一次写入的字节数必须是256、512、1024或者4096。

数据校验:用户不必自己写程序每次对写入的数据进行检查, 而是可以直接调用一个数据校验的IAP命令。

IAP过程中的中断

在擦除和编程操作过程中, 片内闪存是不可访问的, 当用户程序启动执行时, 用户闪存区域的中断向量有效。在调用擦除和编程的IAP命令前, 用户应当关闭中断或者确保中断向量表在SRAM中有效并且中断处理函数也位于SM中。

IAP使用的RAM

IAP命令使用片内SM最顶端的32字节空间。最多使用128字节的栈空间 (位于用户分配的栈内) , 且为向下生长方式。

次级启动加载程序和用户应用程序设计

次级启动加载程序

每次上电或者复位后, 次级启动加载程序将会被运行, 通过串口打印出一些选项, 用户可以选择继续执行应用程序或者更新程序。

次级启动加载程序位于内部闪存中从扇区0开始的若干个扇区内, 这些扇区不能和用户应用程序占用的扇区重叠。

另外, 由于主程序运行在ARM模式, 而IAP运行在THUMB模式, 因此必须做相应配置使得次级启动加载程序里支持ARM和THUMB模式并存。

用户应用程序存储器分布

用户应用程序存放在和次级启动加载程序位置不同的的扇区中, 并且占用了从0x4000 0000开始的一部分片内SM空间。

在片内SRAM的最底部, 存放了应用程序的中断向量表。要注意在配置系统RW区域时, 把这部分空间预留出来, 即用户应用程序的RW从0x4000 0040开始。

中断向量表重映射

对于ARM7处理器而言, 中断向量位于从0x0000 0000到0x0000 001C的地址范围, 因此在Boot ROM和SRAM内的一小部分空间必须被映射到这个地址内, 使得可以在不同的模式 (参考LPC2000用户手册内存映射章节) 下使用中断。

这一小段空间包括32字节的中断向量以及额外的32字节跳转指令, 总共64字节, 范围为0x0000 0000到0x0000 003F。

因为次级启动加载程序的中断向量表存在于闪存的0x0000 0000到0x0000 003F, 因此用户应用程序的中断向量表只能被映射到片内SRAM (对于支持外部总线接口的LPC2000器件, 也可以映射到片外存储器) 。在跳转到用户应用程序执行前, 要将这64字节的数据复制到片内SRAM的底部 (0x4000 0000–0x4000 003F) , 并且将系统的内存映射模式设置为“User RAM Mode”。这样当用户应用程序产生中断时, 系统会自动到位于SRAM的中断向量表取中断向量入口, 而不是错误地跳转到位于0x0地址处的、属于次级启动加载程序的中断向量表。

运行用户应用程序

更新完成后, 修改PC指针, 使其指向新的用户程序的起始地址, 然后开始执行。

注意:要保证用户应用程序能运行, 必须还要做一些必要的初始化工作, 包括RW区域的复制、ZI区域的清零等等, 这些没有放在次级启动加载程序里完成, 而是在用户应用程序开始运行时首先执行。

程序 (从串口利用XMODEM协议更新代码) 上电运行时, 串口将会打印出如图4的信息。

用户可以测试一些IAP命令, 或者选择PROG命令更新用户代码, 更新完成后, 选择RUN命令来执行。

参考文献

[1]NXP半导体.LPC2000芯片用户手册[R/OL].http://ics.nxp.com/products/lpc2000/

[2]NXP半导体.AN10256Using IAP for LPC2000Microcontrollers[R/OL].http://ics.nxp.com/support/documents/microcontrollers/pdf/an10256.pdf

[3]NXP半导体.AN10835Secondary bootloader for code updates using IAP[R/OL].http://ics.nxp.com/support/documents/microcontrollers/zip/an10835.zip

[4]ARM公司.ARM RealView开发套件中文用户手册[R/OL].http://infocenter.arm.com/help/index.jsp-topic=/com.arm.doc.subset.swdev.rvds/index.html

程序代码 篇9

1 数据模型

本系统后端数据库采用Python2.5+原生支持的Sqlite3, 数据库文件的名称在settings.py文件中设置为codedb, 该数据库中包含的数据表如下:

(1) codesharing_language:程序设计语言信息表, 用于存放本系统支持的程序设计语言信息。

(2) codesharing_snippet:程序代码信息表, 用于存放用户发布的程序代码信息。

(3) codesharing_bookmark:程序代码书签信息表, 用于记录用户收藏的程序代码信息。

(4) codesharing_tag:程序代码标签信息表, 用于存放本系统中的程序代码标签信息。

(5) codesharing_tag_snippets:标签程序代码联系表, 用于记录标签与程序代码之间的对应关系信息。

(6) codesharing_snippet_users_voted:用户投票信息表, 用于记录已经对程序代码投过票的用户信息。

(7) codesharing_friendrequest:添加好友请求信息表, 用于存放用户发出的添加好友请求信息。

(8) codesharing_friendship:用户好友信息表, 用于存放用户之间好友关系信息。

(9) auth_user:用户信息表, 用于存放本系统所有用户的信息。此表对应的数据模型User由Django提供。

(10) django_comments:程序代码评论信息表, 用于存放用户对程序代码的评论信息。此表对应的数据模型Comment由Django提供。

这些数据表之间的关系如图1所示。

为了在本系统后端数据库中生成以上这些数据表, 需要首先在本系统的models.py文件中定义与这些数据表相对应的数据模型, 如下所示:

以上这些数据模型定义完之后, 就可以使用命令manage py syncdb建立数据库codedb, 并将这些数据模型对应的数据表添加到该数据库中。如果要查看建立这些数据表所使用的具体SQL语句, 可以通过命令manage.py sqlall codesharing来实现。

2 首页实现

本系统的首页主要实现了对程序代码的分类显示和统计。用户不但可以按照程序代码更新时间的先后顺序来分页浏览系统中所有的程序代码, 而且还能够根据程序设计语言的不同对程序代码进行分类浏览。另外, 在本系统首页中还包含了两个排行榜:一个是用于反映用户发布程序代码数量多少的用户排行榜;另一个是用于反映程序代码受欢迎程度的程序代码排行榜。本系统的首页如图2所示。

在本系统的views.py文件中定义的视图函数main_page负责实现首页中包含的程序代码浏览功能和排行榜功能, 该视图函数的定义如下所示:

从首页模板文件index.html的源代码可知, 该模板文件是从另一个模板文件base.html继承而来。模板文件base.html是本系统中所有模板文件的父模板, 其内容如下所示:

在模板文件base.html中使用了自定义标签get_fr_count, 该标签的实现在自定义标签和过滤器库文件custom_tags_filters py (该文件保存在本系统的templatetags文件夹内) 中进行, 如下所示:

首页模板文件中包含的模板文件snippet_list.html用于生成程序代码列表的html代码, 该模板文件的内容如下所示:

当程序代码列表中包含的程序代码超过了指定数量之后, 本系统就会以分页形式显示程序代码列表, 分页链接和跳转表单也会同时出现在每一页程序代码列表的下方。在首页中生成分页链接和跳转表单的html代码所要用到的模板文件是paginator.html, 内容如下:

为了能正常触发视图函数main_page的执行, 还需要在本系统所在项目mysite的urls.py文件中添加视图函数main_page的一个命名url访问入口, 如下所示:

至此, 本系统数据模型的定义和首页的实现方法就全部讲解完了。

(收稿日期:2012-07-09)

摘要：社会化程序代码共享系统为广大软件开发人员的工作提供了很多便利。目前互联网上此类系统相对较少。以Django1.2.5为基础开发了一个典型的社会化程序代码共享系统。本期详细讲解该系统中数据模型的定义和首页的实现方法。