C语言 optimising btwoc()

Question

根据OpenID Authentication 2.0, section 4.2，

任意精度整数必须编码为大端位有符号二进制补码字符串。从今以后,"btwoc"是一个函数，它接受任意精度整数并返回其最短的大端二进制补码表示形式。所有用于Diffie-Hellman密钥交换的整数都是正数。这意味着这两个补码表示的最左边的位必须为零。如果不是，实现必须在字符串的前面添加一个零字节。

非规范化的例子:

Base 10 number | btwoc string representation
---------------+----------------------------
0              | "x00"
127            | "x7F"
128            | "x00x80"
255            | "x00xFF"
32768          | "x00x80x00"

我试着用C写我自己的btwoc实现，这就是我所拥有的:

typedef struct {
    uint8_t *data;
    uintmax_t length;
} oid_data;
oid_data *oid_btwoc_r(uintmax_t value, oid_data *ret) {
    unsigned    fnz = sizeof(uintmax_t) + 1,
                i = sizeof(uintmax_t) * 8;
    while (--fnz && (!(value >> (i -= 8) & 0xFF)));
    /*
        If `value' is non-zero, `fnz' now contains the index of the first
        non-zero byte in `value', where 1 refers to the least-significant byte.
        `fnz' will therefore be in the range [1 .. sizeof(uintmax_t)]. If
        `value' is zero, then `fnz' is zero.
    */
    if (!value) {
        /* The value is zero */
        ret->length = 1;
        ret->data[0] = 0;
    } else if (value >> ((fnz - 1) * 8 + 7)) {
        /* The most significant bit of the first non-zero byte is 1 */
        ret->length = fnz + 1;
        ret->data[0] = 0;
        for (i = 1; i <= fnz; i++)
            ret->data[1 + fnz - i] =
                value >> ((i - 1) * 8);
    } else {
        /* The most significant bit of the first non-zero byte is 0 */
        ret->length = fnz;
        for (i = 1; i <= fnz; i++)
            ret->data[fnz - i] =
                value >> ((i - 1) * 8);
    }
    return ret;
}

ret->data应该指向至少sizeof(uintmax_t) + 1字节的有效内存。

它工作得很好，我还没有在实现中发现任何错误，但是它可以优化吗?

Answer 1

如果您将零作为一个特例，您肯定应该在while循环之前处理它。(个人bête noire:我不喜欢(!value)的(value == 0)。)

---

我还没有尝试计时这个(尚未)，但这段代码产生的答案与您的相同(至少在我测试的值上;(见下文)，对我来说看起来更简单，尤其是因为它没有将代码翻倍来处理最高位设置在最高位的情况:

void oid_btwoc_r2(uintmax_t value, oid_data *ret)
{
    if (value == 0)
    {
        ret->data[0] = 0;
        ret->length  = 1;
        return;
    }
    uintmax_t v0 = value;
    uintmax_t v1 = v0;
    unsigned  n  = 0;
    while (v0 != 0)
    {
        n++;
        v1 = v0;
        v0 >>= 8;
    }
    //printf("Value: 0x%" PRIXMAX ", v1 = 0x%" PRIXMAX "n", value, v1);
    assert(v1 < 0x100 && v1 != 0);
    if (v1 > 0x7F)
        n++;
    //printf("N = %un", n);
    for (unsigned i = n; i != 0; i--)
    {
        ret->data[i-1] = (value & 0xFF);
        value >>= 8;
    }
    ret->length = n;
}

我用来测试你的版本的代码是:

#include <assert.h>
#include <inttypes.h>
#include <stdio.h>
#include <string.h>
#define DIM(x)  (sizeof(x) / sizeof(*(x)))
static void dump_oid_data(FILE *fp, const char *tag, const oid_data *data)
{
    fprintf(fp, "%s: length %" PRIuMAX ":", tag, data->length);
    for (uintmax_t i = 0; i < data->length; i++)
        fprintf(fp, " 0x%02X", data->data[i]);
    fputc('n', fp);
}
int main(void)
{
    uintmax_t list[] = { 0, 0x7F, 0x80, 0xFF, 0x100, 0x7FFF, 0x8000, 0xFFFF,
                         0x10000, 0x7FFFFF, 0x800000, 0xFFFFFF };
    for (size_t i = 0; i < DIM(list); i++)
    {
        uint8_t b1[sizeof(uintmax_t) + 1];
        uint8_t b2[sizeof(uintmax_t) + 1];
        oid_data v1 = { b1, sizeof(b1) };
        oid_data v2 = { b2, sizeof(b2) };
        oid_btwoc_r(list[i], &v1);
        oid_btwoc_r2(list[i], &v2);
        printf("Value: 0x%" PRIXMAX ": ", list[i]);
        if (v1.length != v2.length)
            printf("Lengths differ (%" PRIuMAX " vs %" PRIuMAX ")n", v1.length, v2.length);
        else if (memcmp(v1.data, v2.data, v1.length) != 0)
        {
            printf("Data differs!n");
            dump_oid_data(stdout, "oid_btwoc_r1()", &v1);
            dump_oid_data(stdout, "oid_btwoc_r2()", &v2);
        }
        else
        {
            printf("Values are the samen");
            dump_oid_data(stdout, "oid_btwoc_rN()", &v2);
        }
    }
    return(0);
}

是的;早期版本的代码需要转储函数来查看哪里出了问题!

我将原来的oid_btwoc_r()改编为返回void(没有最终的return)的函数，并将其重命名为oid_btwoc_r1()。然后我运行了一个计时测试(在运行MacOS X Lion 10.7.1的Mac Mini上)，并得到了计时结果:

oid_btwoc_r1(): 4.925386
oid_btwoc_r2(): 4.022604
oid_btwoc_r1(): 4.930649
oid_btwoc_r2(): 4.004344
oid_btwoc_r1(): 4.927602
oid_btwoc_r2(): 4.005756
oid_btwoc_r1(): 4.923356
oid_btwoc_r2(): 4.007910
oid_btwoc_r1(): 4.984037
oid_btwoc_r2(): 4.202986
oid_btwoc_r1(): 5.015747
oid_btwoc_r2(): 4.067265
oid_btwoc_r1(): 4.982333
oid_btwoc_r2(): 4.019807
oid_btwoc_r1(): 4.957866
oid_btwoc_r2(): 4.074712
oid_btwoc_r1(): 4.993991
oid_btwoc_r2(): 4.042422
oid_btwoc_r1(): 4.970930
oid_btwoc_r2(): 4.077203

因此，oid_btwoc_r2()函数似乎比原始函数快20%左右——至少在测试的数据上是这样。更大的数字改变了平衡，有利于oid_btwoc_r()， ' oid_btwoc_r1()然后大约快20%:

oid_btwoc_r1(): 3.671201
oid_btwoc_r2(): 4.605171
oid_btwoc_r1(): 3.669026
oid_btwoc_r2(): 4.575745
oid_btwoc_r1(): 3.673729
oid_btwoc_r2(): 4.659433
oid_btwoc_r1(): 3.684662
oid_btwoc_r2(): 4.671654
oid_btwoc_r1(): 3.730757
oid_btwoc_r2(): 4.645485
oid_btwoc_r1(): 3.764600
oid_btwoc_r2(): 4.673244
oid_btwoc_r1(): 3.669582
oid_btwoc_r2(): 4.610177
oid_btwoc_r1(): 3.664248
oid_btwoc_r2(): 4.813711
oid_btwoc_r1(): 3.675927
oid_btwoc_r2(): 4.630148
oid_btwoc_r1(): 3.681798
oid_btwoc_r2(): 4.614129

由于在这种情况下，大数字可能比小数字更有可能出现，因此oid_btwoc_r1()(或原始oid_btwoc_r())可以说是更好的选择。

接下来是测试代码。未注释的for循环是"大数"版本，显示oid_btwoc_r1()比oid_btwoc_r2()工作得快;注释掉的for循环是"小数字"版本，显示oid_btwoc_r2()比oid_btowc_r1()工作得快。

static void test_converter(const char *tag, void (*function)(uintmax_t, oid_data *))
{
    Clock clk;
    clk_init(&clk);
    clk_start(&clk);
    for (uintmax_t i = 0x100000000; i < 0x1000000000000000; i += 0x170000000)
    //for (uintmax_t i = 0; i < 0x100000000; i += 17)
    {
        uint8_t b1[sizeof(uintmax_t) + 1];
        oid_data v1 = { b1, sizeof(b1) };
        (*function)(i, &v1);
    }
    clk_stop(&clk);
    char buffer[32];
    printf("%s: %sn", tag, clk_elapsed_us(&clk, buffer, sizeof(buffer)));
}
int main(void)
{
    for (int i = 0; i < 10; i++)
    {
        test_converter("oid_btwoc_r1()", oid_btwoc_r1);
        test_converter("oid_btwoc_r2()", oid_btwoc_r2);
    }
    return(0);
}