i春秋作家：immenma
在说些什么实现的东西之前,笔者仍然想话唠唠叨下虚拟机这个话题,一是给一些在这方面不甚熟悉的读者简单介绍下虚拟机的作用和包治百病的功效,二来是题头好好吹一吹牛,有助于提升笔者在读者心中的逼格,这样在文中犯错的时候,不至于一下就让自己高大上的形象瞬间崩塌。
是的，当前虚拟化技术已经在计算机及互联网中烈火燎原了，从服务器到个人PC上直至手机甚至手表上，几乎都离不开它的身影，尽管当前说起虚拟机，更多的人想到的是Java是运行在JVM上的，而JVM是个虚拟机，或者大家非常熟悉的虚拟机软件VMWare或者是Virtual
Box，KVM等大牌虚拟机软件。但实际上虚拟化技术早而有之甚至不那么容易界定明显，例如，我们在PC上想玩红白机游戏，那么FC模拟器就是个虚拟机，我们想在PC上做做电路实验，试试我们在89C51上编写的跑马灯好不好使，proteus也是虚拟机,甚至于做做虚拟仪器的业内标杆软件Labview,这个无需解释估计是最直观的虚拟机了,大多数虚拟机本质上是执行在宿主的一款程序,对宿主机CPU没办法直接执行的指令字节流或别的一些什么东西进行解释执行,最终达到某种功能或目的的一种程序,那么按照这种推论,浏览器里的JavaScript,Lua脚本语言运行环境,或者是Python算不算虚拟机呢,实际上大多数人更愿意使用解释器来描述这些语言的执行环境,但是不管怎么说,乍看之下其似乎也完全符合虚拟机的特性,不管是文字解释还是将代码编译为字节流再进行解释本质上并没有多少区别,因此笔者认为将它们归为虚拟机也一点毛病也没有,纠结这些毫无意义.
那么简单来讲虚拟机到底是什么呢,简单来说,假如你只会中文而不会英文,某天一个老外要和你交谈,语言不通怎么办,请翻译啊,那么,这个翻译的作用就像虚拟机.
<ignore_js_op>
为什么我们要设计一个虚拟机
相信在文章的开篇就有人跳出来提出这个问题了,为什么要自己做个虚拟机,现在那么多现成的执行体系不好么,为什么要重复造*,何况这个*还未必有别人的圆,当然笔者写这篇文章的目的也并不是吹嘘自己写的虚拟机有多好,但笔者相信只要你在计算机开发的游戏引擎或二进制安全或图形图像或是人机交互PLC工控…等等等领域之一混的足够久,你就会知道自己拥有自己的一套虚拟机系统所带来的好处和必要性了,笔者相信时间和经验会告诉你做一件事有没有这种必要,而别人说再多话也是别人说的,当然,就像别人设计的虚拟机再好也是别人的,自己设计的虚拟机再挫也是自己的.当你在一套虚拟系统中有所疑惑或者是需要额外的功能实现时,你就知道”就算别人的花儿再漂亮,自己种的终归是自己种的”这句话的深刻含义了.
那么,一套虚拟机系统有什么好处呢?笔者总结了部分功能.
- 跨平台使用,在这台机器上是这套虚拟机指令集,在另一套计算机上也是同样的虚拟机指令集,一次开发,永久奔放,当然,你必须也保障目标机能够移植你的虚拟机。
<ignore_js_op>
-
执行环境可控，毕竟每一条指令都由虚拟机负责解释执行，这意味着可以对程序执行的每一个流程进行控制，虚拟机作为一个沙盒环境，对权限控制，调试都有诸多好处。尤其是在权限的控制中，可以避免一些恶意程序对原生系统的破坏，当然，这有没有让你有种主宰世界的感觉。
- 二进制安全，当然目前最让人头疼的是一款软件刚发布又让人给破解了，当然，破解工作必然的涉及到了软件的逆向工程，逆向工程就必然和指令集运行环境有所关联了，当然早期的反逆向技术主要花心思在如何检测调试器上了，然而当开发了一种检测调试器的手段，逆向人员很容易就找得到应对的方法，因此，检测调试器的手段发展到今天基本作为一种备用手段了，虽然说理论上世界上不存在不能被破解的软件，但是当一款软件的破解难度远远大于其本身价值的话，那么这款软件被破解的可能性就变得很低了，那么为什么软件容易被破解呢，很多时候是因为大家都熟悉这套框架这套指令集这套运行原理，用的人多了，资料就多了，资料多了，那程序就没啥隐私了，但是如果自己设计一套全新的指令集和框架结构的虚拟机的话，要破解运行在这个虚拟机上的软件，就意味着攻击者必须熟悉这个指令集和框架的原理，好了，现在问题就变成了当你面对一个运行在全新的架构全新的指令集上的程序时，你有几年的青春可以挥霍了，当前反调试技术并非是让人做到无法破解，而是需要花大于程序本身的价值的精力去破解，正因如此，虚拟机尤其是自己设计的虚拟机成了反逆向分析中的“宠儿”。
<ignore_js_op>
当然如果说读者读完这篇文章就能马上撸出一个虚拟机+完整的编译系统,那真是难为笔者了,这也就是为什么题目中笔者加了导引两个字,这是一个庞大的工程,笔者无法在寥寥万余字中将每一个技术细节都说明白,当中涉及的东西太多不仅在书里更要在实现中去体会而不是纸上谈兵(相信我,那些把编译理论吹得稀烂的大多自己也没有写过编译器最多就使用LLVM描了个边,当他们真正从底层去处理词法和语法上的问题基本也是一脸懵,那一刻就会体会到真正要他们解决的玩意书和那套听不懂的装逼理论并不会告诉他们),虽然书不能帮你解决所有问题,但笔者仍然向有兴趣写编译器虚拟机的推荐\<\<编译原理\>\>\<\<游戏脚本高级编程\>\>这两本书,前者有一套完整的编译理论的构架对学习编译优化非常有好处,当然其实很大一部分理论用不到,后者那本书则是结结实实的写了一套完整的虚拟机和编译器,不过也厚的多,足足2本书近千页的内容(当然,还是无法完全提及每一个技术细节:),但非常有参考价值值得一读.最后是笔者的这篇文章了,是的,虽然无法让读者直接写出个编译器和虚拟机,但是至少可以说个大概,2w字的篇幅说长不长说短不短,半个小时就能读完,买不了吃亏买不了上当,可以让你初略地了解下虚拟机和编译器到底是怎么回事.
虚拟机开发前的准备工作
在码农界设计一个虚拟机一直被当做高端大气上档次的事.然而事实上虚拟机的设计并没有什么复杂的内容,乃至于说解释器里的语法和词法分析都比虚拟机复杂的多,当前,假如你想设计一款和VMWare或者Virtual
Box一样的的虚拟机软件,那当我之前的话没说,在本文中,笔者通过设计一款较为简单的虚拟机程序并且在虚拟机完成我们需要的功能.
因此,在开始这个项目之前，我们首先要确立以下目标
-
我们要虚拟机主要功能是什么，功能的不同，将很大程度改变虚拟机的架构，例如是我们的虚拟机实作为游戏引擎的脚本控制，那么我们的指令设计就应该尽可能的精简稳定并便于优化，这样使用虚拟机设计的游戏引擎才不至少不至于在虚拟机方面卡成PPT让每一个玩家骂娘，而如果是做算法的反逆向保护，那么我们就要好好的藏好我们指令集“真正的”功能，甚至不做优化让破解者绕圈圈，这个时候冗余设计反而有助于保护我们的算法。
-
我们的虚拟机开发环境是什么，用在什么地方，当然，这包括使用什么语言，什么环境来开发我们的虚拟机都在考虑的范围之内，当然，当前相当一部分有名的虚拟机环境都选择使用C语言进行开发，这有很多好处，首先目前绝大部分的运行环境都提供C语言的编译器，虚拟机写好后，可以非常方便地在多平台进行移植，再者只要编译器给力，C语言编译出来的指令流相对执行效率优秀，这对容易带来明显性能损失的虚拟机尤为有利，最后，C语言学习较为容易，学习成本不高，能让我们把更多的注意力放在“如何实现”而不是“如何让别人觉得我代码语法糖写的有多牛逼”上。
-
我们的虚拟机的指令集如何实现，当然这是一个笼统的说法，这还包括如何我们虚拟机如何对内存进行管理，需要哪些寄存器，这些寄存器分别由什么用，指令的数据结构是怎么样的之类多种的问题，不过不用担心，我们有很多现成的指令集可以供我们参考,例如MIPS这种指令集至今仍作为众多CPU粉乐于用虚拟机模拟实现的指令集,这原于这个指令集的精简并容易实现,因此每年的毕设上,总能看到相关的设计论文,相对的x86
ARM指令集就复杂得多,但不用担心,我们可以学习他们部分的实现,管中窥豹可见一斑,即使我们只完成了一部分实现,对于我们的虚拟机而言,大部分的功能也足够实现了. -
如何设计调试器方便我们的虚拟机调试,这个是非常重要的一点,假如你设计的虚拟机没有对应的调试方案,那么即使是作为虚拟机作者的你编写的虚拟机程序进行亲自调试,也将会是一场噩梦,因此在你真正动手开发虚拟机之前,你最好想好你的调试器如何架构在你的虚拟机之上.
-
虚拟机的运行方式及IO,简单来说就是你得想好你的虚拟机如何去解析指令执行,另外虚拟机执行完后也不能光运行啊,算法把结果算出来了总得把结果输出来,这就涉及到了虚拟机和本地代码的数据交互,这些都需要提前考虑好.
- 虚拟机的异常处理方式,老规矩,除0异常,越界访问,无效指令,内存不足…不管你设计的虚拟机再如何的优秀,如果没有异常处理方式,那就是一句话”怎么死的都不知道”,因此不管你设计哪一种虚拟机,你最好先把算盘打好当出现这些异常的时候,你的虚拟机应该如何应对.
<ignore_js_op>
架构一个虚拟机
给虚拟机项目个名字和LOGO
项目开始的第一步,自然没多少难度,不过但凡干大事者,都要先立个名号,虽然说这并不算什么大事,但笔者自认为是一个比较中二病的人,因此,左思右想还是得给这个虚拟机项目取个名字.比如终结者,双子星,地球毁灭者,宇宙收割机之类的,不过好像又过了那个年纪,还是务实一点,当然,本篇文章的事例虚拟机取自笔者早前已经写好的一个虚拟机项目,它被用在游戏引擎,嵌入式系统控制及UI界面当中,名字是早已订好了叫StoryVM,属于StoryEngine(游戏/图像引擎)的一部分
<ignore_js_op>
至于为什么叫StoryVM,笔者自己也不是很清楚.就觉得叫着舒服,当然,本篇文章的目的也是告诉大家这个虚拟到底如何实现的,读者们如果有兴趣,不妨也花点时间为自己的虚拟机项目起个霸气的名字和LOGO,万一火了,那么就可以为这个虚拟机名字怎么来的想个故事了.
认识冯诺依曼结构和哈佛架构
在开始部署我们的虚拟机程序之前,我们先来复习一下计算机专业的经典知识点,冯诺依曼的计算机体系结构和哈佛结构,相信计算机系的看官们应该并不陌生毕竟多多少少都有几位是栽在他们手上的
<ignore_js_op>
冯诺依曼和哈佛结构主要的不同点是程序和运行数据是否是存储在同一个空间中,实际上两种体系虚拟机都能够实现,毕竟时间有限,因此,笔者无法将两种体系的虚拟机实现都说一遍,出于演示和尽可能偷懒原则,笔者在本文中采用的是哈佛结构体系的虚拟机架构,为什么使用哈佛结构(程序和数据分开存储)呢,其中有以下几点好处
-
从执行安全性考虑,方便进行越界检查,当指令地址不在指令的存储范围内时,肯定是无效指令越界访问了.
-
二进制漏洞十有八九都是越界访问或者缺少边界检查的数据修改造成的,程序修改程序造成远程代码执行的事儿咱们也不是第一天见过了,因此,分开存储有利于提高脚本的安全性与可控性.
- 简单啊,写起来方便啊,偷懒舒服啊,分开存储意味着很多时候你不必再使用多个数据费力寻找数据的真实偏移量了,实际上笔者在虚拟机的实现过程中,将字符串,文本,内存,寄存器空间全部分开存储.
那么,这个虚拟机的数据空间看起来是怎么样的呢:
<ignore_js_op>
是的,笔者将虚拟机的各个数据都进行分类存储,一来不仅便于访问,二则方便管理及权限控制,只要设计得当,常量区的只读数据就能得到很好的保护,程序代码区也不会被修改,需要注意的是,笔者仍然将栈空间和堆空间设计在同一空间里,当然这是有一定原因的,这点我会在后面的章节中说出原因.
元数据
那么从现在开始,我们就要开始接触一些编码方面的东西了,当然,为了保证这篇文章尽可能的受众面广,笔者并不打算过于地强调用何种语言来编写这个虚拟机,但笔者编写这个虚拟机使用的是C语言进行开发的,因此在很多的地方,仍然不可避免需要使用C语言中的一些代码对功能的实现进行说明,明显的,本文并不打算写有关C语言怎么写之类的问题,因此如果读者不熟悉C语言的话,笔者仍然建议读者自行查阅相关资料.
在虚拟机开发的第一步,我们先来了解一下元数据
什么是元数据呢,简单来说就是虚拟机能够定义的最小单位,我们以C语言为例,C语言排除结构体和修饰符外,那么能够定义char
short int float double
long….等几种类型,其中,char类型不论在哪种编译器下必定占据一字节,排除位域或编译器额外的实现,char是C语言能够定义的最小数据大小,因此我们称char为元数据类型
而在Basic语言中,定义则简单的多,可以直接使用dim a=3141,或者dim b=”hello
world”来定义类型,在这个时候,类型所需的内存空间不再是一个定数.在这里定义的元数据类型可以是一个整数小数或者是字符串类型.
在很多的情况下,我们把类似于C语言的类型称为强类型,表示类型间无法直接相互转换,而Basic则称为弱类型,不同类型间可以相互转换.
当然,对于那些依靠CPU直接执行的指令,基本不会采用弱类型的数据访问方式,这将导致电路实现过于复杂,但是虚拟机完全可以采用弱类型的方式来编码数据的访问,这主要有以下几个优点.
-
编写程序时简便的多,这意味着开发虚拟机程序时不用花过多的心思在数据转换上
-
写起来方便,看起来直观,比如”Hello”+”World”这样的字符串相加运算,顺手
- 不需要再关注一些例如字符串类型带来的内存管理上的麻烦,这些都由虚拟机适时分配与回收(garbage
collection)
当然,弱类型带来了优点,缺点也不少
-
显然的,虚拟机的实现要复杂的多,必须考虑资源分配、深浅拷贝、垃圾回收等问题。
-
必定带来性能损失，尤其是面临深拷贝和垃圾回收。
-
不论内存管理如何优秀，这种分配回收机制都不可避免引发更多的内存碎片
-
对一些特殊类型的操作,比如字符串,可能需要额外增加一些关键字来加强对类型功能的使用,比如字符串不可避免需要引入strlen函数统计其长度,或者用[]运算符修改其某个字符.
- 容易引发语法上的歧义，例如一个字符串类型和一个整数类型相加，如何定义？例如
“数字:”+4294967295的结果应该是字符串’’数字:4294967295”么?,要知道,4294967295在32位类型中和数字-1是一样的,如果”数字:”+4294967295是字符串”数字:4294967295”那”数字”+-1又该是什么,你可以说给类型定义有符号还是无符号的标识啊,那么好,定义一个类型为100,那么这个100是有符号还是无符号的,你可以说加修饰符来修饰啊,那问题又来了,既然要加修饰符,那我还用弱类型做什么,绕个弯子再自找麻烦么.
总结了弱类型的几个好处,但同时我们也发现其糟糕的地方也不少,那我们虚拟机需要设计成支持弱类型的访问么,当然要,弱类型有如此多的好处,不能因为他存在某些缺点就全盘否定,但这也是为什么本章标题笔者起名为元数据而非”都听好了,我们要设计一个弱类型数据访问型的虚拟机”,为了规避弱类型访问的一些缺点,我们需要对虚拟机的数据结构进一步改造,我们可以这样规定,一个元数据(可能是常规寄存器,堆栈里的某一数据)可以是一个整数,小数,或者是字符串或数据流类型,但是,不同的数据类型不能够直接进行运算,需要使用特殊的指令进行操作,这样我们就解决了弱类型带来的歧义的问题.
说完了理论,我们来看看实践,我们先来看看C语言如何定义一个元数据
typedef struct
{
int type;
union
{
char _byte;
char _char;
word _word;
dword _dword;
short _short;
int _int;
uint _uint;
float _float;
string _string;
memory _memory;
};
} VARIABLE;
观察结构体VARIABLE定义,其中type表示该变量的类型,在该虚拟机中,有如下枚举定义
typedef enum
{
VARIABLE_TYPE_INT,
VARIABLE_TYPE_FLOAT,
VARIABLE_TYPE_STRING,
VARIABLE_TYPE_MEMORY,
} VARIABLE_TYPE;
VARIABLE_TYPE_INT,表示这个数据是一个整数类型定义,
VARIABLE_TYPE_FLOAT表示这个数据是一个浮点类型,
VARIABLE_TYPE_STRING表示这是一个字符串类型定义
VARIABLE_TYPE_MEMORY 表示这是一个数据流类型
接下来是一个联合体,数据类型公用一块内存尽可能节省一个元类型占用的内存空间
数据表达方式
如果在高中数学的角度上来说,6和6.00这两个数字并没有什么区别,6.00后面的两个0可以省略,但是在很多的编程语言当中,6和6.00有着本质上的区别,6是一个整数,6.00是一个浮点数,它们在内存中的布局常常天差地别,同时,6/4和6.00/4的结果也截然不同
笔者在本章开头写这个,目的并不是给读者讲解整数和浮点数编码的区别,而是希望提及一点,数据的不同写法所表达出的数据也截然不同,那么StoryVM支持几种数据呢,在上一章节我们已经讲过元数据的组成方式,从结构体定义我们可以看到,支持char
short int uint float string memroy几种类型(word ,dword..本质上是unsigned
short和unsigned
int),但是笔者并不打算让StoryVM关注于如此多的类型,因此,在笔者设计的StoryVM中,仅仅支持int
float string memroy四种类型
读者可能会表示疑问.如果我需要表示一个无符号数,或者只需要表示一字节那怎么办,int类型不是只能表示有符号整数呢
其实按照读者的设计,在方便的时候,数据长度可以宁多不宁少,int类型完全可以用来表示字节类型,无非是使用时自己注意点将它当做字节类型来用时不要超过255就行了,而有符号无符号类型在内存中表示其实并没有什么出入,例如,-1和4294967295在内存中并没有什么区别,而有符号数适用面更为广泛,至于到底显示出来时是有符号或者是无符号,完全可以靠自己把握.
在StoryVM中,如何使用汇编表示一个数据类型呢
显然的 int类型可以直接使用数字来表示,例如
12345,这个是一个合法的int类型,当然,为了方便,还引入了十六进制表达,例如0xffffffff也是一个合法的int类型,当然,需要注意的是StoryVM最大支持32位的整数类型,这也意味着十六进制范围是0\~0xffffffff,最后是字符类型,例如‘A’表示字符A的asc码值,也是一个合法的整数类型,’B’表示字符B的ascii码值…..以此类推
Float类型应该无需笔者多说了,1.0,3.14,6.66都是合法的float类型
String也就是字符串类型和C语言的字符串表示保持一致,”Hello
World”这就是一个合法的字符串类型,用双引号包含,当然,和C语言有些不同的是,字符串类型中仅支持\r\n\t三种类型转义
最后是数据流类型,这个是StoryVM中自定的一种数据类型,理解起来并不复杂,例如
\@0102030405060708090A0B0C0D0F\@这就是一个数据流类型,一个数据流类型使用两个\@包含,当中的文本是一个十六进制表示的数据流,两两为一对为一字节,这也就意味着当中的字符数必须在范围0-F中,并且必定是偶数个.
指令集数据结构
在开始设计具体的指令前,我们先来考虑下虚拟机指令集如何设计,当然,当前的指令集大多以如下的模式设计:
<ignore_js_op>
其中,操作码表示这条指令的具体作用,例如x86汇编中的MOV eax,1中的mov就是操作码
紧接在操作码之后的是操作数类型(或者也可以叫参数类型),例如上上面这条汇编指令中一共有2个操作数(参数),分别是eax和数字1,它们分别表示一个寄存器类型和一个立即数类型,最后是操作数了,也就是我们常说的参数.
当然,上述的规则适用于大多数的指令编码格式,对于一些非常常用的指令,甚至会将一些操作数给”集成”到操作码中,例如上述的MOV
eax,1指令中,mov
eax,被直接用E8代替,而操作数1则直接使用一个dword来设置,在这条指令中,只有一个操作码和一个操作数.
如此的设计可以保证编译的程序尽快能的小,但是作为代价,执行对于的指令集的CPU或虚拟机也需要设计更多的实现而变得越来越复杂
设计出x86类似的复杂指令集需要耗费大量的心血,但在我们的虚拟机系统中,我们无需使用如此复杂的指令集设计
笔者斟酌了定长指令和不定长指令的一些特点,设计出如下的一套指令集规范
-
操作码以1字节进行标识
-
接着是3字节的操作数类型
- 依据指令类型最终决定之后跟几个操作数,每个操作数都是一个4字节宽度的类型
<ignore_js_op>
这意味着我们的指令设计每个指令至少占4字节宽度,并且最多只能接受3个操作数.
寄存器设计
在CPU设计,寄存器用于数据的暂存,在电路设计中,这不同的寄存器被赋予不同的意义,在笔者的虚拟机架构中,并不需要关注电路设计如此复杂的内容,但笔者仍然将寄存器设计分为两种寄存器,一种是临时数据寄存器,一种是特殊寄存器.
其中,临时数据寄存器本质上就是之前提到的元数据,它与堆栈中的元数据并没有别的区别,访问临时寄存器用R+寄存器标号的方式访问,在笔者设计的虚拟机中,每个虚拟机实例一共有16个这样的临时寄存器,用R0\~R15对他们进行访问.
之后是三个特殊寄存器,SP,IP,BP,如果有阅读过汇编代码的读者应该对这三个寄存器再熟悉不过了,SP永远指向栈顶,IP寄存器指向当前正在执行的指令,BP更多是为了支持函数调用中寻找参数的偏移地址用的,提前将它加进来为后期设计高级语言的编译器做下准备
这三个特殊寄存器都是dword类型,这意味这我们的虚拟机最大的寻址范围是4GB.
堆栈数据结构
在虚拟机的堆栈是由元数据构建起来的,当然,栈的增长方向为高地址向低地址,而堆的方向则是低地址到高地址
<ignore_js_op>
在StoryVM中,一般使用GLOBAL[索引号]访问堆栈的元数据,一般使用LOCAL[索引号]来访问栈数据
当然
GLOBAL[BP+i]和LOCAL[i]是等价的,LOCAL表示在偏移量加上一个BP寄存器的值,主要用来访问参数和临时变量.
虚拟机是如何运行的
实际上不仅仅是虚拟机,目前我们见到的大部分的计算机架构都可以把程序当做一张很长的写满指令的纸条,而计算姬要做的就是从头读到尾,并从头执行到尾,我们的虚拟机同样遵循着这样的”执行守则”
当一个脚本被编译为指令流后,虚拟机依次读取一条指令然后执行,当然,指令也并不是完全按照顺序读取,因为指令当中也包含一些”跳转”指令,这将会让虚拟机”跳转”到纸条的其它地方执行指令.
当然,虚拟机设计是一个庞大的需要深思熟虑的系统,如果考虑IO(输入输出)及中断,多线程的线程调度的话,我们无法简简单单用一个字条来描述一个虚拟机的执行过程,但是在文章的开始,初学者依照这个比喻,对虚拟机是如何运行的有个初步的概念.
<ignore_js_op>
虚拟机指令集设计
千里之行始于足下,MOV指令设计
笔者在最初设计StoryVM的时候,指令只有短短的几条,一个指令集的完善,不能仅仅是靠初期想当然的脑补,在StoryVM部署到实际的项目之后,笔者再不断去添加那些需要的指令,当然,在本文当中笔者并不打算演示所有的指令实现,笔者决定挑选几个非常具有代表性的指令进行讲解,当然,首当其冲的就是mov这条指令,这也就是为什么本章笔者并不把标题起为虚拟机指令设计,笔者认为,有几个特殊指令是值得专门花费一章节去讲解的.
那么,MOV指令是怎么回事,有什么用呢
其实非常简单的说法,这是一个数据传送(赋值)指令,比如下面的算式
i = 314
就是把变量i赋值为314
当然,如果把这条语句写为StoryVM的汇编代码形式,那么就是
MOV\ i,314
当然,i在汇编中并不存在,假设它是一个全局变量,那么它应该在堆中,假设它在GLOBAL[0]的位置,那么,应该写成
MOV\ GLOBAL\lbrack 0\rbrack,314
这样,GLOBAL[0]就被正式赋值为一个整数,为314,当然看到这里,你应该会觉得MOV指令非常简单,例如,下面的汇编语句即使笔者不说读者也很容易理解要表达的意思
MOV R1,123 //R1寄存器赋值为123
MOV R2,3.14 //R2寄存器赋值为3.14
MOV R3,”Hello World” //R3寄存器赋值为字符串”Hello World”
MOV R4,\@0102\@//R4寄存器赋值为两字节长度的0x01 0x02
上面的语句没什么问题,其中,R1和寄存器R2顺利地被赋值到了元数据寄存器中,但是R3和R4不得不提及一下,当一个元数据被赋值为一个字符串和数据流类型时,不可避免地涉及到了内存分配的问题,但还好,这实现起来并不复杂,当一个寄存器被赋值为了字符串或者数据流类型时,从内存池中划出一块内存将字符串或数据类型存储进去,然后这个元数据中指定一个字符串指针指向它就行了.
<ignore_js_op>
那么我们来看看下面的两个语句
MOV R1,123
MOV R1,”Hello”
先将寄存器R1赋值为123,然后再将字符串赋值到寄存器R1中(在内存池申请内存,然后将元),这没什么问题,但是我们将两个语句换一下,那么问题就来了
MOV R1,”Hello”
MOV R1,123
首先,R1寄存器被赋值为”Hello”,在这之后,它又被赋值为123,这将会带来一个问题,如果将R1直接赋值为123,为字符串hello在内存池分配的空间将得不到释放,因此,当一个字符串或是数据流时,在内存池分配的空间都应该被释放
MOV指令和内存管理机制
从上一章节MOV的讨论中我们可以看出当一个元数据由一种类型变换为另一种类型时,一是可能伴随着内存的分配,既然有了分配那就应该有回收机制,例如当一个元数据由int类型变为了string类型,那么,在内存池中必须申请一块内存区域用于存储字符串类型,而由string类型变为了int类型,将伴随着string类型所占用的内存释放,也就是内存的回收,那么在什么时候内存需要分配而什么时候需要回收呢,笔者总结了以下几种情况
-
当一个数据由其他类型变为了string或者是memory类型时,需要在内存池中为其分配内存空间.
- 当一个数据进行拷贝时,需要为其分配内存空间
即如下代码
MOV R1,”ABC”
MOV R2,R1 //需要为R2分配内存以进行字符串类型的拷贝
-
当一个元数据由string或memory类型变为其它类型时,当然,这也包括string类型变为memory或者是memroy类型变为了string类型,需要对原内存进行回收
- 当一个元数据的长度发生改变时,例如下面语句
MOV R1,”Hi”
MOV R1,”Hello”
那么,R1所在的字符串所在内存可能因为字符串长度的改变需要进行重新分配,需要分配与回收
- 最后需要提及的一点是,当MOV指令对特殊寄存器进行操作时,不涉及内存的分配与回收机制,毕竟在StoryVM中,特殊寄存器(SP
BP
IP)都是int类型,如果将特殊寄存器赋值为其它类型,虚拟机将会抛出一个异常并结束运行.
因为采用了这种”元数据”的存储方式,对于字符串及数据流类型,不可避免地就需要好好思考下如何管理内存了,毕竟内存泄漏在虚拟机的执行过程中是决不允许的,谁也不希望自己的程序跑着跑着内存就被一点点吃光最后导致崩溃.这种内存管理机制我们常常称之为GC(garbage
collection 垃圾回收机制)
不过在StoryVM中,我们只要遵循并注意这个”元数据”的类型切换时内存的管理就可以避免内存泄漏了,除此之外我们也注意到了,内存的回收分配机制,是一个非常耗费性能的调度机制,并且优化的难度大且难以避免,这也难怪在网上经常看得到对java这种重度依赖GC的语言被各种的吐槽,不过幸好在StoryVM中我们使用的是自行架构的内存池方案,避免了直接使用malloc/free等需要syscall的API额外调用开销.
当然,不仅仅是mov指令,所有对元数据造成修改(不管它是寄存器还是堆栈中的元数据)的指令我们都需要遵循上述的gc规则进行管理,否者结果必定是灾难性的,笔者使用mov指令做”抛砖引玉”之用,是因为Mov指令太具有代表性了,这个看上去最简单的指令,其实现却是storyVM中最复杂的指令,不过读者们也无需担心,在mov指令设计完成后,剩下的指令要设计起来就简单多了.
运算中的隐式转换
如果说让个小学生做个加减乘除运算,想必并也并不是什么复杂的事情,但在StoryVM上,我们考虑的就有点多了.
首先我们先来看看下面两个表达式
1+1=2
1+1.0=2.0
在数学的意义上,1和1.0是等价的,上面两个表达式同样是个等价的表达式运算,但是,在计算机当中,数字的不同表示方式可能导致截然不同的运算规则,首先,整数和浮点数的编码在计算机中是不同的这也就意味着
1+1是一个整数运算而1+1.0是一个浮点类型的运算
出于精度的考虑,在计算的结果中我们会以精度更高的表达方式进行表达,因此.当一个整数和一个浮点数进行运算后,它的结果也是一个浮点数.这点在StoryVM中需要被认真的考虑,与此同时的,在编程开发时,我们也常常使用的到浮点截断(去掉小数点后面的数值),因此,必须也设计相应的指令,将浮点数转换成整数,或者是将一个整数转换成浮点数的表示方式
在StoryVM的指令运算设计中,双目运算符(需要两个数字进行运算的操作符)遵循以下的运算规律
-
整数与整数运算,得到的也是一个整数
-
整数与浮点数运算,得到一个浮点数
- 浮点数与浮点数运算,得到一个浮点数
同时,浮点数的编码方式也需要被严格的考虑,如果因为编译环境的不同而导致浮点的编码方式不同,那么脚本在跨平台运行方面就会出现错误,但幸运的是,StoryVM使用C语言进行编写开发,而C语言的编译器基本都使用IEEE
754的标准对浮点数进行编码.
虚拟机中的加减乘除指令
在StoryVM中,参考了x86指令中加减乘除的助记符,加减乘除的汇编指令分别为
ADD SUB MUL DIV
写起来也基本类似,例如要实现1+1=2的这个表达式方式,指令编写如下
MOV R1,1 //寄存器R1赋值为1
ADD R1,1 //R1+1=2
在ADD R1,1指令中,ADD称之为操作码,R1,1称之为操作数,其中R1位操作数1,数字1为操作数2
实际上严格来说,ADD应该称之为加法操作码对应的助记符(mnemonic),R1是寄存器1对应的助记符,1是一个常量,当然,ADD函数遵循着运算隐式转换的规则,如果指令改为
ADD R1,1.0
那么寄存器R1对应的元数据类型也会相应的转换为一个浮点数据类型.
如果汇编器将ADD,R1,1这个指令编译成指令流,那么,它应该是下面这个样子的
<ignore_js_op>
参照之前提到的编码格式,其对应的指令流为0x02 0x02 0x01 0x00 0x00000001
0x00000001一共12字节.
下面,我们用opcode表示操作码.op1表示操作数1,op2表示操作数2,GLOBAL表示接受堆数据数据类型,LOCAL表示接受栈数据数据类型,REG表示接受寄存器数据类型,int,float,string,memory分别表示接受整形,浮点型,字符串型和数据流型常量.num表示接受一个数字,即可是是浮点类型也可是整数类型.
例如减法指令sub的描述如下
减法指令,op1=op1-op2,将操作数1的值减去操作数2的值,然后将结果赋值给操作数1
当然,操作数1必须是一个寄存器或者是堆栈中的元数据,因为常量不能被赋值,操作数2可以是一个寄存器或者堆栈中的元数据或者一个数字常量都可.
sub [reg,local,global],[num,reg,local,global]
依次类推,那么,在StoryVM中,几个运算指令的描述如下(为了说明方便,后面的表达式用C语言的运算符进一步描述)
add
加法指令,op1=op1+op2
add [reg,local,global],[num,reg,local,global]
sub
减法指令,op1=op1-op2
sub [reg,local,global],[num,reg,local,global]
neg
符号求反指令,op1=-op1
neg [reg,local,global]
div
除法指令,op1=op1/op2
div [reg,local,global],[num,reg,local,global]
mul
乘法指令,op1=op1*op2
mul [reg,local,global],[num,reg,local,global]
mod
余数指令,两个操作数必须为整数 op1=op1%op2
mod [reg,local,global],[int,reg,local,global]
shl
左移位指令,两个操作数必须为整数 op1=op1\<\<op2
shl [reg,local,global],[int,reg,local,global]
shr
右移位指令,两个操作数必须为整数 op1=op1\>\>op2
shr [reg,local,global],[int,reg,local,global]
and
与运算指令,op1=op1&op2
and [reg,local,global],[num,reg,local,global]
or
或运算指令,op1=op1|op2
or [reg,local,global],[num,reg,local,global]
xor
异或运算指令op1=op1\^op2
xor [reg,local,global],[num,reg,local,global]
inv
位取反指令,op1=\~op1
inv [reg,local,global]
not
逻辑非指令 op1=!op1
not [reg,local,global]
andl
逻辑与指令 op1=op1&&op2
andl [reg,local,global],[num,reg,local,global]
orl
逻辑或指令 op1=op1||op2
andl [reg,local,global],[num,reg,local,global]
pow
阶乘指令(op1为底数,op2为指数,结果在op1中) op1=op1_op2
pow [reg,local,global],[num,reg,local,global]
sin
正弦函数op1=sin(op2)
sin [reg,local,global],[num,reg,local,global]
cos
余弦函数 op1=cos(op2)
cos [reg,local,global],[num,reg,local,global]
int
强制类型转换为int型(原类型float)
int [reg,local,global]
flt
强制类型转换为float型
flt [reg,local,global]
条件跳转指令
相比于可能修改元数据需要小心翼翼管理内存的指令,条件跳转指令的实现可就简单的多了,唯一需要注意的是,如何确定跳转的位置,在x86指令集中,跳转指令的设计就复杂的多了,有近跳转,远跳转,相对跳转和绝对跳转,但是在StoryVM中,跳转指令并不需要设计的那么复杂,所有的跳转指令都为绝对跳转.
在StoryVM中,使用JMP指令表示一个无条件跳转指令,例如
JMP 10表示程序跳转到地址为10的位置执行
这么设计当然没有一点问题,但是我们不可能在编写程序时,手工去计算我们要跳转的位置,那么问题就是如何确定跳转的地址了,幸运的是,每条指令的长度都可以很方便的进行计算,我们只需要设计一个标志,就可以很容易计算出标志所在的地址了
在StoryVM中,标志的表示方式是一个助记符加上一个冒号,例如
FLAG:
MNEMONIC:
ADDR:
TRUE:
都是合法的标志类型,很多时候为了表现这是一个函数,在标号前可以加入描述符FUNC
例如
FUNC FLAG:
和
FLAG是等价的,FUNC这个助记符对源代码没有任何的影响,只是为了代码方便查看及分类添加的一个没有意义的关键字
现在观察下面的指令
MOV R1,1 //长度为12字节
ADD R1,2 //长度为12字节
FLAG: //偏移地址为24
ADD R1,2//长度为12字节
JMP FLAG//跳转到FLAG处开始执行
需要注意的一点是,如果一个汇编程序从开始编译到结束,那么,标号必须在JMP指令之前,也就是说JMP必须是向前跳转的,这显然不符合一个跳转指令应该具有的功能,要解决这一个问题实际也并不复杂,在汇编指令的编译期间,对源代码进行两次扫描,第一次扫描确定所有的标号对应的位置,第二次扫描才将JMP指令”连接”到对应的标号中实现跳转,
<ignore_js_op>
除了无条件跳转指令,当然还有一系列的跳转指令,具体描述如下
je
条件跳转,当op1等于op2,跳转到op3
je [num,string,reg,local,global],[num,string,reg,local,global],[reg,int,local,global,label]
jne
条件跳转,当op1不等于op2,跳转到op3
jne [num,string,reg,local,global],[num,string,reg,local,global],[reg,int,local,global,label]
jl
条件跳转,当op1小于op2,跳转到op3
jl [num,string,reg,local,global],[num,string,reg,local,global],[reg,int,local,global,label]
jle
条件跳转,当op1小于等于op2,跳转到op3
jle [num,string,reg,local,global],[num,string,reg,local,global],[reg,int,local,global,label]
jg
条件跳转,当op1大于op2,跳转到op3
jg [num,string,reg,local,global],[num,string,reg,local,global],[reg,int,local,global,label]
jge
条件跳转,当op1大于等于op2,跳转到op3
堆栈操作指令
堆栈操作本身属于数据结构的一种,当然,堆栈的操作和特殊的寄存器SP,BP相关,就和我们之前说的那样LOCAL[i]和GLOBAL[BP+i]是等价的,而SP指令和
PUSH
POP
两个指令相关
PUSH x指令实际上和下面的指令等价
SUB SP,1
MOV GLOBAL[SP],x
也就是说,每当执行一条PUSH指令,SP寄存器的值会被减去1,然后将PUSH的值赋值到对应的堆空间GLOBAL[SP]中
而POP x指令和PUSH指令刚好相反,其等价于
ADD SP,1
MOV x,GLOBAL[SP]
在指令的编写及设计中,PUSH指令和POP指令常常是成对出现的,也就是我们常常说的要保证堆栈平衡,如果PUSH
POP不成对出现,往往容易导致内存泄漏,越界访问等异常现象.
函数跳转指令
实际上虚拟机有上述指令就已经可以完成大部分的工作了,但除了一般的跳转指令,在StoryVM中还设计了一个特殊的指令CALL指令,CALL指令本身并没有什么特别的地方,它的作用是将下一条指令的地址压栈,然后跳转到目的标号中,CALL指令的设计同样是一种数据结构上的调度处理,当我们为这个汇编语言设计高级语言编译器的时候,CALL指令就会被经常的用到.
StoryVM指令表
介绍完几种关键的指令后,最后贴上StoryVM所支持的所有指令集,读者可以参照这些指令自行实现
mov
赋值指令,将op2的值赋值给op1
mov [reg,local,global],[num,string,reg,local,global]
add
加法指令,op1=op1+op2
add [reg,local,global],[num,reg,local,global]
sub
减法指令,op1=op1-op2
sub [reg,local,global],[num,reg,local,global]
neg
符号求反指令,op1=-op1
neg [reg,local,global]
div
除法指令,op1=op1/op2
div [reg,local,global],[num,reg,local,global]
mul
乘法指令,op1=op1*op2
mul [reg,local,global],[num,reg,local,global]
mod
余数指令,两个操作数必须为整数 op1=op1%op2
mod [reg,local,global],[int,reg,local,global]
shl
左移位指令,两个操作数必须为整数 op1=op1\<\<op2
shl [reg,local,global],[int,reg,local,global]
shr
右移位指令,两个操作数必须为整数 op1=op1\>\>op2
shr [reg,local,global],[int,reg,local,global]
and
与运算指令,op1=op1&op2
and [reg,local,global],[num,reg,local,global]
or
或运算指令,op1=op1|op2
or [reg,local,global],[num,reg,local,global]
xor
异或运算指令op1=op1\^op2
xor [reg,local,global],[num,reg,local,global]
inv
取反指令,op1=\~op1
inv [reg,local,global]
not
逻辑非指令 op1=!op1
not [reg,local,global]
andl
逻辑与指令 op1=op1&&op2
andl [reg,local,global],[num,reg,local,global]
orl
逻辑或指令 op1=op1||op2
andl [reg,local,global],[num,reg,local,global]
pow
阶乘指令(op1为底数,op2为指数,结果在op1中) op1=op1_op2
pow [reg,local,global],[num,reg,local,global]
sin
正弦函数op1=sin(op2)
sin [reg,local,global],[num,reg,local,global]
cos
余弦函数 op1=cos(op2)
cos [reg,local,global],[num,reg,local,global]
int
强制类型转换为int型(原类型float)
int [reg,local,global]
flt
强制类型转换为float型
flt [reg,local,global]
strlen
字符型长度指令
op1=strlen(op2)
strlen [reg,local,global],[reg,local,global,string]
strcat
字符型拼接指令
strcat(op1,op2)
strcat [reg,local,global],[int,reg,local,global,string]
strrep
字符串替换函数
将op1存在的op2字符串替换为op3中的字符串, 注意:op2 op3必须为字符串类型
strrep [reg,local,global],[reg,local,global,string],[reg,local,global,string]
strchr
将op2在索引op3中的字存储在op1中, 注意:op2必须为字符串类型
strchr [reg,local,global],[reg,local,global,string],[reg,local,global,int]
strtoi
将op2转换为整数保存在op1中,注意:op2必须为字符串类型
strtoi [reg,local,global],[reg,local,global,string]
strtof
将op2转换为浮点数保存在op1中,注意:op2必须为字符串类型
strtof [reg,local,global],[reg,local,global,string]
strfri
将op2整数类型转换为字符串类型保存在op1中
strfri [reg,local,global],[reg,local,global,int]
strfrf
将op2浮点类型转换为字符串类型保存在op1中
strfrf [reg,local,global],[reg,local,global,float]
strset
将op1所在字符串索引为op2 int的字符置换为op3
如果op3为一个int,则取asc码(第八位1字节),如果op3为一个字符串,则取第一个字母
strset [reg,local,global],[reg,local,global,int],[reg,local,global,string,int]
strtmem
将op1字符串类型转换为内存类型
strfrf [reg,local,global]
asc
将op2的第一个字母以asc码的形式
asc [reg,local,global],[reg,local,global,string]
membyte
将op3 内存类型对应op2索引复制到op1中,这个类型是一个int类型(小于256)
membyte [reg,local,global],[reg,local,global,int],[reg,local,global,memory]
memset
设置op1对应op2索引的内存为op3
memset [reg,local,global],[reg,local,global,int],[reg,local,global ,int]
memtrm
将op1内存进行裁剪,其中,op2为开始位置,op2为大小
memcpy [reg,local,global],[reg,local,global,int],[reg,local,global,memory]
memfind
查找op2对应于op3内存所在的索引位置,返回结果存储在op1中,如果没有找到,op1将会置为-1
memfind [reg,local,global],[reg,local,global,memory],[reg,local,global,memory]
memlen
将op2的内存长度存储在op1中
memlen [reg,local,global],[reg,local,global,memory]
memcat
将op2的内存拼接到op1的尾部
memcat [reg,local,global],[int,reg,local,global,memory]
memtstr
将op1内存类型转换为字符串类型,如果op1的内存结尾不为0,将会被强制置为0
memtstr [reg,local,global]
datacpy
复制虚拟机data数据,从地址op2到地址op1,长度为op3
datacpy [reg,local,global,int], [reg,local,global,int], [reg,local,global,int]
jmp
跳转指令 跳转到op1地址
jmp [reg,num,local,global,label]
je
条件跳转,当op1等于op2,跳转到op3
je
[num,string,reg,local,global],[num,string,reg,local,global],[reg,int,local,global,label]
jne
条件跳转,当op1不等于op2,跳转到op3
jne
[num,string,reg,local,global],[num,string,reg,local,global],[reg,int,local,global,label]
jl
条件跳转,当op1小于op2,跳转到op3
jl
[num,string,reg,local,global],[num,string,reg,local,global],[reg,int,local,global,label]
jle
条件跳转,当op1小于等于op2,跳转到op3
jle
[num,string,reg,local,global],[num,string,reg,local,global],[reg,int,local,global,label]
jg
条件跳转,当op1大于op2,跳转到op3
jg
[num,string,reg,local,global],[num,string,reg,local,global],[reg,int,local,global,label]
jge
条件跳转,当op1大于等于op2,跳转到op3
jge
[num,string,reg,local,global],[num,string,reg,local,global],[reg,int,local,global,label]
lge
逻辑比较指令,当op2等于op3时将op1置1,否则为0
lge [reg,local,global], [num,string,reg,local,global] ,
[num,string,reg,local,global]
lgne
逻辑比较指令,当op2等于op3时将op1置0,否则为1
lge [reg,local,global], [num,string,reg,local,global] ,
[num,string,reg,local,global]
lgz
逻辑比较指令,当op1等于0时将op1置1,否则为0
lgz [reg,local,global]
lggz
逻辑比较指令,当op1大于0时将op1置1,否则为0
lggz [reg,local,global]
lggez
逻辑比较指令,当op1大于等于0时将op1置1,否则为0
lggez [reg,local,global]
lglz
逻辑比较指令,当op1小于0时将op1置1,否则为0
lglz [reg,local,global]
lglez
逻辑比较指令,当op1小于等于0时将op1置1,否则为0
lglez [reg,local,global]
call
调用指令,如果op1是本地地址则将当期下一条指令地址压栈,然后跳转到op1,如果op1是一个host地址,则该call为一个hostcall,hostcall不会将返回地址压栈
call [reg,int,local,global,label,host]
*Host Call的返回值在r[0]中
*由被调用者清理堆栈
push
将op1压栈 sp-1,stack[0]=op1
push [num,reg,local,global,string,label]
pop
出栈，并将该值
pop [reg,local,global]
adr
取堆栈的绝对地址,返回该堆栈的绝对地址
ADR [reg,local,global], [local,global]
popn
将op1个元素出栈
popn [reg,local,global]
ret
返回,pop一个返回地址,跳转到该地址.
wait
等待一个信号量置为0,否者这个虚拟机实例将被暂时挂起(但并不不影响suspend标准位),在每个虚拟机实例中都有16个信号量,通过signal指令对这些信号量进行设置
signal
等待op1对应索引的信号量置为op2,
在每个虚拟机实例中都有16个信号量,这意味着op1的范围是0-15,当一个信号量被设置为非0值时,执行wait指令后改虚拟机实例会被阻塞,直到这个信号量被置为0时才能继续执行后续指令
bpx
如果启动了调试器,将会在该指令上断点,否者作为一个空指令
nop
空指令
虚拟机汇编编译器
也许制作一个高级语言的编译器会复杂得多,但是编写一个汇编编译器并不复杂,在大部分的时候,汇编编译器所做的工作无非是将助记符”编译”为指令数据流,这有以下几点好处
-
指令流往往所占的空间更小
-
指令流解析速度远远快于直接解析助记符
- 指令流更加安全(当然这也就意味着程序编译后失去了其可读性变得难以修改)
一个指令是否被翻译为指令流也常常被当做是这个语言是解释型语言还是编译型语言的分水岭,但是就和之前提到的,其实本质上都是对指令的解释只是方法不同,并没有特别的区别
预处理
在将指令编译为指令集之前,我们需要先处理几种情况以为开始编译做准备.
首先要处理的是之前提到的标志,标志用于指明跳转指令的跳转位置,因此在编译之前,扫描整个源文件所有的标号,并将标号记录在表中.
<ignore_js_op>
在第二次正式开始编译时,更新对应标号的跳转指令,让他们指向正确的位置
<ignore_js_op>
这样,对标号的处理就算完成了,当然除了标号,还有其他的数据需要处理,观察下面的几句汇编代码:
<ignore_js_op>
首先我们编译MOV
R1,255,当操作数作为寄存器和数字常量这没有一点问题,我们很容易就能写出其编译后对应的指令流,但是,MOV
R1,”Hello
World”就没有那么简单了,依照StoryVM的指令编码标准,每个操作数对应一个1字节的操作数类型和一个4字节的值,显然,Hello
World这个字符串已经超过了四字节所能容纳的范围了,因此和FLAG一样,我们也要将所有的字符串和数据流类型在第一次扫描时提取出来,将他们放入一个表中
<ignore_js_op>
当第二次正式编译时,我们同样和FLAG一样的方式,将字符串对应的索引号链接到对应的操作数当中.
<ignore_js_op>
<ignore_js_op>
当然除了字符串,对数据流也采用同样的办法建立一张表并建立映射关系,
最后是关键字ASSUME的处理,这是一条伪指令,其作用类似于C语言的define
例如下面的代码
ASSUME NUM,123
MOV R1,NUM
它等价于代码
MOV R1,123
堆栈
因为内存空间是有限的,因此对堆栈的大小必须有一个限制,在C语言或者其他的高级语言中,堆的大小可以从全局或者静态变量计算出来,而如果栈没有被明确的设定,那么编译器会选择一个默认值作为栈的大小,以visual
studio的MSVC为例,默认的栈大小是2M,正常情况下这个大小是足够了.
在StoryVM中,因为采用了元数据的存储方式,这也就意味着我们开辟的栈大小实际占用的内存会是这个栈的大小十倍乃至二十几倍,因此控制栈的大小就变得非常有必要,正常情况下,笔者使用65535个元数据作为栈(实际占用了将近2M的内存空间),但是在很多情况下除非使用深度的迭代并在局部变量中建立了大数组,实际并不需要那么大的栈空间,我们无法预测用户实际上会用到多少的栈空间,因此在StoryVM的汇编中,我们引入了.GLOBAL和.STACK两个关键字
例如
.GLOBAL 100
.STACK 1024
表示建立一个大小为100个元数据的堆,大小为1024个元数据的栈,它在内存中实际上是这样排布的
<ignore_js_op>
可以看到,堆栈实际上是访问了同一块内存空间,也就是说,如果访问GLOBAL[101]实际上已经访问了栈的区域了,需要注意的是,当栈溢出后,它将会覆盖堆中的数据,当然,StoryVM中做边界检查并不复杂.
指令编译
实际上在之前已经有过非常多的指令编译的讨论了,以下图为例
上面的指令流实际上是MOV
R1,255的编译,其中MOV被编译为了01表示MOV指令的实际操作码就是01,R1的操作数类型是寄存器,其中,02就表示这个操作数是一个寄存器,因为他是寄存器1,所以其对应的操作码参数也是1,最后是255,他是一个常量,01表示这是一个常量类型的操作数,它的值是255,也就是十六进制的000000ff
实际上,笔者总结了操作数的类型主要为以下几种enum PX_SCRIPT_ASM_OPTYPE
{
PX_SCRIPT_ASM_OPTYPE_INT, //整数常量,操作数参数为这个常量的值
PX_SCRIPT_ASM_OPTYPE_FLOAT, //浮点常量,操作数参数为这个常量的值
PX_SCRIPT_ASM_OPTYPE_REG, //寄存器,操作数参数为这个寄存器的索引号
PX_SCRIPT_ASM_OPTYPE_LOCAL, //局部变量类型
PX_SCRIPT_ASM_OPTYPE_LOCAL_CONST, //局部变量引用,例如LOCAL[5],操作数参数就是5
PX_SCRIPT_ASM_OPTYPE_LOCAL_REGREF,
//局部变量的寄存器引用,例如LOCAL[R1],就是一个寄存器引用,操作数参数是对应寄存器的索引
PX_SCRIPT_ASM_OPTYPE_LOCAL_GLOBALREF,
//局部变量的全局变量引用,例如LOCAL[GLOBAL[1]],就是一个全局变量引用,操作数参数是对应全局变量的偏移量,例如这里就是1
PX_SCRIPT_ASM_OPTYPE_LOCAL_LOCALREF,
//局部变量的局部变量引用,例如LOCAL[LOCAL[2]],就是一个局部变量引用,操作数参数是对应局部变量的偏移量,例如这里就是2
PX_SCRIPT_ASM_OPTYPE_GLOBAL,//全局变量类型
PX_SCRIPT_ASM_OPTYPE_GLOBAL_CONST, //全局变量引用,例如GLOBAL[5],操作数参数就是5
PX_SCRIPT_ASM_OPTYPE_GLOBAL_REGREF,
//全局变量的寄存器引用,例如GLOBAL[R1],就是一个寄存器引用,操作数参数是对应寄存器的索引
PX_SCRIPT_ASM_OPTYPE_GLOBAL_GLOBALREF,
//全局变量的全局变量引用,例如GLOBAL[GLOBAL[1]],就是一个全局变量引用,操作数参数是对应全局变量的偏移量,例如这里就是1
PX_SCRIPT_ASM_OPTYPE_GLOBAL_LOCALREF,
//全局变量的局部变量引用,例如GLOBAL[LOCAL[2]],就是一个局部变量引用,操作数参数是对应局部变量的偏移量,例如这里就是2
PX_SCRIPT_ASM_OPTYPE_GLOBAL_SPREF,
//全局变量的SP寄存器引用,例如GLOBAL[SP],就是一个SP寄存器引用,操作数参数是对应局部变量的偏移量,例如这里就是2
PX_SCRIPT_ASM_OPTYPE_STRING,//字符串常量,操作数参数就是之前所述的对应字符串索引
PX_SCRIPT_ASM_OPTYPE_LABEL,//标签,实际上标签并不会被编译成实体的指令流
PX_SCRIPT_ASM_OPTYPE_HOST,//Host函数标签,之后再说
PX_SCRIPT_ASM_OPTYPE_MEMORY,//数据流类型常量,操作数参数就是之前所述的对应字符串索引
PX_SCRIPT_ASM_OPTYPE_BP,//BP寄存器
PX_SCRIPT_ASM_OPTYPE_SP,//SP寄存器
PX_SCRIPT_ASM_OPTYPE_IP,//IP寄存器
};
操作数类型由以上定义完成,而操作码读者可以自行设计任意一个值,例如笔者设定的StoryVM中
MOV指令的操作码是01
ADD 是02
SUB是03
MUL 是04
DIV是 05
……..读者可以根据自己的需要自行设计
导出与导入函数标签
和原生二进制编译的代码有所不同的是,我们编译出的程序无法直接供外部调用执行,然后脚本的主要作用就是供虚拟机调用需要的函数来执行我们所需要的功能,因此,我们需要将我们的FLAG暴露给外部供原生的程序调用,同时在很多的时候,我们的脚本也需要调用原生代码里的一些函数来完成交互,但是目前我们的虚拟机设计仍然没有办法满足这一功能
例如之前我们所说的下面的程序
MOV R1,1
ADD R1,2
FUNC:
MOV R1,3
JMP FUNC
在这里,FUNC这个标志仅能供给程序中的跳转,但却无法在虚拟机中直接调用.因此,笔者引入了一个关键字EXPORT意为导出函数,当一个标号被加上了EXPORT关键字后,程序编译期间将会把这个标号对应的地址记录在文件当中.以方便虚拟机中进行调用
<ignore_js_op>
同样的,很多时候也需要在脚本中调用原生的代码函数,这种函数我们一般称之为host函数
为此,在虚拟机中我们需要设计一个对应的隐射关系表,将host函数名与其地址对应起来以方便脚本进行调用,例如,假如脚本需要调用一个叫print的函数,那么,对应的脚本代码应该类似于这样编写
MOV R1,”Hello World”
Push R1
Call \$print
注意,在CALL这条指令中,print这个标号在这个脚本文件中本身并不存在,但取而代之的是在其前缀中添加了一个\$号表示这是一个host函数,当虚拟机执行到这条指令的时候,将会在host函数表中查找是否有对应的函数,如果有,那么就会跳转到该函数进行执行,如果没有那么虚拟机会抛出一个异常
<ignore_js_op>
最后就是关于返回值的问题了,在一般情况下,默认规定函数的返回值都存储在寄存器R1中,如果需要获取返回值,读取R1寄存器就可以了
编译可执行文件
最终,我们需要将所有的信息进行进一步的整合,以便于虚拟机更好地执行我们编译出来的指令流,首先我们可以参照PE格式的可执行文件,为我们的可执行文件设置一个文件头在笔者设计的StoryVM的编译文件中,其设计满足以下的描述
<ignore_js_op>
其中,文件头包含以下定义,其中px_dword表示4字节
typedef struct __PX_SCRIPT_ASM_HEADER
{
//////////////////////////////////////////////////////////////////////////
px_dword magic;//Magic Numeric一定是PASM
px_dword CRC;//CRC校验
//////////////////////////////////////////////////////////////////////////
px_dword stacksize;//栈大小
px_dword globalsize;//堆大小
px_dword threadcount;//最大执行线程数量
px_dword oftbin;//到代码区的偏移量
px_dword oftfunc;//到导出表的偏移量
px_dword funcCount;//导出函数数量
px_dword ofthost;//到导入表的偏移量,也就是host函数
px_dword oftmem;//到数据流常量区偏移量
px_dword memsize;//数据流常量区大小
px_dword hostCount;//导入函数数量
px_dword oftString;//到字符串常量区偏移量
px_dword stringSize;//字符串常量区大小
px_dword binsize;//代码区大小
px_dword reserved[6];//保留
}PX_SCRIPT_ASM_HEADER;
将代码进行整理打包后,一个可以供虚拟机执行的编译脚本也就算制作完成了.
执行编译脚本
虚拟机初始化
当虚拟机载入一个编译后的可执行脚本后,一般要进行以下几个步骤
-
验证文件头中的Magic和CRC,验证这个脚本是否是一个完整的编译型脚本,当然,最好引入编译器的版本号,如果以后对虚拟机的环境有修改,并规定该虚拟机可以运行哪些版本的脚本,这个字段将尤为重要.
-
完成了验证之后,之后就是对常量区进行一系列初始化了,从文件中读取字符串及数据流常量区将它们存储在运行内存中以供调用.
-
初始化host函数表,当然,只是初始化一个空表,在这里我们并不急着将导入函数映射到这个表当中.
-
现在要准备运行环境了,第一步当然是为堆和栈分配空间,在这里这个大小是可以计算的,它等于(堆大小+栈大小*最大支持线程数)*元数据的大小,可以看到这里我们引入了一个最大支持的线程数,这点我们将在之后讨论.
- 载入指令流,也就是代码区的代码了,到这一步基本也就意味着程序可以准备运行了
上下文切换与多线程调度
在开始运行虚拟机代码之前,笔者先来聊一聊多线程的问题,如果你是一名开发人员那么这个问题应该是再熟悉不过了,不过如果你并不了解多线程是什么玩意,你可以理解为一个人同时做多件事情.
在你的PC上你可以看见计算机同时运行着多个软件,仿佛所有的程序都在同时运行着,在CPU还是单核的年代,这是如何办到的呢,其实要理解这点也非常的简单,你可以理解为计算机在一秒钟,先执行某一程序的一些指令,然后立刻切换到另一个程序中执行另一个程序的指令而不是等待第一个程序的代码执行完成后再执行另一个程序,如果重复这个过程并且切换的速度非常的快的话,这些程序看上去就像是同时运行的.
那么问题就是如何进行这种切换了,在多线程当中,存在着数据共享区,也有那些独立的区域,共享数据区好说,就是堆区了,不管哪一个线程都访问同一个堆,独立的区域那就是栈了,这关系到函数调用问题,除了栈之外,寄存器也非常重要,因此每一次切换我们都要保存当前线程的栈和寄存器状态,当再次执行到这个线程的时候,再把这个栈和寄存器进行恢复,这就是我们说的上下文切换,可以说,上下文切换时多线程实现的关键技术.
了解了以上这几点,那么就可以解释之前在分配运行时内存空间为什么是参者这个(堆大小+栈大小*最大支持线程数)*元数据的公式了,是的,我们需要为每一个线程分配一个独立的栈空间,并且我们为每一个线程设定一个寄存器实例,那么每一个线程使用的寄存器实际上是分开的.
<ignore_js_op>
因此在虚拟机的设计中,执行的步骤是,先执行某一线程的一些指令,然后切换到下一个线程执行另一些指令,这样就产生了一种多个程序同时执行的情况,但我们也注意到多线程运行的同时也附带着上下文切换带来的性能开销,不过幸运的是,由于在StoryVM中所有的线程都有自己独立的寄存器实例与独立的栈空间,因此上下文切换带来的性能开销基本可以忽略不计,我们要做的就是根据实际情况看给线程分配多少的时间片了(每个线程每次执行多少条指令后切换).
信号量与中断
我们注意到多线程的引入产生了一些新的问题,那就是如何解决多线程的资源竞争问题(多个线程同时访问修改一个数据),在windows中,提供了互斥体才避免这种情况的发送,相信读者也发现了在多线程章节给出的说明图中,多出了一个信号量最高东西,实际上这和互斥体类似,同样是为了解决资源竞争所带来的问题的
在之前的StoryVM指令表中有以下两个特殊的指令
wait
等待一个信号量置为0,否者这个虚拟机实例将被暂时挂起(但并不不影响suspend标志位),在每个虚拟机实例中都有16个信号量,通过signal指令对这些信号量进行设置
signal
等待op1对应索引的信号量置为op2,
在每个虚拟机实例中都有16个信号量,这意味着op1的范围是0-15,当一个信号量被设置为非0值时,执行wait指令后改虚拟机实例会被阻塞,直到这个信号量被置为0时才能继续执行后续指令
这也就意味着,当一个线程需要访问一片资源时,他需要先进行wait某一信号量.如果不需要等待,再使用signal对其置为非0值防止其他线程对其进行访问,最后完成后再对signal归0操作
程序的开始与结束
终于到实际执行指令的时候了,那么程序从哪里开始运行呢,当然,StoryVM中并没有像PE文件里那样有一个OEP(程序最开始执行的地址),但我们的程序的的确确需要执行一些必须先执行的指令,在StoryVM中笔者定义其为_BOOT,一般情况下它是代码区中的第一条指令,还记得我们之前提到的导出标签么,是的,_BOOT实际上就是一个导出标签,在_BOOT标签后紧跟着是一些全局变量的初始化操作,当然这是后话了,在目前我们提到的汇编中,还没有全局变量初始化这一概念.这点我们将在后期StoryScript的高级语言中讨论,但现在我们需要执行代码怎么办,当然,这些都由用户自己决定,如果你希望从某处开始执行,那么你就应该在这里添加一个导出标签,例如如下代码
EXPORT _MAIN:
MOV R1,”Hello,从这里开始运行”
Ret
现在从哪里运行解决了,那么程序怎么结束呢,注意上面的代码有一个ret指令,这个指令的作用是从栈中弹出一个值,并将这个值作为这个函数的返回地址,可以看到,在这个函数前我们并没有对栈进行操作,是的,虚拟机在调用这个导出标签的时候,将会在栈中压入一个值为-1的返回地址,当程序执行到ret时,发现返回地址是-1的话,就意味着这个程序已经执行完成了,那么就会对程序进行资源回收,如果这是一个多线程调用的话,就会注销这个线程,如果虚拟机中已经没有需要执行的线程的话,就会挂起这个虚拟机.
StoryScript编译器
如果说汇编语言是为了简化直接编写机器语言而诞生的,那么大多数的高级语言的出现就是为了进一步简化汇编语言而带来的繁琐.
在前几章节中,笔者阐述了汇编语言的编译与虚拟机的工作流程,但要将虚拟机实际应用这些还远远不够,我们需要更具有效率的编程语言来提高开发的效率,在接下来的章节中主要讨论高级语言编译器的实现技术,当然鉴于篇幅的关系,我们仍然无法讨论所有的技术细节,如果你有相关的需要,你可能需要在网上或书中查找更多相关的资料.
一段StoryScript程序
毫无疑问的是,编写一个高级语言的编译器需要花费大量的心血,其工作量甚至比之前的虚拟机和汇编编译器加起来还多,不过幸运的是,汇编器已经为我们完成了大量的重要工作,比如字符串数据流资源的整理,符号的扫描和集成的汇编指令的实现.
在开始之前,我们仍然需要探讨我们到底需要编写一个什么样的高级语言编译器,关于这点笔者参考了多种方案,最终使用了一个类C语言的方案来编写StoryScript编译器.这主要有以下几个优点.
-
有现成的语言做参考,C语言有相当多的资料
-
函数式语言,过程化,实现起来相对简单
-
笔者编写C语言程序估摸算算也有十多年之久了,是的,笔者也使用过Java Pascal
C++但最终还是回到了C语言的怀抱. -
C语言用的人也不少
-
IDE就更多了,甚至很多情况下可以直接使用C语言的IDE来编写StoryScript
- 笔者是坚定的C语言死忠粉.
那么说了那么多,到底StoryScript是怎么样的呢,笔者先写一段StoryScript看看
#name “Main”
#runtime thread 4
#runtime stack 4096
#define Num 9
Host void Print(string t);
String a,b;
Void print9x9(int c,int d)
{
Int I,j;
For(i=1;i<= Num;i++)
{
For(j=1;j<=I;j++)
Print(string(i)+””+string(j)+”=”+string(ij)+”\t”);
Print(“\n”);
}
}
Export int start()
{
Print9x9(1,2);
}
这是一个输出99乘法表的程序,你可以注意到i这个变量,不过这没关系.,StoryScript是一个大小写无关的语言.下面我们对这段程序进行分析,并最终阐述编译器是如何工作的.
预处理
和汇编脚本语言一样,StoryScript同样有预处理指令,在这章节中将这段程序的预处理命令一起讨论,首先我们先明确一点,StoryScript的编译器其最终目的并不是编译出指令流,而是将StoryScript高级语言转换为符合其语法规则的汇编语言,之后再由汇编编译器将其编译成指令流.
首先我们要处理的是
#name这个预处理,这个是StoryScript特有的一个标示语句,每一个StoryScript必须在源代码的开头有这个语句,他的作用有点像这个源代码起个名字,当然,每个源文件有且必须有一个名字,这样当其他的源文件需要包含这个源文件时就可以用#include
”Name”来包含这个源文件了,其功能和C语言中的#include
“xxxx.h”是一样的,你可能会问为什么要多此一举加上这个name专门去指定这个源文件的名字呢.直接用文件名不好么,但笔者设计StoryScript的目的是,这个语言可以执行在任何可移植StoryVM的平台上,这也意味着其编译器可以一并移植到任意只要能提供C语言编译环境的平台上(这也任意平台不仅可以执行编译后的文件,还可以直接提供源代码执行,也就是即可以当编译型脚本用,也可以当解释型脚本用),在很多的嵌入式平台中,并不提供文件系统这一概念(实际上,StoryVM的虚拟机和编译器的C语言代码不包含任何的C语言标准库,从内存池实现到数学运算全部都重新实现了一遍),因此笔者最终采用了这个方案来标识每个源代码的名称.
接下来是
#runtime thread 4
#runtime stack 4096
两个语句,这两个语句,在汇编中会直接被编译为
.Thread 4
.Stack 4096
如你所见,他设置了这个脚本所支持的最大线程数量和默认的堆栈大小,当然,这两个是可选的参数,如果你不写这两条语句,那么,线程数会被默认设置为1,栈大小会被默认设置为65535
#define Num 9
这条语句和C语言的#define等价,也就是说,源文件中所有的Num会被替换为数字9
最后是Host void Print(string t);
这是一个函数定义,前面的Host关键字表面,这个函数在源文件中并不存在,它是一个host函数,host函数的作用在之前已经讨论过了,它是虚拟机使用原生代码实现的函数,是脚本调用原生代码的一种方式,在之后的代码中,如果调用这个Print函数,其汇编代码会被翻译为
Call \$Print
这样的指令.
函数的定义和调用
接下来就是start函数的定义和实现了
Void print9x9(int c,int d)
函数的调用一向是函数式语言的工作方式,从在StoryScript中并没有与C语言类似的main函数,从哪里开始执行是由用户定义的,但从上面的这个语句来看这显然是一个标准的函数定义,
在函数的定义期间,并不会生成实际工作的汇编代码,但它会产生一个标号,并确定函数的栈分配和调用方式.
谈及函数的调用关系,难以不提及当今主流的两种比较有代表性的函数调用方式stdcall和cdecl,这两种调用方式的参数传递方式都是从右向左压栈,但唯一不同的是,stdcall在函数结束时由函数来维持堆栈平衡,而cdecl则是由调用方来维持堆栈平衡,为了演示这两种调用方式的不同,我们查看两种调用方案的汇编代码
首先是stdcall的
push d
push c
call print9x9
在print9x9中需要弹出2个栈元素
然后是cdecl的
push d
push c
call print9x9
popn 2
在StoryScript中,我们默认采用的是cdecl的模式由调用者来平衡堆栈,这也就意味着调用者必须清理栈来保证堆栈平衡.
最后是关于访问参数的问题了,正如我们之前提到的,LOCAL[x]实际访问的是GLOBAL[x+BP],我们知道,每次CALL指令调用后,会将函数的返回地址压人栈中,因此按照我们的思维来说,LOCAl[1]访问的是参数c,LOCAL[2]访问的是参数d,这也就意味着,我们必须在函数的开头执行
MOV BP,SP将BP寄存器与栈进行挂钩
<ignore_js_op>
这可以很好的工作没有什么问题,但是这样的设计是存在缺陷的,当我们引入局部变量后,这种方式多多少少会引来不便.
变量与堆栈映射关系
我们在代码中注意到,在代码中有两个变量的定义
其中一个是全局变量string a,b
另一个是局部变量int I,j;
那么变量是如何隐射到堆栈中的呢,其中全局变量很好理解,我们只需要在堆中进行线性排布就可以了,例如,a实际上是GLOBAL[0],b实际上是GLOBAL[1]
那么I,j如何处理呢,之前谈论的方案很好的解决了参数的问题,但却没有解决好局部变量的问题,为了继续容纳局部变量I,j,我们需要对栈结构进行重新部署,在函数的开始时就为局部变量预留好空间,那么在print9x9这个函数中,在MOV
BP,SP之前,我们需要为局部变量开辟栈空间
SUB SP,2
MOV BP,SP
那么,实际的栈结构变成了下面这个样子
<ignore_js_op>
因此我们最终发现,参数和局部变量实际上存储在同一个区域并没有什么差别,但要注意的是,局部变量的释放在函数的结束一定要做,例如这里在函数的结尾一定要加上popn
2否者程序就会崩溃,而在执行ret指令后,需要在做一个popn 2把压入的参数释放掉.
AST语法树与递归下降分析法
abstract syntax tree
(AST)抽象语法树,那么什么是语法树呢,简单来说就是把代码转换为一个数结构便于分析的数据结构方案
<ignore_js_op>
那么什么是递归下降分析法呢,简单来说就是模仿语法树的分析方案建立起的一套算法规则,准确来说,递归下降分析法主要是用来分析代码中的表达式的.那么表达式是什么呢,通俗点说就是算式
例如下面的表达式
1+2*3
这个式子建立起的AST树类似于这个样子
<ignore_js_op>
因为2,3节点深度比1节点大,因此先计算2*3,然后结果再和1进行相加得到最终的结果,与AST树稍有不同的是,递归下降分析法是基于堆栈式的语言,我们先来看看递归下降分析法是如何解决上述式子的解析的
为了方便描述,我们建立了两个栈,一个叫做操作码栈,一个叫操作数栈,操作码栈简单而言就是存放数字的,而操作数栈就是存放运算符例如加减乘除的,在进一步讨论之前,我们需要先认识到运算符优先级这一个概念,小学的知识告诉我们,乘法的优先级比加法的高,因此,我们需要先计算乘法再计算加法,例如下面的表达式
1+2*3+4/5
因为乘法和除法的运算优先级比加法高,因此,2*3和4/5会被优先计算,那么递归下降分析法会如何处理呢,实际上,递归下降分析法会先计算2*3,然后结果与1进行相加,之后再计算4/5,再与之前的结果相加
递归下降分析法的核显是,从左到右依次读取运算符,如果读取的运算符优先级比上一个运算符优先级小或处于同一优先级,则进行计算.为了让读者更好地理解递归下降表达式的作用,我们一步一步对1+2*3+4/5用递归下降分析法进行运算
1.读取第一个操作数1
操作数栈: 1
操作码栈:
2.读取操作码+
操作数栈:1
操作码栈:+
3.读取操作数2
操作数栈:1,2
操作码栈:+
4.读取操作码*
操作数栈:1,2
操作码栈:+,*
5.读取操作数3
操作数栈:1,2,3
操作码栈:+,*
6.读取操作码+
操作数栈:1,2,3
操作码栈:+,*
注意,在这个时候,因为加法的运算符优先级比乘法的小,因此我们需要进行计算,因为乘法是一个双目运算符,因此从操作数栈中弹出两个操作数2,3计算2*3得到结果6,在这个时候,再把6压入操作数栈中得到
操作数栈:1,6
操作码栈:+
注意,因为加法的运算级和之前那个加号是同等运算优先级,因此,会在进行计算,因为加法是双目运算符,因此,从操作数栈弹出2个操作数继续计算1+6得7,那么最终结果变为了
操作数栈:7
操作码栈:
最后,别忘了把读取到的加号再次压入栈中,于是就有
操作数栈:7
操作码栈:+
7.读取操作数4
操作数栈:7,4
操作码栈:+
8.读取操作码 /
操作数栈:7,4
操作码栈:+ /
9.读取操作数5
操作数栈:7,4,5
操作码栈:+ /
10.表达式结束,这个时候,当作读取了一个优先级为最低的运算符,因此需要处理所有还没有处理的操作码,,先进行除法运算,4/5的0.8
操作数栈:7,0.8
操作码栈:+
执行加法运算
操作数栈:7.8
操作码栈:
至此表达式结束,取得最终的结果7.8
从上面的递归下降分析中,我们很好地处理了这个表达式的解析关系,因为这个表达式的计算都是常量,计算起来也没有那么多的障碍,在StoryScript中,虽然同样使用递归下降分析法来分析表达式问题,但因为存在变量的引用,实际产生的分析步骤却复杂的多
例如下代码
int a=2,b;
b=1+2*a;
那么,下面的表达式是如何变成汇编代码的呢
我们现在观察递归下降中的堆栈变换,并最终将上述的表达式变为可执行的汇编代码
1.读取第一个操作数b
操作数栈: b
操作码栈:
2.读取操作码=
操作数栈: b
操作码栈:=
3.读取操作数1
操作数栈: b,1
操作码栈:=
4.读取操作码+
操作数栈: b,1
操作码栈:=,+
5.读取操作数2
操作数栈: b,1,2
操作码栈:=,+
6.读取操作码*
操作数栈: b,1,2
操作码栈:=,+,*
7.读取操作数a
操作数栈: b,1,2,a
操作码栈:=,+,*
8.表达式结束,按照递归下降的规则,我们先对乘法进行运算,得到2*a这个算式,为了完成这个算式,我们需要使用寄存器进行操作
MOV R1,2
MUL R1,a
这样,R1的值就存储着我们所需要的值了
那么,栈是否变为了
操作数栈: b,1,R1
操作码栈:=,+
呢,在这个表达式中,这样当然没有问题,然而实际的情况是如果我们直接将R1作为操作数压入栈中,那么碰上
b=2*a+4*a这样的表达式就会出现问题了,因为2*a将结果放在了R1中,那么4*a就不能再使用R1使用了否者会将原来的值覆盖掉,那么就只能选择R2寄存器了,但是寄存器是有限的,如果这个表达式足够的长,那么我们的算法体系就会濒临崩溃,因此我们不能直接将R1作为操作数压入栈中,我们需要将R1作为一个值变成汇编代码压入运行的栈中变成这个样子
MOV R1,2
MUL R1,a
PUSH R1,那么,操作数栈实际变为了
操作数栈: b,1,POP
操作码栈:=,+
那么我们进行了下一步.下一步是一个加法运算,为了取得前一次计算的值我们需要进行一次pop操作,并将这个值放入R2寄存器当中,同样的在计算结束后,结果仍然在R1中,我们还需要再次将R1进行压栈
MOV R1,1
POP R2
ADD R1,R2
PUSH R1
这个时候,递归下降的两个栈变成了
操作数栈: b,POP
操作码栈:=
最后一次运算了
POP R2
MOV b,R2
MOV R1,b
PUSH R1
读者可能会疑惑,为什么还要MOV R1,b再PUSH R1呢,到MOV
b,R2不是已经完成了这个表达式么,当然,我们设计一个程序不能只看到这样的一个表达式,在很多的时候我们必须要保证其通用性例如当碰上
b=(a=1)这样的表达式时,你就知道为什么我们需要”多此一举”了,为了保证我们编译的汇编程序的准确性,我们需要考虑各种不同的情况,尽管这可能会引入一系列的冗余代码,但这是值的的,冗余的代码我们可以在优化的部分再做处理,最后相信读者也知道了,这个表达式最终的结果是什么
MOV R1,2
MUL R1,a
PUSH R1
MOV R1,1
POP R2
ADD R1,R2
PUSH R1
POP R2
MOV b,R2
MOV R1,b
PUSH R1
POP R1
最后的POP
R1,表示取得表达式的最终计算结果.并将它放入寄存器R1当中,当然我们也发现了这个表达式中仍然有非常多的冗余代码可以优化,但这是后话了.当然,最后别忘了汇编代码中的a,b其实被映射到了LOCAL[]的栈元素中,笔者直接写a,b只是为了方便读者观看,最终a,b会被替换成LOCAL[x]这种格式.
强类型与表达式类型匹配
虽然递归下降分析法为我们解决了不少的问题,但是仍然有很多额外的问题需要我们解决,其中一个就是类型在表达式中的作用,其中要说明的一点是StoryScript属于强类型语言,一共支持四种类型
int---整数型
float----浮点型
string----字符串类型
memory-----数据流类型
除了int和float类型可以互相运算操作,string,其它类型间不允许直接进行计算
例如
string a;
a=”hello”+”world”
这个表达式是一个合法的表达式
但a=”hello”+123这个不是一个合法的表达式,在进行递归下降分析时,同样需要对表达式的类型进行进一步的检查,上面的字符串类型和一个整数类型进行加法运算显然不是一个合法的表达式类型的运算,因此在检查到这类无法类型匹配的表达式时,编译器应该要抛出一个错误.
除了类型匹配之外,还需要注意的是运算符匹配,例如位运算中的与或非异或等操作面向的是整数型,如果表达式结果是其它类型同样需要抛出一个错误
例如
int a=1;
a=a\&1;这是一个合法的表达式
但是
int a=1;
a=(a+1.5)&1却是一个不合法的表达式,因为a+1.5的运算结果是一个浮点数
不同类型间如果需要进行计算,需要专门的函数对其进行转换,在StoryVM中,这些特殊的函数被直接编程到汇编指令中专门进行这种转换操作,很多时候也管这种函数称之为关键字,其作用类似于C语言中的sizeof,但有所不同的是,sizeof是编译期间就已经完成的,而StoryScript中的关键字却会变编译成实体的汇编指令.
语法结构For语句
继续观察代码,我们来到了For(j=0;j\<=I;j++)这条语句,之所以在这个代码中使用for语句作为示范是因为这个for语句最具有代表性,它包括了while和if语句的实现细节,可以说,如果你可以编译For语句,你也可以很顺利地编译while和if语句
观察for语句的结构基本由如下这种方式来完成
for(初始化表达式;条件判断表达式;末尾循环体)
{
for循环体
}
我们之前已经说了递归下降分析表达式的方法,那么剩下的就是如何构造for的语句结构了,为了方便说明笔者用一张图来表示for语句结构的剖析
<ignore_js_op>
当执行到for语句的时候首先执行的是初始化代码,执行完成后将会跳转到条件判断代码中判断代码是否成立,如果不成立则直接结束,如果成立则会执行for循环体,当for循环体执行完成后再跳转到末位循环体中,读者可能会有所疑问,为什么末位循环体被前置到那个位置,安装逻辑不应该在for循环体之后么,虽然道理大家都懂但是从编译的角度进行分析,在我们编译for语句的时候,最先被解析的表达式就是初始化代码区,条件判断和末位循环体的表达式,而for循环体中的代码可能很复杂还可能包含有各种的嵌套结构,因此如果将末位循环体放在for循环体之后,其实现起来会复杂的多,一个东西越复杂,那么其就越有可能出错,因此我们采用了这种折中的方式来实现for循环体,效果一样却节省了大量的代码,这也是笔者为什么一直强调,很多问题只有在你真正动手去做了你才知道怎么回事,有些东西书本上无法告诉你,那套听上去吊炸天的架构和公式也无法最终帮你解决很多问题
最后,我们手写下For(j=0;j\<=I;j++)的编译结果
//初始化代码区
mov R1,0
mov j,R1
JMP _FOR_condition
//末位循环体
_FOR_LOOPEXPR:
ADD I,1
//条件判断
MOV R1,j
MOV R2,i
LGLE R1,R2 //如果R1小于R2,则R1为1否者为0
JE R1,0,_FOR_END;//如果R1位0,for语句结束
for循环体的汇编代码
JMP _FOR_LOOP_EXPR
_FOR_END;
IF语句编译
相对于for语句的实现,if语句的实现就简单的多了,IF语句的格式如下
if(条件表达式)
{
IF语句块
}
else
{
ELSE处理
}
如下图所示
<ignore_js_op>
一开始到达的是条件判断代码区,如果条件判断为假,则跳转到else语句块中如果为真就继续执行,当然在if语句块执行结束后也要跳转到结束,不然就继续执行else语句块里面的代码了
相信要编写相应的汇编代码并不复杂.笔者就不继续复述了.
while语句编译
while语句估计是三种语句中最简单的一种了,其语法格式如下
while(条件判断)
{
while语句块
}
就直接看图吧
<ignore_js_op>
首先执行条件判断,如果为假,跳转到结束,否者执行while语句块也就是循环体,循环体执行结束后再跳转到条件判断中继续执行.
其它语法结构
当然有了上述几种结构后,对于其它结构怎么来的读者应该可以自行发挥想象了,像do
while,switch等应该都可以按照上述的思路去完成,在码农界常常称这些结构为语法糖,但不管语法糖怎么造,实际上while和if语句几乎就可以解决所有的逻辑问题了,因此不管一门语言怎么变,了解其最根本的东西才是关键的,不管一个语言的语法糖有多好,真正适合自己的,能做出自己需要功能的语言才是一门好语言
当然在StoryScript中笔者自行实现了Compare语句作为switch语句的替代品
其语法格式为
Compare(比较表达式1)
{
with(比较表达式2;比较表达式3…..)
{
with语句块
}
………
}
其作用为当比较表达式1和with中其中一个表达式的结果相等,那么就执行with语句块中的代码,实际上一个compare语句中可以包含多个with语句,其和switch语句稍有不同的是,with语句中的表达式不同于case需要是一个常量,因此它比switch语句用起来会方便的多,但相对的,其比switch语句在比较较多的条件下性能肯定不如switch,不过既然是一门脚本语言,我们自然不能在性能上奢求太多,毕竟我们无法做到面面俱到.一门语言着眼于做好一类问题,其它方面尽可能好就行了.
嵌套语句的处理
在StoryScript编译器的最后,笔者想最后聊聊关于语句嵌套的问题,那么什么是语句嵌套呢,观察下面的代码
if(a\>10)
{
if(a\>20)
{
}
}
这是一个标准的嵌套语句,由2个IF语句构成,虽然它们都是IF语句,但是处理起来却不愿意,因为if(a\>20)是包含在if(a\>10)的语句块里的,实际上在处理语句嵌套的问题上,编译器采用栈的方式对这些嵌套语句进行处理,当一个语句块结束后,再将它从栈中弹出来并且添加其结束代码(语句块结束有一个很明显的特征,那就是有一个右花括号)
例如在上面的代码中,我们把第一个IF叫做IF1,第二个IF叫做IF2,从之前的代码生成我们知道,语句块的控制基本是有标签+跳转来实现的,那么因为名字的不同,这两个if语句块将会生成不同的标签
因此实际上述代码的实际处理流程实际上是这样的
-
碰到了第一个if语句,将它叫做if1,然后将这个if语句压栈
-
碰到了第二个if语句,将它叫做if2,然后将这个if语句压栈
-
碰到了花括号},从栈中弹出一个语句块,发现这个花括号属于if2的那么添加if2的跳转
-
碰到了花括号},从栈中弹出一个语句块,发现这个花括号属于if1的那么添加if1的跳转
- 分析结束
这个过程适用于任何的语句嵌套,例如
for()
{
if()
{
}
}
这种格式的或者是
while()
{
for()
{
}
}
这种格式的嵌套,每次处理到花括号}时,都从栈中弹出一个结构,然后再添加相应的处理代码,这种栈式的处理方式能够正确的处理嵌套语句的代码生成,同时这也为我们处理continue和break两个特殊指令的关键字提供了思路
众所周知的continue和break语句仅对while for switch(这里应该是compare) do
while语句生效,因此当找到这类特殊指令时,应该从栈顶开始搜索并找到第一个符合条件的结构,然后添加对应的处理代码.
结语
不管怎么说,设计一套虚拟机和编译器系统是一个庞大的工程,从词法到语法分析到整个虚拟机系统的设计和编译器的优化笔者将近使用了5w余行的代码来完成其具体实现,当你真正动手写一个东西时,你会发现有很多之前你都没能考虑到或者是考虑周全的问题,因此尽管码农界一直在说不要重复造*,但有一些*你不自己造一造恐怕你永远不知道他具体是怎么回事.
最后,笔者将之上一章节的99乘法表代码使用这套编译系统运行,你可以在本文的附件中找到这段代码的DEMO,同时你也可以修改这个代码自己尝试一下这个编译器编译的过程和结果.
点击文件夹,找到StoryScript Console.exe
<ignore_js_op>
运行
<ignore_js_op>
点击Load,然后在文件对话框中选中99乘法表示范程序.txt,观察输出结果
<ignore_js_op>
你可以任意修改示范程序中的代码,在示范程序中,程序由Main函数开始执行,有一个导入的host函数为Print,意为在控制台输出消息
<ignore_js_op>
同时你会发现在脚本的同一目录下生成了两个新的文件,一个为.asm后缀的文件,一个是st后缀文件
<ignore_js_op>
你可以打开asm文件查看编译器是如何将StoryScript编译为汇编代码的,也可以使用hex打开st文件查看编译后的文件结果
<ignore_js_op>
<ignore_js_op>
当然在最后,你可以直接Load编译后的程序,那么它将直接运行出99乘法表同样的结果.