В этом посте мы попробуем применить технику символьного выполнения на примере символьной ВМ KLEE для решения простого ASCII-лабиринта. Как вы думаете, сколько верных решений мы сможем найти?

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

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

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

Кэш память процессора используется для уменьшения времени простоя процессора при обращении к RAM.

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

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



Так вот суть кэширования состоит в разбиении RAM на кэш-линии и отображении их на кэш-линии кэш-памяти. Возможно несколько вариантов такого отображения.

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

Дисклеймер

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

Преамбула

Многие наверное слышали, что есть такая вещь как GStreamer, или же видели как Ubuntu и ей подобные дистрибутивы предлагают установить различные пакеты, в названии которых содержится «gstreamer» при первой попытке воспроизвести mp3 или какой-нибудь иной файл с «не свободным» форматом медиаданных. Так вот, речь пойдет именно об этой библиотеке.

Введение

GStreamer — мощный фреймворк для построения мультимедийных приложений, который перенял идеи «video pipeline» от Oregon Graduate Institude, а так же что-то взял из DirectShow. Данный фреймворк позволяет создавать приложения различных уровней сложности, начиная от простого консольного плеера (можно воспроизвести какой-нибудь файл прям из терминала без написания какого-либо кода), заканчивая полноценными аудио/видео плеерами, мультимедийными редакторами и прочими приложениями.

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

Далее в посте:

1. Оптимизация «в глазок»
2. Стандартные функции
3. Вывод в ELF
4. Как это работает?
5. Что получилось?

File names are infinite in length, where infinity is set to 255 characters.
--Peter Collinson: The Unix File System

Итак, у нас есть программа на п-коде, и в её распоряжении неограниченное количество регистров (т.е. 255). Число регистров у реального процессора куда меньше (предположим, четыре). Что будем делать?

Далее в посте:

1. Разбор п-кода
2. Время жизни
3. Реализация
4. Простые оптимизации
5. Расщепление версий
6. Работа с памятью
7. Что получилось?

Первый этап — разбор синтаксиса нашего джей-скрипа — пройден; подбираемся к генерации кода.

Начнём с генерации п-кода (промежуточного переносимого псевдокода) — нечто вроде «абстрактного машинного языка». Его выбирают так, чтобы

• его было легко генерировать;
• его было легко обрабатывать.

Обработка п-кода — это, как правило, его переработка в исполнимый машинно-зависимый код. Тем не менее, можно ограничиться лишь генерацией п-кода, и объявить его готовой скомпилированной программой. Запуск такой программы будет, по сути, интерпретацией п-кода. У этого подхода всё больше и больше сторонников; так что и мы для начала ограничимся компиляцией в п-код.

Далее в посте:

1. Выбор кода
2. Компиляция
3. Выполнение
4. Backpatching

До сих пор занимались восходящим синтаксическим разбором. Какие ещё есть варианты?
Отложим бизона в сторону, и вернёмся к теории.

Далее в посте:

1. Идея
2. Воплощение
3. Холивар
4. Бэктрекинг

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

Чтобы неполноценность нашего языка была понятна уже из названия, назовём его JSkrip.

Далее в посте

1. Синтаксис
2. Грамматика
3. Парсер
4. Синтаксическое дерево
5. Pretty-printing

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

Далее в посте:

1. Компиляция грамматики
2. Двухступенчатый парсер
3. Что у него внутри?
4. Конфликты в грамматике
5. Как это работает?

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

Далее в посте:

1. Магазинный автомат
2. Формальные грамматики
3. LR-парсинг

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

Далее в посте:

1. Выбор кода
2. Загрузчик
3. Изменения в п-коде
4. Генерация
5. Что получилось?

Добро пожаловать в Главу 4 учебника «Создание языка программирования с LLVM». Предыдущие главы (1-я, 2-я и 3-я) описывали реализацию простейшего языка программирования и добавление в него ​​поддержки генерации LLVM IR. В этой главе описаны две новых техники: добавление поддержки оптимизатора и добавление поддержки JIT-компилятора. Эти дополнения продемонстрируют как получить хороший, эффективный код для нашего языка программирования Kaleidoscope.

В компании Intel разрабатывается довольно много ПО для моделирования различных физических процессов. В некоторых из них мы используем пакет OpenFOAM, и в этом посте я постараюсь дать краткое описание его возможностей.
Что такое OpenFOAM? Это, пользуясь термином Википедии, открытая (GPL) платформа для численнного моделирования — в первую очередь для моделирования, связанного с решением уравнений в частных производных методом конечных объемов, и в самую первую очередь — для решения задач механики сплошных сред.
КПДВ: эволюция двух несмешивающихся жидкостей разной плотности, изначально разделенных тонкой перегородкой (пример «lockExchange» из стандартной поставки OpenFOAM). Переходные цвета обозначают ячейки сетки, где присутствует доля и той, и другой жидкости (более точно: при симуляции используется метод объёма жидкости).

Сломанный ноутбук или планшет бывает жалко выкидывать, тем более если у него сгорела материнка/видеокарта/процессор, а дисплей в полном порядке. В этом случае есть выход: можно подключить ЖКИ от мобильного устройства как второй/третий экран к персональному компьютеру. Лучше всего для этого подходит ЖК-дисплей от последних моделей iPad с размером 9,7" и разрешением сторон 2048х1536. Студент Варшавского университета Анджей Суровец (Andrzej Surowiec) сумел подключить retina-дисплей от iPad к ПК через DisplayPort на максимальном разрешении.

Типичная ситуация — в проекте существует некий модуль. Модуль развивается, становится самостоятельным элементом и копируется в другой проект. Потом еще один проект. И еще.
В каждом проекте модуль обновляется и улучшается, и, в какой-то момент, становится не понятно, где актуальная версия. Да ладно, «не понятно где актуальная версия»! Вполне возможно, что в каждом проекте у модуля будут свои модификации, в которые будет достаточно сложно привести в порядок для использования в следующем проекте.
Вполне можно ограничиться созданием отдельного репозитория для модуля, например на GitHub или Bitbucket. Но добавлять репозиторий как субмодуль для GIT — это путь к приключениям.
Но можно пойти дальше, и создать на основе такого модуля npm-пакет. Работать с такими пакетами очень просто. Установить npm-пакет можно с помощью команды npm install, а обновить с помощью npm update.

Вступление

Самой распространенной операционной системой для смартфонов на сегодняшний день является Android. Но не только этот факт подогревает интерес к ней. Открытость, возможность что-то настроить, подкрутить, и, естественно, сломать тоже в немалой степени способствуют увеличению популярности этой платформы. Я попробую поделиться опытом, как устроена эта операционная система, а так же рассмотреть систему безопасности. Всем, кому интересно, добро пожаловать! В этой статье я рассмотрю безопасность на уровне ядра.

Доброго времени суток, Хабрапользователи!

Визуальная криптография [1] впервые была введена Мони Наором и Ади Шамиром в 1994 году [3]. Она используется для шифрования изображения или текста, представленного в виде изображения. Основная идея модели визуальной криптографии состоит в разбиении исходного изображения на несколько шифрованных («теневых» изображений, shadow images), каждое из которых не дает никакой информации об исходном изображении кроме, может быть, его размера (изображение – а-ля «белый шум»). При наложении шифрованных изображений друг на друга, можно получить исходное изображение. Таким образом, для декодирования не требуется специальных знаний, высокопроизводительных вычислений и даже компьютера (в случае, если распечатать теневые изображения на прозрачных пленках). В случае использования этого алгоритма в компьютерных системах, наложить все части изображения друг на друга можно используя логические операции AND, OR, XOR (или установив более высокую степень прозрачности в графическом редакторе). Данная технология обладает криптоустойчивостью за счет того, что при разделении исходного изображения на множество шифроизображений происходит случайным образом.

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


В последние несколько лет интенсивно развивается новое направлении в теории восстановления изображений — слепая обратная свертка (Blind Deconvolution). Появилось достаточно много работ по этой теме, и начинается активное коммерческое использование результатов.
Многие из вас помнят конференцию Adobe MAX 2011, на которой они как раз показали работу одного из алгоритмов Blind Deconvolution: Исправление смазанных фотографий в новой версии Photoshop
В этой статье я хочу подробнее рассказать — как же работает эта удивительная технология, а также показать практическую реализацию SmartDeblur, который теперь тоже имеет в своем распоряжении этот алгоритм.
Внимание, под катом много картинок!