Pull to refresh
-6
0
Рустем Шайдуллин @ndiezel

User

Send message

Тернистый путь Hello World

Reading time 16 min
Views 32K

Вдохновение на написание данной статьи было получено после прочтения похожей публикации для архитектуры x86 [1].


Данный материал поможет тем, кто хочет понять, как устроены программы изнутри, что происходит до входа в main и для чего всё это делается. Также я покажу как можно использовать некоторые особенности библиотеки glibc. И в конце, как и в оригинальной статье [1] будет визуально представлен пройденный путь. В большинстве своём статья представляет собой разбор библиотеки glibc.


Итак, начнём наш поход. Будем использовать Linux x86-64, а в качестве инструмента отладки — lldb. Также иногда будем дизассемблировать программу при помощи objdump.


Исходным текстом будет обычный Hello, world (hello.cpp):


#include <iostream>
int main()
{
        std::cout << "Hello, world!" << std::endl;
}
Читать дальше →
Total votes 76: ↑75 and ↓1 +74
Comments 4

Библиотека быстрого поиска путей на графе

Reading time 8 min
Views 35K

Привет, Друзья!


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


Пример использования на огромном графе:



Поиграться с демо можно здесь


В библиотеке используется мало-известный вариант A* поиска, который называется NBA*. Это двунаправленный поиск, с расслабленными требованиями к функции-эвристике, и очень агрессивным критерием завершения. Не смотря на свою малоизвестность у алгоритма отличная скорость сходимости к оптимальному решению.


Описание разных вариантов A* уже не раз встречалось на хабре. Мне очень понравилось вот это, потому повторяться в этой статье я не буду. Под катом расскажу подробнее почему библиотека работает быстро и о том, как было сделано демо.

Читать дальше →
Total votes 114: ↑112 and ↓2 +110
Comments 53

Как работает видеопроцессор

Reading time 29 min
Views 70K
image

[Прим. пер.: оригинал статьи называется GPU Performance for Game Artists, но, как мне кажется, она будет полезной для всех, кто хочет иметь общее представление о работе видеопроцессора]

За скорость игры несут ответственность все члены команды, вне зависимости от должности. У нас, 3D-программистов, есть широкие возможности для управления производительностью видеопроцессора: мы можем оптимизировать шейдеры, жертвовать качеством картинки ради скорости, использовать более хитрые техники рендеринга… Однако есть аспект, который мы не можем полностью контролировать, и это графические ресурсы игры.

Мы надеемся, что художники создадут ресурсы, которые не только хорошо выглядят, но и будут эффективны при рендеринге. Если художники немного больше узнают о том, что происходит внутри видеопроцессора, это может оказать большое влияние на частоту кадров игры. Если вы художник и хотите понять, почему для производительности важны такие аспекты, как вызовы отрисовки (draw calls), уровни детализации (LOD) и MIP-текстуры, то прочитайте эту статью. Чтобы учитывать то влияние, которое имеют ваши графические ресурсы на производительность игры, вы должны знать, как полигональные сетки попадают из 3D-редактора на игровой экран. Это значит, что вам нужно понять работу видеопроцессора, микросхемы, управляющей графической картой и несущей ответственность за трёхмерный рендеринг в реальном времени. Вооружённые этим знанием, мы рассмотрим наиболее частые проблемы с производительностью, разберём, почему они являются проблемой, и объясним, как с ними справиться.
Читать дальше →
Total votes 54: ↑53 and ↓1 +52
Comments 12

Пошаговый план старта на Upwork

Reading time 3 min
Views 262K
image

Рано или поздно разработчик всерьез задумывается о фрилансе. В этот момент большинство идут на биржи. Выбор бирж огромен. В СНГ: fl.ru, weblancer и прочие. Но когда доходишь до дела начинаешь понимать в каком все упадке. Единственным местом где водятся более-менее нормальные заказы можно назвать fl.ru и еще одну-две биржы. Но на fl.ru нужен pro аккаунт, ведь оказывается чтобы взять заказ нужно заплатить бирже, и далеко не факт что тебе что-то светит. Поэтому было решено идти на Upwork.
Читать дальше →
Total votes 57: ↑51 and ↓6 +45
Comments 99

Попиксельная заливка экрана в Wolfenstein 3D

Reading time 4 min
Views 41K
В коде id Software порой встречаются бесподобные жемчужины. Самая знаменитая — это, конечно, 0x5f3759df, удостоившаяся даже комикса на xkcd. Здесь же речь пойдёт о заливке экрана: пиксели закрашиваются по одному в случайном порядке, без повторов. Как это сделано?

Читать дальше →
Total votes 152: ↑151 and ↓1 +150
Comments 96

История предсказания переходов с 1 500 000 года до н.э. по 1995 год

Reading time 18 min
Views 42K
Это приблизительная расшифровка лекции о предсказании переходов (предсказании ветвлений) на localhost, новом цикле лекций, организованном RC. Выступление состоялось 22 августа 2017 года в Two Sigma Ventures.

Кто из вас использует ветвления в своём коде? Можете поднять руку, если применяете операторы if или сопоставление с образцом?

Большинство присутствующих в аудитории поднимают руки

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

Цель моего выступления — объяснить, как и почему процессоры осуществляют предсказание переходов, а затем вкратце объяснить классические алгоритмы предсказания переходов, о которых вы можете прочитать в современных статьях, чтобы у вас появилось общее понимание темы.
Читать дальше →
Total votes 77: ↑74 and ↓3 +71
Comments 77

Поддержка системных ошибок в C++

Reading time 23 min
Views 31K

Предисловие


Я долго думал, нужно ли делать перевод этого, уже известного, цикла статей под названием «System error support in C++0x», повествующего о <system_error> и обработке ошибок. С одной стороны он написан в 2010 году и меня попросту могут счесть некрофилом, а с другой стороны в рунете очень мало информации по этой теме и многие довольно свежие статьи ссылаются на этот цикл, что говорит о том, что он не теряет актуальности и по сей день.

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

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

Итак, приступим.
Читать дальше →
Total votes 36: ↑36 and ↓0 +36
Comments 11

Как легко расстаться с $1000

Reading time 4 min
Views 40K
  • Прелюдия
  • Разработка игры под iOS
  • Продвижение игры
  • Чисто поржать

Прелюдия


Эта история случилась в мае ровно на той скамейке, где Берлиоз с Бездомным поспорили о сущности Христа. Мы с приятелями тоже поспорили о возможности заработать на своей iPhone-игре. Я заявил, вдруг, что без вложения денег это невозможно. Мои оппоненты нехотя согласились. Я усилил троллинг и добавил: — Друзья мои, без больших денег это совершенно невозможно! Любая сумма менее $25000, потраченная на раскрутку приложения — обернется пшиком. Пшшшш!

Все возмутились и прогнали меня со скамейки. Заодно уж и из Москвы.

По следам публикации


По следам публикации разгорелась нешуточная борьба за Кубок 26-08.
Игроки с Хабра настолько сильны, что в первый же день выгнали меня с вершины Олимпа. Но! В первой башне я нашел решение на 2 очка лучше прочих.И победил парней из Украины и России.
Можем еще!

Total votes 102: ↑90 and ↓12 +78
Comments 47

«Магическая константа» 0x5f3759df

Reading time 9 min
Views 120K
В этой статье мы поговорим о «магической» константе 0x5f3759df, лежащей в основе элегантного алгоритмического трюка для быстрого вычисления обратного квадратного корня.

Вот полная реализация этого алгоритма:

float FastInvSqrt(float x) {
  float xhalf = 0.5f * x;
  int i = *(int*)&x;  // представим биты float в виде целого числа
  i = 0x5f3759df - (i >> 1);  // какого черта здесь происходит ?
  x = *(float*)&i;
  x = x*(1.5f-(xhalf*x*x));
  return x;
}

Этот код вычисляет некоторое (достаточно неплохое) приближение для формулы

image

Сегодня данная реализация уже хорошо известна, и стала она такой после появления в коде игры Quake III Arena в 2005 году. Её создание когда-то приписывали Джону Кармаку, но выяснилось, что корни уходят намного дальше – к Ardent Computer, где в середине 80-ых её написал Грег Уолш. Конкретно та версия кода, которая показана выше (с забавными комментариями), действительно из кода Quake.
В этой статье мы попробуем разобраться с данным хаком, математически вывести эту самую константу и попробовать обобщить данный метод для вычисления произвольных степеней от -1 до 1.

Да, понадобится немного математики, но школьного курса будет более, чем достаточно.
Читать дальше →
Total votes 212: ↑210 and ↓2 +208
Comments 188

Автономный способ обхода DPI и эффективный способ обхода блокировок сайтов по IP-адресу

Reading time 7 min
Views 697K
Провайдеры Российской Федерации, в большинстве своем, применяют системы глубокого анализа трафика (DPI, Deep Packet Inspection) для блокировки сайтов, внесенных в реестр запрещенных. Не существует единого стандарта на DPI, есть большое количество реализации от разных поставщиков DPI-решений, отличающихся по типу подключения и типу работы.

Существует два распространенных типа подключения DPI: пассивный и активный.

Пассивный DPI

Пассивный DPI — DPI, подключенный в провайдерскую сеть параллельно (не в разрез) либо через пассивный оптический сплиттер, либо с использованием зеркалирования исходящего от пользователей трафика. Такое подключение не замедляет скорость работы сети провайдера в случае недостаточной производительности DPI, из-за чего применяется у крупных провайдеров. DPI с таким типом подключения технически может только выявлять попытку запроса запрещенного контента, но не пресекать ее. Чтобы обойти это ограничение и заблокировать доступ на запрещенный сайт, DPI отправляет пользователю, запрашивающему заблокированный URL, специально сформированный HTTP-пакет с перенаправлением на страницу-заглушку провайдера, словно такой ответ прислал сам запрашиваемый ресурс (подделывается IP-адрес отправителя и TCP sequence). Из-за того, что DPI физически расположен ближе к пользователю, чем запрашиваемый сайт, подделанный ответ доходит до устройства пользователя быстрее, чем настоящий ответ от сайта.
Читать дальше →
Total votes 212: ↑212 and ↓0 +212
Comments 352

Продвинутые перечисления с Ruby

Reading time 9 min
Views 17K
Перечисления (enumeration) по определению это — «действие упоминания некоторого количества чего-либо один за одним». В программировании, вместо упоминания, мы выбираем любое действие, которое хотим произвести, будь то простой вывод на монитор или выполнение некоторого рода выборки и/или преобразования над элементом.

В программировании, у нас есть много способов делать выборку и обработку коллекции за единицу времени, путем добавления в цепочку дополнительной функции трансформации на каждом шаге. И каждый шаг, может как потреблять целиком всю коллекцию перед тем как передать результаты обработки следующем шагу, или он может обрабатывать коллекцию «лениво», передавая один или более элементов коллекции через все шаги преобразований.
Читать дальше →
Total votes 14: ↑13 and ↓1 +12
Comments 0

Введение в октодеревья

Reading time 31 min
Views 36K


Что такое октодеревья? Если вам совершенно неизвестно это понятие, то рекомендую прочитать статью в Википедии (это займёт около пяти минут). Она даёт достаточное представление, но едва ли её будет достаточно, чтобы понять, для чего они используются и как их реализовать.

В этой статье я постараюсь рассказать обо всех этапах, необходимых для создания структуры данных октодеревьев, на примере объяснения концепций, иллюстраций и кода. Также я опишу свои решения, которые принимал на каждом из этапов. Не думайте, что эта статья будет единственно верным руководством к реализации октодеревьев, но она должна дать вам хороший фундамент и её можно использовать для справки.
Читать дальше →
Total votes 49: ↑49 and ↓0 +49
Comments 17

Создание шейдеров

Reading time 27 min
Views 187K
Освоить создание графических шейдеров — это значит взять под свой контроль всю мощь видепроцессора с его тысячами параллельно работающих ядер. При таком способе программирования требуется другой образ мышления, но раскрытие его потенциала стоит потраченных усилий.

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


Сцена из Minecraft, до и после добавления нескольких шейдеров.

Задача этого туториала


Иногда программирование шейдеров представляется загадочной чёрной магией и его часто понимают неправильно. Существует множество примеров кода, демонстрирующих создание невероятных эффектов, но в которых практически нет объяснений. В своём руководстве я хочу восполнить этот пробел. Я сосредоточусь в основном на базовых принципах создания и понимания кода шейдеров, чтобы вы смогли с лёгкостью настраивать, сочетать или писать свои собственные шейдеры с нуля!
Total votes 105: ↑105 and ↓0 +105
Comments 27

Вычисление значения выражения

Reading time 7 min
Views 47K
В продолжение поста Компилятор выражений. По просьбам читающих. Специально для michurin

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

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

Мы будем идти слева на право, добавляя операнды в один стек, а операции в другой. При каждом добавлении новой операции мы будем пытаться вытолкнуть из стека старые, руководствуясь приоритетами операций.
Читать дальше →
Total votes 59: ↑55 and ↓4 +51
Comments 36

Как работает Git

Reading time 19 min
Views 148K
В этом эссе описана схема работы Git. Предполагается, что вы знакомы с Git достаточно, чтобы использовать его для контроля версий своих проектов.

Эссе концентрируется на структуре графа, на которой основан Git, и на том, как свойства этого графа определяют поведение Git. Изучая основы, вы строите своё представление на достоверной информации, а не на гипотезах, полученных из экспериментов с API. Правильная модель позволит вам лучше понять, что сделал Git, что он делает и что он собирается сделать.

Текст разбит на серии команд, работающих с единым проектом. Иногда встречаются наблюдения по поводу структуры данных графа, лежащего в основе Git. Наблюдения иллюстрируют свойство графа и поведение, основанное на нём.

После прочтения для ещё более глубокого погружения можно обратиться к обильно комментируемому исходному коду моей реализации Git на JavaScript.
Читать дальше →
Total votes 110: ↑99 and ↓11 +88
Comments 38

Модель взаимодействия судов с водой в видеоиграх

Reading time 16 min
Views 36K


Давайте поговорим о физике транспортных средств


Физика транспортных средств в видеоиграх не очень сильно обсуждается. Статьи в Интернете о физике транспорта в видеоиграх немногочисленны и поверхностны; обычно они посвящены самым основам. Программист транспорта для видеоигр ощущает себя сегодня в относительном вакууме. Возможно, такая ситуация возникла, потому что эту тему довольно сложно объяснить, а может быть, мы просто стыдимся признаваться в использовании хаков, упрощений и хитростей, которые мы вносим по сравнению с «правильной», реалистичной симуляцией физики. Как бы ни обстояло дело, видеоигры имеют уникальные проблемы в симуляции транспорта, а значит, об этом стоит писать. Это захватывающая тема, относящаяся к физике, работе с камерой, звуку, спецэффектам, а также к восприятию и психологии человека.

Я решил сначала поговорить о судах, потому что недавно работал с ними; ещё я обнаружил, что их динамика не совсем понимается даже на уровне исследований (хотя многое и понятно). Модели и теории формулируются таким образом, что их становится сложно применить непосредственно в видеоиграх. Или же они требуют очень ресурсоёмких методов симуляции, которые практически невозможно контролировать и адаптировать под причудливые потребности разработчиков и игроков. Но можно написать упрощённую модель, которая учитывает важные параметры судна. В этом определённо есть доля искусства, «прыжка веры» и небольшая доля «творческой» физики, которая заставит Кельвина и Стокса перевернуться в могилах.
Читать дальше →
Total votes 97: ↑97 and ↓0 +97
Comments 30

Как opcache портил мою жизнь и тратил мои нервы

Reading time 2 min
Views 21K
Jackie-Chan_opcache

Все началось с апдейта php, давным давно и в этой же самой галактике. И с того момента меня преследовала одна мерзкая проблема, которая портила мне жизнь на протяжении достаточно длительного времени.
Читать дальше →
Total votes 46: ↑16 and ↓30 -14
Comments 73

Теперь ваш HTTPS будет прослушиваться, а сертификат для MitM вы должны поставить сами

Reading time 4 min
Views 221K


Пока не Россия. Но уже Казахстан. Как писал ValdikSS в своем посте Казахстан внедряет свой CA для прослушивания всего TLS-трафика:
Государственный провайдер Казахтелеком, в связи с нововведениями закона Республики Казахстан «О связи», намерен с 1 января 2016 года прослушивать весь зашифрованный TLS-трафик, подменяя сертификаты сайтов национальным сертификатом безопасности, выпущенным Комитетом связи, информатизации и информации Министерства по инвестициям и развитию Республики Казахстан.

Что нового произошло с тех пор? Beeline и Telecom.kz (основной провайдер-монополист) выкатили обновленные инструкции по установке государственного сертификата, который позволит осуществлять атаку man-in-the-middle с подменой сертификата. Ссылка на государственный сертификат.
Что это такое и чем это грозит?
Total votes 155: ↑150 and ↓5 +145
Comments 580

Information

Rating
Does not participate
Location
Уфа, Башкортостан(Башкирия), Россия
Date of birth
Registered
Activity