Картинка для привлечения внимания — xkcd

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

Радуясь, что еще не забыли курс ассемблера, вы кое-как написали программу палочкой на песке. Среди уцелевших вещей каким-то чудом оказалась распечатка документации на контроллер (хорошо, что вы еще не успели пустить её на растопку!), и программу удалось перевести в машинные коды. Осталась самая ерунда — прошить её в контроллер. Но в радиусе 500 километров нет ни одного программатора, не говоря уже о компьютерах. У вас только источник питания (батарея из картошки кокосов) и пара кусков провода.

Как же прошить МК фактически голыми руками?

Многие мои друзья и знакомые крутят пальцем у виска или задаются вопросом: не жмёт ли мне череп, когда узнают, что я пишу драйвера под Linux. Слово “драйвер” окутано каким-то почти мистическим смыслом, и постичь Дао его написания способны лишь избранные гуру.
К счастью это не так. Не знаю, как обстоят дела с написанием драйверов под другие операционные системы, в т.ч. и наиболее популярные, но под linux, вне зависимости от аппаратной архитектуры драйвера пишутся очень просто. Для написания драйвера необходимы базовые знания языка си, представление о работе ОС линукс (базовые), понимание того, что мы хотим получить, желание чтения документации и исходных кодов, ну и усидчивость. Всё.
Вы хотите посмотреть как написать драйвер для своего устройства? Тогда ныряйте под кат!

Не так давно на Хабре была статья «Коды Грея и задачи перебора». Статья эта скорее, математическая, нежели программистская, и мне, как простому программисту, читать её было невыносимо тяжело. Но сама тема мне знакома, поэтому я решил описать её своим взглядом, а так же рассказать о том, как использовал её в решении задачи о ранце.


КДПВ: задача о ранце на живом примере

Предыстория

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

Задача почему-то запала мне в душу. Вернувшись домой, я быстро накатал решение: наивный перебор всех возможных сумм с выбором наилучшего. Сочетания я получал, перебирая все N-разрядные двоичные числа и беря суммы тех исходных чисел, которым соответствуют единицы. Но я с огорчением обнаружил, что при количестве элементов начиная где-то с 30, программа работает очень долго. Оно и не удивительно, ведь время работы такого алгоритма — n*2ⁿ (количество сочетаний, умноженное на длину суммы).

Дональд Кнут (известный тем, что его книги никто не читает) пишет, что хотя первый двоичный поиск был опубликован в 1946 году, первый двоичный поиск без багов был опубликован только в 1962.

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

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

Будучи высококвалифицированным исследователем, я потратил немало времени на продвижение науки вперёд. Но я родился на Юге и искренне убеждён, что прогресс — это выдумка, и что нужно готовиться к Судному дню, к жатве того, что мы посеяли и к появлению быстрых зомби, медленных зомби, и даже вежливых зомби, которые обращаются к вам «сэр» или «мадам», но в итоге пытаются съесть ваш мозг дабы заполучить ваши навыки. Когда нагрянет революция, нужно быть готовым; поэтому в моменты тишины и покоя, когда я не произвожу очередной прорыв в науке, я размышляю над тем, что же я буду делать, когда прогноз погоды изменится на «РЕКИ КРОВИ ЦЕЛЫЙ ДЕНЬ ДО СКОНЧАНИЯ ВРЕМЁН».

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

Но! Но… Самым важным членом моей банды будет системный программист, ибо в гоббсовском кошмаре невероятных масштабов умеющему отладить драйвер устройства или распредёленную систему человеку можно доверять; системный программист видел ужасы Вселенной и понимает безысходность бытия. Системный программист писал драйверы для устройств, прошивку которых создавал то ли пьяный ребёнок, то ли трезвый карась. Системный программист отлавливал проблему с сетью через восемь машин, три часовых пояса и с дружеским визитом в Омск, откуда ее перенаправили в левое переднее копыто той лошади, что избавила Трою от перенаселения.¹ Системный программист читал исходники ядра для лучшего понимания процессов мироздания и видел комментарий «И ЭТО РАБОТАЕТ ЛОЛ» в коде планировщика, и не смеялся он, но плакал; и отправил он патч ядра для восстановления баланса Силы и устранения инверсии приоритетов, что приводила к зависанию MySQL. Системный программист знает, что делать, когда общество падёт, потому что он уже живет в мире, где царит беззаконие.

Этот алгоритм является улучшенным алгоритмом поиска пути A*. JPS ускоряет поиск пути, “перепрыгивая” многие места, которые должны быть просмотрены.  В отличие от подобных алгоритмов JPS не требует предварительной обработки и дополнительных затрат памяти. Данный алгоритм представлен в 2011 году, а в 2012 получил высокие отклики. Что из себя представляет данный алгоритм и его реализацию можно прочитать дальше в статье.

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

К сожалению, даже на официальной вики почти не возможно найти каких либо примеров использования SDL2.x, что уж говорить о рунете. Пытаясь разобраться, я нашел всего лишь пару статей, которые не покрыли и трети моих вопросов.
SDL 2.x существенно отличается от 1.x и даже, если в прошлом вам приходилось с ним работать — теперь вы рискуете ничего не понять.

Сегодня мы напишем простенькую программу выводящую на экран фон и зумируемый спрайт персонажа перемещающегося с помощью WASD и стрелок. + разберемся как в SDL работать с мышкой.

2 года назад тут писали про самодельный компьютер с процессором на отдельных интегральных микросхемах — BMOW1. С архитектурной точки зрения он был весьма продвинут, однако крайне сложен для повторения.

Автор BMOW1 (Стив Чемберлин — Steve Chamberlin) разработал компьютер Nibbler, состоящий всего из 17 микросхем. Причем — процессор там также собран на дискретной логике.

Что-ж, посмотрим что у него внутри.

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

В данном посте я расскажу о наиболее интересных командах, которые могут быть очень полезны при работе в консоли. Однозначных критериев определения какая команда лучше другой — нет, каждый сам для своих условий выбирает лучшее. Я решил построить список команд на основе наиболее рейтинговых приемов работы с консолью от commandlinefu.com, кладовой консольных команд. Результат выполнения одной из таких команд под Linux приведен на картинке. Если заинтересовало, прошу под кат.

В этой статье я даю краткий обзор того, как применять библиотеку lock-free структур данных libcds. В реализацию я углубляться здесь не буду, — это просто взгляд извне, взгляд со стороны пользователя библиотеки.

Библиотека libcds имеет свою точку зрения на многие известные структуры данных. Отчасти это объясняется целевой областью – lock-free структуры данных довольно минималистичны по набору предоставляемых методов, — отчасти желанием выйти за ограничения и решения стандартной библиотеки STL. Что из этого получилось – решать пользователям libcds.

Кому интересно – добро пожаловать под кат

От переводчика: вдохновившись циклом статей, я решил попробовать свои силы в SDL. Да вот незадача, каких-либо толковых уроков по SDL версии 2.0 на русском языке найти мне не удалось. Это и подтолкнуло меня к переводу замечательной серии туториалов Twinklebear, в оригинале доступных тут.

Добро пожаловать!

Цель данных уроков — познакомить вас с основами SDL 2.0 и гейм-дева на С++. Подразумевается, что у читателя есть некоторый опыт программирования на С++ и минимальные знания массивов, векторов, управляющих структур, функций и указателей.

Если вы испытываете трудности при разборе кода в примерах, воспользуйтесь одной из книг, представленных в этом чудесном списке на StackOverflow.

Если вы хотите увидеть полный исходник или же скачать ресурсы для уроков, то все это можно получить на GitHub’е. Но не копируйте!

Также документация по SDL 2.0 доступна для чтения в этой вики.

В сырцах разных авторов видел я разные варианты вечного цикла. Чаще всего мне встречались следующие:

while (true) {
...
}

и

for (;;) {
...
}

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

Дополняем цикл статей по УГО для различных САПР-схемотехники. В данном топике описывается процесс создания компонента УГО для KiCad.



KiCad — распространяемый под лицензии GNU GPL программный комплекс класса EDA с открытыми исходными текстами, предназначенный для разработки электрических схем и печатных плат.

Внимание! Под катом трафик!

Как только я заинтересовался lock-free алгоритмами, меня стал мучить вопрос – а откуда взялась необходимость в барьерах памяти, в «наведении порядка» в коде?
Конечно, прочитав несколько тысяч страниц руководств по конкретной архитектуре, мы найдем ответ. Но этот ответ будет годен для этой конкретной архитектуры. Есть ли общий? В конце концов, мы же хотим, чтобы наш код был портабелен. Да и модель памяти C++11 не заточена под конкретный процессор.
Наиболее приемлемый общий ответ дал мне мистер Paul McKenney в своей статье 2010 года Memory Barriers: a Hardware View of Software Hackers. Ценность его статьи – в общности: он построил некоторую упрощенную абстрактную архитектуру, на примере которой и разбирает, что такое барьер памяти и зачем он был введен.
Вообще, Paul McKenney – известная личность. Он является разработчиком и активным пропагандистом технологии RCU, которая активно используется в ядре Linux, а также реализована в последней версии libcds в качестве ещё одного подхода к безопасному освобождению памяти (вообще, о RCU я хотел бы рассказать отдельно). Также принимал участие в работе над моделью памяти C++11.
Статья большая, я даю перевод только первой половины. Я позволил себе добавить некоторые комментарии, [которые выделены в тексте так].

Введение

Прочитав недавнюю статью Загрузка ОС Linux без загрузчика, понял две вещи: многим интересна «новинка», датируемая аж 2011 годом; автор не описал самого основного, без чего, собственно, и работать ничего не будет в некоторых случаях. Также была ещё одна статья, но либо она уже устарела, либо там опять таки много лишнего и недосказанного одновременно.

А конкретно, был упущен основной момент — сборочная опция ядра CONFIG_EFI_STUB. Так как в последних версиях U(lu/ku/edu/*etc*)buntu эта опция по умолчанию уже включена, никаких подозрений у автора не появилось.
Насколько мне известно, на текущий момент она включена в дистрибутивах указанных версий и выше: Arch Linux, Fedora 17, OpenSUSE 12.2 и Ubuntu 12.10. В комментах ещё упомянули, что Debian с ядром 2.6 умеет, но это не более, чем бэкпорт с последних версий. На этих дистрибутивах пересобирать вообще ничего не нужно! А ведь на других CONFIG_EFI_STUB, скорее всего, либо вообще отсутствует, т. к. опция доступна только с ядра версии 3.3.0 и выше, либо выключена по умолчанию. Соответственно, всё, описанное ниже, справедливо для ядра, собранного с опцией CONFIG_EFI_STUB.

Итак, что же такое Linux Kernel EFI Boot Stub?

Общая информация

А ни что иное, как… «exe-файл»!

Небольшая преамбула

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

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

• Устранить предвзятое мнение относительно невозможности использования *nix систем для профессиональной деятельности отличной от работы программиста или администратора сети;
• Показать, что за счет модульности архитектуры *nix систем и использования программного обеспечения с открытым исходным кодом, следующего стандартам POSIX, многие операции, на которые в привычном рабочем окружении я ранее тратил часы а то и дни, могут весьма просто автоматизироваться, либо решатся за считанные минуты;
• Поделиться опытом и показать, какой инструментарий выбирают специалисты (в частности, какой выбрал я в процессе поисков) и какие решения могут быть наиболее приемлемы для тех или иных задач.

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



_{Это тиражный результат. Прошу прощения за качество снимка, была только настольная лампа под рукой, если кто хочет посмотреть оригинал, вот буклет про GPS аудиогид в PDF формате с редуцированным разрешением растровой графики.}

Ниже я расскажу о ключевых этапах и проблемах, которые пришлось решать в процессе.

Думаю, почти каждый сталкивался с проблемой печати больших pdf файлов. Недавно и мне пришлось напечатать мануал в 600 страниц. Так как документ целиком состоит из текста не очень то хотелось печатать все 300 листов а4. В поисках решения наткнулся на статью от rapkasta.

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

Введение

Здесь по возможности я постараюсь как можно проще и детальнее ответить на вопрос:
«Как можно загрузить Linux (на примере ubuntu) без использования загрузчика такого как GRUB 2, iELILO»
Здесь не будет разбираться как запустить/установить Ubuntu в режиме [UEFI only]. Для этого обратитесь сюда help.ubuntu.ru/wiki/установка_дистрибутива_на_компьютер_с_efi
и сюда help.ubuntu.ru/wiki/lubuntu-osinstallation
Все действия будут производиться на уже работающей системе.