我想做一个16进制计算器很久了。面向NDS的开发经常要做一些地址/结构体的计算，Windows系统自带的计算器在某些功能上不能满足我的需求。于是我利用春节假期一周多一点的时间初步实现了一个NDS上的16进制计算器软件HexCalculatorDS。本次甲方乙方都是我自己，但是走了一套完整的开发流程，从需求分析、可行性分析到架构设计，最后开工。现记录一下，备忘。
第一次接触NDS开发的读者可以先看看附录B。
竞品综述
（我诚实，这一节是后补的。不用看都知道，没有软件能满足我的需求。）
自Nintendo DS于2004年发布以来，其独特的硬件架构与成熟的开发工具链迅速催生了活跃的自制软件（homebrew）生态。以GameBrew[1]为代表的社区平台对相关项目进行了系统性整理，其中计算器与数学软件一度成为开发者探索触摸交互与嵌入式计算能力的重要方向（并非）。在2005年至2011年间，NDS平台上集中涌现出一批计算器相关应用，覆盖从基础四则运算[2–5]到函数绘图[6]、符号计算[7]乃至硬件计算器仿真[8,9]的多个层次。
早期工作多集中于基础能力验证（高情商），均在易用性或功能完整性上存在明显局限。例如Calculator DS[2]与PA_calc[3]仅支持四则运算，Handwriting Calculator[4]创新在于手写识别但运算范围有限，MoonCalc[5]具有古典UI审美（高情商），虽然支持括号、小数等功能，但无法输入16进制数字。已有计算器里唯一涉及多进制与位运算能力的DS-HPCALC[9]是基于Nonpareil框架移植的HP计算器（HP-11C/HP-16C）。其中HP-16C作为“程序员计算器”，虽然支持进制切换和位操作，但采用逆波兰表达式（RPN）输入范式，与主流计算交互习惯差异显著、学习成本较高（并且卖得不好）。同时，DS-HPCALC只是对实体设备的界面复刻，未对NDS双屏结构设计优化，上屏资源处于闲置状态，下屏界面清晰度也有限。
从人机交互与系统设计角度观察，现有NDS计算器软件普遍存在两方面不足：其一，在功能方面，多数实现停留于单一运算模式，缺乏对多进制、位宽控制及符号表示等程序员场景的系统支持；其二，在UI方面，相关应用多依赖libnds默认console字体或PAlib控件，未针对双屏架构进行专门设计，难以实现表达式展示与结果输出的有效分离，也未形成现代计算器常见的“公式→结果”可视化交互范式。
基于上述分析，可以认为NDS平台在“面向日常与程序员混合场景的多进制计算器”这一细分方向仍存在明显空白。为此，本文提出HexCalculatorDS，旨在构建一套兼顾整数运算、多进制切换与公式可视化显示的NDS平台计算软件，针对NDS双屏特性设计界面，实现具有输入、表达式渲染与结果输出完整功能的整数计算器，缅怀NDS曾经之流行，填补现有生态之不足。
需求分析和UI原型
我的需求大部分可以被Windows自动计算器的程序员（Programmer）模式满足。微软计算器的功能大致可以概括为：
- 支持输入16进制数字0-F；
- 支持常见运算（加、减、乘、除等）和位运算（与、或、非、取反、位移等）；
- 显示输入的公式；
- 显示计算结果数字；
- 可以切换进制（2/8/10/16）；
- 可以切换数字位宽，也就是字节数（8/4/2/1）。
在此基础上，我有几个额外的需求：
- 显示的16进制要每4个一组补齐。例如
0D00 0721在微软计算器里会省略开头的0，显示为D00 0721，计算地址偏移的时候有点费劲； - 支持切换数字符号（有符号/无符号），也就是C语言里的
signed/unsigned关键字。
甲方首先用PPT画了一个草图，如图1所示。意思是上屏幕上要有公式、当前输入/计算结果、各进制实时转换。并且计算结果字要比其他部分大。
图1: 计算器上屏设计草图。乙方拿到草图之后说，这图里的字体确实不行，NDS屏幕大小为256×192 px，PPT里的字大概率不能像素级对齐显示。
在与甲方充分沟通后，乙方拿出了上下屏幕的原型设计，如图2所示。
图2: 计算器UI原型。上屏幕包括数据类型区、公式区、当前输入区和四个进制转换区。下屏幕包括输入按钮（数字和运算符以形状区分）、分别切换符号和位宽的抽屉。计算器上屏左上角指示当前数据类型，指示有无符号（S/U）和位宽（64/32/16/8）。例如UINT64就是64比特的无符号数，INT8就是8比特的有符号数。下方依次是公式区、当前输入区和四个进制转换区。进制转换区左侧有可以切换的指示条，指示当前输入区数字的进制。例如，在INT8类型计算中，当进制从10进制切换到16进制时，当前输入区数字-1将被转换为FF。
计算器下屏需要有按钮交互逻辑。当用户点击某个按钮时，该按钮变为选中状态，也就是原型图中内部有集中线的按钮。该图中所有形状相同的按钮都设计了集中线样式，不过大差不大。有时按钮处于禁止状态，即原型图中的B和右括号。数字按键的激活/禁止状态与当前进制有关，例如10进制下不能输入A-F。左括号按钮里可以显示当前未闭合的括号数量，使用的字体列在下屏左上角。
下屏幕右上角是两个抽屉（Drawer），分别负责位宽和符号的显示和切换。位宽以QWORD（64）DWORD（32）WORD（16）BYTE（8）指示，符号就是S（有符号，Signed）或者U（无符号，Unsigned）两种。叫抽屉是因为未来做动画效果的时候希望他们像抽屉一样上下移动。
可行性分析
需求和原型确定之后，在正式编码前需要论证方案在NDS硬件上的可行性。 NDS的输入手段有限（按键+触屏），屏幕分辨率仅256×192，背景图层最多4个且图块固定8×8，调色盘最多256色——这些硬件约束直接决定了UI方案能否落地。以下从输入、显示和按钮状态三个方面逐一分析。
输入
使用LR切换进制，方向键选择按钮，a点击按钮，b输入退格，x输入清空，y切换符号，start计算公式结果，select切换位宽，触摸屏输入数字和运算符。
输入绑定最终可能跟上面有出入，但此阶段只需论证按钮够用。
关于触屏的按钮是否容易误触等问题，甲方举起NDS对着原型图量了半天，说问题不大。
显示
原型图中使用了各个尺寸的Ark-pixel-font等宽（monospaced）字体。上屏的数据类型区和当前输入区使用16px字体，每个字形（Glyph）的尺寸为8×10，由于NDS图块大小为8×8，因此至少需要两个图块（tile）显示一个字符。
公式区和四个进制转换区使用10px字体，字形尺寸为6×8，加上1px阴影尺寸为6×9,最多需要两个图块显示一个字符。换句话说，每个字符对应上下两个图块，其中上方图块可能为空。
等宽字体显示时无需考虑每两个字形之间的间隔，直接紧挨着显示即可。但NDS的硬件限制带来一个问题：背景图层图块大小只能是8×8，只使用一个图层显示6×8字体就无法紧挨着。如果要显示紧邻的6×8字体，有两个方案：
- 使用精灵（sprite）而不是背景图层显示字体。
- 同时使用4个图层显示字体。
问GPT说精灵的使用有诸多限制，譬如每条扫描线上精灵的数量和精灵像素数量分别不能超过多少。算了一下发现有点危险，所以最终还是选择了Plan B：同时使用4个图层显示字体，如图3所示。此时上屏的4个图层就都用到了，没有多余的图层显示一些装饰性的背景颜色。不过UI设计稿里本来就没什么色块，问题不大。
图3: 使用4个图层显示字体。最上为显示效果，下方为4个图层，每两个相邻图层之间偏移2像素，从而实现6x8字体的打印。下屏相对简单一些，目前一共用到3个图层，如图4所示。按钮图层通过8比特位图显示，而不是图块背景，一个图层就搞定了。由于未来可能给两个抽屉添加动画，所以从按钮图层独立出来。两个抽屉共用两个图层，边框用一个图层，标题在另一个图层。最后一个图层留给动画备用。
图4: 下屏图层示意图。Layer 3是8-bit位图，显示所有按钮。layer2-3分别是边框图层和文字图层。按钮禁用与选中
从原型设计稿里可以看到，被禁用的按钮是灰色的。为了实现这一点，有两条技术路线。当按钮禁用状态更新时，1. 修改按钮的颜色索引；2. 修改按钮的调色盘。
为对比两种思路的优缺点，首先要介绍一下NDS的图层特性。当图层是16位位图（bitmap）时，其每个像素点的存储宽度都是16；当图层是16位位图以外的类型时，其显示内容由两部分决定：位图和调色盘（palette）。例如，假设图层类型是8位位图，每个像素深度为8，所以每个像素都占8比特，也就是1字节。假设最开始的4个像素点的bitmap是01 02 03 04，那么他们的颜色分别是调色盘里偏移分别为1、2、3、4的颜色。如果位图里某个像素点的索引为0，则为透明。屏幕上某一点处如果各个图层相对位置的索引都是0，则显示为调色盘偏移为0处的颜色，也就是backdrop。libnds与backdrop相关的API就是操作BG_PALETTE[0]的API。
替换按钮的颜色索引是一种容易想到的思路：通过修改位图来更新颜色，也就是将新的索引写入VRAM特定地址。这种做法需要知道每个按钮的坐标，例如边框点的坐标，所有内部背景点的坐标，阴影点的坐标，等等。由于本计算器设计有5种尺寸的按钮，所以这在工程实现方面相当复杂，需要大量硬编码的像素点坐标。
本项目选择了修改按钮调色盘的方案，现举例说明。假设按钮有3个组成部分，分别具有颜色：边框（酒红色）、背景（白色）、标题（黑色）。当选中时，一部分背景像素变为酒红色，当禁用时，颜色方案变为边框（深灰色）、背景（浅灰色）、标题（深灰色）。整理各像素在不同按钮状态下的颜色有以下几种：
表1: 各像素在不同按钮状态下的颜色方案| 像素类型 | 默认 | 选中时 | 禁用时 |
|---|
| 边框 | 酒红色 | 酒红色 | 深灰色 |
| 选中线 | 白色 | 酒红色 | 浅灰色 |
| 背景 | 白色 | 白色 | 浅灰色 |
| 标题 | 黑色 | 黑色 | 深灰色 |
根据表1可以看出，选中线在默认状态下与背景无异，但当按钮被选中时显示为重点色；当按钮被禁用时，所有像素都变成深灰/浅灰。
现在我们尝试通过调色盘控制按钮的颜色方案。先只考虑一个按钮。我们将该按钮的边框、选中线、背景和标题像素的索引分别编码为1、2、3、4。默认状态下调色盘对应位置的颜色分别为酒红色、白色、白色、黑色，与表格第2列相同。当按钮被选中时，将调色盘偏移为2的颜色改为酒红色，那么当前调色盘就变成了酒红色、酒红色、白色、黑色，与表格第3列相同；同理，当按钮被禁用时，替换调色盘为表格第3列的深灰色、浅灰色、浅灰色、深灰色，该按钮就显示成一堆灰色了。
对于个按钮，假设按钮有个状态，每个按钮有个像素类型（上例中），按顺序依次编码每个按钮的每个像素类型为1, 2, 3, 4, … 按钮编码一共要占用个调色盘颜色。再加上偏移为0的背景色占用1个调色盘颜色、按钮颜色方案要占用个调色盘颜色，总共需要个颜色。由于调色盘数量限制，该值需要小于256。
目前本软件一共有3个按钮状态：默认、选中和禁用；每个按钮有5种像素类型；一共有32个按钮；共占用176个调色盘颜色。即使加上为抽屉图层预留的15个颜色（4bpp最大颜色数减一个背景色）也绰绰有余了。
架构设计
软件总体采用MVVM架构，使用事件总线（Event Bus）进行通信，使用指令（Commands）隔离输入层与事件层，如图5所示。
图5: HexCalculatorDS架构示意图。最下方是硬件相关组件，包括屏幕、图层和输入。其中，对应位于NDS下方触屏屏幕的子屏幕（sub screen），只用了编号1-3的3个图层，编号0图层留作备用，以后可能用来实现动画，或者显示版本信息。Input模块从寄存器读取按键和触屏输入，经指令模块转换为事件后进入事件总线。事件总线具有单向性，按输入→模型→视图的顺序，后者不会触发前者监听的事件。有关事件的设计参考事件队列与订阅一节。
架构每一层都对上下层隐藏互相的细节。例如视图（View）层并不关心Layer的存在，即对于视图来说Layer是透明的。视图层只需知道调用Display可以在特定位置显示字形（Glyph），而不关心具体实现。
在讨论其他一切组件的生命周期之前，必须先确定软件的生命周期。对于运行在NDS上的软件来说，软件永远存活，除非按电源键关机。所以，软件的生命周期就是一个死循环。每次循环里，至少要依次做三件事：获取用户输入，处理事件队列，更新视图。伪代码如下所示。
pseudo main loopMVVM组件
MVVM架构由模型（Model），视图（View）和视图模型（ViewModel, VM）三部分组成。其中模型关心数据而不关心显示，对于我们的计算器来说，主要就是公式的状态与更新、当前输入值的状态与更新；视图关心显示而不关心数据，本软件所谓的显示主要就是排版：跳过N个字符位置，打印M个字符，清空上次打印的旧字符等等；视图模型是模型和视图的桥梁：视图通过VM获取数据，此处的数据往往忽略一些模型层次的细节，又有视图层次的细节。
以输入数字为例。当输入数字更新时，例如从之前的“123”，经由用户输入“4”，变成“1234”（在10进制前提下），FormulaModel检查是否超过最大值然后更新当前值，然后通知相关视图更新。 ValuView接收到通知后，调用vm的方法获取一组当前进制（10进制）的字（digit），将其格式化为形如1,234的一系列字形（glyph），然后显示。
在M、V、VM三种组件中传递时，数字被如下变换。
| 数据格式 | 作用范围 | 说明 |
|---|
| 整形(int) | Model | 模型层存有整型数、当前计算器的进制、位宽、是否有符号等信息 |
| Digit数组 | ViewModel | VM层根据进制、位宽、是否有符号等信息将数字转换为一系列的字 |
| Glyph数组 | View | 视图层将Digit数组转换为可直接打印的字形，排版后打印 |
可以看到，模型层不关心数字如何显示，只关心如何存储；视图层不关心数字是如何存储的，只关心字形。VM提供了一种透明的接口，对视图隐藏了模型的存储细节。
事件队列
事件总线（Event Bus）由三部分组成，事件（Event）、监听者（EventListener）和发布者（EventDispatcher）。
事件的生命周期非常简单。1. 调用发布者创建事件；2. 通知监听者进行处理；3. 销毁。
事件总线里通常有多个事件待处理。所以，事件总线是一个队列，先进先出（FIFO）。
有时监听者可能会创建新的事件，但事件总线是单向的。这不是说事件总线可能在发布到一半的时候终止，而是说按输入→模型→视图的顺序，后者不会触发前者监听的事件。
例如FormulaModel监听按键输入事件InputEvent，当值发生改变时就会触发ValueChangeEvent，被ViewModel/FormulaView监听，但输入层的InputHandler不会也没有必要监听ValueChangeEvent。
公式的存储与显示
公式由数字和运算符两种元素组成，可以用树状结构表示。由于本软件涉及的运算符只有一元运算符（unary operator）和二元（binary）运算符，所以运算符节点至多有两个子节点，也就是说，本软件涉及的公式可以用二叉树表示。按结合（associativity）方式，公式树分为左结合和右结合两类，如图6展示了一些简单公式的树结构。本软件的公式树是右结合树，因为插入符号实现相对简单，具体说明参见下一节。
图6: 完整公式树示意图。其中深灰色表示根节点，蓝色为运算符，黄色为数字。(a) 1+2的树表示；(b) 1+2-3的左结合树表示；(c) 1+2-3的右结合树表示。对公式树求值非常简单，后序遍历（左→右→中）所有节点求值即可。以图6c为例，首先求减号子树的值，然后求加号子树的值。本软件的公式树是右结合树，因为对插入符号比较友好，具体说明参见下一节。
公式树的节点有两种类型：要么是数字，要么是运算符。数字节点是叶子节点，没有子节点；而运算符节点是内部节点，至多有2个操作数。例如，一元运算符如左括号(，只有一个子节点，并且一定是左子节点；二元运算符如减号-，有两个子节点，分别是左子节点和右子节点。当运算符的子节点数量等于其运算数数量时，称该运算符节点为完整的（complete），否则为不完整的（incomplete）。
理论上，公式字符串可以通过中序遍历公式树得到。但是，公式树的规模会影响遍历时长。在极端情况下，输入很长的公式会导致软件“越来越卡”。所以，我在VM里加了一道缓存，以空间换时间，同步FormulaModel更新VM层缓存的公式的字形数组，通过事件总线实现的。当用户输入数字/运算符时，经Commands触发InputEvent，FormulaModel获取输入的数字/运算符，尝试将其加入公式树。如果失败，说明输入不合法；如果成功，就触发NumberAcceptEvent或者OperatorAcceptEvent。VM监听这两个事件，并根据相应的数字/运算符更新缓存的字形数组。
公式树的插入与求值
公式树初始化时只有一个根节点=。用户不断输入数字和运算符，树逐步生长。公式树接收输入数据（运算符/数字）的核心逻辑按当前节点类型和输入数据的类型分为4种情况，如表2所示。
表2: 公式树插入逻辑的分类| 当前节点类型 | 输入数据类型 |
|---|
| 不完整的运算符 | 数字 |
| 表达式（数字/完整的运算符） | 运算符 |
| 不完整的运算符 | 左括号 |
| 其他情况（两个数字相邻、两个运算符相邻） | 任意 |
- 当前节点是不完整的运算符，输入数字：创建新节点，挂到当前运算符的子节点上。若运算符为一元则挂左子节点，否则挂右子节点。当前节点指向新数字节点。
- 当前节点是表达式（数字或已闭合的括号），输入运算符：根据优先级决定新运算符在树中的位置（详见下文）。当前节点指向新运算符节点。
- 当前节点是不完整的运算符，输入左括号：创建新的左括号节点，作为当前运算符的子节点。
- 其他情况（两个数字相邻、两个非括号运算符相邻等）：拒绝输入。
以公式1 + 2 × 3的输入过程为例，图7展示了公式树的逐步生长。
图7: 公式1+2×3的逐步插入过程。(a) 输入1；(b) 输入+；(c) 输入2；(d) 输入×；(e) 输入3。其中(b)→(c)和(d)→(e)属于情况1：当前节点是不完整的运算符（+和×），输入的是数字。(a)→(b)和(c)→(d)属于情况2：当前节点是一个完整的表达式（数字1和数字2），输入的是运算符。(c)→(d)是情况2中值得注意的一步。此时+已经有了左右两个子节点（1和2），新的运算符×需要在树中找到正确的位置。算法通过比较新运算符与当前节点的父节点的优先级来决定：
- 新运算符优先级高于或等于父节点运算符：新运算符“插入”到父节点和当前节点之间。具体来说，新运算符替代当前节点成为父节点的子节点，当前节点成为新运算符的左子节点。(c)→(d)即为此情况：
×优先级高于+，于是×替代2成为+的右子节点，2变成×的左子节点。 - 新运算符优先级低于父节点运算符：新运算符“提升”到更高的层级。具体来说，新运算符替代父节点成为祖父节点的子节点，父节点整体成为新运算符的左子节点。图8展示了在
1 + 2 × 3后插入-的情况。 - 父节点是
=或(时：特殊处理，新运算符直接“接管”当前位置。在(a)→(b)中，1的父节点是=，于是+替代1成为=的左子节点，1变成+的左子节点。
运算符的优先级参见附录A。
图8: 低优先级运算符的插入。(a) 公式1+2×3的树；(b) 插入-之后的树。减号优先级低于加号，于是减号替代加号的位置成为根节点=的子节点，而加号子树成为减号的左子节点。右括号的处理比较特殊：收到右括号时不创建新节点，而是从当前节点向上查找，找到最近的未闭合的左括号节点，将其标记为已闭合，并将当前节点指向该左括号。已闭合的左括号节点在后续运算中被视为一个完整的表达式。另外，等号=也可以被视为一个特殊的括号类型，区别在于左括号(被右括号)闭合，而等号=被另一个等号=闭合。并且，当根节点=被闭合时，说明公式输入完成，可以进行求值了。
公式树的求值在用户按下等号时触发，对整棵树进行后序遍历求值。每个节点的求值方法根据自身类型执行不同的操作：
- 数字节点：值就是自身。
- 一元运算符（
=、(）：直接取左子节点的值。 - 二元运算符（
+、-、×等）：取左右子节点的值，执行相应运算。对于除法和取模，还需检查除数为零的情况。
求值完成后，需要保存求值结果和求值状态（成功/除0/其他失败原因）。
代码与项目构建
确定软件架构之后是技术选型。我选择C++17标准的C++进行开发，最主要的理由是我希望用constexpr表示一些编译期就能确定的常量。其次我也想趁此机会尝试一下C++开发，因为类似的嵌入式场景，我通常都选择C。最后我还希望模板编程可以打通不同层次之间的隔离，虽然编程阶段的渲染管线是层次分明的，但我希望可执行文件里对性能有足够的优化。
项目依赖管理使用CMake，不知是不是自己写编译规则的原因，使用最新的libnds v2.x编译出来的东西无论如何就是一片空白，只好回退到v1.8.x。（应该不是，因为他们的hello world例子编译了也这样）也没有选择BlocksDS，有些函数不太一样，徒增我的学习成本。 devkitPro团队的libnds v1.8.x已经够我用了。
本项目最终的构建目标是生成一个可以直接运行在NDS模拟器和实机上的软件。为此，需要准备图标（icon）、ARM9和ARM7的可执行文件。图标是一个bmp格式文件，要求其颜色不能超过16种，也就是4bpp带调色盘的图片。我画了一个蓝色的图标，虽然目前软件主题是酒红色的……ARM9的可执行文件是编程的核心，一切前后端逻辑都在这里。ARM9可以工作在thumb格式，该模式下每条指令只有16比特，比ARM9模式的32比特少一半。通常游戏里不重要的流程代码都是thumb模式，省体积。但本软件本没有那么大量的代码，所以直接默认ARM9模式了。ARM7处理器的作用通常是加载音频，处理系统中断等，本项目并不需要这些功能，使用libnds默认即可。
图形资产
图形资产目前有3个：上屏字体、下屏字体和下屏按钮图片。其中两个字体文件都使用Aseprite进行设计，基于Ark-pixel-font，添加阴影，微调字形。下屏图块地图（tilemap）除字形之外还有抽屉的边框、抽屉的内容。
抽屉标题做了硬编码。例如位宽抽屉标题可以是QWORD或WORD，并没有按照字母将两者分别划分为5字符或4字符，而是都当5字符处理。这是因为当标题字符数量改变时，因为居中显示的原因，标题里各字形的位置也发成了改变，且偏移不为8的整数倍，也就是说无法在不滚动该图层的前提下将字形显示在正确的位置。图层不应该滚动，因为两个抽屉的标题共享同一个图层。于是折衷方案就是将位宽标题视作固定的5×2个图块区域。好在本项目对图块地图大小和内存占用要求非常低，这种方案仍然具有可行性。
下屏按钮图片使用专门的Python代码进行处理。该程序读取我的下屏设计稿，使用OpenCV自动识别按钮位置（酒红色的闭合曲线），根据按钮禁用与选中一节中提到的方式编码调色盘，生成256色的索引BMP图片。最后用grit处理成C源文件，方便导入。为了节省一点体积（不确定后续开发成Download Play软件是否有只要），图形资产在grit处理阶段都压缩了一下，程序初始化时解压缩到相应VRAM地址。
事件与监听
事件总线（Event Bus）由三部分组成，事件（Event）、监听者（EventListener）和发布者（EventDispatcher）。
事件是一个简单的结构体，有数据和类型两个字段。EventDispatcher是事件总线的核心，负责控制事件的生命周期，提供事件入队、分发、销毁的API。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| template <size_t ListenerCapacity, size_t QueueCapacity>
class EventDispatcher {
public:
template <typename Listener> bool Subscribe(Listener &listener);
bool Post(const Event &event);
void DispatchPending(void);
private:
CircularQueue<Event, QueueCapacity> eventQueue;
EventListener listeners[ListenerCapacity];
size_t listenerCount;
};
using EventBus = EventDispatcher<16, 32>;
|
其中模板参数ListenerCapacity表示最大订阅者数量，QueueCapacity表示事件队列里事件数量。公共方法Subscribe()用来添加订阅者Listener类，这是一个封装类，稍后介绍；Post()方法向队列里新增一个事件；DispatchPending()遍历队列处理所有的事件，对每个事件，调用所有订阅者的OnEvent()回调。
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
| enum EventResult {
Failed = -1,
Consumed = 0,
Skipped = 1,
Emitted = 2
};
class EventListener {
public:
using Handler = EventResult (*)(void *, const Event &);
template <typename T>
static EventListener
From(T &instance) {
return EventListener(
static_cast<void *>(&instance),
[](void *ctx, const Event &event) -> EventResult {
return static_cast<T *>(ctx)->HandleEvent(event);
});
}
EventResult
OnEvent(const Event &event) const {
if (handler == nullptr) {
return Skipped;
}
return handler(context, event);
}
private:
EventListener(void *context, Handler handler)
: context(context), handler(handler) {}
void *context;
Handler handler;
};
|
EventListener是兼容层，提供模板函数EventListener::From()，任何具有EventResult HandleEvent(const Event &)方法的类都可以由此转换为一个EventListener。某种程度上，这是禁止使用虚函数的绕路方案。
视图
所有视图类都继承自基类BasicView，且需要指定模板参数DisplayType为MainDisplay或SubDisplay。视图基类BasicView对视图刷新提供了简单的封装，用一个dirty字段表示当前视图是否需要刷新，提供对外的Update()方法，当dirty = true也就是需要刷新调用子类实现的ForceUpdate()方法。
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
| template <class Derived, typename DisplayType>
class BasicView {
public:
BasicView(DisplayType &display) : dirty(true), display(display) {}
EventResult
HandleEvent(const Event &e) {
return Skipped;
}
void
Update(void) {
if (dirty) {
static_cast<Derived *>(this)->ForceUpdate();
}
dirty = false;
}
protected:
DisplayType &display;
void
markDirty(void) {
dirty = true;
}
private:
bool dirty;
};
|
上下两个屏幕显示的东西不同，所以MainDisplay和SubDisplay封装的方法有所区别。上屏幕4个图层都用来显示字，所以MainDisplay提供一些打印相关的接口，下屏幕需要控制按钮状态，所以SubDisplay提供按钮的禁止/选中/激活等接口。
上屏幕的视图类都继承MainView，布局如图9所示。 MainView指定了DisplayType为MainDisplay，同时又新增模板变量ViewAlign，表示该视图是左对齐还是右对齐的。
图9: 上屏幕视图布局示意图，显示出每个组件的对齐属性和大致的高度。其中Indicator是指示条组件，用来指示value的当前进制。图中将指示条作为单独的组件而不由各进制组件控制，是因为指示条由3个从上往下的tile组成，比数字和字母的2个tile要高1格。例如如果在Transcode<Decimal>里显示指示条，可能会被上方的Transcode<Hexadecimal>或下方的Transcode<Octal>覆盖。上屏幕视图相关类定义如下所示。
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
| enum ViewAlign {
AlignLeft,
AlignRight,
};
template <class Derived, ViewAlign Align>
class MainView : public BasicView<Derived, MainDisplay>;
class ConfigView : public MainView<ConfigView, AlignLeft>;
class FormulaView : public MainView<FormulaView, AlignRight>;
class ValueView : public MainView<ValueView, AlignRight>;
template <NumberBase Base>
class TranscodeView : public MainView<TranscodeView<Base>, AlignLeft>;
using HexView = TranscodeView<Hexadecimal>;
using DecView = TranscodeView<Decimal>;
using OctView = TranscodeView<Octal>;
using BinView = TranscodeView<Binary>;
class IndicatorView : public MainView<IndicatorView, AlignLeft>;
|
下屏幕的视图简单许多，只有一个InputView，继承自SubView。比较特殊的一点是，InputView还承担将触屏坐标转换为相应按钮事件的责任。在图5架构图中，Input模块不仅指向Commands，也与InputView相接，体现出这一点。另外，按钮的概念不该在SubDisplay出现，是视图层才应该知道的；但与此同时，视图层也不该知道调色盘这种硬件细节。我暂时还没想好怎么处理，先都放在SubDisplay里。
1
2
3
| template <class Derived>
class SubView : public BasicView<Derived, SubDisplay>;
class InputView : public SubView<InputView>;
|
用户触屏时，首先由Input模块做防抖、去重等处理，然后触发TouchScreenEvent。 InputView监听该事件，当触发时比较触屏坐标与所有按钮“碰撞箱”，确定是否有按钮被点击，调用被点击按钮的触发函数，触发一个内容是字（digit）或运算符的InputEvent。
数字-字形渲染管线
前文提到，当输入数字更新时，FormulaModel处理结束后触发ValueChangeEvent，通知相关视图更新。数字从Model层到硬件层的完整变换过程如表3所示。
表3: 数字-字形渲染管线表| 数据格式 | 作用范围 | 说明 |
|---|
| uint64_t | Model层 | 进制不会影响数字存储，符号视情况而定 |
| DigitArray | ViewModel层 | 将数字转换为一系列的字（Digit） |
| GlyphArray | View层 | 将字数组转换为可直接打印的字形（Glyph） |
| GlyphFormatArray | View层 | 添加前导零、分隔符和负号 |
| 图块（tile） | 硬件层 | MainDisplay接收字形和位置信息，修改相应内存数据 |
前两步已经在MVVM组件一节介绍过了。这里重点说明View层内部的变换：从DigitArray到格式化的GlyphFormatArray。
GlyphArray是基础的字形容器。它是一个定长数组，模板参数W、H指定字形像素尺寸（对应8×8和6×8两种字体），N指定最大容量。GlyphArray可以直接从DigitArray构造，将每个Digit加上字体基址偏移（fontZero）转换为对应的Glyph。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| template <int W, int H, size_t N>
class GlyphArray {
public:
explicit constexpr GlyphArray(DigitArray<N> digits, bool reverse = false)
: glyphs{}, size(0), negative(digits.negative) {
for (size_t i = 0; i < digits.size; i++) {
this->Insert(
Glyph(static_cast<FontType>(digits[...] + fontZero)));
}
}
protected:
Glyph glyphs[N];
size_t size;
};
|
此时GlyphArray里存的只是“裸”的数字字形序列，没有分隔符也没有前导零。
GlyphFormatArray继承自GlyphArray，在构造时自动完成三个步骤：补齐前导零（padding）、插入符号位、按组插入分隔符。这三个步骤的行为都由模板参数控制：
PaddingGroupSize：前导零补齐的分组长度。例如16进制设为4表示总位数必须是4的整数倍，例如DEAD不补零但1补为0001。Signable：是否需要符号位。实际上只有10进制为true，负数时在最前面插入负号字形。GroupSize：分隔符的分组长度。16进制和2进制每4位分隔，10进制和8进制每3位分隔。Separator：分隔符字形。10进制使用逗号,，其他进制使用空格（FontEmpty，宽度等同一个字符但不显示）。
1
2
3
4
5
6
7
8
9
10
11
12
| template <FontType Separator, int GroupSize, int PaddingGroupSize,
bool Signable, int W, int H, size_t N>
class GlyphFormatArray : public GlyphArray<W, H, > {
public:
explicit constexpr GlyphFormatArray(const GlyphArray<W, H, N> &glyphArray)
: Base() {
}
};
|
GlyphFormatArray的最大容量在编译期由GlyphFormatSize()和GlyphPaddedDigitCount()两个constexpr函数计算得出，公式为
其中是按PaddingGroupSize（）补齐后的位数，是GroupSize，在Signable为true时取1否则取0。
不同进制的格式化参数由GlyphFormatTraits特化提供，汇总如下。
讨论
通过调色盘控制图形显示
指针、引用和数组越界
面向NDS编程动态调试极其困难。我知道的唯一的一个解法是下载特定版本带gdb的DeSmuME模拟器，但这要求开发环境要有图像界面。为了使用devkitPro提供的旧版libnds，我使用devkitPro提供的旧docker作为开发容器，也就失去了运行时调试的能力。最终只能使用传统“瞪眼法”或者“打印法”进行调试。然而“打印法”存在隐患：对于局部变量全局化之类的UB，debug函数可能会改变它的生命周期，出现“Debug的时候好好的怎么Release版就炸了”的问题。而devkitARM提供的gcc并没有sanitizer编译选项——即使提供了也只能在运行时而不是编译期发现问题。所以，UB、数组越界和空指针解引用的代价是高昂的。
为了尽量避免数组越界，本软件没有引入任何动态大小的数组，所有数组类型的大小在编译器都已确定，这也符合嵌入式开发避免在堆上开辟内存的原则。
1
2
3
4
5
6
7
8
9
10
| class Digit {
};
template <size_t N>
class DigitArray {
private:
Digit digits[N];
size_t size;
};
|
为了避免空指针解引用，对于一定不为空的引用，使用C++的引用类型；对于可能出现空引用的代码，其实就是公式树，写了单元测试。测试程序面向开发容器本地CPU架构，不使用面向NDS的工具链。虽然容器本地CPU是64位与NDS的32位不同，但我的代码几乎没有平台有关的部分，所以不影响测试。
状态管理与缓存
在MVVM模式下，理论上视图（views）可以是无状态的。也就是说，当触发视图更新时，视图可以通过ViewModel的接口获取全部所需的数据，而不必自己存储数据，从而实现视图与模型的充分解耦。但在实际操作中，我的各视图类多多少少有几个字段，可以视作缓存。
例如所有视图类都有的dirty属性：这是一个布尔值，表示当前视图类是否需要刷新。在MVVM组件一节已经介绍过，每个主循环的最后要刷新一次视图。使用dirty属性可以保证按需刷新每个视图，且至多刷新一次。
指示当前进制的IndicatorView存有当前进制currentBase。假设没有这个字段，IndicatorView可以刷新整个显示区域，然后绘制指示条。但有这个字段之后，只需要擦除旧的指示条再绘制新的指示条。
总结
本文介绍了面向Nintendo DS平台的16进制整数计算器软件HexCalculatorDS的设计与实现，涵盖需求分析、可行性论证、架构设计及关键模块的实现细节。
在架构层面，软件采用MVVM模式并以事件总线解耦各层通信，全部数据结构使用编译期确定大小的静态数组，满足嵌入式环境零堆分配的要求。在模型层面，本软件采用右结合二叉树表示公式结构，并基于运算符优先级比较设计了（为树高）的插入算法，同时在视图模型层引入字形缓存以避免公式显示时的重复遍历。在显示层面，本软件提出了两项针对NDS硬件特性的方案：一是利用8-bit位图调色盘的间接寻址机制实现按钮多状态显示，将个按钮、种状态的图形更新简化为的调色盘写入操作；二是通过4个背景图层各偏移2像素的叠加策略，在8×8图块约束下实现了6×8等宽字体的无间距排列。
附录A：运算符优先级
优先级排序数字越小，代表运算符优先级越高。其中等号=是特殊的运算符，作为公式树的根节点，优先级最高。当新运算符的优先级高于或等于当前节点的父节点的运算符时，新运算符“插入”到父节点和当前节点之间；当新运算符的优先级低于当前节点的父节点的运算符时，新运算符“提升”到更高的层级。
| 排序 | 运算符 | 含义 |
|---|
| 0 | = | 等号（根节点） |
| 1 | ( ) | 括号 |
| 2 | * / % | 乘、除、取模 |
| 3 | + - | 加、减 |
| 4 | << >> | 左移、右移 |
| 5 | & | 按位与 |
| 6 | \| | 按位或 |
附录B：NDS硬件回顾
第一次接触NDS开发的读者，直接去读正文想必云里雾里。这一节简单介绍一些本文用到的NDS硬件相关的基础知识。
两颗CPU
NDS内部有两颗ARM处理器，采用非对称多处理架构。
ARM9（ARM946E-S）是主处理器，运行频率约67 MHz，负责执行游戏/应用程序的全部逻辑。ARM9支持两种指令集模式：ARM模式下每条指令为32比特，Thumb模式下每条指令为16比特。Thumb模式的优势在于节省ROM体积，通常游戏中不关键的流程代码会使用Thumb模式编译。本软件代码量不大，因此全部使用ARM模式。
ARM7（ARM7TDMI）是子处理器，运行频率约34 MHz，与GBA的CPU相同。ARM7负责管理大部分I/O端口，主要承担音频处理和系统中断等辅助工作。ARM9不能直接访问I/O端口，需要通过ARM7中转。两颗CPU之间通过一个专用的FIFO队列进行通信。本软件不涉及音频功能，ARM7直接使用libnds提供的默认程序即可。
编译NDS软件时，需要分别为ARM9和ARM7生成可执行文件，最后和图标一起打包为.nds文件。
双屏与触屏
NDS有两块LCD屏幕，每块分辨率为256×192像素，支持262144种颜色（18比特色深），刷新率约60 Hz。上方的屏幕称为主屏幕（main screen），下方的屏幕称为子屏幕（sub screen），子屏幕带有电阻式触摸屏。
每块屏幕由一个独立的2D引擎驱动。主引擎（Engine A）功能较强，辅助引擎（Engine B）功能稍弱。软件可以自由配置哪个引擎连接哪块物理屏幕。本软件将主引擎连接到上屏显示公式和计算结果，辅助引擎连接到下屏显示按钮界面和触屏交互。
内存与VRAM
NDS的RAM分散在多处。与本软件直接相关的是VRAM（显存），总计656 KB，被划分为9个bank（A~I），大小从16 KB到128 KB不等。开发者需要将各bank映射到2D引擎的特定用途（背景、精灵、调色盘等），两个引擎不能同时访问同一个bank。
NDS采用内存映射I/O（Memory-Mapped I/O）的方式控制硬件：硬件寄存器被映射到特定的内存地址，程序通过读写这些地址来配置图层模式、设置调色盘颜色、触发DMA传输等操作。例如，背景调色盘位于BG_PALETTE起始的一段内存区域，其中BG_PALETTE[0]是backdrop颜色——当屏幕上某一点处所有图层都是透明时，显示的就是这个颜色。
2D图像模式
每个2D引擎可以生成最多4个背景图层（BG0~BG3），各图层独立配置、可以叠加显示。图层的类型取决于当前设定的背景模式（Mode 0~5），不同模式下各图层支持的功能不同。 表5列出了所有模式中各图层的类型，本软件上屏使用模式0（4个文本图层），下屏使用模式5（2个文本图层+2个扩展图层，其中一个配置为8比特位图）。
表5: NDS背景模式与图层类型| 模式 | BG0 | BG1 | BG2 | BG3 |
|---|
| 0 | Text/3D | Text | Text | Text |
| 1 | Text/3D | Text | Text | Affine |
| 2 | Text/3D | Text | Affine | Affine |
| 3 | Text/3D | Text | Text | Affine Extended |
| 4 | Text/3D | Text | Affine | Affine Extended |
| 5 | Text/3D | Text | Affine Extended | Affine Extended |
其中Text（文本）图层是最基本的图块背景，可以滚动、翻转；Affine（仿射）图层支持旋转和缩放等仿射变换；Affine Extended（扩展仿射）图层在仿射的基础上还支持作为位图（bitmap）帧缓冲使用。主引擎的BG0还可以替换为3D引擎的输出。
图块（tile）是2D图形的基本单位，大小固定为8×8像素。文本图层和仿射图层通过图块地图（tilemap）引用VRAM中的图块数据来构建画面：地图中的每个条目指定一个图块编号和翻转属性，引擎根据地图逐图块拼出整个背景。本软件上屏使用4个文本图层显示字体，下屏按钮则使用8比特位图模式直接写入像素。
调色盘（palette）是颜色的间接寻址机制。当图层不是16比特位图时，每个像素存储的不是颜色值，而是调色盘中的索引。索引为0的像素视为透明。8比特位图（8bpp）模式下每个像素占1字节，可索引最多256种颜色；4比特（4bpp）模式下每个像素占半字节，可索引16种颜色。本软件利用调色盘的间接寻址特性，通过替换调色盘颜色而非修改位图数据来切换按钮的默认/选中/禁用状态。
精灵（sprite，又称OBJ）是独立于背景图层的可移动图形对象。每块屏幕每帧最多显示128个精灵，但每条扫描线上可显示的精灵数量和像素数量有上限。本软件对精灵的使用很克制，主要用多个背景图层偏移叠加的方式实现了字体显示。
Fin.
参考链接