（电路与系统专业论文）嵌入式系统代码压缩技术的研究.pdf

浙江大学硕士学位论文一嵌入式系统代码压缩技术的研究 摘要 在消费电子市场需求的有力推动下，嵌入式系统的功能日益强大，其软件 开发的复杂程度也随之越来越高，嵌入式软件的代码量以平均每两年时间翻一 番的速度增长。由于嵌入式系统在成本、体积、功耗等多方面受到制约，代码 量的增长将成为嵌入式系统发展的一个瓶颈。因此，代码压缩技术将成为今后 嵌入式系统发展的一项关键技术。 本文从基本的数据压缩理论入手，分析了典型的数据压缩和代码压缩的各 自特点以及它们之间的内在联系与区别，结合对当今代码压缩技术的发展现状 的介绍，总结出了代码压缩技术的评价标准。基于对a r m v 4 指令集的研究分 析，我们提出了通过字典压缩的方法对程序代码进行压缩以减小其冗余度的方 案。我们对字典压缩的问题进行了数学抽象和描述，进而对字典压缩方案中的 各种参数的设计进行了数学分析以论证所采用的代码压缩方案的正确性与合理 性。本文对我们所设计的代码压缩方案的步骤、代码压缩中的难点问题的解决 等细节以及主要的算法流程均做了详尽的叙述。最终，使用我们所设计的代码 压缩方案，我们对m i b e n c h 基准测试程序中的6 个典型程序进行了压缩实验， 获得了平均8 1 1 的压缩比。 在代码压缩方案设计的基础上，我们对解压缩系统的硬件设计进行了讨论， 并对解压缩系统中的主要部分提出了优化的硬件设计方案。为了验证代码压缩 方案的正确性，我们搭建了一个系统验证平台，其中包括：v e r i l o g i d l 描述的 解压缩模块和压缩指令内存模型，以及p l i 形式的a r m 指令模拟器。通过与 a r m 公司的标准模拟器a r m u l a t o r 的输出结果进行对比，我们完成了验证系统 的自动化测试。 最后，我们对压缩实验的结果进行了深入的分析研究，总结了影响代码压 缩的因素，并对未来工作做了进一步探讨。 关键词：代码压缩，嵌入式系统 浙江大学硕士学位论文一嵌入式系统代码压缩拄术的研究 a b s 觚c t w i t l lt 1 1 ei r i l p e l 】i n go ft h er e q u i r e m e n t 丹o mc o n s u m e re i e c 订o n i cm a r k e t ，e m b e d d e d s y s t e mh a sb e c o m em o r ea 1 1 dm o r ep o w e r f h l n o w a d a y s ，t h ec o d es i z eo fe m b e d d e d s o n w a r ei sd o u b l e d 印弘o x 蛔a t e l ye v e r y 铆oy e a s b yt h el i m i t a t i o no fm ec o s t ， s i l i c o na r e a 锄dp o w e rc o n s u m i n g ，c o d es i z ei s b c c o m i n gm eb o t t l e n e c ko f e m b e d d e ds y g t e m t h e r e f o r e ，c o d ec o m p r e s s i o nw i l lb eo n e “t l l ek e yt e c h n o l o g i e s f o re m b e d d e ds y s t 既ni n l e 向t u r c f i r s t ，w ec o m p a r ec o d cc o m p r c s s i o nt ot y p j c a ld a t ac o m p r c s s i o n ，d e s c r i b em e i r c h a m c t e r i s t i cr e s p e c 咖e l ya n dp o i n to u tt h e i rd i 仃c r c n c e si nm ed i s s e r t a t i o n t h e nw e s u m m a r i z es c v c r a lc r i t c r i o n sf 曲c o d ec o m p r e s s i o n a f t e rs t u d i c da i 蝴v 4i i l s 恤l c t i o n s e t ，w ep r e s e n tas c h e m eu s i n gd i c t i o n a r yc o m p r e s s i o nt or c d u c em er c d u n d 明c yo f 廿l eo b j e c tc o d e w e 如曲墨c tm ep r o b l e mo fd i c t l o n a r yc o m p r c s s i o nm a n l e m a t i c a l l y a n dd i s c u s ss o m ei s s u e so fp a r a m e t c r s s e l e c t i o nu s i n gm a t l l e m a t i c a lm e m o d t h e s t e p so fo u rc o m p r e s s i o ns c h e m e ，t h ed i m c u l t i e so fc o d ec o m p r e s s i o n 锄dn l en o w s o fs o m ei m p o r t a n ta l g o r 汕m sa r ca l lp r e s e n t e di nt h i sd i s s c r t a t i o n f i n a l l y ，w et c s t o u rc o d ec 彻叩r e s s i o ns c h e m eo nt h e6b e n c h m a r k si nm i b e n c ha i l dg a i n8 1 8 c o m p r c s s i o nr a t i o b a s e do no u rc o d ec o m p r c s s i o ns c h e m e ，w ed i s c u s st 1 1 eh a r d w a r ed e s i g no f d e c o m p r c s s i o ns y s t c ma f l dp r e s e n tac o u p l eo fd e s i g ni s s u e so fo p t i h l i z i n gm em a i n p a n si nt l l ed e c o m p r e s s i a nh a r d w a r e t bv a l i d a t eo u rc o d ec o i n p r e s s i o ns c h e m e ，a t e s t b e n c hh a sb e e ne g t a b l i s h e d ，i n c l u d i n gad e c o m p r e s s i o nm o d u l eu s i n gv b m o g i d l ，a ni n s n l l c t i o nr o mc o n t a i n i n gc o m p r e s s e dc o d e s 蚰da i la r mi s as i m u l a t o r u s i n gp l i 1 1 l ev e r i f i c a t i o nh a sb e e n 加i s h c da u t o m a t i c a 】l y w i t hc o r r e c tr e s u i t c o m p a r e d 、i t ha r m u l a t o r ，w h i c hi st h es t a n d a r da r m c o r es i m u l a t o r i n 也ee n d ，w em a k er e s e a r c ho nt h er c s u l to fc o m p r e s s i o ne x p e r i m e n ta 1 1 da n a l y z e t h ef a c t o r si m p a c to nc o m p r c s s i o nr a t i o t h e nw et a l ka b o u t 如t u r cw o r k so fo u rc o d e c o m o r e s s i o ns c h e m e k e y 帅r d s ：c o d ec o m p r 嘲i o n ，e m b e d d e ds y s t e m i i 浙江大学硕士学位论文一嵌入式系统代码压缩技术的研究 图目录 图1 1 压缩技术分类。5 图3 1a r m 寄存器一1 3 图3 2 a r m v 4 指令集二进制编码一1 5 图3 3a r m 指令条件码域1 6 图3 4 典型高级语言的代码生成1 7 图3 5 通信系统模型1 8 图3 6 计算机系统模型1 8 图3 7 变长编解码模型1 9 图3 8 二次编码模型1 9 图3 9 即程序指令重复性统计2 0 图3 1 0m i b c h 基准测试程序2 1 图3 1 lm i b c h 程序指令重复性统计2 2 图3 1 2 典型单指令字典压缩2 3 图3 1 3 字典压缩方案的压缩代码生成2 5 图3 1 4 字典压缩方案示意图2 6 图3 1 5m i b e n c h 单条指令重复性统计2 7 图3 1 6 字典索引代码编码。3 0 图3 1 7 压缩程序内存示意图3 0 图3 1 8 三模式字典索引代码位域图3 l 图3 1 9 双模式字典索引代码位域图- 3 2 图3 2 0 指令组拆分压缩示意图3 3 图3 2 l 指令组间“重叠”情形3 6 图3 2 2 指令组“冲突”解决算法流程3 8 图3 2 3 转移指令编码3 9 图3 2 41 6 位偏移修正码编码4 0 图4 1 解压缩结构图4 2 图4 ，2 固定宽表格结构的字典存储方案4 3 图4 3 表格分组结构的字典存储方案4 3 图4 4 两级查找表结构的字典存储方案一4 4 图4 5 带有起始指令的两级查找表结构的字典存储方案4 4 图4 6 指令队列结构4 5 图4 ，7 验证系统结构图4 6 图4 8 验证测试平台结构图5 0 图4 9 系统仿真波形图5 1 图5 1m i b e n c h 基准测试程序压缩比5 4 v 浙江大学硕士学位论文一嵌入式系统代码压缩技术的研究 表目录 表3 1a r m 的条件码 表3 2m i b c h 单条指令重复性统计 表5 1 压缩字典表( 一) 。 表5 2 压缩字典表( 二) 表5 3m i b c h 基准测试程序压缩比 m 卯盟 钭 浙江大学硕士学位论文一嵌入式系统代码压缩技术的研究 1 1 嵌入式系统 第一章绪论 1 1 1 嵌入式系统的发展概况 2 1 世纪，在全球新一轮汽车、通信、信息电器、医疗、军事等行业的巨大 智能化装各市场需求下，全球嵌入式软件及系统产业得到了快速发展，可以说 已经广泛地应用于人类生活的方方面面。2 0 0 4 年全球嵌入式软件的销售规模已 经达到了3 9 5 亿美元。而嵌入式系统产品的产值已达到2 0 0 0 亿美元，估计全世 界嵌入式系统产品潜在的市场将超过1 0 0 0 0 亿美元。 在中国，虽然嵌入式系统行业刚刚进入起步阶段，但进展神速。2 0 0 4 年我 国嵌入式系统应用产品经济总量估计超过l o o o o 亿元，其中嵌入式处理器芯片 约为1 2 0 亿元。2 0 0 4 我国嵌入式微处理器销售总量大约为1 3 亿片。嵌入式d s p 市场已无处不在，市场规模已接近通用d s p 的两倍，且增长速度强劲。其应用 包括d v d 播放器、机项盒、音视频接收设备、m p 3 播放器、数码相机和汽车 电子等各个领域。发展嵌入式系统产业成为我国信息产业由“中国制造”向 “中国创造”的突破口，成为我国信息产业增长方式由粗放型向集约型转变， 实现可持续发展的重要途径。 1 1 2 嵌入式系统的定义及特点 嵌入式系统被定义为：以应用为中心、以计算机技术为基础、软件硬件可 裁剪、适应应用系统对功能、可靠性、成本、体积、功耗严格要求的专用计算 机系统【2 】o 嵌入式系统具有以下特点： ( 1 ) 嵌入式系统通常是面向特定应用的 嵌入式c p u 与通用型的最大不同就是嵌入式c p u 大多工作在为特定用户 浙江大学硕士学位论文一嵌入式系统代码压缩技术的研究 群设计的系统中，它通常都具有低功耗、体积小、集成度高等特点，能够把通 用c p u 中许多由板卡完成的任务集成在芯片内部，从而有利于嵌入式系统设计 趋于小型化，移动能力大大增强，跟网络的耦合也越来越紧密。 ( 2 ) 嵌入式系统是将先进的计算机技术、半导体技术和电子技术与各个行业 的具体应用相结合后的产物。这一点就决定了它必然是一个技术密集、资金密 集、高度分散、不断创新的知识集成系统。 ( 3 ) 嵌入式系统的硬件和软件都必须高效率地设计，量体裁衣、去除冗余， 力争在同样的硅片面积上实现更高的性能，这样才能在具体应用中对处理器的 选择更具有竞争力。 “) 嵌入式系统和具体应用有机地结合在一起，它的升级换代也是和具体产 品同步进行，因此嵌入式系统产品一旦进入市场，具有较长的生命周期。 ( 5 ) 嵌入式系统本身不具备自主开发能力，即使设计完成以后用户通常也是 不能对其中的程序功能进行修改的，必须有一套开发工具和环境才能进行开发。 1 1 3 嵌入式软件的特点 嵌入式处理器的应用软件是实现嵌入式系统功能的关键，对嵌入式处理器 系统软件和应用软件的要求也和通用计算机有所不同。 ( 1 ) 软件要求固态化存储 为了提高执行速度和系统可靠性，嵌入式系统中的软件一般都固化在存储 器芯片或单片机本身中，而不是存贮于磁盘等载体中。 ( 2 ) 软件代码高质量、高可靠性 尽管半导体技术的发展使处理器速度不断提高、片上存储器容量不断增加， 但在大多数应用中，存储空间仍然是宝贵的，还存在实时性的要求。为此要求 程序编写和编译工具的质量要高，以减少程序二进制代码长度、提高执行速度。 ( 3 ) 系统软件的实时性 多任务嵌入式系统中，对重要性各不相同的任务进行统筹兼顾的合理调度 ， 浙江大学硕士学位论文一嵌入式系统代码压缩技术的研究 是保证每个任务及时执行的关键，单纯通过提高处理器速度是无法完成和没有 效率的，这种任务调度只能由优化编写的系统软件来完成，因此系统软件的实 时性是基本要求。 ( 4 ) 多任务操作系统是知识集成的平台和走向工业标准化道路的基础。 1 2 数据压缩与代码压缩 数据压缩是把输入数据流( 源流或原始数据) 转变为另一种较小的数据流 ( 输出流或压缩流) 的过程。数据压缩的方法很多，它们基于不同的理念，适 合不同的数据类型，产生不同的效果，但是原理都是相同的，即通过去除源文 件的原始数据中的冗余度来压缩数据。经研究发现，大多数信息的表达都存在 着一定的冗余度，例如在典型的英文文本中，字幕e 最常出现而z 很少出现， 成为“字母冗余”( a l p h a b c t i cr e d u n d c y ) ；通常字母q 后常跟有字母u ，这又 称为“文本冗余”( c o n t e x t u a lr e d u n d a n c y ) 。在一幅非随机的图像中，相邻像素的 颜色往往接近，称为“图像冗余”【3 j 。 1 2 1 数据压缩的基本概念 1 2 1 1 无损压缩与有损压缩 通过丢失一些信息来得到更好的压缩，称为有损压缩。有损压缩在解压后， 结果与原始的数据流不完全一致。这种方法适合于图像、电影或声音的压缩， 在丢失的数据很小时感觉不到差别。 无损压缩则是1 0 0 保留数据信息的压缩方式。对于文本文件，特别是计算 机程序的文件一定要使用无损压缩，否则会导致文件全部无效。 1 2 1 2 冗余度 2 0 世纪4 0 年代末期，美国贝尔实验室的c l a u d es h 粕n o n 创立了信息论， 他采用了专业术语“熵”。数据的熵取决于各个符号的概率只，且当所有n 个符 号的概率相等时最大。据此可以把数据的冗余度r 定义为某一符号集合中数据 浙江大学硕士学位论文一嵌入式系统代码压缩技术的研究 的最大可能的熵与其实际熵之差，即 。z 1 3 模型 h r = 一l 0 9 2 ( 1 p ) 一( 一只l 0 9 2 日) = 一l 0 9 2 ，l + 只l 0 9 2 鼻( 式1 1 ) l _ 1 - = 1 根据香农的信息论原理，要压缩一条信息，首先要分析清楚信息中每个符 号出现的概率，对符号的概率计算得越准确，也就越容易得到好的压缩效果。 “静态统计模型”预先扫描文件中的所有字符，统计出每个字符出现的概 率，但是不同的文件中，字符有不同的分布概率。这就需要大量的时间统计要 压缩的所有文件中的字符概率，并为每一个单独的文件保存一份概率表以备解 压缩时需要，且保存概率表也使压缩后的文件增大。 “自适应模型”则是在信息被输入之前对信息内容一无所知并假定每个字 符的出现概率均等，随着字符不断被输入和编码，它统计并纪录已经出现过的 字符的概率并将这些概率应用于对后续字符的编码。自适应模型在压缩开始时 压缩效果并不理想，但随着压缩的进行，它会越来越接近字符概率的准确值， 并达到理想的压缩效果。 “静态统计模型”与“自适应模型”均为“统计模型”，它们都是基于对每 个字符出现次数的统计得到字符概率的。与之相对应的“字典模型”则并不直 接计算字符出现的概率，而是使用一本字典，随着输入信息的读入，模型找出 输入信息在字典中匹配的最长的字符串，然后输出该字符串在字典中的索引信 息。匹配越长，压缩效果越好。事实上，字典模型本质上仍然是基于对字符概 率的计算的，只不过字典模型使用整个字符串的匹配代替了对某一字符重复次 数的统计。 与“统计模型”相类似，保存一本大字典所需的代价也是非常高的，因此， 字典模型也有相应的“自适应”方案，即随着信息的不断输入，从已经输入的 信息中建立合适的字典，并不断更新这本字典，以适应数据的不断变化。 浙江大学硕士学位论文一嵌入式系统代码压缩技术的研究 压缩技术 r l 通用无损数据压缩多娥体数据压觜沃多为有损压缩) l i ，、 基千统计基千字典 模型的压模型的压 缩技术缩技术 ff r u f f m 算木 编码编码 u n i x 下接近无损 的c 0 膪a c t 压缩极限 程序等的高级应用 r _ 、 音频压缩图像压缩视频压缩 职3 等 p x z i p 、l h a r c 、埘、 瑚下的c 0 肝艇s s 程序等 1 2 2 数据压缩的度量 r _ 弋肺 二值灰虔彩色矢量豫阱2 等 图慑 图像 图像图像 l ii 传真机f e l 工c s6 i f p o s t s c n p t 标准j p e 6 等丁p 酷等w i n d o w s 哪等 图1 1 压缩技术分类 1 2 2 1 压缩比( m p r 姻s i 佃n t i o ) 压缩比定又为压缩后数据大小与原始数据大小的比值。压缩比为o 6 就意味 着压缩后的数据大小占原始数据大小的6 0 。通常这个值都是小于l 的，如果 该值大于1 说明压缩后数据量大于原始数据量，即出现了“负压缩”【3 o 压靴= ( 虮2 ) 1 2 2 - 2 压缩因子细p 魁s i 阻纽c t o r ) 压缩因子是压缩比的倒数。此值大于1 表示压缩，小于l 则表示为扩展。 压缩因子= 粼 ( 札3 ) 1 2 3 典型数据压缩与代码压缩的特点 从本质上说，代码压缩是数据压缩的一种，但是典型的数据压缩与代码压 缩却有着各自的特点。 浙江大学硕士学位论文一嵌入式系统代码压缩技术的研究 ( 1 ) 典型的数据压缩对象通常是大量的数据，例如计算机主存中的海量数 据，而代码压缩的对象则是一个应用程序，遥常其数据量则非常小，这特点 对于嵌入式代码而言尤其突出。因此，典型数据压缩方法大多使用基于滑动窗 的扫描方法( 例如：l e m p e l z i v 算法) ，而无法使用静态统计的方法。 ( 2 ) “滑动窗”中记录着压缩数据过程中的历史信息，且这一历史信息随着 窗的“滑动”而改变和更新“字典”中的内容，这样的压缩体制使得解压缩过 程必需从头开始。而对于代码压缩来说，程序的解压缩过程是伴随程序的执行 过程实时进行的。由于程序的执行过程并不是顺序完成，指令流的变化要求代 码解压过程可以从任意点开始。 ( 3 ) 典型的数据压缩的输出通常可以是“位对齐”( b i t - a 1 弘e d ) 的，而代码压 缩通常被处理器的取指与译码部件限制为譬产节对齐”( b ”e - a l i g l l e d ) 方式。 此外，代码压缩还有其自身的特点： 程序的压缩相对于普通的数据压缩有一个很大的优势，那就是在程序语义 不变的前提下可以通过重新组织指令以获得等价的程序。对于高级语言编写的 程序，可以通过编译器的辅助对程序进行优化，生成更加适合压缩的程序代码， 这样可以提高代码压缩的效率。 浙江大学硕士学位论文一嵌入式系统代码压缩技术的研究 第二章代码压缩技术背景知识 2 1 代码压缩的需求 随着消费电子市场的不断扩大，新产品的性能不断地得到提高，其功能也 日益强大而且还在不断地完善。市场地需求促进着嵌入式产品功能的不断增加， 由此嵌入式软件的代码也随之增长。据统计，平均每两年时间嵌入式系统软件 的代码量就会增一倍。随着消费电子领域竞争日趋激烈，为了赢得更广阔的市 场，产品的研发时问以及产品的上市时间逐渐缩短。因此，主流的嵌入式系统 软件开发方式已经由人工汇编发展成为“高级语言+ 编译器”作为主要手段，其 中高级语言多为c c + + 、j a v a 等语言。 尽管编译优化技术已经发展为一项很成熟的技术，但是“高级语言+ 编译器” 方式往往还是无法实现高密度的程序代码生成，这对于那些存储器占据整个系 统主要成本的嵌入式系统而言影响是非常大的。其次，对于手持设备而言，由 于受到电池容量的限制，功耗对于这些产品而言是设计的首要指标。在绝大多 数手持产品中，存储器功耗占据了其整个系统功耗的绝大部分，因此，限制存 储器的大小成为了手持设备低功耗设计的主要途径之一。 总之，嵌入式系统不但需要不断提高自身计算能力以适应更高水平计算领 域的需求，为用户提供更多更好的功能，而且在成本、体积、功耗等多方面受 到制约。因而，代码压缩技术是未来嵌入式发展的关键技术之一。 2 2 代码压缩技术研究现状 目前，国外对于代码压缩技术的研究比较系统，从编译原理、指令集结构 再到处理器结构，乃至各种软、硬件方法均有涉及。尤其是嵌入式处理器厂商 在发布新处理器的同时也注意到了嵌入式领域对于代码压缩技术的需求。 a r m 、m i p s 、i b m 、a r c 等主流处理器厂商都推出了针对自己产品的代码压 缩技术。在学术界也从最早的通用式计算领域过渡到嵌入式计算领域。以下将 对目前主要的一些代码压缩的技术进行简要的介绍1 4 j 。 浙江大学硕士学位论文一嵌入式系统代码压缩技术的研究 删的t h u m b 技术 n l u m b 实际上是添加到a r m 的标准i u s c 指令集之上的独立指令集。在程 序执行过程中，通过一条模式切换指令在两种指令集之间进行切换。标准的 a i t m 指令是3 2 位的，而1 1 1 u m b 指令是1 6 位的。但是n u m b 指令集是不完备 的，它只支持基本的加法、减法、循环移位以及跳转指令等通用功能，必要时 还是需要借助完备的a r m 指令集来完成任务。因此，伯u m b 技术主要是通过 局部使用较短的指令替换删标准的3 2 位指令以达到压缩代码的目的 】。 n l u m b 技术存在一定的限制： 首先，1 1 1 u m b 代码和标准a r m 代码不能混杂使用，必须显式地在两种模 式问进行切换，就好像n i u m b 是一套完全不同的指令集。这迫使程序员将所有 的1 6 位代码与3 2 位代码分开并隔离到独立的模块中。 其次，n i m b 是精简的指令集，在此模式下无法完成中断、长跳转、原子 存储器( a t o m i cm e m o r y ) 操作或协处理器等操作，这些都必须使用a r m 的标准 3 2 位指令集来完成，t h u m b 仅对基本的算术和逻辑操作有用。并且在1 1 1 呲b 模式下，a r m 处理器将仅有8 个寄存器( 而不是1 6 个) ，这些寄存器无法像删 指令那样进行条件执行和移位或循环移位操作。 再次，从标准模式到m m b 模式之间的来回切换也要消耗时间，而且还要 增加代码。此外，还需要几十个前导( p r c a l t l b l e ) 以及后同步指令( p o s t a n l b l e ) 来组 织指针并清空c p u 的流水线。如果在1 1 1 啪b 模式中运行的代码小于几十条指 令，就不值得为其付出这样的开销。 最后，t h m b 还对于性能有着少许的影响。通常，使用t h u m b 指令对代码 进行压缩会导致代码运行速度降低大约1 5 ，这主要是由于在1 6 位模式和3 2 位模式间切换所引起的。1 1 1 u m b 指令还不如3 2 位的标准指令灵活，因此，和 3 2 位代码相比，常常需要更多的指令来完成同样的工作。 4m i p s 的m 哪! “指令集 m i p s l 6 e 是和1 1 1 u m b 类似的一种技术，m i p s l 6 e 指令集包括了一组1 6 位 的标准m i p s 算法、逻辑以及跳转指令的简化版本。它同样需要在标准模式和 浙江大学硕士学位论文一嵌入式系统代码压缩技术的研究 m i p s l 6 e 模式之间来回切换，这也将导致付出时间和增加代码的开销。除非能 在“压缩”模式上运行相当长时间，否则没有必要进行模式切换4 一。 a r c 的a r c o m 砷c t 技术 a r ci n t e m a t i o n a l 公司的越屺t a n g e n t 处理器有用户可定义的指令集，所以 a r c 公司决定加入一组16 位指令来改进处理器代码密度，这就是a r c o m p a c t 指令集。a r c o m p a c t 与1 1 1 u r 由以及m i p s l 6 e 的不同之处在于可以将1 6 位代码 和3 2 位代码任意混杂。由于没有模式切换，代码中任意分布的少许1 6 位指令 无须为之付出什么开销。舢坨o m p a c t 之所以可以做到混合不同长度代码而不必 付出相应的开销，是因为其指令架构并非传统的r l s c 架构。传统砌s c 指令集 在指令字中没有指明指令长度的位，而a r c 这样的新伪s c 架构和c i s c 架 构( 诸如x 8 6 ) 都含有这些表示指令长度的位。因此，a i k o m p a c t 技术才能够 任意混合地使用1 6 位代码与3 2 位代码，且无需切换开销i 蜘。 a r m 的t h 蛐a b l 2 技术 1 1 1 u m b - 2 指令集是a j l m 最新发布的代码压缩系统。1 1 1 u m b - 2 有些类似 a r c o m p a c t ，可以无需模式切换就运行16 位与3 2 位混合代码。它在原有的指 令集中，b l 指令有一些位没有使用，这些原先未定义的位给全颞的指令集提供 了切换入口。1 1 1 啪b 2 最大的优势在于它是一套完整的指令集，程序无需切换 回“标准”3 2 位a i t m 模式，原先t h u m b 模式的限制再也没有了。程序现在可 以处理中断、设置m m u 、管理缓存，和真正的微处理器并没什么不同【4 ，8 】。 尽管没有了模式切换的开销，与标准删代码相比，它还是要花费多一 些的t h u m b 一2 指令来完成特定的任务。对于a r m 处理器而言，这些额外的指 令( 以及额外的周期) 会使速度降低大约t 5 到2 0 。 出p 呷e r p c 的c o d e p 觚k 技术 c o d e p a c k 系统是真正对运行代码进行压缩。c o d e p a c k 会分析并压缩整个程 序，然后运行c o d e p a c k 压缩工具对代码进行压缩，压缩工具会分析代码指令的 分布并生成对专门针对这个程序代码的键值。当运行压缩后的代码时，拥有 c o d e p a c k 功能的处理器使用这一对键值来在运行中解开压缩的代码，就好像直 浙江大学硕士学位论文一嵌入式系统代码压缩技术的研究 接运行压缩后的代码。解压缩会对处理器的流水线产生很小的延迟，但是其影 响被取指延迟以及其它延迟所掩盖。对于绝大多数应用，c o d e p a c k 带来的性能 影响是可以忽略的【4 ，1 9 1 。 值得一提的是，i b m 的工程师发现每一条p o w e r p c 指令的高半字( 操作码 就在其中) 和低半字( 其内容通常为操作数、偏移量或掩码) 的分布频度是不一样 的。对它们分别使用不同的压缩算法会使压缩效果比仅使用任何单一算法要好， 因此c o d e p a c k 对每个程序指令的高1 6 位和低1 6 位分别进行压缩。 c o d e p a c k 和其它指令集技术一样，可以提供大约2 0 到3 0 的空间节省。 4c c p r a n d r e w w o l f i 和a l e xc h a 订抽提出的由砌s c 处理器可以执行压缩代码的体 系结构，称为c c r p ( c o m p 心s s e dc o d e s cp r o c e s s o r ) 。他们使用h u 胁锄的编 码方式在编译过程中对程序代码进行压缩，压缩后的代码存放在指令存储器里。 运行时，压缩的代码会被实时地解压为正常的i u s c 指令并放入指令缓存器中， 这就需要在指令存储器和指令缓存器之间放置相应的解压缩模块【。 小m i n h u b m u 戗e s t a ny l i a o 等人提出了一种在软件级别支持代码压缩与解压缩的方法。他 们找出程序代码中相同的指令序列，称之为m i n i s u b r o u t i n e ，进而建立字典对这 样的指令序列进行索引，最后用一条类似调用子程序的指令来代替被索弓 的指 令序列。这样，原来的程序由未压缩部分和索引调用指令组成“ 。 m i n i s u b r o u t i n e 的方法最大的优点在于他是一种软件级别上的压缩方案， 在各种流行的处理器上均可以使用，且不需要任何额外的硬件代价。 m i n i s u b r o u t i n e 的方法需要找出重复出现的一组指令序列以获得较好的压 缩率，且每组中指令序列数目愈多压缩率就越大。 童r e p e 龋v ec o d ec o m p r e 略o c h a r l e sl e f u 唱y 等人对s p e cc i n t 9 5 基准测试程序进行了研究，针对l i a o 等人的m i n i s u b m u t i n e 的问题进行了改进，采用了更小的c o d c w o r d ( 1 6 b i t 或更 浙江大学硕士学位论文一嵌入式系统代码压缩技术的研究 小) 对程序进行字典压缩，这种方法使得在仅有一条指令重复率较高的情形仍 然可以进行压缩。 综上所述，代码压缩技术本质上说使用更少的代码来表述程序的语义，完 成程序的功能。正如我们所见到，为达到压缩代码的目的可以在不同层面的上 采用不同的方法，上面所介绍的一些压缩技术也只是其中的一部分而已。 2 3 代码压缩技术的评价标准 ( 1 ) 代码压缩技术顾名思义就是为了有效地减少代码长度，使得嵌入式系统 获得成本与功耗的降低。因此“压缩比”成为了首要的评价标准。“压缩比”定 义为压缩后的代码长度与原始代码长度的比例。 压靴= 燃 ( 式2 1 ) 压缩比是一个可量化的客观评价标准，但它并不能很好地用来比较不同的 压缩方法。特定的压缩比是针对特定的指令集架构、特定的编译器、特定的编 译优化参数以及特定的基准测试程序而言的一个特定的量化参数。因此，对于 压缩方法的评价不能完全简单地依靠“压缩比”。 ( 2 ) 代码压缩技术对于性能上带来的降低程度是另外一个重要评价标准。例 如：解压缩过程的时间开销等。以性能损失换得程序代码的压缩是必须考虑的 一个问题，开销过大意味着毫无实用价值，再高的压缩率也成为空谈。 ( 3 ) 如果是硬件支持的解压缩技术，其复杂度可能是其具体实现所不得不面 对的问题。复杂的硬件支持可能需要耗费一定的硅面积，这需要与压缩代码所 带来的存储器节约做很好地设计折衷。同样与第二个评价标准殊途同归，复杂 的电路很难避免对处理器性能造成一定的影响。 ( 4 ) 如果是针对现有的指令集或处理器体系结构提出的代码压缩技术，就无 可回避一个兼容性与易用性的问题。一个好的代码压缩方案是不会对现有的嵌 入式系统的体系结构、编译器以及开发工具等做过多地设计改动。大量的结构 变动无异于一个全新的设计，其潜在的设计成本与兼容性成本是巨大的。 浙江大学硕士学位论文一嵌入式系统代码压缩技术的研究 第三章基于a i m 指令集结构的代码压缩 3 1a r m 指令集体系结构 3 1 1 删指令集综述 ( 1 ) a r m 指令集特点 标准的a r m 指令都是3 2 位宽，在存储器中以4 字节的边界对齐。删指 令集具有以下特点1 4 】： l o a d s t o r c 体系结构 4 三地址的数据处理指令( 两个源操作数寄存器和结果寄存器独立设定) 每条指令都是条件执行 毒具有多寄存器l o a d 和s t o r c 指令 单时钟周期内执行单条指令完成一项移位操作和一项a l u 操作 z 0 通过协处理器指令来扩展a r m 指令集 a r m 指令集同其他商用的r j s c 处理器指令集相比具有更多的指令格式。 这样的指令集体系结构使得译码更加复杂，但同时也带来了较高的代码密度。 ( 2 ) 删微处理器寄存器结构 a i t m 处理器共有3 7 个寄存器，被分为若干个组，这些寄存器包括【1 4 ： 43 1 个通用寄存器，包括程序计数器( p c 指针) ，均为3 2 位的寄存器。 6 个状态寄存器，用以标识c p u 的工作状态及程序的运行状态，均为 3 2 位，目前只使用了其中的一部分。 同时，a r m 处理器又有7 种不同的处理器模式，在每一种处理器模式下均 有一组相应的寄存器与之对应。即在任意一种处理器模式下，可访问的寄存器 包括1 5 个通用寄存器( r o r 1 4 ) 、一至二个状态寄存器和程序计数器。在所 1 2 浙江大学硕士学位论文一嵌入式系统代码压缩技术的研究 有的寄存器中，有些是在7 种处理器模式下共用的同一个物理寄存器，而有些 寄存器则是在不同的处理器模式下有不同的物理寄存器。 r o r 1 r 2 用户模i r 3 r 4 仅供系瑚 r 5 r 6 r 7 r 8 q r 8 r 9 q r 9 r 1 0 _ 阳 r 1 0 r q r 1 1 r 1 2 _ 柏 r 1 2 r 1 3s v c r 1 3 - a b 川r 1 3 - l r q i r 伯q r 1 3 r 1 4s v c r 1 4 - a b t r 14 _ _ i r q i r 1 4 q r 1 4 r 1 5 ( p c ) 菡磊_ c p s r s p s rn 。ls p s r _ s v c i8 9 8 r - a 队p 竺坐刈 用户模式 竹q 模式 s v c 模式a b o r t 模式 j r q 模式 来定义模式 图3 1 a r m 寄存器 ( 3 ) a r m 指令集的具有丰富的寻址方式 。立即寻址 寄存器寻址 毒寄存器间接寻址 4 基址偏移寻址 0 堆栈寻址 0 块拷贝寻址 相对寻址 浙江大学硕士学位论文一嵌入式系统代码压缩技术的研究 a r m v 4 指令集是a r m 指令集发展经历了v l 、v 2 、v 2 a 、v 3 、v 3 g 、v 3 m 后第一个具有全部正式定义的体系结构版本，也是目前嵌入式处理器领域常用 的一种删体系结构版本，支持它的a 跚处理器内核包括s t r o n g a r m 、a r m 8 、 a i t m 8 l o 等【1 4 】。 ( 1 ) a 】r m 指令集分类 r l 小，4 指令集包含：数据处理指令、l 0 8 d s t o r e 指令、跳转指令、程序状 态寄存器处理指令、协处理器指令、异常产生指令 镰数据处理指令 a d d 、a d c 、s u b 、r s b 、s b c 和r s b a n d 、o r r 、e o r 和b i c m o v 和m 、仆i c m p 和c m n t s t 和t e q 乘法指令 4l o a d s t o r e 指令 单寄存器存取指令 多寄存器存取指令 存储器和寄存器交换指令s w p 4 状态寄存器与通用寄存器之间的传送指令 状态寄存器到通用寄存器的传送指令m r s 通用寄存器到状态寄存器的传送指令m s r 跳转指令 转移和转移链接指令( b 、b l ) 4 异常中断产生指令 软件中断指令s 兀 浙江大学硕士学位论文一嵌入式系统代码压缩技术的研究 4 协处理器指令 协处理器的数据操作 协处理器的数据存取 协处理器的寄存器传送 ( 2 ) 触l m v 4 指令集编码 a 鼢肿4 指令集的二进制编码如图3 2 所示【1 3 】 m p 一q h n b d j | 括 3 13 02 9 2 82 7 2 b2 52 4 2 32 22 12 0 1 9 1 8 1 7 1 e 1 5 1 4 1 3 1 2 1 1 1 0 0 80 7 0 5 0 40 3 0 20 1o o c o n d o d a esr nr ds h m a m o u n t8 h i nor m ! c o n d ”0 o 010 xxxxxxx xxxxxxxxxxo c o n d ” sr nr d r sos h m1 r m n d l lo o 0 o n d l lo o ox xxxxxxxxxxxxxxx n d l lo 01o d d es 剐 i m n “i a i e n 一” 0 01o oxxx xxxxxxxxxxxxxx o 一”o o1r10 s b o i m “培d i 刮b n qp u bwlr nr di m m e d l d f e 科lo11p u br nr ds h i na m o u r i ts h l rr m n d xxxx x x xxx xxxxxxxxx1 n d l10 0swl r n r i m r l m n d i 1o1l n d l l11o p unwl c r d c p _ n u m 0 f f s e i c 一”o d d e lc r nc r d c p u mj o p c o d e 2o c r m n 一”1110 o d o d d e llc r nr dc p _ n u mo 口c o d e 2 i1c r m n 一1 l xxxxxxxxxxxxxx xxxxxxxxx xxxxx 注：【l 】条件码( n d ) 爿二允许等于1 11 1 图3 2 a r m v 4 指令集= 进制编码 a r m 指令集不同寻常的特征是每条指令都是条件执行的。条件转移是绝大 多数指令集的标准特征，但a r m 将条件执行扩展到所有的指令