64位除法的单元测试

Question

我的任务是对64位除法函数进行单元测试(我们在汇编程序中为PPC编码了该函数，但这并不重要(。

到目前为止，我已经：

• 最大值div最大值
• 最大值div最小值
• 最大值div减去最大值
• div zer0的最大值
• 零div最大值
• 6div 2
• 6div-2
• -6div 2
• -6div-2
• 1div 1
• 11div 4

我缺少什么来对这个新代码进行彻底的单元测试？

Answer 1

在不了解实现的情况下，可以选择可能暴露典型错误源的模式，例如未能在位或字之间传播进位，或舍入中的角大小写。典型模式：

1. 二的幂：2ⁱ
2. 二的幂减一：2ⁱ-1
3. 二的幂加一：2ⁱ+1
4. 二的任意二次幂之和：2ⁱ+2^j
5. 二的任意二次幂之差：2ⁱ-2^j
6. 模式1中任何一个的补码。至5
7. 模式1中任一模式的二者补码。至5

显然，模式类之间存在重叠，这允许以"烟雾"测试的形式使用少量测试向量进行快速检查，也允许使用大量测试向量进行深入检查。由于除法有两个参数，所以除数和被除数的模式也应该从不同的模式类创建。

根据我的经验，这些简单的模式在消除包括整数除法在内的各种算术运算中的错误方面非常有效。这种测试模式的应用在这个经典的注释中进行了讨论：

N。L.Schryer，"计算机浮点运算单元的测试"，《计算科学技术报告》第89期，美国电话电报公司；T贝尔实验室，1981年2月4日(在线(

在我的x64机器上，使用以下C代码测试使用上述所有模式类的简单64位逐位除法实现只需要一分钟多：

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <limits.h>
int64_t v[32768]; /* FIXME: size appropriately */
#define ADDcc(a,b,cy,t0,t1) 
(t0=(b), t1=(a), t0=t0+t1, cy=t0<t1, t0=t0)
#define ADDC(a,b,cy,t0,t1) 
(t0=(b)+cy, t1=(a), t0+t1)
/* bit-wise non-restoring two's complement division */
void my_div_core (int64_t dividend, int64_t divisor, int64_t *quot, int64_t *rem)
{
const int operand_bits = (int) (sizeof (int64_t) * CHAR_BIT);
uint64_t d = (uint64_t)divisor;
uint64_t nd = 0 - d; /* -divisor */
uint64_t r, q = 0; /* remainder, quotient */
uint64_t dd = d;  /* divisor */
uint64_t cy, t0, t1;
int i;
q = dividend;
r = (dividend < 0) ? (~0) : 0;  // sign-extend
for (i = operand_bits - 1; i >= 0; i--) {
if ((int64_t)(r ^ dd) < 0) {
/* shift 128-bit quantity q:r left by 1 bit */
q = ADDcc (q, q, cy, t0, t1);
r = ADDC  (r, r, cy, t0, t1);
r += dd;
q += 0; /* record quotient bit -1 (as 0) */
} else {
/* shift 128-bit quantity q:r left by 1 bit */
q = ADDcc (q, q, cy, t0, t1);
r = ADDC  (r, r, cy, t0, t1);
r -= dd;
q += 1; /* record quotient bit +1 (as 1) */
}
}
/* convert quotient from digit set {-1,1} to plain two's complement */
q = (q << 1) + 1;
/* fix up cases where we worked past a partial remainder of zero */
if (r == d) { /* remainder equal to divisor */
q = q + 1;
r = 0;
} else if (r == nd) { /* remainder equal to -divisor */
q = q - 1;
r = 0;
}
/* for truncating division, remainder must have same sign as dividend */
if (r && ((int64_t)(dividend ^ r) < 0)) {
if ((int64_t)q < 0) {
q = q + 1;
r = r - d;
} else {
q = q - 1;
r = r + d;
}
}
*quot = (int64_t)q;
*rem  = (int64_t)r;
}
int64_t my_div (int64_t dividend, int64_t divisor)
{
int64_t quot, rem;
my_div_core (dividend, divisor, &quot, &rem);
return quot;
}
int main (void)
{
int64_t dividend, divisor, quot, ref;
int i, j, patterns, idx = 0, nbrBits = sizeof (uint64_t) * CHAR_BIT;
/* pattern class 1: 2**i */
for (i = 0; i < nbrBits; i++) {
v [idx] = (int64_t)((uint64_t)1 << i);
idx++;
}
/* pattern class 2: 2**i-1 */
for (i = 0; i < nbrBits; i++) {
v [idx] = (int64_t)(((uint64_t)1 << i) - 1);
idx++;
}
/* pattern class 3: 2**i+1 */
for (i = 0; i < nbrBits; i++) {
v [idx] = (int64_t)(((uint64_t)1 << i) + 1);
idx++;
}
/* pattern class 4: 2**i + 2**j */
for (i = 0; i < nbrBits; i++) {
for (j = 0; j < nbrBits; j++) {
v [idx] = (int64_t)(((uint64_t)1 << i) + ((uint64_t)1 << j));
idx++;
}
}
/* pattern class 5: 2**i - 2**j */
for (i = 0; i < nbrBits; i++) {
for (j = 0; j < nbrBits; j++) {
v [idx] = (int64_t)(((uint64_t)1 << i) - ((uint64_t)1 << j));
idx++;
}
}
patterns = idx;
/* pattern class 6: one's complement of pattern classes 1 through 5 */
for (i = 0; i < patterns; i++) {
v [idx] = ~v [i];
idx++;
}
/* pattern class 7: two's complement of pattern classes 1 through 5 */
for (i = 0; i < patterns; i++) {
v [idx] = -v [i];
idx++;
}
patterns = idx;
for (i = 0; i < patterns; i++) {
for (j = 0; j < patterns; j++) {
dividend = v [i];
divisor  = v [j];
/* exclude cases with undefined results: division by zero, overflow*/
if (!((divisor == 0LL) || 
((dividend == (-0x7fffffffffffffffLL - 1LL)) && (divisor == -1LL)))) {
quot = my_div (dividend, divisor);
ref = dividend / divisor;
if (quot != ref) {
printf ("error @ (%016llx, %016llx): quot = %016llx  ref=%016llxn", 
dividend, divisor, quot, ref);
return EXIT_FAILURE;
}
}
}
}
printf ("64-bit division: test passedn");
return EXIT_SUCCESS;
}

除了上述模式测试之外，您还希望添加目标伪随机测试向量，特别是关注以下场景：

1. 小除数
2. 小商
3. 小型剩余物

生成类2的测试向量的合适方法。和3。是通过从随机除数中构造乘法被除数(选择一个小的随机乘法器(和乘法加加法被除数。

一般来说，根据系统的速度和参考实现的速度，现代计算机足够快，可以允许2³²和2

48使用大量的随机测试向量需要高质量的PRNG(伪随机数生成器(。George Marsaglia教授的KISS64将是一个最低标准：

/*
From: geo <[e-mail]>
Newsgroups: sci.math,comp.lang.c,comp.lang.fortran
Subject: 64-bit KISS RNGs
Date: Sat, 28 Feb 2009 04:30:48 -0800 (PST)
This 64-bit KISS RNG has three components, each nearly
good enough to serve alone.    The components are:
Multiply-With-Carry (MWC), period (2^121+2^63-1)
Xorshift (XSH), period 2^64-1
Congruential (CNG), period 2^64
*/
static uint64_t kiss64_x = 1234567890987654321ULL;
static uint64_t kiss64_c = 123456123456123456ULL;
static uint64_t kiss64_y = 362436362436362436ULL;
static uint64_t kiss64_z = 1066149217761810ULL;
static uint64_t kiss64_t;
#define MWC64  (kiss64_t = (kiss64_x << 58) + kiss64_c, 
kiss64_c = (kiss64_x >> 6), kiss64_x += kiss64_t, 
kiss64_c += (kiss64_x < kiss64_t), kiss64_x)
#define XSH64  (kiss64_y ^= (kiss64_y << 13), kiss64_y ^= (kiss64_y >> 17), 
kiss64_y ^= (kiss64_y << 43))
#define CNG64  (kiss64_z = 6906969069ULL * kiss64_z + 1234567ULL)
#define KISS64 (MWC64 + XSH64 + CNG64)