汇编练习：不会溢出的除法

王爽老师的《汇编语言》在实验10.2中提出了div指令可能出现的除法溢出的问题。例如对于16位除以8位的情形，考虑被除数是0x1234，除数是0x01。根据div的约定，商在AL中，余数在AH中。但是显然计算结果的商是0x1234，8位的AL无法容纳，因此会产生除法溢出。使用Bochs调试时，会在div之后出现iret，即CPU产生了一个中断返回指令。
为了兼容32位对16位的除法，设计一个双字除法调用过程divdw：

输入：
- 被除数：一个32位的整数，高16位在DX中，低16位在AX中
- 除数：一个16位的整数，存储在CX中
输出：
- 商：32位的整数，高16位在DX中，低16位在AX中
- 余数：16位整数，储存在CX中

因为商也是双字长，因此divdw过程一定不会发生除法溢出。这是因为，考虑被除数最大是0xFFFFFFFF，除数最小是0x0001，则商最大为0xFFFFFFFF，不会超过双字长。但是直接使用div指令是无法办到的，所以我们下面需要设计divdw的过程。首先给出一个数论中关于带余数除法的引理：

(带余数除法)：设 $a,b$ 是两个整数， $b\neq0$ ，则存在唯一的整数对 $(p,r)$ ，使得 $a=pb+r\quad (0\leqslant r <|b|)$

我们接下来约定，符号 $\frac{a}{ b}$ 表示实数除法， $\mathrm{int}(\frac{a}{b})$ 表示整数除法的商，相当于上面的 $p$ ； $\mathrm{rem}(\frac{a}{b})$ 表示整数除法的余数，相当于上面的 $r$ 。例如，对于 $a=7,b=3$ ，我们有 $\frac{a}{ b}=2.333\dotsc,\mathrm{int}(\frac{a}{b})=2,\mathrm{rem}(\frac{a}{b})=1$

现在来考虑双字除法。设被除数如下： $D=\mathrm{0x\ }\underbrace{a_{31}a_{30}\dotsc a_{16}}_{DX}\underbrace{a_{15}a_{14}\dotsc a_{0}}_{AX}$ 如同我们可以把10进制数 $1234$ 写成 $12\times100+34$ ，16进制下的数 $D$ 可以写为 $\begin{split} D&=\mathrm{0x\ }\underbrace{a_{31}a_{30}\dotsc a_{16}}_{H}\times \mathrm{0x}\underbrace{100\dotsc0}_{16\;0's}+\mathrm{0x}\underbrace{a_{15}a_{14}\dotsc a_{0}}_{L}\\&=H\times65536+L\end{split}$ 显然 $H$ 和 $L$ 分别是寄存器DX和AX中的值。
现在设除数是 $n$ ，从而 $\frac{D}{n}=\frac{H}{n}\times 65536+\frac{L}{n}$ 再次强调此时我们表示的是实数除法。根据整数带余数除法引理，对于 $H,n$ ，又存在唯一的如下表示 $H=\mathrm{int}(\frac{H}{n})\times n+\mathrm{rem}(\frac{H}{n})$ 其中 $0\leqslant \mathrm{rem}(\frac{H}{n}) <n$ ，从而 $\frac{H}{n}=\mathrm{int}(\frac{H}{n})+\frac{\mathrm{rem}(H/n)}{n}$ ，于是 $\begin{split} \frac{D}{n}&=\left(\mathrm{int}(\frac{H}{n})+\frac{\mathrm{rem}(H/n)}{n}\right)\times 65536+\frac{L}{n}\\ &=\mathrm{int}(\frac{H}{n})\times 65536+\frac{1}{n}\left(\mathrm{rem}(\frac{H}{n})\times65536+L \right)\end{split}$ 因为 $H$ 是16位的，因此 $H$ 除以 $n$ 的整数部分 $\mathrm{int}(H/n)$ 必然也不超过16位。
对于括号中的部分，讨论其取值范围（设 $n$ 是正整数） $\begin{split} 0\leqslant& \mathrm{rem}(\frac{H}{n})\leqslant n-1\\ 0\leqslant& \mathrm{rem}(\frac{H}{n})\times 65536 + L \leqslant 65536\times (n-1)+L \end{split}$ 因为 $L$ 是16位整数，故 $L<65536$ ，于是 $\begin{split} 0\leqslant& \mathrm{rem}(\frac{H}{n})\times 65536 + L <65536\times n \\ 0\leqslant& \frac{1}{n}\left(\mathrm{rem}(\frac{H}{n})\times65536+L \right)< 65536 \end{split}$ 由此可知，对其取整的结果： $\mathrm{int}\left[\frac{1}{n}\left(\mathrm{rem}(\frac{H}{n})\times65536+L \right)\right]$ 不超过16位。

现在，令 $\begin{cases} P&=\mathrm{int}(H/n)\\ Q&=\mathrm{int}\left[\frac{1}{n}\left(\mathrm{rem}(\frac{H}{n})\times65536+L \right) \right]\\ r&=\frac{1}{n}\left(\mathrm{rem}(\frac{H}{n})\times65536+L \right) -Q \end{cases}$ 我们重新叙述结果：
$\frac{D}{ n}=P\times 65536 + (Q+r)\quad(P,Q\in\mathbb{N},r\in\mathbb{R})$ 换句话说
$D=(P\times65536+Q)\times n + r\times n$ 显然 $n\times r$ 是整数，并且 $n\times r<r$ 。这是因为通过定义可知， $r$ 是实数 $(\mathrm{rem}(H/n)\times65536+L)/n$ 减去它的整数部分（即 $Q$ ），因此结果就是该实数的小数部分，因此 $r\in[0,1)$ ，从而 $n\times r\in\{0,1,\dotsc,n-1\}$ ，根据带余数除法引理，这个余数 $n\times r$ 是唯一的。

因此我们有
$\begin{cases} \mathrm{int}(\frac{D}{ n})&=P\times 65536 +Q \\ \mathrm{rem}(\frac{D}{ n})&=n\times r=D-(P\times65536+Q) \end{cases}$ 因为 $P,Q$ 均不超过16位，因此除法结果，商的高16位 $P$ 存储在DX中，低16位 $Q$ 存储在AX中，余数 $\mathrm{rem}(\frac{D}{n})$ 不能大于除数 $n$ ，故而也可以安全存储在CX中。