оптимизация btwoc ()

Question

В соответствии с OpenID Authentication 2.0 , раздел 4.2,

Произвольные целые числа точности ДОЛЖНЫ быть закодированы как двоичные строки, дополняющие двоичные числа со знаком с прямым порядком байтов.Отныне «btwoc» - это функция, которая принимает целое число произвольной точности и возвращает представление дополнения к его кратчайшему значению с обратным порядком двоичных чисел.Все целые числа, которые используются с обменом ключами Диффи-Хеллмана, положительны.Это означает, что самый левый бит представления дополнения двух ДОЛЖЕН быть нулевым.Если это не так, реализации ДОЛЖНЫ добавить нулевой байт в начале строки.

Ненормативный пример:

Base 10 number | btwoc string representation
---------------+----------------------------
0              | "\x00"
127            | "\x7F"
128            | "\x00\x80"
255            | "\x00\xFF"
32768          | "\x00\x80\x00"

Я попытался написать свою собственную реализацию btwoc в C, и это то, что у меня есть:

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 = %u\n", 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 same\n");
            dump_oid_data(stdout, "oid_btwoc_rN()", &v2);
        }
    }
    return(0);
}

Да; ранняя версия кода нуждалась в функции dump, чтобы увидеть, что происходит не так!

Сроки

Я адаптировал исходный oid_btwoc_r() к функции, возвращающей void (без окончательного return), и переименовал ее в oid_btwoc_r1(). Затем я запустил тест синхронизации (на Mac Mini с MacOS X Lion 10.7.1) и получил результаты синхронизации:

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: %s\n", 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);
}