Всем хорошо известен алгоритм преобразования массива байт в строку base64. Существует большое количество разновидностей данного алгоритма с различными алфавитами, с хвостовыми символами и без. Есть модификации алгоритма, в котором длина алфавита равна другим степеням двойки, например 32, 16. Однако существуют и более интересные модификации, в которых длина алфавита не кратна степени двойки, такими являются алгоритмы base85, base91. Однако мне не попадался алгоритм, в котором алфавит мог бы быть произвольным, в том числе большей длины, чем 256. Задача показалась мне интересной, и я решил ее реализовать.

Сразу выкладываю ссылку на исходники и демо на js. Хотя и разработанный алгоритм имеет скорее теоретическое значение, я посчитал нужным описать детали его реализации. Практически его можно использовать, например, для случаев, когда меньшая длина строки актуальней, чем ее размер в байтах (например, в квайнах).

Аннотация переводчика

Мой топик должен восполнить некий пробел в теме «Чем грозит Heartbleed простому пользователю», благодарю FFF за пост: habrahabr.ru/post/219151

Уязвимости клиентов никто не отменял. Но если топовые платёжные сервисы реагируют в течение суток, то как долго ждать обновлений от производителя смартфона или, скажем, «умного» ТВ? Нехороший сайт сможет запросто выпотрошить память клиента — недопатченного браузера, смартфона, планшета, слишком умного телевизора, видео- или игровой приставки, и т.д. Всякое устройство, способное загружать веб-страницы (включая ваш домашний Linux), и при этом обрабатывающее конфиденциальные данные — это цель, и порой на долгие годы.
Даю вам перевод статьи Роба Ванденбринка (Rob VandenBrink) целиком, это не заняло много времени.

Добрый день.

Логи часто и абсолютно не заслуженно обделены вниманием разработчиков. И когда программистам необходимо пропарсить log-файлы, иногда с нескольких десятков серверов одновременно, задача эта ложится на системных администраторов и отнимает у них много времени и сил.

Поэтому, когда случаются проблемы и надо найти ошибку в логах какого-нибудь сервиса, все зависит от того, насколько силен админ и насколько программисты знают, что искать. А еще от того, отработал ли logrotate и не грохнул ли он старые данные…

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

Почему? Maxifier представляет собой SaaS-продукт с клиентами в США, Бразилии, в нескольких странах Европы и в Японии, так что у нас около сотни серверов, раскиданных по всему миру. Для оперативной работы нам необходимо иметь удобный доступ к логам наших приложений и быстрый поиск ошибок в них в случае проблем на сторонних сервисах/api, появления некорректных данных т.д. Кстати, похожей системой сборки логов пользуются The Guardian (одни из наших клиентов).

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

Речь сегодня пойдёт о генерации изображений с картой расстояний (Signed Distance Field). Данный вид изображений примечателен тем, что фактически позволяет получить «векторную» графику на видеоускорителе, причём даром. Одной из первых данный метод растеризации предложила компания Valve в игре Team Fortress 2 для масштабируемых декалей в 2007 году, но до сих пор он не пользуется особой популярностью, хотя позволяет рендерить прекрасного качества шрифты, используя текстуру всего 256х256 точек. Данный метод прекрасно подходит для современных экранов высокой чёткости и позволяет серьёзно сэкономить на текстурах в играх, он не требователен к железу и прекрасно работает на смартфонах.



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

Как же создавать такие изображения? Очень просто, ImageMagick позволяет сделать это одной командой:

convert in.png -filter Jinc -resize 400% -threshold 30% \( +clone -negate -morphology Distance Euclidean -level 50%,-50% \) -morphology Distance Euclidean -compose Plus -composite -level 45%,55% -resize 25% out.png

На этом можно было бы поставить точку, но так полноценного топика не получится. Что ж, под катом — описание быстрого алгоритма расчёта SDF, пример на C++ и немного шейдеров для OpenGL.

Каждый программист должен написать свою cms, framework, mmorpg. Именно этим мы и займемся.
Демо

Это руководство для WPF-разработчиков, стремящихся добиться максимально чёткой картинки в своих приложениях. Графическая система WPF до мозга костей векторная, но конечным результатом её работы по-прежнему является растр. Если не уделить этому факту должного внимания, можно столкнуться с различными сортами «мыла» — паразитными артефактами растеризации. В такой ситуации важно не терять присутствия духа, причины их возникновения вполне рациональны, а методы борьбы достаточно просты и эффективны.

В результате профилирования моей софтины я сделал вывод о необходимости оптимизации функции сравнения буферов.
Т.к. CLR не предоставляет стандартного способа сравнить два куска памяти, то функция была написан на скорую руку самостоятельно (лишь бы работало).
Погуглив по фразе «Best Way to Compare Byte Arrays in .Net», я пришёл в замешательство: в абсолютном большинстве случаев люди предлагали использовать либо LINQ, либо Enumerable.SequenceEqual(), что практически одно и тоже. Даже на StackOverflow это был самый популярный ответ. Т.е. катастрофически популярно заблуждение вида:

«Compiler\run-time environment will optimize your loop so you don't need to worry about performance.» Отсюда.

Именно оно впервые навело меня на мысль написать этот пост.
Я провёл сравнительное тестирование пяти способов сравнения буферов, доступных из C#, и на основании результатов тестирования дал рекомендации в выборе способа.
Кроме того, я декомпилировал некоторые функции, и проанализировал код, генерируемый JIT-компилятором для конфигурации x86, а так же сравнил машинный код, генерируемый JIT-компилятором, с машинным кодом функции CRT аналогичного назначения.

С радостью делимся второй частью докладов с конференции для тестировщиков LoveQA, которую мы проводили в середине февраля. Первую часть докладов можно посмотреть по ССЫЛКЕ.

Доклады

«Selenium тесты. От RC и одного пользователя к WebDriver, Page Object и пулу пользователей».
Виталий Котов, Badoo.





«Как мы разгоняли тесты — от баш-скриптов до облака».
Илья Relz Кудинов, Badoo.

Доброго времени суток, уважаемые хабравчане. За последнее время я увидел несколько интересных и полезных инструментов/библиотек/событий, которыми хочу поделиться с Хабром.

Colour Schemes

Репозиторий уже набрал более 4000 старов на GitHub. Автор проекта — Dayle Rees — один из участников команды Laravel PHP, где люди убеждены, что «код должен приносить удовольствие разработчикам, а не только пользователям, принимающим вашу трудную работу». Сolour Schemes на сегодняшний день это 56 различных тем для: Sublime Text (2 & 3), Sublime Text UI (2 & 3), Textmate, Coda 2, VIM, Jetbrains Editors (inc. PHPStorm), Google Code Prettify, Highlight.js и Xcode.

Понадобилось мне перехватывать вызовы GDS32.DLL. Решил написать прокси-dll.

Пишем исследовательский стенд

Первое, что нам нужно — это получить список всех экспортируемых функций из настоящей dll.
Сделаем это следующим кодом:

1.	program GetFuncsDll;
2.	  {$APPTYPE CONSOLE}
3.	  uses   Windows;
4.	  var
5.	    ImageBase: DWORD;                  //адрес образа dll
6.	    pNtHeaders: PImageNtHeaders;       // PE заголовок dll
7.	    IED: PImageExportDirectory;        // адрес таблицы экспорта
8.	    ExportAddr: TImageDataDirectory;   // таблица экспорта
9.	    I: DWORD;                          // переменная для цикла
10.	    NamesCursor: PDWORD;               // указатель на адрес имени функции
11.	    OrdinalCursor: PWORD;              // указатель на адрес номера функции
12.	    LIB_NAME:AnsiString;               // имя dll
13.	BEGIN
14.	  LIB_NAME:='MiniLib.dll';
15.	  loadlibraryA(PAnsiChar(LIB_NAME));
16.	  ImageBase := GetModuleHandleA(PAnsiChar(LIB_NAME));
17.	  pNtHeaders := Pointer(ImageBase + DWORD(PImageDosHeader(ImageBase)^._lfanew));
18.	  ExportAddr := pNtHeaders.OptionalHeader.DataDirectory[IMAGE_DIRECTORY_ENTRY_EXPORT];
19.	  IED := PImageExportDirectory(ImageBase+ExportAddr.VirtualAddress);
20.	  NamesCursor := Pointer(ImageBase + DWORD(IED^.AddressOfNames));
21.	  OrdinalCursor := Pointer(ImageBase + DWORD(IED^.AddressOfNameOrdinals));
22.	  For I:=0 to Integer(IED^.NumberOfNames-1) do begin
23.	    WriteLn(output,PAnsiChar(ImageBase + PDWORD(NamesCursor)^),'=',OrdinalCursor^ + IED^.Base);
24.	    Inc(NamesCursor);
25.	    Inc(OrdinalCursor);
26.	  end;
27.	Readln;
28.	end.
Листинг 1

Здесь трудностей вроде нет. Добираемся последовательно до таблицы экспорта (строка 19) указателей на массив имен(NamesCursor) и массива номеров(OrdinalCursor) и читаем функцию за функцией, имена и номера. Количество функций находится в поле NumberOfNames. Этот код был добыт на просторах интернета, потом доработан и упрощён.

Всем привет!
На Хабре появляются и появляются статьи о реализации Умного дома. Самой главной проблемой (ну или только для меня) получается включение/выключение света в санузле. Вроде и вещь не хитрая — а сколько есть вариантов. Прочитав статьи, в том числе, тут и тут, я подумал «А ведь все могло быть проще».

Введение

WPF — замечательная технология, которую, не смотря на все ее недостатки, очень люблю. Тем не менее, часто приходится писать не разметку, а код, который помогает первой работать как надо. Хотелось бы этого избегать и писать чистый XAML, но до сих пор ни одно мое приложение сложнее простого не обходилось без различных хелперов (классов-помощников), написанных на C#. К счастью, есть распространенные случаи, где можно одним хелпером решить сразу группу проблем.

Речь ниже пойдет о привязке в обычных свойствах визуальных элементов, которые не являются свойствами зависимостей (dependency properties). Штатными средствами WPF этого сделать не получится. Ко всему прочему, мы не можем узнать об изменениях такого свойства, кроме как подписавшись на специальное событие, что противоречит шаблону MVVM. Такие события для каждого свойства могут быть свои. Самый распространенный пример — это PasswordBox и его свойство Password. Так у нас сделать не получится:

<PasswordBox Password={Binding OtherProperty} />

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

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

Google использует своего «паука» FeedFetcher для кэширования любого контента в Google Spreadsheet, вставленного через формулу =image(«link»).

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

=image("http://example.com/image.jpg")

Google отправит паука FeedFetcher скачать эту картинку и закэшировать для дальнейшего отображения в таблице.

Однако если добавлять случайный параметр к URL картинки, FeedFetcher будет скачивать её каждый раз заново. Скажем, для примера, на сайте жертвы есть PDF-файл размером в 10 МБ. Вставка подобного списка в таблицу приведет к тому, что паук Google скачает один и тот же файл 1000 раз!

=image("http://targetname/file.pdf?r=1")
=image("http://targetname/file.pdf?r=2")
=image("http://targetname/file.pdf?r=3")
=image("http://targetname/file.pdf?r=4")
...
=image("http://targetname/file.pdf?r=1000")

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

Атакующему даже необязательно иметь быстрый канал. Поскольку в формуле используется ссылка на PDF-файл (т.е. не на картинку, которую можно было бы отобразить в таблице), в ответ от сервера Google атакующий получает только N/A. Это позволяет довольно просто многократно усилить атаку [Аналог DNS и NTP Amplification – прим. переводчика], что представляет серьезную угрозу.



С использованием одного ноутбука с несколькими открытыми вкладками, просто копируя-вставляя списки ссылок на файлы по 10 МБ, паук Google может скачивать этот файл со скоростью более 700 Мбит/c. В моем случае, это продолжалось в течение 30-45 минут, до тех пор, пока я не вырубил сервер. Если я все правильно подсчитал, за 45 минут ушло примерно 240GB трафика.

Эта очень короткая заметка на примере активации ключей в Steam описывает процесс автоматизации операций, выполняемых при помощи мыши и клавиатуры.

Допустим, вы купили несколько наборов игр Humble Bundle. Теперь у вас есть, например, 5 ключей для активации в Steam. А может быть 15 или даже 25. Вы очень не хотите активировать их вручную, потому что это слишком муторно: в клиенте Steam нужно каждый раз наводить курсор на меню «Games», щёлкать, потом наводить курсор на пункт меню «Activate a Product on Steam…», опять щёлкать, потом нажимать Enter, потом ещё раз Enter, и только затем наконец-то вводить ключ (а потом нужно подождать, ещё раз нажать Enter, затем Escape). А потом повторять то же самое для каждого последующего ключа. Как писал Леонид Каганов, стоило ли вообще ради такого «прогресса» спускаться с пальмы и брать в руки каменный топор?

В общем, вы решили этот процесс автоматизировать — тем более, что задача-то, на самом деле, очень простая. Для её решения нам потребуются консольные утилиты xdotool и xclip — убедитесь, что они установлены у вас в системе.

Перевод второй главы свободно распространяемой книги Building and Testing with Gradle

Задача (task) является основным компонентом процесса сборки в файле билда Gradle. Задачи представляют собой именованные наборы инструкций билда, которые Gradle запускает выполняя сборку приложения. При сравнении с другими билд-системами, задачи могут показаться знакомой абстракцией. Однако Gradle предоставляет более развитую модель, в отличие от той, которая вам уже может быть знакома. По сравнению с традиционными возможностями объявления операций билда, связанных зависимостями, задачи Gradle являются полнофункциональными объектами, которыми вы при желании можете управлять программно.

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

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

Сбалансированное дерево поиска является фундаментом для многих современных алгоритмов. На страницах книг по Computer Science вы найдете описания красно-черных, AVL-, B- и многих других сбалансированных деревьев. Но является ли перманентная сбалансированность тем Святым Граалем, за которым следует гоняться?

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

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

От переводчика: Это перевод второй статьи из цикла «Networking for game programmers». Мне очень нравится весь цикл статей, плюс всегда хотелось попробовать себя в качестве переводчика. Возможно, опытным разработчикам статья покажется слишком очевидной, но, как мне кажется, польза от нее в любом случае будет.
Первая статья — http://habrahabr.ru/post/209144/

---

Прием и передача пакетов данных

Введение

Привет, меня зовут Гленн Фидлер и я приветствую вас в своей второй статье из цикла “Сетевое программирование для разработчиков игр”.


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

А сейчас я собираюсь рассказать вам, как на практике использовать UDP для отправки и приема пакетов.

BSD сокеты

В большинстве современных ОС имеется какая-нибудь реализация сокетов, основанная на BSD сокетах (сокетах Беркли).

Сокеты BSD оперируют простыми функциями, такими, как “socket”, “bind”, “sendto” и “recvfrom”. Конечно, вы можете обращаться к этим функциями напрямую, но в таком случае ваш код будет зависим от платформы, так как их реализации в разных ОС могут немного отличаться.

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