Приветствую!

Код лежит тут

Думаю о разработке своей vsnprintf функции думал каждый кто увлекается osdev и есть много кода написанного на эту тему. Так же есть масса гайдов и туториалов, но не один из известных мне не заканчивается vsnprintf функцией проходящей тесты от gcc. Перед вами первый из них!

В первую очередь нужно сказать что ориентироваться будем на этот документ, но реализации расширений gnu в духе $, m$ не будет за исключением всего двух: вывод строки (null) вместо nullptr для спецификатора %s и строки (nil) вместо nullptr для спецификатора %p. Я уже не помню в какой версии glibc я видел (Nil) но мне это очень понравилось. Так же форматирование %p будет реализовано как в glibc.

Сначала посмотрим на это графически:

Теперь текстом:

Список поддерживаемых нами спецификаторов следующий: d, i, u,x, X, o, c, s, p, n

Список поддерживаемых нами модификаторов размера следующий: h, hh, l, ll, z, t,

Общий вид строки форматирования следующий:

%[flags][field_width][.precision][size modifier]conversion specifier

Начнем с флагов:

enum FormatFlags: int
{
    F_NONE = 0,
    F_MINUS = 1 << 0,
    F_PLUS = 1 << 1,
    F_SPACE = 1 << 2,
    F_ALT = 1 << 3,
    F_ZERO = 1 << 4,
    F_HUGE = 1 << 5,
};

Флаг 0 игнорируется, если задан флаг - (минус)или указана точность.

В случае если мы передаем nullptr для %p у нас выводится строка (Nil) которая форматируется как %s.

Что касается ширины поля, важно понимать: что ширина поля никогда не обрезает вывод она может только добавлять пробелы или нули если установлен флаг '0' и соблюдены все остальные условия.

Точность указывает лишь минимальное количество символов которые нужно вывести.

Для чисел если аргумент длиннее, то он выводится целиком, если нет, то недостающее количество символов будет заполнено нулями слева.

Для строк точность означает максимальное количество символов которое будет выведено, т.е. строка может быть обрезана если она длинее.

Модификаторы размера:

enum class LengthSpec: int
{
    null,
    h,
    hh,
    l,
    ll,
    z,
    t
};

Сразу же обращаю ваше внимание что если вы считываете из стека значение не того типа, то все сломается.

Спецификаторы преобразования:

enum class LengthSpec: int
{
    null,
    h,
    hh,
    l,
    ll,
    z,
    t
};

// ...

static long long read_signed_number(const FormatSpec &formatSpec, va_list_wrapper &w)
{
    long long value = 0;

    switch (formatSpec.lengthSpec) {
        case LengthSpec::l:
            value = va_arg(w.ap, long);
            break;

        case LengthSpec::z:
            value = static_cast<int64_t> (va_arg(w.ap, int64_t));
            break;

        case LengthSpec::hh: {
          // необходимо обрезать значение до char.
          // буквально, как требует модификатор!
          // Иначе будет работать некорректно!
            char v = va_arg(w.ap, int);
            value = v;
        }
            break;

        case LengthSpec::h:
            value = va_arg(w.ap, int);
            break;

        case LengthSpec::t:
            value = va_arg(w.ap, ptrdiff_t);
            break;

        case LengthSpec::ll:
        default:
            value = va_arg(w.ap, long long);
            break;
    }

    return value;
}

static unsigned long long read_unsigned_number(const FormatSpec &formatSpec, va_list_wrapper &w)
{
    unsigned long long value = 0;

    switch (formatSpec.lengthSpec) {
        case LengthSpec::l:
            value = va_arg(w.ap, unsigned long);
            break;

        case LengthSpec::z:
            value = static_cast<size_t> (va_arg(w.ap, size_t));
            break;

        case LengthSpec::hh: {          
          // необходимо обрезать значение до unsigned char.
          // буквально, как требует модификатор!
          // Иначе будет работать некорректно!
            unsigned char v = va_arg(w.ap, unsigned int);
            value = v;
        }
            break;

        case LengthSpec::h:
            value = va_arg(w.ap, unsigned int);
            break;

        case LengthSpec::ll:
        default:
            value = va_arg(w.ap, unsigned long long);
            break;
    }

    return value;
}

В конечном итоге мы преобразуем любое число в unsigned long long. Это упрощает нам работу, в последующем мы можем не думать про знак.

Что бы работать с этими сущностями мы введем структуру FormatSpec вида

struct FormatSpec
{
    int flags{FormatFlags::F_NONE};
    LengthSpec lengthSpec{LengthSpec::null};
    int total{0};
    int field_width{-1};
    int precision{-1};
    bool negative{false};
    int radix{10};

  // не обходимо вызывать на каждой итерации так как для каждого спефикиатора
  // формата это параметры свои, напрмер % 05hhi %+-0.5llu %-+ 06.3zd
    inline void reset() noexcept
    {
        flags = FormatFlags::F_NONE;
        lengthSpec = LengthSpec::null;
        field_width = -1;
        precision = -1;
        negative = false;
        radix = 10;
    }
};

Далее вот набросок общего алгоритма действий:

Если проще, то обработка спецификатора является конвейером следующего вида:

1/ Парсинг флагов, ширины поля и точности

2/ Парсинг модификатора размера

3/ Получение строкового представления аргумента

4/ Форматирование в соответствии с шириной поля и точностью

5/ Собственно вывод

Разберем каждый шаг более подробно:

1/ Шаг 1: парсинг флагов, ширины поля и точности

static const char *parse_flags_fw_precision(const char *fmt, FormatSpec &formatSpec,
                                            va_list_wrapper &w)
{
  // Забираем флаги пока они есть
  // Цикл нужен например для таких случаев: % #12x
  // пока встречаем флаги continue всегда возвращает нас в начало цикла
  // забрав флаг
    do {
        switch (*fmt) {
            case '#':
                formatSpec.flags |= FormatFlags::F_ALT;
                continue;

            case ' ':
                formatSpec.flags |= FormatFlags::F_SPACE;
                continue;

            case '0':
                formatSpec.flags |= FormatFlags::F_ZERO;
                continue;

            case '-':
                formatSpec.flags |= FormatFlags::F_MINUS;
                continue;

            case '+':
                formatSpec.flags |= FormatFlags::F_PLUS;
                continue;

            default: // тут выходим из цикла
                break;
        }

        break;
    }
    while (*fmt++);

  // Далее может идти символ * что означает что ширина поля передается аргументом
  // например sprintf("%*d", 12);
    if (*fmt == '*') {
        ++fmt;
        formatSpec.field_width = va_arg(w.ap, int);
    }
    else if (isdigit(*fmt)) {
        fmt = parse_number(fmt, formatSpec.field_width);
    } // тут обрабатываем случай если ширина поля передается числом сразу за %
  // например %12d
    else if (*fmt == '-') {
// отрицательная ширина поля обрабатывается как флаг - и положительная ширина поля
// TODO: проверить, возможно мы никогда сюда не придем из за парсера флагов
        formatSpec.flags |= FormatFlags::F_MINUS;
        
        ++fmt;

        if (isdigit(*++fmt)) {
            fmt = parse_number(fmt, formatSpec.field_width);
        }
    }
// за точкой следует точность, например %.12d
    if (*fmt == '.') {
// если за точкой ничего нет, то мы считаем что точность равна нулю
        formatSpec.precision = 0;
// не забываем что если указана точность, то флаг '0' игнорируется
        formatSpec.flags &= ~FormatFlags::F_ZERO;
        ++fmt;
// тоже самое: если точность равна символу '*' то она передается аргументом функции
        if (*fmt == '*') {
            ++fmt;
            formatSpec.precision = va_arg(w.ap, int);
        }
        else if (*fmt == '-') {
// если точность отрицательная, то она полностью игнорируется
            while (isdigit(*++fmt)) {}
            formatSpec.precision = -1;
        }
        else if (isdigit(*fmt)) {
            fmt = parse_number(fmt, formatSpec.precision);
        }
    }

    return fmt;
}

Шаг 2

Далее забираем модификатор размера. Эта функция простая, думаю тут нечего комментировать

static const char *parse_size_modifier(const char *fmt, FormatSpec &formatSpec)
{
    switch (*fmt) {
        case 'h':
            formatSpec.lengthSpec = LengthSpec::h;

            if (*(fmt + 1) == 'h') {
                formatSpec.lengthSpec = LengthSpec::hh;
                ++fmt;
            }
            ++fmt;
            break;

        case 'l':
            formatSpec.lengthSpec = LengthSpec::l;

            if (*(fmt + 1) == 'l') {
                formatSpec.lengthSpec = LengthSpec::ll;
                ++fmt;
            }
            ++fmt;
            break;

        case 'z':
            formatSpec.lengthSpec = LengthSpec::z;
            ++fmt;
            break;

        case 't':
            formatSpec.lengthSpec = LengthSpec::t;
            ++fmt;
            break;
    }

    return fmt;
}

Далее начинаются уже более интересные вещи. Разберем парсинг числа, работа с модификаторами %c. %s и %n простая и будет рассмотрена позже.

static char *format_number(char *buf, unsigned long long number, FormatSpec &formatSpec,
                           size_t size)
{
  // Если число было отрицательное, сохраняем знак
    char sign = formatSpec.negative ? '-' : 0;
    int number_len = 0;
    int offset = 0;
    char number_str[MAX_NUMBER_LEN];

    if (!formatSpec.negative) {
// обрабатываем флаги, для положительного числа флаг '+' требует вывода знака
        if ((formatSpec.flags & FormatFlags::F_PLUS)) {
            sign = '+';
        } // а флаг ' ' требует вывести пробел вместо знака
        else if ((formatSpec.flags & FormatFlags::F_SPACE)) {
            sign = ' ';
        }
    }

    // emulate zero flag via precision
// тут я понял что допустил архитектурную ошибку, но чинить было лениво
// так что если флаг '0' установлен, то от нас требуется заполнить все нулями
// по ширине поля, по сути эффект эквивалентен результату обработки точности
// т.е. дополнительные нули перед числом, а значит это можно имитировать через точность
    if (formatSpec.flags & FormatFlags::F_ZERO) {
        if (formatSpec.precision < formatSpec.field_width) {
// только в том случае если точность меньше ширины поля, иначе точность побеждает
            formatSpec.precision = formatSpec.field_width;
            formatSpec.field_width = 0;
        }

        if (sign > 0) {
            --formatSpec.precision;
        }
    }
// если у нас есть знак, то нужно передать наш массив таким образом что бы он не был
// перетерт строковым представлением числа
    offset = sign == 0 ? offset : ++offset;
    number_str[0] = sign;
    number_len = number_to_string(&number_str[offset],
                                  number,
                                  formatSpec,
                                  MAX_NUMBER_LEN);
  // тут у нас уже обработанное число в виде строки, нам нужно вывести его
  // в выходной буфер с учетом ширины поля, это сделает для нас функция
  // put_with_field_width
    number_len += offset;
    return put_with_field_width(buf, number_str, number_len, formatSpec, size);
}

Шаг 3

number_to_string() делает три вещи:

1. Получает цифры числа в обратном порядке.
2. Добавляет нули, если нужна точность.
3. Добавляет альтернативный префикс 0 / 0x / 0X.
4. Переворачивает результат в выходной буфер.

int
number_to_string(char *buf, unsigned long long number, const FormatSpec &formatSpec,
                 int size)
{
    const char *digits = (formatSpec.flags & FormatFlags::F_HUGE) > 0 ? "0123456789ABCDEF" : "0123456789abcdef";
    char num_str[MAX_NUMBER_LEN];
    int number_len = 0;
    int p = formatSpec.precision;
    int zero_count = 0;
    auto nr = number;
// Для числа 0 если точность установлена в 0 ничего не выводим
    if (formatSpec.precision == 0 && number == 0) {
        return 0;
    }
// обычное преобразование числа в строку
    if (nr != 0) {
        while (nr != 0) {
            unsigned long long n = nr % formatSpec.radix;
            nr /= formatSpec.radix;
            num_str[number_len++] = digits[n];
        }
    }
    else {
        num_str[number_len++] = '0';
    }
// Точность для целых чисел задаёт минимальное количество цифр.
// Поэтому из precision вычитаем уже полученную длину числа:
// остаток p — это количество ведущих нулей.
    p -= number_len;

    if (formatSpec.flags & FormatFlags::F_ZERO) {
      //учитываем длину специальных символов если установлен соответствующий флаг
      // что бы вывести меньше нулей для точности
        if (formatSpec.flags & FormatFlags::F_ALT) {
            if (number > 0) {
                switch (formatSpec.radix) {
                    case 8:
                        --p;
                        break;

                    case 16:
                        p -= 2;
                        break;
                }
            }
        }
    }
// считаем сколько нулей нужно вывести для соответствия точности
    zero_count = min(p, size);
// и заполняем все нулями до соответствия ей
    while (zero_count > 0) {
        num_str[number_len++] = '0';
        --zero_count;
    }
// добавляем 0 к восьмеричному целому или 0x/0X к шестнадцатиричному
    if (formatSpec.flags & FormatFlags::F_ALT) {
        if (number > 0) {
            switch (formatSpec.radix) {
                case 8:
                    num_str[number_len++] = '0';
                    break;

                case 16:
                    num_str[number_len++] = (formatSpec.flags & FormatFlags::F_HUGE) > 0 ? 'X' : 'x';
                    num_str[number_len++] = '0';
                    break;
            }
        }
    }

    number_len = min(number_len, size);
// собственно выводим число
    for (size_t i = 0; i < number_len; ++i) {
        *buf++ = num_str[number_len - i - 1];
    }

    return number_len;
}

Теперь для полноты картины нужно разобраться с функцией put_with_field_width, она достаточно простая

static char *
put_with_field_width(char *buf, const char *value, int len, FormatSpec &formatSpec,
                     size_t size)
{
// нам нужно понимать как много символов нам нужно вывести
// ширина поля должна учитывать длину аргумента
    int padding_len = formatSpec.field_width - len >= 0 ? formatSpec.field_width - len : 0;
//функция различает фактическую запись в буфер и гипотетическую длину результата. 
// поэтому  все операции записи ограничиваются size, но счётчики и 
// указатель продвигаются так, как будто бы места в буфере достаточно
// я сам был удивлен, gpt мне сказал что так работает glibc и действительно
// glibc возвращает не written, а formatSpec.total, т.е. то, что мы записали бы
// если бы хватило места.
// почему так я не знаю, но у меня тоже реализовано именно так, это один из моментов
// который я скопировал с поведения glibc
    formatSpec.total += padding_len;
// если флаг '-' не установлен то дополняем пробелами слева, например
    if (!(formatSpec.flags & FormatFlags::F_MINUS)) {
// sprintf("'%5d'",12) даст результат '   12'
// как видно аргумент выравнивается по правому краю
        memset(buf, ' ', min(padding_len, size));
        buf += padding_len;
        size = size > padding_len ? size - padding_len : 0;
        padding_len = 0;
    }

    buf = static_cast<char *>(mempcpy(buf, value, min(len, size)));
    formatSpec.total += len;
// если флаг '-' установлен то дополняем пробелами справа
    if (formatSpec.flags & FormatFlags::F_MINUS) {
// sprintf("'%-5d'",12) даст результат '12   '
// как видно аргумент выравнивается по левому краю
        memset(buf, ' ', min(padding_len, size));
        buf += padding_len;
        padding_len = 0;
    }

    return buf;
}

Получается что шаги 3, 4 и 5 уже выполнены тут же

Теперь мы знаем как работает format_number. По сути нам остается только выставить флаги в корректное состояние и функция все сделает сама.

vsnprintf по сути просто считывает флаги, ширину поля и точность, аргумент и вызывает нужную функцию с правильными флагами в formatSpec.

Вот собственно код:

// эта структура существует для того что бы
// что бы безопасно и переносимо передавать va_list
// между разными функциями
struct va_list_wrapper
{
    va_list ap;
};
// ...
int vsnprintf(char *buf, size_t max_size, const char *fmt, va_list ap)
{
    FormatSpec formatSpec;
    va_list_wrapper wrapper{};
    va_copy(wrapper.ap, ap);

    if (max_size > 0) {
        char *pos = buf; // текущая позиция в буфере
// резервируем один символ для конца строки
        size_t size = max_size > 0 ? max_size - 1 : max_size;
// количество фактически записанных символов
        ptrdiff_t written = 0;
        // %[flags][field_width][.precision][size specifier]specifier
        for (size_t i = 0; *fmt && written < size; ++i, ++fmt) {
// обязательно сбрасываем на каждой итерации
            formatSpec.reset();
// выводим в строку все что не является %
            if (*fmt != '%') {
                *pos++ = *fmt;
// количество гипотетически записанных символов
                ++formatSpec.total;
                ++written;
                continue;
            }
          
// поймали %
            ++fmt; // идем дальше, к следующему за % символу
// парсим флаги, ширину поля и точность как объяснялось выше
            fmt = parse_flags_fw_precision(fmt, formatSpec, ap);
// парсим модификатор размера как объяснялось выше
            fmt = parse_size_modifier(fmt, formatSpec);
// не забываем, что если установлен флаг '-', то флаг '0' игнорируется
            if (formatSpec.flags & FormatFlags::F_MINUS) {
                formatSpec.flags &= ~FormatFlags::F_ZERO;
            }

            switch (*fmt) {
// для %% выводим %
                case '%':
                    *pos++ = *fmt;
                    ++formatSpec.total;
                    break;

                case 'd':
                case 'i': {
// это знаковые целые, d, i, ld, lld, li, lli
// значит флаг '#' для них мы игнорируем и убираем его что бы не смущать нашу
// функцию number_to_string
                    formatSpec.flags &= ~FormatFlags::F_ALT;
                    formatSpec.radix = 10;
// для i и d читаем просто int
                    auto value =
                        formatSpec.lengthSpec == LengthSpec::null ? va_arg(wrapper.ap, int) : read_signed_number(formatSpec,
                                                                                                         ap);
                    formatSpec.negative = value < 0;

                    if (value < 0) {
// для отрицательных чисел флаг ' ' игнорируется
                        value = -value;
                        formatSpec.flags &= ~FormatFlags::F_SPACE;
                    }
// проеобразуем все в строку
                    pos = format_number(pos, value, formatSpec, size - i);

                }
                    break;

                case 'u': {
// просто убираем флаг альтернативного представления, дальше магия сработает сама
                    formatSpec.flags &= ~FormatFlags::F_ALT;
                    pos = read_format_unsigned_int(pos, formatSpec, size - i, ap);
                }
                    break;

                case 'o': {
// просто выставляем radix или base кому как угодно. Далее все как в Хогвардсе,
// работает само
                    formatSpec.radix = 8;
                    pos = read_format_unsigned_int(pos, formatSpec, size - i, ap);

                }
                    break;
// тоже самое
                case 'X':
                    formatSpec.flags |= FormatFlags::F_HUGE;
                case 'x': {
                    {
                        formatSpec.radix = 16;
                        pos = read_format_unsigned_int(pos, formatSpec, size - i, ap);
                    }
                }
                    break;

                case 'p': {
                    auto value = read_unsigned_number(formatSpec, ap);
// тут я повторил поведение glibc, сторонний тест сломался ... я поправил его
// тут никакие флаги не работают, только '-' для nullptr
                    if (value > 0) {
                        formatSpec.flags &= ~FormatFlags::F_ZERO;
                        formatSpec.flags &= ~FormatFlags::F_SPACE;
                        formatSpec.flags &= ~FormatFlags::F_PLUS;
                        formatSpec.flags &= ~FormatFlags::F_ALT;
                        formatSpec.radix = 16;

                        if (formatSpec.precision == -1 && formatSpec.field_width == -1) {
                            formatSpec.precision = kPointerHexDigits;
                        }

                        pos = format_number(pos, value, formatSpec, size - i);
                    }
                    else {
// и то только в том случае когда мы работаем с указателем как со строкой
// мы выводим строку (Nil)
                        pos = format_string(pos, formatSpec, size - i, ap, kNil);
                    }
                }
                    break;
// далее все просто
                case 'n': {
                    size_t *ptr = va_arg(wrapper.ap, size_t*);

                    if (ptr) {
                        *ptr = written;
                    }
                }
                    break;

                case 'c':
                    pos = format_char(pos, formatSpec, size - i, ap);
                    break;

                case 's':
                    pos = format_string(pos, formatSpec, size - i, ap);
                    break;

                default:
                    *pos++ = *fmt;
                    ++formatSpec.total;
                    break;
            }

            written = pos - buf;
        }

        *pos = '\0';
    }

    return formatSpec.total;
}

Для полного понимания нам осталось рассмотреть только функцию read_format_unsigned_int.

Она достаточно простая и просто настраивает флаги и читает нужно значение из va_list

static char *read_format_unsigned_int(char *buf, FormatSpec &formatSpec,
                                      size_t size, va_list_wrapper &w)
{
    formatSpec.flags &= ~FormatFlags::F_SPACE;
    formatSpec.flags &= ~FormatFlags::F_PLUS;
    auto value =
        formatSpec.lengthSpec == LengthSpec::null ? va_arg(w.ap, unsigned int) : read_unsigned_number(
            formatSpec,
            ap);

    return format_number(buf, value, formatSpec, size);
}

Вот собственно и все!

В репозитории прилагаются тесты. Так же там реализованы ctype и строковые функции string.h, но они простые и рассмотрены тут не будут.

Следующий этап это минимальный abi itanium C++. Нужно будет реализовать минимум:
Потокобезоасную инициализацию локальных статических объектов, массивы переменного размера и перегрузки new/delete. Теперь мы к этому готовы, у нас есть аллокатор

До новых встреч!