И вновь завершился очередной отборочный online-этап ежегодного соревнования по кибербезопасности — NeoQUEST-2018.

Что было? Хм… Оказалось, что в Атлантиде тоже используют Android, но файлы передают по старинке: с помощью Bluetooth, беспокоятся о безопасности транзакций и создают распределенные сети, взламывают сайты конкурентов и используют информационную разведку, а ещё — почти все компьютеры работают на таинственном «QECOS», написанном на LUA, но с большим количеством опечаток. Как здесь выжить? Читайте под катом.

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

Я попытался объяснить всё в деталях и оставить код максимально простым, насколько это возможно. Если у вас возникли вопросы, предложения или какие-либо проблемы, пожалуйста, оставьте комментарий или создайте таску на GitHub. Исходный код доступен в репозитории.

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

IP-адрес (v4) состоит из 32-бит. Любой уважающий себя админ, да и вообще айтишник (про сетевых инженеров молчу) должен уметь, будучи разбуженным среди ночи или находясь в состоянии сильного алкогольного опьянения, правильно отвечать на вопрос «из скольки бит состоит IP-адрес». Желательно вообще-то и про IPv6 тоже: 128 бит.

Обстоятельство первое. Всего теоретически IPv4-адресов может быть:
2³² = 2¹⁰*2¹⁰*2¹⁰*2² = 1024*1024*1024*4 ≈ 1000*1000*1000*4 = 4 млрд.
Ниже мы увидим, что довольно много из них «съедается» под всякую фигню.

Записывают IPv4-адрес, думаю, все знают, как. Четыре октета (то же, что байта, но если вы хотите блеснуть, то говорите «октет» — сразу сойдете за своего) в десятичном представлении без начальных нулей, разделенные точками: «192.168.11.10».

В заголовке IP-пакета есть поля source IP и destination IP: адреса источника (кто посылает) и назначения (кому). Как на почтовом конверте. Внутри пакетов у IP-адресов нет никаких масок. Разделителей между октетами тоже нет. Просто 32-бита на адрес назначения и еще 32 на адрес источника.

Здравствуйте, хабродамы и хаброгоспода!

Recently попался мне случайно на глаза один эпизод из недавно модного сериала «Мистер Робот». Не будучи сильно знакомым с проектом, я всё же знал о связанной с ним массивной пиар-кампании (которая вроде как даже проводила нечто вроде ARG-мероприятий), поэтому когда я услышал условие занимательного CTF-таска (из жанра bin/exploitation), представленного в сюжете одной из серий, я подумал, что скорее всего, этот таск существовал в действительности. Обратившись ко всемирной паутине, я подтвердил своё предположение, и, так как задача не очень сложная (не успеет наскучить в рамках одной хабростатьи), но крайне оригинальная и интересная, сегодня займемся её разбором.
Cut, cut, cut!

(с)

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

Когда речь заходит о генераторах случайных (или псевдослучайных) чисел, рассказ всегда строится вокруг поиска истинной случайности. Пока серьезные математики десятилетиями ведут дискуссии о том, что считать случайностью, в практическом отношении мы давно научились использовать «правильную» энтропию. Впрочем, «шум» — это лишь вершина айсберга.

С чего начать, если мы хотим распутать клубок самых сильных алгоритмов PRNG и TRNG? На самом деле, с какими бы алгоритмами вы не имели дело, все сводится к трем китам: seed, таблица предопределенных констант и математические формулы.

Каким бы ни был seed, еще есть алгоритмы, участвующие в генераторах истинных случайных чисел, и такие алгоритмы никогда не бывают случайными.

Одна из причин, почему Bitcoin продолжает привлекать столько внимания — это его исключительная «математичность». Сатоши Накамото удалось создать систему, которая способна функционировать при полном отсутствии доверия между ее участниками. Все взаимодействия основаны на строгой математике, никакого человеческого фактора — вот в чем была революционность идеи, а не в одноранговой сети, как многие думают. Поэтому первую главу я решил посвятить именно математическим основам Bitcoin.

Ниже я постараюсь объяснить вам самые базовые вещи — эллиптические кривые, ECC, приватные / публичные ключи и так далее. По возможности я буду иллюстрировать свои слова примерами кода, преимущественно на Python 2.7, если что-то непонятно — спрашивайте в комментариях.

В подавляющем большинстве источников информации о нейронных сетях под «а теперь давайте обучим нашу сеть» понимается «скормим целевую функцию оптимизатору» лишь с минимальной настройкой скорости обучения. Иногда говорится, что обновлять веса сети можно не только стохастическим градиентным спуском, но безо всякого объяснения, чем же примечательны другие алгоритмы и что означают загадочные и в их параметрах. Даже преподаватели на курсах машинного обучения зачастую не заостряют на этом внимание. Я бы хотел исправить недостаток информации в рунете о различных оптимизаторах, которые могут встретиться вам в современных пакетах машинного обучения. Надеюсь, моя статья будет полезна людям, которые хотят углубить своё понимание машинного обучения или даже изобрести что-то своё.

Под катом много картинок, в том числе анимированных gif.

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

При каждом сравнении алгоритм двоичного поиска разбиваем пространство поиска пополам. Благодаря этому всегда будет не более $$ сравнений со временем выполнения $$. Красиво, эффективно, полезно.

Но всегда можно посмотреть под другим углом.

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

Если ты богат – ты покупаешь ролекс за $42 тысячи. Но если ты самый богатый человек мира – ты строишь собственные часы за $42 миллиона. Такой проект реализует Джефф Безос, основатель Amazon с состоянием $120 млрд. Гигантские часы, которые, как он считает, смогут простоять дольше, чем человеческая цивилизация. Вчера вечером миллиардер объявил, что сборка уникального устройства, разработка технологий для создания которого велась 12 лет, наконец стартовала. Первый механизм высотой 150 метров был установлен глубоко в выдолбленных пустотах одной из гор в Техасе.

alizar уже запостил в виде новости (его не опередить!). У нас чуть более расширенно – о том, откуда вообще взялся этот проект и почему так много лучших людей планеты тратят на него своё время.

Вы когда-нибудь сталкивались с таким кодом?

process(true, false);

Эта функция, судя по названию, что-то обрабатывает (process). Но что означают параметры? Какой параметр здесь true, а какой false? По вызывающему коду об этом нельзя судить.

Нам придется заглянуть в объявление функции, которое дает подсказку:

void process(bool withValidation,
             bool withNewEngine);

Очевидно, автор использует два параметра типа bool как флаги (toggles). Реализация функции может быть похожа на это:

void process(bool withValidation,
             bool withNewEngine)
{
  if (withValidation)  // используется 1-й флаг
    validate(); // % подтвердить
 
  do_something_toggle_independent_1
 
  if (withNewEngine)   // используется 2-й флаг
    do_something_new();
  else
    do_something_old();
 
  do_something_toggle_independent_2();
}

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

Бобра!

Что ж, мы плавно выходим на старт второго потока группы «Разработчик С++» и разбираем интересные материалы, которые накопились у преподавателя в свободное от работы и преподавания время. Сегодня рассмотрим (а потом и продолжим) серию материалов, где разбираются отдельные пункты С++ Core Guidelines.

Поехали.

В C++ Core Guidelines много правил, посвященных выражениям и операторам. Если быть точным, то более 50 правил посвящено объявлениям, выражениям, операторам и арифметическим выражениям.



*перевод
Информативные названия

Оптимальная длина переменных

• Не должны быть слишком длинными (maximimNumberOfPointsInModernOlympics.) или слишком короткими (например, x, x1)
• Длинные названия сложно печатать, короткие названия недостаточно информативны..
• Дебажить программы с названиями от 8 до 20 символов гораздо проще
• Гайдлайны не заставляют вас срочно менять названия переменных на имена из 9-15 или 10-16 символов. Но если вы найдете в своем коде более короткие названия, убедитесь, что они достаточно информативны.

Слишком длинные: numberOfPeopleOnTheUsOlympicTeam; numberOfSeatsInTheStadium; maximumNumberOfPointsInModernOlympics
Слишком короткие: n; np; ntmn; ns; nslsd; m; mp; max; points
В самый раз: numTeamMembers, teamMembersCount

Как-то раз в голове возникла мысль, а что бы сделать такое, чтобы скрестить старый радиоприемник в деревянном корпусе и современный контроллер для интернета-вещей ESP32? То ли с головой не так что-то, то ли делать мне нечего, но скрестить получилось. Не шаблонно, в целом, хотя судить вам, дорогие читатели Хабра).

За подробностями прошу под кат.

Всем бобра!

У нас стартует третий набор на курс «Разработчик Python», а значит, что впереди и открытый урок, которые у нас частично замещают староформатные дни открытых дверей и где можно ознакомиться с интересным материалом от наших преподавателей, и то, что мы нашли очередной интересный материальчик. На этот раз по ускорению «змеиного» кода.

Поехали.

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

ДИСКЛЕЙМЕР: это не чудодейственное средство на все случаи жизни, да, сработало конкретно в этом случае, но может оказаться не таким эффективным во многих других. Однако метод все равно интересный. Более того, шаги, описанные здесь, я применял во время разработки в том же порядке, что делает статью жизненным примером оптимизации PyPy.

Я экспериментировал с эволюционными алгоритмами несколько месяцев назад: план был амбициозным — автоматически развить логику, способную контролировать (симулированный) квадрокоптер, то есть PID-регулятор (спойлер: не летает).

Код этого поста, как и сам пост, выложен на github.

До недавнего времени регулярные выражения казались мне какой-то магией. Я никак не мог понять, как можно определить, соответствует ли строка заданному регулярному выражению. А теперь я это понял! Ниже представлена реализация простого движка регулярных выражений менее чем в 200 строках кода.

Часть 1: Парсинг

Спецификация

Реализация регулярных выражений полностью — довольно сложная задача; хуже того, она мало чему вас научит. Реализуемой нами версии достаточно для того, чтобы изучить тему, не скатываясь в рутину. Наш язык регулярных выражений будет поддерживать следующее:

• . — соответствие любому символу
• | — соответствие abc или cde
• + — соответствие одному или более предыдущего паттерна
• * — соответствие 0 или более предыдущего паттерна
• ( и ) — для группировки

Хотя набор опций невелик, с его помощью можно создать интересные regex-ы, например, m (t|n| ) | b позволяющий найти субтитры к Star Wars без субтитров к Star Trek, или (..)* для нахождения множества всех строк чётной длины.

План атаки

Мы будем анализировать регулярные выражения в три этапа:

1. Парсинг (синтаксический анализ) регулярного выражения в синтаксическое дерево
2. Преобразование синтаксического дерева в конечный автомат
3. Анализ конечного автомата для нашей строки

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

Добрый день! Ввиду того, что люди спрашивают как загрузить Embox на отладочные платы на базе STM32, мы решили выпустить этот рецепт. Его можно рассматривать как дополнение к статье.

Описание будет для отладочной платы STM32F7-Discovery, но в целом оно верно и для других серий STM32 (по ходу будут приведены уточнения для STM32F4).

Ставшая уже традиционной, новая подборка вопросов и задач от SpiceIT.



Среди отобранных задач — вопросы и алогоритмические задачи, задаваемые соискателям на должность разработчика в Samsung. Предлагаем Вам попробовать решить их самостоятельно и оценить, готовы ли Вы подавать резюме в Samsung :)

Вступление.

Часто в документации от Qt встречается термин Pimpl. Кроме того, те кто хоть немного копался в исходном коде Qt часто видел такие макросы как: Q_DECLARE_PRIVATE, Q_D. А также встречал так называемые приватные заголовочные файлы, название которых заканчивается на "_p.h".
В этой статье я попробую приоткрыть ширму за всей это структурой.

Pimpl, что это?

Pimpl — Pointer to private implementation. Это одно из названий паттерна программирования. Еще его называют чеширским котом — «Cheshire Cat» (это название мне больше нравится). В чем суть этого паттерна? Основная идея этого паттерна — это вынести все приватные члены класса и, в не которых случаях, функционала в приватный класс.
Отсюда название «чеширский кот» — видно только улыбку, а все остальное остается невидимым, но оно несомненно есть :-) Кто не помнит этого замечательного кота, может обратится к первоисточнику, к книге Льюиса Кэрролла «Алиса в стране чудес». Очень интересная книга, особенно если читать в оригинале.
Что это дает?

Многие программисты не понаслышке знают о том, что программа на языке C и C++ собирается очень долго. Кто-то решает эту проблему, сражаясь на мечах во время сборки, кто-то — походом на кухню «выпить кофе». Это статья для тех, кому это надоело, и он решил, что пора что-то предпринять. В этой статье разобраны различные способы ускорения сборки проекта, а также лечение болезни «поправил один заголовочный файл — пересобралась половина проекта».

Вот какие заголовки мелькали в финансовых новостях в последние недели:

«Цена биткоина наконец дошла до 10 000 $!» — The Economist, 28 ноября 2017
«Биткоин перешагнул рубеж в 10 000 $!» — CNBC, 28 ноября 2017 года
«БИТКОИН ВЗЛЕТЕЛ ВЫШЕ 11 000 $!» — The Guardian, 29 ноября 2017 года


Не успели эти известия толком перекипеть на новостных порталах, как буквально через сутки цена уже выросла до $11,500. К моменту, когда вышли заметки про одиннадцать тысяч, он уже успел упасть до девяти. А потом, пока журналисты лихорадочно дописывали последние строчки про «обвал биткоина», снова вернулся на уровень 11 000 $ за BTC.

И это не первый такой случай.

Мы уже сталкивались с чем-то подобным в 2013 году. Когда стоимость биткоина подошла к отметке в 1000 $, пресса подняла шумиху, что привело к образованию «пузыря». В январе 2013 биткоин уходил примерно за 15 $, к апрелю цена подскочила до 266 $, а затем обвалилась до 50 $. К ноябрю она превысила 1 200$, достигнув максимума в 1 242 $ на Mt.Gox. За тот год биткоин вырос почти в сто раз – это на порядок больше, чем десятикратный подъем, через который он прошел в 2017 году.

Графики выглядят почти одинаково, а новостные заголовки вообще слово в слово. Просто припишите нолик.

Пресса любит такие вещи, потому что люди читают их с большим интересом. Истории о том, как кто-то купил старый компьютер за 25 баксов и обнаружил на нем 5 000 биткоинов, или случайно выбросил жесткий диск с 7 500 биткоинами и долго искал его на свалке, или отдал 10 000 биткоинов за две пиццы, раздувают ажиотаж и приносят деньги.

Насколько трудно может быть измерить производительность простой функции, вроде вот этой?

// func.cpp
void benchmark_func(int* a)
{
	for (int i = 0; i < 32; ++i)
		a[i] += 1;
}

Ну, давайте просто завернём её в какой-нибудь микробенчмарк, вызовем её много-много раз (для усреднения результатов) и посмотрим, что получится, да? Ну ладно, мы можем ещё посмотреть на сгенерированные инструкции просто чтобы убедиться, что компилятор чего-то там не «наоптимизировал». Мы можем также провести несколько разных тестов, чтобы убедиться, что именно цикл является узким местом. Ну и всё. Мы понимаем, что мы измеряем, да?

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

// func.cpp
void foo(int* a)
{
	for (int i = 0; i < 32; ++i)
		a[i] += 1;
}

void benchmark_func(int* a)
{
	for (int i = 0; i < 32; ++i)
		a[i] += 1;
}

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