Пусть мы хотим вычислить десятимиллионное число Фибоначчи программой на Python. Функция, использующая тривиальный алгоритм, на моём компьютере будет производить вычисления более 25 минут. Но если применить к функции специальный оптимизирующий декоратор, функция вычислит ответ всего за 18 секунд (в 85 раз быстрее):


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

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

Работая над очередным игровым (обучающим) проектом ПЛИС для платы Марсоход2 я столкнулся с тем, что мне явно не хватает места в кристалле. Кажется и проект не очень сложный, но моя реализация такова, что требует много логики. В принципе, это ерунда, дело-то житейское. Ну, если очень будет нужно, то можно выбрать ПЛИС с большей емкостью. Собственно мой проект — это игра «Жизнь», но реализованная в ПЛИС на языке Verilog HDL.

Про логику игры, рассказывать не буду, про нее и так написано уже достаточно.

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

Так вот. На моей плате стоит ПЛИС Cyclone III EP3C10E144C8 компании Альтера. 10тыс логических элементов. Сперва я думал, что смогу сделать двумерный массив клеток 128x64=8192 клетки. Не помещается. 64x64=4096 — то же не помещается в кристалл. Как же так. Я сумел вместить в ПЛИС только 32x16=512 клеток. Пичалька…

Размышления приводят меня к мысли, что возможно, в будущем, технология ПЛИС перерастет в нечто большее, чем программируемая логика. Вот об этом своем видении я хотел бы рассказать. Искушенному читателю сразу скажу, что многое далее написанное есть просто плод воображения и может быть даже бред.
Однако…

Рады сообщить, что в издательстве «Питер» вышли вторые тиражи книг: «Битва при черной дыре. Мое сражение со Стивеном Хокингом за мир, безопасный для квантовой механики» — Сасскинд Л. и «Теория струн и скрытые измерения Вселенной» — Шинтан Яу.

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

Серия постов [Неочевидные алгоритмы очевидных вещей] будет содержать алгоритмы действий, которые кажутся очевидными и простыми, но если задать себе вопрос «как это делается?», то ответ является далеко не очевидным. Разумеется, все эти алгоритмы можно найти в литературе. Под катом располагается алгоритм вычисления корня квадратного числа X.

Проглядывая книжку «Эффективное использование C++», Скотта Мейерса, которая ( и я никого не удивлю ) достойна всяческих похвал, меня очень тронуло, то с какой возбуждённостью, вдохновлённостью, трепетом ( может мне показалось? ) автор говорит о шаблонах и их возможностях. Приведу маленький кусочек:

Метапрограммирование шаблонов ( template metaprogramming — TMP ) — это процесс написания основанных на шаблонах программ на C++, исполняемых во время компиляции. На минуту задумайтесь об этом: шаблонная метапрограмма — это программа, написанная на C++, которая исполняется внутри компилятора C++…
Было доказано, что технология TMP предоставляет собой полную машину Тьюринга, то есть обладает достаточной мощь для любых вычислений...

Да уж… сердце забилось, в очередной раз удивился — только подумать — полная машина Тьюринга со всеми вытекающими последствиями… Как по мне, это просто невероятно и удивительно… хотя, кто его знает…

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

Давным-давно, когда трава была зеленее, а деревья выше, жил-был тролль, по имени Xenocephal. Жил он, в принципе, во многих местах, но мне повезло встретить его на одном форуме, где я, в то время, набирался ума-разума. Я уже не вспомню топика, в котором протекала беседа, но суть ее сводилась к тому, что Xenocephal пытался убедить всех окружающих, что Lisp (с его макросами) — всему голова, а C++, с его шаблонами, жалкое подобие левой руки. Также утверждалось, что наметапрограммировать в нем что-то сложнее набившего оскомину факториала не представляется возможным.

**Многие слышали о Кевине Митнике – иконе хакерского сообщества, но мало кто знает, что у крэкерского мира тоже есть своя икона – tHE kEYBOARD cAPER. Эта статья описывает период, когда его команда доминировала над всей cracking-сценой.

1. Детство
2. Первый ПК и первая BBS
3. Wolfenstein BBS и первый конфликт
4. Windows эра и первый рейд
5. Создание Phrozen Crew и Интернет
6. Самая большая команда в мире
7. Болезнь
8. Возвращение на сцену
9. Внезапная Смерть и CIA
10. Безработный
11. Эпилог
12. Послесловие переводчика

Детство

Я родился в Южной Африке, до сих пор здесь. Белый, 45+ лет (на данный момент — здесь и далее прим. Manny Calavera). Извините, я не скажу вам дату рождения или своё настоящее имя, но факт в том, что меня зовут tKC. :-) И да, я глухой и рос в школе для глухих детей, пока не попал в обычную в возрасте 13-ти лет, потому что моя речь была хорошо развита и моё состояние было немного «лучше», чем требовалось для специальных школ. Я не говорю со своими родителями на языке жестов, собственно, именно по этому я и общаюсь лучше остальных глухих, если вы понимаете о чём я. А еще я не говорю по-английски, потому что я вырос в среде, говорящей на Afrikaans, где читал по губам.

«Чем бы вы стали заниматься, зная, что у вас все получится?»

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

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

Под катом несколько искрометных видео на английском и транскрипт Выступления на TED (на руcском)

Как вы думаете, стоит ли признать 6 августа днём хакера?
(или днем социальной инженерии)

Кевин является выдающимся хакером и социальным инженером по следующей причине.
Он «хакнул систему» на метауровне. С точки зрения ТРИЗ он добился идеального конечного результата.
Кевин организовал все так, что если раньше за то, чем он занимался его преследовали, то теперь за то, чем он занимается стоят в очередь и платят деньги.

(на фото: Стив Возняк дарит Митнику компьютер Apple)

Еще один примечательный факт, что Кевин не поступал в университет, а учился по настоящим учебникам мануалам, которые скачивал с хакнутых компов.

Хронология ранних хаков Митника

12 лет

— первые мошенничества с телефоном;

15 лет

— подделка автобусных билетов;

16 лет

— взлом школьной компьютерной сети;
— взлом радиосвязи Макдональдса;

17 лет

— первое незаконное проникновение на территорию Pacific Telephone;
— «диссертация по взлому RSTS/E»;
— «подруга» Кевина совершила взлом, воспользовавшись данными Митника, а обвинили его;
— проникновение в здание COSMOS;
— первый условный срок;

18 лет

— взлом Университета Южной калифорнии, арест;

25 лет

— первый тюремный срок — 12 месяцев, запрет пользоваться телефоном, под предлогом того, что Митник может взломать NORAD;

28 лет

— взлом телефона Novatel (с использованием соц. инженерии), что позволяло менять Митнику ESN.

Под катом несколько видео-интервью Митника, история о взломе радиосвязи Макдональдса и ссылки на интересные статьи.

«Митник, умеешь с телефонами обращаться?» — спросил надзиратель.
«Не особо — ответил я, — но умею вставить вилку в розетку. Вы не волнуйтесь, я быстро учусь».
Два дня я устанавливал и ремонтировал тюремные телефоны. К.Митник «Призрак в сети»

Пару дней назад мне пришла в голову идея привить школьникам вкус к прекрасному и приобщить их к прочтению написанию статей на Хабре.
Дело происходит прямо сейчас, я сижу в лагере в классе робототехники (лагерь необычный, а с блэкджеком и курсами по олимпиадному программированию, разработкой приложений и робототехнике) и пишу эти строки.
Обсуждая темы информационной безопасности, взлома Wi-Fi сетей, 3d-принтеры, Arduino, брутфорс и асимметричное шифрование, выяснилось, что многие (школьники, школьницы, вожатые и преподаватели) активно читают Хабр и пользуются им как справочным пособием для своих проектов.
Идея совместного написания статьи возникла у меня тогда, когда при обсуждении самых прикольных статей за последнее время ребята сослались на статью, где «один знакомый проник на конференцию Митника». Пришлось признаться, что это про моего знакомого и, в развитие темы этичного хакерства, я предложил молодежи попробовать свои силы в написании интересных постов.



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

Цели:
— разжигание интереса к Хабру, информационной безопасности, социальной инженерии;
— показать как то, что раньше считалось нереальным становится реальным (ближайшая зона роста);
— вдохновить молодых авторов на написание статей на Хабре;
— вдохновить/вовлечь ветеранов Хабра на помощь начинающим авторам (джедаи-падаваны).

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

План работ:
первый этап — совместное написание статьи на Хабр, перевод статьи из «Time» и ролика Митника «How to Troll the FBI», а так же дополнить пост интересными моментами из книги про взаимоотношения Митника и ФБР
второй этап — каждый описывает одно событие для второй части статьи «История хакерских взломов информационных систем» (первая часть — История хакерских взломов информационных систем (1903-1971))
третий этап — самостоятельное написание своей статьи под моим присмотром (примерные темы: "Google Code Jam. Интервью с финалистом — Романом Удовиченко (10-е место)", «Будущее робототехники. Интервью с экспертами ТРИК», «Кузница белорусских программистов» и т.д.)
UPD 28.08.2014 первый «Саурон» появился.

Результаты первого этапа под катом.

Команда Visual Studio выпустила агрегированный набор примеров кода Visual Studio 2013 SDK Samples, который содержит множество готовых для использования, тестирования и изучения проектов кода расширяющих возможности среды разработки.



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

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

Build Progress Bar – VS 2013

Пакет для Visual Studio, который предлагает новый инструмент “Build Progress” показывающий индикатор на WPF отображающий прогресс построения решения в среде разработки.

Caret Fish Eye – VS 2013

Расширение, которое визуально масштабирует линии текста кода, уменьшая их в зависимости от удаления от текущего положения указателя.

Code Sweep – VS 2013

Этот пример позволяет пользователю указать набор терминов для поиска указав набор XML-файлов, содержащих определения.

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

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

Случалось ли Вам писать шаблон функции, который должен быть инстанциирован для определённого набора типов и больше ни для чего? Если нет, то эта статья врядли покажется Вам интересной. Но если Вы всё ещё здесь, то тогда начнём.

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

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

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

typedef TypeList<int,char,bool,string, EmptyList> MyTypeList. 

О том, что такое список типов можно почитать у А.Александреску в «Современное проектирование на С++», а пример реализации — здесь.
Под катом самопальная имплементация(такая же как и у тысяч других, наверное). Она, мне лично, больше нравится, так как позволяет писать
typedef TypeList<int,char,bool,string, EmptyList> MyTypeList;
вместо классической записи
typedef TypeList<int,TypeList<char,TypeList<bool,TypeList<string, EmptyList>>>> MyTypeList;

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

"type":
[
	{
		"id": 1,
		"type": "one",
	},
	{
		"id": 2,
		"type": "two",
	},
	{
		"id": 6,
		"type": "three",
	}
]

Но в тоже время в кодe хочется использовать структуры типа:

enum Type
{
	one,
	two,
	three
};

Далее в теле статьи будут приведены несколько вариантов решения.

В игре Prehistorik 2 не предусмотрены сейвы, но на каждом уровне есть (болтается в воздухе в некотором месте уровня) код уровня. Есть два режима прохождения, Beginner и Expert, код также определяет режим. При старте игры можно начать с первого уровня, а можно ввести код и попасть сразу на соответствующий уровень. На одном и том же компьютере с неизменным окружением коды не меняются, но на разных компьютерах коды, вообще говоря, разные, так что коды, найденные при прохождении и тщательно выписанные на бумажку, станут совершенно бесполезны в другом окружении. Поэтому вместо бумажки лучше иметь программу, которая пишет коды для конкретного окружения. Готовый результат: genpass.com, представляет из себя DOS-программу, которая должна запускаться в том же окружении, что и игра. Альтернативный вариант попасть на нужный уровень из экрана ввода кода: ввести три кода ADDE C0DE F00D либо DEAD C0DE F00D, каждый из трёх кодов сам по себе неверен, но при вводе их в таком порядке четвёртый код — номер уровня от 1 до 10, плюс 10 для режима Expert, приводит сразу на запрошенный уровень.

Под катом — процесс исследования. Требуется знание ассемблера x86 хотя бы на уровне «читаю со словарём».

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

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

Для более или менее адекватного восприятия статьи потребуется минимальные знания ассемблера (его будет много) а так-же навыков работы с отладчиком.

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

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

В качестве реципиента, по совету одного достаточно компетентного товарища, я выбрал немножко старый (но не потерявший актуальности, в силу качества исполнения) keygenme от небезызвестного Ms-Rem.

Вот первоначальная ссылка, где он появился: http://exelab.ru/f/index.php?action=vthread&forum=1&topic=4732
А потом он попал вот сюда: http://www.crackmes.de/users/ms_rem/keygenme_by_ms_rem/
Где данному keygenme был выставлена сложность 8 из 10 (*VERY VERY* hard).
Хотя, если честно, это слегка завышенная оценка — я бы поставил в районе 5-6 баллов.

Пожалуй, начнем.

Недавно понадобилось поставить новую wifi карточку стандарта ac в свой ноутбук Lenovo x230, в котором есть whitelist для wlan карточек. Ниже опишу свои изыскания по отключению whitelist'а.

Любителям этой замечательной игры посвящается...

… Если таковые еще есть. Впрочем, я уверен, что не все так плохо и Crysis не поглотил мозг человечества целиком и окончательно.
Так вот, вышеупомянутые любители старых игр и в частности одной замечательной игры 92 года могут помнить, что система сохранений в игре сделана в несколько приставочном духе: по уровням разбросаны (иногда в довольно неожиданных и труднодоступных местах) коды, которые во времена MS-DOS старательно записывались на бумажечку и хранились, как сокровище. Код, введенный в главном меню, позволял начать соответствующий уровень со стартовой позиции.
Soshite, в наше время появилась, в некотором роде, проблема для тех, кто хотел бы поиграть в Prehistorik 2. А именно — необходимость эмулировать игру в Dosbox: далеко не у всех есть возможность найти на свалке или, что еще гораздо реже, вытащить с антресолей заботливо хранящийся там 486-й.
Дело в том, что при генерации кодов игра использует переменные окружения BIOS. Как это эмулируется в Dosbox, я не разбирался, знаю достоверно, что при каждом новом запуске эмулятора коды в игре другие. Соответственно, бумажка с кодами становится бесполезной, а возможность приятного и ненапрягающего прохождения игры сводится практически на нет: полностью игру можно пройти только за один присест. Возможно, это решается детальной настройкой Dosbox. Но это менее интересно, чем небольшое копание в исполняемом файле игры.