一种自动气象站嵌入式软件构件裁剪算法

叶 臻，茅正冲，黄 芳

（江南大学物联网工程学院，江苏无锡 214122）

一种自动气象站嵌入式软件构件裁剪算法

叶 臻，茅正冲，黄 芳

（江南大学物联网工程学院，江苏无锡 214122）

为了解决自动气象站嵌入式软件构件冗余度大，不利于低网速环境下远程更新的问题，提出了一种自动气象站嵌入式软件构件裁剪算法，将算法分为预处理、函数信息表的构造、有序二叉树和状态转移及文本指针跳转表的构造、函数调用树的构造、函数的裁剪几个阶段，并对每个阶段作了详细介绍；根据提出的裁剪算法，实现了一个嵌入式软件构件裁剪工具，设计了裁剪实验，并将裁剪前后的构件体积进行了分析对比；实验表明，算法能够有效地对自动气象站嵌入式软件构件进行裁剪，去除构件的冗余代码，大大提高远程更新的效率。

嵌入式软件；构件；裁剪；自动气象站

0 引言

为了解决自动气象站数据采集器嵌入式软件复用率低，开发效率低，维护困难的问题，文献［1］提出了一种基于构件的嵌入式软件开发模式，使得软件的复用率和开发效率得到了很大的提高。在此基础之上，文献［2］又制定了基于构件的嵌入式软件远程更新方案，很大程度上减小了通信流量的消耗，提高了软件维护的效率。

但是，以上的研究还存在一个很大的问题。功能构件［1］是面向领域的，存放着气象领域中与数据采集、数据质量控制、数据计算、数据存储、数据通信相关的函数集合。随着气象领域的发展，气象要素的增加，功能构件的体积也会越来越大。而在一个具体的项目中，气象要素的数量有限，功能构件库中有很多函数是永远不会被调用到的。若直接将领域级的功能构件部署在目标设备上，大量的冗余代码会增加功能构件的体积，这对低网速环境下的远程更新是极为不利的。目前已有学者提出了一些嵌入式软件裁剪方案，但是对于文献［1］设计的构件式数据采集软件并不完全适用。因此，提出了一种自动气象站嵌入式软件构件裁剪算法，将领域级的功能构件进行裁剪，得到体积较小的应用级功能构件，再部署到目标设备上，这样将进一步减小远程更新的流量消耗，提高远程更新的效率。

1 自动气象站嵌入式软件构件裁剪算法

本文设计的构件裁剪算法是针对自动气象站数据采集器构件式嵌入式软件的，其特点可参考文献［1］。

对于此套软件，在部署到采集器之前，需要裁剪的是功能构件。在领域级功能构件源代码中，函数的调用有两种形式。一种形式是编写代码的时候显式地进行调用，称之为静态调用，这部分代码始终会被调用，因此不会被裁剪；另一种形式是通过函数指针调用，函数是否被调用由配置构件中的信息决定，称之为动态调用，这部分代码会根据具体的应用环境做相应的裁剪。对于静态调用和动态调用，在生成函数调用树时所做的处理不同，在下文中会详细说明。

使用集合S＝ ｛fs1，fs2，...，fsn｝表示领域级源代码中所有静态调用的函数，集合DR＝｛fdr1，fdr2，...，f drn｝表示领域级源代码中需要为具体应用保留的动态调用的函数，集合DT＝｛fdt1，fdt2，…，fdtn｝表示领域级源代码中不被具体应用调用而需要被裁剪的动态调用的函数。由于S∩DR＝Ø，S∩DT＝Ø，DR∩DT＝Ø，所以有领域级源代码函数集合W＝S＋DR＋DT＝｛fs1，fs2，...，fsn，fdr1，fdr2，...，fdrn，fdt1，fdt2，...，fdtn｝，则DT＝ W－SDR。本算法的目的就是分析源代码，得到集合W，S和DR，计算出DT，将其裁剪，以缩小功能构件的体积。

下面给出一个简化的C语言程序示例，下文将结合此示例说明算法的流程。程序代码如下：

functionPointer1和functionPointer2为函数指针，假定它们的值为fdr1和fdr3。代码中，W＝｛main，fs1，fs2，fs3，fs4，fs5，fdr1，fdr2，fdr3，fdt1，fdt2，fdt3｝，S＝｛main，fs1，fs2，fs3，fs4，fs5｝，DR＝ ｛fdr1，fdr2，fdr3｝，DT＝ ｛fdt1，fdt2，fdt3｝，由代码可以得到如图1所示的函数调用关系图。

图1 示例程序函数调用关系图

图中，实线箭头表示显式调用，虚线表示通过函数指针调用。由图可知，函数fdt1，fdt2和fdt3没有被调用，需要被裁剪。

基于树的嵌入式软件构件裁剪算法流程图如图2所示。下文将结合上面给出的C程序示例，对算法的步骤作详细的说明。

1.1 预处理

本文提出的构件裁剪算法是基于多模式字符串匹配算法的，如果文本中搜索到函数名字符串，则认定为函数调用。在源代码中，若在注释或双引号之间出现函数名字符串，则会对函数调用的判断造成干扰，如：

因此，首先需要对源代码进行预处理，创建源代码的副本，找出源代码中的注释和双引号组，用占位符替代原先的内容，以消除对函数调用判断造成的干扰，如：

最后，根据经过处理的源代码副本构造函数调用树。

图2 基于树的嵌入式软件构件裁剪算法流程图

1.2 函数信息表的构造

函数信息表是一个链表，它用来存储源代码中所有函数的信息，如下：

Name为函数名称，DefinitionFile为函数定义所在文件的名称，DefinitionStartOffset为函数定义头部在文件中的偏移量，Definition End Offset为函数定义尾部在文件中的偏移量，Tailor指示函数是否需要被裁剪，Next用于指示下一个节点。

要构造函数信息表，关键在于如何从源代码中提取函数名称以及如何确定函数定义在源代码中的位置。本文采用正则表达式来匹配函数定义，以提取函数名称。用于匹配函数名称的正则表达式如下：

通过逐行扫描源代码，使用上述表达式进行匹配，就可以得到源代码中所有的函数定义字符串，然后根据C语言的语法规则从函数定义字符串中提取函数名称。

得到函数名称之后，还要确定此函数的定义在文件中的偏移量。函数定义头部的偏移量即为正则表达式匹配结果首字符的偏移量，下面叙述确定函数定义尾部偏移量的方法。由于函数体是字符‘｛’，‘｝’构成的语句块，它们成对出现，并且有一定的层次性，因此定义一个计数变量count，并初始化为0，然后从正则表达式匹配结果末字符开始向下搜索，匹配到‘｛’则加1，匹配到‘｝’则减1，当count第一次减为0时，指针指向的位置即为函数定义的尾部。

1.3 有序二叉树和状态转移及文本指针跳转表的构造

本文采用基于有序二叉树的快速多模式字符串匹配算法（SMA－QS算法）构造有序二叉树和状态转移及文本指针跳转表，并且在2.4节中还会利用此算法进行字符串多模式匹配，算法的详细步骤可参考文献［5］。

SMA－QS算法分为预处理和匹配两个部分。在预处理阶段，首先将模式集合排列为字典序，然后对于每个模式串，根据一定的规则，向二叉树中添加节点，生成一颗有序二叉树，然后对于每个节点状态和文本指针将指向的下一个字符计算状态转移及文本指针跳转表。在匹配阶段，按照一定的访问规则访问二叉树，使用栈记录已经匹配的字符，若访问到标记为“输出”的节点，说明已经匹配到一个模式串，则将栈中的字符串输出。若出现失配，则根据状态转移及文本指针跳转表中的信息进行跳跃，开始下一次比较。

在本步骤中，以2.2节构造的函数信息表中函数名字符串集合作为输入模式集，使用SMA－QS算法构造一颗有序二叉树及一个状态转移及文本指针跳转表，为函数调用树的构造做好准备。示例程序对应的有序二叉树和状态转移及文本指针跳转表分别如图3和表1所示。

图3 示例程序模式集合对应的有序二叉树

表1 示例程序对应的状态转移及文本指针跳转表

1.4 函数调用树的构造

函数调用树的构造分为两部分，首先构造深度为2的函数调用树链表，然后将其转化为函数调用树，下面首先给出函数调用树节点的定义：

Function Name为函数名称，Right为右节点，Child为子节点。

首先从头至尾扫描函数信息表，对于每个节点，打开DefinitionFile指定的源文件，在DefinitionStartOffset和Definition End Offset指定的偏移量范围内，对源码进行逐行扫描，利用SMA－QS匹配算法进行模式匹配，若有匹配结果，则说明当前节点对应的函数调用了其它的函数，则将此节点及其调用的函数对应的节点加到深度为2的函数调用树链表的尾部。在函数信息表扫描结束后，会生成一个源码对应的深度为2的函数调用树链表。下面给出生成深度为2的函数调用树链表的算法描述：

算法1：生成深度为2的函数调用树链表

输入：函数信息表，有序二叉树，MOVE表

输出：深度为2的函数调用树链表

步骤：

1）对于函数信息表的每个节点m，执行以下操作：

（1）如果m对应的函数fm进行了函数调用，则：

①创建fm对应的节点nm。

②将nm连接在深度为1的节点组成的链表尾部。

③对于fm调用的每个函数f，执行以下操作：

a.创建f对应的节点nf。

b.如果nm有子节点，则把nf连接在以nm的子节点为头节点的链表尾部，否则nm的子节点←nf。

对于上文给出的C语言示例程序，生成的深度为2的函数调用树链表如图4所示。

图4 示例程序对应的深度为2的函数调用树链表

图中的每个节点有3个域，左边的域指向子节点，中间的域存储函数名称，右边的域指向右节点。此链表是将以main，fs1，fs2，fdr1，fdt1为根节点的深度为2的函数调用树串接在一起的结果。

接下来，给出将深度为2的函数调用树链表转化为函数调用树的算法描述：

算法2：生成函数调用树

输入：深度为2的函数调用树链表，根节点r

输出：以r为根节点的函数调用树

步骤：

1）对于深度为2的函数调用树链表中每个深度为1的节点n，执行以下操作：

（1）如果n的函数名称＝r的函数名称，则：

①r的子节点←n的子节点。

②跳出循环。

（2）以r的子节点为根节点递归生成函数调用树。

（3）以r的右节点为根节点递归生成函数调用树。

以main函数对应的节点为根节点，调用上述算法，可生成被静态调用的函数构成的函数调用树Ts；以用户配置的动态调用的函数为根节点，调用上述算法，可生成若干被动态调用的函数构成的函数调用子树Tdk（k＝1，2，...，n），将这些函数调用子树Tdk挂在Ts的根节点下，最终得到代码对应的函数调用树T，树T中所有函数都会被调用，树T以外的函数为冗余代码，应被裁剪。对于上文给出的C语言示例程序，生成的函数调用树T如图5所示。

图5 示例程序对应的函数调用树

1.5 函数的裁剪

在初始化时，将函数信息表中的Tailor初始化为true，意为需要裁剪。然后遍历2.4节生成的函数调用树，对于树中每个节点对应的函数，在函数信息表中将其Tailor修改为false，意为不需要裁剪。遍历结束之后，函数信息表中所有Tailor为true的函数即为需要被裁剪的函数。对于每个需要被裁剪的函数，打开DefinitionFile指定的源文件，在DefinitionStartOffset 和DefinitionEnd Offset指定的偏移量分别写入”／*”和”*／”注释其间的代码，这样就完成了函数裁剪，在编译时此函数将不会被编译进目标文件。

2 裁剪实验

根据以上裁剪算法，开发了一个自动气象站嵌入式软件构件裁剪工具，进行了裁剪实验，以验证算法的可行性。实验针对不同的应用环境，对文献［1］中的构件式嵌入式软件示例代码进行了裁剪。示例代码中包含了适用于风向、风速、气温、气压、降水量、蒸发量、相对湿度的所有函数以及其它通用的函数，不同应用环境中涉及的要素是上述七个要素的子集。对于应用环境1，要素为风向、风速；对于应用环境2，要素为气温、气压；对于应用环境3，要素为降水量、蒸发量、相对湿度。实验结果如表2和表3所示。

表2 裁剪前构件体积

裁剪率计算公式如式（1）所示：

由式（1）可知，对于应用环境1，裁剪率为10.8%；对于应用环境2，裁剪率为9.5%；对于应用环境3，裁剪率为13.3%。目前在实际工程中，要素多达数百个，构件库体积庞大，因此对于一个具体的应用环境，裁剪率会比实验中大得多。

表3 裁剪后构件体积

3 结束语

针对自动气象站嵌入式软件构件代码冗余度大，不利于远程更新的问题，提出了一种自动气象站嵌入式软件构件裁剪算法，对算法的各个步骤进行了详细说明，并实现了构件裁剪工具，设计了裁剪实验。实验表明，提出的裁剪算法可以有效地对构件进行裁剪。随着气象领域的飞速发展，监测的气象要素越来越多，构件库的体积越来越大，远程更新时无意义的流量消耗越来越大，因此嵌入式软件构件的裁剪在气象领域中的应用具有深远的意义。

［1］茅正冲，叶 臻，黄 芳.基于构件的可配置嵌入式应用程序设计模式［J］.计算机测量与控制，2015，23（4）：1432-1434，1437.

［2］茅正冲，叶 臻，黄 芳，基于构件的自动气象站嵌入式程序远程更新［J］.单片机与嵌入式系统应用，2015，15（11）：44 -47.

［3］王亚刚，陈莉君.ELF目标文件的裁剪方法研究［J］.电脑知识与技术，2009，5（11）：3018-3020.

［4］成月良，方寿海.面向应用的嵌入式Linux裁剪方法研究与实现［J］.计算机工程与设计，2009，30（11）：2684-2686，2697.

［5］周 燕，侯整风，何 玲.基于有序二叉树的快速多模式字符串匹配算法［J］.计算机工程，2010，36（17）：42-44.

［6］崔欢欢，霍 华，王永杰.一种面向应用的嵌入式Linux内核混合裁剪方法［J］.河南科技大学学报（自然科学版），2011，32 （2）：32-35.

［7］江梦涛，荆 琦.C语言静态代码分析中的调用关系提取方法［J］.计算机科学，2014，41（z1）：442-444.

［8］苗 磊，陈莉君.基于静态分析的函数调用关系研究［J］.计算机与数字工程，2014，42（9）：1653-1656，1728.

［9］庄克良，高云岭，纪向尚.嵌入式系统程序调用关系分析设计方法［J］.舰船电子工程，2010，30（10）：129-131，149.

［10］严 义，左 鼎.基于关系矩阵的嵌入式组件裁剪方法［J］.计算机工程与应用，2009，45（24）：77-79，90.

［11］蔡 虹，沈 雷，李永红，等.基于覆盖测试的嵌入式软件自动裁剪［J］.计算机工程，2010，36（1）：73-75.

［12］Matthys N，Hughes D，Michiels S，et al.Fine－grained tailoring of component behaviour for embedded systems［A］.7th IFIP WG 10.2 International Workshop on Software Technologies for Embedded andUbiquitous Systems［C］.SEUS2009.Compendex，2009：156-167.

A Tailor Algorithm of Embedded Software Components of Automatic Meteorological Station

Ye Zhen，Mao Zhengchong，Huang Fang

（College of Io T Engineering，Jiangnan University，Wuxi 214122，China）

To solve the problem of big redundancy of embedded software components of automatic meteorological station which goes against remote update under low internet speed environment，proposing a tailor algorithm of embedded software components of automatic meteorological station.Dividing the algorithm into several stages which are pretreatment，construction of function information table，construction of ordered binary tree，state transfer and text pointer skip table，construction of function call tree and tailor of functions and then introducing each stage specifically.Realizing a tailor tool of embedded software according to proposed tailor algorithm and designing a tailor experiment.Analyzing and comparing the volume of components before and after tailor.The experiment shows that the algorithm is able to tailor embedded software components of automatic meteorological station effectively，cut redundant code of components and improve the efficiency of remote update immensely.

embedded software；component；tailor；automatic meteorological station

1671-4598（2016）08-0157-04

10.16526／j.cnki.11－4762／tp.2016.08.042

：TP311

：A

2016-03-04；

：2016-03-29。

江苏省自然科学基金（BK20131107）。

叶 臻（1991-），男，江苏南京人，硕士研究生，主要从事嵌入式软件构件技术方向的研究。