Хобрук: Ваш путь к мастерству в программировании

Реализация memset для установки целого слова вместо байта за байтом в C

Итак, я пытаюсь реализовать свой личный MemSet, который будет делать то же самое, что и memset, но также:

  • По возможности копируйте фрагменты размером слова, а не байт за байтом.

  • Гарантия выравнивания назначения

  • Проверка всех возможностей выравнивания

Итак, это мой код:

void *MemSet(void *dest, int c, size_t n)
{
    unsigned char *runner = (unsigned char *)dest;
    
    size_t i = 0;
    
    unsigned char swap_word[sizeof(size_t)];
    
    for (i = 0; i < sizeof(size_t); ++i)
    {
        swap_word[i] = (unsigned char)c;
    }
    
    if (NULL == dest)
    {
        return (NULL);
    }
    
    while (n > 0)
    {
        /* setting byte by byte */
        if (n < sizeof(size_t) || (((size_t)runner & (sizeof(size_t) - 1)) != 0))
        {
            *runner++ = (unsigned char)c;
            --n;
            printf("Byte written\n"); /* for debugging */
        }
        else
        {
            /* setting a whole word */
            *((void **)runner) = *((void **)swap_word);
            runner += sizeof(size_t);
            n -= sizeof(size_t);
            printf("Word written\n"); /* for debugging */
        }
    }
    return (dest);
}

Что я здесь делаю?

  • создание указателя без знака runner для запуска поверх dest, но без изменения его адреса, поэтому я смогу вернуть его в качестве возвращаемого значения.

  • создание готового массива swap_word с размером sizeof(size_t), потому что этот размер определяет, является ли моя машина 32-битной или 64-битной (и, следовательно, размер WORD составляет 4 или 8 байтов. Этот массив будет заменен, когда мне нужно будет установить слово.

  • запуск простого while loop, который проверит, осталось ли для установки более sizeof(size_t) байтов, если нет, это точно означает, что мы не сможем установить целое слово, а затем установить их байт за байтом.

  • Другой вариант установить байты побайтно, если адрес не делится на 4 или 8 (опять же, зависит от машины), что означает, что я не смогу установить слово без пересечения WORD Boundary, поэтому просто установите их байт за байтом, пока я не достигну выровненного адреса.

  • Единственный вариант настроить целое слово — только если данные уже выровнены с WORD size машины, а затем просто установить 8 байт (просто установите их, используя массив swap_word, который мы сделали ранее, и продвиньте еще 8 адресов. Я сделаю это с помощью приведения

    *((void **)бегун) = *((void **)swap_word);

и это мой тестовый файл:

int array[] = { 2, 3 };
    
int main () 
{
    for (i = 0; i < 2; i++)
    {
        printf("Before MemSet, target is \"%d\"\n\n", array[i]);
    }
    if (NULL == MemSet(array, 3, 2 * sizeof(int)))
    {
        fprintf(stderr,"MemSet failed!\n");
        
    }
    for (i = 0; i < 2; i++)
    {
        printf("After MemSet, target is \"%d\"\n\n", array[i]);
    }
    return (0);
}

Выход:

Before Memset, target is "2"

Before Memset, target is "3"

Word written
After Memset, target is "50529027"

After Memset, target is "50529027"

Почему элементы не «3»? оба из них? я использую здесь

MemSet(array, 3, 2 * sizeof(int))

Что, по идее, должно установить оба элемента как 3, потому что массив использует 2*sizeof(int) пробелов в памяти, а я устанавливаю их все как 3.

Как вы думаете? А также, как я могу проверить, работает ли мое выравнивание?

Спасибо.

08.03.2021

  • Накладные расходы вашего кода сводят на нет все преимущества, которые он может иметь по сравнению с простым байтовым набором памяти. 09.03.2021
  • @ЕвгенийШ. Я просто следую инструкциям своей задачи, я должен добавить эту опцию установки целого слова, если это возможно. 09.03.2021

Ответы:


1

Ваша функция имеет несколько проблем:

  • вы проверяете изменение размера слова на каждой итерации, что, вероятно, медленнее, чем простая операция с байтами.

  • *((void * *)runner) = *((void **)swap_word); неверен, потому что нарушает правило псевдонимов и потому что swap_word может быть неправильно выровнено для типа void *.

Вы должны запускать отдельные циклы:

  • первый, чтобы выровнять указатель назначения
  • второй для установки полных слов, возможно, более одного за раз
  • последний, чтобы установить конечные байты, если они есть

Вот пример:

#include <limits.h>
#include <stdio.h>
#include <stdint.h>

// assuming uintptr_t has no padding bits
void *MemSet(void *dest, int c, size_t n) {
    if (dest != NULL) {
        unsigned char *p = dest;
        if (n >= sizeof(uintptr_t)) {
            // align destination pointer
            // this test is not fully defined but works on all classic targets
            while ((uintptr_t)p & (sizeof(uintptr_t) - 1)) {
                *p++ = (unsigned char)c;
                n--;
            }
            // compute word value (generalized chux formula)
            uintptr_t w = UINTPTR_MAX / UCHAR_MAX * (unsigned char)c;
            // added a redundant (void *) cast to prevent compiler warning
            uintptr_t *pw = (uintptr_t *)(void *)p;
            // set 16 or 32 bytes at a time
            while (n >= 4 * sizeof(uintptr_t)) {
                pw[0] = w;
                pw[1] = w;
                pw[2] = w;
                pw[3] = w;
                pw += 4;
                n -= 4 * sizeof(uintptr_t);
            }
            // set the remaining 0 to 3 words
            while (n >= sizeof(uintptr_t)) {
                *pw++ = w;
                n -= sizeof(uintptr_t);
            }
            p = (unsigned char *)pw;
        }
        // set the trailing bytes
        while (n --> 0) {
            *p++ = (unsigned char)c;
        }
    }
    return dest;
}

Однако обратите внимание, что приведенный выше код вряд ли превзойдет memset(), потому что:

  • компилятор может расширить приведенную выше логику в строке для константных размеров, пропуская тесты выравнивания, если известно, что указатель назначения выровнен или если ЦП разрешает невыровненный доступ.
  • библиотека может использовать специализированные инструкции, такие как SIMD или REP/STOS, для увеличения пропускной способности в зависимости от фактического целевого ЦП.

Причина неожиданных результатов заключается в том, что int охватывает 4 байта, каждый из которых получает значение 3, поэтому результирующее значение для целого числа равно 0x03030303, что в точности равно 50529027.

08.03.2021
  • Кандидат в качестве альтернативы (uintptr_t)0x0101010101010101 --> UINTPTR_MAX/0xFF. Теперь не ограничивается sizeof(uintptr_t) <= 8. 09.03.2021
  • @chux-ReinstateМоника: спасибо! Я нашел еще более общую формулу, позволяющую использовать не 8-битные байты... Только при условии отсутствия битов заполнения. 09.03.2021
  • while ((uintptr_t)p & (sizeof(uintptr_t) - 1)) — разумный, но не указанный способ достижения выравнивания. Нет способа сделать это в C. 09.03.2021
  • @chux-ReinstateMonica: я мог бы использовать while ((uintptr_t)p & (alignof(uintptr_t) - 1)), но это было бы менее портативно. 09.03.2021
  • Мне нравится идея 4, но, возможно, я использую #define CHUNK 4 или что-то подобное. 09.03.2021
  • @chux-ReinstateMonica: хорошая идея, но тогда мне пришлось бы полагаться на развертывание цикла. 09.03.2021
  • (uintptr_t)p & anything предполагает математическое свойство преобразованного указателя - значения указателя не указаны как линейные, но, скорее всего, таковыми являются. Хорошая работа МАК. 09.03.2021
  • Мне не разрешено использовать uintptr_t, поэтому я использую size_t 09.03.2021
  • поэтому я изменил каждое место, где вы это написали, на size_t. Он компилируется и запускается, но относительно отправки strings в функцию - не работает. Что касается int, он работает, в приведенном выше примере, отправляющем int array из 2 элементов, он устанавливает число 24 для первых элементов, а 2-й - 0. Вместо того, чтобы они оба были 3 09.03.2021
  • @NoobCoder: я добавил объяснение значения 50529027, которое вы наблюдаете. Должна быть другая проблема при копировании приведенного выше кода, чтобы получить результат в комментарии. В частности, что вы имеете в виду под относительно строк, отправляемых в функцию - это не работает? 09.03.2021
  • @NoobCoder: если вы измените все uintptr_t на size_t, вы также должны изменить UINTPTR_MAX на SIZE_MAX. 09.03.2021
  • @chqrlie хорошо, это работает, но это работало и раньше (благодаря вашему объяснению о int value теперь я понимаю, что мой код также работает по мере необходимости). Вы сделали 3 петли, которые делают то же самое, что и моя одна петля (на мой взгляд) 09.03.2021
  • @NoobCoder: ваш цикл выполняет 3 теста на слово и имеет проблему с выравниванием swap_word, но он будет работать для текущих процессоров Intel. Мое предложение уменьшает количество тестов для больших размеров примерно до 0,25 на слово и пропускает накладные расходы для небольших размеров... Это больше работы, но в среднем может быть более эффективным, в зависимости от конкретного использования приложения. 09.03.2021
  • @chqrlie Последний вопрос. Можете ли вы объяснить мне, почему while ((uintptr_t)p & (sizeof(uintptr_t) - 1)) действителен и определяет, соответствует ли адрес 4/8 (в зависимости от машины)? Почему здесь требуется -1? 09.03.2021
  • @NoobCoder: sizeof(uintptr_t)-1 — это битовая маска, в которой все биты установлены ниже значения выравнивания. while ((uintptr_t)p & mask) эквивалентно while (((uintptr_t)p & mask) != 0) проверяет, является ли указатель невыровненным, т.е. установлен ли один из младших битов. 09.03.2021
  • Новые материалы

    Как симулировать серию пенальти на Python с помощью симуляции Монте-Карло, часть 1: генерация функций
    Серия пенальти была огромным испытанием во время чемпионата мира по футболу. Они вызвали много споров в социальных сетях и новостных агентствах. Даже финальный матч турнира решался по..

    AST для разработчиков JavaScript
    TL; DR Эта статья - мое выступление на недавно состоявшейся конференции Stockholm ReactJS Meetup. Вы можете посмотреть слайды здесь..

    5 проектов на Python, которые нужно создать прямо сейчас!
    Добро пожаловать! Python — один из моих любимых языков программирования. Если вы новичок в этом языке, перейдите по ссылке ниже, чтобы узнать о нем больше:

    Dall-E 2: недавние исследования показывают недостатки в искусстве, созданном искусственным интеллектом
    DALL-E 2 — это всеобщее внимание в индустрии искусственного интеллекта. Люди в списке ожидания пытаются заполучить продукт. Что это означает для развития креативной индустрии? О применении ИИ в..

    «Очень простой» эволюционный подход к обучению с подкреплением
    В прошлом семестре я посетил лекцию по обучению с подкреплением (RL) в моем университете. Честно говоря, я присоединился к нему официально, но я редко ходил на лекции, потому что в целом я нахожу..

    Освоение информационного поиска: создание интеллектуальных поисковых систем (глава 1)
    Глава 1. Поиск по ключевым словам: основы информационного поиска Справочная глава: «Оценка моделей поиска информации: подробное руководство по показателям производительности » Глава 1: «Поиск..

    Фишинг — Упаковано и зашифровано
    Будучи старшим ИТ-специалистом в небольшой фирме, я могу делать много разных вещей. Одна из этих вещей: специалист по кибербезопасности. Мне нравится это делать, потому что в настоящее время я..