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

Некриптографические хеш-функции

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

Критерии, которые важны для некриптографических хеш-функций:

Вступление

Всем доброго времени суток! В этой статье я хотел бы еще раз поднять тему защиты персональных данных (далее будем обзывать их — ПДн), а также тему защиты от регуляторов. Пик дебатов на тему защиты ПДн давно прошел. Приходились эти пики как правило на приближение очередного «самого последнего срока» ввода 152-ФЗ в полную силу. В итоге «самый последний срок» наступил, активные дебаты стихли, но закон «О персональных данных» живет, регуляторы устраивают проверки и наказывают нарушителей. Поэтому тема будет еще долго актуальна.

Сразу оговорюсь, что в этой статье в основном будет информация организационного характера, нежели техническая. «А зачем такая информация нужна нам?» — спросит читатель хабра. Объясняю: так уж получилось, что начальники как крупных, так и не очень организаций не любят выстраивать длинные логические цепочки и вникать в суть вопроса, который лежит далеко от их компетенции. Поэтому при возникновении необходимости обеспечения защиты персональных данных строится вполне логичная по их мнению взаимосвязь: «Защита персональных данных» -> «Защита информации» -> «Информационные технологии» -> «Взвалить вопрос защиты ПДн на IT-шников». И пофигу, что в этом вопросе львиную долю можно поручить юристам и кадровикам, но как говорится в бородатом анекдоте: «кому не нравится грузить люминь, пойдет грузить чугуний».


Типичный пример разглашения ПДн специальной категории (сведения об интимной жизни)

Задача: в массиве длиной N найти элемент, который повторяется больше N/2 раз.

Казалось бы, чего тут думать? Возьмём Dictionary<значение элемента, число появлений>, за один проход по массиву сосчитаем появления каждого элемента, потом выберем из словаря искомый элемент. Решение за O(N), куда может быть ещё быстрее?

Есть один нюанс: для словаря нам потребуется O(N) дополнительной памяти — в несколько раз больше размера исходного массива, и это при реализации словаря хоть хэш-таблицей, хоть деревом. Что будем делать, если наша цель — обработка сигнала неким устройством с маленькой памятью? Массив — замеры уровня сигнала, из которых один — «настоящий» передаваемый уровень, а остальные — шум и помехи. Неужели придётся для определения «настоящего» уровня возиться с хэш-таблицами и деревьями?

К счастью, нет: достаточно O(1) дополнительной памяти, и по-прежнему одного прохода по массиву.

Всем здравствуйте!
В этом посте я постараюсь убедить вас в том, что добавить поддержку Wi-FI к своему устройству на микроконтроллере можно абсолютно без проблем. И для этого не надо ни курочить свой любимый роутер и подпаиваться к выводам отладочного uart'а, ни ставить переходник usb-uart (что, конечно выход).
Я расскажу о двух модулях фирмы WizNet: WizFi220.

Вместо предисловия

Компания WizNet основана в 1998 в Корее и занимается производством сетевых решений. Спектр того, что компания производит, широк. Это и микроконтроллеры на ядре 8051 со встроенный PHY-контроллером, и отдельные SPI-управляемые контроллеры Ethernet, и модули Wi-FI, и макетки почти к каждой микросхеме.
Про первые два вида я мало чего знаю, поскольку с ними не работал. А про Wi-Fi довольно много.
Кому интересно — прошу под кат.

Представляю вашему вниманию заключительную статью из трилогии «Восстановление расфокусированных и смазанных изображений». Первые две вызвали заметный интерес — область, действительно, интересная. В этой части я рассмотрю семейство методов, которые дают лучшее качество, по сравнении со стандартным Винеровским фильтром — это методы, основанные на Total Variaton prior.
Также по традиции я выложил новую версию SmartDeblur (вместе с исходниками в open-source) в которой реализовал этот метод. Итоговое качество получилось на уровне коммерческих аналогов типа Topaz InFocus. Вот пример обработки реального изображения с очень большим размытием:

Тестирование является важной составляющей процесса разработки приложения. Для Android тестирование особенно важно, так как устройства сильно отличаются друг от друга:

• Размером и разрешением экрана.
• Версией Android.
• Форм-фактором.
• Системой команд процессора.
• Наличием фронтальной камеры, NFC, внешней клавиатуры, и т.д.

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

Недавняя статья на Хабре напомнила мне о том, сколько времени я провел пытаясь написать свой плагин к Intellij IDEA. Официальная документация по созданию плагинов хоть и есть, но её неожиданно мало.

В этой статье я расскажу о том, как зарегистрировать свой тип файла в Intellij IDEA. Это может понадобиться если вы пишете свой языковой плагин или хотите запускать внешний редактор для файлов. В качестве примера возьмем файлы Apache JMeter (установка самого JMeter не требуется).

Около полутора лет назад на Хабре был размещен пост про уникальные карты китайского поисковика Baidu (для тех, кто не видел, вот он: http://habrahabr.ru/post/115107/). Я был поражен тем, насколько кропотливо, детально и красиво эти карты сделаны, поэтому однажды мы, вместе с группой товарищей, решили разобраться в процессе создания Baidu-карт и сделать собственные карты всего мира, которые выглядели бы так же круто. Под катом много картинок, раскрытие секрета Baidu-подобных карт и то, что получилось у нас.

В предыдущей статье я рассказывал, как можно реализовать алгоритм k-means на c# с обобщенной метрикой. В комментах можно почитать обсуждение того, насколько целесообразно использовать разные метрики, о математической природе использования разных метрик и тому прочее. Мне тогда хотелось привести красивый пример, но не было под рукой подходящих данных. И вот сегодня я столкнулся с задачей, которая хорошо иллюстрирует преимущества использования расстояния Махаланобиса в k-means кластеризации. Подробности под катом.

Думаю, никому не нужно объяснять, насколько широко в играх (и не только) используются гексагональные сетки. Как для заданной шестиугольной ячейки найти координаты ее центра и вершин — достаточно очевидно. Обратное же преобразование (т.е. поиск ячейки, в которую попала данная точка с координатами x и y) уже не столь тривиально. О нём и пойдет речь в данном топике.

Добрый день.

После размещения вопроса о том интересно ли будет почитать об автоматизации процесса игры во Flood-it. Было получено несколько положительных отзывов, в связи с чем публикую данную статью.

Введение

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


Рисунок 1: игровое поле.

Необходимо реализовать алгоритм, для выбора оптимального цвета для заливки. Подробности можно прочитать реализации под катом.

Здравствуй Хабр!

Adobe Photoshop CS5 (Save For Web) — 53,8 КБ	Image Catalyst (Xtreme) — 46,0 КБ

Image Catalyst — программа для комплексной оптимизации/сжатии изображений формата PNG и JPEG без потери качества в рамках того же формата.

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

На многих устройствах с большим разрешением экрана приложение падает c ошибкой
AndroidRuntime: java.lang.OutOfMemoryError: bitmap size exceeds VM budget

Проблема в том, что память для Bitmap, а также для SurfaceView резервируется из общей кучи процесса. Лимит размера кучи — невелик, как правило немногим больше 10Мб. И задается этот лимит при сборке системы.

Попытки улучшить ситуацию урезанием формата пикселя с 32 бит до 16 не слишком помогают. Проблема просто вылезает позже — например, при открытии окна поверх SurfaceView (видимо, при этом создается еще один Bitmap размером с экран).

Ограничение размера графических буферов программы в 3-4 экрана — это до обидного мало! Попробуем исправить такую несправедливость.

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

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

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

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

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

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

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

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

1. С какой стати писать компиляторы?
2. Общий план
3. Анализ текста
4. Практический пример
5. Как это работает?

В данной статье мы попытаемся описать свой опыт работы с AIDL в Android IPC.
В ней содержится пример приложения с сервисом, который запущен в отдельном процессе.

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

Сегодня я постараюсь объяснить генетические алгоритмы проще и нагляднее, а заодно рассказать вкратце о прототипе очень простого JavaScript-фреймворка для распределенных генетических вычислений degas.js. В двух словах – degas.js запускает генетический алгоритм в виде «треда» в браузере клиента используя web workers и обменивается информацией о полученных в ходе эволюции индивидуумах с сервером и другими клиентами с помощью web sockets. Сервер использует node.js.

Degas.js пока в супер-зародышевом состоянии, функционал еще примитивен, а код некрасив, но если кто-то захочет присоединиться к разработке – было бы здорово.

Для определения страны по IP необходимы специальные базы данных, состоящие из диапазонов IP адресов и соответствующих им стран. Обычно такие базы данных распространяются в виде CSV или SQL файлов для использования в СУБД, либо бинарных файлов специального формата.

Для проведения тестирования была выбрана февральская база GeoLite Country, бесплатная версия GeoIP Country от MaxMind.

В тестировании приняли участие несколько популярных решений и мой «велосипед» на эту тему.

Здравствуйте, уважаемое сообщество!
На Хабре уже много сказано слов о различных устройствах автоматизации, начиная от простых Arduino, заканчивая промышленными многопроцессорными системами. Я же хочу закрасить очередное белое пятно на карте хабро-автоматики статьей о промежуточных устройствах — программируемых реле, на примере микропроцессорных устройств Easy производства корпорации Eaton (Moeller).
Прошло уже достаточно много времени с моего первого знакомства с данным типом устройств, но по-прежнему, эти «электронные малыши» остаются незаменимыми помощниками для реализации широкого спектра инженерных и бытовых задач.

Рад представить вашему вниманию еще одну крохотную, но полезную open-source-утилиту своего авторства — Simplify.js.



Simplify.js — очень быстрая реализация упрощения ломаных линий на JavaScript. Изначально написав ее для Leaflet (библиотеки для интерактивных карт), после небольшого эксперимента по оптимизации захотелось выпустить ее в качестве отдельной библиотеки без зависимостей, которую можно использовать как в браузере, так и на серверных платформах, таких, как Node.js, и применять и для 2D, и для 3D-точек.

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