Оптимальная функция Base-10 только itoa()?

Question

За 20 с лишним лет программирования на C я использовал базу, отличную от 10, один раз, поэтому, когда я обнаружил, что _itoa() моего надежного MSVC отсутствует в другой среде, я решил написать ту, которая работает только с базой 10, и поместил целевой буфер. аргумент, указывающий на хранилище, возвращаемое функцией слева, а не справа, как и все строковые функции в стандартной библиотеке C. Я считаю, что этот код также потокобезопасен.

Есть ли более быстрый способ сделать это?

Я также собирался спросить о корректности, но я полагаю, что включенный тестовый код доказывает, что он работает, даже для конкретного случая LONG_MIN, который равен (-1 * LONG_MAX) -1, что вызывало сбой в коде, пока я не изменил тактику, отметил знак, а затем скопировал подписанный int в неподписанный int. Затем я выполнил всю основную работу в функции в неподписанных целочисленных значениях, которые также успешно выполнялись в 75% случаев.

char * _i32toa(char *const rtn, int32_t i)    {
    if (NULL == rtn) return NULL;

    // declare local buffer, and write to it back-to-front
    char buff[12];
    uint32_t  ut, ui;
    char minus_sign=0;
    char *p = buff + sizeof(buff)-1;
    *p-- = 0;    // nul-terminate buffer

    // deal with negative numbers while using an unsigned integer
    if (i < 0)    {
        minus_sign = '-';
        ui = (uint32_t)((int)-1 * (int)i);
    }    else    {
        ui = i;
    }

    // core code here...
    while (ui > 9) {
        ut = ui;
        ui /= 10;
        *p-- = (ut - (ui * 10)) + '0';
    }
    *p = ui + '0';

    if ('-' == minus_sign) *--p = minus_sign;

    // knowing how much storage we needed, copy chars from buff to rtn...
    memcpy(rtn, p, sizeof(buff)-(p - buff));

    return rtn;
}

// ------------------------------------------------------------------------------------------------
#define LOOP_KNT (SHRT_MAX * 1024)
// ------------------------------------------------------------------------------------------------
int main(void)    {
    time_t start = clock();

    int32_t t = 123456, i;
    char *buff = (char *)malloc(256);

    for (i = (SHRT_MIN *1024); i < LOOP_KNT; i++)    {
        _i32toa(buff, i);
    }
    printf("\nElapsed time was %f milliseconds", (double)clock() - (double)(start));

    start = clock();
    for (i = (SHRT_MIN * 1024); i < LOOP_KNT; i++)    {
        _itoa(i, buff, 10);
    }
    printf("\nElapsed time was %f milliseconds", (double)clock() - (double)(start));

    start = clock();
    for (i = (SHRT_MIN * 1024); i < LOOP_KNT; i++)    {
        ___itoa(i, buff, 10);
    }
    printf("\nElapsed time was %f milliseconds", (double)clock() - (double)(start));

    printf("\nString from integer %i is %s\n", t, _i32toa(buff, t));
    printf("\nString from integer %i is %s\n", -0, _i32toa(buff, -0));
    printf("\nString from integer %i is %s\n", -1, _i32toa(buff, -1));
    printf("\nString from integer %i is %s\n", LONG_MIN, _i32toa(buff, LONG_MIN));

    start = clock();
    for (int i = LONG_MIN; i < LONG_MAX; i++) {
        if (i != atoi(_i32toa(buff, (int32_t)i))) {
            printf("\nError for %i", i);
        }
        if (!i) printf("\nAt zero");
    }
    printf("\nElapsed time was %f milliseconds", (double)clock() - (double)(start));

    getchar();
    return 0;
}

Производительность в 2-4 раза выше, чем у _itoa(), не являющейся частью стандарта C в Visual Studio 2013, и в 10-15 раз выше, чем у sprintf().

Подход несколько нов и зависит от знания требуемого размера буфера для завершенной строки - проблема, которую функция, выделяющая собственный строковый буфер, решает buff[], делая его одновременно поточно-ориентированным.

Знание того, где находится конец буфера, позволяет записывать символы строки сзади вперед, решая проблему обратного порядка. Вызывающая функция не должна каким-либо образом подготавливать *rtn, поскольку рабочая строка, которая возвращает memcpy() в *ptr, уже завершена нулем.

TVMIA за ваш отзыв. Отсутствие хорошей функции _atoi() является достаточно постоянной проблемой, которая заслуживает хорошего решения. Давайте сделаем один.

PS: На моем i7 Hazwell box, работающем под управлением MSVS C++ 64-bit с полной оптимизацией, полный цикл от LONG_MIN до LONG_MAX в среднем составляет 116 тактов на конверсию для туда-обратно и только 28 тактов для _itoa(). Это более 725 мегабайт в секунду строки - по сравнению с кодом Бена Фойгта. Я думаю, что выиграл Бен!

Answer 1

Вы можете устранить memcpy записав прямо в область памяти звонящего.
Вы должны сделать так, чтобы вызывающий передавал размер буфера.

Другим узким местом является разделение, но я не вижу, как это обойти.

Редактировать 1: правильная инициализация указателя буфера

char * _i32toa(char *const rtn, unsigned int buff_size, int32_t i)  
{
    if (NULL == rtn) return NULL;

    uint32_t  ut, ui;
    char minus_sign=0;
    char *p = rtn + buff_size - 1;
    // As before, without memcpy.
    return rtn;
}

Answer 2

Избавьтесь от массива auto char и сделайте так, чтобы они передавали размер, чтобы вы могли проверить переполнение.

#define I32TOA( buff, val ) _i32toa( (buff), sizeof(buff), (val) )

char * _i32toa(char *const rtn, size_t size, int32_t i)    {
    if (NULL == rtn) return NULL;

    uint32_t  ut, ui;
    char minus_sign=0;
    char *p = rtn + size-1;
    *p-- = 0;    // nul-terminate buffer
    assert( p >= rtn );

    if (i < 0)    {
        minus_sign = '-';
        ui = (uint32_t)((int)-1 * (int)i);
    }    else    {
        ui = i;
    }

    while (ui > 9) {
        ut = ui;
        ui /= 10;
        *p-- = (ut - (ui * 10)) + 48;
        assert( p >= rtn );
    }
    *p = ui + 48;

    if ('-' == minus_sign) {
        *--p = minus_sign;
        assert( p >= rtn );
    }

    return p;
}