TripleCamera 的博客

基于代码块的数据生成器

沈锎 | | ⭐️ 1 | 💬️ 3
分享
测试
Verilog

提示：这篇文章也在作者的博客上发布，协议为 CC BY-NC 4.0。

沈锎

本文主要交流两个方面的问题：数据生成器程序的结构与生成数据的强度。文末有代码获取链接与具体代码的介绍。个人观点，抛砖引玉，望批评交流！

目录

  • 生成器采用的程序架构
    • 面向接口与继承的指令设计
    • 面向块的模板文件
    • 此种设计方式的优劣
  • 数据合法性与强度保障
    • 跳转指令
    • 内存读写指令
    • 过程调用
  • 代码设计分析
    • 抽象基类与代码块
    • 软件包与模块
    • 模板文件与参数定制化
    • 完整代码获取

生成器采用的程序架构

在之前分享的数据生成器设计思路中，有同学将指令硬编码进生成器，也有同学将指令写入配置文件，并设置相关参数，取得了比较理想的随机效果。

在 P3 的自动测试中，我采取了一种人工编写“描述文件”，由生成器进行解析，并生成随机产生的汇编代码。这种比较麻烦，而且添加指令需要对之前编写好的文件进行修改。同时，数据的强度非常依赖于编写描述文件时的设计与想法。

如果不考虑新增指令与可拓展性，上述几种方式都可以取得比较好的效果，但问题的关键便在于可拓展性上。

面向接口与继承的指令设计

不如先看一看我们的 “黄金标准” Mars 是怎样处理那么多的指令的。如下是 “注册” addu 指令的代码，添加的内容是一个类的对象，这个类在构造时需要指令的格式、描述、类型等。此外，还有一个实现了接口 SimulationCode 的匿名类，其中有一个 simulate 方法，定义了指令执行的具体过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
instructionList.add(
    new BasicInstruction(
        "addu $t1,$t2,$t3",
        "Addition unsigned without overflow : set $t1 to ($t2 plus $t3), no overflow",
        BasicInstructionFormat.R_FORMAT,
        "000000 sssss ttttt fffff 00000 100001",
        new SimulationCode() {
            public void simulate(ProgramStatement statement) throws ProcessingException {
                int[] operands = statement.getOperands();
                RegisterFile.updateRegister(
                    operands[0],
                    RegisterFile.getValue(operands[1]) + RegisterFile.getValue(operands[2])
                );
            }
        }
    )
);

总结以下，Mars 采用的方法是抽象出一个基类或者接口，然后通过继承或者实现来添加指令。

那它的设计思路适用于我们的需求吗？我觉得，适用，但略微不一样。Mars 作为执行者，需要很明确地定义各个指令，而我们只需要生成这些指令。若不考虑特殊用途，面对海量的随机数据，add 和 sub 没有本质的区别，因此可以将它们放在一起考虑。

同时，很多指令并不能很随意的生成，比如分支跳转指令，它们需要被精心地设计，以满足既不出现死循环，也能够尽可能提高覆盖率的条件。

基于这些原因，我在设计数据生成器时，采用了 “块” 的设计思路。比如，将几条涉及“计算”的指令放在一起抽取，又比如，将 beq 设计为 while 或者 do-while 循环等。

面向块的模板文件

有了块就可以 random 启动了吗？当然可以！但除了单纯的随机生成，我还设计了一种模板文件（.template）的语法，通过模板文件将块组织起来，配合一系列定制化设计与嵌套组合，可以构造出更加丰富多彩的数据。

下面是其中的一个模板文件，通过 Beq 块（不是 beq 指令，而是用 beq 实现的循环）的嵌套可以构造一个双层循环，其中还夹杂着一些随机的计算指令，用短短十几条指令跑出十几万行的输出。

1
2
3
4
5
6
7
Init

Beq end=$s0 var=$s1
    Beq end=$s2 var=$s3
        Nop
        Calc reg=v repeat=2
    Calc reg=t repeat=10

每个模板文件可以有不同的侧重，重点测试某些指令的具体功能，也可以进行过程更加随机的综合测试，还可以利用专门的构造，进行极限测试。

此种设计方式的优劣

优势在于拓展方便快捷，可定制化强，能够很轻易地构造出一些复杂结构。

劣势则在于，使用规定的范式取代了部分随机性，数据的强度很依赖于块的设计与模板文件的编写。

数据合法性与强度保障

跳转指令

设定好一个 “跳转块”，采用构造循环的方式，可以尽可能地覆盖全部测试情况，比如正跳与反跳、比较结果偏大或偏小。

在目前的程序实现中，只包含了 while 型的循环，循环体在 PC 较小的位置，如能再增添 do-while 型的循环，则可以进一步提高覆盖率。

为了弥补上述缺漏，在当前的实现中，循环终值、循环初值均随机生成，这意味着循环变量是自增还是自减也是随机的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
    return f"""\
ori {loop_var_r}, $zero, {loop_var}
ori {loop_end_r}, $zero, {loop_end}
{loop_label}:

beq {loop_var_r}, {loop_end_r}, {end_label}

{insert}

ori $at, $zero, 1
{loop_inc} {loop_var_r}, {loop_var_r}, $at
beq $0, $0, {loop_label}
{end_label}:
"""

为了使情况更加复杂，我还为其设计了一个 “子块” 的概念，即上述代码第 8 行，可以很轻松地向其中插入其他代码块，甚至构造双层循环。上面的例子便是如此。

内存读写指令

内存读写测试最大的难点在于，保证地址合法以及测到立即数、基地址的各种情况。

前者，我通过随机生成要读写的字地址，只要确保生成的立即数与基地址之和为其的四倍即可。

后者，我通过随机生成一个立即数的偏移量，再通过计算得到基地址的方式，能够覆盖到基地址为正、为负的情况。

1
2
3
addr = int(self.imm(low=low_addr, high=hgh_addr)) * 4
addr_imm = int(self.imm(low=low_addr, high=hgh_addr))
addr_reg = hex(0xffffffff & (addr - addr_imm))[2:].zfill(8)

过程调用

可以定义出一个 “函数体”，通过前置的跳转保护，通过 jal 和 jr 进行调用。如能随机生成函数体的位置，可以进一步提高覆盖率。

1
2
3
4
5
6
7
8
9
10
11
    return f"""\
beq $0, $0, {end_label}
{procedure_label}:

{insert}

jr $ra

{end_label}:
jal {procedure_label}
"""

代码设计分析

抽象基类与代码块

在这里我简单介绍一下我的代码层面的设计思路。

首先是基类，考虑到 Python 语言的一些特性与限制，我采用的是抽象类，而非接口。

1
2
3
4
5
6
7
class BlockBase:
    """
        The abstract base class for all blocks
    """
    @abc.abstractmethod
    def spawn(self, *args, **kwargs):
        pass

抽象类中唯一的抽象方法为 spawn，接收一系列参数（这是为了后续进行代码块的定制化），并返回一个字符串，代表当前产生的指令。

此外，抽象类中也定义了一系列静态方法，以随机量的生成为主。部分列举如下，可能会方便我后续的阐述：

1
2
3
4
5
6
7
8
9
10
11
@staticmethod
def imm(*, low, high) -> str:
    return str(random.randint(low, high))

@staticmethod
def shamt() -> str:
    return BlockBase.imm(low=0, high=31)

@staticmethod
def imm16() -> str:
    return BlockBase.imm(low=0, high=65535)

下面，以计算类指令代码块为例，看一看具体的操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class __Calculation(BlockBase):

    choice = [
        "add #r, #r, #r",
        "sub #r, #r, #r",
        "lui #r, #i",
        "ori #r, #r, #i",
        # "sll #r, #r, #s"
    ]

    def spawn(self, *args, **kwargs):
        """
        Spawn a random instruction that is about calculation
        :keyword pick: pick some specified instructions, splitted by `|`
        :keyword reg: choose the registers which are allowed to use
        :keyword repeat: repeat(random) `repeat` times, 1 by default
        :return: multi-line instructions(`repeat` lines)
        """

        # 定制化参数：指定生成的指令列表
        pick_list = kwargs.get("pick", "|".join([choice.split()[0] for choice in self.choice])).split("|")
        choice_list = [choice for choice in self.choice if choice.split()[0] in pick_list]

        # 定制化参数：指定随机生成的指令数
        try:
            repeat = int(kwargs.get("repeat", "1"))
        except ValueError as e:
            repeat = 1

        instr = "\n".join(random.choices(choice_list, k=repeat))

        # 定制化参数：指定允许选用的寄存器种类
        reg = kwargs.get("reg", "vats")

        # 对指令中的操作数进行随机替换
        while instr.find("#r") != -1:
            instr = instr.replace("#r", self.reg(reg), 1)
        while instr.find("#i") != -1:
            instr = instr.replace("#i", self.imm16(), 1)
        while instr.find("#s") != -1:
            instr = instr.replace("#s", self.shamt(), 1)

        return instr + "\n"

软件包与模块

为了简化编写块的步骤，我将全部块放在了一个软件包中，通过 __init__.py 用一种似乎不太规范的方法自动导入其中的模块。

同时，在每个具体模块中，我都要求提供一个全局的方法来提供类的实例：

1
2
def instance():
    return __Calculation()

模板文件与参数定制化

通过上面的例子，同学们也可以看到一些参数，它们会被解析为键值对，传递给 kwargs 参数。

例如下面的例子：

1
Beq end=$s0 var=$s1

解析到的参数为：

1
{"end": "$s0", "var": "$s1"}

此外，上面的例子中也出现了嵌套层次，可以利用 Python 缩进的思路来理解它，下一层缩进中的内容会被优先解析生成，并将生成的内容作为 args 列表参数的第一项传递给 spawn 方法。

完整代码获取

压缩包链接（存档）

没有入口函数，也没有入口类，需要调用的方法是 DataSpawner.gen_data，俩参数含义见代码注释。

这个函数会返回一个生成器，使用方法见同文件最后被注释掉的语句。

生成的全部数据均在 temporary/test.asm 中，这意味着后生成的会覆盖先生成的，可以自行修改写入文件名（DataSpawner.py 39 行），或者在循环中进行处理（Dataspawner.py 第 50 行）。其他的可以看一看 README 中的表格，也可以看看模板文件都是怎样写的。

利用我已经提供的模板，可以测试到全部指令，也可以测试 DM 中全部位置的读取与写入，如果有同学有兴趣编写一些更强或者更有趣的块或者模板，欢迎分享交流！

欢迎同学们提出批评意见，或者进行补充！

| CC BY-NC 4.0（代码 MIT） ❤️ 4
灰袍甘道夫 回复 沈锎

同学，感谢你的分享！ 使用效果很好，有一个问题是在生成add和sub指令时会出现溢出的情况，导致mars报错

| 保留所有权利 ❤️ 0
沈锎 回复 灰袍甘道夫

这个可以使用 Toby 学长定制过的 Mars，开启忽略溢出的功能 ~

| CC BY-NC 4.0（代码 MIT） ❤️ 0
0%