Найди летающих друзей

Сегодня будет не по С++ контент, но я не мог мимо этого пройти. Надеюсь вы сейчас никуда не спешите и у вас есть огнетушитель под рукой, будет жарко.

В общем, недавно в твиттере завирусился японский "'экспресс" тест на деменцию. Задача очень простая - найти на картинке бабочку, летучую мышь и утку. Все это надо сделать за 10 мин. Успели - молодцы. Не успели - скорее всего ваша разработческая карьера продлится не так долго, как вы этого ожидаете.

У меня не хватает усидчивости на такие штуки. Через 3 минуты безрезультатного поиска мне захотелось с криками "лайт вейт бэйбэээ" выкинуть что-нибудь тяжелое из окна и я понял, что пора залезать в комменты и ловить спойлеры. Буду верить, что раз я искал не 10 мин, это все не считается.

❤️ - нашел всех за 10 мин.
🤬 - где эта ср*ная бабочка?!

Keep calm. Stay cool.

#fun

​​Присвоение лямбды
#новичкам

Изучение лямбда выражений - не самая простая задача для начинающего плюсовика. Сложные термины, какие-то замыкания, списки захвата и прочее. В общем, непросто. И с виду можно подумать, что 2 одинаковые лямбды можно присваивать друг другу с легкостью. То есть может показаться, что такой код валидный:

int main() {
  auto test = [](){};
  test = [](){};
    
  return 0;
}

Однако он генерирует примерно следующую ошибку:

In function ‘int main()’:
error: no match for ‘operator=’ in ‘test = <lambda closure object>main()::<lambda()>{}’
note: candidate is:
note: main()::<lambda()>& main()::<lambda()>::operator=(const main()::<lambda()>&) <deleted>
no known conversion for argument 1 from ‘main()::<lambda()>’ to ‘const main()::<lambda()>&’

Не нашел нужного оператора присваивания.

Да и вообще, это ж все лямбды, почему я не могу их присваивать друг другу?

Дело в том, что каждое отдельное лямбда-выражение генерирует свой тип, который называется замыканием. Только компилятор знает этот тип, вы его наружу никак не можете получить. Стандарт говорит:

The type of the lambda-expression [...] is a unique, unnamed non-union class type — called the closure type.

Это легко проверить. Такой код выведет 0:

auto test = [](){};
auto test2 = [](){};
std::cout << std::is_same_v<decltype( test ), decltype( test2 )> << std::endl;

Типы действительно разные.

В целом, поэтому вместе с лямбдами всегда нужно использовать auto. Потому что ничего другого вы вместо типа физически не сможете написать. Но компилятор знает тип замыкания и сможет вывести правильный тип для переменной.

Ну и естественно, для двух рандомных классов неопределены операторы присваивания своих объектов друг другу. Поэтому код из начала и фейлится.

Differentiate thing apart. Stay cool.

#cpp11

​​Что на самом деле представляют собой short circuit операторы?

Мы уже узнали, что операторы && и || для кастомных типов - простые функции. Для функций существует гарантия вычисления всех аргументов перед тем как функция начнет выполняться. Поэтому перегруженные версии этих операторов и не проявляют своих короткосхемных свойств. Однако операторы && и || для тривиальных типов - другое дело и имеют такие свойства. Но почему? Как это так работает в одном случае и не работает в другом? Давайте разбираться.

Во-первых(и в-единственных), операторы для тривиальных типов - это не функции. Они сразу превращаются в определенную последовательность машинных команд. Так как у нас теперь нет ограничения, что мы должны вычислить все аргументы сразу, то и похимичить можно уже знатно.

Если подумать, то логика тут очень похожа на вложенные условия. Если первое выражение правдиво, переходим в вычислению второго, если нет, то выходим из условия(это для &&). И если еще подумать, то у нас и нет никаких других средств это сделать, кроме джампов(условных переходов к метке). Покажу, во что примерно компиляторы С/С++ преобразуют выражение содержащее оператор &&. Не настаиваю на достоверность и точность. Объяснение больше для понимание происходящих процессов.

Вот есть у нас такой код

if (expr1 && expr2 && expr3) {  
  // cool operation
} else { 
  // even cooler operation
}
// the coolest operation

Он преобразуется примерно вот в такое:

if (!expr1) goto do_even_cooler_operation; 
if (!expr2) goto do_even_cooler_operation; 
if (!expr3) goto do_even_cooler_operation; 

{
  // cool operation
  goto do_the_coolest_operation;
} 

do_even_cooler_operation: 
{ 
  // even cooler operation
} 

do_the_coolest_operation:
  // the coolest operation

Что здесь происходит. Входим в первое условие и если оно ложное(то есть expr1 - true), то проваливаемся дальше в следующее условие и делаем так, пока наши выражения правдивые. Если они в итоге все оказались правдивыми, то мы входим в блок выполняющий клевую операцию и дальше прыгаем уже наружу первоначального условия и выполняем самую клевую операцию. Если хоть одно из выражений expr оказалось ложным, то мы переходим по метке и выполняем еще круче операцию и естественным образом переходим к выполнению самой крутой операции. Прикол здесь в трех условиях. Так как они абсолютно не связаны друг другом и последовательны, то следующее по счету выражение просто не будет выполняться, пока выполнение не дойдет до него. Таким образом и обеспечиваются последовательные вычисления слева направо.

То есть встроенные операторы && и || разворачиваются вот с такую гармошку условий. Надеюсь, для кого-то открыл глаза, как это работает)

See what's under the hood. Stay cool.

#compiler #cppcore

Квиз

Мы с вами недавно коснулись темы лямбд, поэтому вдогонку устроим #quiz по этой теме. Как всегда, тут нужно либо хорошее знание стандарта, либо хорошая интуиция. Хотя интуиция поможет вам на квиз только правильно ответить, челюсть с пола она вам не поднимет, когда вы поймете, в чем дело.

Итак. Какой результат попытки компиляции(с одним флагом указания стандарта С++20) и выполнения этого кода?:

int main() {
  auto test = +[]{};
  test = []{};
    
  return 0;
}

Ответ выйдет завтра.

Stay surprised. Stay cool.

Магическое заклинание +[]{}

Правильный ответ на квиз - программа успешно завершится. Удивились? Погнали разбирать

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

Дальше

Здесь мы рассматривали, что присвоение лямбд запрещено и приводит к ошибке компиляции. Каким образом один + переворачивает все сверх на голову и код работает?

Стандарт нам говорит:

The closure type for a lambda-expression with no lambda-capture has a public non-virtual non-explicit const conversion function to pointer to function having the same parameter and return types as the closure type's function call operator. The value returned by this conversion function shall be the address of a function that, when invoked, has the same effect as invoking the closure type's function call operator.

То есть ламбды без захваченых значений имеют возможность прикидываться указателями на функции.

И так вышло, что оператор+ определен для всех типов указателей в виде:

For every type T there exist candidate operator functions of the form

    T* operator+(T*);

Он ничего не делает с указателем и просто его возвращает наружу.

Когда мы ставим + спереди лямбды, компилятор пытается найти подходящую перегрузку для оператора+. Логично, что для любого замыкания он не перегружен, поэтому что он не нужен там. Но зато есть перегрузка для указателя, под который может косить лямбда. Что она успешно и делает.

Поэтому для здесь для test

auto test = +[]{};
auto test2 = []{};

компилятор выведет тип указателя на функцию, а не замыкания. И ничего нам не мешает перенаправлять этот указатель на другую функцию.

Итого, один бессмысленный плюс тащит катку.

Stay amazed. Stay cool.

#cpp11 #cppcore

​​Теория заговора

Вот живет программист по С++ своей прекрасной и беззаботной жизнью. Все у него хорошо: код пишется, баги фиксятся, деньги мутятся. И имя у него такое прекрасное - Иннокентий.

Иногда он лазается по cppreference, чтобы освежить знания по каким-то фичам или узнать что-то новое. Представим себе, что он зашел просмотреть на доку std::atoi и видит там такой фрагмент:

const auto data =
    {
        "42",
        "0x2A", // treated as "0" and junk "x2A", not as hexadecimal
        "3.14159",
        "31337 with words",
        "words and 2",
        "-012345",
        "10000000000" // note: out of int32_t range
    };

Ничего необычного, просто определяется std::initializer_list<const char *> и записываются туда разные строки. Ну ладно, работает дальше.

А дальше ищет статейку по std::variant. И находит там вот какой отрывок:

int main()
{
    std::variant<int, float> v, w;
    v = 42; // v contains int
    int i = std::get<int>(v);
    assert(42 == i); // succeeds
    w = std::get<int>(v);
    w = std::get<0>(v); // same effect as the previous line
    w = v; // same effect as the previous line
  ...
}

Почему-то он обратил внимание на число 42. "Где-то я его уже видел.". И вспоминает, что недавно видел это же число в коде для std::atoi. Это, конечно, немного странно - подумал, он. Но решил, что это просто случайность.

Приходит наш герой домой с работы и, как каждый уважающий себя программист, вместо ужина садится писать свой пет-проект. А вы не знали, что программисты могут годами жить на диете "код+кофе"?

Пишет он какое-то многопоточное приложение. Чтобы адекватно писать такие штуки, нужны глубокие знания о модели памяти в С++ и как работает синхронизация данных в многопроцессорном мире. Поэтому кодер снова идет на cppreference и находит там статейку про std::memory_order. Читает, читает. И херак, вылупил глаза в экран. "Это уже очень странно". А увидел он следующий фрагмент:

std::vector<int> data;
std::atomic<int> flag = {0};
 
void thread_1()
{
    data.push_back(42);
    flag.store(1, std::memory_order_release);
}

Опять это 42! "Что за приколы такие? Это что, любимое число плюсовиков, что они его везде пихают?". На том и порешил. Не нервничать же по поводу чьего-то любимого числа. Может именно на этот день рождения Страуструпу подарили маленького щеночка....

В общем, затерпели и забыли.

Иннокентий только начинает писать свой проект и ему нужен хороший сборочный скрипт. Выбор языка пал на модномолодежный питухон, поэтому он полез в документацию изучать базовый синтаксис питона. И тут на тебе:

x = int(input("Please enter an integer: "))
Please enter an integer: 42
if x < 0:
    x = 0
    print('Negative changed to zero')
elif x == 0:
    print('Zero')
elif x == 1:
    print('Single')
else:
    print('More')

Whatafuck? Страуструп здесь уже никак не может быть замешан. Ситуация больше похожа на массонский заговор. Кенни не выдержал и пошел распутывать тайну века.

Оказалось, что это отсылка на книгу Дугласа Адамса "Автостопом по галактике". Там люди создали супермощный супекомпьютер только с одной целью - узнать ответ на "Главный вопрос жизни, Вселенной и всего такого". Этот вопрос настолько сложный и комплексный, что на нахождение ответа суперкомпьютер потратил целых 7.5 млн лет вычислений. И в окончании выдал: "42".

Роман вышел в период расцвета sci-fi, поэтому оставил глубокий отпечаток в массовой культуре. Оно появлялось в популярных сериалах типа "Остаться в живых". Даже один из радиотелескопов НАСА использует ровно 42 тарелки в честь отсылки к произведению.

Неудивительно, что гики по всему миру начали пихать это число во всех места в качестве пасхалки. Сейчас почти где-угодно встречая 42, вы можете быть на 99% уверены, что это именно отсылка на "Автостопом по галактике".

Так и была разгадана величайшая из тайн иллюминатов и Иннокентий довольный пошел спать. The end.

Make references to the great things. Stay cool.

#fun

Представление отрицательных чисел в С++

Отрицательные числа - заноза в заднице компьютеров. В нашем простом мире мы различаем положительные и отрицательные числа с помощью знака. Положительные числа состоят просто из набора цифр(ну и по желанию можно добавить + слева, никто не обидится), а к отрицательным слева приписывается минус. Но компьютеры у нас имеют бинарную логику, там все представляется в виде единиц и ноликов. И там нет никаких плюсов-минусов. Тогда если у нас модуль числа уже представляется в виде единичек и ноликов, то непонятно, как туда впихнуть минус.

Вот и в комитете по стандартизации не знали, как лучше это сделать и удовлетворить всем, поэтому до С++20 они скидывали с себя этот головняк. До этого момента С++ стандарт разрешал любое представление знаковых целых чисел. Главное, чтобы соблюдались минимальные гарантии. А именно: минимальный гарантированный диапазон N-битных знаковых целых чисел был [-2^(N-1) + 1; 2^(N-1)-1]. Например, для восьмибитных чисел рендж был бы от -127 до 127. Это соответствовало трем самым распространенным способам представления отрицательных чисел: обратному коду, дополнительному коду и метод "знак-величина".

Однако все адекватные компиляторы современности юзают дополнительный код. Поэтому, начиная с С++20, он стал единственным стандартным способом представления знаковых целых чисел с минимальным гарантированным диапазоном N-битных знаковых целых чисел [-2^(N-1); 2^(N-1)-1]. Так для наших любимых восьмибитных чисел рендж стал от -128 до 127.

Кстати для восьмибитных чисел обратной код и метод "знак-амплитуда" были запрещены уже начиная с С++11. Все из-за того, что в этом стандарте сделали так, чтобы все строковые литералы UTF-8 могли быть представлены с помощью типа char. Но есть один краевой случай, когда один из юнитов кода UTF-8 равен 0x80. Это число не может быть представлен знаковым чаром, для которого используются обратной код и метод "знак-величина". Поэтому комитет просто сказал "запретить".

Для кого-то много непонятных слов и терминов, поэтому в дальнейшем будем раскрывать все секреты представления отрицательных чисел в памяти.

Stay defined. Stay cool.

#cppcore #cpp20 #cpp11

Квиз

Вчера в комментах наш подписчик Вячеслав скинул интересный примерчик, который здорово показывает вашу плюсовую интуицию. Поэтому захотелось разобрать его в рамках поста. Ну и для интереса предлагаю вам поучаствовать в #quiz и испытать свою интуицию. Код до боли краток, и до еще большей боли бессмысленен и ужасен. Но все же.

Какой будет результат попытки компиляции и запуска следующего кода?

#include <iostream>

int main () {
    std::cout << +-!!"" << std::endl;
    return 0;
}

Have a meaning in your life. Stay cool.

#fun

​​Ответ на квиз

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

#include <iostream>

int main () {
    std::cout << +-!!"" << std::endl;
    return 0;
}

Начнем с того, что этот код компилируется. Это уже много дает. По крайней мере вы смотрите на валидный С++ код.

Плюс-минусы и два восклицательных знака - валидные операции над валидными тривиальными типами. Поэтому, по факту, единственное, что надо доказать - что !"" - валидное выражение.

Разберемся с кавычками. Это строковый литерал, обозначающий пустую строку. И он имеет тип const char[1]. Единичка берется из-за того, что сишные строки неявно содержат символ '\0' в конце. Так собственно и определяется конец строки.

Для массивов не определен оператор логического отрицания. Печаль...

Но зато он определен для указателей! А у массивов есть одно замечательное свойство - косить под указатель на свой первый элемент. Поэтому для выполнения !"", компилятор приведет "" к const char *, который будет указывать на какой-то конкретный участок памяти, где лежит эта пустая строка. Раз участок конкретный - тогда этот указатель считается типа true. Отрицаем true - получаем false.

Дальше остается всего-то +-!false. Отрицает false - получаем true. Также у нас есть встроеные унарные операторы для арифметических типов. А bool - тоже арифметический тип. Поэтому true - это как бы 1. +-1 в итоге дает -1(+знака числа не меняет).

Таким нехитрым образом, получаем ответ: -1.

Ставьте снеговика☃️, если ваша интуиция(или знания) вас не подвели.

Stay on positive side. Stay cool.

​​Знак-амплитуда

Начнем раскрывать тему вариантов представления отрицательных чисел с метода "знак-величина" или sign-magnitude. Это самый интуитивно понятный для нас способ репрезентации целых чисел. В обычной математике как: есть грубо говоря модуль числа и его знак.

И это довольно просто перенести в память. Мы просто обговариваем, что наиболее значимый бит числа мы отводим по бит знака, а остальные биты обозначают модуль числа. Если знаковый бит - 0, значит число положительное. Если 1 - отрицательное. Таким образом получается вполне естественная ассоциация с привычными нам правилами. Есть натуральный ряд чисел плюс ноль. Чтобы получить множество всех целых чисел, нужно ко множеству натуральных чисел прибавить множество чисел, которое получается из натуральных путем добавления минуса в начале числа.

Давайте на примере. В восьмибитном числе только 7 бит будут описывать модуль числа, который может находится в отрезке [0, 127]. А самый старший бит будет отведен для знака. С добавлением знака мы теперь может кодировать все числа от -127 до 127. Так, число -43 будет выглядеть как 10101011, в то время как 43 будет выглядеть как 00101011. Однако очень внимательные читатели уже догадались, что эта форма представления отрицательных чисел имеет некоторые side-effect'ы, которые усложняют внедрение этого способа в реальные архитектуры:

1️⃣ Появление двух способов изображения нуля: 00000000 и 10000000.

2️⃣ Представление числа из определения разбивается на 2 части, каждая из которых должна иметься в виду и каким-то образом обрабатываться.

3️⃣ Из предыдущего пункта выходит, что операции сложения и вычитания чисел с таким представлением требуют разной логики в зависимости от знакового бита. Мы должны в начале "отрезать" знаковый бит, сделать операцию, которая соответствует комбинации знаковых битов операндов и первоначальной операции, и потом обратно совместить результат со знаком.

4️⃣ Раз у нас 2 нуля, мы можем представлять на 1 число меньше, чем могли бы в идеале.

В общем, минусы значительные. И хоть такое представление и использовалось в ранних компьютерах из-за интуитивной понятности для инженеров, однако в наше время этот способ представления знаковых целых чисел практически не используется.

Однако "знак-величина" используется по сей день, но немного для другого. IEEE floating point использует этот метод для отображения мантиссы числа. Есть модуль мантиссы(ее абсолютное значение) и есть ее знаковый бит. Кстати поэтому у нас есть положительные и отрицательные нули, бесконечности и NaN'ы во флотах. Вот как оно оказывается работает.

Apply yourself in the proper place. Stay cool.

#cppcore #base

Обратный код

Обратный код или ones' complement - уже более совершенное представление целых чисел в двоичном виде. Этот код позволяет очень легко выполнять операции сложения/вычитания над числами, используя только лишь операцию сложения.

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

a - b = a + (-b)

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

Как и во всех системах, поддерживающих представление отрицательных чисел, в нем есть зарезервированный знаковый бит, а затем идет "модуль" числа. Например, число 5 в двоичном виде представляется, как 101. Восьмибиное знаковое число 5 в обратном коде представляется, как 00000101. Старший бит 0 значит, что число положительное, дальше идут незначащие нули и в конце наше число.

Инвертированное же число получается просто обращением всех битов в обратные. 0 в 1 и 1 в 0.

То есть число -5 представляется, как 11111010.

И если мы сложим 2 обратных числа, то получим естественно 0:

00000101 + 11111010 = 11111111 = 0

Причем складываются два числа без учета "особенности" старшего бита. Сложение происходит просто как сложение двух двоичных чисел. Если сумма не умещается в заданное количество бит, то есть произошло "переполнение", то нужно сделать end-round carry aka добавление этого переполненного бита к сумме. Пока не очень понятно, но давайте попробуем что-нибудь посчитать:

31 - 12 = 31 + (-12) = 00011111 + (-00001100) = 00011111+ 11110011 = 1'00010010(произошло переполнение, поэтому отбрасываем старший бит и добавляем его к сумме) = 00010010 + 1 = 00010011 = 19

Получили ожидаемое положительное(знаковый бит 0) число 19.

Можем уйти в минуса:

25 - 29 = 25 + (-29) = 00011001 + (-00011101) = 00011001 + 11100010 = 11111011 = -00000100 = -4

Вот так все просто.

Но и у этого кода есть недостатки. Главный из них вы уже могли заметить в посте. Ноль представляется, как 11111111. Точнее, у нуля 2 значения - все нули и все единички. То есть появляется +0 и -0.

С точки зрения вычислений это особо никак не влияет на результат, но добавляет головной боли при разработке, так как надо тестировать софт и для отрицательного нуля.

Недостаток довольно надоедливый. Поэтому, и хоть динозавристые компьютеры использовали этот код, все современный машины используют дополнительный код. О нем в следующем посте.

Ну и вот этот end-round carry создает дополнительный этап вычисления: carry flag в процессоре нужно складывать с результатом.

Remove inconvenience from your life. Stay cool.

#base

​​Дополнительный код

Вот мы и дошли до самого распространенного способа представления знаковых целых чисел в современных компьютерах. Это дополнительный код или two's complement на бездуховном.

По своей сути, это чуть усложненный обратный код. Если там для представления отрицательного числа нам нужно было инвертировать все биты числа и дело в шляпе, то здесь нам к получившемуся результату добавить единичку.

То есть:

-5 = ~5 + 1 = ~0000101 + 1 = 11111010 + 1 = 11111011

Дополнительный код также поддерживает замену операции вычитания через сложение с обратным вычитаемым. В случае переполнения просто откидываем новый получившийся разряд.

Можем проверить, кстати, что при сложении 2 обратных друг другу чисел, мы получим 0.

13 - 13 = 13 + (-13) = 13 + ~13 + 1 = 00001101 + 11110010 + 1 = 11111111 + 1 = 1'00000000 = 0

Именно за счет добавления единички мы избегаем ситуации, когда у нас есть 2 разных способа кодирования нуля.

Однако теперь у нас несимметричный диапазон представляемых чисел, так как место одного из нулей должно занять другое число. Если для обратного кода он был [-(2^(N-1) - 1), 2^(N-1) - 1] ([-127, 127] для восьмибитных чисел), то для дополнительного кода он такой [-2^(N-1), 2^(N-1) - 1] ([-128, 127] для восьмибитных чисел).

Вы наверное все это читаете и немного грустите. Во-первых, скучно. Во-вторых, это надо просто заучить(возможно только для экзамена). Никаких аналогий в голове на это особо не придумаешь.

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

В английском достаточно знать слово complement и иметь немного воображения.

> Ones' complement (обратный код)
> Two's complement (дополнительный код).

Complement - дополнение. Грубо говоря если у вас есть часть предмета, то compliment это остальная часть, которой нужно дополнить вашу, чтобы получить целое.

В случае обратного кода (one's complement), отрицательное значение дополняет положительное так, чтобы их сумма давала в результате единицы во всех разрядах. Технически мы просто инвертируем биты, а идейно дополняем до всех единиц.

> (0) 000 -> 111 (-0)
> (1) 001 -> 110 (-1)
> (2) 010 -> 101 (-2)
> (3) 011 -> 100 (-3)

То есть: 000 + 111 = 001 + 110 = 010 + 101 = 011 + 100 == 111 - тот самый отрицательный ноль

Дополнительный код (two's complement) - похожий принцип. Здесь two (2) это основание системы счисления. Если у нас двоичная система счисления и есть N разрядов, то представление отрицательного значения должно дополнять представление положительного так, чтобы в сумме они давали 2^N. Например, для трёх бит 2^3 это (8) 1000. Следовательно:

> (0) 000 - у него нет "дополнения"
> (1) 001 -> 111 (-1)
> (2) 010 -> 110 (-2)
> (3) 011 -> 101 (-3)

001 + 111 = 010 + 110 = 011 + 101 = 1'000(2^3, откидываем старший разряд) == 0

А теперь еще немного магии для тех, кто путался, куда ставить апостроф в этих комплементах. Ones' complement -"дополнение до единиц". Единиц во множественном числе. То есть должны во всех разрядах получиться единицы при сложении с обратным. Two's complement - "дополнение до двойки". Двойки в единственном числе. Дополняем так, чтобы в сумме получилась степень двойки.

В английском апострофом обозначается принадлежность одного объекта другому. И для обозначения принадлежности существительным в единственном числе после слова идет апостроф и 's'. А для множественных просто апостроф(типа потому что s на конце уже есть).

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

Have a deep meaning in your life. Stay cool.

#base

​​Целочисленные переполнения

Переполнения интегральных типов - одна из самых частых проблем при написании кода, наряду с выходом за границу массива и попыткой записи по нулевому указателю. Поэтому важно знать, как это происходит и какие гарантии при этом нам дает стандарт.

Для беззнаковых типов тут довольно просто. Переполнение переменных этих типов нельзя в полной мере назвать переполнением, потому что для них все операции происходят по модулю 2^N. При "переполнении" беззнакового числа происходит его уменьшение с помощью деления по модулю числа, которое на 1 больше максимально доступного значения данного типа(то есть 2^N, N - количество доступных разрядов). Но это скорее не математическая операция настоящего деления по модулю, а следствие ограниченного размера ячейки памяти. Чтобы было понятно, сразу приведу пример.

Вот у нас есть число UINT32_MAX. Его бинарное представление - 32 единички. Больше просто не влезет. Дальше мы пробуем прибавить к нему единичку. Чистая и незапятнанная плотью компьютеров математика говорит нам, что в результате должно получится число, которое состоит из единички и 32 нулей. Но у нас в распоряжении всего 32 бита. Поэтому верхушка просто отрезается и остаются только нолики.

Захотим мы допустим пятерку, бинарное представление которой это 101, прибавить к UINT32_MAX. Произойдет опять переполнение. В начале мы берем младший разряд 5-ки и складываем его с UINT32_MAX и уже переполненяемся, получаем ноль. Осталось прибавить 100 в двоичном виде к нолю и получим 4. Как и полагается.

И здесь поведение определенное, известное и стандартное. На него можно положиться.

Но вот что со знаковыми числами?

Стандарт говорит, что переполнение знаковых целых чисел - undefined behaviour. Но почему?

Ну как минимум потому что стандарт отдавал на откуп компиляторам выбор представления отрицательных чисел. Как ранее мы обсуждали, выбирать приходится между тремя представлениями: обратный код, дополнительный код и метод "знак-амплитуда".

Так вот во всех трех сценариях результат переполнения будет разный!

Возьмем для примера дополнительный код и 4-х байтное знаковое число. Ноль выглядит, как 000...00, один как 000...01 и тд. Максимальное значение этого типа INT_MAX выглядит так: 0111...11 (2,147,483,647). Но! Когда мы прибавляем к нему единичку, то получаем 100...000, что переворачиваем знаковый бит, число становится отрицательным и равным INT_MIN.

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

Ситуация здесь на самом деле немного поменялась с приходом С++20, который сказал нам, что у нас теперь единственный стандартный способ представления отрицательных чисел - дополнительный код. Об этих изменениях расскажу в следующем посте.

Don't let the patience cup overflow. Stay cool.

#cpp20 #compiler #cppcore

​​Проверяем на целочисленное переполнение

По просьбам трудящихся рассказываю, как определить, произошло переполнение или нет.

Почти очевидно, что если переполнение - это неопределенное поведение, то мы не хотим, чтобы оно возникало. Ну или хотя бы хотим, чтобы нам сигнализировали о таком событии и мы что-нибудь с ним сделали.

Какие вообще бывают переполнения по типу операции? Если мы складываем 2 числа, то их результат может не влезать в нужное количество разрядов. Вычитание тоже может привести к переполнению, если оба числа будут сильно негативные(не будьте, как эти числа). Умножение тоже, очевидно, может привести к overflow. А вот деление не может. Целые числа у нас не могут быть по модулю меньше единицы, поэтому деление всегда неувеличивает модуль делимого. Значит и переполнится оно не может.

И какая радость, что популярные компиляторы GCC и Clang уже за нас сделали готовые функции, которые могут проверять на signed integer overflow!

bool __builtin_add_overflow(type1 a, type2 b, type3 *res);
bool __builtin_sub_overflow(type1 a, type2 b, type3 *res);
bool __builtin_mul_overflow(type1 a, type2 b, type3 *res);

Они возвращают false, если операция проведена штатно, и true, если было переполнение. Типы type1, type2 и type3 должны быть интегральными типами.

Пользоваться функциями очень просто. Допустим мы решаем стандартную задачку по перевороту инта. То есть из 123 нужно получить 321, из 7493 - 3947, и тд. Задачка плевая, но есть загвоздка. Не любое число можно так перевернуть. Модуль максимального инта ограничивается двумя миллиадрами с копейками. Если у входного значения будут заняты все разряды и на конце будет 9, то перевернутое число уже не влезет в инт. Такие события хотелось бы детектировать и возвращать в этом случае фигу.

std::optional<int32_t> decimal_reverse(int32_t value) {
  int32_t result{};
  while (value) {
    if (__builtin_mul_overflow(result, 10, &result) or
      __builtin_add_overflow(result, value % 10, &result))
      return std::nullopt;
    value /= 10;
  }
  return result;
}

int main() {
  if (decimal_reverse(1234567891).has_value()) {
    std::cout << decimal_reverse(1234567891).value() << std::endl;
  } else {
    std::cout << "Reversing cannot be perform due overflow" << std::endl;
  }
  
  if (decimal_reverse(1234567894).has_value()) {
    std::cout << decimal_reverse(1234567894).value() << std::endl;
  } else {
    std::cout << "Reversing cannot be perform due overflow" << std::endl;
  }
}

// OUTPUT:
// 1987654321
// Reversing cannot be perform due overflow

Use ready-made solutions. Stay cool.

#cppcore #compiler

Как компилятор определяет переполнение

В прошлом посте я рассказал, как можно детектировать signed integer overflow с помощью готовых функций. Сегодня рассмотрим, что ж за магия такая используется для таких заклинаний.

Сразу с места в карьер. То есть в ассемблер.

Есть функция

int add(int lhs, int rhs) {
  int sum;
  if (__builtin_add_overflow(lhs, rhs, &sum))
    abort();
  return sum;
}

Посмотрим, во что эта штука компилируется под гцц х86.

Все немного упрощаю, но в целом картина такая:

    mov %edi, %eax
    add %esi, %eax
    jo call_abort 
    ret
call_abort:
    call abort

Подготавливаем регистры, делаем сложение. А далее идет инструкция jo. Это условный прыжок. Если условие истино - прыгаем на метку call_abort, если нет - то выходим из функции.

Инструкция jo выполняет прыжок, если выставлен флаг OF в регистре EFLAGS. То есть Overflow Flag. Он выставляется в двух случаях:

1️⃣ Если операция между двумя положительными числами дает отрицательное число.

2️⃣ Если сумма двух отрицательных чисел дает в результате положительное число.

Можно считать, что это два условия для переполнения знаковых чисел. Например

127 + 127 = 0111 1111 + 0111 1111 = 1111 1110 = -2 (в дополнительном коде)

Результат сложения двух положительных чисел - отрицательное число, поэтому при таком сложении выставится регист OF.

Для беззнаковых чисел тоже кстати есть похожий флаг. CF или Carry Flag. Мы говорили, что переполнение для беззнаковых - не совсем переполнение, но процессор нам и о таком событии дает знать через выставление carry флага.

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

Но учитывая все условия для overflow, есть более простые способы его задетектить, чисто на арифметике. Но об этом позже.

Detect problems. Stay cool.

#base #cppcore #compiler

​​Signed Integer overflow

Переполнение знаковых целых чисел - всегда было и остается болью в левой булке. Раньше даже стандартом не было определено, каким образом отрицательные числа хранились бы в памяти. Однако с приходом С++20 мы можем смело утверждать, что стандартом разрешено единственное представление отрицательных чисел - дополнительный код или two's complement по-жидоанглосаксонски. Казалось бы, мы теперь знаем наверняка, что будет происходить с битиками при любых видах операций. Так давайте снимем клеймо позора с переполнения знаковых интов. Однако не все так просто оказывается.

С приходом С++20 только переполнение знаковых чисел вследствие преобразования стало определенным по стандарту поведением. Теперь говорится, что, если результирующий тип преобразование - знаковый, то значение переменной никак не изменяется, если исходное число может быть представлено в результирующем типе без потерь.
В обратном случае, если исходное число не может быть представлено в результирующем типе, то результирующим значением будет являться остаток от деления исходного значения по модулю 2^N, где N - количество бит, которое занимает результирующий тип. То есть результат будет получаться просто откидыванием лишних наиболее значащих бит и все!

Однако переполнение знаковых интов вследствие арифметических операций до сих пор является неопределенным поведением!(возмутительно восклицаю). Однако сколько бы возмущений не было, все упирается в конкретные причины. Я подумал вот о каких:

👉🏿 Переносимость. Разные системы работают по разным принципам и UB помогает поддерживать все системы оптимальным образом. Мы могли бы сказать, что пусть переполнение знаковых интов работает также как и переполнение беззнаковых. То есть получалось бы просто совершенно другое неожиданное (ожидаемое с точки зрения стандарта, но неожиданное для нас при запуске программы) значение. Однако некоторые системы просто напросто не продуцируют это "неправильное значение". Например, процессоры MIPS генерируют CPU exception при знаковом переполнении. Для обработки этих исключений и получения стандартного поведения было бы потрачено слишком много ресурсов.

👉🏿 Оптимизации. Неопределенное поведение позволяет компиляторам предположить, что переполнения не произойдет, и оптимизировать код. Действительно, если УБ - так плохо и об этом знают все, то можно предположить, что никто этого не допустит. Тогда компилятор может заняться своим любимым делом - оптимизировать все на свете.
Очень простой пример: когда происходит сравнение a - 10 < b -10, то компилятор может просто убрать вычитание и тогда переполнения не будет и все пойдет, как ожидается.

Так что УБ оставляет некий коридор свободы, благодаря которому могут существовать разные сценарии обработки переполнения: от полного его игнора до включения процессором "сирены", что произошло что-то очень плохое.

Leave room for uncertainty in life. Stay cool.

#cpp20 #compiler #cppcore

​​Ревью
#опытным

Сегодня будет довольно хардкорное #ревью в плане порога входа. Дело в том, что вы будете препарировать код, который использует неблокирующее апи ввода-вывода линуксов - epoll. Совсем вкратце, есть набор файловых дескрипторов и мы хотим в асинхронном режиме обрабатывать информацию, которая пришла на эти дискрипторы. Для этого мы :

1️⃣ Предварительно за кадром зарегистрировали нужные события на еполле

2️⃣ Создали массив из эвентов, в который эполл будет записывать произошедшие события

3️⃣ Дожидаемся этих событий в epoll_wait и дальше как-то обрабатываем.

Если вы знакомы с select|poll, то здесь небольшие отличия в интерфейсе + еполл сам говорит нам на каких дискрипторах появился евент.

Цель всего этого добра - подсчитать общее количество байт, которое пришло на все дескрипторы.

Понимаю, что от кода прям несет чистой сишатиной, но мы и такой код должны уметь ревьюить. Однако все предложения по улучшению могут включать в себя любые фичи стандартных плюсов.

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

Ну и чего ждем? Комментарии сами себя не напишут! Погнали хейтить чужой код!

Analyse solutions. Stay cool.

​​Результаты ревью
#опытным

Понимаю, что код был, мягко говоря, не для новичков, хоть и иллюстрировал начальный пример работы с epoll. Поэтому критиков не очень было много. Но все же Максим и Михаил хорошо постарались с поиском проблем. Давайте им похлопаем 👏👏👏.

А теперь суммируем.

Пройдемся по очевидному, что бросается в глаза сразу.

🔞 В функции read_data_and_count есть возвращаемое значение, но ничего не возвращается.

🔞 Повсюду утечки. Не освобождаются entries, не закрывается дескриптор epoll_fd.

🔞 Все три функции связаны и, если уж мы пишем на С++, то хочется все это дело обернуть в класс. А если не очень хочется, то хотя бы статиками пометить, чтобы скоуп не засорять.

🔞 Надоели указатели эти. Мы же С++, нам ссылки подавай!

🔞 Цикл, собирающий результаты мог бы быть более полюсовым и использовать стандартные функции из STL.

🔞 Как-то странно передавать десткрипторы именно массивом. Намного более универсальный инферфейс - указатели, так как массивы к ним неявно приводятся. А с указателями в вызывающем коде можно уже не сишный массив использовать, а нормальный вектор и передавать данные через метод data().

Из неочевидного:

😱 Использование VLA, то есть variable-length array, в строчке с epoll_event pending[N]. Это не стандарт языка С++, поэтому надо переделать на нормальный вектор.

😱 Не проверяются никакие ошибки. epoll_create1, epoll_wait, calloc, read - все эти системные функции не только говорят, что все летает и играет яркими красками, а еще и сигнализируют об ошибках. Здесь нигде их возвращаемые значения не проверяются, в надежде, что мы живем в мире розовых пони, где все всегда стабильно работает.

😱 Еполл может вернуть событие EPOLLERR в случае какой-то ошибки. А также он может прерваться из-за приема сигнала сгенерить ошибку EINTR. Опять же нет проверки.

😱 epoll_wait последним параметром принимает таймаут. -1 значит, что мы бесконечно блочимся в ожидании событий. И выходим из него только когда события произошли. Потенциально, это может длится примерно 100500 лет. Не очень хочется иметь потенциальную возможность получить бесконечный цикл. Поэтому какой-то таймаут поставить нужно, чтобы мы хотя бы об ошибке узнали.

😱 Не очень понятно, зачем обработчику событий знать о том, сколько файлов осталось, и влиять на это количество. Из process_epoll_event вполне можно возвращать индикатор, сигнализирующий о том, что мы прочитали данные из сокета до конца. Таким образом чисто внутренняя переменная files_left становится в единоличной власти своей материнской функции. Собственно, как и должно быть. Тогда и флаг done в структуре не нужен.

😱 Обо всех ошибках вызывающему коду хотелось бы знать, поэтому надо как-то сообщать ему о них. Можно по аналогии с сисколами использовать возвращаемое значение -1, как индикатор ошибки, но по плюсовому можно использовать std::optional. Ну или кидать исключения/возвращать объект ошибки, кому как нравится.

Фух, вроде все, что увидел, написал. Кто еще что-то заметит - не стесняйтесь, пишите в комменты. Исправленный код скину в комменты.

Let people critique your solutions. Stay cool.