Как стать автором
Обновить

Комментарии 65

>Согласно современному стандарту C++, сдвиг влево отрицательного числа приводит к неопределённому поведению.

Не являюсь C++ программистом, но интересно, почему так?
Статья на эту тему.
Статья неплохая, но полного ответа на вопрос она не дает, просто ссылается на стандарт.
Быть может потому, что старший бит часто является знаком и при сдвиге влево (любом: арифметическом или циклическим) он уничтожится или завернется в младший разряд. При арифметическом сдвиге вправо старший разряд копируется и поэтому такой ситуации нет.
Стандарт не читал, но уверен, что UB ради перформанса. Сдвигая биты не ожидаешь изменения знака, т.е. при сдвиге вправо нужно дублировать старший бит, а при сдвиге влево нужно сдвигать все биты, кроме старшего. Это сложнее делать, поэтому биты просто сдвигаются и число становится то знаковым, то беззнаковым, в зависимости от того, какой бит попадётся. При этом оно из дополнительной формы не преобразовывается и числа просто «скачут». В общем, UB он и есть UB.
>> при сдвиге вправо нужно дублировать старший бит
CPU, в массе своей, имеют команды логического и арифметического сдвига. Репликация старшего бита осуществляется аппаратно.
Так что сдвиг int вправо работает на любом известном мне компиляторе, несмотря на то, что он отнесён к UB.

>> а при сдвиге влево нужно сдвигать все биты, кроме старшего.
Вы точно понимаете основы представления чисел в дополнительном коде?
-1 это 0xffffffff (для 32-битного числа). Ничего со старшим битом делать не надо.
Если же у вас происходит переполнение из 30 в 31 бит, то по-любому будет неверное число.
Если разбудить среди ночи, то про дополнительный код вряд ли отвечу. Но! Помимо -1 есть и куча других отрицательных чисел. Например, если взять целое "-9651325" и 31 сдвинуть его по одному биту влево, то получаются вот такие числа:
1824228096
-646511104
-1293022208
1708922880
-877121536
-1754243072
786481152
1572962304
-1149042688
1996881920
-301203456
-602406912
-1204813824
1885339648
-524288000
-1048576000
-2097152000
100663296
201326592
402653184
805306368
1610612736
-1073741824
-2147483648

Как видите, проблема не в том, что происходит «переполнение в старший бит». Ка краз наоборот! Происходит «недополнение». Т.е. 1 заменяется на 0. Если говорить о переполнении, то при сдвиге влево любого отрицательного числа старший выпадает. При сдвиге вправо реплицируется, как вы заметили, а при сдвиге влево замещается младшим битом.

Это вывод в MSVC2015-debug. Т.к. UB, то цифры могут быть другими в других условиях.
я не знаю что вы выводите, но -9651325 это FF6CBB83
Его вы можете сдвинуть влево 7 раз без переполнений

>> «переполнение в старший бит». Ка краз наоборот! Происходит «недополнение».
Не нужно изобретать «недотермины».
Предлагаете для каждого отрицательного числа выяснять, сколько раз его можно сдвинуть влево без изменения знака? Я не знаю, как underflow по русски будет, поэтому «недополнение».

Я тоже не знаю, но Яндекс утверждает, что это будет «потеря значимости». Google сильно неадекватнее: «изчезновение».


В любом случае, непонятно, при чём тут «underflow»: underflow будет когда вы (целое)3 разделите на (целое)2 и получите (целое)1, а не (с плавающей точкой)1,5.

НЛО прилетело и опубликовало эту надпись здесь
Существует несколько способов представления отрицательных чисел: прямое, сдвиг, дополнение до единицы, дополнение до двух…
Как представляет их микроконтроллер, это его дело, но (-1)<<1 (сдвиг без всякой логики) может превратиться в:
прямое) 1001 -> 0010 = 2,
сдвиг) 0111 -> 1110 = 6 (в 8-битной логике 126),
до 1) 1110 -> 1100 = -3,
до 2) 1111 -> 1110 = -2.

Скорей всего, дело в том, что крайний левый бит отвечает за знак. А побитовый сдвиг сдвигает все биты (в том числе и знаковый), и непонятно, что будет в этом крайнем бите после сдвига.


P.S. Я тоже не C++ программист, поэтому это лишь мои догадки

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

Так что даже так, не совсем понятно, почему поведение зовут «неопределенным».
Разные процессоры реализуют сдвиг по-разному, поэтому комитет поступил, как поступает обычно в таких случаях — объявил поведение неопределённым. Цитата под спойлером насчёт сдвига на ширину, большую размеру типа, но со сдвигом отрицательных чисел история та же.

Скрытый текст
Shifting a uint32_t by 32 or more bits is undefined. My guess is that this originated because the underlying shift operations on various CPUs do different things with this: for example, X86 truncates 32-bit shift amount to 5 bits (so a shift by 32-bits is the same as a shift by 0-bits), but PowerPC truncates 32-bit shift amounts to 6 bits (so a shift by 32 produces zero). Because of these hardware differences, the behavior is completely undefined by C (thus shifting by 32-bits on PowerPC could format your hard drive, it is *not* guaranteed to produce zero). The cost of eliminating this undefined behavior is that the compiler would have to emit an extra operation (like an 'and') for variable shifts, which would make them twice as expensive on common CPUs.

What Every C Programmer Should Know About Undefined Behavior #1/3
Спасибо вам и meduzik за ответы. Тогда возникает интересный вопрос — почему в стандарте 98 года, как раз, когда соотношение между архитектурами еще не так сильно перекашивало так сильно в сторону отдельных пунктов, поведение неопределенным объявлено еще не было?

Скорее всего, одно из двух: либо не догадались о потере производительности на этом моменте, либо не уделили достаточно внимания описанию в спеке. Человеческий фактор, стандарт большой и его пишет много людей.

Стандарт C++ не гарантирует вам представление отрицательных чисел. На некоторых архитектурах это вполне может быть не привычный two's complement, а one's complement или еще какой-то экзотический вариант.

Далее, опять же, на некоторых патформах некоторый набор бит в числе может быть так называемым trap representation, то есть вызывать хардварные исключения при появлении в вычислениях. Один из примеров — Signaling NaN.

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

Поскольку стандарты C и C++ писались «в пользу компилятора», то есть чтобы позволить максимальное число оптимизаций, они разрешают компилятору считать, что trap не произойдет и, значит, сдвига отрицательных чисел в программе нет.
Ради интереса, покажите false-positive.

В прошлой статье я нашёл одно ложное срабатывание, в этой


void CBuffer::Execute()
{
  ....
  QuatT * pJointsTemp = static_cast<QuatT*>(
    alloca(m_state.m_jointCount * sizeof(QuatT)));
  ....
}

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


Но я пока не знаю теорию статического анализа так хорошо, как авторы, поэтому не могу оценить объём работы, который требуется, чтобы проанализировать эти два случая правильно. Более того, формально второе предупреждение скорее всего верно, потому что использовать Си-инициализацию в С++ разрешено только для POD-типов, а QuantT не подходит под это определение. И я не помню стандарт так хорошо, чтобы точно сказать, может ли быть UB при таком определении и при такой инициализации класса.

НЛО прилетело и опубликовало эту надпись здесь
А мне стыдно за ваш комментарий. Странно да?
НЛО прилетело и опубликовало эту надпись здесь
Ладно, тогда 75% всего бюджета будем выделять дизайнерам.
НЛО прилетело и опубликовало эту надпись здесь
Таким софтом пользуются не для просмотра красивых кнопок и логотипов.
НЛО прилетело и опубликовало эту надпись здесь
Предлагаю Вам начать писать статьи на Хабре, чтобы продемонстрировать красивый дизайн в оформлении иллюстраций и тем самым повысить общий уровень представленного здесь материала. Сделаем вместе мир лучше!
«Не заметил Ваш комментарий»…
Вы из тех людей, которые говорят, что всё плохо в России, национальные беды какие-то упоминаете, но сами при этом не пытаетесь что-либо сделать для изменения ситуации?

Я много таких людей встречал. Уезжая в другую страну, такие людей точно также будут сетовать на проблемы в этой стране.
Что плохого в сетовании на проблему? Уж точно лучше, чем жевать кактус.
Сразу картинка в голове: бабульки на скамейке говорят за жизнь. Толку сетовать и ничего не делать. Это ничем не отличается от жевания кактуса.
> High: 576

ого!!! Вам не кажется, что это ОЧЕНЬ МНОГО ошибок для коммерческой разработки? (или для сипипей это норма?)
В тырнетах все такие умные — про тесты говорят, инверсии зависимостей, шаблоны, а тут проверили годами полируемый код — и такая лажа! Кого ж эти СлёзоТеки наняли, что на выходе имеют такое позорное качество?

Но коммент не ради этого, удивлят другое — как эта копипастная лапша вообще работала-то?? Вы все учили матрицы, 3D и всё такое — нельзя просто взять и вместо Z присвоить Y — получится такая белиберда, что её вообще на экране нельзя отображать! У них там что, на каждую индусофункцию ещё 10, которые исправляют баги первой? :)

PS
Для сипиписников с их ужасным инструментом, PVS — это must have за любые деньги!
Там проверки на коректность, а не присвоения, две большие разницы. Часть этих проверок в реальности может вообще оказаться лишней. Да и не надо делать вид, будто такую ошибку можно допустить только на плюсах. Конечно, 500 — это чуть-чуть многовато, но в движке не килобайт кода. Даже не мегабайт. Даже не 100 мегабайт. Так что будьте аккуратнее, сравнивая огромный проект и ваш личный опыт.

Что до годами полируемого кода — очень смешно. Если бы это было так, у них бы была графика уровня 2003 года. А у них реальная гонка по скоростному освоению новых высот геймдева и, прежде всего, графена. И тут за право первым реализовать поддержку DX11 или VulkanAPI приносят в жертву не одного бычка, включая спагетти-код.

> сипиписников с их ужасным инструментом
А вот это про что было?
Скорее уж тогда DX12, ну так, позанудствовать :)
Тогда уж лучше VR и продвинутую поддержку окулуса с кардбоксом, это ж самый мейнстрим. Ну так, позанудствовать)
Игровык движки это адовый овер-инженеринг. Это всё может фикситься на других уровнях абстракции. Не думаю, что каждый будет лезть в middleware при каждой баге. Время тоже дорого.
Перепись людей, не работавших на продакшене, объявляется открытой
Для UB тоже надо единорога сделать.
ХЗ какой должен быть единорог для UB :-).

image
Неопределённый Единорог.
Неопределеннорог
Единорог Шрёдингера?
Розовый единорог! (в обнимку с чайником Рассела)
— ты его не видишь, а он есть!
Круто, так их, багов, давить!

[Далее небольшой сеанс конструктивной (надеюсь) критики]

Скажите, а у вас есть доступ к native speaker'ам или хотя бы к учителям английского?
Мне кажется, это слишком похоже на «рунглиш со словарём»:
— «There is a probability of logical error presence
— «The '...' variable is assigned values twice successively
— «Member of a class is initialized by itself»
— «always returns one and the same value»
— «The memcmp function receives the pointer and its size as arguments.»
(аналогично вашей статье, выбрал только несколько ошибок для демонстрации, обращайтесь за полным отчётом :))

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

Keep up the good work!
Тимур, привет! Пойдешь к нам на эту работу?
Евгений, привет, давно не виделись!
Сколько предлагаете? :D
Пошли в личку. Но прежде чем написать свой ценник, вспомни, что мы маленькая провинциальная компания :-).
Другим: учитесь на работу устраиваться!
Кстати, на полном серьёзе, примерно так я и устроился на свою первую работу: на презентации одной команды нашёл что они не подумали об одной проблеме, и прислал им прототип решения этой проблемы.
;)
const float endTime = spawn.delay + HasDuration()? spawn.duration: fHUGE;

Так писать вообще плохая практика, неужели переменной отдельной жалко выделить под spawnDuration.
Вы на столько идеальный и стерильный, что у вас даже нет своего крайенжна.
Плохая практика?
Здравствуйте. Я очень давно работаю с движками серии «CryEngine», и у меня есть несколько вопросов касательно ошибок которые нашёл ваш анализатор, конкретно меня интересуют ошибки связанные с функциями и алгоритмами выделения памяти объектам в движке. Дело в том, что в движке есть очень серьёзные проблемы с выделением памяти, зачастую движок не в состоянии задействовать более 3.5 гигабайт системной памяти, иногда меньше, иногда чуть больше, зависит от того чем заполнять память, инстанциями каких объектов и т.д. Это наблюдается на любом железе с достаточным объёмом оперативной памяти и любой 64х разрядной ОС. Данная проблема, скорее всего, уже имела место быть с самой первой версии движка, однако я с ней столкнулся начиная со второй версии движка(CryEngine 2), первую не тестировал на предмет наличия.

Собственно, при достижении указанного значения потребления памяти движок просто выдаёт ошибку выделения памяти(memory allocation for x bytes failed) по сей день на самой последней версии СЕ 5.1.1, прямо «из коробки», т.е без каких либо изменений кода и прочих элементов. На систему установлено 32 гигабайта оперативной памяти, в других движках, например «Юнити 5», подобных проблем с выделением памяти не наблюдалось. Память 100% остаётся свободна при возникновении ошибки, были протестированы конфигурации с 8ю и 16ю гигабайтами памяти, ошибка проявляется всегда при одинаковых условиях, появление ошибки так же не зависит от размера файла подкачки(при размере меньше 1го гб появляется похожая ошибка но уже с рекомендацией увеличить размер «heap» памяти).

Что меня конкретно интересует по результатам анализа: ошибки и спорные места в файлах GeneralMemoryHeap.h и cpp, MemoryFragmentationProfiler.h, MemoryAddressRange.h и cpp, MemoryManager.h и cpp, CryMemoryManager.cpp, CustomMemoryHeap.h и cpp, MTSafeAllocator.h и срр, PageMappingHeap.h и срр, CryDLMalloc.c, CrySizerImpl.h и срр, LevelHeap.cpp, MemReplay.h и срр а так же SystemWin32.cpp. Крайтек игнорирует сообщения об этой ошибке на своих форумах уже довольно давно, или в некоторых случаях просто не может сказать ничего вразумительного. Учитывая тот факт что за 10 лет проблема как была так и осталась то просто очевидно что фиксить они её не собираются в ближайшее время.

Данная проблема проявляет себя во всей красе при работе с большими уровнями, или уровнями с хорошей детализацией( в большом количестве мелкие объекты, инстанции растительности и пр.), всё это в совокупности может привести к заполнению движком 3.5 гб памяти с последующим возникновением ошибки выделения памяти. При тестировании такого уровня в дальнейшем в режиме игры проблем не возникает, т.к в режиме игры включаются определённые оптимизации и часть объектов просто не загружается в память полностью, тем не менее можно вызвать данную ошибку выделения даже во время игры заспавнив определённое количество объектов в любых местах уровня, при этом количество объектов не обязательно будет слишком большим, скажем 1700 объектов, что далеко от предела количества объектов на одном уровне обозначенного в офиц. документации.

Буду также очень рад если вы поделитесь своими идеями по поводу корней данной проблемы а так же возможных теоретических способах её решения. Вообще я стараюсь работать только с 2мя модулями движка — СryGame и CryAction и не лезть в другие модули, но моя надежда на то что Крайтек решит эту проблему в каком нибудь обновлении движка давно утрачена, а учитывая что теперь исходный код почти всех модулей доступен — почему бы не попробовать решить её?
Из описания не понятно, речь идёт о 32-битной или 64-битной версии библиотеки. Если о 32-битной, то тогда собственно это нормальное поведение — просто не хватает памяти (3.5 гигабайт это и есть предел). И даже если в данный момент выделено меньше, все равно из-за фрагментации памяти может возникнуть ситуация, когда нельзя выделить память под очередной большой массив.

Если речь о 64-битной версии, то скорее всего библиотека содержит классические 64-битные ошибки, о которых мы много писали. И тогда, когда память начинает выделяться за пределами младших 4 гигабайт, начинаются различные проблемы. Например, может разрушаться менеджер памяти и нехватка памяти это просто последствия его некорректной работы. На 64-битные ошибки мы код библиотеки не исследовали, так как для написания статьи нам хватило и предупреждений общего назначения. :)
Из описания не понятно, речь идёт о 32-битной или 64-битной версии библиотеки.
Там вроде нормально написано:
Это наблюдается на любом железе с достаточным объёмом оперативной памяти и любой 64х разрядной ОС.

Не думаю, что человек, тестирующий на 32ГБ ОЗУ в течении 10 лет споткнётся о такую простую ошибку как несоответствие разрядности ОС и библиотеки.
А причём здесь разрядность ОС? А причём здесь несоответствие разрядности ОС и библиотеки? Всё смешалось, кони, люди…

Программа 32-битная или 64-битная?!
Версия библиотек 64х битная, 32х битная версия не поддерживает редактор уровней,.ехе файл редактора давно не поставляется с ней в комплекте, потому то я и не посчитал нужным указать информацию о версии. Спасибо за ответ, значит проблема всё же в 64х битных ошибках.
почему бы не попробовать решить её?


Потому что подобные ошибки с памятью очень тяжело отлаживать. Даже программисту, который помнит свой код наизусть. А уж человеку, впервые увидевшему эти исходники, тем более нужно огромное количество времени, чтобы хоть как-то начать ориентироваться. И вообще, проблема может заключаться не только в движке, но и в каких-то сторонних библиотеках или даже в операционной системе (мало ли, какая программа из-за ошибки вышла за пределы своей памяти).
мало ли, какая программа из-за ошибки вышла за пределы своей памяти
На какой платформе, поддерживаемой CryEngine, это возможно, на приставках?
Думаю проблема всё же в коде движка, сторонние библиотеки здесь не играют роли, разные версии движка тестировались на разных ОС и железе(конечно количество установленной оперативной памяти позволяло диагностировать ошибку), ошибка везде одинаковая, количество свободной памяти при возникновении ошибки достаточно большое(в случае 32х гб свободными остаются более 22х), ос и библиотеки движка 64х битные. А так понятно что дело сложное, тем не менее при возникновении ошибки дебаггер первым делом скидывает на модуль CrySystem, впрочем я ещё толком не смотрел что там, нужно сначала его скомпилировать чтобы сгенерировалась информация для дебаггера. В общем движок сам по себе стал нестабилен со времён пятой версии, иногда зависает на начальном этапе загрузки без видимых причин, бывает что вылетает на загрузке уровня указав на atidxx64.dll. В предыдущих версиях (EAAS) подобные проблемы отсутствовали, за исключением конечно ошибки выделения памяти.
Зарегистрируйтесь на Хабре , чтобы оставить комментарий