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

Казалось бы, ничего не остается, как купить у соответствующих товарищей credit card with US billing понуро закрыть страницу магазина, уйдя на поиски более дружелюбного продавца, как тут вы замечаете знакомый шильдик PayPal, который повесил владелец сайта, приглашая всех приобрести его товар, заплатив максимально удобным для вас способом. И вот она, победа, вы деловито шествуете по страницам чекаут процесса, как вдруг осознаете, что продавец малого того, что не принимает православные карты к оплате, так еще и на настолько обнаглел, что отправляет свой товар только в пределах своей отчизны, забивая на весь мир и связанные с международной отправкой проблемы.

Если получить адрес для получения посылок в США уже давно не проблема, то вот как получить американский адрес, доступный для выбора при оплате PayPal? Да, система PayPal не позволяет штатным образом владельцам аккаунтов, зарегистрированных в стране, отличной от США, добавить американский адрес доставки.

Но на каждую хитрую жопу, как известно…

Эта статья посвящена тестированию возможности использования технологии Intel Processor Trace (Intel PT) для записи трассы в System Management Mode (SMM) режиме. Работа была выполнена в рамках Summer Of Hack 2019. Автор работы: @sysenter_eip.

Большинство использованных инструментов написаны другими людьми (в частности @d_olex, @aionescu). Результат представляет собой лишь объединение имеющихся инструментов с целью получения трассы исполнения кода в режиме SMM для одной конкретной материнской платы. Однако, материал может быть интересен для тех, кто захочет повторить это для своей платформы или просто интересуется работой SMM.

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



Сразу предупрежу: под катом нет «серебряной пули», которая умножит на 0 проблему хаоса в файлах на ваших устройствах. И даже ни строчки про нейросети, распознавание чего-либо кем-либо и прочие нанотехнологии. Под катом — немного текста и дубовая табличка, которую ещё и заполнять придётся вручную =) Но которая работает.

Перед каждым сервисом, генерирующим хотя бы 1 Мбит/сек трафика в интернете возникает вопрос: «Как? по TCP или по UDP?» В прикладных областях, в том числе и платформах доставки уже сложились предпочтения и традиции принятия подобных решений.

По идее, если бы, к примеру, однажды один ленивый разработчик не попробовал развернуть свой ML на Python (потому что только его и знал), мир скорее всего никогда не проникся бы такой любовью к презренному «супер-джава-кодерами» языку. А сегодня слабости этого языка в прошлом контексте применения безоговорочно обеспечивают ему первенство в развертывании и запуске многочисленных майнерских А/Б.

Сравнивать можно многое: ARM с Intel, iOS и Android, а Mortal Kombat с Injustice. И нарваться на космический холивар, поэтому вернемся к теме доставки огромных объемов разноформатного контента.

Десять лет назад все были абсолютно уверены, UDP — это что-то про негарантированную доставку. Если нужен надежный протокол — это TCP. И вопреки традициям в этой статье мы будем сравнивать такие, кажущиеся несравнимыми вещи, как TCP и UDP.


Осторожно, под катом 99 иллюстраций и схем и все важные.

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

Задача 391. Perfect Rectangle

Given N axis-aligned rectangles where N > 0, determine if they all together form an exact cover of a rectangular region.
Each rectangle is represented as a bottom-left point and a top-right point. For example, a unit square is represented as [1,1,2,2]. (coordinate of bottom-left point is (1, 1) and top-right point is (2, 2)).

Example 1: rectangles = [
[1,1,3,3],
[3,1,4,2],
[3,2,4,4],
[1,3,2,4],
[2,3,3,4]]
Return true. All 5 rectangles together form an exact cover of a rectangular region.
…
Example 3:rectangles =
[ [1,1,3,3],
[3,1,4,2],
[1,3,2,4],
[3,2,4,4]]
Return false. Because there is a gap in the top center.

Предисловие

Не так давно пришлось поработать с упрощением полигональной цепи (процесс, позволяющий уменьшить число точек полилинии). В целом, данный тип задач очень распространен при обработке векторной графики и при построении карт. В качестве примера можно взять цепь, несколько точек которой попадают в один и тот же пиксель – очевидно, что все эти точки можно упростить в одну. Некоторое время назад я практически ничего не знал об этом от слова «совсем», в связи с чем, пришлось в быстром темпе восполнять необходимый багаж знаний по этой теме. Но каково было мое удивление, когда в интернете я не нашел достаточно полных руководств по этому вопросу… Мне приходилось отрывками искать информацию с совершенно разных источников и, после проведенного анализа, выстраивать все в общую картину. Занятие не из самых приятных, если честно. Поэтому мне хотелось бы написать цикл статей, посвященных алгоритмам упрощения полигональной цепи. Как раз-таки начать я решил с наиболее популярного алгоритма Дугласа-Пекера.

Не так давно я прочёл фантастический роман «Задача трёх тел» Лю Цысиня. В нём у одних инопланетян была проблема — они не умели, с достаточной для них точностью, вычислять траекторию своей родной планеты. В отличии от нас, они жили в системе из трёх звёзд, и от их взаимного расположения сильно зависела «погода» на планете — от испепеляющей жары до леденящего мороза. И я решил проверить, можем ли мы решать подобные задачи.

Одна городская легенда гласит, что создатель сахарных пакетиков-палочек повесился, узнав, что потребители не разламывают их пополам над чашкой, а аккуратно отрывают кончик. Это, разумеется, не так, но если следовать такой логике, то один британский любитель пива "Гиннесс" по имени Уильям Госсет должен был не просто повеситься, но и своим вращением в гробу уже пробурить Землю до самого центра. А все потому, что его знаковое изобретение, опубликованное под псевдонимом Стьюдент, уже десятки лет используют катастрофически неправильно.

Рисунок выше приведен из книги С. Гланц. Медико-биологическая статистика. Пер. с англ. — М., Практика, 1998. — 459 с. Мне неизвестно, проверял ли кто-нибудь на статистические ошибки расчеты для этой диаграммы. Однако и ряд современных статей по теме, и мой собственный опыт говорят о том, что t-критерий Стьюдента остается самым известным, и оттого — самым популярным в применении, по поводу и без.

Введение

Умножение матриц — это один из базовых алгоритмов, который широко применяется в различных численных методах, и в частности в алгоритмах машинного обучения. Многие реализации прямого и обратного распространения сигнала в сверточных слоях неронной сети базируются на этой операции. Так порой до 90-95% всего времени, затрачиваемого на машинное обучение, приходится именно на эту операцию. Почему так происходит? Ответ кроется в очень эффективной реализации этого алгоритма для процессоров, графических ускорителей (а в последнее время и специальных ускорителей матричного умножения). Матричное умножение — один из немногих алгоритмов, которые позволяет эффективно задействовать все вычислительные ресурсы современных процессоров и графических ускорителей. Поэтому не удивительно, что многие алгоритмы стараются свести к матричному умножению — дополнительная расходы, связанные с подготовкой данных, как правило с лихвой окупаются общим ускорением алгоритмов.

Так как реализован алгоритм матричного умножения? Хотя сейчас существуют множество реализаций данного алгоритма, в том числе и в открытых исходных кодах. Но к сожалению, код данных реализаций (большей частью на ассемблере) весьма сложен. Существует хорошая англоязычная статья, подробно описывающая эти алгоритмы. К моему удивлению, я не обнаружил аналогов на Хабре. Как по мне, этого повода вполне достаточно, чтобы написать собственную статью. С целью ограничить объем изложения, я ограничился описанием однопоточного алгоритма для обычных процессоров. Тема многопоточности и алгоритмов для графических ускорителей явно заслуживает отдельной статьи.

Процесс изложения будет вестись ввиде шагов с примерами по последовательному ускорению алгоритма. Я старался писать максимально упрощая задачу, но не более того. Надеюсь у меня получилось…

«В режиме трассировки программист видит последовательность выполнения команд и значения переменных на данном шаге выполнения программы, что позволяет легче обнаруживать ошибки» — сообщает нам Википедия. Сами будучи поклонниками Linux, мы регулярно сталкиваемся с вопросом, какими именно инструментами её лучше осуществлять. И хотим поделиться переводом статьи программиста Хонгли Лая, который рекомендует bpftrace. Забегая вперёд, скажу, что заканчивается статья лаконично: «bpftrace — это будущее». Так чем же он так впечатлил коллегу Лая? Развёрнутый ответ под катом.

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

UPD 14.10.2023
Эта статья немного устарела. Здесь можно узнать, как использовать готовые списки IP-адресов, что не совсем актуально. Актуальная статья с маршрутизацией по доменам: https://habr.com/ru/articles/767464/

UPD 16.10.2022

• Исправлены конфиги для Openwrt 22
• Добавлен community список
• В скрипт добавлена проверка загрузки файлов. Которая решает проблему, если при старте устройства не удалось сразу загрузить списки
• DNSCrypt изменён на DNSCrypt v2

UPD 15.03.2023

• Добавлена логика для работы с доменами, используются список доменов из community
• Изменена проверка загрузки файлов в скрипте
• В Ansible playbook теперь можно выбрать определённые списки

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

Часть 2: Поиск и исправление ошибок

Чем отличается от подобных материалов?

• Реализация на чистом OpenWrt
• Использование WireGuard
• Конфигурация роутера организуется с помощью конфигов OpenWrt, а не кучей в одном скрипте
• Предусмотрены ситуации при рестарте сети и перезагрузке
• Потребляет мало ресурсов роутера: подсети содержатся в ipset, а не в таблицах маршрутизации. Что позволяет развернуть это дело даже на слабых устройствах
• Автоматизация конфигурации с помощью Ansible (не требуется python на роутере)

В этой статье мы смоделируем и исследуем протокол двухфазного коммита с помощью TLA+.

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

Проблема двухфазного коммита

Транзакция проходит через диспетчеры ресурсов (RM). Все RM должны договориться, будет транзакция завершена или прервана.

Менеджер транзакций (TM) принимает окончательное решение: коммит или отмена. Условием для коммита является готовность к коммиту всех RM. В противном случае транзакцию следует отменить.

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

Меня зовут Сергей Трифонов, я работаю в команде Real-Time Map Reduce в Яндексе. Мы разрабатываем платформу для обработки потока данных в реальном времени с секундным и субсекундным временем отклика. Платформа доступна для внутренних пользователей и позволяет им выполнять прикладной код над постоянно поступающими потоками данных. Я попытаюсь сделать краткий обзор основных концепций человечества на тему анализа latency за последние сто десять лет, и сейчас мы попробуем понять, что именно про latency можно узнать, применяя теорию массового обслуживания.

Александр Крижановский ( krizhanovsky, NatSys Lab.)

По Сети уже давно бегает эта картинка, по крайней мере, я ее часто видел на Фейсбуке, и появилась идея рассказать про нее:

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

Один из моих читателей привёз мне пять ламп трёх российских производителей.

Содержание курса

• Статья 1: алгоритм Брезенхэма
• Статья 2: растеризация треугольника + отсечение задних граней
• Статья 3: Удаление невидимых поверхностей: z-буфер
• Статья 4: Необходимая геометрия: фестиваль матриц
  
  • 4а: Построение перспективного искажения
  • 4б: двигаем камеру и что из этого следует
  • 4в: новый растеризатор и коррекция перспективных искажений
• Статья 5: Пишем шейдеры под нашу библиотеку
• Статья 6: Чуть больше, чем просто шейдер: просчёт теней

Улучшение кода

• Статья 3.1: Настала пора рефакторинга
• Статья 3.14: Красивый класс матриц

---

Official translation (with a bit of polishing) is available here.

---

А что потом? Я разобрал весь материал!

В статьях 7 и 8 мы поговорим о программировании непосредственно под OpenGL. Есть ненулевая вероятность получить краткий курс OpenCL/CUDA в статьях 9+.

Удаление невидимых поверхностей

Знакомьтесь, это мой друг z-buffer головы абстрактного африканца. Он нам поможет убрать визуальные артефакты отбрасывания задних граней, которые у нас оставались в прошлой статье.



Кстати, не могу не упомянуть, что эта модель, которую я использую в хвост и в гриву, была любезно предоставлена замечательным Vidar Rapp.

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

последняя редакция статьи доступна на сайте makeloft.xyz

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

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

Перед прочтением статьи рекомендую посмотреть посты про splay-деревья (1) и деревья по неявному ключу (2, 3, 4)

Динамические деревья (link/cut trees) мало освещены в русскоязычном интернете. Я нашел только краткое описание на алголисте. Тем не менее эта структура данных очень интересна. Она находится на стыке двух областей: потоки и динамические графы.

В первом случае динамические деревья позволяют построить эффективные алгоритмы для задачи о поиске максимального потока. Улучшенные алгоритмы Диница и проталкивания предпотока работают за и соответственно. Если вы не знаете, что такое поток, и на лекциях у вас такого не было, спешите пополнить свои знания в Кормене.

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

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

Хочу поговорить об устройстве управления памятью (Memory Management Unit, MMU). Как вы, разумеется, знаете, основной функцией MMU является аппаратная поддержка виртуальной памяти. Словарь по кибернетике под редакцией академика Глушкова говорит нам, что виртуальная память — это воображаемая память, выделяемая операционной системой для размещения пользовательской программы, ее рабочих полей и информационных массивов.

У систем с виртуальной памятью четыре основных свойства:

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

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

К сожалению, по какой-то причине все вышеперечисленные товарищи недостаточно почтительно относятся к MMU, а их знакомство с виртуальной памятью обычно начинается и заканчивается изучением страничной организации памяти и буфера ассоциативной трансляции (Translation Lookaside Buffer, TLB). Самое интересное при этом остается за кадром.

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

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